Abstract: Graph kernels are usually defined in terms of simpler kernels over local substructures of the original graphs. Different kernels consider different types of substructures. However, in some cases they have similar predictive performances, probably because the substructures can be interpreted as approximations of the subgraphs they induce. In this paper, we propose to associate to each feature a piece of information about the context in which the feature appears in the graph. A substructure appearing in two different graphs will match only if it appears with the same context in both graphs. We propose a kernel based on this idea that considers trees as substructures, and where the contexts are features too. The kernel is inspired from the framework in [6], even if it is not part of it. We give an efficient algorithm for computing the kernel and show promising results on real-world graph classification datasets.
Introduction
In machine learning for graphs, kernels serve as critical functions to measure similarity between complex structures. Most state-of-the-art graph kernels operate by decomposing a graph into local substructures—such as paths, walks, or subtrees—and counting shared occurrences. However, researchers face a persistent trade-off between efficiency and expressiveness. While small local features are efficient to compute, they often fail to capture the broader structural arrangement, leading many kernels to perform similarly as they approximate the same local information. This paper introduces a method to enhance these kernels by "contextualizing" local features, capturing where a feature sits in the graph without incurring the prohibitive costs of large subgraph matching.
Methodology: The Tree Context Kernel (TCK)
The authors build upon the Ordered Decomposition DAGs (ODD) framework to introduce the Tree Context Kernel (TCK). The core innovation lies in how features are matched:
- Contextualization: Unlike standard kernels that count every instance of a subtree feature $f$, TCK associates $f$ with a context $c$ (itself a structural feature). A match only occurs if feature $f$ appears within the same context $c$ in both graphs.
- Recursive Definition: The context of a subtree is defined by the structure of its parent node. This allows context to be represented using the same language as the features themselves, creating an elegant, recursive system.
- Efficiency via DAGs: To manage the potentially exponential growth of "tree-visits," the authors developed an algorithm operating on Directed Acyclic Graphs (DAGs). By utilizing topological sorting and hashing, the contextualized features are computed in a timeframe nearly identical to traditional, non-contextual kernels.
Experimental Evaluation
The approach was evaluated on five standard real-world benchmarks for graph classification: chemical compound datasets (AIDS, CAS, CPDB, NCI1) and a protein structure dataset (GDD). These datasets vary in size from 684 to over 4,000 instances.
Key Results and Performance
The TCK approach, particularly its hybrid version (TCK + ODDK), achieved the highest accuracy on four out of the five tested datasets. By combining contextualized and standard features, the hybrid model balances local detail with broader structural context.
On the GDD protein dataset, TCK reached 79.35% accuracy, a notable improvement over the original ODDK's 76.99%. The results suggest that adding context makes the feature space sparser and more discriminative, preventing "false positive" matches between subtrees that are locally identical but structurally distinct in their respective graphs.
Computational Efficiency
A significant finding is that the added expressiveness of context comes with almost no computational penalty. As shown in the runtime analysis for the CAS dataset, the time required to compute the TCK Gram matrix is nearly indistinguishable from the original ODDK across various tree heights ($h$).
Conclusion
The Tree Context Kernel demonstrates that contextual information can significantly enhance the discriminative power of graph kernels with minimal overhead. While the method showed some sensitivity on the AIDS dataset—where high sparsity may have obscured relevant similarities—it generally outperformed established baselines like the Weisfeiler-Lehman (WL) kernel. Future work may extend this contextualization logic to other substructures, such as paths or cycles, to further generalize the framework.
Summary updated