Paper | How Powerful are Graph Neural Networks
Intro
新的Graph Networks基本上都是基于实验直觉, 启发式探索以及反复试验得来的. 基本上没有理论的解释对于GNN.
我们提出了理论的框架起分析GNN的表示能力. GIN受到了GNN的近距离连接和Weisfeiler-Lehman(WL) test的影响.
WL test就是迭代的更新一个给定节点的特征通过不断聚合相邻节点的特征. WL test的关键在于injective aggregation 它将不同邻居节点映射到不同特征向量. (就是这个映射函数f是单射的)
我们的框架首先表示了给定节点邻居的特征向量的集合作为multiset, GNN内的邻居聚合可以被想成在_multiset_之上的聚合函数. 因此, 表示能力越强, GNN可以把不同的_multiset_聚合到不同的表示.
Preliminaries
节点v更新分为两步, aggregate和combine
$$
a_v^{(k)} = AGGREGATE^{(k)}({h_u^{(k-1)}:u\in N(v})
$$
$$
h_v^{(k)}=COMBINE^{(k)}(h_v^{(k-1)}, a_v^{(k)})
$$
Aggregate把所有邻居节点的信息聚合
Combine把聚合的信息加到当前节点上, 作为更新的信息
k是迭代的步数, 是1阶邻居迭代k次
对于节点分类问题, 节点的最后一层hv可以用来分类. 对于图分类, 再通过一个Readout function可以获得图的表示hG
$$
h_G=READOUT({h_v^{(K)}|v\in G})
$$
Readout可以是简单的求和也可以是复杂的图上的pooling.
Theoretical Framework: Overview
邻居节点集合的特征向量构成了multiset, 相同的元素可以出现多次, 因为不同的节点可以有相同的特征向量.
比如节点i和节点j都有且仅有E,F,G三个邻居节点, 那么他们通过网络映射出来的表示应该是相同的.
比如节点i有邻居节点(2, 2, 2), 节点j有邻居节点(1, 2, 3), 如果都通过(1, 1, 1)这样一个映射函数那么得到的表示是相同的, 说明这个映射不是一个单射函数, 也就不是powerful的GNN.
最powerful的GNN不会映射两个不同的邻居节点集合(multisets), 到一个相同的表示. 聚合函数是单射的.
Graph Isomorphism Network
我们想让同构图被映射到相同的表示, 非同构图被映射到不同的表示.
如果邻居聚合和图上的readout function都是单射的, GNN的结果就和WL test一样powerful.
满足定理3的就是powerful GNN, 不满足的就是less powerful GNN.
GIN更新节点