图神经网络与图同构测试

图神经网络在很多任务上取得了非凡的成功，如：

(1) Node Classification

(2) Link Prediction

(3) Graph Classification

图神经网络的表示能力究竟如何呢？例如，两个不一样的图，对于某个神经网络来说，是否足够可以区分呢？

图神经网络的第$k$k层为：

为了研究图神经网络的表达能力，需要一种叫multiset的东西，平常我们常说的集合是指不相同元素的聚集，但multiset却可以由重复的元素出现。
我们还需要Weisfeiler-Lehman图同构测试算法，感兴趣的小伙伴去找找古董资料看看哦 ：）
【文献：Boris Weisfeiler and AA Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsia, 2(9):12–16, 1968.】

Any aggregation-based GNN is at most as powerful as the WL test in distinguishing different graphs.
A natural follow-up question is whether there exist GNNs that are, in principle, as powerful as the WL test? Our answer, in Theorem 3, is yes: if the neighbor aggregation and graph-level readout functions are injective, then the resulting GNN is as powerful as the WL test.



图同构网络GIN (ICLR 2019)

传送门： 图神经网络GIN原文
https://cs.stanford.edu/people/jure/pubs/gin-iclr19.pdf