MASTER: across Multiple social networks, integrate Attribute and STructure Embedding for Reconciliation

1 Introduction

Nowadays, social network is becoming increasingly important in people's lives. People often have several social network accounts, e.g., Twitter for news, Facebook for friends and LinkedIn for jobs. However, these accounts are often independent from each other. It arises the problem of identifying the corresponding accounts belonging to the same individual, which is termed as reconciling social networks. Reconciling social networks can support a wide range of applications, e.g., network fusion [Zhang and Yu, 2016], link prediction [Zhang et al., 2017b] and cross-domain recommendation [Man et al., 2017].

This problem still remains open as most of the existing methods have several limitations as follows:

• Multiplicity: In real world, people usually have several social network accounts. However, most of the existing methods [Kong et al., 2013; Liu et al., 2014; Korula and Lattanzi, 2014; Liu et al., 2016; Man et al., 2016] focus on reconciling only two social networks and cannot pairwise reconcile multiple social networks due to the global inconsistency.

∗Corresponding Author

• Comprehensiveness: Social networks usually have two categories of spaces, i.e., attribute space and structure space. However, most of existing methods [Korula and Lattanzi, 2014; Liu et al., 2016; Man et al., 2016; Mu et al., 2016] do not comprehensively exploit the information of both spaces to reconcile social networks.
• Robustness: The social network is noisy and most of the existing methods [Zafarani and Liu, 2013; Kong et al., 2013; Liu et al., 2014; Zhang et al., 2015] struggle in defining effective features sensitive to data. Therefore, they are still away from robustly reconciling networks.

These limitations motivate us to rethink: Can we comprehensively and robustly reconcile multiple social networks?

The answer is YES! In this paper, for the first time, we propose the MASTER framework, i.e., across Multiple social networks, integrate Attribute and STructure Embedding for Reconciliation. In this framework, there are two main challenges: (1) Modeling: To the best of our knowledge, there is no embedding model reconciling multiple social networks in the literatures. Both spaces of multiple networks should be integrated and, moreover, the problem of global inconsistency is to be addressed in the embedding. (2) Optimizing: The network embedding problem is often formulated as an optimization problem. In our framework, the optimization problem behind tends to be non-convex and hence much tougher.

To address the issue (1), we design a novel Constrained Dual Embedding (CDE) model to formulate the reconciling social network problem. The core idea of CDE is to simultaneously embed and reconcile multiple social networks in the joint latent space via uni- and joint-embedding. For uniembedding, we perform collaborative matrix factorization to independently embed each network into a latent space, which collaboratively captures the observations of attribute space and structure space. For joint-embedding, we align these embedded social networks at the known correspondences to construct the joint latent space for consistent reconciliation and we finally give the formulation of the unified optimization.

To address the issue (2), we design an effective NSAlternating algorithm to approach the optima of the highorder matrix optimization. Specifically, we first reformulate the optimization problem, inspired by a recent advance in computational mathematics. We then alternately solve the representation matrices subproblem and the kernel matrices subproblem of the reformulated problem via first-order method and semidefinite programming, respectively. Moreover, we make analysis of the convergence property in depth and give the sufficient condition of Karush-Kuhn-Tucker (KKT) convergence.

We validate MASTER through extensive experiments on real-world datasets and show that MASTER outperforms several state-of-the-art methods.

To summarize, we make the following contributions:

• To the best of our knowledge, our proposed MASTER is the first attempt to robustly reconcile multiple social networks comprehensively exploiting attribute and structure information via an embedding approach.
• We design a novel model (CDE) to formulate the problem of reconciliation into a unified optimization.
• We design an effective NS-Alternating algorithm to address the optimization and prove that it converges to KKT points.
• We conducted extensive experiments on real-world datasets and the experiment results demonstrate the superiority of our approach.

2 ProblemDefinition

In this paper, we consider a set of M social networks {S(m) }. A social network S(m) of N (m) users is denoted as (G(m) ,A(m) ). The adjacency matrix G(m) ∈ RN (m)×N (m) represents the structure space, where binary G(m) ij indicates whether or not a social connection exists between user account v(m) i and v(m) j . G(m) is symmetric as the network is considered to be undirected. A(m) ∈ RN (m)×l represents the attribute space and its ith row a(m) i denotes the l-dimensional attribute vector associated with v(m) i . Part of the user account correspondences can be obtained from user profiles or some third-party platforms. Such information is represented in a label set ˆL = {L(m, n)}, where L(m, n) is the set of known account pairs between S(m) and S(n) of the same individual.

Without loss of generality, we assume that social networks are partially overlapped. We formally define the problem of reconciling multiple social networks as follows:

ProblemDefinition. Given the set {S(m) } with labels ˆL, the problem of reconciling multiple social networks is to find a φ(m) , mapping the user account to its owner, for each S(m) so that φ(1) (v(1) (·) ) = ... = φ(m) (v(m) (·) ) = ... = φ(M) (v(M) (·) ) to identify correspondences of shared users.

To address this problem, we propose the MASTER framework. In MASTER, we design a novel model, Constrained Dual Embedding (CDE), to formulate the problem into a unified optimization (Section 3). To address the optimization, we design an effective NS-Alternating algorithm (Section 4).

3 Modeling: Constrained Dual Embedding

In CDE, we independently embed each social network via uni-embedding and simultaneously reconcile these embedded networks via joint-embedding.

3.1 Uni-embedding

The goal of uni-embedding is, for each social network S(m) , to obtain the representation matrix H(m) ∈ RN (m)×d (d ≪ min{N (m) }), whose ith row h(m) i is the d-dimensional vector of v(m) i in the latent space, capturing the observations of both structure and attribute space.

To achieve this goal, first, we construct the similarity matrix M(m) of structure space. Note that G(m) ij encodes the first-order proximity, defined in [Tang et al., 2015], which is measured by whether or not v(m) i and v(m) j have a direct connection. Obviously, it is necessary to preserve the first-order proximity as it depicts the original structure of the social network. However, the observed edges are usually sparse in the network. For two user accounts with no direct connection, an alternative way to imply the proximity is to measure their neighbors. Intuitively, the more similar their neighbors are, the higher proximity they share. Therefore, we formally define the second-order proximity as follows:

Definition (second-order proximity). Given the adjacency matrix (or first-order proximity matrix) G(m) , the secondorder proximity ¯G(m) ij between v(m) i and v(m) j is the similarity of G(m) i and G(m) j , where G(m) i is the ith row of G(m) .

The inner product similarity is into account in this paper, i.e., ¯G(m) = G(m) 2 as G(m) is symmetric. To incorporate the first- and second-order proximity, M(m) = G(m) + η ¯G(m) where η is a non-negative weight.

Second, we derive the similarity matrixW(m) of attribute space by computing the pairwise inner product of the attribute vector, i.e.,W(m) =A(m)A(m) T .

Finally, we approximate the pairwise similarity in each space by the inner product of h(m) i . Assume that h(m) i is projected onto structure space and attribute space via different projection ϕ(.). We introduce kernel technique to bridge the inner product 〈·, ·〉 of the ϕ(h(m) i ) with that of h(m) i , i.e., 〈ϕ(h(m) i ), ϕ(h(m) j )〉 = h(m) i K(m) ϕ h(m) j , where K(m) ϕ is semidefinite. Let B(m) and C(m) denote K(m) ϕ of the projection onto structure space and attribute space respectively. H(m) can be learned by the optimization of a collaborative matrix factorization as below:

where ||·||F is Frobenius norm, Sd+ denotes semidefinite cone, and α and β are positive parameters weighting the observed similarities in structure space and attribute space respectively.

Take Fig. 1 for example. For each social network, e.g., S(1) , we first calculate the similarity matrices M(1) and W(1) . Then, we perform the collaborative matrix factorization in optimization (1) to embed S(1) into a latent space, represented by H(1) . In the latent space, h(1) b will be closer to h(1) a than h(1) c , and h(1) a and h(1) c are far away.

3.2 Joint-embedding

Based on uni-embedding, joint-embedding aims to construct the joint latent space by aligning latent spaces of S(m) at the known correspondences ˆL so that (1) the h(·) l of the correspondences coincides in the joint latent space and (2) the proximity of both structure and attribute spaces within the individual networks is captured in h(m) (·) .

To achieve the first goal, we leverage natural constraints to encode the correspondences and thus force alignment. To give its matrix form, we introduce an elementary matrix E(m) for each social network S(m) . Each row of E(m) has only one non-zero element (i.e., 1), to select a h(m) (·) according to the correspondences in L(m, n). We obtain the constraints as follows:

where E(m) ∈ R|L(m,n)|×N (m) and E(n) ∈ R|L(m,n)|×N (n) . This is an equation system of | ˆL| = M · (M - 1) equations.

We further formulate the equation system into a unified equation pair, despite of the number of networks M. First, we define rotating matrices ˜Dp and ˜Dq. If M is odd,

otherwise,

where D = [ I I ] and I is the identity matrix. Second,

we let Rp(X) = ˜DpX˜Dp and Rq(X) = ˜DqX˜Dq for rotating operation. Let ˜ denote the block diagonal matrix, i.e.,

˜X = diag({X(m) }). We obtain the equivalent equation pair:

To achieve the second goal, similarly, we incorporate uniembedding preserving the proximity within each network. Utilizing ∑i ||X||2F = || ˜X||2F , we obtain the unified objective, which is equivalent to combining M objectives of uniembedding, as follows:

Note that, ˜Band ˜C inherit the semi-definiteness while ˜Mand ˜W remain to be symmetric.

Finally, we remove the constraint by adding penalty with a coefficient γ and obtain the unified optimization objective:

Recall the example in Fig. 1. In this example, since the correspondence {v(1) b , v(2) b , v(3) b } is known in advance, we will force h(1) b = h(2) b = h(3) b to align the embedded space of S(1) , S(2) and S(3) . Those who are close in the joint latent space from different S(·) are regarded as good candidates.

The benefits of CDE model are two-folded: (1) both spaces are comprehensively exploited and (2) the problem of reconciliation is formulated in a unified approach for effective reconciliation, regardless of the number of networks.

4 Optimization: NS-Alternating

To address the optimization problem of the CDE model, inspired by Non-convex Spiting framework [Lu et al., 2017], we design an effective NS-Alternating algorithm. In this algorithm, we first reformulate the problem (6) and alternately solve the subproblems of the reformulation.

4.1 ProblemReformulation

The high-order objective (6) is not jointly convex over ˜H, ˜B and ˜C. Therefore, we reduce the order by introducing an auxiliary matrix V = ˜H, and formulate the problem as follows:

According to the study [Vandaele et al., 2016], problem (6) is equivalent to problem (7) in the sense of KKT points if τ = √C is sufficiently large (C = max{|| ˜M||2F , || ˜W||2F } in our algorithm). That is, the KKT points of problem (6) and problem (7) have a one-to-one correspondence.

We alternately solve ( ˜H,V) and ( ˜B, ˜C) of problem (7), referred to as representation matrices subproblem and kernel matrices subproblem respectively.

4.2 RepresentationMatrix Subproblem

Fixing kernel matrices, the updating rules are given below:

L( ˜H,V;Λ) is the augmented Lagrangian. Note that, proximal term ||V-V(t) ||2F and penalty parameter ξ (t) are added according to the study [Lu et al., 2017]. The optimization w.r.t. V can be decomposed into k separable problems, each of which can be solved using gradient projection:

where r denotes the inner-iteration number, λ denotes the step size and V[i] denotes the ith column of matrix V. For a given vector w, projV(·) projects it onto the feasible set of V[i]. ˜H can be solved via 1st -order method, whose gradient is:

4.3 Kernel Matrix Subproblem

Utilizing ||X||2F = tr(XT X), we reformulate the optimization w.r.t. B into an inner-product form ( ˜C-subproblem is the same as ˜B-subproblem, and omitted due to the space limit):

whereQ( ˜B) =VT V˜B˜HT ˜HandA=VT ˜M˜H. The equality constraint ˜H = V holds when representation matrix subproblem converges. Let ˜HT ˜H = P and we further analyze Q. For arbitrary X,Y, the following equations hold:

That is, Q is semidefinite (Eq. 19) and self-adjoint (Eq. 20). According to the study [Toh, 2008], we conclude that:

Theorem 1. ˜B-subproblem ( ˜C-subproblem) is a convex Quadratic Semi-Definite Programming (QSDP) problem with Q of PXP form and has the solution of the global optima with quadratic convergence rate.

We summarize the overall process of NS-Alternating in Algo. 1, where line 4 and line 5 refer to representation matrix subproblem and kernel matrix subproblem respectively. Recall our example. Optimizing via the Algo. 1, we obtain h(1) (·) , h(2) (·) and h(3) (·) and then, ∀i, j ∈ {1, 2, 3} (i ̸= j), we calculate ||h(i) (·) -h(j) (·) ||2F to identify the candidates for correspondence.

Algorithm 1: NS-Alternating

Input: observed {G(·) ,A(·) } of S(·) and ˆL Output: H(·) for each S(·) of the joint latent space 1 Compute ˜M, ˜W, {˜E(·,·) }; 2 Initialize ˜H(0) ,V(0) = ˜H(0) , ˜B(0) , ˜C(0) , n = 0; 3 while not converge do 4 ( ˜H,V)(n+1) = argmin l( ˜H,V, ˜B(n+1) , ˜C(n+1) ); 5 ( ˜B, ˜C)(n+1) = argmin˜B, ˜C∈SMd + l( ˜H(n) ,V(n) , ˜B, ˜C); 6 n = n+1; 7 end 8 return {H(·) } from ˜H;

4.4 Convergence and Complexity Analysis

Convergence Analysis: Utilizing the convergence properties [Hong et al., 2016], we can conclude that:

Theorem 2. With given ˜B and ˜C, if ρ > max{ρ1, ρ2, ρ3}:

We can claim that:

• The equality constraint on the auxiliary matrix is satisfied in the limit, i.e., limt→∞|| ˜H(t) -V(t) ||2F = 0.
• The sequence { ˜H(t) ,V(t) ,Λ(t) } generated by the NSAlternating algorithm is bounded, and every limit point of the sequence is a KKT point of problem (6).

The detailed proof can be found at the website. 1

Computational Complexity: The outer loop of Algo 1 (line 3-7) achieves the satisfactory accuracy in a few iterations. Note that, ˜B and ˜C of convex QSDP, blocks H(·) of ˜H and columns of V can be computed in parallel. Therefore, the computational complexity depends on matrix operations in updating rules. The inversions in QSDP is O(d3 ) and matrix multiplication is O(N 2maxd) where Nmax = max{N (m) } and d ≪ min{N (m) }. Moreover, there are quantities of optimized libraries (e.g., OpenBLAS) to speed up the most expensive multiplication operations.

The benefit of our proposed NS-Alternating algorithm lies in that, besides monotonously non-increasing the objective, it guarantees to converge to KKT points of the optimization of CDE with the modest computational complexity.

1 http://www.zhongbaozhang.com/publications

Competitive Methods: To evaluate the performance of the proposed MASTER, we compared it with several state-ofthe-art methods listed as follows:

• ULink [Mu et al., 2016]: This method links user identities by modeling users' attributes in the latent user space. We implemented the CCP version of this method.
• PALE [Man et al., 2016]: This method performs reconciliation in an embedding-matching framework. We implemented this method with the matching of MLP.
• COSNET [Zhang et al., 2015]: This method considers the local and global consistency in reconciliation.
• MASTER-: We implemented a degraded version of MASTER ignoring the attribute space to emphasize the importance of comprehensiveness.

In all the experiments, the dimension of the representation vector in MASTER and PALE is set to be 100.

5.2 Experimental Results

We repeated each experiment for 10 times and both the mean and 95% confidence interval are reported. The experimental results are summarized as follows:

Bi-network Case: We evaluated competitive methods on dense and sparse pairs with different η = [5%, 10%, ..., 30%]. Experimental results are reported in Fig. 2(a). In all the experiments, MASTER achieves the highest hit-precision. MASTER has an improvement of 4.92%, 6.21% and 9.40% in average compared to COSNET, PALE and ULink respectively. It is expected. The reasons are two-folded: (i) InMASTER, both observations of attribute and structure space are comprehensively exploited. (ii) The embeddings, capturing the intrinsic relation between users, facilitate the robust reconciliation. MASTER performs better than MASTER- consistently, demonstrating the necessity of comprehensiveness.

5 Experiment

5.1 Experimental Setup

Datasets: We use the Twitter-Foursquare dataset [Kong et al., 2013]. Since Foursquare can be registered by Twitter account, we regard this part of data as ground truth. Twitter dataset consists of 5,220 users and 164,917 connections while Foursquare dataset consists of 5,315 users and 76,972 connections. There are 1,610 shared users. We evaluated the performance of competing methods in the following two cases:

• Bi-network case: We generated a series of network pairs with different overlap rates (η), measured by 2Ns NT+NF , where Ns, NT and NF denote the number of shared users, Twitter users and Foursquare users respectively. Specifically, for each network pair, we sample users from this dataset according to η, called dense pairs. Moreover, in order to evaluate the robustness, we generated a sparse pair for each η-overlap dense pair by randomly removing 30% connections.
• Multi-network case: We generated two networks from Twitter by inheriting all the users and randomly sampling 70% of the connections and attributes (e.g., profiles, generated contents), and also generated two networks from Foursquare via the same process. Then, we simulated a series of four-network dense groups and corresponding sparse groups with different values of η.

Performance Metric: We evaluated all the competitive methods by the hit-precision of the candidate lists, which is measured by 1M ∑m Ei[ (K+1)-hitm(v(·) i ) K ], where E[·] denotes the expectation and K is set to be 5. For instance, for social network S(m) , we obtain a top-K candidates list {v(m) 6 , v(m) 9 , ..., v(m) 1 } for v(1) 5 . If v(m) 9 hits the ground truth, hitm(v(1) 5 ) = 2; hitm(v(1) 5 ) =K +1 for not hitting.

COSNET struggles in defining local consistency and ULink performs the worst due to that it only considers the attribute space with lots of noise.

Multi-network Case: We conducted experiments on the four-network groups with different η = [5%, 10%, ..., 30%], reported in Fig. 2(b). It is evident that MASTER remains the best. This is expected owing to following reasons: MASTER consistently and robustly reconciles multiple social networks in the joint latent space where the information of both space is comprehensively captured and global inconsistency is naturally eliminated. In contrast, PALE presents low hit-precision due to global inconsistency. Although MASTER-, COSNET and ULink address the problem of global inconsistency, however, MASTER- ignores the information in attribute space, COSNET is limited to the sparse information in this case and ULink still suffers from the noise in attribute space.

Robustness: To further evaluate the robustness of our solution, we conducted experiments the sparse pairs and sparse groups, reported in Fig. 2(c) and 2(d) respectively. The performances of COSNET become noticeably worser in sparse pairs (groups) as less information can be leveraged. The robustness of ULink is not evaluated, since the difference among them is in the structure space neglected by ULink. However, the embedding based approaches, i.e., MASTER, MASTER- and PALE, lose much less hit-precision in sparse pairs (groups) and MASTER achieves the highest robustness.

The impacts of parameters: To further evaluate MASTER, we conducted experiments to evaluate the effect of training ratio θ and the contribution of each space. Regarding the impact of θ, we fix η = 30%, β/α = 2/3, and vary the value of θ to [0.5%, 1%, 1.5%, ..., 5%]. We report the corresponding result in Fig. 2(e). From this figure, we observe that the hit-precision of MASTER raises quickly as the training ratio increases from 0.5% to 2%, and slows down when θ exceeds 2%. That is to say, MASTER can achieve good performance with relatively less label information. Regarding the impact of the contribution of each space, we set η = 30%, θ = 5%, and vary the value of lg(β/α) to [-1,-0.8,-0.6, ..., 1]. We report the corresponding result in Fig. 2(f). From this figure, it can be inferred that the structure space has higher contribution than that in attribute space. A reasonable interpretation behind this is that people are not willing to provide truthful personal information (e.g., location, birthday), which results in lots of noise in the attribute space.

6 RelatedWork

The MASTER reconciles multiple social networks in an embedding approach. We briefly summarize the related work in the problem of reconciliation and network embedding:

Reconciliation: The problem is generally regarded as a (semi-) supervised task as the labels can be observed [Shu et al., 2017]. Most of the existing models focus on reconciling only two social networks. A few models reconcile multiple networks, however, ULink [Mu et al., 2016] suffers from the noise in attribute space while COSNET [Zhang et al., 2015] and UniRank [Zhang et al., 2017a] struggle in defining local consistency. Most of the typical models are summarized in Table 1. The difference between our model and the others lies in that we, for the first time, address all these limitations. Network embedding: Network embedding can be addressed through several techniques: (1) matrix factorization, e.g., TADW [Yang et al., 2015], HOPE [Ou et al., 2016], LANE [Huang et al., 2017], M-NMF [Wang et al., 2017b]; (2) deep neural network, e.g., SDAE [Cao et al., 2016], SiNE [Wang et al., 2017a]; (3) random walk, e.g., DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016]. Moreover, both DeepWalk and LINE [Tang et al., 2015] are proved to be equivalent to matrix factorization recently [Qiu et al., 2018]. However, different from all these models, our model is tailored for reconciling multiple social networks.

7 Conclusion

To address the problem of robustly reconciling multiple social networks, we, for the first time, propose the MASTER framework. In MASTER, we design the CDE model to formulate the reconciliation problem into a unified optimization where we embed and reconcile multiple social networks in the joint latent space constructed by uni- and joint-embedding. We design an effective NS-Alternating algorithm to solve the nonconvex optimization of CDE and further prove the KKT convergence of the algorithm. We conducted extensive experiments on real-world datasets and demonstrate that MASTER outperforms several state-of-the-art methods.

Acknowledgments

This work was supported in part by the following funding agencies of China: National Key Research and Development Program under Grant 2016QY01W0200 and National Natural Science Foundation under Grant 61602050 and U1534201.