Power Iterated Color Refinement

Kristian Kersting, Martin Mladenov, Roman Garnett, Martin Grohe

Abstract

Color Refinement (CR) is a cornerstone of graph isomorphism testing and graph kernels. Traditionally viewed as a discrete combinatorial procedure, this paper demonstrates that CR is equivalent to a symmetry-regularized conditional gradient optimization process. By leveraging this continuous perspective, the authors introduce Hashed and Power Iterated variants that are highly parallelizable and capable of processing massive, weighted graphs with millions of edges. Empirical evaluations show that these methods outperform standard Weisfeiler-Lehman implementations and efficiently handle graphs with large diameters.

Introduction

Determining graph isomorphism—whether two graphs are structurally identical—is a central challenge in graph theory. The standard heuristic, Color Refinement (CR), iteratively partitions nodes based on neighborhood colors. Despite its utility, CR has remained isolated from the continuous optimization techniques that drive modern machine learning. This gap limits its applicability to weighted graphs and hinders its integration into parallel computing frameworks.

This work bridges the divide by reframing CR as an optimization problem: finding Fractional Graph Automorphisms (FGA). By viewing CR through the lens of Conditional Gradient (CG) methods, the authors unlock new algorithmic possibilities for scalability and generalization.

Optimization Perspective on Color Refinement

The authors prove that CR is equivalent to solving an optimization task using a modified Conditional Gradient (CG) approach. Standard Frank-Wolfe algorithms often converge to "integral" (all-or-nothing) solutions that fail to capture the coarsest equitable partition. To resolve this, the authors introduce CGCR (Conditional Gradient for Color Refinement), which employs symmetry-regularization to cluster nodes with identical gradients, ensuring the algorithm finds the most general solution (the Coarsest Equitable Partition).

Scalable Variants

To address the computational demands of large graphs, two primary variants are proposed:

  1. HCGCR (Hashed CGCR): This version utilizes perfect hashing based on prime numbers to identify identical node neighborhoods. This reduces iteration complexity to $O(n + m)$, where $n$ is the number of nodes and $m$ is the number of edges, making it highly efficient for sparse graphs.
  2. PICGCR (Power Iterated CGCR): By connecting CR to Power Iteration (similar to PageRank), the authors show that color classes correspond to steady-state distributions of "color-preferred" random walks. This variant is particularly effective for graphs with large diameters, such as chains or grids.

Experimental Evaluation

The proposed methods were evaluated against standard benchmarks and massive real-world networks.

Performance on Weighted and Kernel Datasets

A significant advantage of the optimization-based approach is its natural extension to weighted graphs. Traditional combinatorial solvers often struggle with non-discrete edge weights. As shown in the performance comparison below, the Hashed and CGCR methods provide competitive runtimes on standard biological and chemical datasets, while successfully handling their weighted counterparts.

Performance comparison on graph kernel benchmarks and weighted variants.

Scalability and Large-Diameter Graphs

The scalability of the Hashed and Power Iterated versions was tested on networks with millions of edges. On social and web graphs like flickr and web-Google, the Hashed version (HCGCR) achieved remarkable speeds, processing nearly 10 million edges in under 2 seconds. For structural graphs with large diameters, such as chain100001, the Power Iterated (PIflex) version significantly reduced the number of iterations required compared to standard hashing.

Scalability and runtime performance on large-scale and structural graphs.

Conclusion

By establishing a formal link between color refinement and continuous optimization, this work provides a rigorous foundation for graph isomorphism heuristics. The resulting algorithms are not only faster and more scalable than traditional implementations but also extend the reach of CR to weighted graphs and parallel architectures. Future work may explore different norms for fractional automorphisms, potentially impacting graph compression and model lifting.

Summary updated

Abstract

Color refinement is a basic algorithmic routine for graph isomorphism testing 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 that it 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.
BibTeX
@inproceedings{kersting2014power,
  author = {Kristian Kersting and Martin Mladenov and Roman Garnett and Martin Grohe},
  title = {{Power Iterated Color Refinement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8992},
}
Figure