论文阅读笔记:Towards Graph-level Anomaly Detection via Deep Evolutionary Mapping
https://www.craft.me/s/IOF4XCaapPtD55
- 从一个图网络集合中找出存在异常的那几个,不是时序化的检测
动机:
- 【数据层面->学习representation的时候用了anomaly aware 的loss】已有的用图表示学习的异常检测方法准确性的问题(引文),尤其是节点和图层级的异常检测,其中一个重要原因是图的异常很罕见,异常与否的数据分布十分不均衡
- 【学习能力问题->要跨着图学】仅仅使用网络自己的节点信息不足以学习到全局inter-graph 的信息
- 【特征空间中图的分布问题->graph mapping】在某些空间中,有无异常的图应当被明显的边界分开
文中给出的几个重要定义:
- Graph set and Node set 图/节点集合:
- candidate
- graph mapping 图映射
- 问题
总体思路:
- 处理不平衡的数据分布,正常的图表示学习(消息传递,GCN、GAT),获得节点向量。区别在于这里使用异常感知anomaly aware的目标函数来训练GNN。由此获得了intra信息
- 衡量它们与图的相似度,找到信息量最大的k个节点作为candidate
- 优化candidate集合
- 用优化后的candidate集合将所有图网络映射到一个新的特征空间,在这个空间上,异常和非异常(线性可分)?
细分流程:
- 基于消息传递的GNN,用于获得节点的intra表示,此时仍缺乏inter信息。目标函数: “异常感知”:\mathbb{G}_0和\mathbb{G}_1 分别是异常图集合和正常图集合,\phi() 表达了一个图是正常和异常的概率【文中是这么说的,但实际上应该为要么是异常要么是正常的概率吧】。L是交叉熵,衡量该结果跟真实标签的差距。(应该都是1维)
- Graph mapping 操作,用于获得inter信息。将图级别的映射到一个新空间,这个空间中,异常与非异常能被分的很开。具体如下:
- 将G给encode到h(一个新的feature space)h_{\mathcal{G_i}}^m \in R^{|C_i^t|} ,可见维度跟C有关(与candidate数量有关?)。h的组成如下:
- s(·)是相似度函数,衡量Gi和节点j的相似度,
- 通过图映射,可以根据他们与candidate的相似性进行聚类
- candidate selection and optimization 作用是让有无异常的图有着明确边界
- Informative node selection 由于正常的图在图set中占大多数,所以不适用节点集V的所有节点进行图映射,而是只考虑与正常图最相似的前k个节点。可以减少计算和存储成本,缓解维数灾难。GampAD通过余弦相似度从正常图中选择前k个节点。 其中计算j和Gi的相似度得分是: 对每个节点计算它对每个图的相似度,并将得分求和作为该节点的最终得分,取得分最高的k个作为初始candidate集合C_{init}
- differential (差分) evolutionary candidate optimization 目的是优化candidate集合。给定一个candidate集合,可以用一个对角阵I描述它,在此之上,如I \in R^{N \times N}矩阵,如果v_e在candidate中,则I_{ee} = 1 ,否则为0
- Initialization:不是很懂(最开始随机生成了多个I,对应多个candidate C,那此前的相似度计算步骤又是干什么的)
- Evaluation:通过binary SVM将每个图判别为异常/正常,然后进行打分 y是预测或真实的label
- Updating 根据C^t 获得C^{t+1}的过程
实验和数据集
数据集
数据集名称 | 来源 | 备注 | 链接 |
---|---|---|---|
KKI | Brain network | https://github.com/GRAND-Lab/graph_datasets#5functional-brain-network-analysis-data-brain | |
OHSU | Brain network | 同上 | |
AIDS | Biochemistry 生物化学 | 以下均在https://chrsmrrs.github.io/datasets/docs/datasets/ 可以找到 | |
MUTAG | Biochemistry 生物化学 | ||
Mutagenicity | Biochemistry 生物化学 | ||
NCI1 | Biochemistry 生物化学 | ||
PROTEINS | Biochemistry 生物化学 | ||
IMDB-BINARY | social network | ||
REDDIT-BINARY | social network |
对比方法
方法 | 方法概述 | code availibility |
---|---|---|
WWL | representative graph kernel-based method | WWL (https://github.com/BorgwardtLab/WWL). |
g-U-Nets | GNN, SOTA | g-U-Nets (https://github.com/HongyangGao/Graph-U-Nets). |
SAGPool | GNN, SOTA | SAGPool (https://github.com/inyeoplee77/SAGPool). |
DIFFPOOL | GNN, SOTA | DIFFPOOL (https://github.com/RexYing/diffpool). |
GMT | GNN, SOTA | GMT (https://github.com/JinheonBaek/GMT). |
OCGIN | graph level anomaly detection | OCGIN (https://github.com/LingxiaoShawn/GLOD-Issues). |
OCGTL | graph level anomaly detection | OCGTL (https://github.com/boschresearch/GraphLevel-AnomalyDetection). |
GLocalKD | graph level anomaly detection | GLocalKD (https://github.com/RongrongMa/GLocalKD). |
iGAD | graph level anomaly detection | iGAD (https://github.com/graph-level-anomalies/iGAD/tree/main). |
GCN | baseline | |
GAT | baseline |
结果对比(部分)
评价指标是标准的P、R、F1
评论区