Isolation Graph Kernel

Bi-Cun Xu, Kai Ming Ting, Yuan Jiang

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:

  1. 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.
  2. 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.
  3. 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.

The "Shrinking" Problem: Standard WL (a) causes convergence, while IK-WL (b) in Hilbert space preserves uniqueness.

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.

Runtime scalability: IGK exhibits linear growth compared to the quadratic scaling of previous state-of-the-art methods.

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

Abstract

A recent Wasserstein Weisfeiler-Lehman (WWL) Graph Kernel has a distinctive feature: Representing the distribution of Weisfeiler-Lehman (WL)-embedded node vectors of a graph in a histogram that enables a dissimilarity measurement of two graphs using Wasserstein distance. It has been shown to produce better classification accuracy than other graph kernels which do not employ such distribution and Wasserstein distance. This paper introduces an alternative called Isolation Graph Kernel (IGK) that measures the similarity between two attributed graphs. IGK is unique in two aspects among existing graph kernels. First, it is the first graph kernel which employs a distributional kernel in the framework of kernel mean embedding. This avoids the need to use the computationally expensive Wasserstein distance. Second, it is the first graph kernel that incorporates the distribution of attributed nodes (ignoring the edges) in a dataset of graphs. We reveal that this distributional information, extracted in the form of a feature map of Isolation Kernel, is crucial in building an efficient and effective graph kernel. We show that IGK is better than WWL in terms of classification accuracy, and it runs orders of magnitude faster in large datasets when used in the context of SVM classification.
BibTeX
@inproceedings{xu2021isolation,
  author = {Bi-Cun Xu and Kai Ming Ting and Yuan Jiang},
  title = {{Isolation Graph Kernel}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i12.17255},
}
Figure