[图神经网络论文]:Link Prediction Based on Graph Neural Networks
传统link prediction算法
经典算法
现有的启发式可以根据计算分数所需的邻居的最大跳数(k-hop)进行分类
例如:
one-hop
- Common Neighbors 算法基于以下这一假设：两个节点拥有共同的邻居数量越多，则它们之间建立连接的可能性越大：\mathrm{CN}(u,v)=|\Gamma(u)\cap\Gamma(v)|其中符号\Gamma(v)代表的是节点v的所有邻居。
- Preferential Attachment算法则以"富者得富"或"优先连接"的理念为基础：即那些拥有较高邻居数量的节点在未来更容易获得更多的新连接。这一理念源自无标度网络的增长模型：其中某些高连接度的节点更容易吸引更多的新链接 \mathrm{PA}(u,v)=|\Gamma(u)|\times|\Gamma(v)|。
two-hop
- Adamic-Adar:Adamic-Adar算法基于以下假设：并非所有的共享邻居都对链接预测具有同等重要性。具体而言，在该模型中如果一个节点z是节点u和v的共同邻居，并且其连接数量（度）较高，则它对u和v之间链接的可能性贡献较小；反之，在Adamic-Adar算法中将给予度较低的共享邻居更高的权重以进行链接预测计算。\mathrm{AA}(u,v)=\sum_{z\in\Gamma(u)\cap\Gamma(v)}\frac1{\overline{\log|\Gamma(z)|}}
- Resource Allocation:Resource Allocation算法借鉴物理学中的资源分配机制，在该模型中每个节点被视为拥有一定数量资源的实体，并通过它们所共有的邻居进行资源传递和分配。当两个节点通过共享邻居接收更多资源时，则表明它们之间产生链接的可能性更大；此外Resource Allocation算法假定了资源分配过程中的均等性特点与Adamic-Adar算法在处理低度节点上的偏好存在显著差异。\mathrm{RA}(u,v)=\sum_{z\in\Gamma(u)\cap\Gamma(v)}\frac1{|\Gamma(z)|}
k-hop
- PageRank
- Katz index
- SimRank
缺陷
该方法对于何时存在连接具有较强的预设 :这些方法通常基于预先定义好的图结构特征进行分析。例如，在公共邻居启发式的框架下认为：如果两个节点拥有较多共同邻居，则它们之间更容易形成连接。这一假设有其合理性在社会网络分析中得到广泛应用；但在交通与物流系统等实际应用领域，则发现这种关联更多取决于地理距离与通达性等因素而非共同邻居的数量关系。而在这些实际应用领域（如交通与物流系统），基于地理距离与流量优化的传统算法往往表现不如某些新型优化方法。
γ-decaying heuristic
封闭子图 enclosing graph
给定图G=(V,E)以及其上的两个节点x, y ∈ V。我们称满足以下条件的所有节点i ∈ V构成的集合\{i | d(i,x) ≤ h \; 或者 \; d(i,y) ≤ h\}所导出的子图为(x,y)-hop闭包子图，并记作G_{x,y}^h = (V_h, E_h)
定义
在节点x和y之间应用的γ-衰减启发式被称为γ-descaying heuristic。其计算公式如下所示：
\mathcal{H} (x,y)=\eta\sum_{l=1}^{\infty}\gamma^{l}f(x,y,l)
其中:
- H表示节点对 (x,y) 通过链接关系所形成的启发式评估
,* γ是一个介于0到1之间的衰减系数
,* η是一个正常数或者与γ相关的正函数，并且具有上限常数
,* f对于给定网络中的任意节点x,y以及路径长度l(其中l=1,2,\cdots,g(h))来说都是一个非负值，并且满足以下条件：对于所有l=1,2,\cdots,g(h)，
f(x,y,l) ≤ λl \quad \text{其中} \quad λ < 1/γ
,* 计算该函数所需的图数据集G_{x,y}^h在路径长度l=1到l=g(h)之间可获得（其中g(h)=ah + b）。
误差
基于γ衰竭理论的误差解释表明：误差值随着聚合半径的增长呈指数衰减趋势；具体而言，
其计算公式为：
|\mathcal{H}(x,y)-\widetilde{\mathcal{H}}(x,y)|=\eta\sum_{l=g(h)+1}^\infty\gamma^lf(x,y,l)\leq\eta\sum_{l=ak+b+1}^\infty(\gamma\lambda)^l=\eta(\gamma\lambda)^{ak+b+1}(1-\gammaλ)^{-1}
理论解释
一个成功的链接预测启发式算法应将权重急剧下降地分配在远离目标的位置上。这是因为网络中距离目标较远的部分节点对链接的存在影响较小。这表明局部封闭子图已经包含了足够的信息来学习良好的图结构特征。考虑到从整个网络中学习通常难以实施
SEAL: An implemetation of the theory using GNN
SEAL-based framework is a link prediction framework proposed in this paper, specifically including three main aspects.
封闭子图 enclosed subgraph
- 使用GNN进行链接预测
提取封闭子图
给定一个网络结构，我们旨在通过自动化过程学习最优启发式解析机制。基于理论分析的结果表明，在局部封闭子图中分析链接生成机制最为有效。为此设计并训练模型时，在封闭子图上使用图神经网络（GNN）来预测或评估链接的存在概率。SEAL算法的第一步即是从观测到的正链和未观测到的负链中提取一系列局部封闭子图作为训练数据。
G_{\nu_1,\nu_2}^k=\{\nu|\text{满足}~d(\nu,\nu_1)~\text{及}~d(\nu,\nu_2)~\text{均不超过}~k\}即为所有满足到两个目标节点距离均不超过k的所有节点构成的子图### 节点信息矩阵
Node labeling
X的第一个主要组成部分是所有节点的结构标识符。这些标识符由函数f_{l}定义为从集合V到N的一个映射关系，在代码块中表示为特定变量i对应的整数标签f_{l}(i)。这种设计旨在通过独特的标识符来区分封闭子图中不同角色的节点：具体来说，在封闭子图中通过函数f_{l}为每个节点分配一个唯一的整数标签i。
- 中心节点x和y是作为链接的目标节点之一。
- 相对于中心而言,不同相对位置的节点对于链路而言具有不同的结构重要性:适当的标签能够区分这些差异。
如果我们不标记这些差异,GNNs将无法准确判断应该预测链路存在的目标节点的位置,从而导致结构信息的丢失。
- 相对于中心而言,不同相对位置的节点对于链路而言具有不同的结构重要性:适当的标签能够区分这些差异。
因此，基于上述准则，作者提出了Double-Radius Node Labeling (DRNL):
中心核心点x、y被标记为1。
非核心点i其标签值由它们与目标之间的距离决定。
具体而言，在计算标签时会考虑每个非核心点i到两个目标点x和y的距离之和。
其中d_x表示i到x的距离,d_y表示i到y的距离,d等于d_x + d_y。
根据这些参数,f_l(i)将被赋予相应的值。
如果某个非核心点无法到达x或y，则其标签值设为0。
例子:
初始化阶段：考虑的目标集合为{A, B}且满足条件A=B=1
计算其他非目标节点到该目标集合的距离并进行分类标记：
对于C和D这两个非目标邻居而言，在本阶段它们分别仅连接到该初始目标集合中的一个成员（即A或B），因此它们各自被赋予相同的初始值C=2
对于非初始邻居E而言：它仅连接到该初始目标集合中的一个成员（即B），而从该点出发到达另一个初始成员的距离则需要经过中间层神经元进行传递（路径长度为2）。基于此判断依据可得E应被赋予值3
对于更高层级的非邻居F而言：它既不直接连接也不间接通过短程路径到达任一初始成员点；此时观察发现，在到达这两个初始成员之前它必须经过比这两个初始成员更远的一系列中间层神经元。基于此判断依据可得F应被赋予值4
Node embedding
在论文研究中, 节点嵌入采用的方法是 node2vec 算法. 然而, node2vec 在整个图上）的节点嵌入反映了连接特征, 易出现过拟合现象. 针对上述问题, 提出了一种改进方案: 负样本注入(negative injection), 即将负样本采样的边加入整个图后重新运行一次 node2vec 算法. 然而, 该方法可能会存在以下缺陷: 首先, 负样本注入可能会引入新的噪声数据, 影响模型的学习效果；其次, 重新运行算法可能导致计算成本增加.
通过重构或优化图结构，在蛋白质链接预测中的应用。
在平衡问题上，需要确定加入多少数量的负样本，并且要选择合适的代表。
引入过多的负样本可能导致模型过于依赖这些额外的数据而影响性能。
Node attributes
结点本身的特征(元数据)，例如用户的年龄、性别、兴趣点等
GNN
最后使用信息矩阵X训练GNN
论文中使用的GNN是DGCNN架构
- 图卷积网络（Graph Convolutional Networks, GCNs）是一种基于图数据的学习方法。
- Sort Pooling机制被DGCNN引入用于处理不同规模图数据，在此过程中该机制旨在将具有不同大小节点集的图转换为固定大小表示形式。
- 在经过Sort Pooling处理之后，在每一层中都会依次应用一系列的一维卷积操作以提取局部特征并增强节点间关系表达。
- 最后一步通过全连接层将提取到的特征向量映射为图对应的分类结果，在本研究中该分类任务被设定为二分类问题（存在链接/不存在链接）
训练框架
- 选择两组目标节点：
- 设定领域半径h：
- 提取限定子图：
- 标记限定子图中各节点的DRNL标签：
- 引入负样本：
- 通过node2vec算法生成节点向量矩阵：
- 收集节点属性向量集合：
- 将步骤4、6、7的结果组合形成信息矩阵X：
- 采用DGCNN模型进行学习训练：