目录
概
作者认为 link prediction 是一种更加依赖图拓扑结构的任务, 所以提出了一种 WalkPool 的技术用于从 subgraph 中提取更有用的结构信息.
符号说明
- \(|\mathcal{V}| = n\), nodes;
- \(\mathcal{E}^o\), 观测到的 true links;
- \(\mathcal{E}^*\), 所有的 true links 的集合, 故有 \(\mathcal{E}^o \subset \mathcal{E}^*\) 成立;
- \(\mathcal{E}^c\), 候选的 links (或许是 true, 或许是 false);
- \(\mathcal{G}^o = (\mathcal{V}, \mathcal{E}^o)\);
- \(\mathbf{A} = (a_{ij})_{i,j=1}^N \in \{0, 1\}^{N \times N}\), 邻接矩阵;
- \(\mathbf{Z} = [\mathbf{z}_1, \cdots, \mathbf{z}_N]^T \in \mathbb{R}^{N \times F}\), 结点的特征矩阵;
- \(\mathbf{D} = \text{diag}(d_1, \ldots, d_N)\), degree matrix;
- \(\mathbf{P = D^{-1}A}\), transition matrix;
- 我们的任务是找到一个算法 \(\prod: \mathcal{V} \times \mathcal{V} \rightarrow \{\text{True, False}\}\), 最好能够正确分类.
WalkPool
-
如上图所示, WalkPool 的初衷是提取更有效的拓扑信息用于 link prediction, 其大概思路是:
- 假设我们关注的是 A 中若隐若现的那条边 (不妨设其为结点 \(i, j\) 之前的边), 我们想要预测这条边是不是存在, WalkPool 希望通过它附近的一个子图 \(\mathcal{G}_{i, j}\) 来提取足够的信息.
- 进一步假设由 \(\mathcal{G}_{i, j}\) 导出的包含边 \(e_{ij}\) 的图 \(\mathcal{G}_{i,j}^+\) 和不包含边 \(e_{ij}\) 的图 \(\mathcal{G}_{i,j}^-\);
- 通过可训练的 encoder 得到该图的每个结点表示, 并由此跌倒子图的 transition matrix \(\mathbf{P}^+, \mathbf{P}^-\);
- 根据这两个 transition matrix 提取最后的特征用于分类.
-
令 \(d(i, j)\) 表示两个结点 \(i, j\) 间的最短路径, 则 \(k\)-hop enclosing subgraph \(\mathcal{G}_{i,j}^k = (\mathcal{V}_{i,j}^k, \mathcal{E}_{i, j}^k)\) 可以表示为:
\[\mathcal{V}_{i,j}^k = \{x \in \mathcal{V}: d(x, i) \le k \text{ or } d(x, j) \le k\}, \\ \mathcal{E}_{i, j}^k = \{(x, y) \in \mathcal{E}^{o}: x, y \in \mathcal{V}_{i,j}^k\}. \]对于这些 subgraph, 我们可以类似地定义其邻接矩阵 \(\mathbf{A}_{\{i, j\}}\), 这里不多赘述了.
-
假设子图的结点特征表示为 \(\mathbf{Z}_{\{i, j\}}\), 我们通过
\[w_{x, y} = Q_{\theta}(\mathbf{z}_x)^T K_{\theta}(\mathbf{z}_y) / \sqrt{F''} \]来获得结点 \(x, y\) 间的权重, 其中
\[Q_{\theta}: \mathbb{R}^{F'} \rightarrow \mathbb{R}^{F''}, \quad K_{\theta}: \mathbb{R}^{F'} \rightarrow \mathbb{R}^{F''}, \]作者是用两层 MLPs 来实现的. 最后的子图的 transition matrix 为:
\[\mathbf{P} = (p_{x, y}), \\ p_{x, y} = \frac{\exp(w_{x, y})}{\sum_{z \in \mathcal{N}_x} \exp(w_{x, z})}. \]其中 \(\mathcal{N}(x)\) 是 \(x\) 在 enclosing graph \(\mathcal{G}_{i, j}\) 中的一阶邻居.
-
由此, 我们可以从 \(\mathbf{P}\) 中获取结构信息 (注意, 下面的 \(i, j\) 表示我们所关心 link \(e_{ij}\) 所对应的结点):
-
node-level:
\[\text{node}^{\tau} = [\mathbf{P}^\tau]_{i,i} + [\mathbf{P}^{\tau}]_{j,j}. \]它描述了 \(i, j\) 的 loop structure.
-
link-level:
\[\text{link}^{\tau} = [\mathbf{P}^\tau]_{i,j} + [\mathbf{P}^{\tau}]_{j,i}. \]它描述了经过长度为 \(\tau\) 的 random walk 后由 \(i\) 到 \(j\) 或者由 \(j\) 到 \(i\) 的概率.
-
graph-level:
\[\text{graph}^{\tau} = \text{tr}[\mathbf{P}^{\tau}]. \]他描述了长度为 \(\tau\) 的 random walk 下结点的 loops 的概率.
-
-
一个形象的例子可以参考下图:
-
至此, 我们讨论了一般的子图的结构信息如何提取, 现在给定感兴趣的边 \(\{i,j\}\), 我们可以得到
\[\mathcal{G}_{i,j}^+ = (\mathcal{V}_{i,j}, \mathcal{E}_{i,j} \cup \{i, j\}), \\ \mathcal{G}_{i,j}^- = (\mathcal{V}_{i,j}, \mathcal{E}_{i,j} \setminus \{i, j\}). \]对于每一个子图我们都可以得到类似上面的结构信息, 不过作者认为, \(\text{graph}^{\tau, +}, \text{graph}^{\tau, -}\) 本身对于 link prediction 来说没有特别大的作用, 故采用
\[\Delta \text{graph}^{\tau} = \text{graph}^{\tau, +} - \text{graph}^{\tau, -}. \] -
最后的特征为:
\[\text{WP}_{\theta}(\mathcal{G}, \mathbf{Z}) = [w_{i, j}, ( \text{node}^{\tau, +}, \text{node}^{\tau, -}, \text{link}^{\tau, +}, \text{link}^{\tau, -}, \Delta \text{graph}^{\tau} )_{\tau=2}^{\tau_c}. ] \] -
基于此, 通过一个分类器 \(c_{\theta}\) (MLP + sigmoid) 将特征映射为 \([0, 1]\) 间的概率.
-
预测自不必说, 训练的时候, 作者采用 MSE 损失:
\[\min_{\theta} \quad \frac{1}{|\mathcal{E}^t|} \sum_{\{i, j\}\in \mathcal{E}^t} (y_{\{i, j\}} - c_{\theta} (\text{WP}_{\theta}(\mathcal{G}_{i,j}, \mathbf{Z}_{\{i, j\}}))^2. \]