Link Prediction in Multilayer Networks via Cross-Network Embedding

Guojing Ren, Xiao Ding, Xiao-Ke Xu, Hai-Feng ZhangAAAI 2024 · OpenReview

Abstract: Link prediction is a fundamental task in network analysis, with the objective of predicting missing or potential links. While existing studies have mainly concentrated on single networks, it is worth noting that numerous real-world networks exhibit interconnectedness. For example, individuals often register on various social media platforms to access diverse services, such as chatting, tweeting, blogging, and rating movies. These platforms share a subset of users and are termed multilayer networks. The interlayer links in such networks hold valuable information that provides more comprehensive insights into the network structure. To effectively exploit this complementary information and enhance link prediction in the target network, we propose a novel cross-network embedding method. This method aims to represent different networks in a shared latent space, preserving proximity within single networks as well as consistency across multilayer networks. Specifically, nodes can aggregate messages from aligned nodes in other layers. Extensive experiments conducted on real-world datasets demonstrate the superior performance of our proposed method for link prediction in multilayer networks.

Introduction

Link prediction—the task of forecasting missing or future connections between nodes—is a cornerstone of network science with applications ranging from social recommendation to biological discovery. Traditional methods typically analyze a single network in isolation. However, real-world entities often exist across multiple interconnected platforms, forming "multilayer networks."

Conceptual diagram of a multilayer network where nodes are aligned across layers Gs and Gt.

As illustrated in the figure above, a single user may maintain profiles on different platforms (e.g., Facebook and Twitter), each capturing different facets of their social behavior. Existing research often assumes "multiplexity," where all node identities are known across all layers. In practice, we only possess a partial map of these identities, known as anchor nodes. This paper addresses the challenge of link prediction in these partially overlapped multilayer networks by leveraging complementary information from across layers.

Methodology: Cross-network Graph Neural Networks (CGNN)

The proposed CGNN model embeds multiple networks into a shared latent space to facilitate knowledge transfer. The architecture rests on three primary innovations:

  1. Cross-GNN Layers: Unlike standard GNNs that aggregate messages only from local neighbors, CGNN allows a node to aggregate information from its immediate neighbors within the same layer and its aligned counterpart in the other layer. This mechanism enables the model to fill structural gaps in one network using data from another.
  2. Joint Objective Function: The model is trained using a dual-loss approach. An Intralayer Loss preserves local community structures using random-walk-based proximity, while an Interlayer Loss ensures that aligned nodes across platforms are mapped closely together in the embedding space.
  3. Degree-Discount Mechanism: To address the "popularity problem," the authors implemented a mechanism that reduces the influence of high-degree nodes, which were found to be less useful for capturing meaningful interlayer features.

Experimental Evaluation

The model was evaluated on two real-world multilayer datasets: Facebook-Twitter and Twitter-YouTube. To test robustness, the researchers varied the "Ratio of Interlayer Links" from 0% to 90%, simulating scenarios with varying levels of known cross-platform identities. This allows for an assessment of how the model performs when cross-network information is sparse.

Key Results and Discussion

CGNN consistently outperformed a wide array of baselines, including classic heuristic methods (CN, RA), matrix factorization (SVD), and state-of-the-art deep learning models (GAE, GAT, CELP).

Performance comparison of CGNN against baseline methods across different interlayer link ratios.

As shown in the results table, CGNN achieved an AUC of 0.9653 on the Facebook-Twitter dataset at a 90% link ratio, significantly surpassing the single-network GAT (0.9213). Notably, the model maintains high performance even when cross-network information is sparse (e.g., at a 30% ratio), demonstrating its practical utility for real-world applications where data is often incomplete.

Ablation studies further revealed that the cross-GNN layer and the intralayer loss are critical; removing the latter caused a significant drop in performance, highlighting that understanding internal network structure is a prerequisite for successful cross-network prediction.

Conclusion

CGNN provides a robust framework for link prediction by effectively "borrowing" structural information across multilayer networks. By integrating cross-network message passing with a joint optimization strategy, it overcomes the limitations of data sparsity and noise inherent in single-network analysis. Future work will focus on scaling the model to handle more than two layers and extending it to directed or weighted network types.

Summary updated

Abstract

Link prediction is a fundamental task in network analysis, with the objective of predicting missing or potential links. While existing studies have mainly concentrated on single networks, it is worth noting that numerous real-world networks exhibit interconnectedness. For example, individuals often register on various social media platforms to access diverse services, such as chatting, tweeting, blogging, and rating movies. These platforms share a subset of users and are termed multilayer networks. The interlayer links in such networks hold valuable information that provides more comprehensive insights into the network structure. To effectively exploit this complementary information and enhance link prediction in the target network, we propose a novel cross-network embedding method. This method aims to represent different networks in a shared latent space, preserving proximity within single networks as well as consistency across multilayer networks. Specifically, nodes can aggregate messages from aligned nodes in other layers. Extensive experiments conducted on real-world datasets demonstrate the superior performance of our proposed method for link prediction in multilayer networks.
BibTeX
@inproceedings{ren2024link,
  author = {Guojing Ren and Xiao Ding and Xiao-Ke Xu and Hai-Feng Zhang},
  title = {{Link Prediction in Multilayer Networks via Cross-Network Embedding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=f53C9a6PFm},
}
Figure