Random Graph Isomorphism

By László Babai, P. Erdös, S. Selkow. 1980

How researchers see this paper

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

In Graph Learning

Citations in the corpus

Learning Convolutional Neural Networks for Graphs (2016, background): “Due to the constant size k of the neighborhood graphs, the algorithm runs in time polynomial in the size of the original graph and, on average, in time linear in k (Babai et al., 1980).”
The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “It is also easy to solve for almost all graphs [4, 7].”
Graphs Identified by Logics with Counting (2015, background): “Moreover, a graph is asymptotically almost surely identified by C(2), that is, the fraction of graphs of size n which are not identified by C(2) tends to 0 as n tends to infinity [3].”
Detecting Similar Programs via The Weisfeiler-Leman Graph Kernel (2016, background): “Indeed, by a result from [1], for almost all graph, each final color already encodes the isomorphism type of the graph.”
An optimal lower bound on the number of variables for graph identification (1992, background): “Babai, ErdSs and Selkow [ 8 ] have shown that the 1-dim W-L algorithm already produces normal forms for all but an n -1/7 fraction of the nvertex graphs.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “isomorphic graphs does not provide the necessary granularity: even the 1-WL test can distinguish almost all (in the probabilistic sense) non-isomorphic graphs [75].”
Canonical labelling of graphs in linear average time (1979, background): “We prove that this algorithm leads to a CL with very large probability, the probability of rejection being (0 ( 1 )) n.”
An optimal lower bound on the number of variables for graph identification (1989, background): “Babai, Erd˝os and Selkow [ 8 ] have shown that the 1-dim W-L algorithm already produces normal forms for all but ann 1/7 fraction of then-vertex graphs.”
Base size, metric dimension and other invariants of groups and graphs (2011, background): “[6] showed that, in a random graph in G(n, 12 ), the set of 3 log n vertices of highest degree all have different degrees, and form a resolving set (asymptotically almost surely).”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “1-WL is known to succeed on almost all pairs of non-isomorphic graphs [2], and the power of k-WL further increases as k grows.”
Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements (2008, methodology): “For most graphs, this method distinguishes all the vertices [1], but it does not work in general.”
Can graph neural networks count substructures? (2020, background): “Moreover, WL is powerful enough to distinguish almost all pairs of non-isomorphic graphs except for rare counterexamples [3].”
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2013, background): “Babai, Erd¨os, and Selkow [2] showed that colour refinement distinguishes almost all graphs (in the G(n, 1 / 2 ) model).”
Logical complexity of graphs: a survey (2010, background): “(Babai, Erdős, and Selkow [7]) 2 color refinements split a random graph Gn,1/2 into color classes which are singletons with probability more than 1 − 1/ 7 √n, for all large enough n.”
Weisfeiler-Lehman Neural Machine for Link Prediction (2017, methodology): “First, after running Palette-WL, ties can be broken by running Nauty, which has an average time complexity of O ( K ) [21].”