An optimal lower bound on the number of variables for graph identification

By Jin-Yi Cai, Martin Fürer, Neil Immerman. 1989

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

How Powerful are Graph Neural Networks? (2018, methodology): “…we characterize the representational capacity of GNNs via a slightly weaker criterion: the Weisfeiler-Lehman (WL) graph isomorphism test that is known to work well in general, with some few exceptions, in particular, regular graphs (Cai et al., 1992; Douglas, 2011; Evdokimov & Ponomarenko, 1999).”
Covariant Compositional Networks For Learning Graphs (2018, background): “More broadly, the classic Weisfeiler–Lehman test of isomorphism also follows the same logic (Weisfeiler & Lehman, 1968; Read & Corneil, 1977; Cai et al., 1992), and so does the related Weisfeiler–Lehman kernel, arguably the most successful kernel-based approach to graph learning (Shervashidze et…”
Provably Powerful Graph Networks (2019, background): “Several known results of WL and FWL algorithms (Cai et al., 1992; Grohe, 2017; Morris et al., 2018; Grohe and Otto, 2015) are: 1.”
Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement (2013, unknown): “Now Immerman and Lander’s theorem states that for all graphs G (possible coloured and/or directed) and all vertices v, w ∈ V (G) , the vertices v and w have the same colour in the coarsest bi-stable colouring of G if and only if they are C 2 -equivalent.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “It follows from results of [15] that for every k ≥ 0, k-WL fails to distinguish the graphs Gk and Hk of our constructed family.”
Accurate Decentralized Application Identification via Encrypted Traffic Analysis Using Graph Neural Networks (2021, background): “It has been proved that GNNs are at most as representational as the WL test in distinguishing different graph structures [8].”
Graphs Identified by Logics with Counting (2015, methodology): “The graphs G and G′ referred to in the fact are obtained by replacing every vertex v of a suitable connected graph by a gadget that only depends on the degree of v (see [6] for details).”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “By increasing k , the algorithm gets more powerful in terms of distinguishing non-isomorphic graphs, i.e., for each k ≥ 2 , there are non-isomorphic graphs which can be distinguished by the ( k + 1 )-WL but not by the k -WL (Cai, F ¨ urer, and Immerman 1992).”
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].”
Inductive Relation Prediction by Subgraph Reasoning (2019, background): “Barcel ´ o et al. (2020) presented a strong connection between the expressive powers of GNNs and a subset of ﬁrst order predicate logic—FOC 2 — leveraging their connections to the WL isomorphism test (Cai et al., 1992).”
Relational Pooling for Graph Representations (2019, background): “WL-GNNs have a representation shortcoming that they inherit from the WL test (Arvind et al., 2017; Cai et al., 1992; F ¨ urer, 2017).”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, background): “Their failure in this task is unsurprising: 1 -WL is proved to fall short of distinguishing such pairs of non-isomorphic regular graphs [6], and hence neither can GIN [42]; by Theorem 7, 2 -IGN is unable to distinguish them either.”