Identity-aware Graph Neural Networks

• 概
• ID-GNN

You J., Gomoes-Selman J., Ying R. and Leskovec J. Identity-aware graph neural networks. AAAI, 2021.

概

提出了一种能够超越 1-WL-Test 的 GNN.

ID-GNN

• ID-GNN 的 motivation 主要如下:

• 主要到, 传统的 MPNN, 即第 \(k\) 层:

  \[\mathbf{m}_u^{(k)} = \text{MSG}^{(k)} (\mathbf{h}_u^{(k-1)}), \\ \mathbf{h}_v^{(k)} = \text{AGG}^{(k)} ( \{ \mathbf{m}_u^{(k)}, u \in \mathcal{N}(v) \}, \mathbf{h}_v^{(k-1)} ). \]

  这种方式, 对于上图的三种任务, 其实都是无法区分的 (如果不考虑初始特征的差异), 因为虽然整体结构不同, 通过 MPNN 所导出的树的结构是一致的, 所以不同的节点也会有相同的节点表征.

• ID-GNN 的想法很简单, 就是为对 ego 节点 \(v\) 和其它节点采取不同的消息传播方式:

  \[\text{MSG}_{\mathbb{I}[s = v]} (h_s^{(k-1)}). \]

  \(\mathbb{I}[s=v] = 1\) 当 \(s=v\) 否则为 0.

• 具体的算法如上.