Diffusion Improves Graph Learning

• 概
• 符号说明
• 本文思路

Gasteiger J., Weißenberger S., Günnemann S. Diffusion improves graph learning. In Advances in Neural Information Processing Systems (NIPS), 2019.

概

传统的 GCN 所用到的邻接矩阵 \(A\) 实际一种 1-hop 信息的度量, 本文通过 graph diffusion 和 sparsification 引入高阶信息的同时保留局部性质.

符号说明

• \(\mathcal{G = (V, E)}\);
• \(|\mathcal{V}| = N\);
• \(A \in \mathbb{R}^{N \times N}\), 邻接矩阵;
• \(D\), degree matrix.

本文思路

• 一般的 GCN 可以表述为:

  \[\tag{1} H \leftarrow \sigma(\tilde{A}HW). \]

• 它有很强的局部性, 事实上, 每一次更新, 每个节点会与它的 1-hop 邻居结点发生交互.

• 作者希望在此基础上进行扩展, 如果能够每次更新都能接触到高阶信息就好.

• 这个问题其实 spectral graph theory 中已经涉及了:

  \[g_{\xi}(L) \bm{h} = U \hat{G}_{\xi}(\Lambda)U^T \bm{h} = U(\sum_{j=0}^J \xi_j \Lambda^j) U^T \bm{h}, \]

  其中 \(L = U\Lambda U^T\).

• 但是 spectral graph theory 存在两个问题:

  1. 它本身的计算复杂度的问题;
  2. 其次 \(g_{\xi}(L)\) 丢失了 locality.

• 故作者采用如下的方式来解决上面的问题:

  1. 通过 graph diffusion 得到 diffusion matrix:

     \[S = \sum_{k=0}^{\infty} \theta_k T^k, \]

     其中 \(T^k\) 是 generalized transition matrix, 可以是

     \[T_{rw} = AD^{-1}, \\ T_{sym} = D^{-1/2} A D^{-1/2}, \\ \tilde{T}_{sym} = (wI + D)^{-1/2} (wI + A) (wI + D)^{-1/2}. \]

  2. 此时得到的 diffusion matrix 和 \(g_{\xi}(L)\) 一样通常是稠密的, 我们可以通过如下两种 sparsification 方法来得到稀疏化后的结果:

     • 每一列取 top-k 元素;
     • 设定阈值 \(\epsilon\), 且只保留大于阈值的元素.

  3. 记稀疏化后的 diffusion matrix 为 \(\tilde{S}\), 并令

     \[T_{sym}^{\tilde{S}} = D_{\tilde{S}}^{-1/2} \tilde{S} D_{\tilde{S}}^{-1/2}. \]

• 我们可以用 \(T_{sym}^{\tilde{S}}\) 来替代 (1) 中的 \(A\).