Community Preserving Network Embedding

By Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, Shiqiang Yang. 2017

922 citations recorded by the source corpus.

Network embedding, aiming to learn the low-dimensional representations of nodes in networks, is of paramount importance in many real applications. One basic requirement of network embedding is to preserve the structure and inherent properties of the networks. While previous network embedding methods primarily preserve the microscopic structure, such as the first- and second-order proximities of nodes, the mesoscopic community structure, which is one of the most prominent feature of networks, is largely ignored. In this paper, we propose a novel Modularized Nonnegative Matrix Factorization (M-NMF) model to incorporate the community structure into network embedding. We exploit the consensus relationship between the representations of nodes and community structure, and then jointly optimize NMF based representation learning model and modularity based community detection model in a unified framework, which enables the learned representations of nodes to preserve both of the microscopic and community structures. We also provide efficient updating rules to infer the parameters of our model, together with the correctness and convergence guarantees. Extensive experimental results on a variety of real-world networks show the superior performance of the proposed method over the state-of-the-arts.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Transportation, 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 Statistical and Nonlinear Physics

In Transportation

In Graph Learning

Citations in the corpus

Inductive Representation Learning on Large Graphs (2017, neutral): “The majority of these approaches directly optimize the embeddings for each node using matrix-factorization-based objectives, and do not naturally generalize to unseen data, since they make predictions on nodes in a single, fixed graph [5, 11, 23, 28, 35, 36, 37, 39].”
Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “As described in the main paper, there are many methods to obtain such node embeddings, such as: • Matrix Factorization: This category includes a vast amount of both early and recent works on network (node) embedding, such as LAPLACIAN EIGENMAPS (LLE) (Belkin & Niyogi, 2003), MNMF (Wang et al., 2017)”
Deep Graph Infomax (2018, background): “…best of our knowledge, the sole prior works that instead focuses on contrasting “global” and “local” representations on graphs do so via (auto-)encoding objectives on the adjacency matrix (Wang et al., 2016) and incorporation of community-level constraints into node embeddings (Wang et al., 2017).”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “(5) + O(SVM classifier) HSCA [57] PMI O(MMDW) + (1st order proximity constraint) MVE [107] KNN,W ¼ argmin trðWð Pd i¼1 yiy T i þ PN i¼dþ1 yiy T i ÞÞ Eq.”
Adversarially Regularized Graph Autoencoder (2018, methodology): “As a graph can be mathematically represented as an adjacency matrix, many matrix factorization approaches such as GraRep [Cao et al. , 2015], HOPE [Ou et al. , 2016], M-NMF [Wang et al. , 2017b] are proposed to learn the latent representation for a graph.”
Deep Representation Learning for Social Network Analysis (2019, methodology): “Some methods treat embedding and clustering as disjointed tasks, where they first embed nodes to low-dimensional vectors, and then apply traditional clustering algorithms to produce clusters (Tian et al., 2014; Cao et al., 2015; Wang et al., 2017).”
A Survey on Network Embedding (2017, methodology): “Network embedding, as a promising way of network representation, is capable of supporting subsequent network processing and analysis tasks such as node classification [2], [3], node clustering [4], network visualization [5], [6] and link prediction [7], [8].”
Signed Graph Convolutional Networks (2018, background): “Furthermore, learning low-dimensional node representations have been previously proven to be useful in many network analysis tasks beyond node classification [9], such as link prediction [10], community detection [11], and visualization [12].”
Deep Learning on Graphs: A Survey (2018, neutral): “Some existing tasks are associated with mesoscopic structures such as community detection [21].”
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.”
Spatio-Temporal Self-Supervised Learning for Traffic Flow Prediction (2022, background): “It has achieved great success with text (Kenton and Toutanova 2019), image (Chen et al. 2020), and graph data (Wang et al. 2017).”
Learning Community Embedding with Community Detection and Node Embedding on Graphs (2017, methodology): “For example, M-NMF [31] constructs the modularity matrix with O (| V | 2 ) complexity, then applies non-negative matrix factorization to learn node embedding and community detection together with a complexity proportional to O (| V | 2 ) .”
Improved Semantic-Aware Network Embedding with Fine-Grained Word Alignment (2018, background): “This approach has attracted considerable attention in recent years (Tang and Liu, 2009; Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Wang et al., 2016; Chen et al., 2016; Wang et al., 2017a; Zhang et al., 2018).”
Fast Network Embedding Enhancement via High Order Proximity Approximation (2017, background): “, 2016], community preserving [Wang et al., 2017] and heterogenous [Tang et al.”
Attributed Graph Clustering: A Deep Attentional Embedding Approach (2019, methodology): “Many embedding learning based approaches apply an existing clustering algorithm on the learned embedding [ Wang et al. , 2017b ] .”
Heterogeneous Graph Attention Network (2019, methodology): “rned embeddings can be applied to the downstream network tasks. For example, the random walk based methods [12, 23], the deep neural network based methods [36], the matrix factorization based methods [22, 37], and others, e.g., LINE [33]. However, all these algorithms are proposed for the homogeneou”
Unsupervised Attributed Multiplex Network Embedding (2019, background): “Among various graph mining techniques, network embedding, which learns low-dimensional vector representations for nodes in a graph, is shown to be especially effective for various network-based tasks (Tang et al. 2015; Wang et al. 2017; Meng et al. 2019).”
A Survey on Heterogeneous Graph Embedding: Methods, Techniques, Applications and Sources (2020, neutral): “Accordingly, the homogeneous graph embedding pays more attention on higherorder graph structures, for example, second-order structures [39], [46], high-order structures [47], [48] and community structures [40].”
Domain-specific Knowledge Graphs: A survey (2020, background): “This can be indicated in the current extensive use of KGE to tackle problems such as KG completion, entity recognition, and link-based clustering [31-33].”
Learning Graph Embedding With Adversarial Training Methods (2019, methodology): “Matrix factorization-based algorithms, such as GraRep [18], HOPE [19], and M-NMF [20] preprocess the graph structure into an adjacency matrix and obtain the embedding by factorizing the adjacency matrix.”