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:
- 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.
- 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.
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.
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