Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective

of the GNN depends on ○ ability to produce different output for non-isomorphic graphs. ○ 1-WL=2-WL <3-WL<4-WL<......<k-WL ○ We can classify GNN by equivalence of WL test order • k>2, k-WL GNN needs ○ O(n^(k-1)) memory, O(n^k) CPU time 2 should be different Graphs are taken from Expressive power of graph neural networks and the Weisfeiler-Lehman test By M. Bronstein