大纲

根据算法模型的检测级别图异常检测任务大体上分为三类：

在上述分类下可以根据图数据类型可以进一步区分，主要包括：① 静态图：简单图，属性图 ② 动态图

异常子图检测

在现实生活中，异常现象可能是与他人串通或共同行动以获得更多利润。当数据用图表示时，这些异常及其相互作用通常会形成可疑的子图结构。

与异常点和异常边检测不同，异常子图中的点或者边单独而言属于正常，但是整体而言是异常情况。

传统方法

静态图

假设：异常子图通常表现出明显不同的属性分布。

  • [SDM 2014] gAnomaly [1]
  • [SDM 2016] AMEN [2]

动态图

  • [ICDM 2008] [3]

    开山之作，定义动态图中异常子图检测问题。

  • [KDD 2018] SpotLight [4]

    探索动态图中的 sudden changes，并识别与这些变化相关的异常子图。

  • [SDM 2013] NetSpot [5]

  • [KDD 2017] DenseAlert [6]

    利用人工提取的特征和点异常密集子图，这些子图已经进化出与其它部分明显不同的特征。

  • [NIPS 2013] LESS [7]

    利用各种图扫描统计信息进行异常子图检测。

  • [INFOCOM 2018] dGraphScan[8]

    针对网络结构不变但节点属性随时间变化的动态图中异常子图的检测问题，提出了一种非参数检测方法。

DNN-based

  • [ICDM 2018] DeepFD [9]

    针对二分异质图学习用户的异常感知表示，使同簇中的可疑用户将在向量空间中靠近，而良性用户距离较远。DBSCAN 聚类发现异常簇。

    DeepFD 模型

  • [IJCNN 2019] FraudNE [10]

    与 DeepFD 不同，FraudNE 将两种类型的节点编码到一个共享的潜在空间中，其中属于同一密集块的可疑 users 和 items 彼此非常接近，而其他人则均匀分布。

异常图检测

图级别的异常检测方法主要目标是在图序列/集合/数据库中检测集合中偏离正常分布的图，主要应用在化学分子图检测或者脑图序列中。

Node/Edge/SubGraph-Level 的方法主要是在单个图中检测对象，因此不能直接用于检测 Graph-Level 的异常点。

传统方法

  • [KDD 2016] StreamSpot [11]

    通过使用图核度量图的成对相似性，然后基于聚类的方法来检测异常图。

  • [CIKM 2018] ChangeDAR [12]

    检测由异常节点组产生的异常图信号。

DNN-based

主要思想是编码图的完整信息用于异常图检测。

  • [IJCAI 2018] DeepSphere [13]

    首先利用 LSTM+AE 对图快照进行编码至隐空间，然后采用单分类器 Deep-SVDD 学习超球面覆盖正常的样本。

GNN-based

整体思路架构如下所示：

GNN-based 模型

  • [SIGIR 2021] UPFD[14]

    将新闻建模为树形结构的传播图，其中根节点表示新闻片段，其他节点表示共享根新闻的用户。然后使用 GNN 模块来融合新闻和用户间的特征进行分类。

  • [2020] GIN + DeepSVDD [15]

NRL-based

上述仅代表目前个人统计的图异常检测领域的部分方法，后续学习补充…

  1. A probabilistic approach to uncovering attributed graph anomalies ↩︎

  2. Scalable anomaly ranking of attributed neighborhoods ↩︎

  3. Spotting significant changing subgraphs in evolving graphs ↩︎

  4. Spotlight: Detecting anomalies in streaming graphs ↩︎

  5. Netspot: Spotting significant anomalous regions on dynamic networks ↩︎

  6. Densealert: Incremental dense-subtensor detection in tensor streams ↩︎

  7. Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic ↩︎

  8. An efficient framework for detecting evolving anomalous subgraphs in dynamic networks ↩︎

  9. Deep structure learning for fraud detection ↩︎

  10. Fraudne: A joint embedding approach for fraud detection ↩︎

  11. Fast memory-efficient anomaly detection in streaming heterogeneous graphs ↩︎

  12. Changedar: Online localized change detection for sensor data on a graph ↩︎

  13. Deep into hypersphere: Robust and unsupervised anomaly discovery in dynamic networks ↩︎

  14. User preference-aware fake news detection ↩︎

  15. On Using Classification Datasets to Evaluate Graph-Level Outlier Detection: Peculiar Observations and New Insights ↩︎

  16. graph2vec: Learning distributed representations of graphs ↩︎

  17. Hunt for the unique, stable, sparse and fast feature learning on graphs ↩︎