PEBBLE GAMES AND LINEAR EQUATIONS

By Martin Grohe, Martin Otto. 2012

104 citations recorded by the source corpus.

Abstract We give a new, simplified and detailed account of the correspondence between levels of the Sherali–Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler–Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level k Sherali–Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali–Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

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, neutral): “All rights reserved. kernel (Shervashidze et al. 2011), which is based on the 1- dimensional Weisfeiler-Leman graph isomorphism heuristic (Grohe 2017, pp. 79 ff.), generates node features through an iterative relabeling, or coloring, scheme: First, all nodes are assigned a common initial color; the…”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “…complexity (Immerman & Lander, 1990), Sherali-Adams relaxations of the natural integer linear program for the graph isomorphism problem (Atserias & Maneva, 2013; Grohe & Otto, 2015; Malkin, 2014), homomorphism counts (Dell et al., 2018), and quantum isomorphism games (Atserias et al., 2019).”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, methodology): “Equivalence to logic [17], Sherali-Adams relaxations of the natural integer linear program for the graph isomorphism problem [2, 15, 24], homomorphism counts [12], and quantum isomorphism games [3] have been shown.”
Graphs Identified by Logics with Counting (2015, background): “The k-th level of the Sherali-Adams hierarchy of a natural linear integer programming formulation of graph isomorphism essentially corresponds to the expressive power of C [2, 12].”