概
为每个结点抽取一子图作为结点的代表, 然后推理过程仅限定在子图上, 作者证明了这种方式的表达能力.
符号说明
-
\(\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)\) 则是将图表征转换为结点的表征, 以用于后续的任务.
-
本文主要聚焦的点在于这种方式的表达能力, 作者证明了:
- Shadow-GNN 是 local-smoothing 的 (但很难 over-smoothing), 所以允许多层的 GNN 网络架构;
- Shadow-SAGE 有着和 GraphSAGE 相似的逼近能力;
- Shadow-GIN 有着和 GIN 一样的 1-WL test 的能力.
-
至于子图的具体提取方式, 作者主要考虑了启发式的抽取方式: 根据 pagerank weight 采样, 或者直接根据 hops 选取 (一般 2, 3 hops 就足够了).
代码
[official]
- Decoupling Networks Neural Depth Scopedecoupling networks neural depth learning networks neural hello graph condensation networks neural understanding plasticity networks neural networks neural bigdataaiml-ibm-a introduction pre-train learning networks neural convolutional networks neural cnn powerful networks spectral neural sequence learning networks neural networks learning neural comp