Multi-Relational Graph Attention Network for Social Relationship Inference from Human Mobility Data

1 Introduction

Location-based social services, such as Foursquare, Yelp, Facebook, and Twitter, are increasingly affecting human daily life and have generated a considerable amount of user spatiotemporal mobility data that record their daily behaviors [Li et al., 2023a]. Revealing social relationships from these mobility trajectory data is crucial to understanding human dynamics, which is widely used to study the impact of human mobility and social bonds on each other [Cho et al., 2011; Yang et al., 2019]. As demonstrated in [Wang et al., 2014; Pham et al., 2016], user mobility data can indeed serve as a strong predictor for inferring social ties. Specifically, estimating social relationships based on users' check-in mobility data is beneficial to various real-world recommendation systems, such as friend suggestion [Yu et al., 2020; Yu et al., 2021], location recommendations [Dai et al., 2022; Li et al., 2024; Wu et al., 2023a], and targeted advertising [Sharma et al., 2021].

∗Corresponding author: Yanwei Yu.

Recent years have brought advances in leveraging network representation learning [Liu et al., 2021; Cui et al., 2018; Sun et al., 2019] to infer mobility social relationships, such as walk2friends [Backes et al., 2017], emb-cat [Yu et al., 2018], vec2link [Zhou et al., 2018], Heter-GCN [Wu et al., 2019], MVMN [Zhang et al., 2020], and HMGCL [Li et al., 2023b]. These methods often model users and checkin locations into homogeneous or heterogeneous networks (e.g., user meeting graph), use network embedding technologies to learn vector representations of user nodes, and use node representation similarities to predict mobility social relationships. To utilize check-in semantic information, a complex heterogeneous hypergraph [Xia et al., 2022] is recently proposed [Yang et al., 2019; Yang et al., 2022; Huynh et al., 2022; Li et al., 2022]. These models treat check-ins as hyperedges, and learn user embedding from hypergraph via preserving high-order proximity between users and check-ins.

However, most previous studies either infer potential links between users from direct relations between users (such as user meetings) or unified learn corrections between users from complex interactions between users and check-ins (with contextual semantics). Most recently, SRINet [Qin et al., 2023], a model based on graph structure learning, has been proposed, which claims that by removing noise edges in the user meeting network, graph neural networks can be used to learn effective user representations for inferring friendships. Nonetheless, these methods have the following two major limitations: First, in user mobility data, especially commonly used meeting relation or co-locations between users, although they can reflect users' social activities to some extent, they are only partially visible (because many real meetings may not be recorded through check-ins). Solely relying on this partially visible direct relation to infer social links between users is obviously not sufficient. Second, various indirect relations reflecting social activities between users have not been fully utilized, and their effect and impact on social relationship inference have not been explicitly modeled and effectively captured. For example, the impact of users' preferences for different locations on friend prediction has not been explored in previous user representation learning.

To address the aforementioned challenges, we propose a Multi-Relational Graph Attention Network (MRGAN) for inferring mobility social relationships. Specially, we first build a heterogeneous mobility graph by combining user checkin relation and partially known friendships, as well as user meeting relations and location co-occurrences mined from user mobility data. In addition to the direct relations, e.g., user meeting and friendship, which have been proven to be strongly related to social ties, MRGAN also aims to capture the impact of users' personalized preferences for locations and users' common preferences for location co-occurrences on social relationship inference, respectively. To this end, MRGAN constructs a multi-relational graph derived from a heterogeneous mobility graph. This graph encompasses not only direct relations such as friendships and meetings for the preservation of social connections but also explicitly models indirect relations, including personalized preferences and common preferences, for exploring user mobility preferences. To learn the different impacts of these relations on social relationship inference, MRGAN first separately learns users' relation-specific embedding and utilizes an attention mechanism to learn their different influence on each other, and eventually fuse the relation-specific user embedding with their importance to infer social ties among users. Extensive experiments on three real-life mobility datasets demonstrate that the proposed model significantly outperforms all stateof-the-art baselines, with an average improvement of 4.28% and 5.51% in terms of PRAUC and ROCAUC.

To summarize, we make the following contributions:

• To improve the performance of mobility social relationship inference, we explicitly model the impact of users' personalized preferences for locations and users' common preferences for location co-occurrence on social relationship inference.
• We propose a novel multi-relational graph attention network that effectively captures and integrates multiple relations between users that reflect users' social relationships, i.e., direct known friendships and meeting relations, and indirect personalized location preference relations and common location co-occurrence preference relations.
• We perform extensive experiments on three real-life mobility datasets, and the experimental results verify the superiority of the proposed model compared to all baseline methods in terms of all metrics.

2 RelatedWork

In the literature, several studies delve into the inference of social relationships through the analysis of human mobility trajectories. Eagle et al. [2009] aim to unveil the correlation between meeting events and social relationships by leveraging mobile phone data. Li et al. [2011] find that the timing of meetings could serve as an indicator for distinguishing between various types of relationships. An entropy-based model (EBM), proposed by [Pham et al., 2013], considers the diversity of meeting events and location entropy in friendship inference. Wang et al. [2014] devise a unified framework, denoted as PGT, that takes into account personal background, global background, and temporal factors. Pham et al. [2016] further extend EBM via integrating location semantic information and stay duration.

The advancements in representation learning and graph deep learning [Cai et al., 2023; Wu et al., 2023b; Dai et al., 2023; Wang et al., 2023; Antelmi et al., 2024] have led to the proposal of more sophisticated methods for social relationship inference. Backes et al. [2017] apply randomwalk based embedding technique on a user-location bipartite graph to predict friendship. Yu et al. [2018] construct a user meeting graph and learning embedding on it via hierarchical walk sampling to infer mobility relationship. Inspired by [Schlichtkrull et al., 2018], Wu et al. [2019] first employ GCN on heterogeneous graph to infer relationship. Yang et al. [2019] present an LBSN hypergraph comprising user, location, time, and semantic nodes, investigating the mutual influence of mobility and social ties on each other. Yang et al. [2022] further extend [Yang et al., 2019] to a heterogeneous hypergraph to consider the heterogeneous nature of LBSN data. Zhang et al. [2020] develop a multi-view matching network designed to acquire three view-specific representations and integrate them for the ultimate relationship inference. Li et al. [2022] model user trajectories and checkin records as hyperedges in a heterogeneous hypergrah, and learn user embedding using attention and contrastive learning for friend recommendation. Huynh et al. [2022] develop an embedding technique that encompasses high-order, dynamic, and multi-role contexts in LBSN hypergraph data, catering to both friend suggestion and POI recommendation.

Recently, Li et al. [2023b] construct a mobility social multi-graph with multi types of edges and apply supervised constractive learning and attention to learn user embedding for friend recommendation. To solve the noise issue in mobility data, Qin et al. [2023] propose a social relationship inference framework, which weeds out noise edge on a multiplex graph via graph structure learning. All the aforementioned methods either predict friendship from direct relations between users (e.g., meeting and friendship in [Qin et al., 2023]) or learn implicit connections between users from complex interactions between users and check-ins. For example, in [Yang et al., 2022], in addition to friendship, users can only achieve indirect interaction through intermediate nodes (e.g., POI, time nodes). Diverging from prior studies, our MRGAN not only leverages explicit and direct relations, such as meetings, but also has the capability to unveil implicit and indirect relations like personalized preferences, modeling them explicitly. Moreover, both direct and indirect relations are fused by taking into consideration their impact and importance.

3 ProblemDefinition

We use U = {u1, u2, . . . , uN} to represent the set of all users and P = {p1, p2, . . . , pM} to represent the set of all POIs.

Definition 1 (Check-in Record). A check-in record, denoted as ⟨u, t, p⟩, signifies the visit of user u to point-of-interest (POI) p at time t. Here, p is a distinct identified venue in the form of ⟨pid, ℓ⟩, where pid indicates the POI identifier and ℓ denotes the the geographical coordinates of the POI (i.e., longitude and latitude).

Definition 2 (Mobility Trajectory). The mobility trajectory, represented as Tru, is a chronological-ordered sequence of check-in records generated by user u, denoted as (⟨u, t1, p1⟩, ⟨u, t2, p2⟩, . . . , ⟨u, ti, pi⟩).

Based on the aforementioned definitions, we formally outline the problem studied in this paper as follows:

Problem (Mobility Social Relationship Inference). Given a set of users U, our aim is to learn an inference model F(ui, uj) → ˆ y for each pair of users based on their corresponding mobility trajectories, and partial social relationship (friendship), where ˆ y ∈ {0, 1}, and ˆ y = 1 indicates that they are friends, otherwise, they are not.

Typically, mobility social relationships are manifested in the spatio-temporal interactions among users and are commonly defined as Meeting Event in the literature [Yu et al., 2018; Qin et al., 2023]:

Definition 3 (Meeting Event). Users ui and uj are deemed to have a meeting event if they both checked in at the same location within a time threshold τ, i.e., ∃⟨ui, t, p⟩ ∈

Trui , ⟨uj , t′ , p′ ⟩ ∈ Truj such that p = p′ and |t - t′ | ≤ τ .

Definition 4 (Meeting Frequency). The number of all meeting events between users ui and uj is defined as the meeting frequency between them, denoted by mi,j .

4 The ProposedModel

In this section, we elaborate our MRGAN. The overall architecture of the proposed MRGAN is shown in Figure 1, which consists of four key components: (1) heterogeneous mobility graph, (2) multi-relational graph construction, (3) relation-specific influence encoder, and (4) cross-relation embedding aggregator. First, we introduce a heterogeneous mobility graph to model user-specific mobility preference and spatio-temporal interactions among users and POIs. Second, to effectively and explicitly model direct and indirect connections (e.g., shared mobility preference), we further construct the multi-relational graph which derives a multiplex graph with four types of relations from the original heterogeneous mobility graph. Third, for each relation, we design a relation-specific influence encoder with the influence attention mechanism to explore distinct social influences among different users. Finally, the cross-relation embedding aggregator based on relation-level attention is involved to aggregate user embedding across all relations. With the aggregated user embedding, we sample positive and negative instances on the multi-relational graph and design a optimization objective specially.

4.1 Heterogeneous Mobility Graph

To better predict social ties from mobility data, we need to effectively model user mobility data to capture users' movement patterns and interaction behaviors, e.g., meeting events, and check-ins. Motivated by [Wu et al., 2019; Li et al., 2023b], we construct a heterogeneous mobility graph illustrated in Figure 1. There are two types of node, namely, user and POI, and four types of relations (edges): friendship (i.e., social relationship), check-in, meeting, and co-occurring. The friendship relation between user pairs indicates they are friends, i.e., the known friend relationships. The check-in relation between a user and a POI represents that the user have check-in records at the POI, and this relation is weighted by number of check-in records. The meeting relation among users denotes that they have meeting events, which is weighted by meeting frequency. The co-occurring relation denotes the link between POI pairs that co-occur frequently in user mobility trajectories.

However, the multiple types of relations we described above in the heterogeneous mobility graph could only capture the direct connectivity among nodes, which may neglect useful indirect spatio-temporal interactions. Existing inference models based on heterogeneous graphs only focus on learning user embedding from direct relations, making it challenging to uncover implicit connections between users, such co-visiting at same POI between users, which reflects shared mobility preferences.

4.2 Multi-Relational Graph Construction

To explicitly model the indirect relations that reflect users' mobility preferences while retaining the previous direct relations, we then construct a multi-relational graph based on the direct and indirect relations derived from the original heterogeneous mobility graph. Specifically, we adopt two types of direct relations, i.e., friendship and meeting, and two types of indirect relations, i.e., personalized preference and common preference. The direct relations (friendship and meeting) have proven to be quite effective in capturing social ties in prior studies [Yu et al., 2018; Wu et al., 2019; Qin et al., 2023]. Personalized preference is a relation between users with the POI acting as the intermediate node (user-POI-user), for example, in Figure 1, user u1 would be linked to user u2 through the POI p2. Personalized preference preserves the connections between users who share same individualized mobility habits. Common preference connects users with POI pairs linked indirectly by co-occurring relation serving as the medium (i.e., user-POI-POI-user), e.g., user u1 and u3 can be connected implicitly via the linked POI pair < p1, p2 > or < p1, p4 >. Common preference is employed to explore the impact of common preference among all users on visited user pairs, because co-occurring between POIs is selected from trajectories of all users. To explicitly model the indirect relations, in multi-relational graph, we straightforwardly link the users that are connected by indirect relations in original heterogeneous mobility graph.

We denote the multi-relational graph as G = {U, {EF , EM, EPP , ECP}}, where U is the set of all users, EF , EM, EPP and ECP represent the edges of friendship, meeting, personalized preference and common preference respectively. Edges in EPP and ECP are also weighted by the number of indirect links between user pairs in the original graph. Notice that we use Gr to represent the r-th layer subgraph in the multi-relational graph.

4.3 Relation-Specific Influence Encoder

Given multi-relational graph G, here, we aim to learn relationspecific user embedding for each relation (i.e., layer). In each layer, different neighbors of user show different social influence and contribute distinctly to its embedding during learning process. The social influence expresses the social pattern of users, e.g., socially active users may be assigned a higher weight, because they are more inclined to make friends. In the spirit of [Veliˇckovi´c et al., 2017; Wang et al., 2021; Tian et al., 2023], we propose a relation-specific influence encoder, where we employ attention mechanism [Vaswani et al., 2017] to distinguish different social impact of neighbors and aggregate information from meaningful neighbors to derive node embedding. Specifically, let N r i denote the neighbors of node ui in the r-th layer Gr, we fuse the neighbors of node ui for relation type r via influence attention:

where x ∈ Rd×1 represents feature of node, hri is the learned embedding of node ui with relation type r, and σ is nonlinear activation. αr i,j is the attention value (i.e., social influence) of node uj to node ui in relation layer Gr, which is formulated as follows:

where ar ∈ R2d×1 is the influence attention vector for type r and || denotes concatenate operator. To enable the training process more stable, we extend the influence attention to multi-head attention:

With carefully preserving the social influence of users, we could obtain four groups of relation-specific node embeddings for all users, denoted as {HF ,HM ,HP ,HC } respectively.

4.4 Cross-Relation Embedding Aggregator

Relation-specific embeddings of user nodes only capture the single mobility interaction pattern of users. To obtain the comprehensive node embedding, we further fuse all relationspecific embedding of node with cross-relation attention. Given relation-specific embedding set {hFi , hMi , hPi , hCi } of node ui, we compute the weight of each relation type as follows:

where U is the set of all users, aRA represents relationlevel attention vector, WRA and bRA are learnable parameters, βr is the importance for relation r to node ui, and R = {F,M, P, C} denotes the set of relations. We thus fuse relation-specific embedding with weighted sum to get the final cross-relation embedding hi of node ui:

Given relation-specific embedding, we finally get final cross-relation embedding H, which effectively captures multiple mobility interaction patterns.

4.5 Model Optimization

In this section, we present the optimization objective of MRGAN. Specifically, we employ binary cross entropy loss function for each relation through negative sampling to optimize model parameters:

where Lr denotes the loss for the relation r, Hi is the embedding of user ui. <, > is a cosine similarity measure function, which acts as the decoder. Θ is the set of positive user pair instances, to learn model parameters in a more effective and stable way, we sample the positive instances via random walk [Perozzi et al., 2014] on each relation layer. Θ- is the set of negative user pairs sampled from all pairs of users who have not connected in each relation layer.

Given the multi-relational graph and the four relations R, the final loss function can be formulated as:

where δr is the hyper-parameter which controls weight of Lr.

5 Experiments

In this section, we perform model evaluation to investigate the effectiveness of our MRGAN and baseline methods on three real-world datasets. Our experiments aim to answer the research questions as follows:

• RQ1: What is the performance of our MRGAN as compared to various state-of-the-art social relationship inference methods?
• RQ2: How do the key components contribute to the performance?
• RQ3: How do the key hyperparameters influence the performance of the proposed MRGAN?

5.1 Datasets

In experiments, three real-world check-in datasets, Gowalla, Brightkite [Cho et al., 2011] and Foursquare [Yang et al., 2019], are used to evaluate the performance of methods. Notice that, we do not discard any user mobility data as in [Qin et al., 2023], while previous works [Pham et al., 2016; Yang et al., 2022; Huynh et al., 2022] discard inactive users with few check-ins. We present the data statistics in Table 1.

5.2 Baselines

We compare our MRGAN against with three categories of baselines:

Classic graph embedding models:

• DeepWalk [Perozzi et al., 2014] - applies randomwalks to gain sequences of nodes, and uses Skip-gram to learn embedding.
• node2vec [Grover and Leskovec, 2016] - conducts second-order random walks to embed nodes using SkipGram model.
• GCN [Kipf and Welling, 2017] - is a semi-supervised graph convolutional network that designed for the homogeneous graphs.

Heterogeneous graph embedding models:

• R-GCN [Schlichtkrull et al., 2018] - assigns different weight matrices for the propagation on different kinds of edges.
• HAN [Wang et al., 2019] - is a semi-supervised heterogeneous graph neural network.
• HGMAE [Tian et al., 2023] - is a heterogeneous graph masked autoencoder.

Social relationship inference models:

• emb-cat [Yu et al., 2018] - applies skip-gram based model on user meeting graph to learn node embeddings.
• Heter-GCN [Wu et al., 2019] - applies GCN on user mobility heterogeneous graph for social relationship inference.
• MVMN [Zhang et al., 2020] - learns view-specific representations and combines them to infer final social relationships.
• LBSN2Vec++ [Yang et al., 2019; Yang et al., 2022] - samples hyperedges from LBSN heterogeneous hypergraph and learns node embeddings.
• MSC-LBSN [Huynh et al., 2022] - is a multi-context embedding method designed to learn multiple representations for each user.
• HHGNN [Li et al., 2022] - is a heterogeneous hypergraph neural network with supervised contrastive learning for the friend recommendation.
• HMGCL [Li et al., 2023b] - captures spatio-temporal characteristics of human trajectories on a heterogeneous multigraph.
• SRINet [Qin et al., 2023] - learns user embedding for social relationship inference by denoising mobility data.

5.3 Experiment Settings

In our experiments, we sample 25% friendships in social networks on each dataset as training set, which is used to build the social relation in heterogeneous mobility graph. Then we randomly sample another 5% friendships for validating, and use the remaining 70% as testing set.

Our MRGAN is implemented in PyTorch and optimized by Adam [Kingma and Ba, 2014] for parameter learning. In the model implementation, we set the learning rate to 0.001, and employ learning rate scheduler provided by PyTorch to adjust the learning rate based on the number of epochs. We set dimension of node representation to 128, the number of attention head to 4, the dimension of influence and cross-relation attention vector to 128. Guided by [Qin et al., 2023], we set time threshold τ = 2 hours. We keep location co-occurrence relations with frequency ϵ >= 10. In multi-relational graph, we retain top-η PP relations and top-γ CP relations by frequency for each user (Default η = 4 and γ = 10).

Notice that we can reproduce their results using the source code of SRINet [Qin et al., 2023], so for a fair comparison, we directly adopt the results of SRINet and its baselines in their original paper. For other baselines, we evaluate using the source code released by their authors, and tune the parameters of baselines for optimal performance. We repeat each experiment 10 times on each dataset for all methods and report the results of methods after averaging.

5.4 EvaluationMetrics

Derived from [Yu et al., 2018; Qin et al., 2023], in our evaluation, we employ the widely used Area Under the ROC Curve (ROCAUC) and the Area Under the Precision-Recall Curve (PRAUC) to evaluate the performance of various methods. In the context of social relationship inference, we calculate the pairwise cosine similarity of learned user representations in each method to derive a score indicating the likelihood of two users being friends.

5.5 Experiment Results

Overall Performance (RQ1)

As the experimental result shown in Table 2, our MRGAN significantly outperforms all baselines across three datasets in terms of all evaluation metrics. This observation confirms the the superiority of our proposed MRGAN. This may be because our model not only considers the social connections between users reflected in direct relations, but also captures users' mobility preferences implied by indirect relations, which can be used to learn more interest correlations between users, further improving accuracy in social relationship inference. Moreover, benefiting from the influence attention, the social influence from various users can be comprehensively taken into account, besides, with relation-level attention, MRGAN could preserve semantic information of user's different mobility patterns. Specifically, results in Table 2 indicate that our MRGAN achieves average gains of 5.51% ROCAUC and 4.28% PRAUC in comparison to the best-performed baseline across all datasets.

SRINet achieves the second-best performance in most cases, which improves the performance by handling mobility noise data issue. Despite effectiveness, SRINet overlooks the user mobility preference, a crucial aspect in friend inference. Heter-GCN and HMGCL, another two inference models based on heterogeneous graph, take the user mobility pattern into account, but hardly capture the mobility preference by singularly applying embedding learning on direct relations. Although MSC-LBSN, LBSN2Vec++ and HHGNN apply sophisticated embedding learning method on heterogeneous hypergraph, they suffer from the noise issue. In addition, HAN and HGMAE, two heterogeneous graph representation learning models, achieve competitive results even compared with inference models. The possible reason is HAN and HGMAE are both powered by hierarchical attention, which suggests that effectively accounting for the influence of diverse users and various mobility semantics is crucial for friendship inference.

Ablation Study (RQ2)

To analysis the effectiveness of the key components in our model, we conduct the following ablation studies. Two major categories of variants are designed: relation-induced and attention-induced variants.

Relation-induced variants are employed to verify the contribution of different relations to model performance, which consists of:

• w/o M removes meeting relation and corresponding loss.
• w/o PP deletes personalized preference relation and corresponding loss.
• w/o CP excludes common preference relation and corresponding loss.

Attention-induced variants are designed to verify the contribution of attention mechanism :

• w/o IA removes the node-level attention (i.e., influence attention).
• w/o RA takes away the relation-level attention in crossrelation embedding aggregator.

The results of ablation studies are summarized in Figure 2. From the results, three conclusions are made as follows: (1) Five variants are consistently worse than MRGAN across all datasets in terms of ROCAUC and PRAUC, indicating the effectiveness and necessity of the five key components. (2) With regard to relation-induced variants, the performance of w/o M experiences a significant decline compared to that of MRGAN, which demonstrates that the meeting relation is powerful for capturing possible social links. w/o PP and w/o CP perform worse than MRGAN in all cases, which suggests the employment of PP and CP relations reveal the shared mobility preference and common mobility pattern of users. (3) Regarding attention-induced variants, the performance of w/o IA drops significantly compared to MRGAN, which means that considering and learning the importance of social influence among users is effective for relationship inference. The gap between MRGAN and w/o RA shows that aggregation of different interaction patterns is critical.

Hyper-parameter Analysis (RQ3)

We investigate the sensitivity of four main parameters: training set ratio, user embedding dimension d, the number of attention head K and time threshold τ .

As shown in Figure 3a, as the training set ratio increases from 5% to 25%, a substantial improvement in performance is observed. Subsequently, with further increments in the training set, performance exhibits a gradual and incremental increase. The observed result aligns with our expectation, and our model can attain the desired performance with a training set ratio of 25%. In Figure 3b, we observe that model performance initially improves with increasing dimensionlity, peaking at 128. Subsequently, as dimensions continue to increase, performance degrades. Clearly, too small dimensions poses challenges in adequately expressing the comprehensive information captured by our MRGAN. Figure 3c illustrates the performance w.r.t. attention head K in influence and cross-relation attentions. We can see that model performance reaches its highest when K is 4. As illustrated in Figure 3d, the model performance reaches its peak at τ = 2. It is noteworthy that before τ = 2, the performance shows a gradual increase or intermittent fluctuations. We interpret this phenomenon as a trade-off between noise and interactive informativeness. The smaller τ is, the less noise is introduced, but a large amount of interactive information is filtered out. On the other hand, as τ increases, the noise increases, but so does the amount of interactive information. However, when τ is too large, noise takes precedence, resulting in a significant performance degradation, e.g., τ = 3.

6 Conclusion

In this paper, we present a multi-relational graph attention network for inferring social relationships from user mobility data. Our proposed model effectively learns user representations for friendship inference by explicitly modeling users' mobility preference and effectively capture the different impact and importance of both direct and indirect relations. Experiments on three real-world mobility datasets show that our model significantly outperforms state-of-the-art baselines.

Acknowledgments

This work is partially supported by the National Natural Science Foundation of China under grant Nos. 62176243, 62372421, and 41927805, the Project funded by China Postdoctoral Science Foundation (No. 2023M743328), the Postdoctoral Fellowship Program of CPSF (No. GZC20232500), and the Postdoctoral Project funded by Qingdao (No. QDBSH20240102093). Guangming Qin and Jianpeng Qi contribute equally to this work.