论文《Line Graph Neural Networks for Link Prediction》阅读
论文《Line Graph Neural Networks for Link Prediction》阅读
- 论文概况
-
引言
-
方法论
- 子图提取技术
- 节点标记过程
- 图学习阶段
- 子图提取技术
-
Experiments
-
Summary
-
本文介绍了一篇经典论文《Line Graph Neural Networks for Link Prediction》，该研究发表于IEEE TPAMI期刊上，并由微软研究人员Lei Cai及其团队完成。该论文已在Google Scholar上获得超过200份引用，并已成为当前领域内的最优链路预测模型。
论文概况
论文发表时间为2021年，在此之前实则早在2020年便已投稿至arXiv平台；从时间线来看，在时效性方面具有显著优势的链路预测模型。
该研究专注于链路预测场景，并旨在展示模型的通用性。实验结果表明，在涵盖多个领域的14个数据集上（包括学术转发、生物、交通以及社交网络等），该方法均展现出良好的性能。
论文的方法论模块设计得极为简洁且功能完善，在写作模块的引入方面具有极高的精准度，并成功提出了LGLP模型
论文链接：TPAMI LGLP
代码仓库：LGLP
Introduction
先对链路预测（Link Prediction）进行概述，并说明其核心任务：基于给定的网络数据预测节点之间的潜在连接概率。该模型属于分类模型，在实际应用中即通过分析节点特征和网络拓扑结构的信息来判断是否存在连接。
论文的切入点聚焦是以链路预测中的信息损失为研究核心点。在现有的网络分析领域中，GNN模型已成为处理链路预测问题的主要方法之一，在该领域的基本流程是：从整个链路图中随机选取任意两个节点作为中心节点，并通过深度或广度优先的方式遍历其周围的子图，在此过程中进行节点表示学习；随后通过log loss损失函数对目标边的存在与否进行学习判断，在这一过程中通常会对两个大小为 D 的表示向量进行聚合运算以得到一个介于0到1之间的实数结果；这种学习任务本质上等同于一种图分类任务（判断该图为非图或者图为图），然而在这一操作过程中会丢失大量关键信息而导致模型性能有待提升
该作者在此基础上提出了采用线图方法，并具体而言，则是将连边预测任务转化为线图中的节点分类问题。具体而言，则是判断这些节点是否具有连接边。
图分类 \Longrightarrow 节点分类
Methodology
基于此，在SEAL模型的基础上构建了LGLP模型，并遵循了相同的流程来进行操作。作者将链路预测划分为三个关键步骤来完成这一任务。
- Closed Subgraph Extraction: Closed Subgraph Extraction
- Node Marking: Node importance annotation
- Feature Learning and Link Prediction: Graph methods and result prediction
下面依次介绍。
子图提取
其中K-hop子图提取的过程是：对于目标结点对v_i或v_j的距离不超过K的所有结点均被计算并纳入子图G_{(v_i,v_j)}^K}之中。
然后进行线图转换，点变成边，边变成点。
那么，在该线图中节点数量相当于原来的边数数量级N；而边的数量相当于\dfrac{1}{2}\sum_{i=1}^{M}d_{i}^{2}-N。具体来说，在这种转换过程中，默认情况下每个原始节点会被视为相互连接两次（即两次连接），但为了避免重复计算这些原始存在的边数N。
Node Labeling
图有了，现在需要标注结点的重要性。
该节点无特征。
l_{(v₁, v₂)} = concatenate(\min(f_{subscript{l}}(v₁), f_{subscript{l}}(v₂)), \max(f_{subscript{l}}(v₁), f_{subscript{l}}(v₂))) ，\tag{2}
对于包含特征标记的节点：
l_{(v_1, v_2)} = \text{concatenate}\bigl( \text{较小值}(f_l(v_1), f_l(v_2)), \text{较大值}(f_l(v_1), f_l(v_2)), X_{v1} + X_{v2} \bigr)，\tag{3}
这些变量代表节点 v_{1} 和 v_{2} 的特征向量；其中的函数符号f_{l}(\cdot)被定义为标注函数；本文将采用以下标注策略：对于任意节点v而言；其对应的标签值f_{l}(v)由下式计算得出：
f_{l}(v)=1+\min \left(d(v, v_{1}), d(v, v_{2})\right)+ \frac{d_{s}}{2} \cdot \left[\frac{d_{s}}{2} + (d_s \bmod 2) - 1 \right] ，
其中d(v, v_i)表示节点v与v_i之间的距离；而d_s则表示某种度量的标准参数。
d_s = d(v, v_1) + d(v, v_2)用来计算两端点之间的距离总和的一半。对该值进行二分法处理得到两个结果：一半的值\left(d_s / 2\right)以及取模后的余数值\left(d_s \% 2\right)。这些结果分别对应整数商与余数。
Graph Learning
针对原图G^{h}_{v_1, v_2}而言，在其第k层中存在一个嵌入表示为\mathcal{Z}_{(v_i, v_j)}^{(k+1)}；随后我们采用以下方式对嵌入进行聚合运算：
具体来说，在此模型中所涉及的节点嵌入可以通过以下方式进行聚合。\ 其中，
Z^1(v_i, v_j) = (\ l^{1}(v_i,v_j)+β∑_{d₁∈Neighbors(v_i)}∑_{d₂∈Neighbors(d₁)} l^{1}(d₁,d₂)\ ) + β∑_{d₃∈Neighbors(v_j)}∑_{d₄∈Neighbors(d₃)} l^{1}(d₃,d₄)\ ) W^{(0)}.
这一过程通过结合邻居节点间的相似性信息实现了对原始关系路径长度的一种加权累加表示。\ 标签（6）
即, 单一跳线图聚合等同于原图中一对结点的两次跳聚合. 扩展了聚接范围之后将会更加高效.
预测模型基于一个双层结构的多层感知机（MLP）生成输出概率p_{l}；随后采用交叉熵损失函数计算出分类损失指标
整体流程如下：
Experiments
不同的边密度：
Summary
整个模型其实非常简单，作者论文中的线图实际上是直接调用的库
from torch_geometric.transforms import LineGraph
但模型在整体创新方面表现突出，并且在写作上也体现了其创新性特点，值得借鉴学习