subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs

By Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, S. Saminathan. 2016

160 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems, Representation & Self-Supervised Learning, Graph Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Yoshua Bengio
2. Sergey Levine
3. Percy Liang
4. Mohit Bansal
5. Quoc V. Le
6. Ruslan Salakhutdinov
7. Jianfeng Gao
8. Kyunghyun Cho

In Information Systems

1. Pushmeet Kohli
2. Jure Leskovec
3. Marinka Zitnik
4. Peter W. Battaglia
5. Oriol Vinyals
6. Mateusz Malinowski
7. Weihua Hu
8. Percy Liang

In Representation & Self-Supervised Learning

1. Jure Leskovec
2. Yoshua Bengio
3. Sergey Levine
4. Marinka Zitnik
5. Razvan Pascanu
6. Oriol Vinyals
7. Kevin Chen-Chuan Chang
8. Adam Santoro

In Graph Learning

1. Jure Leskovec
2. William L. Hamilton
3. Marinka Zitnik
4. Peter W. Battaglia
5. Jian Tang
6. Weihua Hu
7. Kevin Chen-Chuan Chang
8. Percy Liang

In Signal Processing

1. Yoshua Bengio
2. Li Deng
3. Dong Yu
4. Oriol Vinyals
5. Chris Dyer
6. Razvan Pascanu
7. Caglar Gulcehre
8. Charlie Nash

Citations in the corpus

• Strategies for Pre-training Graph Neural Networks (2019, background): “A number of recent works have also explored how node embeddings generalize across tasks (Jaeger et al., 2018; Zhou et al., 2018; Chakravarti, 2018; Narayanan et al., 2016).”
• Relational inductive biases, deep learning, and graph networks (2018, background): “…which use distributed, vector representations to capture rich semantic content in text (Mikolov et al., 2013; Pennington et al., 2014), graphs (Narayanan et al., 2016, 2017), algebraic and logical expressions (Allamanis et al., 2017; Evans et al., 2018), and programs (Devlin et al., 2017;…”
• graph2vec: Learning Distributed Representations of Graphs (2017, background): “Recently, several approaches have been proposed to learn embeddings of graph substructures such as nodes [4], paths [7] and sub-graphs [5, 6].”
• struc2vec: Learning Node Representations from Structural Identity (2017, background): “subgraph2vec [14] is another recent approach for learning embeddings for rooted subgraphs, and unlike the previous techniques it does not use random walks to generate context.”
• DeepCas: An End-to-end Predictor of Information Cascades (2016, background): “Some studies have applied deep learning techniques to improving graph kernels [40, 27].”
• Geom-GCN: Geometric Graph Convolutional Networks (2020, background): “In the latent space, complicated topology patterns in graphs can be preserved and presented as intuitive geometry, such as subgraph (Narayanan et al., 2016), community (Ni et al., 2019), and hierarchy (Nickel & Kiela, 2017; 2018).”
• GEMSEC: Graph Embedding with Self Clustering (2018, background): “Specifically, there is work looking at graphs with signed edges [35] and rooted subgraphs [18].”
• Autoencoder-based feature learning for cyber security applications (2017, methodology): “Deep learning models have been recently used to detect and classify malware in Microsoft Windows and Android [12, 13, 14, 15].”
• Pre-training Graph Neural Networks (2019, background): “It should be noted that similar intuition has been explored in the literature [32, 19, 63].”