Attributed Graph Kernels Using the Jensen-Tsallis q-Differences

Lu Bai, Luca Rossi, Horst Bunke, Edwin R. HancockECML/PKDD 2014 · OpenReview

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.

Examples of distinct graph structures G1, G2, and G3.

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.

The Tree-Index (TI) label strengthening process applied to a graph.

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

Abstract

We propose a family of attributed graph kernels based on mutual information measures, i.e., the Jensen-Tsallis (JT) q-differences (for q ∈ [1,2]) between probability distributions over the graphs. To this end, we first assign a probability to each vertex of the graph through a continuous-time quantum walk (CTQW). We then adopt the tree-index approach [1] to strengthen the original vertex labels, and we show how the CTQW can induce a probability distribution over these strengthened labels. We show that our JT kernel (for q = 1) overcomes the shortcoming of discarding non-isomorphic substructures arising in the R-convolution kernels. Moreover, we prove that the proposed JT kernels generalize the Jensen-Shannon graph kernel [2] (for q = 1) and the classical subtree kernel [3] (for q = 2), respectively. Experimental evaluations demonstrate the effectiveness and efficiency of the JT kernels.
BibTeX
@inproceedings{bai2014attributed,
  author = {Lu Bai and Luca Rossi and Horst Bunke and Edwin R. Hancock},
  title = {{Attributed Graph Kernels Using the Jensen-Tsallis q-Differences}},
  booktitle = {ECML/PKDD},
  year = {2014},
  url = {https://openreview.net/forum?id=kd6PpNXIbIH},
}
Figure