The Structurally Smoothed Graphlet Kernel

Pinar Yanardag, S. V. N. VishwanathanarXiv 2014 · OpenReview

TL;DR

This paper introduces a novel "Structurally Smoothed Graphlet Kernel" (SKN) that addresses the sparsity and diagonal dominance issues inherent in traditional graphlet kernels. By extending natural language processing smoothing techniques (Kneser-Ney) to graph structures, SKN improves graph comparison accuracy, especially for larger graphs.

What Problem Does This Paper Address?

Representing graphs as vectors of normalized frequencies of small subgraphs (graphlets) is a common approach for tasks like similarity computation. However, this method faces a dilemma: using small graphlets (low k) leads to insufficient discriminatory power, while using large graphlets (high k) results in sparse vectors where most graphlets don't appear in any given graph. This "diagonal dominance" makes graphs appear similar only to themselves, hindering effective comparison. The paper aims to overcome this by developing a smoothing technique that leverages the inherent structure of graphlets.

Methods

The core contribution is a Structurally Smoothed Graphlet Kernel (SKN). This method extends the Kneser-Ney smoothing technique, originally developed for language models, to the domain of graphlets. The key innovation lies in defining a base distribution that respects the hierarchical relationships between graphlets of different sizes. This is achieved by constructing a Directed Acyclic Graph (DAG) where nodes represent graphlets, and edges connect graphlets that differ by a single node deletion. The edge weights in this DAG are derived from the frequency of smaller graphlets appearing within larger ones.

SKN then uses this structural information to redistribute probability mass from observed graphlets to unobserved ones, mitigating sparsity. It also incorporates a Pitman-Yor process for a Bayesian interpretation and automatic tuning of the smoothing parameters.

Datasets

The paper evaluates its method on several real-world benchmark datasets:

  • MUTAG: Mutagenic aromatic and heteroaromatic nitro compounds.
  • PTC: Predictive Toxicology Challenge dataset (carcinogenicity).
  • ENZYMES: Protein tertiary structures.
  • DD: Protein structures represented as graphs.
  • NCI1 & NCI109: Chemical compounds screened for tumor cell growth inhibition.

These datasets are described as sparse graphs, and for experiments, random sampling (10,000 subgraphs) was used to estimate graphlet counts, except for some comparisons where exhaustive sampling was performed.

Key Insights and Ideas

  • The Graphlet Dilemma: There's a fundamental trade-off between graphlet size (k) and the effectiveness of frequency-based graph representations. Small k lacks discrimination, while large k leads to sparsity and diagonal dominance.
  • Structure is Key: The relationships between graphlets of different sizes (e.g., a size-4 graphlet containing a specific size-3 graphlet) are crucial and can be leveraged for smoothing.
  • NLP Smoothing for Graphs: Kneser-Ney smoothing, successful in language modeling for handling unseen words, provides a powerful framework for addressing graphlet sparsity.
  • DAG as a Structural Blueprint: A DAG representing graphlet hierarchy naturally captures relationships and provides a principled way to define a base distribution for smoothing.
  • Power-Law Behavior: Graphlet frequencies exhibit power-law behavior, meaning a few graphlets are very common while most are rare. Smoothing techniques must respect this.

Key Results

  • The proposed Structurally Smoothed Graphlet Kernel (SKN) consistently outperforms the standard graphlet kernel (MLE estimate) and hash kernels across all benchmark datasets.
  • SKN achieved the highest accuracy on the PTC, DD, and ENZYMES datasets.
  • On MUTAG, NCI1, and NCI109, SKN achieved comparable or better accuracy than shortest path and random walk kernels.
  • The smoothed kernels are shown to be competitive and applicable to very large graphs, where raw frequency counts struggle due to sparsity.
  • Experiments suggest that an intermediate discount parameter value (not too small, not too large) yields the best performance, indicating the importance of balancing observed data with smoothed estimates.

Limitations and Future Work

  • Hyperparameter Tuning: The Pitman-Yor smoothed kernel's performance is sensitive to hyperparameters, and the paper notes that they did not extensively tune these in their experiments, suggesting room for improvement.
  • Generalization to Other Kernels: The authors are interested in extending their structural smoothing framework to other graph kernels (e.g., random walk kernels) and other structured data types like string and tree kernels.
  • Node-Labeled Graphs: The framework is also applicable to node-labeled graphs, which also suffer from sparsity issues, and this is a direction for future work.

Summary updated

Abstract

A commonly used paradigm for representing graphs is to use a vector that contains normalized frequencies of occurrence of certain motifs or sub-graphs. This vector representation can be used in a variety of applications, such as, for computing similarity between graphs. The graphlet kernel of Shervashidze et al. [32] uses induced sub-graphs of k nodes (christened as graphlets by Przulj [28]) as motifs in the vector representation, and computes the kernel via a dot product between these vectors. One can easily show that this is a valid kernel between graphs. However, such a vector representation suffers from a few drawbacks. As k becomes larger we encounter the sparsity problem; most higher order graphlets will not occur in a given graph. This leads to diagonal dominance, that is, a given graph is similar to itself but not to any other graph in the dataset. On the other hand, since lower order graphlets tend to be more numerous, using lower values of k does not provide enough discrimination ability. We propose a smoothing technique to tackle the above problems. Our method is based on a novel extension of Kneser-Ney and Pitman-Yor smoothing techniques from natural language processing to graphs. We use the relationships between lower order and higher order graphlets in order to derive our method. Consequently, our smoothing algorithm not only respects the dependency between sub-graphs but also tackles the diagonal dominance problem by distributing the probability mass across graphlets. In our experiments, the smoothed graphlet kernel outperforms graph kernels based on raw frequency counts.
BibTeX
@misc{yanardag2014structurally,
  author = {Pinar Yanardag and S. V. N. Vishwanathan},
  title = {{The Structurally Smoothed Graphlet Kernel}},
  year = {2014},
  eprint = {1403.0598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1403.0598},
}

Loading related content...

Figure