On the Power of Color Refinement

By Vikraman Arvind, J. Köbler, Gaurav Rattan, Oleg Verbitsky. 2015

48 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition

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 Computer Vision and Pattern Recognition

Citations in the corpus

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, background): “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.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “The heuristic is well understood and is known to have many shortcomings (Arvind et al., 2015), such as being unable to detect cyclic information or distinguish between non-isomorphic bipartite graphs.”
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): “[4] V.”
Graphs Identified by Logics with Counting (2015, result): “Independently of our work, Arvind, Köbler, Rattan and Verbitsky [1] have investigated the structure of undirected graphs identified by C obtaining results similar to the ones we provide in Sect.”
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).”