ICLR19一篇从图同构测试（Graph Isomorphism Test）角度说明GNN性能表现的论文

### 解决的问题

GNN性能表现好的原因是什么？

#### 贡献：

1. 证明了GNN的性能上限是Weisfeiler-Lehman (WL) test，最多只和它一样有效
2. 给出了GNN在什么条件下能够和WL test一样有效
3. 指明了主流GNN框架如GCN、GraphSage无法区分的图结构，以及它们能够区分的图结构的特点
4. 提出了一个简单有效的框架GIN，能够与WL test一样有效

### 做法及创新

#### GNN与WL test

1. Aggregate：聚合邻域内的信息

2. Combine：将聚合后的邻域信息与当前顶点信息结合

• 聚合顶点及其邻域的标签信息
• 将聚合后的标签集合哈希成唯一的新标签

Note that node feature vectors in the WL test are essentially one-hot encodings and thus cannot capture the similarity between subtrees. In contrast, a GNN satisfying the criteria in Theorem 3 generalizes the WL test by learning to embed the subtrees to low-dimensional space. This enables GNNs to not only discriminate different structures, but also to learn to map similar graph structures to similar embeddings and capture dependencies between graph structures.

### 数据集

MUTAG、PTC、NCI1、PROTEINS、COLLAB、IMDB-BINARY、IMDB-MULTI、REDDIT-BINARY、REDDIT-MULTI5K