A structural cluster kernel for learning on graphs

Madeleine Seeland, Andreas Karwath, Stefan KramerKDD 2012 · DOI

TL;DR

This paper introduces a novel "structural cluster kernel" (SCK) that enhances graph-based machine learning by incorporating structural neighborhood information. By clustering graphs based on their structural similarities and then using these cluster assignments to refine pairwise graph similarities, SCK significantly improves prediction performance, especially for structurally diverse datasets.

What Problem Does This Paper Address?

Machine learning on graphs, particularly using graph kernels, has become a powerful tool for analyzing complex relational data like molecular structures. Traditional graph kernels primarily rely on comparing substructures or graph features. However, they often overlook the broader structural context or "neighborhood" in which a graph exists. This paper addresses the limitation of existing graph kernels by proposing a method that leverages this structural neighborhood information. The core idea is that the similarity between two graphs can be enhanced not only by their intrinsic structural similarities but also by how they relate to other graphs within their structural clusters. This is particularly relevant for datasets where individual graphs might be sparse or structurally diverse, making it difficult for traditional kernels to capture meaningful similarities.

Methods

The paper introduces the Structural Cluster Kernel (SCK), which builds upon existing graph kernels by incorporating structural clustering. The SCK operates in two main stages:

  1. Structural Graph Clustering: The authors utilize a method called Parallel Structural Clustering of Graphs (PSCG) [21, 22]. PSCG groups graphs that share common substructures. A key feature of PSCG is its ability to handle overlapping and non-exhaustive clustering, meaning a graph can belong to multiple clusters or none at all. This clustering is based on the size of common substructures relative to the graphs themselves.
  2. Kernel Construction:
    • Base Kernels: The SCK is designed to extend two state-of-the-art graph kernels: the Weighted Decomposition Kernel (WDK) [18] and the Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) [10]. These kernels capture structural similarities between graphs.
  3. Cluster Kernel ($K_{cl}$): A kernel is constructed based on the PSCG cluster assignments. This cluster kernel measures the similarity between two graphs based on the average pairwise similarities of their constituent clusters. The idea is that graphs within the same cluster should have higher similarity.
  4. Structural Cluster Kernel (SCK): The final SCK is formed by combining the base kernel ($K_b$) with the cluster kernel ($K_{cl}$) through element-wise multiplication: $K_{SC}(x_i, x_j) = K_b(x_i, x_j) \times K_{cl}(x_i, x_j)$. This means the similarity between two graphs is amplified if they are both structurally similar (via $K_b$) and belong to similar structural neighborhoods (via $K_{cl}$).

The paper also explores a semi-supervised setting where unlabeled data is incorporated into the PSCG clustering process to further enhance the structural neighborhood information used by the SCK.

Datasets

The authors evaluated their SCK approach on several real-world datasets of molecular graphs, primarily from the cheminformatics domain. These datasets were used for both regression (predicting properties like QSAR) and classification tasks. The datasets include:

  • Regression Datasets: 4QSAR COX2, 4QSAR DHFR, CPD MOUSE, CPD RAT, ISS MOUSE, ISS RAT, Suth COX2, Suth DHFR, Suth ER TOX, FDAMDD, Biodeg, Tox09, ER_LIT.
  • Classification Datasets: CYP INH, CYP SUB 2C9, Fontaine, NCI AIDS, CPDB MUT.

The paper notes that the FDAMDD dataset is particularly large and structurally heterogeneous, while others like CPD and ISS datasets consist of many small, structurally diverse molecules.

Key Insights and Ideas

  • Neighborhood Matters: The core insight is that a graph's "neighborhood" (i.e., its structural context within a larger collection of graphs) can be as informative as its intrinsic structure for determining similarity.
  • Clustering as a Similarity Enhancer: Structural clustering (using PSCG) effectively identifies groups of structurally similar graphs. This grouping can then be leveraged to refine pairwise similarities computed by traditional graph kernels.
  • Synergy of Kernels: The SCK demonstrates a powerful synergy by combining a graph kernel (capturing direct structural similarity) with a cluster kernel (capturing contextual similarity).
  • Handling Structural Sparsity: The SCK shows particular promise for datasets with structurally sparse or diverse molecules, where traditional kernels might struggle to find robust similarities. The structural neighborhood provides a more stable basis for comparison in such cases.
  • Semi-Supervised Learning Boost: Incorporating unlabeled data into the clustering process significantly improves performance, especially in the semi-supervised setting, highlighting the value of large unlabeled datasets for learning robust structural representations.

Key Results

The experimental results, summarized in Tables 2-7 and Figure 2, demonstrate the effectiveness of the SCK:

  • Improved Performance: SCK consistently outperformed or matched the performance of the base kernels (WDK and NSPDK) and the LoMoGraph method across many datasets.
  • NSPDK Advantage: The NSPDK proved to be a more powerful base kernel than WDK, and SCK built upon NSPDK generally yielded better results.
  • Dataset Dependency: The performance gains were most pronounced on datasets that were structurally more sparse and diverse (e.g., FDAMDD, CPD, ISS, Biodeg datasets). On datasets with very similar molecules (e.g., COX2 datasets), the SCK showed less improvement over the base kernel.
  • Semi-Supervised Gains: In the semi-supervised setting, SCK NSPDK achieved significant performance improvements on most datasets compared to its supervised counterpart and the base NSPDK, particularly for classification tasks.
  • Statistical Significance: The paper reports statistically significant improvements using Wilcoxon signed-rank tests and corrected resampled t-tests, lending strong support to the SCK's effectiveness.

Limitations and Future Work

  • Parameter Sensitivity: The performance of SCK can be influenced by parameters of both the base kernel and the PSCG clustering algorithm (e.g., the similarity coefficient $\theta$). The paper mentions optimizing these parameters through cross-validation.
  • Computational Cost: While not explicitly detailed as a limitation, combining clustering with kernel methods can increase computational complexity. The paper does mention using PSCG for "online structural graph clustering," suggesting an effort towards efficiency.
  • Generalizability: The authors suggest that the SCK approach is general and can be employed with various kernels and clustering algorithms, implying future work could explore different combinations.
  • Broader Applications: The paper focuses on molecular graphs, but the authors believe the approach is not restricted to graph mining alone and could be applied to other domains with graph-structured data.

Summary updated

BibTeX
@inproceedings{seeland2012structural,
  author = {Madeleine Seeland and Andreas Karwath and Stefan Kramer},
  title = {{A structural cluster kernel for learning on graphs}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2012},
  doi = {10.1145/2339530.2339614},
}
Figure