Towards a practical k-dimensional Weisfeiler-Leman algorithm
By Christopher Morris, Petra Mutzel. 2019
13 citations recorded by the source corpus.
The $k$-dimensional Weisfeiler-Leman algorithm is a well-known heuristic for the graph isomorphism problem. Moreover, it recently emerged as a powerful tool for supervised graph classification. The algorithm iteratively partitions the set of $k$-tuples, defined over the set of vertices of a graph, by considering neighboring $k$-tuples. Here, we propose a \new{local} variant which considers a subset of the original neighborhood in each iteration step. The cardinality of this local neighborhood, unlike the original one, only depends on the sparsity of the graph. Surprisingly, we show that the local variant has at least the same power as the original algorithm in terms of distinguishing non-isomorphic graphs. In order to demonstrate the practical utility of our local variant, we apply it to supervised graph classification. Our experimental study shows that our local algorithm leads to improved running times and classification accuracies on established benchmark datasets.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Materials Chemistry
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
- Yaron Lipman
- Haggai Maron
- Hadar Serviansky
- Heli Ben-Hamu
- Jure Leskovec
- William L. Hamilton
- Nimrod Segol
- Rex Ying
In Computational Theory and Mathematics
In Materials Chemistry
- Yaron Lipman
- Heli Ben-Hamu
- Haggai Maron
- Hadar Serviansky
- William L. Hamilton
- Jure Leskovec
- Nimrod Segol
- Rex Ying
Citations in the corpus
- Provably Powerful Graph Networks (2019, methodology): “2017). Lei et al. (2017) showed that their suggested GNN has a theoretical connection to the WL test. WL tests were also used in Zhang and Chen (2017) for link prediction tasks. In a concurrent work, Morris and Mutzel (2019) suggest constructing graph features based on an equivalent sparse version o”