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

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

Subfields: Optimization & Training, Algorithms & Complexity

How researchers see this paper

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

In Optimization & Training

In Algorithms & Complexity

Citations in the corpus

The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “Properties of the ‘k-equivalent’ graph families constructed in Cai, Fürer and Immerman [10] and Evdokimov and Ponomarenko [15] are analysed relative the the recursive k-dim WL method.”
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:”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “We note here that the above variant is not equal to the folklore variant of k-WL described in (Cai, Fürer, and Immerman 1992), which differs slightly in its update rule.”
Can graph neural networks count substructures? (2020, methodology): “For k ≥ 2, it is known that (k + 1)-WL is strictly more powerful than k-WL, in the sense that there exist pairs of graph distinguishable by the former but not the latter [6].”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, methodology): “In contrast, in most graph theory papers on graph isomorphism (Cai et al., 1992; Fürer, 2017; Arvind et al., 2019) the k-WL term is used to describe the algorithms referred to as k-FWL in GNN papers.”
Relational Pooling for Graph Representations (2019, background): “These cannot give distinct representations for graphs that cannot be distinguished by the standard WL isomorphism test (Cai et al., 1992; Xu et al., 2019).”
Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, background): “We also show that the SWL test and MPSN are not less powerful than the 3-WL test (Cai et al., 1992; Morris et al., 2019).”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “[40] J.”
Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements (2008, methodology): “In [3], Cai, Immerman and Fürer showed how to construct pairs of nonisomorphic n-vertex graphs which are not distinguished by the k-WL method, even for k = Ω(n).”
Weisfeiler-Lehman Graph Kernels (2011, background): “If the sets are identical after n iterations, it means that either G and G ′ are isomorphic, or the algorithm has not been able to determine that they are not isomorphic (see Cai et al., 1992, for examples of graphs that cannot be distinguished by this algorithm or its higherdimensional variants).”
Non-Isomorphic Graphs with Cospectral Symmetric Powers (2009, background): “Therefore, given x ∈ X we have dG′(x) > m > n which proves the left-hand side inequality in (7).”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, methodology): “[9], and the δ-k-dimensional Weisfeiler-Leman algorithm (δ-k-WL), which is a variant of the k-dimensional combinatorial vertex coloring algorithm due to Malkin [24].”
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, methodology): “Cai–Fürer–Immerman construction The series cfi-〈n〉 consists of 3-regular graphs built from a random 3-regular graph on n vertices by replacing each vertex with a gadget graph and each edge with two edges as described in [11].”
Elements of Finite Model Theory (2004, background): “27 is from Cai, Fiirer, and Immerman [30] (see also Otto [191], as well as Gire and Hoang [91] for extensions).”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “[15] J.”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “[238] study the expressiveness of certain GCN models with respect to graph classification 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] bu”
Graphs Identified by Logics with Counting (2015, methodology): “This stands in contrast to a remark in [6] claiming that a graph G identified by C can be canonized in polynomial time.”