BANANA: when Behavior ANAlysis meets social Network Alignment

1 Introduction

longing to the same person (named anchor users in this paper), has received significant attention. It can support many concrete real-world applications, such as cross-domain recommendation [Man et al., 2017; Jiang et al., 2015], mutual community detection [Zhang and Yu, 2015a] and link prediction [Zhang et al., 2017]. However, this problem still remains open as most of the existing methods do not take advantage of users' behavior information, which has been proved to be highly correlated among multi-networks [Wu et al., 2014].

⇤Corresponding author

In fact, analyzing user behaviors, which aims to mine users' latent intentions, can provide more information for user profiling and benefit social network alignment tasks. In turn, social network alignment can help to guide the behavior analysis of a specific person among multiple online social networks and obtain a more comprehensive understanding of his/her behavior pattern. In summary, social network alignment and behavior analysis can benefit from each other. For example, as shown in Fig. 1, on Twitter, user a announced that he will leave LA and go to Tokyo at t0. On Foursquare, user b had a check-in in LA at the same time and arrived in Tokyo at t1. By analyzing behaviors of a and b, and fusing with other information, we can infer that a and b are more likely to be the same person. In turn, with such an inferred result, we can utilize his tweet at t2 (a is in Kyoto) to predict that the next check-in of b may be in Kyoto at t3. This motivates us to rethink: Can we jointly address the social network alignment problem and user behavior analysis problem?

The answer is YES! However, there still exist tremendous challenges as follows:

• ÷ (1) How to leverage behavior analysis for social network alignment: Generally, users may behave differently in different social networks. It is very difficult to discover latent consistent pattern from behaviors. Moreover, aligning users with very few annotated anchor users brings an extra challenge.
• ÷ (2) How to further leverage social network alignment for cross-network behavior analysis: User behaviors in social networks are usually dynamic and full of uncertainty. Although given anchor users, it is still tough to make an accurate predictive analysis of behaviors due to the aforementioned characteristic.

To address the challenges above, we propose a novel endto-end framework, called BANANA, i.e., a joint framework for Behavior ANAlysis and social Network Alignment. The core idea of BANANA is to simultaneously address the two challenges above in an end-to-end manner.

To address the challenge (1), we design an earth mover's distance (EMD) based alignment component. Its core idea is to 1) fuse users' behavior information for more comprehensive user representations; and 2) handle the alignment problem at the distribution level with very few annotated anchor users. First, we utilize a multi-channel attention mechanism

)RXUVTXDUH

Figure 1: A toy example for demonstrating that behavior analysis and social network alignment can benefit from each other.

to integrate users' behavior information along with other information in a flexible way. Then, we design an MLP-based embedding network to discover latent consistent patterns by embedding user representations into the same metric space. Finally, we view users in different social networks as samples from different distributions and employ the EMD, which is proved to have nicer properties than other metrics, as the metric of distribution distance and learn the alignment matrix in an end-to-end manner.

To address the challenge (2), based on the alignment result above, we design a temporal graph convolutional network (TGNN) component to make predictive analysis of user behaviors across social networks. In the TGNN component, we first construct a cross-network temporal graph among behaviors in different social networks. Then, we propose an Advanced Temporal Graph-based LSTM (ATG-LSTM) units to enhance the memorization of users' latent intentions. Finally, we design a TGNN layer with several such ATG-LSTM units to fuse cross-network information for a more comprehensive understanding of users' behavior patterns to improve the prediction accuracy.

In order to integrate the above components together, we design a shared alignment matrix as a learnable parameter. In summary, the main contributions are as follows:

• ÷ To the best of our knowledge, this is the first attempt to study the joint problem of social network alignment and user behavior analysis.
• ÷ We propose a novel end-to-end framework (BANANA) to address the joint problem above.
• ÷ We conduct extensive experiments on real-world datasets. The experiment results demonstrate the superiority of our framework.

2 ProblemDefinition

Let G = ¶V↪ S↪ B♦ denote a social network, where V is a set of all users, S 2 R♣V♣⇥♣V♣ is an adjacency matrix among all users, and B = ¶B1 ↪B2 ↪ ▷▷▷↪Bn ♦ is the set of behavior sequences for all users. Here, Bi = ¶bi1 ↪ bi2 ↪ ▷▷▷↪ biT i♦ denotes

6RFLDO 1HWZRUN $OLJQPHQW

7ZLWWHU

D

E

the behavior sequence for each user vi , where T i denotes the number of his/her behaviors.

Let G (1) = {V (1) ↪ S(1) ↪ B(1) and G (2) = {V (2) ↪ S(2) ↪ B(2) represent two social networks, respectively. Part of anchor users can be obtained from user profiles or third-party platforms. Such information is represented as a prior alignment matrix Pl, where Pl (i↪ j) = 1 means user vi 2 V (1) and vj 2 V (2) are the same person.

Problem Definition. Given two social networks G (1) and G (2) , and the prior alignment matrix Pl, the joint problem of social network alignment and user behavior analysis is to:

1) Find a maping function 'a : V (1) ⇥ V (2) 7! ¶0↪ 1♦ such that for any pairs of users (vi ↪ vj ) 2 V (1) ⇥ V (2) , we have 'a (vi ↪ vj ) = 1 if user vi and vj are the same person; otherwise, 'a (vi ↪ vj ) = 0;

2) Find a function 'b (Bi ) = biT i+1 to predict the behavior at the next time T i +1 for any user vi 2 V (1) . Note that, this function 'b also works for any user vj 2 V (2) .

3 The BANANA Framework

In this section, we will introduce the framework for jointly alleviating the social network alignment problem and behavior analysis problem. As shown in Fig. 2, the framework can be divided into two parts: an EMD based alignment component and a TGNN behavior analysis component.

3.1 The EMD-Based Alignment Component

For social network alignment, most existing methods seldom take advantage of users' behavior information. Moreover, they component the alignment problem in the sample level and need plenty of annotated anchor users to ensure the performance. However, it is tough to obtain such a large number of anchor users in the real world. To address the issues above, we design an earth mover's distance (EMD) based alignment component. Its core idea is to 1) fuse users' behavior information for more comprehensive user representations; and 2)

handle the alignment problem at the distribution level with very few annotated anchor users.

First, in order to integrate users' behavior information and other kinds of information, we apply the multi-channel attention for more comprehensive user representations. The multichannel attention integrates information in a flexible way. Thus, channels can process multiple kinds of information independently. In multi-channel attention, a convolution operation is performed with N convolutional filters {Wiu ↪ biu Ni=1 followed by a non-linear activation operation, where N is the number of channels. We calculate attention weights with a learnable vector γ, which reflects the contribution of each kind of information to the final alignment task. We integrate those representations and obtain the user representation as:

where ⇤ can be behavior, attribute or structure information, and softmax (·) is a channel-wise softmax function.

Then, in order to discover consistent behavior patterns, we design an MLP-based embedding network to produce hidden representation for each user in two social networks in the same metric space:

where u0 2 Rd0 is the normalized user representation and d0 is the dimension of representation vectors. The parameter ✓e is shared for users in two social networks in order to embed all representations into the same metric space. We construct the distance matrix D 2 Rn1⇥n2 between users in two social networks, in which each element d (i↪ j) represents the ground distances between users, defined as:

where u(1) i 0 and u(2) j 0 are user representations.

Finally, we view users in different social networks as samples from different distributions and handle the alignment problem at the distribution level. We employ the EMD, which has been proved to have nicer properties in the optimization than JS or KL divergence, to measure the distance between two distributions in the same space. Thus, we aim to minimize the EMD defined as follows:

where Wa (i↪ j) represents the alignment probability between vi and vj . Meanwhile, we incorporate a few annotated anchor user pairs to guide the learning process of our embedding network and the alignment matrix. For the pre-known anchor users vi and vj whose Pl (i↪ j) = 1, we aim to minimize the ground distance between them and the difference between Wa and Pl:

where np is the number of pre-known anchor user pairs, and λw and λd are hyper-parameters to control the weights. Hence, the entire objective of the alignment is defined as:

3.2 The TGNNComponent

In order to leverage social network alignment for crossnetwork behavior analysis, we first design a cross-network temporal graph. A toy example of this graph is shown in Fig. 3. Given a user's behavior sequence Bi , we construct the graph Gb based on the following principles: 1) each vertex bit represents a behavior of user vi ; 2) there should exist an edge between each behavior and its preceding one, i.e., ⌦bit-1 ↪ bit ↵; 3) each behavior should be linked to the behavior of the highest similarity, i.e., ⌦bit⇤↪ bit ↵ ↪ (t⇤ < t); 4) each behavior should connect to m preceding behaviors of the m users in the other social network who have the largest probabilities to be aligned with user vi according to the alignment matrixWa, i.e., ⌦b1t1 ↪ bit ↵ ↪ · · · ↪ ⌦bmtm ↪ bit ↵.

After constructing such a temporal graph, there still exist two issues when handling the user behavior analysis problem, i.e., 1) how to analyze temporal sequences and capture users' latent intentions; 2) based on the alignment result, how to integrate users' cross-network behavior information for more comprehensive behavior representations. To address the issues above, we design a novel temporal graph neural network component as illustrated in Fig. 4. It takes behavior sequences as input and employs the graph we construct above to guide the input of hidden and cell states based on the LSTM.

The ATG-LSTM Unit

Specifically, to address the issue 1), inspired by [Li et al., 2019b], we propose an advanced temporal graph-based LSTM which can enhance the memorization of users' latent intentions and further handle the irregular time interval among behaviors.

For the edge ⌦bit-1 ↪ bit ↵, we employ a variant of LSTM unit:

where xt represents the behavior embedding at the time step t, ht-1 and ct-1 respectively represent the hidden state and cell state at time step t-1 which are linked by edge ⌦bit-1 ↪ bit ↵, g (∆t) is a heuristic decaying function such that the larger the value of ∆t, the less effect of the behavior at time step t - 1. We employ the same unit to handle the edge Dbjtj ↪ bitE.

For the edge ⌦bit⇤ ↪ bit ↵, we employ another LSTM unit, and integrate the hidden states as the output of our ATG-LSTM:

where o⇤t and c⇤t represent the activation of the output gate and cell state, respectively.

The Temporal Graph Neural Network Layer

To address the issue 2), we design a TGNN component for cross-network user behavior analysis.

In each TGNN layer, we first utilize m + 1 such ATGLSTM units to component the behaviors of user vi by fusing behavior information linked by edges ⌦bit-1 ↪ bit ↵ and ⌦b1t1 ↪ bit ↵ ↪ · · · ↪ ⌦bmtm ↪ bit ↵. Given a behavior bit in social network G (1) , the inputs of the 1st ATG-LSTM unit shall be hit-1 , cit-1 , cit⇤, hit⇤ and xit . The inputs of the other mATGLSTM units are hjtj , cjtj , cit⇤, hit⇤ and xit , where hjtj and cjtj denote the hidden state and cell state of bjtj in social network G (2) . We concatenate the outputs of the other m ATG-LSTM units and obtain Hi↪(2) t 2 Rm⇥d as:

where k denotes the concatenation operation.

Then, for each column of Hi↪(2) t , we rank the m values in the descending order and output a new matrix ˜Hi↪(2) t . By inserting the output of the 1st ATG-LSTM unit (i.e., hi↪i t ) in the first row, we obtain the output Hit 2 R(m+1)⇥d .

Finally, we employ a 1-D CNN network to fuse users' cross-network behavior information by considering the batch size as 1, the spatial size as m+ 1, and the number of channels as d. The 1-D CNN network outputs hit 2 R1⇥d as the representation of behavior bit . We repeat this process for each behavior and obtain the set of behavior representations: H.

The Behavior Analysis Objective

We adopt the prediction objective as our behavior analysis objective. In order to predict user behaviors, the component computes a probability distribution over all user behaviors in B at time t:

where yi t is the predicted next behavior, Wh is the weight matrix, and B is a set consisting of all unique behaviors in the social network. The loss at time t is calculated as follows:

where bit+1 is the (t + 1)th behavior of user i. For the social network G (1) , the behavior prediction objective is given by the following equation:

where T (1)↪i is the number of behaviors for user vi .

Similar to G (1) , the behavior prediction objective in G (2) can be calculated as follows:

where T (2)↪j is the number of behaviors for user vj .

Our behavior analysis objective is then defined as:

3.3 Joint Learning

To jointly address two problems above, we propose to train the EMD-based alignment component and the TGNN component together, by defining a shared alignment matrix as a learnable alignment parameter matrix:

where W is a randomly initialized parameter matrix, ReLu (·) is an activation function to eliminate weak anchor links between users and ensures the alignment probability to be non-negative, and softmax (·) is applied to normalize the alignment matrix. We define the whole objective function of our end-to-end framework as follows:

where ↵ is a hyper-parameters controlling the trade-off.

4 Experiments

4.1 Datasets

In order to validate our approaches, we employ two realworld datasets. One of the real-world datasets is a TwitterFoursquare (TF) dataset [Kong et al., 2013]. We extend this dataset for more behavior information. The other realworld dataset [Zhong et al., 2012] is collected from the Douban website and can be divided into two networks, i.e., Douban-online and Douban-offline networks which are partial aligned. We report the statistics of datasets in Table 1.

4.2 Experiment Settings

Comparison methods. To evaluate the advantages of BANANA, we conduct comparisons in the following aspects: social network alignment and user behavior prediction. The comparison methods are shown in Table 2.

Evaluation metrics. We employ Precision@k (same as Recall@k in this problem) and MAP@k as evaluation metrics for social network alignment, and Recall@k and MRR (Mean Reciprocal Rank) as evaluation metrics for behavior analysis. Note that higher values indicate better performance.

4.3 Experimental Results

BANANA achieves the best precision and MAP among comparison methods. For social network alignment, from Fig. 5 (due to the lack of space we omit the result in the Douban dataset), we notice that BANANA outperforms all comparison methods. The reason lies in that BANANA takes full advantage of users' behavior information during the alignment process. We also notice that BANANA- achieves lower precision compared to BANANA. The reason for this phenomenon is that BANANA- only fuse users' structure and attribute information which is not rich enough for alignment. In Fig. 5(a), we observe that even with a small size of training ratio, the precision of BANANA achieves the best among all comparison methods. The reason lies in that we solve this problem at the distribution level that does not need that much anchor users for training. In Fig. 5(b), we can observe the ranking performance of BANANA is the best, evaluated by MAP@k. It demonstrates that with the help of behavior information, we can improve the ranking performance of social network alignment.

BANANA achieves the best performance in terms of recall and MRR. For behavior prediction, from Table 3, we observe that BANANA tends to achieve significantly better performance compared to other methods. This observation demonstrates that fusing behavior information from other social networks can help to improve the performance of behavior prediction tasks. We also observe that BANANA achieves higher performance in Douban-online, Douban-offline and Foursquare, and obtains lower Recall@k and MRR in Twitter. The reason lies in that users' tweeting behaviors have such high irregularity to be accurately predicted.

5 RelatedWork

We briefly summarize the related work as follows:

Social network alignment. Most existing approaches can be divided into two main categories: 1) Attribute-based approaches [Zafarani and Liu, 2013; Mu et al., 2016], which find anchor user pairs by calculating their similarities of attributes, such as username, location, profiles, etc; 2) Structure-based approaches [Zhang et al., 2015; Zhang and Yu, 2015b; Su et al., 2018; Zhou et al., 2018; Zhang et al., 2018; Derr et al., 2019; Jiao et al., 2019; Zhang et al., 2019b; Sun et al., 2019], which measures the similarities of users' neighborhood and network features by exploring the connectivity of network topology structures.

User behavior analysis. In recent years, RNNs have been widely applied to analyze behavior sequences. Wu et al. [Wu et al., 2017] proposed the Recurrent Recommender Networks which endowed both users and items with an LSTM autoregressive model that captures the dynamics of users and items for the rating prediction. Chen, et al. [Chen et al., 2018] proposed a time-aware RNN model to learn users' behavior patterns and leverages temporal information for predictive analysis. Different from these previous studies, BANANA can analyze users' comprehensive behaviors in different social networks based on the social network alignment result.

6 Conclusion

In this paper, we propose to jointly study the social network alignment problem and user behavior analysis problem and design an end-to-end framework named BANANA. In BANANA, to leverage behavior analysis for social network alignment, we design an EMD based alignment component to handle the alignment problem at the distribution level. To further leverage social network alignment for behavior analysis, we design a TGNN component to fuse behavior information in different social networks based on the alignment result. We conduct extensive experiments on real-world datasets. The results demonstrate that our framework outperforms several state-of-the-art methods.

Acknowledgments

This work was supported in part by: National Natural Science Foundation under Grant U1936103 and 61921003, and National Key Research and Development Program of China under Grant 2018YFB1003804. This work is also partially supported by NSF through grant IIS-1763365 and by FSU.