Noise-Resilient Similarity Preserving Network Embedding for Social Networks

1 Introduction

Network embedding is an important method to learn lowdimensional representations of a network through the study of its high-dimensional representation, while preserving the network's structure and its inherent properties. Based on network embedding, mining information in networks, such as link prediction [Yu et al., 2017], classification [Liu et al., 2017], and network visualization [Tang et al., 2015], can be directly conducted in the low-dimensional space.

Given a network G = (V,E), the network embedding is a mapping f = vi → yi ∈ Rd . The function f maps each node vi in the node set V to d-dimensional space [Goyal and Ferrara, 2018]. Various methods of network embedding have been proposed [Cui et al., 2017] and many network properties such as first-order proximity [Wang et al., 2016], high-order proximity [Zhu et al., 2018], and social community [Zhang et al., 2018] have been considered. Essentially, most of methods didn't consider network noise. However, the observed data always contains noise. That is, false links always exist in observed network data and many actual links are missing during network observation. We call this problem network embedding with noise. The noise in the network will affect the performance of network embedding dramatically. Fig. 1 presents an example to illustrate the incorrect embedding of a network due to noise.

∗Corresponding Author

To some extent, the effect of network noise can be reduced and the actual network structure can be recovered by node similarity. In Fig. 1 (a), according to the common neighbor (CN) index method [Liben-Nowell and Kleinberg, 2007], nodes 1 and 2 have high similarity because they share many common neighbors, thus there is a high probability that a link exists between nodes 1 and 2. On the contrary, the probability of the existence of a link between nodes 1 and 3 is low because they have low similarity according to the CN index. As a result, the false link and the missing link in Fig. 1 (a) can be detected by node similarity. Intuitively, we aim to exploit node similarity to quantify the authenticity of the observed network structure and reduce network noise. The greater the similarity between two nodes, the higher the authenticity of the link between them; therefore, they should be represented closely to each other, and vice versa.

In this paper, we propose a node similarity preserving (NSP) embedding method to reduce the influence of network noise through the analysis of node similarity. In general, node similarity is quantified by a single similarity index, and many such indices have been proposed [Hu et al., 2017]. However, existing single indices cannot fully describe node similarity in complex real-world social networks [Wang et al., 2017a]. In view of this, we propose a comprehensive similarity index to quantify node similarity accurately. For a given network, a similarity matrix is constructed from the adjacency matrix by using the comprehensive similarity index. Then we propose a correction matrix that can reduce the noise in the adjacency matrix by the analysis of the similarity matrix. Finally, we formulate an objective function for accurate network embedding and propose an efficient algorithm based on interactive search to solve the optimization problem. As a result, the learned network representation can preserve the actual network structure well. The contributions of this paper can be summarized as follows:

• We propose a comprehensive similarity index to measure node similarity and compute a node similarity matrix. Compared to existing single similarity indices, the proposed index is more accurate.
• We propose an algorithm to construct a correction matrix to reduce the influence of noise on a given network and recover the actual network structure.
• We formulate an objective function for accurate network embedding by introducing a weight matrix and a penalty function. We also propose an efficient algorithm to solve the optimization problem of network embedding.

2 RelatedWork

Various methods of network embedding have been proposed in the literature. For example, DeepWalk [Perozzi et al., 2014] aims to preserve the neighbor structure of nodes and uses the SkipGram model to learn the representations of nodes. Node2Vec [Grover and Leskovec, 2016] is able to learn the representations that closely embed nodes that belong to the same network community. LINE [Tang et al., 2015] is intended for large-scale network embedding, and can preserve both first-order and second-order proximities. Community structure is also an important property in network representation. [Wang et al., 2017c] propose a modularized nonnegative matrix factorization (M-NMF) model for network embedding that preserves both the microscopic structure and the mesoscopic (community) structure. In addition, some other network properties such as non-transitivity [Ou et al., 2015], asymmetric transitivity [Ou et al., 2016], node side information [Yang et al., 2015], and structure balance [Wang et al., 2017b] have been embedded into representation vectors. Despite the success of these network embedding approaches, they all assume that there is no noise in the observed network data. Therefore, a method to reduce the influence of noise is still lacking.

3 ProblemDefinition

A social network is defined as G = (V,E), where V = {v1, ..., vn} is the node set and E = {e1, ..., em} is the link set. The adjacency matrix is denoted as A ∈ Rn×n , where Ai,j ∈ [0, 1] is the link weight between nodes vi and vj. The value of Ai,j represents the connection strength between nodes vi and vj. If there is no link between vi and vj, then Ai,j = 0. Our task is to find an approach to reduce the influence of noise and embed each node in V into a point in the embedding space. Let S ∈ Rn×n denote the node similarity matrix: Si,j ≥ 0 denotes the similarity between vi and vj. Let C ∈ Rn×n denote the correction matrix. Let U ∈ Rn×d denote the embedding matrix. The i-th row of U, Ui,∗, is the embedding vector of vi. We first need to derive S from A by using a comprehensive similarity index, so that S can preserve the accurate similarity between nodes. Since A contains noise, we need to compute C based on S and A for noise reduction. Finally, we compute U, such that the learned representations can preserve the actual network structure.

4 Node Similarity Preserving Embedding

The NSP method has three modules: 1) node similarity construction, which generates a comprehensive similarity index to evaluate node similarity and constructs the node similarity matrix S; 2) after node similarity constriction, a noise reduction module is proposed, which computes a correction matrix C based on S to reduce network noise; 3) finally, a node similarity embedding module is proposed, which formulates an objective function for accurate network embedding by approximating the S and C, and proposes an efficient algorithm to solve the optimization problem.

4.1 Node Similarity Construction

Node similarity is an important measurement to quantify the strength of node relationship and is used to predict links between nodes [Yu et al., 2017]. In general, node similarity is quantified by a similarity index. Most similarity indices are derived from specific evolution mechanisms. However, realworld networks are dynamic and jointly driven by a hybrid mechanism [Zhang et al., 2014]. A single index cannot fully describe the node similarity. To evaluate node similarity accurately, we propose a comprehensive similarity index S that considers multiple single similarity indices. The definition of S is as follows:

Definition 1. (Similarity index vector). The similarity index vector Sv = {s1, ..., si, ..., sγ} is a vector consisting of γ single similarity indices. For example, si could be the CN index. For any node pair {vi, vj}, the similarity index vector is Sv(vi, vj) = {s1(vi, vj), ..., sγ(vi, vj)}.

Since each single similarity index si in Sv plays different weight in the overall similarity measurement, we introduce a weight vector for Sv.

Definition 2. (Similarity index weight). The similarity index weight φ = {ϕ1, ..., ϕi, ..., ϕγ} is the weight vector of Sv. ϕi denotes the weight of index si in Sv.

Definition 3. (Comprehensive similarity index). Given Sv and φ, the comprehensive similarity index S(vi, vj) between nodes vi and vj is defined as:

where min(sk) is the minimum sk value of all node pairs in the network, and max(sk) is the maximum value.

A real-world social network is driven by a hybrid mechanism. Experimental analysis in [Zhang et al., 2014] indicates that the relative contribution of each mechanism varies in the evolution of different social networks. While a single similarity index si is derived from a specific evolution mechanism. When a similarity index is consistent with the network evolution mechanism, the index will provide accurate node similarity evaluation [Hu et al., 2017]. Therefore, to make the comprehensive similarity index S more consistent with the hybrid network evolution mechanism, we need to determine the optimal weight value of each single similarity index si in Sv. A φ whose corresponding S achieves the most accurate node similarity evaluation is defined as the optimal index weight, φ∗ . For a given social network, we need to optimize the φ∗ to evaluate node similarity accurately.

Note that the Sv can include any existing single similarity index. To enable the S to be applied to large-scale networks, a sampling step is included in NSP. In detail, the node similarity construction phase consists of the following two steps:

Step1: Network Sampling

We sample from the original network with the alias method [Li et al., 2014] according to the link weights, and treat the sampled links as binary links. The sampling is conducted by the following steps.

1. Initialize the sampled networkG′ = (V ′ ,E′ ), where v′ ⊂ V , E′ ⊂ E.
2. According to the link weights, sample a link ei from G by the alias method [Li et al., 2014]. If ei is in E′ , then discard it, else set the weight of ei to 1 and add ei to E′ . For the nodes vi, vj linked by ei, if they do not exist in V ′ , then add them to V ′ .
3. Repeat 2) until |E′ | =K. K is a control parameter of the sampled network size.

Step2: Searching For Optimal Index Weight

After the network sampling, we need to search the optimal φ∗ according to the obtained G′ .

A good similarity index should provide accurate link prediction [Hu et al., 2017]. To search for the optimal φ∗ , we adopt the AUC [Hu et al., 2017] as the metric of prediction accuracy. Let AUC(φ) denote the prediction accuracy of the S corresponding to the φ. The problem turns into searching for the φ∗ such that the corresponding AUC(φ∗ ) is maximized. Since this is a random search problem, we use the quantum-behaved particle swarm optimization method (QPSO) [Tang et al., 2014] to search φ∗ .

Once the S is determined by φ∗ for the given network G′ , we can calculate the Si,j for each node pair {vi, vj} in G to construct the node similarity matrix S.

4.2 Noise Reduction

In this section, we introduce how to construct the correction matrix C based on S to reduce the noise in A. According to the experimental analysis in [Lu and Zhou, 2010], two nodes are more likely to be connected if they have high similarity. Inspired by this conclusion, we use the matrix S as a metric to

Algorithm 1 Construct Correction Matrix

Input: adjacency matrix A, similarity matrix S. Output: correction matrix C.

• 1: Initialize correction matrix C;
• 2: if Ai,j > 0 and Si,j < avg(S) ×α then
• 3: calculate Ci,j by Equation (2);
• 4: else if Ai,j = 0 and Si,j ≥ avg(S) × (α+1) then
• 5: calculate Ci,j by Equation (3);
• 6: else
• 7: Ci,j =Ai,j;
• 8: end if
• 9: return C.

evaluate the confidence level of the observed A, and propose the construct correction matrix (CCM) algorithm to compute the matrix C to reduce network noise.

There are two types of network noise: false links and missing links. The CCM algorithm checks the node similarity Si,j and link weight Ai,j of each node pair {vi, vj} to detect these two types of noise, and computes the Ci,j to reduce them.

In terms of false links, if Ai,j > 0 and Si,j < avg(S)×α, where avg(S) is the average of all the elements in S and α is a threshold parameter such that 0 < α < 1, this means that there is a link between vi and vj in the observed network but their similarity Si,j is very small. In this case, we regard this link as a false link. To reduce the influence of such false links, we need to reduce the original Ai,j to reflect the actual connection strength. Thus, the value of Ci,j is defined as follows:

On the contrary, if Ai,j = 0 and Ai,j ≥ avg(S)×(α+1), this means that there is no link between vi and vj in the observed network but the similarity Si,j is large enough. In this case, we believe that there is a link between vi and vj in the actual network, but it has been lost in the observation process. In this case, we need to increase the Ai,j to compensate for the missing link. Therefore, the value of Ci,j is defined as follows:

Finally, the CCM algorithm is detailed in Algorithm 1.

4.3 Node Similarity Preserving Embedding

After obtaining the correction matrix C, we now construct the network embedding matrix U. The C is derived from A after a noise reduction process, which is the most direct expression of network. To make the embedding matrix U preserve the actual node relationship in the embedding space, we introduce a non-negative basis matrix M ∈ Rn×d according to the non-negative decomposition [Lee and Seung, 2000]. Then we expect to make M times U to be as close as possible to C, which leads to the following objective function:

Because of the sparsity of real-world networks, the number of zero elements in C is far greater than the number of non-zero elements. This makes the learned U more prone to reconstruct the zero elements. Inspired by [Wang et al., 2016], we add a greater penalty to the reconstruction error of the non-zero elements than to that of the zero elements. For this purpose, we add a weight matrix W ∈ Rn×n to Equation (4). Specifically, if Ci,j = 0, Wi,j = 1, else Wi,j = θ > 1. The revised objective function is as follows:

where ⊙ means the Hadamard product.

To further reduce the impact of noise, we add a penalty function to the objective function (5). Since the matrix S accurately evaluates node similarity, it is well-suited for this purpose. We adopt the theory of Laplacian Eigenmaps [Belkin and Niyogi, 2003], which adds a penalty when similar nodes are mapped far apart in the embedding space. Let ||Ui,∗ -Uj,∗||2 denote the distance between nodes vi and vj in the embedding space. The penalty function is as follows:

Based on Laplacian Eigenmaps, we can reformulate Equation (6) to the following objective function:

where Laplacian L = D - S and D is a diagonal matrix with the sum of each row of S on its diagonal, and tr(X) is the trace of matrix X.

Finally, the actual network structure can be preserved by combining Equations (5) and (7) and jointly minimizing the following objective function:

Because the objective function (8) is not convex, it is impossible to give closed-form solutions. Inspired by [Wang et al., 2017c], we propose an algorithm to find an approximate solution. Our method iteratively updates U and M until the function (8) converges. The updating steps for U and M are as follows.

Update M: When matrix U is fixed during the update process of M, Equation (8) can be revised to

[Wang et al., 2017c], the updating of M can be obtained as:

Update U: When matrix M is fixed during the update process of U, the Lagrange multiplier matrix ψ = [ψi,j ] is introduced to guarantee that U is nonnegative. Then Equation (8) is equivalent to:

Setting derivatives of L(U), with respect to U, to 0, we have:

Following the Karush-Kuhn-Tucker (KKT) [Wang et al., 2017c] condition for the nonnegativity of U, we have the following equation:

This equation leads to the following updating formula:

To prove the convergence of the updating rule (13), we introduce an auxiliary function as in [Lee and Seung, 2000]. The definition of the auxiliary function is as follows.

Definition 4. A function V (x, x′ ) is an auxiliary function of function F (x) where V (x, x′ ) ≥ F (x) and V (x, x) = F (x) for any x, x′ .

Based on the auxiliary function, [Lee and Seung, 2000] proposed the following lemma.

Lemma 1. If V is an auxiliary function of F, then F is nonincreasing under the updating rule:

Let Fi,j denote the part of objective function (10) which is only relevant to Ui,j . Then we have:

Now we propose a specific auxiliary function V (x, x′ ) for Fi,j based on Lemma 2.

Lemma 2. The function

(17)

is an auxiliary function for Fi,j .

Proof. It is obvious that Fi,j(Ui,j) = V (Ui,j,Ui,j), so we need to prove V (Ui,j , U(t) i,j ) ≥ Fi,j(Ui,j). The Taylor series expansion of Fi,j(Ui,j) at U(t) i,j is

Compared to Equation (17), we need to prove that

We have

Therefore, Equation (19) is proved.

Based on Lemmas 1 and 2, we can show the convergence of the update rule (13).

Theorem 1. The objective function (10) is nonincreasing under the update rule of Equation (13) for U.

Proof. According to Lemma 2, V (Ui,j,U(t) i,j ) in Equation (17) is an auxiliary function of Fi,j. Replacing the V (Ui,j , U(t) i,j ) in Equation (14) by Equation (17), we have the following update rule:

which is the same as (13). Following Lemma 1, under this update rule, the objective function (10) will be nonincreasing.

Finally, the objective function (8) can be achieved by updating M and U in Equations (9) and (13), respectively. The complexity of the updating rules in (9) and (13) is O(n2d + nd2 ), since n ≫ d, so the overall complexity of the update rules of NSP is O(n2d).

5 Experimental Evaluation

In this section, we conduct experiments to validate the effectiveness of NSP on several real-world applications: node classification, node clustering, and link prediction. We evaluated the method on four social networks. 1) BlogCatalog is a network of social relationships of bloggers listed on the BlogCatalog website (10312 nodes, 333983 links, and 39 different labels). 2) Cora is a citation network of scientific publications (2708 nodes, 5278 links, and 7 different labels). 3) EmailEu is an email network of a large European research institution (1005 nodes, 25571 links, and 42 different labels). 4) Polblogs is a blog network about US politics recorded in 2005 (1490 nodes, 16715 links, and 2 different labels).

The following five network embedding algorithms are used in our experiments for comparison: DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], Node2vec [Grover and Leskovec, 2016], M-NMF [Wang et al., 2017c], and GraRep [Cao et al., 2015]. The parameters of the comparison algorithms are set to their default values, and the parameters of NSP are tuned by using grid search on the validation set. The Sv of NSP is consists of two local similarity indexes CN and AA, and two global similarity indexes KI and SimRank [Lu and Zhou, 2010]. We uniformly set the representation dimension d = 128.

5.1 Node Classification

This section presents the performance of all algorithms on the node classification task with varying proportions of noise in the network datasets. Let R denote the proportion of noise added. We first delete |E|/R links from the experimental network, to simulate the missing links, and then we randomly add |E|/R links to the network to simulate false links. For node classification, the learned representations of nodes are used to classify these nodes into a set of labels. Following [Wang et al., 2017c], we used the KNN algorithm to train the classifiers. For each class of a given network, we randomly selected 80% of the nodes as the training nodes and the rest as the testing nodes. The prediction accuracy is used as the evaluation metric.

As illustrated in Fig. 2, in these four networks, the classification accuracy of all algorithms decreases with the increase of noise ratio R, especially in the Cora and Polblogs networks. This is because the network noise disturbs the network structure and leads to inferior performance in all of the algorithms. In the absence of artificial noise (R = 0), the accuracy of NSP is similar to the optimal results in BlogCatalog, Cora, and Polblogs, while NSP achieves the best accuracy in EmailEu. With increased network noise, R ∈ [5%, 20%], the advantage of NSP becomes increasingly apparent: when R > 5%, NSP outperforms other algorithms in all networks; when R = 20%, the accuracy of NSP is about 5% - 15%

in BlogCatalog, Cora, and Polblogs. This is because NSP adopts more node similarity measures; hence, it is more effective in eliminating part of the noise.

5.2 Node Clustering

In this section, we evaluate the performance of all algorithms on the node clustering task. Following [Wang et al., 2017c], we adopt the K-means algorithm in this experiment to perform the node clustering and use normalized mutual information (NMI) [Goyal and Ferrara, 2018] for evaluating the clustering results. Since K-means is sensitive to the initialization of the centroids, we adopt k-means++ [Bachem et al., 2016] for centroids initialization and run each clustering 10 times.

As we can see, the NMI of all algorithms decreases as the noise rate R increases in these four networks, just like the results in Section 5.1. This again suggests that the existence of noise has a significant impact on the effectiveness of embedding algorithms. By considering the node similarity, NSP has a stronger noise tolerance than the other algorithms. NSP outperforms the other algorithms when R > 5% in the BlogCatalog, Cora, and EmailEu networks. Although the NMI of NSP is not the largest in the Polblogs network, its rate of decline is the smallest. When R increases from 0% to 20%, the NMI of NSP only decreases about 0.04 in Polblogs, in contrast to M-NMF (decreases 0.12), Node2vec (0.14), and LINE (0.15). These results again show the advantages of introducing node similarity to network embedding.

5.3 Link Prediction

In this section, we concentrate on the link prediction task and experiment on the BlogCatalog and EmailEu networks. In the link prediction task, for each dataset we first randomly hide 20% of the network links and learn the embedding using the remaining 80% of the links, to predict from the learned embedding the most likely links that are not observed in the training data. The precision@k [Goyal and Ferrara, 2018] is adopted as the evaluation metric of predicting the hidden links. The results of all embedding algorithms on BlogCatalog and EmailEu are presented in Tables 1 and 2.

The results in the BlogCatalog and EmailEu networks show that as k increases, the performance of our method is consistently better than other network embedding algorithms, especially in the EmailEu network. (When k = 1000, the precision of NSP is still greater than 0.8, while other competitors are all less than 0.8.) This is because the idea of NSP preserves the node similarity quantified by the hybrid similarity index in the network embedding process, thereby giving NSP better link prediction power.

6 Conclusion

We propose the node similarity preserving (NSP) method in this paper to perform network embedding for social networks with noise. NSP uses a comprehensive similarity index to construct the node similarity matrix S. S can quantify the credibility of the observed network structure. Based on S, we obtain a corrected matrix C, which has reduced noise. NSP also includes a objective function that preserves the constructed node similarity S and the corrected network structure C. Finally, efficient updating rules, with correctness and convergence guarantees, are also provided in NSP. Comprehensive experiments comparing NSP with state-of-the-art approaches on four real-world social networks demonstrated the substantial gains of the proposed method for node classification, node clustering, and link prediction tasks.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (No. 61572369), in part by the Key Projects of Guangdong Natural Science Foundation (No. 2018B030311003).