Graphs Identified by Logics with Counting
By Sandra Kiefer, Pascal Schweitzer, Erkal Selman. 2015
52 citations recorded by the source corpus.
We classify graphs and, more generally, finite relational structures that are identified by \({C^{2}}\), that is, two-variable first-order logic with counting. Using this classification, we show that it can be decided in almost linear time whether a structure is identified by \({C^{2}}\). Our classification implies that for every graph identified by this logic, all vertex-colored versions of it are also identified. A similar statement is true for finite relational structures.
Subfields: Computational Theory and Mathematics
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
- Christopher Morris
- Petra Mutzel
- Gaurav Rattan
- William L. Hamilton
- Matthias Fey
- Martin Ritzert
- Jan Eric Lenssen
- Martin Grohe
Citations in the corpus
- Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, positive): “Since the power of the 1-WL has been completely characterized, see, e.g., (Arvind et al. 2015; Kiefer, Schweitzer, and Selman 2015), we can transfer these results to the case of GNNs, showing that both approaches have the same shortcomings.”
- Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, background): “For k = 1, the power of the algorithm has been completely characterized [1, 20].”
- Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “[63] S.”
- What graph neural networks cannot learn: depth vs width (2019, background): “The equivalence implies that anonymous networks are blind to the many graph properties that WL cannot see: e.g., any two regular graphs with the same number of nodes are identical from the perspective of the WL test (Arvind et al., 2015; Kiefer et al., 2015).”