ICML  2022 | Learning from Counterfactual Links for Link Prediction

“

文章信息

来源：Proceedings of the 39th International Conference on Machine Learning（ICML） 2022
标题：Learning from Counterfactual Links for Link Prediction
作者：Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, Meng Jiang
链接：https://proceedings.mlr.press/v162/zhao22e.html
代码：https://github.com/DM2-ND/CFLP

”

内容简介

学习预测丢失的链接对于许多基于图的应用程序很重要。现有方法旨在学习观察到的图结构与一对节点之间存在链接之间的关联。然而，在学习预测图上的链接时，两个变量之间的因果关系在很大程度上被忽略了。本文通过提出一个反事实问题来访问这个因素：“如果图结构与观察结果不同，这种联系还会存在吗？”答案是反事实链接将能够为表示学习增加图数据。为了创建这些链接，本文采用因果模型，将节点对的信息（即学习表示）视为上下文，将全局图结构属性视为处理，并将链接存在视为结果。本文提出了一种新颖的基于数据增强的链接预测方法，该方法创建反事实链接并从观察到的和反事实链接中学习表示。基准数据的实验表明，本文的图学习方法在链接预测任务上实现了最佳性能。

下图说明了本文的主要工作背景：假设处理变量被定义为一种全局图结构，例如，通过谱聚类或社区检测算法发现的邻域分配。需要知道邻域分布对每对节点的链接（不）存在有多大影响。因此，给定一对节点（如 Alice 和 Adam）和这对节点上的处理值（在同一邻域中），找到满足两个条件的一对节点（如 Helen 和 Bob）：（1）它有一个不同的处理（在不同的邻域中）和（2）它是与给定节点对最相似的对。将这些匹配的节点对命名为反事实链接。请注意，反事实链接的结果可以是 1 或 0，具体取决于匹配的节点对之间是否存在边。反事实链接在反事实条件下为给定的节点对提供不可观察的结果。为所有正面和负面训练示例创建反事实链接的过程可以被视为一种图数据增强方法，因为它丰富了训练集。然后，CFLP 训练一个链接预测器（基于 GNN）来学习节点的表示向量，以预测观察到的事实链接和反事实链接。在此 Alice-Adam 示例中，链接预测器被训练以估计邻域分配的个体治疗效果 (ITE) 为 ，其中 ITE 是治疗对结果的影响的度量，零表示给定的治疗对结果没有影响。因此，学习者将尝试发现Alice 和 Adam之间友谊的本质因素。CFLP 从反事实链接中学习，为图学习模型找到这些因素，从而准确预测缺失的链接。

本文的主要贡献如下：

• 这是第一项旨在通过因果推理改进链接预测的工作，具体来说，是生成反事实链接以回答有关链接存在的反事实问题。
• 本文引入了 CFLP，它训练基于 GNN 的链接预测器来预测事实和反事实链接。它利用全局图结构和链接存在之间的因果关系来增强链接预测。
• CFLP 在几个基准数据集上优于竞争基线。本文分析了反事实链接的影响以及治疗变量的选择。该研究为通过因果分析改进图机器学习提供了见解，该分析尚未得到广泛研究，而另一个方向（用于因果推理的机器学习）已经研究了很长时间。

问题定义

令 为 N 个节点的无向图，其中 是节点集， 是观察到的链接集。本文将邻接矩阵表示为 ，其中 表示节点 是连接的，反之亦然。将节点特征矩阵表示为 ，其中 F 是节点特征的数量，的特征向量。

该研究遵循普遍接受的关于图数据链接预测的问题定义（Zhang & Chen, 2018; Zhang et al., 2020; Cai et al., 2021）：给定一个观察到的图 G（掩蔽地带有验证和测试链接），预测每对节点之间的链接存在。更具体地说，对于基于 GNN 的链接预测方法，他们学习低维节点表示 Z ∈ RN×H，其中 H 是潜在空间的维度大小，使得 H ≪N，然后使用 来预测链接存在每个节点对之间。

方案介绍

用因果模型改进图学习

利用因果模型：本文用图学习来研究链接预测，即学习有效的节点表示 来预测测试数据中的链接存在。在下图（b）中，的表示，结果 之间的链接存在。

在这里，目标不同于经典的因果推理。在图学习中希望通过估计处理 的影响来改进 的学习。具体来说，对于每一对节点 ，它的 ITE 可以估计为:

使用这些信息来改进 的学习。

治疗变量：先前关于基于 GNN 的链接预测的工作（Zhang & Chen，2018；Zhang et al，2020）表明，基于消息传递的 GNN 能够捕获用于链接预测的结构信息（例如，Katz 索引）。然而，如前文中的 Alice-Adam 示例所示，此类结构信息与实际链接存在之间的关联可能太强，以至于模型无法发现比它更多的基本因素，从而导致次优的链接预测性能。因此，本文使用每个节点对的全局结构角色作为其处理。值得一提的是，上图所示的因果模型并没有将处理限制为结构角色。在不失一般性的情况下，本文以 Louvain (Blondel et al., 2008) 为例，这是一种广泛用于社区检测的无监督方法。Louvain 发现图的社区结构并将每个节点分配给一个社区。然后可以将二元处理变量定义为该对中的这两个节点是否属于同一个社区。

反事实链接

为了实现基于上述思想的解决方案，本文提出了反事实链接。如前所述，对于每个节点对，观察到的数据仅包含事实处理和结果，这意味着给定节点对与相反处理的链接存在是未知的。因此使用最近观察到的上下文的结果作为替代。这种类型的协变量匹配被广泛用于从观察数据估计治疗效果（Johansson et al，2016；Alaa&Van Der Schaar，2019）。也就是说，作者希望为每个观察到的节点对找到具有相反处理的最近邻居，并将最近邻居的结果用作反事实链接。形式上，，它的反事实链接 是：

从反事实链接中学习

本节介绍模型的设计以及训练方法。CFLP 中模型的输入包括（1）观察到的图数据 ，（2）事实处理 ，以及（3）反事实链接数据 。输出分别包含事实和反事实邻接矩阵 的 中的链接预测。

下图所示算法总结了CFLP的整个过程。

实验分析

下表显示了所有方法的 Hits@20 和 AUC 的链路预测性能。

由于运行官方代码包时出现内存不足错误，PUBMED 和 OGB-DDI 上的 LGLP 丢失。作者观察到与基线相比，本文在不同图形编码器上的 CFLP 实现了相似或更好的性能。唯一的例外是 FACEBOOK 上的 AUC，其中大多数方法都具有接近完美的 AUC。由于与 Hits@20 相比，AUC 是一个相对容易的指标，因此大多数方法在 AUC 上都取得了良好的性能。本文观察到带有 JKNet 的 CFLP 几乎一致地实现了最佳性能，并且在 Hits@20 上显着优于基线。具体来说，与最佳基线相比，CFLP 在 Hits@20 和 AUC 上分别相对提高了 16.4% 和 0.8%。与同样基于 GNN 的最佳性能基线相比，CFLP 受益于观察到的链接存在和我们定义的反事实链接 的学习。

总结展望

本文提出了反事实链接的新概念和用于链接预测 (CFLP) 的新图学习方法。反事实链接回答了关于链接存在的反事实问题，并被用作增强训练数据，CFLP 通过探索全局图结构与链接存在之间的因果关系，准确预测缺失的链接。大量实验表明，CFLP 在基准数据集上实现了最先进的性能。这项工作揭示了良好使用因果模型（甚至是基本模型）可以大大提高（图）机器学习任务（例如链接预测）的性能。作者注意到，使用更复杂设计的因果模型可能会导致机器学习任务的更大改进，这对于研究界来说可能是一个有价值的未来方向。除了基于集群的全局图结构作为处理之外，其他选择（包括经验和理论分析）也值得探索。