A Structural Smoothing Framework For Robust Graph Comparison

Pinar Yanardag, S. V. N. VishwanathanNeurIPS 2015 · OpenReview

Comparing complex relational structures, such as molecular compounds or social networks, is a foundational challenge in machine learning. A standard approach to this problem is the R-convolution framework, which decomposes graphs into smaller, manageable sub-structures—like paths, trees, or small subgraphs called "graphlets"—and counts their occurrences to measure similarity.

While effective, this approach struggles with complex, real-world data. This paper introduces a novel smoothing framework for graph kernels that borrows techniques from Natural Language Processing (NLP) to better compare these complex structures. By redistributing probability mass across a hierarchy of sub-structures, the authors solve the notorious "diagonal dominance" problem and significantly improve both classification accuracy and robustness to noise.

The Challenge of Graph Comparison

Traditional graph comparison methods face three major hurdles:

  1. Diagonal Dominance: As the sub-structures used for comparison become more complex, the probability of two different graphs sharing the exact same structure drops to nearly zero. Consequently, the similarity matrix begins to look like an identity matrix—every graph appears unique, and nothing is deemed "similar" to anything else.
  2. The Power-Law Problem: In real-world graphs, a few simple structures appear ubiquitously, while the vast majority of complex structures are extremely rare. Standard counting methods (like Maximum Likelihood Estimation) often underestimate the importance of these rare, yet highly discriminative, features.
  3. Lack of Partial Similarity: Traditional kernels demand exact matches. If two sub-structures differ by just a single edge, the kernel treats them as completely distinct. This rigidness makes the model fragile when faced with noisy data.
A dictionary of graphlets (sub-structures) used to decompose and compare larger graphs.

Methodology: Structural Smoothing

To overcome these limitations, the authors propose Structural Smoothing. The core inspiration comes from NLP: just as language models use smoothing to handle unseen words (n-grams) by falling back to shorter, known phrases, graph models can handle rare structural patterns by falling back to simpler sub-structures.

The DAG Hierarchy

The framework uses a Directed Acyclic Graph (DAG) to map the relationships between sub-structures. They organize these sub-structures into hierarchical levels. For instance, a "parent" node in the DAG might be a simple 3-node graphlet, while its "children" are larger 4-node graphlets formed by adding a single node to that parent.

A Directed Acyclic Graph (DAG) illustrating the hierarchical relationships between different graphlets.

Redistributing Probability

Instead of relying solely on raw counts, the model uses an interpolated smoothing technique. If a specific, complex sub-structure is absent from a graph, the model "falls back" to its parents in the DAG. It effectively reasons: "I didn't find this exact 5-node shape, but I found the 4-node shapes that comprise it, so I will count that as a partial match."

The amount of "similarity" a child structure receives depends on how "authoritative" its parents are. This allows the model to respect the actual topology of the feature space, capturing partial similarities that traditional kernels miss.

Bayesian Extension

The authors also introduce a variant based on the Pitman-Yor process. This statistical model is known for producing "power-law" distributions (the "rich-get-richer" effect), which perfectly aligns with how sub-structures naturally occur in real-world graphs.

The framework is highly adaptable and was successfully applied to three popular existing kernels: the Graphlet kernel, the Weisfeiler-Lehman (WL) kernel, and the Shortest-Path (SP) kernel.

Experimental Validation and Results

The authors evaluated their smoothed kernels against standard benchmark datasets from bioinformatics and chemistry, including MUTAG (mutagenic compounds), PTC (carcinogenicity), ENZYMES, PROTEINS, and the large-scale NCI1/NCI109 datasets (anti-cancer activity screens).

Key findings include:

  • Accuracy Boost: Smoothed kernels consistently outperformed their unsmoothed counterparts. For example, on the MUTAG dataset, applying structural smoothing to the Shortest-Path kernel increased accuracy from 85.22% to 87.94%.
  • Statistical Significance: Most performance gains were statistically significant ($p \leq 0.05$), indicating robust improvements rather than random variance.
  • Noise Tolerance: The fallback mechanism makes the model highly resilient. In experiments where edges or labels were randomly altered to simulate noise, the smoothed kernels maintained high performance, whereas the accuracy of base kernels dropped sharply.
  • Efficiency: Despite adding a computational step to build and traverse the DAG, the authors demonstrated that the smoothing process remains competitive in terms of runtime, making it viable for practical applications.

Limitations and Future Directions

While highly effective, the framework does have limitations. For kernels like Weisfeiler-Lehman, the "vocabulary" of possible sub-structures can grow exponentially with the number of iterations, making the resulting DAG massive and memory-intensive.

Future work may explore domain-specific weighting schemes for the DAG edges, rather than uniform weights, to further refine similarity measures. Additionally, adapting this discrete-label framework to handle graphs with continuous node attributes (such as physical 3D coordinates) remains an exciting open challenge.

Summary updated

Abstract

In this paper, we propose a general smoothing framework for graph kernels by taking \textit{structural similarity} into account, and apply it to derive smoothed variants of popular graph kernels. Our framework is inspired by state-of-the-art smoothing techniques used in natural language processing (NLP). However, unlike NLP applications which primarily deal with strings, we show how one can apply smoothing to a richer class of inter-dependent sub-structures that naturally arise in graphs. Moreover, we discuss extensions of the Pitman-Yor process that can be adapted to smooth structured objects thereby leading to novel graph kernels. Our kernels are able to tackle the diagonal dominance problem, while respecting the structural similarity between sub-structures, especially under the presence of edge or label noise. Experimental evaluation shows that not only our kernels outperform the unsmoothed variants, but also achieve statistically significant improvements in classification accuracy over several other graph kernels that have been recently proposed in literature. Our kernels are competitive in terms of runtime, and offer a viable option for practitioners.
BibTeX
@inproceedings{yanardag2015structural,
  author = {Pinar Yanardag and S. V. N. Vishwanathan},
  title = {{A Structural Smoothing Framework For Robust Graph Comparison}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=SJZSDObOZS},
}
Figure