Deep Neural Networks for Learning Graph Representations

By Shaosheng Cao, Wei Dang Lu, Qiongkai Xu. 2016

1,030 citations recorded by the source corpus.

In this paper, we propose a novel model for learning graph representations, which generates a low-dimensional vector representation for each vertex by capturing the graph structural information. Different from other previous research efforts, we adopt a random surfing model to capture graph structural information directly, instead of using the sampling-based method for generating linear sequences proposed by Perozzi et al. (2014). The advantages of our approach will be illustrated from both theorical and empirical perspectives. We also give a new perspective for the matrix factorization method proposed by Levy and Goldberg (2014), in which the pointwise mutual information (PMI) matrix is considered as an analytical solution to the objective function of the skip-gram model with negative sampling proposed by Mikolov et al. (2013). Unlike their approach which involves the use of the SVD for finding the low-dimensitonal projections from the PMI matrix, however, the stacked denoising autoencoder is introduced in our model to extract complex features and model non-linearities. To demonstrate the effectiveness of our model, we conduct experiments on clustering and visualization tasks, employing the learned vertex representations as features. Empirical results on datasets of varying sizes show that our model outperforms other stat-of-the-art models in such tasks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics, Graph Learning

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

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Representation Learning on Graphs: Methods and Applications (2017, background): “Deep Neural Graph Representations (DNGR) [10] and Structural Deep Network Embeddings (SDNE) [58] address the ﬁrst problem outlined above: unlike the direct encoding methods, they directly incorporate graph structure into the encoder algorithm.”
Learning Graph-Level Representation for Drug Discovery (2017, background): “(Cao, Lu, and Xu 2016) propose a novel model for learning graph representations, which generates a low-dimensional vector representation for each vertex by capturing the graph structural information.”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, methodology): “ embed each substructure as a vector and compare graphs via the substructure similarities. 5.3.2 Visualization Graph visualization generates visualizations of a graph on a low dimensional space [19], [22], [48], [55], [58], [72]. Usually, for visualization purpose, all nodes are embedded as 2D vecto”
Adversarially Regularized Graph Autoencoder (2018, background): “DNGR [Cao et al., 2016] trains a stacked denoising autoencoder for graph embedding.”
Self-Supervised Learning: Generative or Contrastive (2020, methodology): “In general, existing network embedding approaches are broadly categorized as (1) factorization-based approaches such as NetMF [110], [111], GraRep [18], HOPE [102], (2) shallow embedding approaches such as DeepWalk [106], LINE [134], HARP [21], and (3) neural network approaches [19], [86].”
Graph Embedding Techniques, Applications, and Performance: A Survey (2017, background): “The growing research on deep learning has led to a deluge of deep neural networks based methods applied to graphs [23], [33], [34].”
Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec (2017, background): “…[7, 11, 17, 34], direct network embedding [27], semi-supervised network embedding [18, 42, 49], network embedding with rich vertex attributes [41, 47], network embedding with high order structure [5, 15], network embedding via deep neural network [6, 22, 44], signed network embedding [9], etc.”
struc2vec: Learning Node Representations from Structural Identity (2017, background): “Similarly to subgraph2vec, considerable eort has recently been made on learning richer representations for network nodes [4, 24].”
Network Representation Learning: A Survey (2017, methodology): “, GraRep [26], DNGR [9], MNMF [28], and pRBM [29]) used the clustering performance to evaluate the quality of the learned network representations on different networks.”
Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba (2018, methodology): “These methods could be categorized into three broad categories: (1) Factorization methods such as LINE [1] try to approximately factorize the adjacencymatrix and preserve both first order and second proximities, (2) Deep learning methods [4, 21, 22] enhance the model’s ability of capturing non-linea”
A Survey on Network Embedding (2017, methodology): “Cao et al. (Cao, Lu, and Xu 2016) propose a network embedding method to capture the weighted graph structure In summary, many network embedding methods aim to preserve the local structure of a node, including neighborhood structure, high-order proximity as well as community structure, in the latent ”
deepDR: a network-based deep learning approach to in silico drug repositioning (2019, methodology): “2.2 Random walk-based network representation We adopt the approach used in Cao (2016) to capture network structural information and to characterize the topological context of each drug.”
GEMSEC: Graph Embedding with Self Clustering (2018, methodology): “Besides sequence based graph embedding procedures other neural models were developed specifically to create representations of graphs for downstream machine learning tasks [4, 31].”
Adaptive Graph Encoder for Attributed Graph Embedding (2020, background): “ctive function. [10, 25] learn node embeddings by generating random walks and input the sequences into SkipGram model [17], assuming that similar nodes tend to cooccur in same sequences. Other models [4, 27, 33] can be concluded by an encoder-decoder framework [11], while they differ from model stru”
Graph embedding on biomedical networks: methods, applications and evaluations (2019, methodology): “DNGR (Cao et al., 2016) applies the stacked denoising autoencoders on the positive pointwise mutual information (PPMI) matrix to learn deep low-dimensional node embeddings.”
Adversarial Examples on Graph Data: Deep Insights into Attack and Defense (2019, background): “The recent advance [Kipf and Welling, 2017; Veliˇckovi´c et al. , 2018; Cao et al. , 2016; Henaff et al. , 2015] in deep learning expands its applications on graph data.”
GraphGAN: Graph Representation Learning with Generative Adversarial Nets (2017, methodology): “The second kind of graph representation learning method is the discriminative model (Wang et al. 2018; Cao, Lu, and Xu 2016; Wang, Cui, and Zhu 2016; Li et al. 2017b).”