PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jiacheng Ding, Xiaofei Zhang

arXiv:2608.22727v1cs.DBcs.LG

TL;DR

Sparse temporal graphs make 1-hop common-neighbour structure nearly random, leaving a gap in temporal-link-prediction structure channels. HAWKEYE fills it with incrementally maintained k-family and 2-hop cohesive-bridge features as a drop-in backbone channel, improving performance across validated datasets while exposing predictable saturation and cold-start boundaries.

  • Problem

    On sparse temporal graphs, common-neighbour structure channels are near-random even though temporal-link-prediction models depend on a structural signal alongside interaction and time channels.

  • Method

    HAWKEYE incrementally maintains degree, k-core, and k-truss indicators and forms 2-hop cohesive-bridge features as a drop-in replacement for a model’s native structure channel.

  • Results

    +0.6 to +10.8 points in test AP/MRR over DyGFormer’s cooccurrence channel across six multi-seed-validated datasets.

  • Takeaways & Limitations

    HAWKEYE’s gains track training-free 2-hop discAUC and disappear on degenerate or saturated graphs, making its applicability boundary predictable.

  • Takeaways & Limitations

    Cohesion-only HAWKEYE can underperform on unseen-node queries because cached cohesion features for new nodes are zero or near zero; combining it with cooccurrence largely recovers the loss.

Abstract

from arXiv · show

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.

1 Introduction

Temporal-link-prediction models refine interaction and time channels while relying on weak 1-hop structure signals. Measurements show that sparse graphs instead expose stronger 2-hop cohesive-bridge structure, motivating HAWKEYE as a drop-in structural replacement.

  • Temporal-link prediction forecasts new edges in evolving graphs and supports recommendation, fraud detection, and other applications.
  • State-of-the-art models aggregate interaction-history, time-encoding, and structure channels, but the structure channel often uses only neighbour cooccurrence or common-neighbour counts.
  • discAUC ≈0.50 for 1-hop common neighbours and 0.73–0.98 for 2-hop cohesive bridges on sparse temporal graphs, across bipartite and non-bipartite settings.The deciding factor is sparsity rather than graph type.
  • HAWKEYE incrementally maintains degree, k-core, and k-truss indicators and forms 2-hop cohesive-bridge features without changing the temporal model backbone.It is designed as a drop-in replacement for the native structure channel.
  • +0.6 to +10.8 points in test AP/MRR over DyGFormer’s cooccurrence channel across six multi-seed-validated datasets.The combined channel is strongest on every non-saturated multi-seed dataset, while structural precomputation yields a uniform 3.0–3.5× training speedup.

2 Preliminary

The paper formalizes temporal link prediction on continuously evolving graphs and introduces a hierarchy of increasingly strict cohesiveness indicators. Its 2-hop cohesive bridge measures structurally embedded candidate pairs beyond direct common neighbours.

  • 2.1 Problem Formulation: A temporal graph is represented as a time-ordered stream of timestamped edges, with cumulative snapshots formed from all events up to each native timestamp.
  • 2.1 Problem Formulation: Temporal link prediction scores candidate destinations so the truly occurring edge ranks highest, using MRR on TGB and AP on DGB evaluations.
  • 2.2 The k-family of Cohesiveness Indicators: The k-family is a paper-specific hierarchy of node-level cohesiveness indicators with increasingly strict local constraints: degree, k-core, and k-truss.
  • 2.2 The k-family of Cohesiveness Indicators: k-truss is a tight proxy for the hierarchy’s clique limit because it requires triangle support, whereas the paper does not use k-clique directly because finding large cliques is NP-hard.
  • 2.3 The 2-hop Cohesive Bridge: The 2-hop cohesive bridge counts direct neighbours of v reachable from u in two hops, optionally weighting them by intermediary cohesiveness.This captures shared structural communities even when direct common-neighbour counts are zero.
  • 2.3 The 2-hop Cohesive Bridge: In the Alice–Bob example, CN = 0 but bridge = 2, and core-weighting gives bridge_c = 5 + 4 = 9.These bridges are the slot input passed from the cache to Hawkeye’s model channel.

3 Empirical Study: Why Existing Structural Signals Fail

The study finds that 1-hop common-neighbour signals are weak or degenerate across sparse and bipartite temporal graphs, while 2-hop cohesive bridges are generally more discriminative. It further identifies k-core as the practical sweet spot and shows that structural augmentation helps within predictable graph regimes.

  • discAUC 0.50: 1-hop common neighbours are near-random on sparse datasets, while 2-hop cohesive bridges reach 0.73–0.85.The sparse regime includes tgbl-uci, tgbl-enron, and tgbl-wiki.
  • discAUC 0.50, 0.09, and 0.43: 1-hop common neighbours are structurally crippled on tgbl-subreddit, mooc, and reddit, whereas 2-hop bridges reach 0.94–0.98.The bipartite regime is where the 2-hop signal dominates.
  • 0.48–0.56: simple 2-hop bridge counts saturate on near-complete CanParl and USLegis graphs, although trained Hawkeye still improves performance by +10.8 and +4.8 points.In these graphs, 1-hop common neighbours are slightly informative at 0.60–0.63.
  • At most 0.01: core-weighting changes 2-hop discAUC only marginally, indicating that 2-hop topology is the dominant signal and k-family weighting is a refinement.On uci, core-weighted and raw 2-hop discAUC are 0.76 and 0.75, respectively.
  • +6.0 points: adding k-core to degree raises struct-only test MRR from 0.120±0.004 to 0.180±0.011 on tgbl-uci, while k-truss reduces it to 0.166±0.007.K-truss also costs an order of magnitude more compute: O(m^1.5) versus O(m).
  • The design therefore reads structure at 2 hops, defaults to k-core, and exposes weighted and unweighted features for model selection.These implications follow from the empirical signal and efficiency comparisons.

4 Method: Hawkeye

Hawkeye replaces a temporal model’s native structure encoder with an incrementally maintained cohesion channel that supplies 2-hop and k-family features through the same interface. Its streaming design preserves chronological evaluation while moving structural computation to the CPU and leaving the backbone unchanged.

  • Hawkeye maintains adjacency and k-family indicators incrementally over the edge stream, optionally evicting edges through a sliding window.Degree updates are O(1), core updates affect a small local set, and trussness is available at higher cost.
  • For each historical-neighbour slot, Hawkeye emits a cohesion vector centered on the 2-hop bridge and its core-weighted variant.The full backend is approximately 20-dimensional; a 6-dimensional fast backend is available for very large graphs.
  • One encoder is swapped at the native interface, while the Transformer backbone and per-slot input sum remain unchanged.The GPU receives only the cohesion slot encoder and unchanged DyGFormer computation.
  • P1–P7 score each chronological batch using strictly earlier graph history, and P8 commits the batch edges only after scoring.This predict-then-advance contract prevents the batch’s own edges from entering its structural features.
  • Cache resets, chronological evaluation, and training-stream replay enforce that structural features reflect exactly the graph state before each scored edge.The corrected protocol addresses leakage from future or double-counted edges.
  • No added GPU burden: structural computation runs on the CPU and the GPU gains only a small MLP of approximately 10^3 parameters.The cache uses approximately 10–20 MB on tgbl-wiki, while precomputation reduces runtime overhead by approximately 3×.

5 Experiments

Experiments compare Hawkeye with native structure channels under fixed-backbone, multi-seed, large-graph, predictive-boundary, and efficiency analyses. Hawkeye improves performance where 2-hop cohesion is informative, but has cold-start and pairwise-scaling limits.

  • Experimental setup: The experiments use DyGFormer structure-channel swaps, same-backbone controls, and comparisons with TGAT, GraphMixer, TGN, and EdgeBank under TGB and DGB protocols.TGB uses chronological 70/15/15 splits and MRR with curated negatives; DGB uses AP/AUC with random negatives.
  • Effectiveness: +10.8 points: Hawkeye raises CanParl test AP from 0.708±0.008 to 0.816±0.001, the largest single-dataset improvement observed across three seeds.USLegis gains +4.8 points and mooc gains +5.8 points under the same current pipeline.
  • Limitations: New-node AP drops to 0.657±0.014 with +Hawkeye on tgbl-enron, a −22.8-point change relative to cooccurrence, while ⊕Hawkeye recovers AP to 0.866±0.009.The cohesion cache assigns unseen nodes zero structural values, depressing their scores.
  • Limitations: A 3-seed sweep at tgbl-review is unavailable because retries OOM at the 4.87M-edge scale when pairwise-cohesion adjacency exceeds the single-GPU memory ceiling.The seed-0 run completes in 36.8 minutes.
  • Scalability and large graphs: +10.1 test-MRR points: on tgbl-subreddit, Hawkeye increases struct-only performance from 0.103±.003 to 0.204±.005 across three seeds.The degree-only baseline completes in ∼5 minutes per pass on tgbl-flight with 67M edges, while full pairwise cohesion exceeds one hour above ∼5M edges.
  • Effectiveness: +2.8 points: replacing DyGFormer’s structure channel raises tgbl-wiki test MRR from 0.779 to 0.807, exceeding the published DyGFormer result of 0.798.This result is single-seed, while the six DGB swap-in results are 3-seed validated.
  • Analysis: Hawkeye’s gain spans 0.0 to +10.8 points and tracks the training-free 2-hop discAUC, vanishing on degenerate or saturated graphs.The combined ⊕Hawkeye configuration preserves complementary cooccurrence information and is recommended when unseen nodes are expected.
  • Efficiency: Precomputation yields a uniform 3.0–3.5× speedup and reduces Hawkeye’s measured per-epoch overhead by ∼3×, despite the default add configuration increasing end-to-end time by +154%.The offline feature phase is amortised across subsequent runs, sweeps, and ablations.

6 Related Work

Prior temporal-link-prediction methods either omit structural information or rely on 1-hop common-neighbour signals. HAWKEYE instead uses incrementally maintained k-family structure to construct 2-hop pairwise features in continuous time.

  • Temporal-link-prediction methods span memory-based, attention-based, matrix-projection, and signal-specific families, but their structure channels are often absent or limited to 1-hop common neighbours.
  • Static link prediction uses heuristic and subgraph-based structural features, whereas dynamic approaches have applied k-core or k-truss mainly through separate snapshot GCNs on small datasets.
  • HAWKEYE differs by operating continuously, using the k-family as a substrate for 2-hop pairwise features, and validating at large TGB/DGB scale.
  • Existing k-core and k-truss work primarily optimizes decomposition and streaming maintenance, while HAWKEYE builds prediction-oriented features on top of these computational modules.

7 Conclusion

The paper identifies a structural gap in temporal-link prediction and addresses it with HAWKEYE, an incrementally maintained k-family channel for 2-hop cohesive-bridge features. Its benefits are strongest on informative, non-saturated graphs, with applicability predicted by training-free 2-hop discAUC.

  • HAWKEYE improves DyGFormer by +0.6 to +10.8 points across six multi-seed-validated TGB and DGB datasets.
  • HAWKEYE is an incrementally maintained, cohesion-aware structure channel built on the k-family and instantiated as a DyGFormer drop-in.
  • The applicability boundary is predictable from a training-free 2-hop discAUC measurement, while data-determined slot features support a one-time precomputation with 3.0–3.5× training speedup.

GenAI Usage Disclosure

Generative-AI tools assisted with manuscript language editing and code documentation; the authors state that the research and conclusions are their own and that AI-assisted passages were reviewed.

  • Generative-AI tools were used for language editing and documenting the released code, while the authors retain responsibility for the research ideas, methods, experiments, analyses, and conclusions.
  • The authors state that every AI-assisted passage was reviewed and verified by them.
Loading 2608.22727v1…