Abstract
We propose a family of attributed graph kernels based on mutual information measures, specifically the Jensen-Tsallis (JT) $q$-differences (for $q \in [1,2]$) between probability distributions over graphs. Our approach first assigns a probability to each vertex through a continuous-time quantum walk (CTQW). We then adopt a tree-index approach to strengthen original vertex labels and show how the CTQW induces a probability distribution over these labels. We demonstrate that the JT kernel (for $q=1$) overcomes the limitations of R-convolution kernels regarding non-isomorphic substructures. Furthermore, we prove that the proposed JT kernels generalize the Jensen-Shannon graph kernel (for $q=1$) and the classical subtree kernel (for $q=2$). Experimental evaluations confirm the effectiveness and efficiency of the JT kernels.
Introduction
In graph machine learning, kernels are fundamental tools for measuring similarity between complex structures. A common paradigm is the R-convolution kernel, which decomposes graphs into substructures—such as subtrees or paths—and counts identical matches. However, this "all-or-nothing" approach often fails to capture subtle structural similarities, discarding information when substructures are similar but not perfectly isomorphic.
To address these challenges, we introduce the Jensen-Tsallis (JT) Graph Kernel. This framework bridges the gap between local substructure matching and global graph entropy measures by comparing probability distributions of labels rather than simple counts.
Methodology
The JT Graph Kernel framework integrates three core components:
1. Continuous-Time Quantum Walk (CTQW)
Unlike classical random walks, a quantum walk is reversible and does not converge to a simple stationary distribution. This property allows it to capture richer topological information. We use CTQW to calculate a "time-averaged probability" for each vertex, which serves as a measure of node importance or centrality based on the graph's quantum dynamics.
2. Tree-Index (TI) Label Strengthening
To incorporate local neighborhood context, we employ an iterative label-strengthening process. Similar to the Weisfeiler-Lehman algorithm, this method updates a node's label based on the labels of its neighbors, effectively encoding the subtree structure rooted at that node.
3. Jensen-Tsallis q-Differences
The final kernel is computed by creating a probability distribution over these strengthened labels, weighted by the CTQW probabilities. We then apply $q$-differences—a generalization of information-theoretic measures—to compare these distributions.
- At $q=1$, the kernel generalizes the Jensen-Shannon divergence.
- At $q=2$, it generalizes the classical subtree kernel, incorporating an exponential diffusion weighting.
Experimental Evaluation
We evaluated the JT kernels on standard bioinformatics and chemical benchmarks, including MUTAG, NCI1, NCI109, ENZYMES, PPIs, and PTC(MR).
The results indicate that JT kernels (specifically JT1 and JT2) consistently outperform state-of-the-art methods like the Weisfeiler-Lehman subtree kernel (WLSK) and the Shortest Path kernel (SPGK). For instance, on the NCI1 dataset, JT1 achieved an accuracy of 86.35%, surpassing WLSK's 84.77%.
Conclusion
The Jensen-Tsallis $q$-difference framework provides a unifying perspective on graph kernels. By moving beyond exact isomorphism and leveraging quantum walks, the JT kernel captures both local topology and global distributions effectively. While the $O(n^3)$ complexity of the quantum walk simulation presents a challenge for massive graphs, the kernel's accuracy and robustness make it a powerful tool for attributed graph analysis. Future work will explore broader ranges of $q$ and applications in diverse domains such as financial time-series.
Summary updated