How Powerful Are Graph Neural Networks?

How Powerful Are Graph Neural Networks?

提供了一个理论框架，来研究GNN的性质。

Intro

我们的框架是由此激励的：GNN与Weisfeiler-Lehman graph isomorphism test的联系。

为了证明，我们框架首先将所以vector的特征考虑为multiset，然后propagation就相当于在这个multiset上进行的。

Preliminary

前面的表示是比较常用的。

WL test 图的isomorphism问题是看两张图是否能够拓扑上一致。目前还没有P的解决方案。除了一些特殊情况，WL test是一种高效的可以用来测试一系列graph是否同构。WL test，或者WL embedding，其变种之一就是Fingerprint。

Theoretical Framework： Overview

只有当两个node开始的subtree一样的时候，它们才会在embedding space上同一个点表示。（这个在node feature比较少的时候会产生额外的collision）

Building Powerful Graph Neural Networks

证明了一些。

Graph Isomorphism Network (GIN)

sum aggregation可以保持injective特性。

根据universal approximation theorem，可以用MLP作为hashing function。

那么node的更新方式就是

$$hv^k = MLP^k ((1+\epsilon^k) \cdot h_v^{k-1} + \sum{u \in N(v)} h_u^{k-1} )$$

那么$$MLP$$在这里是$$R^d \to R^d$$?

Graph-Level Readout of GIN

$$h_G = CONCAT(READOUT( {h_v^k | v \in G} )| k=1, 2, ..., K)$$

注意，这里concat是非常关键的一步。如果仅仅是readout最后一层，就和WL差不多。

Appendix

总的来说，就是从理论上证明了GNN不比WL差。

几个问题

  1. hashing会带来collision
  2. social network, GIN比较好是有道理的。而molecule可以是图，但不仅仅是图，isomorphism不够。因为它还有空间结构，有一些键/bond稍微变动一下，它的反应结果就会完全不一样。所以spatial information很重要。isomorphic molecule can have different properties.
  3. WL test，Morgan Fingerprint就是WL embedding的一个变种，而且也的确做得很好。但是GIN不确定。
  4. 熟悉一下这几个数据集。one-hot encoding?

results matching ""

    No results matching ""