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