Canonical labelling of graphs in linear average time

By László Babai, L. Kučera. 1979

How researchers see this paper

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

In Evaluation & Benchmarks

Citations in the corpus

The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “Although conceptually quite simple, the 1-dim WL method succeeds in characterising almost all graphs in linear time [7], although it cannot for instance partition the vertex set of regular graphs.”
How Powerful are Graph Neural Networks? (2018, methodology): “Our framework is inspired by the close connection between GNNs and the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Lehman, 1968), a powerful test known to distinguish a broad class of graphs (Babai & Kucera, 1979).”
An optimal lower bound on the number of variables for graph identification (1989, methodology): “This contrasts sharply with results in [10, 27] where it is shown that two variables suffice to identify all trees and almost all graphs, and that three variables suffice to identify all graphs of color class size 3.”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, result): “…with respect to graph classiﬁcation and show that in terms of distinguishing different graphs, these GCNs are at most as powerful as the Weisfeiler-Lehman isomorphism test [231] — a test which is able to distinguish a broad class of graphs [7] but also known to fail in some corner cases [26].”
How Powerful are Spectral Graph Neural Networks (2022, unknown): “The node labels assigned by 1-WL test can also be used to check if two nodes are isomorphic (Babai & Kucera, 1979; Srinivasan & Ribeiro, 2020), as two isomorphic nodes always have the same label while two non-isomorphic ones mostly have different labels.”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, methodology): “Recently, a graph kernel based on the 1-dimensional Weisfeiler-Lehman algorithm [6] has been proposed [3].”
Resisting structural re-identification in anonymized social networks (2008, methodology): “The vertex refinement technique is the basis of efficient graph isomorphism algorithms which can be shown to work for almost all graphs [3].”
A survey on graph kernels (2019, methodology): “Methods proposed for cheminformatics are shown in italics , kernels for attributed graphs in bold problem, see, e.g., (Babai and Kucera 1979).”
Enumerating Unique Computational Graphs via an Iterative Graph Invariant (2019, methodology): “The Weisfeiler–Lehman algorithm [5] uses an iterative coloring approach to come up with a canonical coloring on a graph, though subsequent work [1] shows that the algorithm can fail for some graphs.”
Logical complexity of graphs: a survey (2010, background): “(Babai and Kučera [8]) 3 color refinements split a random graph Gn,1/2 into color classes which are singletons with probability more than 1 − 1/2, for a constant c > 0 and all large enough n.”
Anonymizing Social Networks (2007, methodology): “The vertex refinement technique is the basis of efficient graph isomorphism algorithms which can be shown to work for almost all graphs [3].”
Graph Representation Learning (2020, methodology): “The WL algorithm is known to converge in at most |V| iterations and is known to known to successfully test isomorphism for a broad class of graphs [Babai and Kucera, 1979].”
Weisfeiler-Lehman Graph Kernels (2011, background): “4: Relabeling • Set l i (v) := f (s i (v)) for all nodes in G and G ′ . gorithm has been shown to be a valid isomorphism test for almost all graphs (Babai and Kucera, 1979).”
Graphs Identified by Logics with Counting (2015, background): “Even more strongly, it is known [4] that the fraction of graphs which are not identified is exponentially small in n.”