NormanZyq
发布于 2023-09-04 / 111 阅读
0
0

论文阅读笔记:Towards Graph-level Anomaly Detection via Deep Evolutionary Mapping

论文阅读笔记:Towards Graph-level Anomaly Detection via Deep Evolutionary Mapping

https://www.craft.me/s/IOF4XCaapPtD55

  • 从一个图网络集合中找出存在异常的那几个,不是时序化的检测

动机:

  • 【数据层面->学习representation的时候用了anomaly aware 的loss】已有的用图表示学习的异常检测方法准确性的问题(引文),尤其是节点和图层级的异常检测,其中一个重要原因是图的异常很罕见,异常与否的数据分布十分不均衡
  • 【学习能力问题->要跨着图学】仅仅使用网络自己的节点信息不足以学习到全局inter-graph 的信息
  • 【特征空间中图的分布问题->graph mapping】在某些空间中,有无异常的图应当被明显的边界分开

Image.png

文中给出的几个重要定义:

  • Graph set and Node set 图/节点集合:
  • candidate
  • graph mapping 图映射
  • 问题

Image.png

总体思路:

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

细分流程:

  1. 基于消息传递的GNN,用于获得节点的intra表示,此时仍缺乏inter信息。目标函数: Image.png “异常感知”:\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的组成如下: Image.png
    • s(·)是相似度函数,衡量Gi和节点j的相似度, Image.png
    • 通过图映射,可以根据他们与candidate的相似性进行聚类
  3. candidate selection and optimization 作用是让有无异常的图有着明确边界
    1. Informative node selection 由于正常的图在图set中占大多数,所以不适用节点集V的所有节点进行图映射,而是只考虑与正常图最相似的前k个节点。可以减少计算和存储成本,缓解维数灾难。GampAD通过余弦相似度从正常图中选择前k个节点。 其中计算j和Gi的相似度得分是: Image.png 对每个节点计算它对每个图的相似度,并将得分求和作为该节点的最终得分,取得分最高的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将每个图判别为异常/正常,然后进行打分 Image.png y是预测或真实的label
    5. Updating 根据C^t 获得C^{t+1}的过程

实验和数据集

数据集

数据集名称来源备注链接
KKIBrain networkhttps://github.com/GRAND-Lab/graph_datasets#5functional-brain-network-analysis-data-brain
OHSUBrain network同上
AIDSBiochemistry 生物化学以下均在https://chrsmrrs.github.io/datasets/docs/datasets/ 可以找到
MUTAGBiochemistry 生物化学
MutagenicityBiochemistry 生物化学
NCI1Biochemistry 生物化学
PROTEINSBiochemistry 生物化学
IMDB-BINARYsocial network
REDDIT-BINARYsocial network

对比方法

方法方法概述code availibility
WWLrepresentative graph kernel-based methodWWL (https://github.com/BorgwardtLab/WWL).
g-U-NetsGNN, SOTAg-U-Nets (https://github.com/HongyangGao/Graph-U-Nets).
SAGPoolGNN, SOTASAGPool (https://github.com/inyeoplee77/SAGPool).
DIFFPOOLGNN, SOTADIFFPOOL (https://github.com/RexYing/diffpool).
GMTGNN, SOTAGMT (https://github.com/JinheonBaek/GMT).
OCGINgraph level anomaly detectionOCGIN (https://github.com/LingxiaoShawn/GLOD-Issues).
OCGTLgraph level anomaly detectionOCGTL (https://github.com/boschresearch/GraphLevel-AnomalyDetection).
GLocalKDgraph level anomaly detectionGLocalKD (https://github.com/RongrongMa/GLocalKD).
iGADgraph level anomaly detectioniGAD (https://github.com/graph-level-anomalies/iGAD/tree/main).
GCNbaseline
GATbaseline

结果对比(部分)

Image.png

评价指标是标准的P、R、F1


评论