Extending Local Features with Contextual Information in Graph Kernels

Nicolò Navarin, Alessandro Sperduti, Riccardo Tesselli

TL;DR

This paper introduces a method to enhance graph kernels by "contextualizing" local features. Instead of simply counting occurrences of substructures (like subtrees), the proposed Tree Context Kernel (TCK) only matches features if they appear within a similar structural neighborhood, significantly increasing the kernel's expressiveness and classification accuracy on biological and chemical datasets with minimal computational overhead.

What Problem Does This Paper Address?

In machine learning for graphs, "kernels" are functions that measure the similarity between two graphs. Most state-of-the-art graph kernels work by breaking a graph down into small, local substructures—such as paths, walks, or subtrees—and counting how many of these pieces the two graphs have in common.

The challenge is a trade-off between efficiency and expressiveness. If you only look at very small local pieces, you lose the "big picture" of how those pieces are arranged. However, looking at large, complex subgraphs is often computationally impossible (NP-complete). The authors noted that many existing kernels perform similarly because they are all essentially approximating the same local information. They sought a way to capture the context of a feature—where it sits in the graph—without making the algorithm too slow to use.

Methods

The authors build upon the Ordered Decomposition DAGs (ODD) framework. Their key innovation is the Tree Context Kernel (TCK).

  • Contextualization: In a standard kernel, a specific subtree feature $f$ is counted regardless of its surroundings. In TCK, a feature $f$ is associated with a context $c$ (which is itself another structural feature). A match between two graphs only occurs if feature $f$ appears in context $c$ in both graphs.
  • Recursive Definition: The context of a subtree is defined by its parent node's structure. This allows the "context" to be represented using the same language as the "features," making the system elegant and recursive.
  • Empty Contexts: To ensure the kernel remains robust, they include an "empty context" ($\emptyset$) for features that have reached the maximum allowed depth or have no further surrounding structure.
  • Efficient Algorithm: While "tree-visits" can grow exponentially in size, the authors provide an algorithm that operates on DAG-visits (Directed Acyclic Graphs). By using clever hashing and topological sorting, they can compute these contextualized features in a time-frame nearly identical to traditional, non-contextual kernels.

Datasets

The researchers evaluated their approach on five standard real-world benchmarks for graph classification:

  • AIDS, CAS, CPDB, NCI1: Collections of chemical compounds represented as graphs (nodes are atoms, edges are bonds).
  • GDD: A dataset of protein structures where nodes represent amino acids.

These datasets range from small (CPDB: 684 instances) to large (CAS and NCI1: over 4,000 instances).

Key Insights and Ideas

  • Sparsity as a Strength: Adding context makes the feature space "sparser." While this sounds like a disadvantage, it actually makes the kernel more discriminative. It prevents "false positive" matches between subtrees that look the same locally but serve completely different roles in their respective graphs.
  • Context is "Free": One of the most impressive "aha" moments is the realization that if you are already computing subtree features (like in the ODDK kernel), the information needed to define the "context" is already available in the computation pipeline.
  • Hybridization: The authors found that sometimes the contextualized kernel is too specific. They introduced a hybrid version (TCK + ODDK) that combines both contextualized and standard features, often yielding the best results by balancing local detail with broader context.

Key Results

The TCK approach (or its hybrid version) achieved the highest accuracy on 4 out of the 5 tested datasets, outperforming established baselines like the Weisfeiler-Lehman (WL) kernel and the Neighborhood Subgraph Pairwise Distance Kernel (NSPDK).

  • Accuracy Boost: On the GDD (protein) dataset, TCK reached 79.35% accuracy, a significant jump over the original ODDK's 76.99%.
  • Efficiency: Computational benchmarks showed that the time required to compute the TCK Gram matrix is almost indistinguishable from the original ODDK. For the CAS dataset, both hovered around the same execution time across various tree heights ($h$).

Limitations and Future Work

  • Dataset Sensitivity: The method did not outperform the baseline on the AIDS dataset. This suggests that for some specific types of data, the extra "sparsity" provided by context might actually hide relevant similarities.
  • Generalization: The current work focuses specifically on tree-based features. The authors suggest that this "contextualization" logic could be applied to other types of graph kernels (like those based on paths or cycles) or even other discrete data structures.
  • Parameter Tuning: Like many kernel methods, performance is sensitive to the height ($h$) and weight factor ($\lambda$), requiring nested cross-validation to find the optimal settings.

Summary updated

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 [7], 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.
BibTeX
@inproceedings{navarin2015extending,
  author = {Nicolò Navarin and Alessandro Sperduti and Riccardo Tesselli},
  title = {{Extending Local Features with Contextual Information in Graph Kernels}},
  booktitle = {ICONIP},
  year = {2015},
  url = {https://openreview.net/forum?id=m8al4keYsgE},
}

Loading related content...

Figure