--- title: "Learning Network Embedding with Community Structural Information" authors: - "Yu Li" - "Ying Wang" - "Tingting Zhang" - "Jiawei Zhang" - "Yi Chang" doi: "10.24963/ijcai.2019/407" url: "https://ijcai.org/proceedings/2019/407" pdf: "https://ijcai.org/proceedings/2019/0407.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "2937-2943" track: "Main track" keywords: - "Machine Learning: Relational Learning" - "Machine Learning: Data Mining" --- # Learning Network Embedding with Community Structural Information Yu Li, Ying Wang, Tingting Zhang, Jiawei Zhang, Yi Chang *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 2937-2943. DOI: [10.24963/ijcai.2019/407](https://doi.org/10.24963/ijcai.2019/407) ## Abstract Network embedding is an effective approach to learn the low-dimensional representations of vertices in networks, aiming to capture and preserve the structure and inherent properties of networks. The vast majority of existing network embedding methods exclusively focus on vertex proximity of networks, while ignoring the network internal community structure. However, the homophily principle indicates that vertices within the same community are more similar to each other than those from different communities, thus vertices within the same community should have similar vertex representations. Motivated by this, we propose a novel network embedding framework NECS to learn the Network Embedding with Community Structural information, which preserves the high-order proximity and incorporates the community structure in vertex representation learning. We formulate the problem into a principled optimization framework and provide an effective alternating algorithm to solve it. Extensive experimental results on several benchmark network datasets demonstrate the effectiveness of the proposed framework in various network analysis tasks including network reconstruction, link prediction and vertex classification. ## Full text ## 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: Table 1: The statistics of datasets. | Datasets | Cornell | Texas | Washington | Wisconsin | Polbooks | Football | Citeseer | Cora | Wiki | Email | Polblogs | |----------------|-----------|---------|--------------|-------------|------------|------------|------------|--------|--------|---------|------------| | |V | | 183 | 183 | 215 | 251 | 105 | 115 | 2110 | 2485 | 2357 | 986 | 1222 | | |E | | 277 | 279 | 365 | 450 | 441 | 613 | 3668 | 5069 | 11592 | 16064 | 16714 | | Avg. degree | 1.51 | 1.52 | 1.70 | 1.79 | 4.20 | 5.33 | 1.74 | 2.04 | 4.92 | 16.29 | 13.68 | | No. of labels | 5 | 5 | 5 | 5 | 3 | 12 | 6 | 7 | 17 | 42 | 2 | Figure 1: Network reconstruction results in terms of precision@K. ![Image](https://ijcai.org/proceedings/2019/fulltext/407/image_000000_9a0ecb801d338c73f1110c67d4d59b14b84a10847d4204527a016de264674912.png) 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. Figure 2: Link prediction results in terms of precision@K. ![Image](https://ijcai.org/proceedings/2019/fulltext/407/image_000001_2a76f61ffb67fb85840d3341b9869845b06924f597d8ea1b4df3e802ad609108.png) 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. Table 2: Link prediction results in terms of map@K. | Methods - map@K | Citeseer - 20 | Citeseer - 50 | Citeseer - 100 | Cora - 20 | Cora - 50 | Cora - 100 | Wiki - 20 | Wiki - 50 | Wiki - 100 | Polblogs - 20 | Polblogs - 50 | Polblogs - 100 | |-------------------|-----------------|-----------------|------------------|-------------|-------------|--------------|-------------|-------------|--------------|-----------------|-----------------|------------------| | DeepWalk | 0.036 | 0.030 | 0.022 | 0.036 | 0.028 | 0.020 | 0.048 | 0.037 | 0.027 | 0.004 | 0.006 | 0.008 | | LINE | 0.056 | 0.041 | 0.028 | 0.046 | 0.032 | 0.022 | 0.056 | 0.042 | 0.030 | 0.009 | 0.010 | 0.010 | | Node2Vec | 0.060 | 0.043 | 0.030 | 0.051 | 0.035 | 0.024 | 0.050 | 0.038 | 0.027 | 0.024 | 0.023 | 0.020 | | GraRep | 0.037 | 0.033 | 0.024 | 0.033 | 0.026 | 0.019 | 0.050 | 0.040 | 0.029 | 0.027 | 0.026 | 0.024 | | SDNE | 0.013 | 0.009 | 0.007 | 0.011 | 0.008 | 0.006 | 0.012 | 0.010 | 0.008 | 0.043 | 0.033 | 0.026 | | M-NMF | 0.042 | 0.037 | 0.027 | 0.027 | 0.023 | 0.018 | 0.050 | 0.038 | 0.028 | 0.027 | 0.027 | 0.026 | | NECS | 0.061 | 0.044 | 0.031 | 0.046 | 0.032 | 0.023 | 0.059 | 0.044 | 0.032 | 0.048 | 0.041 | 0.035 | Table 3: Vertex classification accuracies(%). | Methods | Cornell | Texas | Washington | Wisconsin | Polbooks | Football | Citeseer | Cora | Wiki | Email | Polblogs | |-----------|-----------|---------|--------------|-------------|------------|------------|------------|--------|--------|---------|------------| | DeepWalk | 37.19 | 49.84 | 49.21 | 46.98 | 84.95 | 87.83 | 73.57 | 84.68 | 68.74 | 76.34 | 95.15 | | LINE | 27.03 | 43.24 | 35.81 | 38.43 | 72.00 | 90.78 | 62.05 | 77.28 | 60.66 | 71.78 | 94.92 | | Node2Vec | 37.51 | 55.16 | 54.80 | 48.31 | 87.81 | 41.57 | 74.74 | 85.03 | 65.04 | 63.72 | 95.84 | | GraRep | 54.59 | 69.30 | 58.70 | 58.43 | 81.33 | 90.43 | 71.27 | 81.19 | 65.29 | 73.66 | 95.05 | | SDNE | 45.08 | 61.95 | 54.79 | 50.59 | 83.24 | 74.43 | 41.61 | 49.58 | 47.19 | 56.10 | 91.80 | | M-NMF | 46.27 | 66.92 | 64.47 | 58.35 | 88.86 | 89.91 | 73.06 | 81.15 | 65.08 | 74.59 | 95.90 | | NECS0 | 51.78 | 69.19 | 63.35 | 58.20 | 85.71 | 85.57 | 74.14 | 82.22 | 61.87 | 72.57 | 95.71 | | NECS | 60.54 | 73.51 | 70.69 | 66.27 | 91.43 | 96.52 | 76.16 | 84.59 | 68.18 | 79.90 | 96.49 | 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. Figure 3: Parameter sensitivity and convergence. ![Image](https://ijcai.org/proceedings/2019/fulltext/407/image_000002_52e026ee011b454d0f5b362aa3fa5d9620db440091db248c9bd29d634d4e4224.png) ## 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. ## References 1. [Adamic and Glance, 2005] Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us elec- tion: divided they blog. In Proceedings of the 3rd interna- tional workshop on Link discovery, pages 36-43, 2005. 2. [Cao et al., 2015] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of CIKM, pages 891-900, 2015. 3. [Cavallari et al., 2017] Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cam- bria. Learning community embedding with community de- tection and node embedding on graphs. In Proceedings of CIKM, pages 377-386, 2017. 4. [Fan et al., 2008] Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. Journal of machine learning research, 9(Aug):1871-1874, 2008. 5. [Gao and Huang, 2018] Hongchang Gao and Heng Huang. Self-paced network embedding. In Proceedings of KDD, pages 1406-1415, 2018. 6. [Girvan and Newman, 2002] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sci- ences, 99(12):7821-7826, 2002. 7. [Gligorijevic et al., 2016] Vladimir Gligorijevic, Yannis Panagakis, and Stefanos P. Zafeiriou. Non-negative matrix factorizations for multiplex network analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, PP(99):1-1, 2016. 8. [Grover and Leskovec, 2016] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of KDD, pages 855-864, 2016. 9. [Karrer and Newman, 2011] Brian Karrer and Mark EJ New- man. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011. 10. [Lee and Seung, 2001] Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Pro- ceedings of NIPS, pages 556-562, 2001. 11. [Li et al., 2018] Yixuan Li, Kun He, Kyle Kloster, David Bindel, and John Hopcroft. Local spectral clustering for overlapping community detection. ACM Transactions on Knowledge Discovery from Data, 12(2):17, 2018. 12. [Lian et al., 2018] Defu Lian, Kai Zheng, Vincent W Zheng, Yong Ge, Longbing Cao, Ivor W Tsang, and Xing Xie. High-order proximity preserving information net- work hashing. In Proceedings of KDD, pages 1744-1753, 2018. 13. [McCallum et al., 2000] Andrew Kachites McCallum, Ka- mal Nigam, Jason Rennie, and Kristie Seymore. Automat- ing the construction of internet portals with machine learn- ing. Information Retrieval, 3(2):127-163, 2000. 14. [Mikolov et al., 2013] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed rep- resentations of words and phrases and their composition- ality. In Proceedings of NIPS, pages 3111-3119, 2013. 15. [Newman, 2004] Mark EJ Newman. Detecting community structure in networks. The European Physical Journal B, 38(2):321-330, 2004. 16. [Newman, 2006] Mark EJ Newman. Modularity and com- munity structure in networks. Proceedings of the national academy of sciences, 103(23):8577-8582, 2006. 17. [Perozzi et al., 2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of KDD, pages 701-710, 2014. 18. [Riolo et al., 2017] Maria A Riolo, George T Cantwell, Ge- sine Reinert, and Mark EJ Newman. Efficient method for estimating the number of communities in a network. Phys- ical Review E, 96(3):032310, 2017. 19. [Tang and Liu, 2011] Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23(3):447-478, 2011. 20. [Tang et al., 2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of WWW, pages 1067-1077, 2015. 21. [Von Luxburg, 2007] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395- 416, 2007. 22. [Wang et al., 2011] Fei Wang, Tao Li, Xin Wang, Shenghuo Zhu, and Chris Ding. Community discovery using nonneg- ative matrix factorization. Data Mining and Knowledge Discovery, 22(3):493-521, 2011. 23. [Wang et al., 2016] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of KDD, pages 1225-1234, 2016. 24. [Wang et al., 2017] Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserv- ing network embedding. In Proceedings of AAAI, pages 203-209, 2017. 25. [Yang and Leskovec, 2012] Jaewon Yang and Jure Leskovec. Community-affiliation graph model for overlapping network community detection. In Proceed- ings of ICDM, pages 1170-1175, 2012. 26. [Yang and Leskovec, 2013] Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of WSDM, pages 587-596, 2013. 27. [Yang et al., 2017] Cheng Yang, Maosong Sun, Zhiyuan Liu, and Cunchao Tu. Fast network embedding enhancement via high order proximity approximation. In Proceedings of IJCAI, pages 19-25, 2017. 28. [Zhang et al., 2018] Ziwei Zhang, Peng Cui, Xiao Wang, Jian Pei, Xuanrong Yao, and Wenwu Zhu. Arbitrary-order proximity preserved network embedding. In Proceedings of KDD, pages 2778-2786, 2018.