Source-linked AI summary
subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs
Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, Santhoshkumar Saminathan
TL;DR
Existing graph kernels can overlook dependencies among rooted substructures and suffer diagonal dominance. subgraph2vec learns rooted-subgraph embeddings from varying neighbourhood contexts using unsupervised representation learning, and these embeddings improve graph classification and clustering across benchmark and real-world tasks, including gains exceeding 12% and 4% over specified baselines in malware detection.
Problem
Existing graph kernels treat related substructures as separate features, causing diagonal dominance, while prior context assumptions can misrepresent substructure similarities.
Method
subgraph2vec learns rooted-subgraph embeddings from neighbourhood contexts using an unsupervised corpus-and-vocabulary language-model procedure with negative sampling.
Results
Across benchmark and real-world datasets, subgraph2vec significantly outperforms state-of-the-art graph kernels; SVM embeddings exceed WL and Deep WLYV kernels by more than 12% and 4% in malware detection.
Takeaways & Limitations
The embeddings can be paired with CNNs, SVMs and relational clustering algorithms and used to build a deep learning variant of the Weisfeiler-Lehman kernel.
Takeaways & Limitations
Existing graph kernels are limited because they treat dependent substructures independently and can produce diagonally dominant similarity matrices.
Abstract
from arXiv · showhide
In this paper, we present subgraph2vec, a novel approach for learning latent representations of rooted subgraphs from large graphs inspired by recent advancements in Deep Learning and Graph Kernels. These latent representations encode semantic substructure dependencies in a continuous vector space, which is easily exploited by statistical models for tasks such as graph classification, clustering, link prediction and community detection. subgraph2vec leverages on local information obtained from neighbourhoods of nodes to learn their latent representations in an unsupervised fashion. We demonstrate that subgraph vectors learnt by our approach could be used in conjunction with classifiers such as CNNs, SVMs and relational data clustering algorithms to achieve significantly superior accuracies. Also, we show that the subgraph vectors could be used for building a deep learning variant of Weisfeiler-Lehman graph kernel. Our experiments on several benchmark and large-scale real-world datasets reveal that subgraph2vec achieves significant improvements in accuracies over existing graph kernels on both supervised and unsupervised learning tasks. Specifically, on two realworld program analysis tasks, namely, code clone and malware detection, subgraph2vec outperforms state-of-the-art kernels by more than 17% and 4%, respectively.
1. INTRODUCTION
Graph kernels compare graphs through substructure counts, but they treat related substructures as independent and can suffer diagonal dominance. subgraph2vec addresses these limitations by learning rooted-subgraph embeddings from radial contexts and uses them for graph kernels and learning tasks.
- Existing Graph Kernels: Graph kernels measure graph similarity by comparing vectors of atomic-substructure counts in a reproducing kernel Hilbert space.The resulting kernel matrix supports graph classification with SVMs and relational clustering.
- Limitations of Existing Graph Kernels: Treating related substructures as independent expands the feature space and causes diagonal dominance, which can reduce classification and clustering accuracy.Under diagonal dominance, graphs are similar to themselves but not to other graphs in the dataset.
- Limitations of Existing Graph Kernels: Rooted subgraphs at different neighbourhood degrees are strongly related because larger subgraphs can be formed by adding nodes and edges to smaller ones.Figure 1 illustrates this relation for degree-1, degree-2 and degree-3 subgraphs, while also showing a highly dissimilar degree-1 graph.
- Existing Solution: Deep Graph Kernels: Deep Graph Kernels learn substructure embeddings, but their context assumptions can incorrectly mark dissimilar same-degree subgraphs as similar and related different-degree subgraphs as dissimilar.They also assume every subgraph has the same number of contextual subgraphs, violating graph neighbourhood structure.
- Our Approach: subgraph2vec learns rooted-subgraph representations with a modified skipgram model that captures varying-length radial contexts.The framework uses neighbourhoods of rooted subgraphs as its corpus and rooted subgraphs as its vocabulary, then supports a deep learning variant of the Weisfeiler-Lehman kernel.
- Contributions: Experiments show that subgraph2vec significantly outperforms state-of-the-art graph kernels on graph classification and clustering tasks.The learned embeddings can be used with classifiers and relational clustering algorithms.
2. RELATED WORK
Related work spans graph-kernel families and representation-learning methods for graph nodes and substructures. subgraph2vec is positioned as complementary to existing kernels when their substructures exhibit meaningful similarities.
- Representation Learning from Graphs: Graph representation-learning research includes methods for nodes and other graph substructures, including Deep Walk, node2vec and Deep Graph Kernels.The paper compares these approaches in Table 1.
- Graph Kernels: Existing graph kernels can be grouped into kernels for limited-size subgraphs, subtree patterns, walks and paths.subgraph2vec is described as complementary when the underlying substructures have reasonable similarities.
3. PROBLEM STATEMENT
The paper formalizes learning distributed representations for rooted subgraphs extracted from a set of labeled graphs. These embeddings are intended for graph and related prediction, classification, clustering and community-detection applications.
- Problem Definition: A subgraph is defined through an injective mapping from its nodes into a graph that preserves the graph's edge relations.Graphs may include node labels assigned from an alphabet.
- Problem Definition: Given graphs and a maximum degree D, the method extracts rooted neighbourhood subgraphs of degrees 0 ≤ d ≤ D and learns δ-dimensional embeddings for them.The embedding matrix has one row for each vocabulary subgraph.
- Applications: The learned embeddings can support graph classification, clustering, node classification, link prediction and community detection.They can be combined with CNNs, recurrent neural networks, SVMs and relational clustering algorithms, or used to construct graph kernels.
4. BACKGROUND: LANGUAGE MODELS
Language-model methods learn distributed word representations from contextual co-occurrence, and subgraph2vec transfers this idea by treating graph substructures as words generated from a special language.
- Language-model foundations: Traditional language models estimate the likelihood of word sequences from previously observed words in a corpus.Neural language models instead learn distributed vector representations using surrounding context.
- Skipgram: Skipgram maximizes the co-occurrence probability of words appearing within a fixed context window around a target word.The model assumes contextual words and the current word are independent when decomposing the objective.
- Efficient training: Negative sampling avoids exhaustive prediction over a large vocabulary by selecting non-context words at random during training.Words observed in context are therefore mapped closer to one another than randomly selected vocabulary words.
- Embedding intuition: After skipgram training converges, semantically similar words occupy closer positions in the embedding space.This provides the semantic-preservation intuition extended to graph substructures.
- Transfer to graphs: Subgraph2vec treats different subgraphs as words that compose graphs like words compose sentences, enabling word-embedding models to learn subgraph similarity dimensions.The algorithm learns subgraph representations from a graph corpus and subgraph vocabulary.
5. METHOD: LEARNING SUB-GRAPH REPRESENTATIONS
The method section presents subgraph2vec, explains how it enables a deep-learning variant of the Weisfeiler–Lehman kernel, and discusses its use cases.
- This section covers subgraph2vec, its deep-learning variant of the WL kernel, and detailed use cases.
5.1 Overview
Subgraph2vec learns rooted-subgraph representations from graph neighborhoods by using subgraph contexts as a corpus and vocabulary for language-model training.
- Subgraph2vec constructs a corpus from neighborhoods around rooted subgraphs up to a specified degree.It uses all rooted subgraphs around nodes in every graph as the vocabulary.
- The method learns subgraph embeddings by applying a language-model training process to subgraphs and their graph-derived contexts.
5.2 Algorithm: subgraph2vec
The algorithm generates rooted subgraphs using Weisfeiler–Lehman-style extraction, then learns their embeddings with a radial skipgram model and negative sampling.
- Algorithm overview: The algorithm has two components: generating rooted subgraphs around graph nodes and learning embeddings for those subgraphs.
- Algorithm overview: It builds a vocabulary of subgraphs up to degree D, initializes their embeddings, and iteratively trains across the input graphs for e epochs.The embeddings have δ dimensions.
- Rooted-subgraph extraction: Rooted subgraphs are extracted recursively using Weisfeiler–Lehman relabeling, taking a root node, graph, and target degree as inputs.The procedure returns the rooted subgraph around the selected node.
- Rooted-subgraph extraction: For degree zero, extraction returns the root label; for higher degrees, it recursively combines neighboring subgraphs with the root’s lower-degree subgraph.The resulting components are concatenated after sorting the neighboring subgraphs.
- Radial skipgram: The radial skipgram model learns a target subgraph from neighboring subgraphs of degrees d−1, d, and d+1.This defines graph-based radial context rather than the fixed linear context used by vanilla skipgram.
- Embedding optimization: Training moves a target embedding closer to embeddings of context subgraphs while moving it away from a fixed number of sampled non-context subgraphs.Negative sampling is used because the subgraph vocabulary may contain thousands or millions of labels, making full posterior calculation prohibitively expensive.
5.3 Relation to Deep WL kernel
Subgraph2vec embeddings of WL-derived subgraphs can define similarities among WL substructures and thereby produce a deep WL kernel across graphs.
- Subgraph2vec represents WL neighbourhood labels through embeddings of rooted subgraphs in SGvocab.
- The learned embeddings define an M matrix whose entries are inner products between subgraph embeddings.
- Plugging M into the kernel formulation yields a deep WL kernel representing similarities across graphs.
5.4 Use cases
Subgraph2vec embeddings support graph classification and clustering, while also extending to node-level and other graph-learning tasks.
- Graph Classification: Subgraph2vec embeddings can support graph classification through CNNs or a deep WL kernel with kernelized learning algorithms.
- Graph Clustering: Graph clustering uses graph-kernel similarities followed by relational algorithms such as Affinity Propagation or Hierarchical Clustering.
- The method can also learn node representations, enabling node classification, community detection, and link prediction.
6. EVALUATION
The evaluation compares subgraph2vec with graph kernels across benchmark classification, clone detection, and malware detection, measuring accuracy and pre-training efficiency. Subgraph2vec generally improves accuracy while requiring slightly less pre-training time than Deep WLYV.
- Evaluation scope: The evaluation covers benchmark graph classification and large-scale real-world clone and malware detection tasks, using comparisons with WL and Deep WLYV kernels.Benchmark datasets include MUTAG, PTC, PROTEINS, NCI1, and NCI109; real-world tasks use Android app graphs.
- Benchmark classification: SVMs with subgraph2vec embeddings achieve better accuracy on MUTAG, PTC, and PROTEINS, and comparable accuracy on NCI1 and NCI109.The benchmark evaluation uses 90% training data, 10% testing data, and 5-fold cross-validation for hyperparameter tuning.
- Efficiency: Subgraph2vec requires less pre-training time than Deep WLYV on the evaluated datasets.The paper attributes this to radial skipgram involving slightly fewer computations than Deep WLYV’s vanilla skipgram.
- Evaluation scope: Benchmark classification is simpler than real-world classification, so the paper extends evaluation to practical graph clustering and classification tasks.The authors note that trivial features such as graph node counts can achieve comparable benchmark accuracies to state-of-the-art kernels.
- Clone detection: Subgraph2vec outperforms WL and Deep WLYV by more than 21% and 17%, respectively, on clone detection.The difference between subgraph2vec embeddings and Deep WLYV is more pronounced in this unsupervised task.
- Malware detection: Subgraph2vec embeddings outperform WL and Deep WLYV by more than 12% and 4%, respectively, on malware detection.Both pre-trained methods outperform WL because they capture latent similarities between semantically similar but syntactically different malware features.
7. CONCLUSION
subgraph2vec learns unsupervised embeddings of rooted subgraphs in large graphs and supports graph classification and clustering with standard statistical models. Experiments show significantly superior accuracies on benchmark and real-world datasets without compromising overall efficiency.
- subgraph2vec learns embeddings of rooted subgraphs in large graphs through unsupervised representation learning.
- The learned embeddings work with CNNs, SVMs, and relational data clustering algorithms for graph classification and clustering.
- Experiments on benchmark and real-world datasets show significantly superior accuracies over existing graph kernels without compromising overall performance efficiency.