Source-linked AI summary
graph2vec: Learning Distributed Representations of Graphs
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, Shantanu Jaiswal
TL;DR
Graph analytics tasks require fixed-length graph vectors, while existing substructure methods are task-specific and graph kernels rely on handcrafted features. graph2vec learns unsupervised, data-driven embeddings for arbitrary-sized graphs and outperforms substructure approaches while matching or exceeding graph-kernel performance across evaluated datasets.
Problem
Graph classification, clustering, and regression require fixed-length graph vectors, but substructure representations are task-specific and graph kernels use handcrafted features.
Method
graph2vec learns unsupervised distributed representations of arbitrary-sized graphs from rooted subgraphs using a doc2vec skipgram process.
Results
Across benchmark and real-world datasets, graph2vec significantly outperforms substructure embedding approaches and is comparable to or better than graph kernels.
Takeaways & Limitations
Data-driven graph embeddings provide accurate representations for graph analytics tasks with reasonably good efficiency and broad downstream applicability.
Takeaways & Limitations
For unlabeled graphs, graph2vec requires node labels and assigns each node its degree as a substitute.
Abstract
from arXiv · showhide
Recent works on representation learning for graph structured data predominantly focus on learning distributed representations of graph substructures such as nodes and subgraphs. However, many graph analytics tasks such as graph classification and clustering require representing entire graphs as fixed length feature vectors. While the aforementioned approaches are naturally unequipped to learn such representations, graph kernels remain as the most effective way of obtaining them. However, these graph kernels use handcrafted features (e.g., shortest paths, graphlets, etc.) and hence are hampered by problems such as poor generalization. To address this limitation, in this work, we propose a neural embedding framework named graph2vec to learn data-driven distributed representations of arbitrary sized graphs. graph2vec's embeddings are learnt in an unsupervised manner and are task agnostic. Hence, they could be used for any downstream task such as graph classification, clustering and even seeding supervised representation learning approaches. Our experiments on several benchmark and large real-world datasets show that graph2vec achieves significant improvements in classification and clustering accuracies over substructure representation learning approaches and are competitive with state-of-the-art graph kernels.
1. INTRODUCTION
Graph2vec addresses the need for fixed-length representations of entire graphs with an unsupervised, data-driven neural embedding framework. It uses rooted subgraphs and performs competitively across graph analytics tasks.
- Graph classification, clustering, and regression require fixed-length feature vectors for entire graphs.
- Existing substructure embeddings represent nodes, paths, or subgraphs but cannot represent entire graphs for graph classification.
- Supervised whole-graph embeddings require large labeled datasets and produce task-specific representations that cannot transfer across problems.
- Graph2vec views each graph as a document and rooted subgraphs around its nodes as words, extending document embedding models to learn graph representations.
- Graph2vec uses data-driven, non-linear rooted substructures and improves classification and clustering over substructure embedding methods while competing with graph kernels.
- Graph2vec learns arbitrary-sized graph embeddings without labels, making them generic across analytics tasks and usable for seeding supervised representation learning.
2. PROBLEM STATEMENT
The paper formalizes graph embedding as learning fixed-dimensional vectors for a collection of labeled or unlabeled graphs. Its procedure requires node labels, using node degree for unlabeled graphs.
- Given a graph set G and embedding size δ, the goal is to learn a δ-dimensional representation for every graph.
- A graph is represented as G = (N, E, λ), with nodes N, edges E, and an optional node-labeling function λ.
- For unlabeled graphs, the procedure assigns node labels according to node degree.
- Edges may also carry labels through an edge-labeling function η : E → e.
- The paper focuses on rooted subgraphs, defined as neighborhoods containing nodes and edges reachable within d hops from a root node.
3. BACKGROUND: SKIPGRAM WORD & DOCUMENT EMBEDDING MODELS
The background introduces skipgram and document embedding models as the neural foundation for graph2vec. These models learn representations from contextual relationships using efficient training procedures.
- Skipgram: Skipgram learns word vectors by maximizing the likelihood of context words surrounding each target word.
- Skipgram: The model treats context words as conditionally independent given the target and represents words with input and output vectors.
- Negative Sampling: Negative sampling reduces training cost by updating a small random subset of words instead of the full vocabulary.
- Skipgram: After training, semantically similar words occupy nearby positions in the embedding space.
- Document Embeddings: Doc2vec extends word2vec to represent arbitrary-length word sequences, including whole documents, using the PV-DBOW model.
- Graph2vec Connection: Graph2vec adapts document embedding by treating graphs as documents and rooted subgraphs as vocabulary elements.
4. METHOD: LEARNING GRAPH REPRESENTATIONS
graph2vec treats each graph as a document composed of rooted subgraphs, then extends doc2vec-style skipgram learning to produce fixed-length graph embeddings. It extracts rooted subgraphs, assigns them vocabulary labels, and trains graph representations so graphs with similar substructure contexts are closer in embedding space.
- 4.1 Intuition: Rooted subgraphs provide higher-order neighborhood structure and are expected to preserve structural equivalence, making them suitable atomic entities for graph embeddings.The paper contrasts them with simpler entities such as nodes, walks, and paths.
- 4.1 Intuition: graph2vec views an entire graph as a document and rooted subgraphs around its nodes as the words composing that document.The approach extends document embedding models to graph representation learning.
- 4.2 Overview: Given a graph corpus, graph2vec builds a vocabulary of rooted subgraphs up to a chosen degree and learns graph representations using doc2vec’s skipgram process.The required input is a dataset of graphs; rooted subgraphs are extracted around every node.
- 4.3 graph2vec: Algorithm: The algorithm has two components: extracting rooted subgraphs around every node and learning embeddings for the graphs.Embeddings are initialized and iteratively refined over multiple epochs.
- 4.3.1 Extracting Rooted Subgraphs: WL relabeling recursively constructs rooted subgraphs by combining the root representation with sorted representations of neighboring degree d −1 subgraphs.For d = 0, the procedure returns the root node’s label; for d > 0, it recursively processes breadth-first neighbors.
- 4.3.2 Skipgram with Negative Sampling: Negative sampling updates embeddings for observed graph–subgraph pairs and a small set of vocabulary subgraphs absent from the graph.The number of negative samples is a tunable hyper-parameter, with k << |SGvocab|.
5. EVALUATION
The evaluation compares graph2vec with substructure embedding methods and graph kernels across benchmark and real-world classification and clustering tasks. Graph2vec generally outperforms substructure approaches, remains competitive with kernels, and achieves strong accuracy with reasonable efficiency.
- Experimental setup: The evaluation covers graph classification and clustering on benchmark datasets and large real-world malware datasets, comparing graph2vec with node2vec, sub2vec, WL kernel, and Deep WL kernel.The experiments assess both accuracy and efficiency, including malware detection and familial clustering.
- Benchmark classification: Graph2vec outperforms other methods on MUTAG, PTC, and PROTEINS, while achieving slightly lower accuracy than kernels on NCI1 and NCI109.These results are based on benchmark graph-classification datasets.
- Benchmark classification: Node2vec and sub2vec perform poorly for whole-graph representation, while WL and Deep WL kernels provide consistently strong benchmark classification results.Node2vec mainly captures local similarity, and sub2vec’s random-walk sampling is ill-suited to large graphs.
- Real-world clustering: For malware clustering, graph2vec outperforms substructure embedding techniques by more than 39% and kernels by more than 5%, while all methods obtain lower ARIs than in the classification tasks.The clustering task is described as inherently more complex than the preceding classification tasks.
- Overall findings: Across the three experiments, trivially extending node or subgraph embeddings yields subpar results, whereas data-driven graph embeddings achieve accurate results with reasonably good efficiency.The evaluation attributes graph2vec’s performance to an embedding that models local and global graph similarities.
6. CONCLUSIONS
The paper presents graph2vec as an unsupervised method for embedding arbitrarily sized graphs. Experiments show it significantly outperforms substructure embedding approaches, matches graph kernels on benchmark datasets, and surpasses state-of-the-art graph kernels on two large real-world applications without compromising efficiency.
- graph2vec learns unsupervised embeddings for graphs of arbitrary sizes.
- On benchmark graph-classification datasets, graph2vec significantly outperforms substructure embedding approaches and is comparable to graph kernels.
- On two large real-world applications, graph2vec outperforms state-of-the-art graph kernels without compromising overall efficiency.