Higher-order Structure Boosts Link Prediction on Temporal Graphs

Jingzhe Liu, Zhigang Hua, Yan Xie, Bingheng Li, Harry Shomer, Yu Song, Kaveh Hassani, Jiliang Tang · 2025

Read Higher-order Structure Boosts Link Prediction on Temporal Graphs by Jingzhe Liu, Zhigang Hua, Yan Xie, Bingheng Li, Harry Shomer, Yu Song, Kaveh Hassani, Jiliang Tang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15746.txt.

Introduction

Groups, not just pairs, make networks evolve, and a 2025 paper by Jingzhe Liu and co-authors builds that truth into a forecasting model. Temporal graph networks predict links in changing networks, but most watch only one-to-one ties and burn memory doing it.

The proposed model folds hypergraphs into the learning, so group interactions get their own representation. An algorithm first digs out the hidden group structures in the data. Edge features are then bundled into group features, trimming memory during training. Theory shows the model can tell apart structures that pairwise models cannot. On real temporal networks, it predicted links better than rivals while cutting memory use sharply.

Catalog record

CREATORJingzhe Liu, Zhigang Hua, Yan Xie, Bingheng Li, Harry Shomer, Yu Song, Kaveh Hassani, Jiliang Tang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15746

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Higher-order Structure Boosts Link Prediction on Temporal Graphs Jingzhe Liu, Zhigang Hua, Yan Xie, Bingheng Li, Harry Shomer, Yu Song, Kaveh Hassani, Jiliang Tang Abstract Temporal Graph Neural Networks (TGNNs) have gained growing attention for modeling and predicting structures in temporal graphs. However, existing TGNNs primarily focus on pairwise interactions while overlooking higher-order structures that are integral to link formation and evolution in real-world temporal graphs. Meanwhile, these models often suffer from efficiency bottlenecks, further limiting their expressive power. To tackle these challenges, we propose a Higher-order structure Temporal Graph Neural Network (HTGN), which incorporates hypergraph representations into temporal graph learning. In particular, we develop an algorithm to identify the underlying higher-order structures, enhancing the model’s ability to capture the group interactions. Furthermore, by aggregating multiple edge features into hyperedge representations, HTGN effectively reduces memory cost during training. We theoretically demonstrate the enhanced expressiveness of our approach and validate its effectiveness and efficiency through extensive experiments on various real-world temporal graphs. Experimental results show that HTGN achieves superior performance on dynamic link prediction while reducing memory costs by up to 50% compared to existing methods. 1 Introduction Graphs have been widely used to model interactions in complex real-world systems. With the rapid progress of deep learning, graph neural networks (GNNs) have been developed to predict properties at graph, node, or edge level ( Ma & Tang 2021 ) . Recently, there has been increasing attention to graphs that evolve over time, such as transportation, transaction, or social networks, leading to the study of temporal graphs (TGs) ( Holme & Saramäki 2012 ; Masuda & Lambiotte 2016 ) . Unlike static graphs, TGs change dynamically and pose new challenges for graph learning. A central task in this domain is dynamic link prediction, which predicts whether two nodes will be connected at a specific time ( Poursafaei et al. 2022 ) . As a result, efforts have been made to develop temporal graph neural networks (TGNNs) for temporal link prediction ( Cai et al. 2024 ) . These models show a strong capacity for capturing dynamic patterns in TGs, achieving promising performance. Despite their success, TGNNs still exhibit inherent limitations that may impede their ability to capture the underlying structures of temporal graphs and constrain their effectiveness in dynamic link prediction. One key drawback is that most existing TGNNs focus predominantly on pairwise interactions, overlooking higher-order interactions and structures. Nodes in real-world evolving networks often interact within groups rather than solely through one-to-one connections ( Petri & Barrat 2018 ; Battiston et al. 2021 ) . For example, a communication event may involve a team of individuals, and a transaction could include multiple stakeholders. It is evident that such group interactions – formally referred to as higher-order structures – are integral to the dynamic behavior and link formation of temporal graphs ( Benson et al. 2018 ) . However, how to effectively capture these higher-order structures in TGNNs remains underexplored. Another critical challenge in current TGNN research is the limited expressive power ( Xu et al. 2018 ) constrained by efficiency bottlenecks. Existing studies have shown that a TGNN’s expressiveness is crucial for dynamic link prediction ( Souza et al. 2022 ) . One straightforward way to improve expressiveness is to expand the model’s receptive field to include multi-hop neighborhood information ( Xu et al. 2020 ; Wang et al. 2022 ) . However, edges can recur multiple times between the same nodes in temporal graphs ( Poursafaei et al. 2022 ) , therefore, this expansion often leads to an exponential increase in training edges ( Luo & Li 2022 ) , incurring high memory and computational costs. There are methods ( Rossi et al. 2020 ) that introduce a memory module to keep track of evolving features of each node, correspondingly improving the expressive power ( Souza et al. 2022 ) . However, these modules require substantial resources in large-scale networks, and multi-hop aggregation remains necessary to mitigate memory staleness ( Rossi et al. 2020 ) before computing output embeddings. Consequently, overcoming these efficiency constraints while enhancing the model’s expressiveness power remains a significant challenge. Based on these challenges, a natural question arises: Can we design a TGNN that is both expressive and scalable? To address this, we propose a novel Higher-order structure Temporal Graph neural Network (HTGN). To effectively leverage higher-order information, we propose an algorithm that identifies higher-order structures and constructs hyperedges to represent them. Next, HTGN integrates temporal graph learning with hypergraph learning, aggregating multiple edge features into a single hyperedge feature, thereby reducing memory costs. As a result, the hyperedge representations enable the HTGN to incorporate multiple hops of neighborhood information, enhancing the model’s expressiveness. Our main contributions can be summarized as follows: • We highlight the importance of higher-order structures in temporal graph learning. To effectively capture and represent these structures, we formulate the problem of hyperedge construction in temporal graphs and propose an algorithm with a theoretical proof of its validity. • We propose a novel Higher-order structure Temporal Graph neural Network (HTGN) that integrates temporal graph learning with hypergraph learning to better capture higher-order structures for temporal link prediction. Moreover, we theoretically demonstrate that HTGN exhibits greater expressiveness compared to baseline methods. • We conduct extensive experiments on temporal graphs of various sizes and domains. The results demonstrate that HTGN can outperform baseline methods while also reducing memory costs by up to 50%. 2 Related Works Temporal Graph Neural Networks. Temporal graph learning has gained significant attention in recent years, with various kinds of temporal graph neural networks emerging to model dynamic relationships effectively. These methods can be roughly classified into two types: memory-based and subgraph-based. Memory-based methods utilize a memory module to record the evolving dynamics. Kumar et al. 2019 introduced JODIE, a coupled recurrent neural network designed to learn the embedding trajectories of users and items. Similarly, DyRep ( Trivedi et al. 2019 ) focuses on generating low-dimensional node embeddings to encode communication patterns and associations. Rossi et al. 2020 proposed TGN, a temporal graph neural network that incorporates a memory module to maintain and update node representations. Recently, Zhang et al. 2024 integrated the Neural Common Neighbor with TGN, further improving the performance. Subgraph-based methods focus on utilizing temporal neighborhood structures in temporal graph learning. CAWN ( Wang et al. 2022 ) leverages random anonymous walks to model the evolving neighborhood dynamics, while TCL ( Wang et al. 2021 ) constructs a temporal dependency interaction graph to capture sequential cascades of interactions. TGAT ( Xu et al. 2020 ) introduces a temporal graph attention mechanism to process time-aware neighborhood features. Additionally, NAT ( Luo & Li 2022 ) employs a multi-hop neighboring node dictionary to extract joint neighborhood features. GraphMixer ( Cong et al. 2023 ) and DyGFormer ( Yu et al. 2023 ) generate node features by aggregating one-hop neighborhood embeddings and input them to a transformer-based decoder ( Vaswani 2017 ) to produce final predictions. Hypergraph Construction. The problem of hypergraph (re)construction aims at identifying higher-order structures within graphs. Once these structures are identified, they are represented as hyperedges, allowing for the reconstruction of the entire network as a hypergraph. Early studies ( Petri et al. 2013a ; Petri

Read the complete text