Abstract
Measuring graph similarity is critical for various machine learning tasks, yet existing methods like the Weisfeiler-Lehman (WL) framework and Wasserstein-based kernels face significant challenges in scalability and discriminative power. We present the Isolation Graph Kernel (IGK), a novel approach that leverages Isolation Kernels to map node attributes into a high-dimensional Hilbert space. This mapping ensures that WL-style aggregations remain injective, preventing the "shrinking" effect where distinct graphs converge to similar representations. Empirically, IGK demonstrates superior accuracy across benchmark datasets and achieves linear scalability, processing large-scale datasets orders of magnitude faster than state-of-the-art alternatives.
Introduction
The Isolation Graph Kernel (IGK) represents a significant advancement in measuring graph similarity. By combining Isolation Kernels (IK) with Kernel Mean Embedding (KME), IGK captures complex node attribute distributions without the massive computational overhead associated with the Wasserstein distance. This allows for high accuracy and exceptional speed, particularly on large-scale datasets.
The Limitations of Current Frameworks
Traditionally, the Weisfeiler-Lehman (WL) framework has been the standard for graph similarity, using iterative neighbor aggregation to create structural fingerprints. While effective, standard WL schemes often lose discriminative power as iterations increase—a phenomenon known as "shrinking," where different graphs converge toward the same center point in the input space.
Recent improvements, such as the Wasserstein Weisfeiler-Lehman (WWL) kernel, enhanced accuracy by treating graphs as distributions of node vectors. However, WWL introduces a computational bottleneck: the Wasserstein distance has a complexity of $O(n^3 \log n)$, rendering it impractical for large datasets.
The IGK Methodology
The proposed Isolation Graph Kernel (IGK) constructs graph representations through three hierarchical embedding layers:
- Dataset-Wide Node Embedding: IGK utilizes an Isolation Kernel (IK), a data-dependent kernel that builds a feature map based on the global distribution of node attributes across the entire dataset. This allows the model to identify dense and sparse regions in the attribute space.
- Graph-Specific Node Embedding: A WL-style aggregation is applied to these IK-mapped vectors within a high-dimensional Hilbert space, rather than raw input space.
- Mean Embedding of a Graph: Finally, Kernel Mean Embedding (KME) represents the entire graph as the average of its node embeddings.
By producing an explicit feature map, IGK can be paired with fast linear SVMs, avoiding the need to compute a full $N \times N$ kernel matrix.
Key Insights: Overcoming the "Shrinking" Problem
A core contribution of this work is the theoretical and visual demonstration of the "shrinking" problem. In standard input space, WL iterations cause non-isomorphic graphs to converge toward a common "graph center," limiting the effectiveness of deeper iterations.
By moving the WL process into a Hilbert space using a characteristic kernel like IK, the mapping becomes injective. This preserves the uniqueness of the graph's distribution even as iterations increase, maintaining discriminative power for larger subgraphs.
Experimental Results and Scalability
The authors evaluated IGK against 13 benchmark datasets spanning bioinformatics, chemistry, and social networks. IGK achieved the highest average rank in accuracy, significantly outperforming WWL and Hash Graph Kernel (HGK).
Beyond accuracy, IGK's primary advantage is its scalability. On the TWITTER dataset (144,000+ graphs), IGK processed the data in a fraction of the time required by competitors, many of which failed to complete within 24 hours.
As shown in the runtime analysis, IGK scales linearly with the number of graphs, whereas previous methods exhibit quadratic growth. This efficiency stems from the explicit feature mapping and the avoidance of expensive distance calculations like Wasserstein.
Conclusion
The Isolation Graph Kernel provides a robust solution to the scalability-accuracy trade-off in graph similarity. By leveraging data-dependent kernels in a Hilbert space, it avoids the "shrinking" pitfalls of traditional WL and the computational costs of Wasserstein-based methods. Future work may extend these principles to Graph Neural Networks (GNNs) to mitigate over-smoothing issues.
Summary updated