The Weisfeiler-Lehman Method and Graph Isomorphism Testing

Abstract

Properties of the `$k$-equivalent' graph families constructed in Cai, Fü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.

References in corpus (2)

• Two-particle quantum walks applied to the graph isomorphism problem
• k-Boson Quantum Walks Do Not Distinguish Arbitrary Graphs

Cited by in corpus (14)

• Semi-Supervised Classification with Graph Convolutional Networks
• How Powerful are Graph Neural Networks?
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Strategies for Pre-training Graph Neural Networks
• Graphite: Iterative Generative Modeling of Graphs
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Expressive Power of Invariant and Equivariant Graph Neural Networks
• Provably Powerful Graph Networks
• Deep Graph Similarity Learning: A Survey
• On the Equivalence Between Temporal and Static Graph Representations for Observational Predictions
• Learning Graph-Level Representations with Recurrent Neural Networks
• On quantum invariants and the graph isomorphism problem
• Modeling Edge Features with Deep Bayesian Graph Networks
• Network Representation Learning: From Traditional Feature Learning to Deep Learning