HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers
HOT combines 2-hop structure with Block-Recurrent Transformers, improving MOOC accuracy by 9% over DyGFormer.
Key Findings
Methodology
HOT represents historical 1-hop and 2-hop interactions of query nodes u and v in a continuous-time dynamic graph. It combines TGAT sinusoidal time encoding, one-hot hop indicators, and shared-neighbor counts for temporal triangles. Patching and alignment compress the inputs, while a Block-Recurrent Transformer (BRT) applies local block attention plus recurrent state summaries. Average-pooled node representations are passed to a link decoder.
Key Results
- On MOOC, HOT improves accuracy by 9%, 7%, and 15% over DyGFormer, TGN, and GraphMixer, respectively, while leading across AP, AUC, and RNES, HNES, and INES sampling settings.
- On LastFM, 2-hop information generally improves prediction. On CanParl, 1-hop performance is already strong; larger s2 can add noise and produces limited benefit.
- Neighborhood construction costs O(sΔ log Δ), while BRT attention costs approximately O(sdB/P), versus Θ(s²d/P) for vanilla Transformer attention, reducing long-history memory pressure.
Significance
The paper brings higher-order structure, long established in static graph learning, into dynamic link prediction. It addresses a central weakness of update-token models: they may encode who interacted, but not whether the interactions form triangles, shared neighborhoods, or longer temporal patterns. By combining structural enrichment with memory-efficient attention, HOT makes higher-order dynamic reasoning more plausible for real-time recommendation, social analysis, and transaction systems. The results suggest that temporal co-occurrence structure provides predictive information beyond individual events.
Technical Contribution
HOT retains truncated historical neighborhoods Su and Sv; constructs Cu to count a neighbor’s occurrences in its own and the opposite query neighborhood; maps these counts through MLPs into Xu,C and Xv,C; horizontally concatenates the two query-side sequences; and replaces global attention with BRT local attention plus recurrent summaries. The paper analyzes O(sΔ log Δ) preprocessing and near-linear BRT attention, offering an engineering route to longer histories without simply discarding higher-order evidence.
Novelty
Unlike DyGFormer, which primarily treats dynamic updates as sequence tokens, HOT injects k-hop neighborhoods and subgraph evidence involving the queried pair into the Transformer input. Its fundamental novelty is the joint design of higher-order temporal encoding, patching, alignment, horizontal fusion, and hierarchical recurrent attention. The contribution is therefore not merely adding more neighbors; it addresses the accuracy–memory conflict created by those neighbors.
Limitations
- The experiments emphasize 1-hop and 2-hop neighborhoods and triangle-like structures. Since neighborhood size grows roughly with the product of sk values, higher orders rapidly increase preprocessing, storage, and the risk of noisy evidence.
- The supplied text reports relative improvements and plotted trends but not all numerical AP/AUC values from Figure 2, limiting independent assessment of variance, statistical significance, and dataset-level effect sizes.
Future Work
Future work could support arbitrary k-hop structures, conjunctions of cycles, and dynamic node classification or other DGRL workloads. Adaptive selection of s1, s2, patch size P, and block size B could match structural complexity to query difficulty. Further priorities include parallelizing recurrent blocks, improving inductive robustness, and systematically evaluating deletion-heavy, larger-scale industrial graphs.
AI Executive Summary
Dynamic networks generate continuous streams of edge additions, deletions, and feature updates. Dynamic link prediction asks whether a pair of vertices will connect at time t using only events before t. Existing systems such as TGN, GraphMixer, and DyGFormer have made strong progress, but update-token formulations often underrepresent shared neighbors, triangles, and multi-hop context. Adding such context naively lengthens the sequence and makes vanilla Transformer attention prohibitively expensive.
HOT addresses this trade-off by combining higher-order temporal structure with efficient attention. For each query node, it keeps the most recent s1 one-hop interactions and expands them with s2 recent two-hop interactions. TGAT’s learnable sinusoidal time encoding represents elapsed time, while hop indicators distinguish one-hop from two-hop neighbors. Matrix Cu counts shared-neighbor occurrences in the two query neighborhoods; MLPs convert these counts into structural features. Patching merges adjacent rows, alignment projects features to a common dimension, and horizontal concatenation joins the two query-side representations. A Block-Recurrent Transformer then performs local block attention while recurrent states summarize earlier blocks.
Evaluation covers MOOC, LastFM, and CanParl, with TGN, CAWN, TCL, GraphMixer, DyGFormer, and EdgeBank as baselines. AP and AUC are measured under RNES, HNES, INES, transductive, and inductive settings. On MOOC, HOT improves accuracy by 9% over DyGFormer, 7% over TGN, and 15% over GraphMixer. LastFM benefits from higher-order context, whereas CanParl gains little and may become noisier as s2 grows. BRT changes the attention scaling from approximately Θ(s²d/P) to O(sdB/P). HOT therefore shows that dynamic prediction benefits from modeling not only events, but the evolving structures formed by events—while adaptive sampling, parallel recurrence, and broader validation remain open challenges.
Deep Analysis
Background
A continuous-time dynamic graph (CTDG) is represented as (G(0), T), where T contains timestamped node, edge, and feature events. DGRL evolved from temporal random walks, sequential models, memory networks, and dynamic GNNs to systems such as TGN, CAWN, TCL, GraphMixer, and DyGFormer. DyGFormer demonstrated the value of Transformer sequence modeling, but its update-centric representation does not explicitly capture higher-order structures such as shared neighbors and triangles.
Core Problem
Given timestamp t and an edge (u,v), the model must predict whether an event concerning that edge occurs at t using only earlier CTDG history. The task is evaluated transductively and inductively. Long histories already challenge quadratic Transformer attention; adding k-hop neighbors multiplies the token count. Shortening the history saves memory but can erase precisely the structural evidence that higher-order modeling provides.
Innovation
HOT introduces three linked innovations. First, it extracts recent 1-hop and 2-hop historical interactions. Second, it encodes shared-neighbor counts through Cu and MLPs, representing temporal triangles and, more generally, cycles up to length 2k+1. Third, it uses patching, alignment, horizontal fusion, and BRT local-plus-recurrent attention. Compared with DyGFormer, HOT changes both the graph representation and the temporal attention mechanism rather than only increasing model capacity.
Methodology
- �� Retain the latest s1 one-hop interactions for u and v; expand each through s2 recent two-hop interactions, yielding approximately O(s1s2) context.
- �� Build node, edge, and time matrices; use TGAT encoding p^(1/dT)[cos(w1Δt′), sin(w1Δt′), …].
- �� Construct Cu with counts of each neighbor in Su and in Sv; compute Xu,C=MLP0(Cu[:,0])+MLP1(Cu[:,1]).
- �� Patch P adjacent rows and align each feature matrix to dimension d; concatenate node, edge, temporal, and HO channels, then join u and v horizontally.
- �� Feed the result to BRT, which attends within blocks and carries recurrent summaries across blocks; average pooling produces node representations for decoding.
Experiments
The study uses MOOC, LastFM, and CanParl, comparing TGN, CAWN, TCL, GraphMixer, DyGFormer, and EdgeBank. Metrics are Average Precision and AUC. It evaluates transductive and inductive settings with random negative edge sampling (RNES), historical sampling (HNES), and inductive sampling (INES). Ablations vary s2 while fixing s1, and memory studies vary BRT block size B and patch size P against vanilla Transformer attention.
Results
On MOOC, HOT exceeds DyGFormer, TGN, and GraphMixer by 9%, 7%, and 15%, respectively, and remains strongest across sampling regimes. LastFM shows similar benefits from higher-order neighbors. CanParl is already strong with 1-hop information; larger s2 may add noise. With s2=1, the model can capture cycles up to five nodes. BRT attention is approximately O(sdB/P), compared with Θ(s²d/P) for vanilla attention.
Applications
E-commerce platforms can predict future purchases or co-purchases for recommendation and inventory planning; social platforms can predict emerging connections or diffusion paths. Deployment requires timestamped interactions plus node and edge features, followed by tuning s1, s2, B, and P for latency and memory. Transportation, scientific collaboration, transaction monitoring, and real-time risk analysis are also plausible targets.
Limitations & Outlook
Larger higher-order neighborhoods increase preprocessing and memory, while distant context can introduce noise. BRT saves memory, but small blocks increase the number of sequential blocks and may raise latency. The evaluation centers on three datasets, 1/2-hop context, and link prediction; it does not establish broad generalization to deletion-dominated or industrial-scale graphs. Future work should add adaptive sampling, parallel recurrent execution, larger benchmarks, and complete uncertainty reporting.
Plain Language Accessible to non-experts
Imagine a restaurant receiving orders all day. Each customer is a person, and each shared meal or interaction is a time-stamped record. A basic predictor only checks whether two customers directly appeared together. HOT also asks whether they share regular companions, whether those companions repeatedly appear with both customers, and whether these small groups formed recently. Such patterns can signal that the two customers will soon order together.
HOT keeps the most recent direct and indirect relationships, records how long ago each event happened, and counts repeated shared companions. It then bundles nearby records into small packets, like grouping orders by short time windows. Each packet examines its local neighbors while carrying a summary from earlier packets. This lets the model use a long history without opening every past order at once.
On MOOC, HOT improves accuracy by 9% over DyGFormer, 7% over TGN, and 15% over GraphMixer. The lesson is simple: predicting the next connection requires more than remembering who met whom; it requires understanding the small groups those meetings create. Yet including too many distant relationships can become distracting, and the system still needs careful memory and preprocessing control.
ELI14 Explained like you're 14
Picture trying to guess who will become friends at school next week. The easiest clue is whether two students have already chatted. A better clue is whether they share friends, join the same club, or keep appearing in the same group. HOT makes this kind of guess for online networks: it looks beyond direct contact and studies the surrounding friendship pattern.
It checks the recent first layer of connections and then the second layer—friends of friends. It also remembers when each interaction happened, because yesterday’s message should usually matter more than one from last year. If Alex and Bella both often talk with Casey, that triangle is a useful hint that Alex and Bella may connect soon. HOT groups nearby history into blocks, like reviewing chapter summaries instead of every page simultaneously.
Why is this useful? Online relationships are not isolated messages; they form circles, clubs, and repeated patterns. On the MOOC dataset, HOT beats DyGFormer by 9%, TGN by 7%, and GraphMixer by 15%. But looking at too many distant friends can confuse the model, so it must choose how much history to keep. That balance between seeing more and computing less is the clever part!
Glossary
Continuous-Time Dynamic Graph (CTDG)
A graph whose nodes, edges, and features change through timestamped events. Unlike a static snapshot, it represents continuous evolution.
HOT predicts events at time t from CTDG events before t.
Dynamic Link Prediction
Predicting whether a future interaction will occur between a pair of vertices from historical graph activity. It can be transductive or inductive.
This is HOT’s primary downstream task and the basis for comparison with TGN and DyGFormer.
Higher-Order Structure
A relational pattern beyond a single edge, including shared neighbors, triangles, cycles, and multi-hop neighborhoods. It captures indirect dependence among vertices.
HOT focuses on 1-hop and 2-hop histories and the structures they induce.
TGAT Time Encoding
A learnable sinusoidal representation of the elapsed time between an interaction and the prediction time. It preserves continuous temporal differences.
HOT applies it to every historical interaction in Su and Sv.
Block-Recurrent Transformer
A Transformer variant that computes attention within local blocks and carries recurrent state summaries across blocks. It avoids full quadratic attention over the entire sequence.
BRT is HOT’s principal mechanism for reducing higher-order history memory.
Patching and Alignment
Patching merges adjacent temporal rows; alignment projects the resulting vectors into a common dimension. Together they shorten and standardize the Transformer input.
HOT applies both operations before BRT processing.
Open Questions Unanswered questions from this research
- 1 It remains unclear when higher-order expansion produces genuine signal and when it becomes noise. Adaptive, structure-aware sampling and cross-dataset studies are needed to identify useful orders.
- 2 BRT reduces memory but recurrent block processing can limit parallelism. Designing low-latency parallel recurrence without losing long-range temporal information is unresolved.
- 3 The supplied paper text does not provide every AP/AUC value or variance from Figure 2, so statistical significance, robustness, and industrial-scale gains require independent reproduction.
Applications
Immediate Applications
Real-time recommendation and transaction forecasting
E-commerce systems can model users, products, and transactions as a dynamic graph and predict future purchase or co-purchase edges. Timestamped node and edge features are required; s1, s2, B, and P control latency and memory.
Social connection and diffusion prediction
Social platforms can use shared follows, groups, and repeated interactions to predict emerging links or propagation paths. HOT is most suitable when relationships change rapidly and triangle-like patterns are informative; privacy and noise controls remain essential.
Long-term Vision
A general real-time dynamic-graph intelligence engine
HOT could extend to dynamic node classification and other DGRL workloads, combining higher-order structure with long histories. Major obstacles are the cost of higher orders, parallel recurrent execution, and reliable transfer across domains.
Abstract
Many graph representation learning (GRL) problems are dynamic, with millions of edges added or removed per second. A fundamental workload in this setting is dynamic link prediction: using a history of graph updates to predict whether a given pair of vertices will become connected. Recent schemes for link prediction in such dynamic settings employ Transformers, modeling individual graph updates as single tokens. In this work, we propose HOT: a model that enhances this line of works by harnessing higher-order (HO) graph structures; specifically, k-hop neighbors and more general subgraphs containing a given pair of vertices. Harnessing such HO structures by encoding them into the attention matrix of the underlying Transformer results in higher accuracy of link prediction outcomes, but at the expense of increased memory pressure. To alleviate this, we resort to a recent class of schemes that impose hierarchy on the attention matrix, significantly reducing memory footprint. The final design offers a sweetspot between high accuracy and low memory utilization. HOT outperforms other dynamic GRL schemes, for example achieving 9%, 7%, and 15% higher accuracy than - respectively - DyGFormer, TGN, and GraphMixer, for the MOOC dataset. Our design can be seamlessly extended towards other dynamic GRL workloads.