Community Detection and Link Prediction via Cluster-driven Low-rank Matrix Completion

1 Introduction

Community structure is ubiquitous in real-world networks, and many community detection algorithms have been proposed, e.g., NCut [Shi and Malik, 2000], MCL [Van Dongen, 2000], Modularity [Newman, 2006], Attractor [Shao et al., 2015], FUSE [Ye et al., 2016], ORSC[Shao et al., 2017], MAPPR [Yin et al., 2017], Dcut [Shao et al., 2018], to mention a few. Although community detection has achieved great success during the past decade, finding intrinsic community structure in networks is still challenging. For example, most existing community detection approaches usually work well if (but only if) the communities are well separated. With the increase of inter-cluster edges, the performance of established approaches tends to decrease since they significantly hamper community separation. In addition, many connections in realworld networks are missing. Such problem, further aggravates the difficulty to find high-quality communities. Therefore, identifying inter-cluster edges and supplementing missing edges offer a promising way to enhance the performance of community detection and link prediction simultaneously.

In recent years, matrix completion becomes an important tool in machine learning, and has been extensively studied in recommender systems and computer vision [Liu et al., 2013; Natarajan and Dhillon, 2014; Kang et al., 2016]. Given an observed matrix A, matrix completion constructs a new matrix ˆ A that approximates A at its unobserved entries. Since there are infinite number of matrices that perfectly agree with the observed entries of A, some additional assumptions are usually imposed such as low-rank [Cand`es and Recht, 2009; Liu et al., 2013; Hastie et al., 2015; Yang et al., 2018] and sparsity [Lu et al., 2016; Fan and Chow, 2017].

Motivated by aforementioned problems and existing matrix completion techniques, in this paper, we propose a Cluster-driven Low-rank Matrix Completion, called CLMC, which aims to learn an ideal similarity matrix to perform graph clustering and a supplement matrix to conduct link prediction simultaneously in a unified framework. The basic idea of CLMC is to decompose the original data matrix into three additive matrices: the first corresponds to an ideal clustering matrix (Figure 1(b)), which is expected to be a block-diagonal matrix where the inter-cluster edges are removed and meanwhile, the missing or trend connections are supplemented in each community. The second corresponds to the inter-cluster edges, which is viewed as a noisy matrix (Figure 1(c)). The third one, called supplement matrix, is used to characterize the missing or trend connections (Figure 1(d)). With the resulting matrices, we can perform community detection on the clustering matrix, and, conduct link prediction with the supplement matrix.

CLMC has several attractive benefits, most importantly:

• Reciprocal Learning. Instead of treat community detection and link prediction as two separated problems, CLMC learns an ideal similarity matrix to perform graph clustering and a supplement matrix to conduct link prediction simultaneously. As a result, CLMC allows finding high-quality communities since the noisy connections are well filtered and the missing connections are supplemented. In return, the resulting good graph clustering further boosts the link prediction performance.
• Robustness: Since CLMC examines clustering part, noise part and missing part simultaneously, it is thus quite insensitive to noisy or missing edges.

2 Proposed Approach

2.1 Low-rankMatrix Completion

Given an observed matrix A, if the number of known entries in A is sufficiently large (i.e., p ≥ Crn6/5 log n) and the entries are uniformly distributed, we can complete the data matrix by solving the following optimization problem [Cand`es and Recht, 2009].

where ˆ A is the completed matrix, rank( ˆ A) is the rank of matrix ˆ A, and Ω is the set of indices of observed entries. Although the optimization problem is NP-hard, it can be approximated to optimize the nuclear norm [Cand`es and Recht, 2009; Keshavan et al., 2010] as follows.

where || · ||∗ denotes the nuclear norm of a matrix.

2.2 Cluster-driven Low-rankMatrix Completion

As aforementioned, the key idea of our algorithm is to learn an ideal clustering matrix by removing noisy edges and completing missing edges in each community. To this end, the observed data matrix A can be divided into three parts: clustering matrix, noise matrix and supplement matrix. Here, we borrow the idea from low-rank matrix completion to handle missing edges. However, since the low-rank assumption of the recovered matrix ˆ A may not hold in real-world applications, unlike existing approaches, we impose the low-rank constraint on the clustering matrix instead. As a result, we first formulate our objective function as follows.

Where ˆ C, ˆR andE are the clusteringmatrix, noisematrix and supplement matrix, respectively. πΩ : Rm×n → Rm×n is a linear operator that keeps the entries in Ω unchanged and sets those outside Ω zeroes.

Since we expect ˆ C to be an ideal block-diagonal matrix where the inter-cluster edges are removed, and meanwhile, the missing or trend connections are supplemented in each community, a cluster structure constraint needs to be added to make ˆ C have exactly k connected components, where k is the number of clusters. Let Lˆ C = D - ˆ C be the Laplacian matrix associated with ˆ C, and D is the diagonal matrix where the ii-th diagonal element is ∑j ˆ Cij. If ˆ C is non-negative, according to the property of Laplacian matrix, we have the following theorem [Mohar et al., 1991; Chung, 1997].

THEOREM 1 The number k of the eigenvalue 0 of the Laplacian matrix Lˆ C is equal to the number of connected components in the graph associated with ˆ C.

According to Theorem 1, the ideal clustering matrix can be obtained by imposing rank(Lˆ C ) = n - k constraint. Suppose that λi is the i-th smallest eigenvalue of Lˆ C , the constraint can be approximated to the following problem for a large positive value of α1.

When α1 is large enough, ∑ki=1 λi will be driven to be close to zero, which results in rank(Lˆ C ) = n - k. In addition, according to the Ky Fan's Theorem [Fan, 1949], we have

By adding the clustering constraint, our problem is further written as follows.

As for noise matrix, we assume that it is sparse and the ℓ1-norm constraint is imposed. As a result, we have our final objective function as follows.

2.3 Optimization

In the following, we will introduce an iterative strategy to solve our optimization problem.

Update F By fixing ˆ C, ˆR and E, the problem (7) is equivalent to optimizing the following objective function:

The optimal solution F to the problem is formed by the k eigenvectors of L ˆ C corresponding to the k smallest eigenvalues.

Update ˆ C, ˆR and E By fixing F, we can obtain ˆ C, ˆR and E by optimizing the following objective function.

Generally, it is a non-trivial task to obtain ˆ C directly. Therefore, we introduce an auxiliary variable Z, and optimize the following objective function.

where LZ is the Laplacian matrix of Z, LZ = DZ - Z.

By fixing the others, we can update ˆ C as follows. First, we introduce the partial augmented Lagrange multipliers and incorporate the equality constraints into the objective function, the problem is transformed as follows.

By fixing the others, we can update Z by optimizing the following objective function.

Since Eq.(12) is convex and smooth, the closed-form of Z can be derived as follows.

where fi is the i-th row of F ∈ Rn×k , and Hij = ||fi-fj ||2F . Since Z is non-negative, during the whole optimization process, Z keeps to be non-negative by Z = Z+, where Z+ is the positive part of Z, namely, Z+ = max(0, Z). This is the same to ˆ C and ˆR.

By fixing the others, we can update ˆ C by optimizing the following objective function.

Algorithm 1 Solving Problem (7)

• 1: Input: Data matrix A, parameters: α1, α2
• 2: Output: ˆ C, ˆR,E, F

• 3: Initialize Z = ˆ C = 0, ˆR = 0, Y 0 1 = 0, Y 0 2 = 0, µ = 10-6 , maxµ = 1010 , ρ = 1.5, ϵ = 10-8
• 4: while not converge do
• 5: Fix the others and update F by solving problem (8),

• 7: Fix the others and update Z by solving problem (12),

• 9: Fix the others and update ˆ C by solving problem (14),

• 11: Fix the others and update ˆR by solving the problem (17),

• 13: Fix the others and update E by solving problem (20),

• 15: Update the Lagrange multipliers

• 18: Update the parameter µ by µ =min(ρµ,maxµ)
• 19: Check the convergence conditions
• 20: ||A- ˆ C - ˆR-E||2F < ϵ and ||Z - ˆ C||2F < ϵ
• 21: end while

By further reformulating the equation (14), the problem is equivalent to optimizing the following well-known objective function [Cai et al., 2010].

According to the singular value thresholding (SVT) algorithm [Cai et al., 2010], we can obtain ˆ C as follows.

where the soft-thresholding operator Dµ is defined as Dµ(X) := UDµ(Σ)V T , Dµ(Σ) = diag(δi - µ)+.

By fixing the others, we can update ˆR by optimizing the following objective function.

The problem is equivalent to optimizing the following well-known objective function.

According to the shrinkage operator [Hale et al., 2007], we can obtain the ˆR as follows.

Algorithm 2 Clustering and Link Prediction via CLMC

• 1: Input: Data matrix A, α1, α2, number of clusters k
• 2: Obtain four matrices matrices, ˆ C, ˆR, E and F by solving Problem (7) via Algorithm 1.
• 3: Use k-means to cluster the affinity matrix F into k groups.
• 4: Construct the recovered data matrix ˆ A = A - E+ET 2 .
• 5: Perform link prediction with ˆ A.

where the shrinkage operator Sµ is defined as Sµ(X) := Xµsgn(X) + sgn(X) ⊙ [µ - |X|]+.

By fixing the others, we can update E by optimizing the following objective function.

To solve the problem, we can update E as follows.

Furthermore, the multipliers Y1 and Y2 are updated directly by

Finally, Algorithm 1 gives the pseudocode of solving Problem (7).

2.4 Graph Clustering and Link Prediction

After solving Problem (7), we can derive three matrices, including a clustering matrix ˆ C, a noise matrix ˆR and a completion matrix E, plus the clustering indicator matrix F . We utilize F as a similarity matrix, and then use the k-means algorithm to produce the final clustering results. Moreover, since E is a completion matrix, and we can use it to perform link prediction. Specifically, we can compute the completed matrix ˆ A = A - E+ET 2 . It is important to note that community detection and link prediction work on ˆ F and ˆ A, respectively, instead of the original data matrix A. Beyond, the two mining tasks are also mutually enhanced. On the one hand, with supplementing missing and/or trend edges while removing noisy edges, it makes clustering be more easy and effective. On the other hand, a good clustering will result in a better matrix completion to support link prediction. Finally, Algorithm 2 gives the pseudocode of graph clustering and link prediction via CLMC.

3 Experiment

We use ten publicly available real-world datasets to evaluate the performance of CLMC, including Karate, Football, Polbooks, Politics-ie, Olympics, Twitter, USAir, Celegans, PB and NS.

3.1 Proof of Concept

Here we start with several synthetic networks featuring distinct characteristics to prove the concept of CLMC. To make the synthetic networks to be more consistent with real-world networks, the LFR benchmark networks [Lancichinetti et al., 2008] have been applied, where the distributions of degree and community size of networks can be easily controlled.

Community Detection with Noise

First, we evaluate how well our clustering algorithm allows detecting communities by varying their inter-cluster edges. We fix node average degree and community size, and change the mixing parameter µ from 0.1 to 0.6 to generate a set of networks with different inter-cluster edges. µ is defined as the fraction of links of each node outside its community, which is used to control the difficulty of community separation. With the increase of mixing parameter, the performance (measured by NMI) of all eight approaches is shown in Figure 2. We can observe that CLMC, Attractor, Ncut and MCL almost achieve perfect clustering with the mixing parameter up to 0.5. The performance begins to decrease with more and more interedges added into the network, and CLMC tends to be more robust to these noisy edges. For Modularity, PIC and MCL, the performance is not comparable with other five algorithms on these networks.

Community Detection with Missing Edges

We further evaluate how the algorithms respond to networks with different average degrees, which can be regarded as missing edges in communities. Here we fix the inter-cluster edges, and change the average degree from 5 to 40, and examine the graph clustering performance. Figure 3 shows CLMC allows perfect clustering when the average degree

Mixing Parameter ranges from 15 to 40. For Spectral, Metis, FUSE and Modularity, they cannot produce promising results.

Figure 3: The performance of different algorithms on the LFR benchmark networks by varying community density using the average degree.

3.2 Community Detection Evaluation

Here, we compare CLMC to eight representatives of community detection algorithms: Ncut, Modularity, Metis, MCL, Spectral, PIC, FUSE and Attractor. Ncut [Shi and Malik, 2000] is a well-known algorithm for graph clustering by optimizing the normalized cut criterion. Modularity [Newman, 2006] is a popular community detection algorithm based on the modularity measure. Metis [Karypis and Kumar, 1998] is a typical clustering approach for large networks via multilevel partitioning and parallelized implementation. MCL [Van Dongen, 2000] is an algorithm widely used in life sciences based on the simulation of (stochastic) flow in graphs. Spectral is a typical clustering algorithm which allows finding arbitrarily shaped clusters [Lin and Cohen, 2010]. PIC is a power-iteration-based clustering method based on spectral clustering [Ng et al., 2002]. FUSE is a new spectral clustering approach by employing ensemble learning and ICA [Ye et al., 2016]. Attractor is a model-based community detection approach based on distance dynamics [Shao et al., 2015].

For all experiments, Ncut, Modularity, Metis, Spectral, PIC and FUSE specify the number of clusters (k = |C|), where |C| is the true number of classes. For MCL, we perform parameter tuning on the range (1.0, 4.0) with step size of 0.2.

For Attractor, the cohesion parameter varies from 0.1 to 1.0 with stepsize of 0.1. For CLMC, α1 takes the values from (0.001, 0.1, 1) and α2 takes the values from (0.1, 1, 10) . For all algorithms, the best results are recorded. In addition, since the performance of Spectral, PIC, FUSE and CLMC depend on the initialization with k-means clustering, we run them for 10 times, and the best results are reported. For networks whose communities are already known, the performance is measured by three widely used evaluation measures: Normalized Mutual Information (NMI) [Strehl and Ghosh, 2003], Adjusted Rand Index (ARI) [Rand, 1971] and Cluster Purity.

Table 1 summarizes the performance of different community detection algorithms on six real-world data sets. From the table, we can observe that CLMC achieves good performance on all data sets. On the Karate data, it even produces perfect clustering. The success of CLMC on community detection lies in the removal of noisy edges and the completion of missing/trend connections. Table 2 further reports the performance of different algorithms on the real-world data sets with 10% missing edges, and we can see that CLMC outperforms the state-of-the-art algorithms.

3.3 Link Prediction Evaluation

As an other function, CLMC also supports link prediction with the supplement matrix. Here we further evaluate its link prediction performance.

Here, we compare CLMC with sixteen link prediction algorithms, including neighor-based methods: common neighbors (CN), Jaccard, Hub Promoted Index (HPI), Hub Depressed Index (HDI), Leicht-Holme-Newman Index (LHN1 and LHN2), Adamic-Adar (AA), resource allocation (RA), preferential attachment (PA), path-based methods: Katz, local path index, average commute time (ACT), random walk with restart (RWR), transfer similarity (TS), SimRank, and latent-based method: matrix factorization (MF). For details, please refer to the link prediction survey paper [Mart´ınez et al., 2017]. For Katz, the damping factor is searched from 0.001 and 0.01. The free parameter φ is searched in {0.90, 0.95, 0.99}. For RWR, the probability parameter c is searched from 0.85 and 0.95. For MF, the number of latent factors is searched in {5, 10, 15, 20, 50}. The best results on all data sets are recorded. Moreover, the standard metric: the area under the ROC curve (AUC) [Hanley and McNeil, 1982], is used to measure the link prediction performance.

For all data sets, existing links are randomly split into: a training set (90%) and a test set (10%). After that, all link prediction approaches perform experiments on training test, and validate its performance on test set with AUC. Table 3 summarizes the link prediction performances of different algorithms on ten data sets with 10% missing connections. From Table 3, we can observe that CLMC shows its superiority over all comparing link prediction algorithms. The potential reason is that the community detection and link prediction are mutually enhanced. The clustering constraint will make more intra-connections to be supplemented.

3.4 Parameter Analysis

For CLMC, it involves two parameters α1 and α2. Figure 4 shows the different community detection performance by varying the values of α1 and α2. From the figure, we can see that CLMC can achieve a relatively stable good performance (indicating by the yellow blocks) when α1 ranges from 0.001 to 1, and α2 ranges from 0.01 to 10 on the four data sets.

4 Conclusions

In this paper, we consider community detection and link prediction simultaneously in a unified framework with clusterdriven low-rank matrix completion. Instead of working on the original network directly, the proposed framework learns a new ideal clustering matrix to perform graph clustering and a supplement matrix to conduct link prediction. Experimental results show that the proposed CLMC achieves better results on both tasks of community detection and link prediction over many state-of-the-art approaches.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (61403062, 61433014, 41601025), ScienceTechnology Foundation for Young Scientist of Sichuan Province (2016JQ0007), Fok Ying-Tong Education Foundation for Young Teachers in the Higher Education Institutions of China (161062) and National key research and development program (2016YFB0502300).