论文阅读笔记：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 图映射
• 问题

总体思路：

1. 处理不平衡的数据分布，正常的图表示学习（消息传递，GCN、GAT），获得节点向量。区别在于这里使用异常感知anomaly aware的目标函数来训练GNN。由此获得了intra信息
2. 衡量它们与图的相似度，找到信息量最大的k个节点作为candidate
3. 优化candidate集合
4. 用优化后的candidate集合将所有图网络映射到一个新的特征空间，在这个空间上，异常和非异常（线性可分）？

细分流程：

1. 基于消息传递的GNN，用于获得节点的intra表示，此时仍缺乏inter信息。目标函数： “异常感知”：$$\mathbb{G}_0$$和$$\mathbb{G}_1$$ 分别是异常图集合和正常图集合，$$\phi()$$ 表达了一个图是正常和异常的概率【文中是这么说的，但实际上应该为要么是异常要么是正常的概率吧】。$$L$$是交叉熵，衡量该结果跟真实标签的差距。（应该都是1维）
2. 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的相似性进行聚类
3. candidate selection and optimization 作用是让有无异常的图有着明确边界
   1. Informative node selection 由于正常的图在图set中占大多数，所以不适用节点集V的所有节点进行图映射，而是只考虑与正常图最相似的前k个节点。可以减少计算和存储成本，缓解维数灾难。GampAD通过余弦相似度从正常图中选择前k个节点。 其中计算j和Gi的相似度得分是： 对每个节点计算它对每个图的相似度，并将得分求和作为该节点的最终得分，取得分最高的k个作为初始candidate集合$$C_{init}$$
   2. differential (差分) evolutionary candidate optimization 目的是优化candidate集合。给定一个candidate集合，可以用一个对角阵$$I$$描述它，在此之上，如$$I \in R^{N \times N}$$矩阵，如果$$v_e$$在candidate中，则$$I_{ee} = 1$$ ，否则为0
   3. Initialization：不是很懂（最开始随机生成了多个I，对应多个candidate C，那此前的相似度计算步骤又是干什么的）
   4. Evaluation：通过binary SVM将每个图判别为异常/正常，然后进行打分 y是预测或真实的label
   5. 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