Paper

Introduction

由于GNNs过度强调平滑的节点特征而不是图结构，使得在Link Prediction任务上的表现甚至弱于heuristic方法。平滑邻居难以反映邻域结构的相关性以及其他拓扑特征。 Structural information, (e.g., overlapped neighborhoods, degrees, and shortest path), is crucial for link prediction whereas GNNs heavily rely on smoothed node features rather than graph structure。

Link prediction heuristics: 基于预定义的假设的链路预测。举几个例子[1]：

  1. Common Neighbors (CN)： 公共邻居较多的节点存在边（heuristic），则需要计算节点对间的公共邻居。
  2. Preferential Attachment (PA): 一个节点当前的连接越多，那么它越有可能接受到新的连接（heuristic）,这需要统计每个节点的度, i.e., $P A(x, y)=|N(x)| *|N(y)|$
  3. Katz Index heuristic: $\sum^{\infty}_{\ell=1} \beta^{\ell}|walks(x,y)=\ell|$ 表示从$x$到$y$的所有路径数， $0<\beta<1$， 表示越长的路径权重越低。 katz Index作为Link prediction heuristic假设来作为边是否存在的预测。

本文提出了Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs)来从邻接矩阵中学习结构信息，并且估计重叠多跳邻域用于link prediction。

Preliminaries

$$ \hat{y}_{i j}=\sigma\left(s\left(h_{i}^{(L)}, h_{j}^{(L)}\right)\right) $$

其中$s(\cdot, \cdot)$ 是一个相似度计算函数 e.g., inner product or MLP. $h_{i}^{(L)}$为 $v_i$的 node embedding.

Neighborhood Overlap-based Heuristic Methods

就是上面提到的CN heuristic。Common Neighbors 通过count节点的公共邻居来衡量两个节点之间的链路存在分数$\mathrm{link}(u,v)$： $$ S_{C N}(u, v)=|\mathcal{N}(u) \cap \mathcal{N}(v)|=\sum_{k \in \mathcal{N}(u) \cap \mathcal{N}(v)} 1 $$ CN的缺点在于不能衡量公共节点的权重。

Resource Allocation (RA) 认为度叫小的节点因更加重要， 所以用度的倒数来加权公共节点： $$ S_{R A}(u, v)=\sum_{k \in \mathcal{N}(u) \cap \mathcal{N}(v)} \frac{1}{d_{k}} $$

Adamic-Adar：通过使用节点 $u$ 和$v$之间的共同邻居度的倒数对数，与 RA 相比，Adamic-Adar 对更高度的惩罚相对减少： $$ S_{A A}(u, v)=\sum_{k \in \mathcal{N}(u) \cap \mathcal{N}(v)} \frac{1}{\log d_{k}} $$ 上述基于公共邻居的方法存在两个局限，1. 需要手动设计邻居结构特征，比如CN的公共邻居结构特征为1， RA的结构特征为$\frac{1}{d}$, AA 的邻居结构特征为$\frac{1}{\log d}$。 2. 忽略了node features

本文提出的Neo-GNN从邻接矩阵中学习结构特征，并且结合了node feature信息来做Link prediction。

Model: Neo-GNNs

定义structural feature generator $\mathcal{F}_{\theta}$: $$ x_{i}^{\text {struct }}=\mathcal{F}_{\theta}\left(A_{i}\right)=f_{\theta_{n o d e}}\left(\sum_{j \in \mathcal{N}_{i}} f_{\theta_{e d g e}}\left(A_{i j}\right)\right) $$ 输入节点$i$的邻居$A_i$，提取自邻接矩阵$A$, Neo-GNNs 只是用$A$作为输入来获得节点的结构特征。 其中，$f_{\theta_{e d g e}}(A_{ij})$生成节点$i$的局部边特征，然后聚合起来用$f_{\theta_{n o d e}}$生成节点$i$的总体结构特征$x_{i}^{\text {struct }}$， 作为节点$i$的structural feature，表示反映了节点$i$的局部结构。其中$f_{\theta_{n o d e}}$和$f_{\theta_{e d g e}}$是两个MLP。 也可以把上面的$A$替换成$A$的幂的组合，那就是$k$跳以内邻域的结构特征。

得到了节点的邻居结构特征$x_{i}^{\text {struct }}$后， 要用重叠邻居的结构特征来计算两个节点的相似度分数。 传统的GNN无法计算重叠邻域的结构特征的原因有两个：1. normalized adjacency matrix: 归一化邻接矩阵阻止了GNN计数邻居数量（我的理解是因为Norm adj上的元素为小数）2. 远低于节点数的hidden representation维度$d \ll N$：低维度的节点表示向量使得在neighborhood aggregration后 节点邻域特征难以区分。

本文提出了邻域重叠感知的聚合模式。 注意，上面的节点邻域特征是一个scale, 即$x_{i}^{\text {struct }} \in \mathbb{R}^1$, 整个图的节点邻域结构特征可以表示为$X^{struct} \in \mathbb{R}^{N \times N}$, 为一个对角阵，对角线元素为每个节点的邻域结构特征，如Figure 1所示。也就是$X^{struct}$的每一行为一个节点的局部结构特征表示向量，作为这个节点的结构特征。

那么$Z = AX^{struct}$就可以为节点聚合结构特征。 因为$X^{struct}_i$表示节点$v_i$的structural feature (neighborhood structural), 所以$Z_i$表示节点$i$的1-st neighborhood structural feature, 所以$z_{i}^{T} z_{j}=\sum_{k \in \mathcal{N}(i) \cap \mathcal{N}(j)}\left(x_{k}^{s t r u c t}\right)^{2}$表可以表示节点$i$和节点$j$的重叠邻域。

注意 $X_{i}^{\text {struct }}$表示节点$i$自身的结构特征。 而$Z_i$表示节点$i$的邻居的结构特征聚合, 所以$z_{i}^{T} z_{j}$表示节点$i$邻居的结构特征和节点$j$邻居的结构特征的相似度。 $x_i^T x_j$表示节点$i$自身的结构特征和节点$j$自身的结构特征的相似度。

进一步，考虑多跳邻居： $$ Z=g_{\Phi}\left(\sum_{l=1}^{L} \beta^{l-1} A^{l} X^{\text {struct }}\right) $$

$A^lX^{struct}$的第$i$行表示节点$i$ 的$l$跳邻居特征。 $Z_i$表示节点$i$在$L$跳以内的邻居结构特征总和。

除了考虑结构特征来预测链接外，还应考虑node features，直接用GNN： $$ H=\operatorname{GNN}\left(X, \tilde{A}_{G N N} ; W\right) $$ 最终节点$i$和节点$j$的相似度分数表示为： $$ \left.\hat{y}_{i j}=\alpha \cdot \sigma\left(z_{i}^{T} z_{j}\right)+(1-\alpha) \cdot \sigma\left(s\left(h_{i}, h_{j}\right)\right)\right) $$ 即为邻域结构相似度 与 特征相似度 的加权平均。

最终损失函数要求 3种相似度衡量标准（基于邻域结构，基于节点feature, 两者加权平均）都可以你和真实的相似度，即： $$ \mathcal{L}=\sum_{(i, j) \in D}\left(\lambda_{1} B C E\left(\hat{y}_{i j}, y_{i j}\right)+\lambda_{2} B C E\left(\sigma\left(z_{i}^{T} z_{j}\right), y_{i j}\right)+\lambda_{3} B C E\left(\sigma\left(s\left(h_{i}, h_{j}\right)\right), y_{i j}\right)\right) $$ 其中$BCE(\cdot, \cdot)$为 binary cross entropy loss。

Reference

[1] Link Prediction Based on Graph Neural Networks. NeurIPS 2018.