CS Paper Radar

HAWKEYE: Seeing One Layer Deeper -- A Cohesion-Aware Structural Channel for Temporal Link Prediction

Jiacheng Ding, Xiaofei Zhang

cs.DB cs.LG ·submitted 2026-08-24 02:31 UTC · v1
top venuebenchmarkcode/data

Abstract

State-of-the-art temporal-link-prediction (TLP) models are, in essence, multi-channel information aggregators: they combine an interaction-history channel, a time-encoding channel, and a structure channel. The first two have been refined relentlessly; the structure channel remains a crude afterthought -- DyGFormer encodes it as a 1--2-bit neighbour-cooccurrence count. We begin with a measurement: on sparse temporal graphs the classical 1-hop common-neighbour signal is near-random (discriminative AUC $\approx 0.50$), because two nodes almost never share a direct neighbour; the genuinely discriminative signal lies one hop deeper -- the 2-hop cohesive bridge, whose discAUC reaches 0.73--0.98, on both bipartite and non-bipartite graphs. Motivated by this, we propose HAWKEYE, a cohesion-aware structural channel that incrementally maintains the classical k-family of cohesiveness indicators (degree $\to$ k-core $\to$ k-truss) and forms 2-hop cohesive-bridge features. HAWKEYE is a drop-in replacement for a temporal-graph model's native structure channel, with no change to the backbone. Swapping HAWKEYE into DyGFormer improves test AP/MRR over the cooccurrence channel by +0.6 to +10.8 points across six multi-seed-validated datasets (uci, enron, USLegis, CanParl, reddit, mooc). On the bipartite recommendation benchmark tgbl-subreddit, a 3-seed single-pass struct-only ablation shows HAWKEYE nearly doubling the baseline test MRR (0.103$\pm$0.003 $\to$ 0.204$\pm$0.005, +10.1 points across all three seeds); the streaming pipeline scales to the 67M-edge tgbl-flight in five minutes per pass. We further characterise when it helps: the gain tracks a graph's training-free 2-hop discAUC and vanishes on degenerate or saturated graphs -- a predictable boundary. All code, data, and figure-generation scripts are released.

DOI
10.1145/3799682.3841168

Closest papers

Nearest neighbours by meaning across the whole index.

MambaTG: Candidate-Aware State Space Modeling for Future Link Prediction on Temporal Graphs

cs.LG ·2026-11-05 ·Nguyen Hong Quan, Sitao Luan, Yilun Zheng, Lihui Chen
similarity 0.65
Abstract

Future link prediction on temporal graphs involves both repeated interactions between previously connected node pairs and first-time interactions between pairs with no prior interaction. While repeated-edge prediction can exploit direct pairwise evidence, unseen-edge prediction must generalize beyond historical recurrence. Existing temporal graph models often exploit signals tied to recurring interactions or historical overlap, which are highly informative for repeated edges but become limited or unavailable for unseen edges, contributing to substantial performance degradation on unseen-edge prediction. Based on this observation, we identify two complementary signals for modeling sequential dynamics beyond historical recurrence: (1) historical-sequence evolution, which captures dependencies among the source node's chronologically ordered interactions, and (2) candidate--history compatibility, which captures how well a candidate fits the source node's evolving history. Based on the decomposition, we propose MambaTG, a candidate-aware Mamba-based framework that jointly models these two signals. Mamba provides a natural mechanism for this design: its selective recurrence captures the evolution of ordered interaction histories, while its input-dependent state transitions allow the history state to adapt to different candidate inputs. Extensive experiments on 13 temporal graph datasets against 13 representative baselines show that MambaTG achieves strong and consistent performance across both repeated and unseen edges while remaining computationally efficient.

0.20

WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

cs.SI ·2026-09-15 ·Longlong Lin, Wei Chen, Pingpeng Yuan, Ruikun Luo, Qiangqiang Dai +1 more
similarity 0.63
Abstract

Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.

0.11

Revisiting Temporal Link Prediction through Structural Proximity

cs.SI cs.LG ·2026-10-28 ·Yuzhang Fei, Yanping Zheng, Lu Yi, Zhewei Wei
hot direction similarity 0.60
Abstract

Existing temporal link prediction methods typically rely on learned temporal representations to capture evolving interaction patterns. In this paper, we show that a classical structural proximity measure can match or outperform these methods without training or learned temporal sequence modeling. We revisit Personalized PageRank (PPR) on historical interaction graphs, using simple sliding-window retention or exponential time decay. Surprisingly, across 14 datasets, Time-decay PPR ranks first on nine and second on four among the compared methods, including datasets with few repeated edges. To understand this result, we examine the historical paths connecting source nodes to previously unseen destinations. We find that such paths contain useful predictive information, and that PPR outperforms a strong neural baseline on queries where historical structure clearly distinguishes the true destination from negative candidates. These results show that strong performance on current benchmarks does not necessarily require complex temporal models. More fundamentally, they raise the question of how much predictive value learned temporal modeling adds beyond historical structural proximity. Our findings motivate reassessing progress in temporal link prediction with strong classical baselines.

0.23

Do Temporal Link Predictors Need Learned Memory? A Smoothed-Count Baseline with a Handful of Parameters

cs.LG cs.AI ·2026-09-28 ·Lisi Qarkaxhija, Ingo Scholtes
similarity 0.59
Abstract

Many temporal link predictors summarize past interactions through learned node representations. We examine whether simple counts of recurring interaction patterns can provide competitive predictions without learning these representations. We propose a temporal link predictor based on statistical language modelling. It pools transition and co-occurrence counts across sources to predict links that a source has never formed. We smooth sparse estimates using destination frequencies or Kneser-Ney continuation counts. A shared log-linear rule combines these estimates with popularity, source history, and recency, without node embeddings. In our main evaluation, the model achieves the highest MRR among the compared methods on 7 out of 16 datasets from TGB and TGB-Seq. It also outperforms EdgeBank and Base3 on all 16 datasets and the heuristic family on 14. These gains extend to datasets designed to limit repeated edges. With only 9--13 learned parameters, our model provides a simple and competitive baseline for evaluating future neural temporal link predictors.

0.33

DyNA-Mixer: Decoupling Time and Topology for Scalable Dynamic Node Affinity Prediction

cs.LG ·2026-11-18 ·Yuanxing Zheng, Liping Wang, Xuemin Lin
benchmark similarity 0.58
Abstract · Includes appendices

Continuous-time dynamic graphs preserve the ordering, timing, and evolving strength of interactions that static snapshots discard, making dynamic graph mining essential for evolving systems such as recommender systems, trade networks, and transaction platforms. Research in this area has centered on dynamic link prediction, which forecasts only whether a future interaction will occur, whereas many applications also need its intensity. The dynamic node affinity prediction (DNAP) problem generalizes this task to continuous targets and full-candidate ranking, making it more broadly applicable but substantially harder. This raises two coupled difficulties: ranking requires a predictor expressive enough to capture both multi-scale temporal evolution and graph-wide collaborative patterns, yet running such a predictor over every source--destination pair is computationally prohibitive. We propose DyNA-Mixer, which decouples temporal forecasting from collaborative structure modeling. It adopts a multi-scale temporal predictor for pair-specific affinity evolution, constructs a Virtual Collaborative Graph that infers query-time relationships and aggregates trends from related interactions, and fuses the two through a gated residual mechanism. A sparsity-aware evaluation strategy further restricts expensive forecasting to pairs with recent non-zero affinities. Experiments on four Temporal Graph Benchmark datasets for the DNAP problem show that DyNA-Mixer achieves new state-of-the-art NDCG@10 on every dataset, including a 17.8\% relative test improvement over the strongest baseline on tgbn-token, the largest dataset.

0.10

Dynamic Graph World Modelling: Learning Future Dynamics from Temporal Context

cs.LG ·2026-10-14 ·Bo Li, Yue Yang, Yujin Huang, Siao Liu, David Lemphers +4 more
similarity 0.58
Abstract

Dynamic graph learning models how entities and their relations evolve from historical observations to predict future graph states. Existing methods do not fully address dynamic graph world modelling, which requires learning transitions from temporal context to future latent graph states. This is difficult for three reasons: nodes and relations rely on different historical evidence, structural evolution is path-dependent, and future snapshots provide sparse and realization-specific targets. We propose Dynamic Graph World Modelling (DyG-WM), the first framework to jointly predict future node and relation representations from temporal context by answering three questions: what has evolved, how it evolved, and what will evolve next. To capture what has evolved, a historical node-relation context encoder summarizes node-neighborhood trajectories and pair-specific histories. To characterize how it evolved, a node-relation path-signature encoder captures ordered structural changes. To predict what will evolve next, a dual-level joint-embedding objective predicts target-snapshot node and relation representations without reconstructing the raw graph. Experiments on 12 link-prediction and two node-classification datasets demonstrate the effectiveness of DyG-WM across both tasks.

0.04

A Topological Encoder Decoder Framework for Temporal Graph Learning

cs.AI cs.LG ·2026-11-07 ·Ronan Buck, Kiarash Shamsi, Tran Gia Bao Ngo, Astrit Tola, Baris Coskunuzer +1 more
similarity 0.58
Abstract

Most temporal graph learning methods reduce future prediction to discriminative inference over past interactions, focusing on edges or node labels for a largely persistent set of nodes. This view breaks down when new nodes and edges appear, since the future graph becomes a new object with changing size, composition, and structure. We address this gap by framing temporal graph prediction as an inverse topology problem. Instead of predicting edges directly, we first predict a multiscale topological descriptor of the future graph and then reconstruct a plausible future snapshot that realizes this descriptor under inductive constraints. This approach makes global structure and node churn explicit prediction targets and produces forecasted graphs that downstream tasks can evaluate without retraining. Across 14 temporal graph datasets, we evaluate our method, TOPOGED, on node, link, and graph property prediction and compare it against state-of-the-art temporal graph models. TOPOGED significantly improves node-level forecasting accuracy over the strongest baseline, with a macro average of 0.49 versus 0.05. It also outperforms baselines in 60% of graph-structure metric evaluations and substantially increases macro-average edge prediction metrics, from near-zero to 0.12. Our results show that topology-guided graph forecasting can predict inductive future snapshots whose structure supports multiple downstream evaluations.

0.15

Inferring Hidden Structural Changes from Node-State Responses under Partial Network Observations

cs.SI ·2026-10-12 ·En Xu, Jingtao Ding, Yong Li
similarity 0.57
Abstract

Online platforms often expose activity signals even when records of the underlying connections are incomplete or delayed. These activity responses may retain indirect evidence of connections that formed during the observation period but are absent from the recorded topology. Recovering such hidden structural changes can help keep network records aligned with evolving interactions and support downstream network analysis. However, the effects of a change propagate through the network and may overlap, making state changes difficult to associate with specific connections. We propose the Hierarchical Structural Context Ranker (HSCR), which combines visible network structure with node-state changes to infer connections that have formed but remain unrecorded. By jointly modeling the topological context of state responses and associations among potential connections, HSCR converts distributed activity changes into evidence for distinguishing potential connections without prespecified dynamical equations or parameters. Experiments on five temporal-network benchmarks and a real temporal Reddit network validate its effectiveness. Across observation spans and structural-record delays, true added connections achieve a 36%-50% reduction in mean true rank relative to the corresponding best baselines. This work provides a principled way to prioritize unrecorded additions for structural verification and record maintenance in online communities, information networks, and other networked systems.

0.23