异配图表示学习
一、简介
图神经网络（GNNs）已成为一系列图学习任务中不可或缺的关键工具。然而，大多数现有的GNN架构在显式或隐式上都遵循同配性假设，即具有相同标签或相似属性的节点更可能相互连接。尽管这一潜在假设在实践中被广泛采纳，但其普适性却有待商榷，可能导致在某些场景下学习效果的不足。近年来，针对图数据中普遍存在的异配性问题的研究和解决方案取得了显著进展。本文特别聚焦于两项旨在提升GNN在异配图上表现的最新研究成果：HES和SE-GSL。这两项研究分别通过自适应节点感受野调整与结构优化的创新策略，显著增强了现有GNN对于异配图的鲁棒性。
二、The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs（KDD 2024）
在图数据中，节点的同配性分布展现出丰富的多样性。HES首次将“一个节点一个感受野”的流行概念转移到异配图中。该方法通过构建一个伪标签预测器，为每个节点生成伪标签概率分布，帮助相连节点判断是否应聚合其相关的邻居。该值可以进一步表示相邻两个节点之间的同配性分数，替代原始的邻接矩阵。通过分析每层同配性分数的变化，能够适当地确定早停的深度。最终，每个节点都可以拥有其独特的聚合跳数，就像每一片雪花都是独一无二的，拥有其自身的特性。
HES整体架构图
2.1.伪标签预测器
HES 构建了一个代理标签预测器 ，具体来说，采用一个简单的预测模型例如MLP和GNN，来获得伪概率标签，并使用交叉熵损失函数来优化预测模型：
其中 表示训练节点集 和图结构， 表示网络参数。
2.2.同配性掩码训练
在获得节点的伪标签后，HES定义了同配性掩码 ，其中 通过计算节点 和 各自预测概率分布的外积的迹来得到，它表示边 的同配性强度，即节点 和 具有相同标签的可能性。
由代理模型 参数化，可以表示为：
和 的形状相同，可以通过以下目标函数 进行端到端的优化：
2.3.基于多跳异配性的早停策略
在经过多轮训练和优化后的相对准确的掩码记作 ，使用进一步表示基于同配性分数的 -跳邻居聚合表达式，计算每跳的行和值作为早停策略的参考值：
如果满足条件，则有，其中 表示过滤阈值,在第 层采用异配性感知的早期停止，以确保每个节点具有独特的感受野大小。
实验效果
HES 算法可以适用于各种GNN，具有极大的灵活性，并始终表现出优秀的性能。
三、SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization（WWW 2023）
图神经网络容易受到低质量和不可靠结构的影响，现有的图结构学习框架在鲁棒性和可解释性方面仍显不足。SE-GSL通过结构熵理论和编码树中抽象的图层次结构来实现免学习的方式自适应地优化拓扑图结构。SE-GSL兼容各种GNN模型，并增强了GNN对噪声和异配性结构的鲁棒性。SE-GSL分为图结构增强、分层编码树生成、基于采样的图重构、节点表示学习四个过程。
SE-GSL架构图
3.1.图结构增强
为了充分整合图结构中的顶点属性和邻域信息，SE-GSL执行特征融合和边权重调整，以便将拓扑结构和信息丰富的顶点邻接相似性传递给分层编码树生成器。首先，采用皮尔逊相关系数（PCC）作为相似性度量计算图 G 中顶点之间的成对相似性矩阵 。接下来，基于 ，构建 -近邻图 ，其中 中的每条边表示一个顶点及其 个最近邻。最后，将 和原始图 融合为 ，其中。
3.2.分层编码树生成
把图抽象为分层编码树的目标是最小化图的不确定性并最大化嵌入的知识。因此，优化目标限制为寻找结构熵最小的具有超参数 的 级树。寻找最优的 级编码树的算法是一个贪心的启发式算法，其中有两个基本操作：
定义 1. 组合操作：给定编码树 对于 ，设 和 为 中的两个节点，它们共享相同的父节点 。组合操作在 和其子节点 、 之间插入一个新节点 作为 、新的父节点， 的子节点。
定义 2. 提升操作：给定编码树 对于 ，设 和 为 中的节点，满足 的父节点为 且 的父节点为。提升操作将以 为根的子树提升为 的子节点。如果提升后 不再存在子节点，将从 中删除。
基于高维结构熵最小化原理，SE-GSL首先通过贪心地执行组合操作来构建一个全高的二进制编码树,直到结构熵不再降低。为了满足高度限制，进一步通过将子树提升到更高的层次来压缩编码树,直到编码树的高度小于 且结构熵无法再降低。最终，SE-GSL得到一个具有特定高度 的编码树 ，并且其结构熵最小。
3.3.基于采样的图重构
接下来的步骤是在最优编码树 中已建立的层级语义的基础上，从层次结构中恢复拓扑结构。图重建的关键在于确定需要增强或削弱的边，即增强簇内边缘并减少簇间边缘。
SE-GSL定义了一个推演结构熵，从消息传递的角度来看，具有更高推演结构熵的顶点会产生更多的多样性和不确定性，因此需要更多的监督信息。为此，这些顶点在图重建过程中需要扩展连接域，以通过广泛的边缘聚合更多信息。为实现这一点，SE-GSL设计了一种基于采样的图重建方法。该方法的核心思想是在叶节点级别挑选节点对，并以与推演结构熵相关的概率随机生成给定节点对之间的边缘。具体而言，SE-GSL以单一采样流在自顶向下的方式下采样叶节点对，具体步骤如下：
对于根节点为 的编码树（或子树），根据推演结构熵样选择两个不同的子节点 和 ，设 且 ； 若 是非叶节点，则在以 为根的子树上进行一次采样以获得它的子节点 ，并更新 ，对 执行相同操作； 经过递归执行步骤2后，在叶节点中采样出 和 ，并将连接两个节点的边添加到图 的边集 中。
为了在所有层次上建立广泛的连接，需要对所有编码子树进行多次采样。
3.4.实验效果
SE-GSL 在 5 个数据集上取得了最佳结果。
四、总结
在本文中，介绍了异配图表示学习中的两项研究成果，HES和SE-GSL。这两种方法各具特色，各自从结构优化和节点自适应聚合出发，针对不同层面的挑战提出了解决方案。未来，这些创新有望为异配图上的GNN模型提供更广泛的应用前景，也为后续研究提供了方向和参考框架。
