Power Iterated Color Refinement

By Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe. 2014

41 citations recorded by the source corpus.

Color refinement is a basic algorithmic routine for graph isomorphismtesting and has recently been used for computing graph kernels as well as for lifting belief propagation and linear programming. So far, color refinement has been treated as a combinatorial problem. Instead, we treat it as a nonlinear continuous optimization problem and prove thatit implements a conditional gradient optimizer that can be turned into graph clustering approaches using hashing and truncated power iterations. This shows that color refinement is easy to understand in terms of random walks, easy to implement (matrix-matrix/vector multiplications) and readily parallelizable. We support our theoretical results with experiments on real-world graphs with millions of edges.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Graph Learning

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Graph Learning

Citations in the corpus

Learning Convolutional Neural Networks for Graphs (2016, methodology): “Color reﬁnement has attracted considerable interest in the ML community since it can be applied to speed-up inference in graphical models (Kersting et al., 2009; 2014) and as a method to compute graph kernels (Shervashidze et al., 2011).”
An End-to-End Deep Learning Architecture for Graph Classification (2018, background): “The connection between discrete WL, continuous optimization, and random walks have also been studied in (Boldi et al. 2006; Kersting et al. 2014; Kipf and Welling 2016) etc.”
Propagation kernels: efficient graph kernels from propagated information (2014, methodology): “For all wl computations, we used the fast implementation12 introduced in (Kersting et al. 2014).”
Weisfeiler-Lehman Neural Machine for Link Prediction (2017, methodology): “On the other hand, a hashing-based WL [13] is much faster, but is no longer stable: the vertex ordering is not preserved between iterations.”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, methodology): “B. Sparse Linear Algebra Implementation Kersting, Mladenov, Garnett, and Grohe [10] proposed a linear algebra based implementation of the 1-WL: Let G = ({v1, . . . , vn}, E) be a graph with adjacency matrix A, let c0 = (l0(v1), . . . , l 0(vn)).”
Ordered Decompositional DAG kernels enhancements (2015, background): “All these kernels adopt an hashing function, similar in spirit to [45].”
Learning Graph Representations with Embedding Propagation (2017, methodology): “This is reminiscent of power iteration algorithms which are used for such problems as computing the PageRank for the web graph [33], running label propagation algorithms [47], performing isomorphism testing [16], and spectral clustering [25].”