The Weisfeiler-Lehman Method and Graph Isomorphism Testing

By B. Douglas. 2011

67 citations recorded by the source corpus.

Properties of the `$k$-equivalent' graph families constructed in Cai, F\"{u}rer and Immerman, and Evdokimov and Ponomarenko are analysed relative the the recursive $k$-dim WL method. An extension to the recursive $k$-dim WL method is presented that is shown to efficiently characterise all such types of `counterexample' graphs, under certain assumptions. These assumptions are shown to hold in all known cases.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

In Graph Learning

Citations in the corpus

Semi-Supervised Classification with Graph Convolutional Networks (2016, neutral): “For an in-depth mathematical discussion of the WL-1 algorithm see, e.g., Douglas (2011).”
Learning Convolutional Neural Networks for Graphs (2016, methodology): “For a given graph, we used P ATCHY - SAN to compute a receptive ﬁeld for all nodes using the 1 -dimensional Weisfeiler-Lehman (Douglas, 2011) (1-WL) algorithm for the normalization. torus is a periodic lattice with 10 , 000 nodes; random is a random undirected graph with 10 , 000 nodes and a degree…”
How Powerful are Graph Neural Networks? (2018, methodology): “…we characterize the representational capacity of GNNs via a slightly weaker criterion: the Weisfeiler-Lehman (WL) graph isomorphism test that is known to work well in general, with some few exceptions, in particular, regular graphs (Cai et al., 1992; Douglas, 2011; Evdokimov & Ponomarenko, 1999).”
Graphite: Iterative Generative Modeling of Graphs (2018, methodology): “The k -dim Weisfeiler-Lehman (WL) algorithm [52, 6] is a heuristic test of graph isomorphism between any two graphs G and G (cid:48) .”
Provably Powerful Graph Networks (2019, background): “It is guaranteed that no more than l = poly ( n ) iterations are required (Douglas, 2011).”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “These are known in the literature as k-isoregular graphs [43], and the most well-known example is the Strongly Regular (SR) graph family, for k 1⁄4 2 (more details in Appendix B).”