pith. machine review for the scientific record. sign in

arxiv: 1101.5211 · v1 · submitted 2011-01-27 · 🧮 math.CO

Recognition: unknown

The Weisfeiler-Lehman Method and Graph Isomorphism Testing

B. L. Douglas
Authors on Pith no claims yet
classification 🧮 math.CO
keywords methodassumptionsgraphrecursiveanalysedcasescertaincharacterise
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. How Powerful are Graph Neural Networks?

    cs.LG 2018-10 accept novelty 9.0

    GIN is provably as expressive as the Weisfeiler-Lehman graph isomorphism test, while GCN and GraphSAGE have strictly weaker discriminative power on some graphs.

  2. Semi-Supervised Classification with Graph Convolutional Networks

    cs.LG 2016-09 unverdicted novelty 7.0

    Graph Convolutional Networks enable semi-supervised learning on graphs by learning node representations that combine local structure and node features, outperforming prior methods on citation networks and knowledge graphs.