Abstract
In this paper we present a novel graph kernel framework inspired the by the Weisfeiler-Lehman (WL) isomorphism tests. Any WL test comprises a relabelling phase of the nodes based on test-specific information extracted from the graph, for example the set of neighbours of a node. We defined a novel relabelling and derived two kernels of the framework from it. The novel kernels are very fast to compute and achieve state-of-the-art results on five real-world datasets.
Introduction
Graphs are a primary data structure for representing complex relationships in fields like bioinformatics and social network analysis. To utilize standard machine learning algorithms such as Support Vector Machines (SVMs), researchers use graph kernels to measure similarity. The challenge lies in the trade-off between expressivity—the ability to distinguish non-isomorphic graphs—and computational efficiency. This paper addresses this by extending the Weisfeiler-Lehman (WL) isomorphism test, enriching node relabelling with broader topological context while maintaining linear scalability.
Methodology: The Extended WL Framework
The core innovation is a framework that generalizes the 1-dimensional WL test. While standard WL tests iteratively relabel nodes based on immediate neighbor sets, this approach extracts a Directed Acyclic Graph (DAG) rooted at each node. This DAG captures all shortest paths from the root to nodes within a distance $r$, providing significantly more structural context than simple neighborhood sets.
Two specific kernels are derived from this framework:
- $WL_{NS-DDK}$: A "hard match" kernel that relabels nodes based on their rooted DAGs and counts exact label matches between graphs.
- $WL_{DDK}$: A flexible kernel that transforms the rooted DAG into a tree and applies a Subtree Kernel for comparison.
By utilizing efficient canonical representations for these DAGs, the framework maintains a time complexity of $O(|V| \log |V|)$ per graph for sparse graphs, ensuring it remains practical for large-scale datasets.
Experimental Results
The kernels were evaluated on five real-world binary classification datasets, including chemical compounds (CAS, CPDB, AIDS, NCI1) and proteins (GDD). The results demonstrate that the proposed kernels consistently outperform established baselines such as the Fast Subtree (FS) kernel and the Neighborhood Subgraph Pairwise Distance Kernel (NSPDK).
As shown in the performance table, $WL_{DDK}$ achieved the best average ranking of 1.8, while $WL_{NS-DDK}$ followed with a rank of 2.0. On the NCI1 dataset, $WL_{DDK}$ reached an accuracy of 84.90%, a significant improvement over the 81.05% achieved by the standard FS kernel. Efficiency benchmarks on NCI1 confirmed that Gram matrix computation scales linearly with kernel parameters, taking only a few hundred seconds for the entire dataset.
Discussion and Conclusion
This research demonstrates that treating the WL test as a feature engineering mechanism allows structural information to diffuse effectively through iterative relabelling. By restricting comparisons to rooted DAGs based on shortest paths, the authors capture complex patterns while maintaining tractability. Future work may explore handling continuous node attributes and investigating the framework's performance on exceptionally dense graphs where DAG size could impact efficiency.
Summary updated