AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Power Iterated Color Refinement
Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe

Last modified: 2014-06-21

Abstract


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.

Keywords


Fractional Automorphisms; Weisfeiler-Lehman; Conditional Gradient; Hashing; Power Iteration; Lifted Inference; Graph Kernels; Matrix-Vector Multiplication

Full Text: PDF