Decoupling the Depth and Scope of Graph Neural Networks

• 概
• 符号说明
• Shadow-GNN
• 代码

Zeng H., Zhang M., Xia Y., Srivastava A., Malevich A., Kannan R., Prasanna V., Jin L. and Chen R. Decoupling the depth and scope of graph neural networks. NIPS, 2021.

概

为每个结点抽取一子图作为结点的代表, 然后推理过程仅限定在子图上, 作者证明了这种方式的表达能力.

符号说明

• \(\mathcal{G} = (\mathcal{V}, \mathcal{E}, \bm{X})\), global graph;

• \(\mathcal{V}\), node set;

• \(\mathcal{E} \subset \mathcal{V} \times \mathcal{V}\), edge set;

• \(\mathbf{X} \in \mathbb{R}^{|\mathcal{V}| \times d}\), node feature matrix;

• \(\bm{A} \in \mathbb{R}^{|\mathcal{V} \times \mathcal{V}|}\), adjacency matrix;

• \(\mathcal{G}_{[u]}\), 以结点为 \(u\) 中心的子图, 这个子图可以是通过一些启发式的方法从 global graph \(\mathcal{G}\) 采样得到的, 也可以是学习的得到的 (比如以 \(u\) 为中心的 2-hop 子图);

• \(\bm{X}_{[u]}, \bm{A}_{[u]}\) 就是子图 \(\mathcal{G}_{[u]}\) 所诱导的特征矩阵和邻接矩阵, 且规定:

  \[[\bm{X}_{[u]}]_v = \bm{0}, \quad \forall v \not \in \mathcal{V}_{[u]}, \\ [\bm{A}_{[u]}]_{v,w} = \bm{0}, \quad v \not \in \mathcal{V}_{[u]} \text{ or } w \not \in \mathcal{V}_{[u]}. \]

Shadow-GNN

• Shadow-GNN 的想法其实很简单, 就是假设我们有一个 GNN 的网络, 其为:

  \[\bm{H} = f(\bm{X}; \mathcal{G}), \]

  \(u\) 的表征为 \(\bm{H}_u\). Shadow-GNN 做如下的一个改动:

  \[\bm{H}_u := \text{READOUT} \circ f \circ \text{EXTRACT}(u;\bm{X}; \mathcal{G})), \]

• \(\text{EXTRACT}(\cdot)\) 是提取中心为 \(u\) 的子图, 而 \(\text{READOUT}(\cdot)\) 则是将图表征转换为结点的表征, 以用于后续的任务.

• 本文主要聚焦的点在于这种方式的表达能力, 作者证明了:

  1. Shadow-GNN 是 local-smoothing 的 (但很难 over-smoothing), 所以允许多层的 GNN 网络架构;
  2. Shadow-SAGE 有着和 GraphSAGE 相似的逼近能力;
  3. Shadow-GIN 有着和 GIN 一样的 1-WL test 的能力.

• 至于子图的具体提取方式, 作者主要考虑了启发式的抽取方式: 根据 pagerank weight 采样, 或者直接根据 hops 选取 (一般 2, 3 hops 就足够了).

代码

[official]