Social network alignment has been an important research problem for social network analysis in recent years. With the identified shared users across networks, it will provide researchers with the opportunity to achieve a more comprehensive understanding of users’ social activities both within and across networks. Social network alignment is a very difficult problem. Besides the challenges introduced by the network heterogeneity, the network alignment can be reduced to a combinatorial optimization problem with an extremely large search space. The learning effectiveness and efficiency of existing alignment models will be degraded significantly as the network size increases. In this paper, we focus on studying the scalable heterogeneous social network alignment problem, and propose to address it with a novel two-stage network alignment model, namely Scalable Heterogeneous Network Alignment (SHNA). Based on a group of intra- and inter-network meta diagrams, SHNA first partitions the social networks into a group of sub-networks synergistically. Via the partially known anchor links, SHNA can extract the partitioned sub-network correspondence relationships. Instead of aligning the complete input network, SHNA proposes to identify the anchor links between the matched subnetwork pairs, while those between the unmatched sub-networks will be pruned to effectively shrink the search space. Extensive experiments have been done to compare SHNA with the state-ofthe-art baseline methods on a real-world aligned social networks dataset. The experimental results have demonstrated both the effectiveness and efficiency of SHNA in addressing the problem.

Heterogeneous Network; Network Alignment; Synergistic Partition

ACM Reference Format: Yuxiang Ren, Lin Meng, and Jiawei Zhang. 2020. Scalable Heterogeneous Social Network Alignment through Synergistic Graph Partition. In Proceedings of the 31st ACM Conference on Hypertext and Social Media (HT ’20), July 13–15, 2020, Virtual Event, USA. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3372923.3404799

Florida State University, FL, USA

jiawei@ifmlab.org

1 INTRODUCTION In recent years, a large number of online social networks have appeared, which can provide people with various kinds of services. To enjoy these different services at the same time, users nowadays are usually involved in a number of online social networks simultaneously. For instance, people will join in Facebook1 to socialize with their friends; use Linkedin2 to establish their professional profile; rely on Twitter3 to access and comment on the latest news information. However, in the real world, these different online social networks are mostly isolated without any knowledge about the shared users among them, which renders the inter-network social network analysis a great challenge.

Recently, some research works have proposed to study the alignment problem [6, 27] across multiple online social networks. The main objective of the social network alignment problem is to uncover the mappings of common users across networks, which are named as the anchor links [6] formally. Social network alignment provides researchers with the opportunity to study the users’ social activities from a global perspective. By integrating the social activity information from multiple social sites, we can achieve a more comprehensive knowledge about users’ social preferences. Meanwhile, via these inferred anchor links, information can also propagate across different social networks to improve the services of different social networks simultaneously.

Formally, given two networks G(1) and G(2) with m and n users respectively, we can denote the number of true anchor links existing between G(1) and G(2) as l. According to [6], the anchor links to be inferred are usually subject to the one-to-one cardinality constraint. In other words, each user will be connected by at most one anchor link between the networks, and we can have l ≤min(m,n). Social network alignment problem aims at identifying these l true anchor links from the m × n potential anchor links, which will lead to a combinatorial optimization problem of time

 m × n



complexity O

. Most of the existing network align-

min(m,n)

ment models are mainly proposed based on the complete input network [6, 25, 26], which will become ineffective for large-scale online social networks with a large number of users. Problem Studied: In this paper, we will study the scalable online social network alignment problem, where each social network studied is of a heterogeneous structure involving multiple types of nodes and links. To address the problem, a reduction of the search space, i.e., these aforementioned m × n potential anchor links, is

1https://www.facebook.com 2https://www.linkedin.com 3https://twitter.com

necessary and critical, which can not only improve the learning effectiveness but also significantly lower down the time costs in model learning.

The heterogeneous social network alignment problem is extremely challenging to address due to several different reasons:

• Heterogeneity: There exist various types of heterogeneous information in social networks, which can provide critical signals for identifying the common users across networks. Meanwhile, properly handling such heterogeneous information in a unified way is not an easy task. • Scalability: For the large-sized input online social networks, learning efficiency is a crucial factor to consider in the model building. Few of the existing research works have ever studied this problem yet, which remains an open problem. • Generalizability: To ensure the applicability of the proposed model, we need to propose a general learning model that can be extensible to various learning settings. Besides differentiating the non-existing anchor links from the real ones, the model should also incorporate the one-to-one cardinality constraint [6] effectively. To address these challenges aforementioned, we introduce a novel scalable heterogeneous social network alignment framework, namely Scalable Heterogeneous Network Alignment (SHNA), in this paper. To effectively capture the diverse connections among users within and across networks with heterogeneous information, SHNA employs a group of meta diagrams in this paper. Meta diagram is a novel concept proposed in [16], which includes both meta path and more complex meta structures to outline the user correlations both within and across heterogeneous networks . As a scalable and general solution, SHNA addresses the social network alignment problem via two stages: network synergistic partition and parallel sub-network alignment. SHNA proposes to partition the large-sized input social network data into a group sub-networks with a synergistic network partition method. The partition process needs to take care of both the diverse intra- and inter-network user connections, where the shared users should be partitioned into the groups with correspondence relationships as indicated by the partially known anchor links. Then alignment will be performed between these identified corresponding sub-networks only in the second stage, whose learning results will be fused to recover the complete alignment result of the input networks.

The remaining parts of this paper are organized as follows. In Section 2, we introduce the definitions of several important terminologies and the formal problem statement. Meta diagram which is the basis of features in this paper is introduced in Section 3. Detailed information about the proposed model is provided in Section 4, whose effectiveness and efficiency are verified in Section 5. Related works are discussed in Section 6 and finally in Section 7 we conclude this paper. 2 PROBLEM FORMULATION 2.1 Terminology Definition

The network we study is an attributed heterogeneous social network. Definition 1 (Attributed Heterogeneous Social Network): The attributed heterogeneous social network can be represented as G = (V, E, T). V = Ð

i Vi is the set of different nodes, while E = Ð

i Ei

Session 8: Social Media Analysis HT ’20, July 13–15, 2020, Virtual Event, USA

Figure 1: Schema of aligned networks.

represents the set of complex links in the network. Besides, the set T = Ð

i Ti represents a group of attributes attached to nodes. Between two attributed heterogeneous social networks, if there exist shared users, we define them as aligned attributed heterogeneous social networks Definition 2 (Aligned Attributed Heterogeneous Social Networks): Given the attributed heterogeneous social networks G(1), G(2) and common users are shared between them, we can define them as the aligned attributed heterogeneous social networks G =



(G(1),G(2)), A(1,2)

,

and A(1,2) is the set of undirected anchor links between G(1) and G(2) which connect the common users.

Here, we take two famous online social networks Foursquare and Twitter as an example. We represent them as G = ((G(1),G(2)), A(1,2)), whereG(1) represents Foursquare andG(2) is Twitter. The Foursquare network G(1) can be represented as G(1) = (V(1), E(1), T (1)), where V(1) is the union of U(1) and Post(1) representing the sets of users and posts in the network respectively. E(1) = E(1)

u,u ∪E(1)

u,p contains the set of social links among users and the set of write links between users and posts. T (1) = T (1)

l ∪T (1)

t denotes the set of attributes

extracted from the posts in Post(1) including location checkins T (1)

l and timestamps T (1)

t in this example. The Twitter network can be represented in a similar format as Foursquare, which can be denoted as G(2) = (V(2), E(2), T (2)). User anchor links in set A(1,2)

connecting to shared users between Foursquare and Twitter can effectively align these two networks together. In the following parts, we illustrate the problem setting and the proposed framework based on the aligned Foursquare and Twitter networks, i.e., G.

Given aligned attributed heterogeneous social networks G, we can represent all potential anchor links between networks G(1) and G(2)

as set H = U(1) × U(2), where U(1) and U(2) denote the user sets in G(1) and G(2) respectively. For the known anchor links, we can group them as a labeled set D = A(1,2). The remaining anchor links with unknown labels are those to be inferred, and they can be denoted as the unlabeled set P = H D. Based on both D and P, we aim at building a mapping function f : H →Y to infer anchor link labels in Y = {0, +1} subject to the one-to-one constraint, where labels +1 and 0 denote the existing and non-existing anchor links respectively.

Before introducing the SHNA framework, we first introduce intranetwork meta diagram and inter-network meta diagram, which are used to measure the proximity among users in the SHNA.

In order to better understand the aligned attributed heterogeneous social networks, it is necessary to define a schema-level description. Definition 3 (Aligned Attributed Heterogeneous Social Network Schema): The schema of the given aligned social networks G can be represented as SG = ((SG(1),SG(2)), {anchor}). Here, SG(1) =

(N(1)

V ∪N(1)

T , R(1)

E ∪R(1)

A ), where N(1)

V and N(1)

T denote the set of

node types and attribute types in the network, while R(1)

E represents

the set of link types in the network, and R(1)

A denotes the set of association types between nodes and attributes. In a similar way, the schema of G(2) is SG(2) = (N(2)

E ∪R(2)

T , R(2)

V ∪N(2)

A ). We display the schema of the Foursquare and Twitter networks in Figure 1, where the exact node, attribute, and link types can be found intuitively.

The definition of inter-network meta diagram is first proposed in [16]. Based on our own problem, the definition of inter-network meta diagram can be presented as follows: Definition 4 (Inter-Network Meta Diagram): Given aligned attributed heterogeneous social networks SG = ((SG(1),SG(2)), {anchor}). An inter-network meta diagram can be formally represented as a directed acyclic subgraph ΨA = (NΨ, RΨ, Ns, Nt ), where NΨ ⊂ (N(1)

T ) and RΨ ⊂(R(1)

E ∪R(2)

E ∪R(1)

V ∪N(2)

V ∪N(1)

T ∪N(2)

A ∪R(2)

A ∪ {anchor}). Ns, Nt denote the source and target node types from G(1) and G(2) respectively.

The notaion, description and physical meanings of inter-network meta paths used in this paper are summarized in the first section of Table 1. Because of the problem we try to solve, we are concerned about inter-network meta diagrams connecting two users from different networks. We list several inter-network meta diagram examples in the second section of Table 1. Now we focus on the ΨA

f = {PA

relationship based inter-network meta paths and PAa = {PA

f . We list inter-network meta diagrams used

Figure 2: Parallel Implementation of Framework SHNA 3.1 Network Schema

in SHNA in Table 2. We can represent inter-network meta diagrams as ΨA = PA ∪ΨA

f 2 ∪ΨA

a2 ∪ΨA

f ,a ∪ΨA

f ,a2 ∪ΨA

f 2,a2. The physical

meanings of notations (e.g. f 2) are also explained in Table 2.

The intra-network meta diagrams can be defined in a similar way as inter-network meta diagrams in Section 3.2. There main differences lie in: inter-network meta diagrams connect two nodes across two networks but intra-network meta diagrams exist in one single network. Formally, we can define intra-network meta diagrams as: Definition 5 (Intra-Network Meta Diagram): Given attributed heterogeneous social network schema SG = (NV ∪NT, RE ∪RA). An inter-network meta diagram can be defined as a directed acyclic subgraph ΨI = (NΨ, RΨ, Ns, Nt ), where NΨ ⊂(NV ∪NT) and RΨ ⊂(RE ∪RA), while Ns, Nt denote the source and target node types.

We only consider intra-network meta diagrams which Ns, Nt ∈ {U}. We list the notaion and physical meanings of intra-network meta paths used in this paper in the first section of Table 3. Besides, several intra-network meta diagram examples are presented in the second section of Table 3. Similar to the inter-network meta diagrams, intra-network meta diagrams can be represented as ΨI = PI ∪ΨI

f 2 ∪ΨI

a2 ∪ΨI

f ,a ∪ΨI

f ,a2 ∪ΨI

f 2,a2. Meta path [21] is a special type of the meta diagram in the shape of the path. In the following sections, we directly use the term meta diagram to refer to both meta path and meta diagram.

The structure of SHNA is shown in Figure 2. SHNA is a two-stage framework involving network synergistic partition and parallel subnetwork alignment. Partitioned networks matching acts as a bridge between two stages. We will introduce three parts respectively in this section.

The first stage of SHNA is network synergistic partition, and we both exploit information within and across networks to obtain the optimal sub-networks. We measure the proximity among users within single network based on intra-network meta diagrams and adjust sub-network structures synergistically with the support of inter-network meta diagrams.

f ollow −−−−−−−−→User anchor ←−−−−−−→User

PA

f ollow ←−−−−−−−−User anchor ←−−−−−−→User

PA

f ollow −−−−−−−−→User anchor ←−−−−−−→User

PA

f ollow ←−−−−−−−−User anchor ←−−−−−−→User

PA

PA

PA

f ollow

ΨA

f ollow

L

checkin

P U User write −−−−−−→ Location Timestamp Post

ΨA

at Post

at

T

User User anchor

f ollow

U

U

checkin

ΨA

L

Location Timestamp Post

User write

U P

P U

T

Table 2: Inter-network Meta Diagrams

Set Physical Meanings

f 2 (PA

f × PA

ΨA

f ) Common Aligned Neighbors

a2 (PAa × PAa ) Common Attributes

ΨA

ΨA

f ,a (PA

f × PAa ) Common Aligned Neighbor & Attribute

f × PAa × PAa ) Common Aligned Neighbor & Attributes

ΨA

f ,a2 (PA

f ×PAa ×PAa ) Common Aligned Neighbors & Attributes

f 2,a2 (PA

f ×PA

ΨA

Definition 6 (IntraMD-Pro): Given DΨI

i (x,y) to represent the set

of diagram ΨI

i starting from x to y, and DΨI

i (x, ·) to represent the

set of diagram ΨI

i which go from x to other nodes in the network. The IntraMD-Pro of node pair (x,y) can be defined as

DΨI

DΨI

DΨI

i (x, y)

i (y, x)

Õ

© «

ª®® ¬

IntraMD-Pro(x, y) =

ωi

,

DΨI

i (x, ·)

i (y, ·)

i

where ωi is the weight of ΨI

i ωi = 1. Accoriding to [23], the specific values of hyperparameters ωi can be adjusted automatically by optimizing certain learning objectives, e.g., clustering entropy as used in [23]. We will not elaborate the hyperparameter adjustment algorithm in this paper. What’s more, we use Ai as the adjacency matrix which represents ΨI

i and Í

i among users in the network. The proximity score matrix among users of ΨI





Ai + AT

i can be represented as Si = Bi ◦

, where the matrix Bi represents the out-degree of user x and y, e.g., Bi(x,y) = (Í

i

m Ai(y,m))−1. The ◦represents the Hadamard product. IntraMD-Pro matrix of the network can be represented as:

m Ai(x,m) + Í







Õ

Õ

Ai + AT

Bi ◦

S =

ωiSi =

ωi

.

i

i

i

We can represent the user-cluster belonging confidence scores as a vector hi = (hi,1,hi,2, . . . ,hi,k), where hi,j denotes the confidence score that ui ∈U is in the sub-network Uj ∈C (C is the set of detected clusters), and k is the number of detected communities. Therefore, we can define the partition results of all users in U as the user-cluster belonging confidence matrix H, where H = [h1, h2, . . . , hn]T and n = |U|. We choose to solve the following objective function to minimize the normalized-cut (Ncut) cost [9, 19] and

Table 1: Summary of Inter-Network Meta Diagrams.

ID Notation Meta Diagram Semantics

f ollow ←−−−−−−−−User Common Anchored Followee

f ollow −−−−−−−−→User Common Anchored Follower

f ollow −−−−−−−−→User Common Anchored Followee-Follower

f ollow ←−−−−−−−−User Common Anchored Follower-Followee

f ollow

Common Aligned Neighbors

User

f ollow

checkin

write ←−−−−−−User Common Attributes

f ollow

checkin

Common Aligned Neighbor & Attributes

User write

Post

at

at

achieve the optimal partition result:

H Tr(HTLH),

min

s.t . HTDH = I.

where the Laplacian matrix L = D −S, the diagonal matrix D has D(i,i) = Í

j S(i, j) on its diagonal, and I is an identity matrix.

4.1.2 Inter-Network Meta Diagram based Partition. With the help of inter-network meta diagrams, we can represent the extra knowledge about the aligned attributed heterogeneous networks from a more complete and convincing view.

Inter-network meta diagrams effectively indicate the closeness among the users across different networks, which can be quantified with the proximity scores in this paper. Given a pair of usersu(1)

x and u(2)

y , we denote the set of inter-network diagram ΨA

i connecting

u(1)

x and u(2)

x ,u(2)

i (u(1)

y ). Formally, we represent all inter-

y as DΨA

network meta diagram instances going out from user u(1)

x (or going into u(2)

i (u(1)

i (·,u(2)

x , ·) (or DΨA

y )). The proximity score

y ) as set DΨA

between u(1)

x and u(2)

y based on ΨA

i can be defined as the following InterMD-Pro. Definition 7 (InterMD-Pro): Based on ΨA

i , the proximity between

x and u(2)

u(1)

y in G can be represented as:

2|DΨA i (u(1)

x , u(2)

y )|

i (u(1)

x , u(2)

y ) =

sΨA

.

i (u(1)

i (·, u(2)

x , ·)| + |DΨA

y )|

Based on the promixity of every single inter-network meta diagram, InterMD-proximity between users u(1)

x and u(2)

y in G can be defined as





InterMD-Pro(u(1)

x , u(2)

i (u(1)

x , u(2)

Õ

y ) =

y )

ωi

sΨA

.

i

where ωi is the weight of ΨA

i ωi = 1. The promixity matrix among all users across networks can be represented as SΨA ∈R|U(1) |×|U(2) |, and SΨA(x,y) = InterMD-Pro(u(1)

i and Í

x ,u(2)

y ). We can correlate users together with their cluster belonging relationships effectively across networks with the matrix SΨA. Given one user u(1)

l in G(1), we are able to calculate the user-cluster be-

longing confidence scores of u(1)

l with the user-cluster belonging

PI

f ollow −−−−−−−−→User

PI

f ollow −−−−−−−−→User

PI

f ollow−1 −−−−−−−−−−→User

PI

PI

PI

f ollow

ΨI

f ollow

L

checkin

P U User write −−−−−−→ Location Timestamp Post

ΨI

at Post

at

T

ΨI

L

checkin

P U Location Timestamp Post

T

at

Figure 3: An illustration of Discrepancy. There exists a known anchor link between User A and User A’, also User B and User B’. If User A and User B are partitioned into the same sub-network, but User A’ and User B’ are partitioned into different sub-networks, the discrepancy will arise. Synergistic partition works on eliminating the discrepancy confidence scores from G(2). Formally, we define Transition Usercluster Belonging Confidence Scores as follow:

¯h(1)

SΨA(l, j) · h(2)

l =

j

j=1

By maximizing the consensus of partition results based on the transition user-cluster belonging confidence scores, we can refine the partition results with information from the other partially aligned network synergistically. In this paper, we will propose the definition of discrepancy, which measures how different the shared user pairs are clustered across networks. We provide an illustration about discrepancy in Figure 3. Definition 8 (Discrepancy): Given two users u(1)

l and u(1)

m in G(1),

If users u(1)

l and u(1)

m are partitioned into the same sub-network in

G(1) but into different sub-networks based on the transition usercluster belonging confidence scores from G(2), then it will lead to the discrepancy between the partition results of u(1)

l , u(1)

m . The confi-

dence thatu(1)

l andu(1)

m are in the same sub-network can be denoted

as h(1)

l (h(1)

m )⊤. Formally, the discrepancy of u(1)

l and u(1)

m is defined

m )⊤2



h(1)

l (h(1)

m )⊤−¯h(1)

l (¯h(1)

to be dlm(C(1)) =

. Furthermore, the

discrepancy of C(1):

Table 3: Summary of Intra-Network Meta Diagram.

ID Notation Meta Diagram Semantics

f ollow −−−−−−−−→User Follow

f ollow −−−−−−−−→User Follower of Follower

f ollow−1 −−−−−−−−−−→User Common Out Neighbor

f ollow −−−−−−−−→User Common In Neighbor

Follower and Followee

checkin

write ←−−−−−−User Common Attributes

f ollow

checkin

Common Attributes & Follower and Followee

at User write User write User

Post

d(C(1)) =

dij(C(1))

i

j=i+1

With the user-cluster belonging confidence matrices H(1) and H(2), the discrepancy of G is

d(C(1), C(2)) = d(C(1)) + d(C(2))

¯H(1) 

H(1)T

¯H(2) 

H(2)T

¯H(1)T

¯H(2)T

−H(1) 

−H(2) 

=

.

F

F

Where ¯H(1) = [¯h(1)

⊤H(1) and ¯H(1) = SΨAH(2). 4.1.3 Synergistic Partition of Multiple Networks. By taking both Intra-Network Meta Diagram based Partition and Inter-Network Meta Diagram based Partition into considerations, the optimal synergistic partition results C(1) and C(2) can be achieved by minimizing both the Ncut costs and the discrepancy simultaneously as follows:

arg min C(1),C(2) α · Ncut(C(1)) + β · Ncut(C(2)) + θ · d(C(1), C(2))

where α, β and θ represent the weights of these compositions. We can replace Ncut(C(1)), Ncut(C(2)), d(C(1), C(2)) with the terms derived before, and the joint objective function can be rewrited as:

min H(1),H(2) α · Tr((H(1))TL(1)H(1)) + β · Tr((H(2))TL(2)H(2))

¯H(1) 

H(1)T

¯H(2) 

H(2)T

¯H(1)T

¯H(2)T

−H(1) 

−H(2) 

θ ·

θ ·

,

F

F

s.t . (H(1))TD(1)H(1) = I(1), (H(2))TD(2)H(2) = I(2),

The joint objective function involves two variables: H(1) and H(2), and the objective is not jointly convex. Besides, the objective function contains complex orthogonality constraints which are numerically expensive to preserve in optimization. In order to preserve constraints in an efficient way during the learning process, we propose to relax the objective function as follows:

min H(1),H(2) α · Ncut(C(1)) + β · Ncut(C(2)) + θ · d(C(1), C(2))

(H(1))TD(1)H(1) −I(1)

(H(2))TD(2)H(2) −I(2)

ρ1

F + ρ2

F ,

By setting ρ1 and ρ2 with large values, e.g., 109, optimizing the above function is (approximately) equivalent to the original objective function. We design an hierarchical alternative variable updating process for solving the problem:

• Step (1): Fix H(2), Update H(1). Based on the Gradient Descent, we calculate H(1)

k representing

H(1) after k descent steps:

H(1)

k = H(1)

k−1 −η1 · ∇L(H(1))

η1 is the step length, and the gradient ∇L(H(1)) is:

∇L(H(1)) = ∂L ∂H(1)

L(1)H(1) + (L(1))TH(1)



α ·

XH(1) + XTH(1) + 2H(1)(H(1))TH(1)



2θ

ΨAH(1) −XH(1) −XTH(1)



2SΨAST ΨAH(1)(H(1))TSΨAST

2θ

D(1)H(1)(H(1))TD(1)H(1) −D(1)H(1)



4ρ1

H(2)T

ΨA and Y = H(2) 

where X = SΨAYST

.

• Step (2): Fix H(1), Update H(2). When H(1) is fixed, the method of updating H(2) with a fixed H(1) is almost the same as Step (1):

H(2)

k = H(2)

k−1 −η2 · ∇L(H(2))

We iteratively operate Step (1) and Step (2), and every iteration operates one step descent for H(1), H(2) until convergence.

Based on the learned matrix H(1), we can learn the clusters of users in network G(1) by applying K-Means algorithms to the learned latent vectors, i.e., rows of matrix H(1), and the detected clusters can be represented as set C(1) = {U (1)

1 ,U (1) 2 , . . . ,U (1) k }. For the users within the same cluster, we propose to extract a sub-network formed by these users and other associated nodes/attributes. For instance, based on the cluster U (1)

l ∈C(1), we can represent the

extracted sub-network as G(1)

l . Formally, the set of extracted subnetwork from G(1) based on the clustering result C(1) can be represented as G(1) = {G(1)

1 ,G(1) 2 , . . . ,G(1) k }. Here, we need to add a remark that the synergistic network partition process involves an iterative variable updating process, which may take some time to converge. Meanwhile, in the real-world application of the proposed model, such a step can be done in an offline manner, where the clustering results can be computed and stored in hard-drive in advance. It will greatly improve the learning efficiency of SHNA in aligning the large-scale social networks.

After partitioning the original networks, it’s critical to matching the sub-networks from different networks, which is the prerequisite for the next stage. As a bridge, the matching step should consider not only the object of network synergistic partition but also the target of parallel sub-network alignment. Here, we propose the sub-network Matching Score as the metric to serve for partitioned networks matching in SHNA. Definition 9 (Matching Score): Given two sub-network G(1)

i and

G(2)

j , which comes from G(1) and G(2) respectively. We define

Matching Score(M-Score) between G(1)

i and G(2)

j as:

i , G(2)

j )|

i , G(2)

j ) = |A(G(1)

i , G(2)

M-Score(G(1)

j |) ·

i | · |U (2)

j |

where A(G(1)

i ,G(2)

j ) is the set of known anchor links between G(1)

i and G(2)

j , and U (1)

i , U (2)

j are sets of user accounts belongs to G(1)

i ,

G(2)

j . In fact, the second term above is the proportion of known links

of all links across G(1)

i and G(2)

j . M-Score takes both the number of known anchor users and the performance of pruning negative links into considerations. We can match the sub-networks according to the descending rank of M-Score to achieve the sub-network matching results M = {M1, M2, . . . , Ms }, and Mi = {G(1)

a ,G(2)

b }. Here, s is a parameter we set corresponding to the top s(s ≤k) pairs for alignment. Then SHNA will start to focus on parallel sub-network alignment on M. 4.3 Sub-network Alignment

In this part, we introduce the alignment model for all the subnetwork pairs in M. We take Mi = {G(1)

a ,G(2)

b } as an example to illustrate the alignment process. 4.3.1 Optimization Objective Function. For all the potential anchor links between G(1)

a and G(2)

b in set H, a set of features will be extracted based on inter-network meta diagrams. Formally, the feature vector extracted for the link l ∈H can be represented as vector xl ∈Rf , where f is the number of types of inter-network meta diagrams. Meanwhile, we can denote the label of link l ∈H as yl ∈Y, and Y = {0, +1}, which denotes the existence of anchor link l between the networks. For the existing anchor links in set D, they will be assigned with +1 label; while the labels of anchor links in P are unknown. All the labeled anchor links in set D can be represented as a tuple set {(xl,yl)}l ∈D. The discriminative component can effectively differentiate the positive instances from the non-existing ones, which can be denoted as mapping f (·;θf ) : Rd →{+1, 0} parameterized by θf . In this paper, we will use a linear model to fit the link instances, and the discriminative model to be learned can be represented as f (xl; w) = w⊤xl + b, where θf = [w,b]. By adding a dummy feature 1 for all the anchor link feature vectors, we can incorporate bias term b into the weight vector w and the parameter vector can be denoted as θf = w for simplicity. The introduced discriminative loss function on the labeled set D can be represented as

2 =

Õ

Õ

(w⊤xl −yl )2.

f (xl ; w) −yl

L(f , D; w) =

l∈D

l∈D

Meanwhile, we also propose to utilize the unlabeled anchor links to encourage the learned model can capture the salient structures of all the anchor link instances. Based on the above discriminative model function f (·; w), for an unlabeled anchor link l ∈P, we can represent its inferred “label” as yl = f (xl ; w). Considering that the result of f (·; w) may not necessary the exact label values in Y, in the generative component, we can represent the generated anchor link label as siдnf (xl; w)
∈{+1, 0}. How to determine its value will be introduced later in the joint function. The loss function introduced in the generative component based on the unlabeled anchor links can be denoted as

w⊤xl −siдnf (xl ; w)
2



Õ

L(f , P; w) =

.

l∈P

As introduced before, the anchor links to be inferred between networks are subject to the one-to-one cardinality constraint. Subject to the cardinality constraint, the prediction tasks of anchor links between networks are no longer independent. For instance, if anchor link (u(1)

i ,u(2)

j ) is predicted to be positive, then all the

remaining anchor links incident to u(1)

i and u(2)

j in the unlabeled set P will be negative by default. Viewed in such a perspective, the cardinality constraint on anchor links should be effectively incorporated in model building, which will be modeled as the mathematical constraints on node degrees. To represent the user node-anchor link relationships in networks G(1)

a and G(2)

b respectively, we introduce the user node-anchor link incidence matrices

a |×|H|, A(2) ∈{0, 1}|U(2)

A(1) ∈{0, 1}|U(1)

b |×|H|. Entry A(1)(i, j) = 1 iff anchor link lj ∈H is connected withu(1)

i in G(1)

a , and it is similar for A(2).

According to the analysis provided before, we can represent the labels of links in H as vector y ∈{+1, 0}|H|, where entry y(i) represents the label of link li ∈H. Based on the anchor link label vector y, user node-anchor link incidence matrices A(1) and A(2), the one-to-one constraint on anchor links can be denoted as the constraints on node degrees as follows:

By combining the loss terms introduced by the labeled and unlabeled anchor links together with the cardinality constraint, we can represent the joint optimization objective function as

min w,y L(f , D; w) + L(f , P; w) + γ · ∥w∥2

s.t . yl ∈{+1, 0}, ∀l ∈H,

In fact, we can simplify the loss function as:

L(f , D; w) + L(f , P; w) = L(f , H; w) = ∥Xw −y∥2

l|H|]T denotes the feature matrix

l1, x⊤

l2, · · · , x⊤

where matrix X = [x⊤

of all the links in the set H.

We use a hierarchical alternative variable updating process to solve the problem: • Step (1): Fix y, Update w. With y fixed, the objective function involving w is:

c 2 ∥Xw −y∥2 2 + 1 2 ∥w∥2 2 .

min w

Here, the objective function is a quadratic convex function, and its optimal solution can be represented as

w = c(I + cX⊤X)−1X⊤y,

where c(I+cX⊤X)−1X⊤is a constant matrix. Therefore, the weight vector w depends only on the y variable. • Step (2): Fix w, Update y. With w fixed, together with the constraint, we know that terms L(f , D; w), L(f , P; w) and ∥w∥2

min y ∥Xw −y∥2

s.t . yl ∈{+1, 0}, ∀l ∈H,

Table 4: Properties of the Heterogeneous Networks

network

property Twitter Foursquare

user 5,223 5,392 tweet/tip 9,490,707 48,756 location 297,182 38,921

2-approximation of the optimal solution. 4.3.2 Parallel Implementation of Sub-network Alignment. The time complexity of these two steps is related to |H| which is determined by the number of users from two sub-networks. The alignment for all the sub-network pairs in the set M can be implemented in parallel, so compared with the alignment method conducted in the whole networks directly, SHNA has the apparent advantage even counting the time consumption of the network synergistic partition. Finally, we have to aggregate alignment results from parallel subnetwork alignment in the sub-network pairs. In SHNA, we choose to preserve the original results from all sub-network pairs in the set M as the final result.

5 EXPERIMENTS 5.1 Dataset Our dataset comes from two real-world heterogeneous networks: Foursquare and Twitter, which are both famous online social networks. The key statistical data of these two networks is listed in Table 4. Detailed information about the strategy of crawling the dataset can be reached in [6]. 5.2 Experimental Settings 5.2.1 Experimental Setup. We can obtain the set of anchor links across Foursquare and Twitter, which will be the positive links. The links between users from Foursquare and Twitter except for anchor links can be treated as negative links. We apply the 2-fold cross-validation to partition the links with the ratio 1 : 1. One fold will be used as the training set and the other one will be treated as the test set. The features depending on the known anchor links like inter-network meta diagrams are extracted only on the basis of the training set. All codes are implemented in Python, and we run the experiments on a Dell PowerEdge T630 Server with 2 20-core Intel CPUs and 256GB memory. 5.2.2 Comparison Methods. Comparison methods in the experiments can be divided into 2 categories according to whether original networks are partitioned or not in building models. Comparison Methods without partition:

• IterClip-MD: IterClip-MD extends the cardinality constrained link prediction model in [25] by incorporating meta diagrams. • Mna-MD: Mna-MD extends the anchor links prediction model in [6] by incorporating meta diagrams as features. • DeepWalk: A random walk based network embedding method [15]. We utilize it to learn the representation of users merely based on the friendship information and concatenate the representations of two users as the feature of a potential anchor link. Then SVM is trained to predict anchor links based on this feature.

Table 5: Performance comparison of different methods for Network Alignment.

Metrics

Methods Precision Recall F1 Time (sec)

SHNA(θ = 10) 0.677±0.002 0.500±0.001 0.575±0.001 7.62 SHNA(θ = 80) 0.691±0.001 0.532±0.011 0.601±0.006 9.12 SHNA(θ = 100) 0.684±0.010 0.515±0.018 0.588±0.015 12.87

SpectralIter 0.481±0.002 0.392±0.013 0.432±0.006 450.14 KmeansIter 0.415±0.003 0.239±0.009 0.303±0.008 361.97

IterClip-MD 0.318±0.004 0.281±0.002 0.298±0.003 49393.81 Mna-MD 0.137±0.008 0.259±0.003 0.178±0.002 6480.38 DeepWalk 0.043±0.001 0.075±0.001 0.054±0.000 18756.13 Metapath2vec 0.071±0.001 0.102±0.002 0.084±0.001 21314.67

• Metapath2vec: A meta-path based heterogeneous network embedding method [2]. Similar to DeepWalk, we use it to learn the embeddings and predict anchor links with a SVM. We report the best result of all intra-network meta diagrams. Comparison Methods with partition:

• SHNA: SHNA is the model proposed in this paper. • SpectralIter: It implements the network partition using spectral clustering, and the sub-network alignment algorithm is the same as SHNA. • KmeansIter: In KmeansIter, we directly use k-means clustering to partition the networks. Some recent methods based on graph embedding and structural seeds like [3, 5, 22, 28] are designed for homogeneous graph and attributed networks, which are different from our problem definition. Therefore, we do not include all of them in comparison methods. 5.3 Experimental Results with Analysis

We will evaluate network synergistic partition and parallel subnetwork alignment respectively together with partitioned networks matching that connects them.

Figure 4: Discrepancy with different parameter θ 5.3.1 Network Synergistic Partition. To illustrate the effectiveness of network synergistic partition, we evaluate the results of the partition before performing the alignment. First, according to Definition 8, the discrepancy of different partition methods is displayed in Figure 4 which shows that network synergistic partition can minimize the discrepancy compared to the other two methods, and the effect of decreasing the discrepancy becomes more apparent as the weight of θ increases.

Besides, according to M-Score defined in Section 4.2, we can observe the average M-Score of Top 20 subnetwork pairs in Figure 5.

Figure 5: The average M-Score of Top 20 sub-network pairs

It essentially demonstrates that network synergistic partition has the best performance in the task of partitioning according to our requirements. Here we do not apply some classic metrics which are often used to evaluate the clustering result, because in SHNA, the partition is used by the next stage in order to better perform the alignment. Conventional metrics for clustering may not be effective here. For example, the partition method obtaining a better result based on conventional clustering metrics in every single network does not guarantee that partitioning multiple networks simultaneously can obtain well-matched sub-networks. From Figure 4 and Figure 5, we can find that as θ rises, the discrepancy is declining, but it does not bring the monotonous rise of the average M-Score. We will make detailed analysis through the discussion on the parameter θ in Section 5.5.

Figure 6: The ratio of covering unknown anchor links 5.3.2 Partitioned Networks Matching. Based on the partitioned networks, we can select the optimal sub-network pairs to perform the alignment and reduce the search space by ignoring links not exist in sub-network pairs. We choose the optimal sub-network pairs based on the ranking of M-Score, so to illustrate that our M-Score-based ranking is reliable and effective, we present related experimental results in Figure 6. Here, the x-axis denotes the number of selected top sub-network pairs, i.e., x = 5 means top 5 sub-network pairs in the ranking list are selected for alignment. For the y-axis indicator, we use the truth of the test set where the coverage ratio represents the coverage of positive anchor links in the test set. The reason why the coverage ratio is important is that if the positive anchor links in the test set are not included in selected sub-network pairs, there will be no chance to be predicted to positive in the alignment stage. In other words, positive anchor links are pruned as negative links. What needs to be explained is that the truth of the test set is only used for evaluation here. From Figure 6 we can find top

30 sub-network pairs from network synergistic partition can cover 92.8% positive anchor links which is higher than two other methods with the ratio 0.866 and 0.693 respectively. It proves not only the matching policy we used is effective which guarantees that 92.8% positive anchor links have the chance to be predicted, but also the effectiveness of network synergistic partition. From another perspec-

Figure 7: Upward trend of potential anchor links

tive, the upward trend of the number of potential anchor links with the rise of the coverage ratio can also reflect the performance of negative links pruning. We display the correlation in Figure 7, and it is obvious that the increasing rate of network synergistic partition is the slowest. It means more impossible and meaningless links are pruned by SHNA, which can affect both time complexity and prediction performance badly in the alignment stage.

5.3.3 Parallel Sub-network Alignment. The experimental results of the alignment stage are shown in Table 5. The methods we test in experiments can all output link prediction labels, and we will use F1, Recall and Precision as evaluation metrics. We will not present the metric Accuracy in the tables, because in such a class-imbalance setting of alignment tasks (the number of negative anchor links is much larger than positive links), the value of Accuracy is not so critical in evaluation. Firstly, we focus on the comparison among SHNA and IterClip-MD. We can find SHNA has a distinct advantage over IterClip-MD according to all four metrics. It means the alignment task achieves better performance after partition compared with no partition. We insist that network synergistic partition not only ensures the scalability but also effectively reduces the search space, that is, pruning impossible and meaningless links. In fact, these links will increase time complexity and affect the alignment stage badly simultaneously. Besides, the comparison among SHNA, DeepWalk and Metapath2vec verifies the effectiveness of inter-network meta diagram based features. It also reminds us that the heterogeneity of social networks needs to be handled in a precise way. Meanwhile, by comparing SHNA, KmeansIter and SpectralIter, we can demonstrate the partition stage is critical to the alignment stage. SHNA overperforms other methods significantly which verifies the effectiveness of network synergistic partition as well. We can observe that the Recall of KmeansIter is lower than IterClip-MD which means the partition based on simple k-means will prune lots of positive anchor links and miss them in the final alignment result. 5.4 Time and Convergence Analysis The number of rounds used to convergence has a significant impact on running time. In Figure 8, we show the label matrix y changes in each iteration when built SHNA and IterClip-MD respectively. Here, the x axis denotes the iterations, and the y axis denotes the changes of y in sequential iterations i and i −1, i.e., ∆y =

yi −yi−1

Figure 8: Convergence comparison Because the iteration steps are excuted simultaneously within each subnetwork pair for SHNA, we set the changes of y as the sum of the changes of subnetwork pairs, i.e., ∆y = Ím

yi

From Figure 8, we can find SHNA can reach convergence in much fewer rounds than IterClip-MD where IterClip-MD needs more than 20 rounds to converge, but SHNA converges within 5 rounds. The alignment time cost of different methods is listed in Table 5. IterClip-MD can achieve better prediction results than classic classification methods such as Mna-MD, but it costs the longest time. The reason lies in as the size of network increases, the number of rounds required for convergence increases together with each iteration time rises rapidly. SHNA has the best performance in the alignment time cost compared with SpectralIter, KmeansIter, because the partition results of SpectralIter, KmeansIter are uneven and some subnetworks are very large in size. In conclusion, SHNA can deduct the alignment time cost significantly based on faster convergence speed and parallel computing. 5.5 Parameter Analysis

j −yi−1

j=1

j

Considering the objective function in Section 4.1.3 is composed of 3 parts, the parameters α, β, and θ reflect the extent to which each part influences the objective function, the proportional relationship among them must be more critical than the numerical values. Therefore, we fix α = β = 1 because we assume that each network is equally important for partition, and tune θ. From Figure 4, we can observe that the discrepancy keeps monotonous decline with the rising of θ. But combining with Figure 5, the average M-Score gets the highest value when θ = 80 instead of θ = 100 which means the value of discrepancy is not the smaller the better for the synergistic partition. We further observe the result of partition with θ = 1000 and find that in order to make the discrepancy infinitely close to 0, most of the anchor links in the training set are concentrated in one pair of sub-networks, and IntraMD-Pro is completely ignored. When θ is small, the result of partitioning will approximate spectral clustering, because InterMD-Pro will not work due to the insignificant weight. Further, the results of alignment with different θ can be observed in Figure 9 intuitively. The results show that F1 and Recall obtain the best performance when θ = 80. On the contrary, when the value of θ is too large or too small, the performance becomes worse. In conclusion, θ should be in a suitable interval to make all parts of the objective function contribute to final results. 6 RELATED WORK Network alignment has become an important research topic in recent years. Network alignment has concrete applications in various areas, e.g., protein-protein-interaction(PPI) and gene regulatory networks alignment in bioinformatics [17], chemical compound matching in chemistry [20], graph matching in combinatorial mathematics [11], figure matching and merging in computer vision [1],

Similarity measurement on heterogeneous networks has been widely studied. Sun introduces the concept of meta path-based similarity in [21]. The meta path suffers from the disadvantage that cannot describe rich semantics effectively. Meta structure [4] is proposed to similarity measure problem, but entities are constrained to the same type. Zhao [29] proposes the concept of meta graph for the single non-attribute network and extends the idea to recommendation problems.

Clustering-based community detection in online social networks is also related to our SHNA framework. Many different techniques are proposed to optimize certain measures, e.g., modularity function [14], and normalized cut [19]. A comprehensive survey of correlated techniques used to detect communities is given by Malliaros et al.[10] and a detailed tutorial on spectral clustering is provided by Luxburg [9]. These works are mostly studied based on homogeneous networks. Consensus clustering [7, 8, 13] is a sub-topic under clustering closing to our paper. However, these works mostly aim to find a single consensus clustering from fully mapped clustering solutions. Shao et al.[18] propose MMC which is based on collective spectral clustering with a discrepancy penalty across sources to deal with partially unknown mappings. In comparison, the purpose of partition in our paper is to obtain optimal sub-network matching instead of optimizing the discrepancy merely. 7 CONCLUSION In this paper, we study the heterogeneous social network alignment problem and propose a novel two-stage framework SHNA to solve it. In order to address the extremely large search space, SHNA partitions the original networks with network synergistic partition. A group of inter- and intra-network meta diagrams are defined to constitute heterogeneous features. The metrics Matching Score is proposed to obtain optimal sub-network matching results. With the support of the partition stage, not only the search space is greatly reduced, but also the alignment within sub-network pairs can be performed in parallel. Extensive experiments are conducted on real-world networks Foursquare and Twitter. The experiment results demonstrate that SHNA has outstanding performance compared with the state-of-the-art baseline methods in both network synergistic partition and parallel sub-network alignment stage.

(a) F1 (b) Recall (c) Precision (d) Accuracy Figure 9: Performance Analysis with different parameter θ and data schemas matching in data management [12]. In the field of social networks, network alignment provides a powerful tool for information fusion[27]. Zafarani et al. studies the cross-network user matching problem in [24] based on both users relationships and various attribute information. Kong et al.[6] propose to fully align social networks with the heterogeneous link and attribute information simultaneously based on a supervised learning setting. Zhang et al.[25, 26] propose to study the problem based on the PU learning setting. A manifold-based social network alignment method is porposed in [30].

8 ACKNOWLEDGEMENT