Learning Network Embedding with Community Structural Information

1 Introduction

Networks are ubiquitous in the real world, such as social networks, bibliographic networks and communication networks. Networks often involve extensively interconnected structures, which make it difficult to directly apply machine learning algorithms on them for various network analysis tasks, such as network reconstruction, link prediction and vertex classification. Therefore, how to represent network data is a crucial problem for network analysis tasks. In recent years, network embedding has been widely recognized as an effective approach to learn the low-dimensional vector representations of vertices in networks. With proper network embedding, vector-based machine learning algorithms can be easily applied to those aforementioned network analysis tasks.

∗Corresponding author: wangying2010@jlu.edu.cn

One effective strategy to obtain the low-dimensional vector representations is to preserve the proximity between vertices in networks. The adjacency matrix (i.e., first-order proximity) is the most intuitive way to reveal the network structure. However, the adjacency matrix is also very sparse and insufficient to fully characterize the relationships between vertices. In order to capture the network structure and characterize the relationships better, researchers turn their attentions to high-order proximity [Cao et al., 2015; Yang et al., 2017; Gao and Huang, 2018; Lian et al., 2018; Zhang et al., 2018]. Particularly, NEU [Yang et al., 2017] improves the performance of some network embedding methods [Perozzi et al., 2014; Tang et al., 2015; Cao et al., 2015; Grover and Leskovec, 2016] in some ways by approximating high-order proximity matrix.

However, the aforementioned methods predominantly focus on the vertex proximity of networks, while ignoring the community structure which is ubiquitous in networks. A community is intuitively identified as a group of vertices with more connections between its internal vertices compared with the external ones [Girvan and Newman, 2002]. The homophily principle indicates that vertices within the same community are more similar to each other than those from different communities. Network embedding aims to learn the low-dimensional vector representations of vertices while preserving both the structure and inherent properties of networks. Therefore, It is nontrivial to integrate the community structure into network embedding as community structure is an important property of network [Wang et al., 2017; Cavallari et al., 2017].

Inspired by the effectiveness of high-order proximity and the homophily principle, we propose a novel network embedding framework NECS to learn the Network Embedding with Community Structural information, which utilizes the high-order proximity to learn the vertex representations while incorporating the network community structure. NECS first learns the vertex representations using nonnegative matrix factorization that approximates the high-order proximity. Afterwards, NECS models the community structure according to the homophily principle, and incorporates the community structure to guide the vertex representation learning. NECS optimizes the vertex representations based on both the vertex proximity together with the community structure. Thus, the vertex representations learned by NECS can preserve both the vertex proximity and the community structure of the networks, and whose effectiveness will be tested with extensive experiments on real-world benchmark network datasets. The main contributions of our paper are as follows:

• we propose a novel network embedding framework NECS, which effectively preserves the high-order vertex proximity and incorporates the community structure of networks in vertex representation learning;
• we provide an effective alternating optimization algorithm for the proposed NECS framework; and
• we evaluate the effectiveness of the proposed NECS framework on several real-world benchmark network datasets with various concrete network analysis tasks.

2 RelatedWork

2.1 Network Embedding

Here we give a brief introduction to existing network embedding methods. DeepWalk [Perozzi et al., 2014] introduces truncated random walks to obtain the vertex sequences and adopts Skip-gram [Mikolov et al., 2013] model to learn the vertex representations. LINE [Tang et al., 2015] optimizes an objective function that preserves the first-order and second-order proximities during vertex representation learning. Not only the first-order and second-order proximities, but the high-order proximities are also adopted to preserve the proximity between vertices. NEU [Yang et al., 2017] enhances the performance of the network embedding methods by approximating high-order proximity. INH-MF [Lian et al., 2018] obtains binary code representations of information networks by preserving high-order proximity. AROPE [Zhang et al., 2018] derives the vertex representations based on singular value decomposition framework while preserving arbitraryorder proximity. In addition, many other works [Cao et al., 2015; Grover and Leskovec, 2016; Wang et al., 2016; Gao and Huang, 2018] preserve the vertex proximity explicitly or implicitly.

2.2 Community Structure

Effectively identifying communities in a network can help us to know the network structure better and facilitate the network analysis tasks. Many types of community detection methods have been proposed to identify the communities contained in a network, such as clustering-based methods [Newman, 2004], modularity-based methods [Newman, 2006], spectral algorithms [Tang and Liu, 2011; Li et al., 2018] and so on. However, most of these methods assign a vertex to only one community and lack the interpretability. In recent years, community affiliation based algorithms have attracted considerable attention [Yang and Leskovec, 2012; Yang and Leskovec, 2013; Gligorijevic et al., 2016]. Community affiliation based algorithms learn the vertex-community membership low-dimensional representations of vertices and assign vertices to the corresponding communities according to these representations. For example, NF-CCE [Gligorijevic et al., 2016] decomposes adjacency matrix into a low-dimensional, nonnegative community affiliation representation matrix, and extracts communities from the matrix. By incorporating vertex representation learning with community affiliation representation learning and jointly optimizing them, we can utilize community structural information to learn more discriminative representations of vertices.

3 The Proposed Framework

In this section, we present the proposed network embedding framework - NECS in detail. We first summarize the notations used in this paper. We use bold uppercase characters for matrices(e.g., A), and represent the (i, j)-th entry of matrix A as Aij, the i-th row of matrix A as Ai∗, the j-th column of matrix A as A∗j, the transpose of A as AT , the trace of A as tr(A) if A is a square matrix. For an arbitrary matrix A ∈ Rn×d , its Frobenius norm is defined as ‖A‖F = √∑ni=1 ∑dj=1 A2ij . In addition, ⊙, I, ‖ · ‖ and 1 denote the hadamard product, identify matrix, L2-norm of a vector and a vector with each element equals to 1, respectively.

Let G = (V, E) be an undirected and unweighted graph, where V = {v1, v2, ..., vn} is the set of vertices and E is the set of edges connecting vertices in V. Nonnegative symmetric matrix A ∈ Rn×n denotes the adjacency matrix of G, where Aij = 1 if there is an edge between vi and vj, or Aij = 0 otherwise.

With these notations, we will discuss how to incorporate the high-order proximity and the community structure to learn the low-dimensional representations of vertices in G in the following subsections.

3.1 High-Order Vertex Proximity

The homophily principle indicates the correlations between vertices, which imply that the connected vertices are more likely to be similar to each other than the unconnected ones. Thus, the adjacency matrix A can be treated as the firstorder proximity, which captures the pairwise proximity between vertices. However, the first-order proximity is also very sparse and insufficient to fully model the relationships between vertices in most cases. In order to characterize the connections between vertices better, high-order proximity is widely studied, and the order of the proximity varies considerably on different networks and target applications [Yang et al., 2017; Zhang et al., 2018].

Definition 1 (High-order Proximity). Given the adjacency matrix A, a high-order proximity can be defined as a polynomial function of A :

where l is the order, and w1, ...,wl are the weights for each term. Matrix Al denotes the l-order proximity matrix, which is defined as follows:

To integrate the high-order proximity in network embedding, the widely adopted method is nonnegative matrix factorization, which can be formulated as follows:

where the positive semi-definite matrix U, V ∈ Rn×d are the low-dimensional representations of vertices.

3.2 Community Structure

In the stochastic block model [Karrer and Newman, 2011], the value of Aij can be viewed as the probability that there is an edge between vi and vj, and also determined by the probability that vi and vj generate edges belonging to the same community. Denote C = {c1, c2, ..., ck} as the set of community labels, and H = [Hir] ∈ Rn×k , where Hir represents the probability that vi generates an edge belonging to community cr. Hir is also viewed as the probability of vi belonging to community cr, thus the probability of vi and vj belonging to the same community can be represented as: ˜Sij = ∑kr=1 HirHjr. In real-world networks, the homophily principle indicates that if vertices are more similar to each other, they are more likely to belong to the same community. Thus, we can measure the similarity between two arbitrary vertices vi and vj as Sij = Ai∗A∗j/‖Ai∗‖‖A∗j‖. By minimizing the difference between ˜Sij and Sij, we can learn the community structure with the following nonnegative matrix factorization problem:

In order to utilize the community structure to learn the lowdimensional vertex representation matrix U, we introduce a nonnegative community representation matrix W ∈ Rk×d , where r-th row of W (e.g., Wr∗) is the representation of community cr [Wang et al., 2017]. Thus, with the representation Ui∗ of vi, we can mathematically model the probability of vi belonging to community cr as Ui∗WT r∗ . Without loss of generality, for all the vertices, the problem is formulated as follows:

where we learn the low-dimensional representations of vertices by minimizing the difference between H and UWT . In other words, we expect to jointly optimize U and H to boost each other to obtain more discriminative representations.

With modeling the relationship between U and H, the final objective function of the proposed NECS framework is formulated as follows:

The problem in Eq.(5) is difficult to solve due to the constraint on H. To tackle the issue, we relax the constraint on H to an orthogonal constraint instead, i.e., HT H = I [Von Luxburg, 2007]. After the relaxation, we can further rewrite the above objective function as:

where we introduce a parameter λ to ensure that the orthogonal condition is satisfied. Normally, we set it as a enough large number (e.g., 108 ) to make the orthogonal condition satisfied.

4 Alternating Optimization Algorithm

The objective function of the proposed NECS framework is not jointly convex, so we cannot optimize all the variables U, V, W and H simultaneously. To optimize the objective function, we provide an alternating optimization algorithm to learn one variable while fixing others.

4.1 Update Rule for U

First, we fix V, W and H to update U. Specifically, when V, W and H are fixed, the objective function is convex w.r.t the low-dimensional vertex representation matrix U. Then by removing the terms that are irrelevant to U, the objective function can be rewritten as follows:

The Lagrangian function of Eq.(7) is:

where ΛU is the Lagrange multiplier for the constraint U ≥ 0. By taking the derivative of L(U) w.r.t. U and setting it to zero, we can get:

With the KKT complementary condition for the nonnegativity of U, i.e., [ΛU]ij Uij = 0, we have:

which leads to the following update rule for U:

4.2 Update Rules for V, Wand H

Similar to the process of getting the update rule for U, we can update V, W and H by the following update rules:

where Φ = (α + λ)HHT H ⊙ (4αSH + 2βUWT + (4λ - 2β)H). Such an updating procedure will continue until convergence.

4.3 Framework Learning Analysis

We use J(U,V,W,H) to denote the objective function in Eq.(6). In each iteration, we update U, V, W and H iteratively. Following the definitions and lemmas in [Lee and Seung, 2001; Wang et al., 2011], we can define auxiliary functions F(θ, ˜ θ) for θ, where θ ∈ {U,V,W,H}. By minimizing these auxiliary functions, we can get the corresponding update rules, which hold the following inequality condition:

which proves the convergence of the proposed framework.

Based on the descriptions aforementioned, the main computation of NECS is in computing the update values for U, V, W and H in each iteration. The computation cost of updating U, V, W and H are O(nd2 + n2d + d2k), O(n2k), O(ndk) and O(n2d + n2k), respectively. Thus, the overall computation cost of NECS is O(n2d + n2k), which is in the same order of magnitude as nonnegative matrix factorization.

5 Experiments

5.1 Datasets and Baseline Methods

To verify the effectiveness of the proposed framework, we conduct experiments on the following eleven network datasets, including WebKB(Cornell, Texas, Washington, Wisconsin) 1 [Wang et al., 2017], Citeseer 1 [McCallum et al., 2000], Cora 1 [McCallum et al., 2000], Polbooks 2 , Football 2 , Polblogs 2 [Adamic and Glance, 2005], Wiki 3 and Email 4 . All statistics of the datasets are summarized in Table 1.

We compare the proposed framework with the following state-of-the-art methods:

• Deepwalk [Perozzi et al., 2014]: It adopts random walk and skip-grammodel to learn the vertex representations.
• LINE [Tang et al., 2015]: It optimizes an objective function that preserves the first-order and second-order proximities to learn the vertex representations. LINE also achieves a better performance when preserving both the first-order and second-order proximities by concatenating the corresponding vertex representations.
• Node2Vec [Grover and Leskovec, 2016]: It obtains the vertex representations by maximizing the likelihood of preserving network neighborhoods of vertices.
• GraRep [Cao et al., 2015]: It integrates global structural information to generate the vertex representations.
• SDNE [Wang et al., 2016]: It exploits both the firstorder and second-order proximities jointly in a semisupervised deep model to generate the vertex representations.

1 http://www.cs.umd.edu/%7Esen/lbc-proj/LBC.html

2 http://www-personal.umich.edu/%7Emejn/netdata/

3 https://github.com/thunlp/MMDW/tree/master/data

4 http://snap.stanford.edu/data/email-Eu-core.html

• M-NMF [Wang et al., 2017]: It incorporates vertex proximity and modularity-based community detection problem to learn the vertex representations.

For a fair comparison, we set the representation dimension d as 128 for all methods. For DeepWalk, we set the windowsize as 5, the number of walks as 10 and the walk-length as 40. For LINE, we set the number of negative samples as 5, the total number of training samples as 10 million and the starting learning rate as 0.025. For Node2Vec, we set the number of walks as 10, the walk-length as 80, p as 1, q as 1 and the window size as 5. For GraRep, we set the maximum matrix transition as 4. For SDNE, we set α as 100, β as 10 and batch size as 16. For M-NMF, we tune α and β from {0.1, 0.5, 1, 5, 10} to get the best performance. In NECS, we vary the order l from {1, 2, 3} and α, β from {0.1, 0.2, 0.5, 1, 2, 5, 10}. To shrink the searching space for hyper-parameters of high-order proximity, we simply fix the weights as wi = µi-1 and vary µ from {0.1, 0.2, 0.3}.

5.2 Network Reconstruction

The capability of reconstructing the original network is a basic evaluation metric for network embedding, and the vertex representations learned by a good network embedding method should preserve the original network structure. Generally, a larger similarity between two vertices implies that they are more likely to be linked. Thus, we rank pairs of vertices according to their similarities, i.e. the inner product of vertex representations. In this section, we use Citeseer, Cora, Wiki and Polblogs as representatives to assess the performance of network reconstruction in term of precision@K, which is defined as follows:

where index(j) is the rank index of j-th vertex, and △i(j) = 1 indicates vi and vj have an edge.

The precision@K results are shown in Figure 1, and the maximum K equals to the number of the edges |E|. On Wiki, NECS outperforms all the baselines significantly. On the remaining datasets, LINE performs better than NECS when K is relatively small, and NECS begins to generally outperform the baselines when K becomes relatively large. A point to note is that when K varies in the range of 2500 to 3000 on Cora, the precision scores of GraRep are higher than NECS. A possible reason is that GraRep integrates the network structural information to learn the vertex representations, which demonstrates the necessity of the integrating network structural information into network embedding. And the same goes for the network community structural information.

5.3 Link Prediction

For link prediction task, we randomly remove 10% edges as test set for evaluation and utilize the remaining edges to learn the vertex representations. Similar to the network reconstruction task, we rank pairs of vertices in a similar way as network reconstruction and conduct experiments on Citeseer, Cora, Wiki and Polblogs to assess the performance of link prediction in terms of precision@K and map@K. The formula of map@K is:

where Vt is the set of vertices whose edges are removed.

The precision@K results are shown in Figure 2, and the maximum K equals to the number of the removed edges. The results show that NECS outperforms all the baselines significantly, especially when K equals to the number of the removed edges, NECS achieves at least 40% improvement over all the baselines. The precision scores for all the methods are lower on Citeseer than other datasets, this is mainly because Citeseer is relatively sparser, which makes it difficult to predict links. But NECS still achieves significantly better results in that case. Furthermore, the map@K results are listed in Table 2. The results show that NECS outperforms the baselines on all the datasets except Cora. NECS achieves the second best results on map@20, map@50 and map@100 on Cora. The performance of NECS in link prediction task demonstrates its ability to capture the network structure.

5.4 Vertex Classification

For vertex classification task, we randomly sample 80% vertices as training set and the remaining vertices as test set, and then adopt the L2-regularized logistic regression implemented by LIBLINEAR[Fan et al., 2008] to build the classifiers. We conduct experiments on all the eleven datasets described in Table 1 and repeat the process 5 times. The average accuracies are reported in Table 3.

We use NECS0 to denote the formulation defined in Eq.(2), and note that NECS0 achieves a comparable performance, which verifies the effectiveness of the vertex proximity P. The results show that NECS outperforms the baselines on the majority of datasets. Especially on WebKB, Polbooks and Football, NECS achieves a significant improvement. Although NECS achieves the second and third best results on Wiki and Cora respectively, the results are evidently better than the remaining baselines. Comparing NECS with NECS0, NECS achieves a significant improvement over NECS0 on all the datasets, which demonstrates the necessity and effectiveness of incorporating network embedding and the community structure.

5.5 Parameter Study

NECS has five parameters α, β, µ, l and k. Among them, α and β control how well the network embedding preserves the community structure, µ and l control to what extent the highorder proximity contributes to vertex proximity, and k controls the number of communities we desire to extract. For the number of communities k, we just simply set k as the known number of communities. Generally speaking, we can use the method in [Riolo et al., 2017] to estimate k. We further investigate the impacts of parameters of α, β, µ and l on the performance of NECS using vertex classification task as an example. Due to the space limit, we only show the parameter study results on the Email dataset as we have similar observations on other datasets. To study how its variation affects the performance, we fix one parameter each time and vary the others. The performance variation of these parameters are shown in Figure 3(a)-(c). Particularly, we set l = 2 so as to plot in a 3-D figure. We can see that the performance is relatively stable, however, without clear trends. This is mainly because α and β collectively control the degree of network embedding preserving the community structure.

To show the convergence of NECS intuitively, the value of the loss function in Eq.(6) at the end of each iteration is recorded and normalized by |V| for different datasets so as to illustrate them in one figure. For simplicity, we set α, β, µ and l as 1, 1, 0.1 and 2 for all the datasets, respectively. As illustrated in Figure 3(d), NECS converges very quickly.

6 Conclusion

In this paper, we propose a novel network embedding framework NECS, which preserves the high-order proximity and incorporates the community structure. First, we use nonnegative matrix factorization to learn the vertex representations by preserving the high-order proximity. Then, we obtain the community structure by approximating the similarity between vertices according to the homophily principle. Finally, we establish the consensus relationship between the vertex representations and the community structure, and jointly optimize them to boost each other to obtain more discriminative representations. Methodologically, we provide an alternating optimizing algorithm for the proposed framework. Extensive experimental results demonstrate the effectiveness of the framework in several network analysis tasks. In the future, we strive to generalize this framework to signed networks.

Acknowledgements

This work is partially supported by National Natural Science Foundation of China (No.61872161, No.61602057), National Science Foundation (No.IIS-1763365), the special research program of Jilin University of Finance and Economics for newly recruited teacher with doctorates in 2018 (No.08183402), and the Fundamental Research Funds for the Central Universities, JLU.