截断亲和力最大化：用于图异常检测的单类同质性建模 NIPS2023

基本信息和摘要

论文题目：Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection

作者：乔贺辙， 庞观松

作者研究单位：新加坡管理大学

我们揭示了现实世界的图异常检测数据集中的一个普遍属性——单类同质现象，即正常节点往往彼此具有很强的连接性/亲和性，而异常节点之间的连接/亲和性异常节点明显弱于正常节点。然而，现有的图异常检测方法通常使用传统的异常检测目标函数(如数据重建），这些方法忽略了如何利用这种具体判别性的异常特性。在这项工作中，我们探索了这一特性，引入了一种新的无监督的图异常检测异常评分方法——局部节点亲和力——该方法将亲和度定义为节点属性/表示的相似性并将较大的异常评分分配给与邻居关联较少的节点。我们进一步提出了截断亲和力最大化模型(TAM)，它通过最大化节点的局部关联来为我们的异常度量学习定制的节点表示。但是，在原始图结构上进行优化可能会受到非同态边(即连接正常节点和异常节点的边)的影响。因此，TAM在截断的图上进行优化，其中非同态边被迭代地删除来地减轻这种偏差。最终通过学习表征来使得正常节点的局部亲和力明显强于异常节点。在10个真实图异常检测数据集上的结果表明，TAM的表现明显优于图异常检测七个相互竞争的模型，在具有挑战性的数据集上，与最佳竞争者相比，AUROC/AUPRC增加了10%以上。

论文地址：https://arxiv.org/pdf/2306.00006.pdf 代码地址：https://github.com/mala-lab/TAM-master/

介绍

图异常检测旨在识别图中与大多数节点不同的异常节点。近年来，由于其在现实中广泛的应用，例如检测非友好评论或恶意/欺诈用户，这极大地引起了研究者们的兴趣。但是，由于图数据是非欧式数据，往往具有多样的图结构和节点属性，因此如何有效地对正常特征进行建模并检测图中的不同类型的异常节点是非常具有挑战性的。为了应对这一挑战，图神经网络（GNN）已被广泛用于 图异常检测。基于 GNN 的方法通常使用数据重建或自监督的方法来构建学习目标。数据重构方法侧重于学习节点通过最小化重建节点属性和图的误差来识别异常节点，而自监督方法则侧重于设计相关的代理任务来进行异常的检测。在本文中，我们第一次经验性地揭示了单类同质现象，它提供了一种有效的图异常检测属性。受此属性的启发，我们引入了一种新的无监督异常评分措施即本地节点亲和力分数。然后，我们引入截断亲和力最大化模型（TAM），它可以针对所提出的异常测量的来学习节点的表示。

如图所示， TAM 利用单类同质性通过在截断的图上最大化本地节点亲和力来学习节点的表征，这样得到的局部亲和力分数为图异常检测提供了一种具有判别性的分数。本文的主要贡献可以总结为以下几点：我们第一次经验性地揭示了图异常检测数据集中的单类同质现象，它提供了一种异常区分属性。受此属性的启发，我们引入了一种新颖的无监督异常评分措施即本地节点亲和力。然后，我们引入截断亲和力最大化（TAM），它可以学习针对所提出的异常测量的定制节点表示。TAM 充分利用单类同质性通过在截断的邻接矩阵上最大化本地节点亲和力来学习节点的表示，为准确的图异常检测提供了有判别性的局部亲和力分数。我们进一步介绍了两个新颖的组件，即基于局部亲和力最大化的图神经网络（简称LAMNet）和正常结构保留图截断 (NSGT)，以实施 TAM。十个真实世界 GAD 数据集的实验结果表明我们的 TAM 模型明显优于七个竞争模型.

方法

局部亲和力是量化节点正常/异常的新视角，比重建误差等现有流行测量方法实现更简单的异常评分。节点 的局部亲和力 定义为与相邻节点的平均相似度，异常得分 与亲和度相反

我们的异常测量还提供了一个新的视角来学习定制的节点表示。不是常用的最小化数据重建误差，而是基于单类同质, 通过最大化节点的本地节点亲和力, 来学习节点的表示。我们首先定义

其中 是 基于 GNN 的节点表示通过映射函数学习得到， 是 TAM 中的 函数 的参数。下面我们介绍一下如何通过这两个组件LAMNet 和 NSGT来学习函数 ，这两个组件以及方法的框架如图所示

LAMNet 由单类同质性驱动, 它的目标是学习一种基于 GNN 的映射函数 ，该函数最大化具有同质关系的节点与其邻居的亲和力，同时保持具有非同质边缘的节点的亲和力较弱。

其中第一项相当于根据学习到的节点表示来最大化每个节点的局部亲和力，而第二项是正则化项，λ是正则化超参数。正则化项添加了一个约束，即每个节点的表示应该与非相邻节点的表示不同，以强制非本地节点的表示是可区分的，同时最大化本地节点表示的相似性。但LAMNet的目标和图卷积运算可能会因非同质边存在而产生偏差，即连接正常节点和异常节点的边。

NSGT 组件旨在删除这些非同质边，通过产生截断的邻接矩阵 。然后LAMNet 执行使用截断的邻接矩阵 而不是原始邻接矩阵 ， 以减轻消息传递中由非同质边引起的偏差。如图（a）(b) 所示，由于同质边（即连接正常节点的边）连接相似属性的节点， 同质边的节点之间的距离通常远小于非同质边的节点之间的距离，受此启发，NSGT 采用一种基于概率的方法来执行图截断：对于给定的边