PaperlayerView exact revision on arXiv

Source-linked AI summary

QUARTET: Quad-branch cross-Attention and Random-walk Traces for Enhancing Transformers on Relational Graphs

Kyaw Hpone Myint, Nan Jiang, Xiang Li, Zhe Wu, Alexandre G. R. Day, Pranab Mohanty, Giri Iyengar

arXiv:2609.26855v3cs.LGcs.AI

TL;DR

Relational graph transformers face fragmented local samples and global context limited to seed features. QUARTET combines causal random-walk sampling with four global cross-attention branches. On RELBENCH v1 classification tasks, it matches or outperforms RelGT on eight of twelve tasks and achieves top test ROC-AUC on seven.

  • Problem

    RelGT uses loosely connected local samples and global attention limited to seed features, leaving topology, temporal, and collaborative context unmodeled.

    Source: §1 · p. 2

  • Method

    QUARTET combines causal random-walk local sampling with feature, topology, temporal, and collaborative global cross-attention branches.

    Source: §1 · p. 2, §2.5 · p. 5

  • Results

    QUARTET matches or outperforms RelGT on eight of twelve RELBENCH v1 classification tasks and secures top test ROC-AUC on seven.

    Source: §5 · p. 10

  • Takeaways & Limitations

    Ablations identify local topology as the primary predictive signal on average, while the Perceiver bottleneck improves representation quality over direct full self-attention.

    Source: §4.3 · p. 9

    Evaluation currently covers twelve binary-classification tasks; regression, pair-wise link prediction, and ERP benchmarking remain future work.

    Source: §6 · p. 10

Abstract

from arXiv · show

Relational Deep Learning (RDL) models multi-table databases as heterogeneous temporal graphs, and graph transformers currently achieve state-of-the-art performance on benchmarks like RelBench. However, the current leading model, RelGT, suffers from two key limitations: its random local sampler yields loosely connected subgraphs that hinder message passing, and its global attention module relies on a single, seed-feature-based memory that ignores broader macro-level dynamics. To overcome these limitations, we introduce QUARTET, an expressive graph transformer architecture that applies full self-attention on local subgraphs while enriching global context through cross-attention branches. Specifically, QUARTET employs a Causal Random Walk (CRW) sampler based on recency-truncated Personalized PageRank (PPR) to extract compact, hub-robust, and densely connected local subgraphs without temporal leakage. Concurrently, a quad-branch cross-attention module integrates global context from four complementary perspectives: seed feature, seed topology, temporal dynamics, and collaborative dynamics. Across the RelBench v1 classification tasks, QUARTET consistently matches or outperforms the current state-of-the-art graph transformer baselines (HGT and RelGT). Ablation studies confirm that the CRW sampler significantly enriches local neighborhood quality, while the global branches provide essential, task-specific predictive gains.

1 Introduction

Relational Deep Learning models relational databases as heterogeneous temporal graphs, but graph neural networks face expressiveness and long-range dependency limits. QUARTET addresses two RelGT limitations: fragmented local samples and global context restricted to seed features.

1 Introduction

  • Relational Deep Learning treats database rows as nodes and primary-foreign-key links as edges, enabling end-to-end learning over relational entity graphs.Traditional workflows flattened multi-table data into a feature table through labor-intensive, error-prone feature engineering.Source: §1 · p. 1
  • Message-passing GNNs have bounded expressiveness and struggle with long-range dependencies, while deeper stacks can oversmooth representations.In relational entity graphs, rows may interact only through multi-hop paths via shared parents.Source: §1 · pp. 1–2
  • Graph transformers use attention across structurally distant parts of sampled subgraphs and have become leading supervised RDL models on RELBENCH.HGT handles relational data with meta-relation-dependent attention; RelGT adds a global module querying learnable centroids.Source: §1 · p. 2
  • QUARTET targets RelGT’s fragmented local neighborhoods with causal random walks and its narrow global context with feature, topology, temporal, and collaborative branches.Its CRW sampler ranks neighbors using localized random-walk estimates, regularizes against hubs, and enforces temporal constraints.Source: §1 · p. 2

2 Methodology

QUARTET converts relational data into causal heterogeneous temporal graphs, samples complementary local and global contexts, and processes them with local self-attention and four global cross-attention branches. The resulting embeddings are fused for downstream prediction.

2.1 Relational Entity Graphs (REG)

  • Relational databases become heterogeneous temporal graphs whose nodes represent entities and whose edges represent primary-foreign-key relationships; sampling uses only edges available by the seed prediction time.All local and global samplers are generated per seed and cached for training.Source: §2.1 · p. 3, §2.2 · p. 3

2.2.1 Causal Random Walk (CRW) Local Subgraph Sampler

  • CRW ranks causal neighbors by truncated Monte Carlo estimates of recency-truncated Personalized PageRank, yielding a hub-robust, relevance-weighted local subgraph.Restart walks default to at most 50 recent valid neighbors per step; the branching cap bounds sampling complexity independently of maximum hub degree.Source: §2.2.1 · p. 4

2.2.2 Temporal Global Subgraph Sampler

  • The temporal sampler selects recent causal nodes under per-type budgets, while the collaborative sampler ranks long-horizon peers by two-hop hit counts.Temporal sampling uses a 365-day lookback; collaborative sampling uses shared-intermediary hits to identify peers independently of recency.Source: §2.2.2 · p. 4, §2.2.3 · p. 4

2.3 Graph Tokenization

  • Each local token fuses feature, node type, hop distance, relative time, and GIN positional encodings into one embedding.The fixed-size sequence contains the seed and its CRW-ranked neighbors.Source: §2.3 · p. 4

2.4 Local Attention Module

  • The Local Module applies all-pair self-attention across the CRW-sampled tokens, then pools them into a local representation.This lets attention capture long-range dependencies within strictly causal, structurally dense neighborhoods.Source: §2.4 · p. 5

2.5 Global Attention Module

  • The Global Attention Module uses four seed-conditioned branches: feature and topology codebooks, plus Perceiver-style temporal and collaborative sequence branches.Its shared query-driven bottleneck bounds output dimensionality by a fixed query budget rather than variable neighborhood size.Source: §2.5 · p. 5

2.5.1 Feature and Topological Codebook Branches

  • Feature and topological codebook branches read global archetypes, with the structural query derived from a sketch of causal one-hop connectivity.The sketch captures causal degree, temporal span, arrival density, peak causal-PPR mass, and node-type mix.Source: §2.5.1 · pp. 5–6

2.5.2 Temporal and Collaborative Cross-Attention Branches

  • Separate temporal and collaborative Perceiver bottlenecks compress their neighbor sequences, then their latent blocks exchange information before seed-conditioned readout.Temporal context represents recent activity; collaborative context represents co-occurring multi-hop peers and bypasses recency bias.Source: §2.5.2 · p. 6

3 Experimental Setup

The experiments compare QUARTET with reproduced graph-transformer baselines on RELBENCH v1 classification tasks using a shared updated data pipeline.

3 Experimental Setup

  • The evaluation covers twelve binary-classification tasks from seven RELBENCH datasets and uses test ROC-AUC for models selected on validation performance.The datasets span domains including racing, clinical trials, advertising, e-commerce, fashion retail, and Q&A.Source: §3 · p. 7
  • HGT and RelGT were reproduced from scratch under the shared RELBENCH v2 data-processing pipeline, using the original authors’ reported hyperparameters.The tasks remain the twelve RELBENCH v1 classification tasks to align with prior work.Source: §3 · p. 7
  • All models were trained end-to-end with Adam, and results average four random seeds; large tasks used four A100 GPUs while small tasks used one.Subgraphs were precomputed and cached, and model capacity and selected hyperparameters were configured per task.Source: §3 · p. 7

4 Results and Discussion

QUARTET improves on or matches RelGT on eight of twelve RELBENCH v1 classification tasks, while its CRW sampler matches or exceeds RelGT’s sampler with fewer local attention layers. Ablations show that local topology remains central and the four global branches add complementary, task-dependent gains.

4.2 QUARTET Outperforms RelGT on Most Classification Tasks

  • QUARTET improves on or matches RelGT on eight of twelve RELBENCH v1 classification tasks.Table 1 reports test ROC-AUC and the change relative to RelGT.Source: Table 1 · p. 8, §4.2 · p. 8

4.1 Causal Random-Walk Sampling Allows Better Graph Representation Learning with Fewer Local Attention Layers

  • With RelGT held fixed, the PPR-ranked CRW sampler matches or outperforms BFS2 while requiring fewer local self-attention layers.The comparison varies only the sampler and uses the same local attention architecture and restricted hyperparameter tuning protocol.Source: §4.1 · pp. 7–8, Figure 3 · p. 8

4.3 CRW Enriches Local Context While Global Branches Add Complementary Gains

  • Removing the local module and CRW sampler causes the steepest average drop, 6.7%, while removing the Perceiver bottleneck degrades performance by 2.2% on average.Removing local context improves performance on rel-event user-ignore, indicating that the effect is task-dependent.Source: §4.3 · p. 9, Table 2 · p. 9
  • Replacing CRW with BFS2 degrades performance by 1.6% on average; removing hub truncation or restart causes larger average drops of 1.8% and 2.1%.Without hub truncation and restart, CRW underperforms naive BFS2.Source: §4.3 · pp. 9–10
  • Removing the Temporal, Collaborative, Feature, and Structural branches yields average gains of 2.0%, 1.8%, 1.7%, and 1.5%, respectively, in the full model.No branch is globally redundant; the dominant branch varies by task, with Temporal producing the largest drop on half the tasks.Source: Table 2 · p. 9, §4.3 · p. 10

5 Conclusion

QUARTET combines a Causal Random Walk sampler with Perceiver- and codebook-style cross-attention branches to extend RelGT. On RELBENCH v1 classification, it matches or exceeds RelGT on eight of twelve tasks and achieves top test ROC-AUC on seven.

5 Conclusion

  • QUARTET extends RelGT with a Causal Random Walk sampler and Perceiver- and codebook-style cross-attention branches.The sampler ranks neighbors by causal PPR, and the global branches supply complementary, task-dependent signals alongside local topology.Source: §5 · p. 10
  • On RELBENCH v1 classification, QUARTET matches or outperforms RelGT on eight of twelve tasks and achieves top test ROC-AUC on seven.RelGT retains an edge on a few large, stationary tasks.Source: §5 · p. 10
  • Ablations indicate that CRW improves test performance with fewer attention layers, while global context complements rather than replaces local topology.Removing the local module causes the most severe performance drop; the four global branches provide complementary, task-dependent signals.Source: §5 · p. 10

6 Future Directions

Future work will extend QUARTET beyond its current evaluation on twelve binary-classification tasks. Planned directions include regression, pair-wise link prediction, and benchmarking on the SALT dataset.

6 Future Directions

  • The current evaluation covers twelve binary-classification tasks; regression and pair-wise link prediction are planned extensions.For link prediction, candidate entities would be treated as independent seed nodes and their embeddings scored for relational affinity; regression would use a continuous-output prediction head.Source: §6 · p. 10
  • The authors plan to benchmark QUARTET on the SALT dataset to assess scalability and generalizability in enterprise resource planning environments.Source: §6 · p. 10
  • For pair-wise link prediction, the proposed adaptation extracts enriched graph embeddings for candidate entities treated as independent seed nodes, then applies a shallow classifier.Source: §6 · p. 10

§A.1 Model Details

The appendix model-details section lists topics on neighbor sampling, CRW, collaborative sampling, and token encoders.

§A.1 Model Details

  • The listed model-detail topics are neighbor-sampling algorithms, CRW’s walk kernel and edge cases, collaborative sampling as a two-hop Jaccard-numerator estimator, and token-encoder details.Source: §A.1 Model Details · p. 14

§A.2 Complexity Analysis

Appendix A.2 is organized around sampler complexity, attention-module complexity, and empirical runtime, memory, and storage comparisons.

§A.2 Complexity Analysis

§A.3 Experiment Details

Appendix A.3 lists implementation and training details, tuning and baseline comparisons, per-task hyperparameters, and quad-branch capacity search.

§A.3 Experiment Details

§A.4 Additional Results

Appendix A.4 covers connectivity analysis, full baseline scores, ablation results with seed variability, and reproduction of the RGP baseline.

§A.4 Additional Results

A.1.1 Neighbor Sampling Algorithms

This appendix section documents QUARTET’s causal sampling design and related implementation details, including encoders, computational costs, and training configuration. It reports local-subgraph connectivity comparisons and describes the scope, metrics, and caveats for baseline, ablation, and RGP reproduction results.

A.1.1 Neighbor Sampling Algorithms

  • The three seed-rooted samplers are CRW local walks, a backward-in-time temporal scan, and a two-hop collaborative probe; collaborative hit counts estimate degree-discounted shared-neighbor overlap.The two-hop sampler keeps top-ranked peers, with inverse intermediary-degree weighting down-weighting popular intermediaries; the appendix identifies this as proportional to a Jaccard numerator when shared-intermediary degrees are comparable.Source: §A.1.1 · p. 14, §A.1.3 · pp. 16–17

A.1.4 Token Encoder Details

  • Each token combines encoded node features, entity type, hop, time, and local subgraph positional information before a learned projection mixes the five elements.The positional encoder applies a lightweight GIN to local adjacency and resamples random node features during training to break structural symmetries while preserving permutation equivariance.Source: §A.1.4 · pp. 17–18

A.2.1 Subgraph Sampler Time Complexity

  • Per seed, CRW costs O(WL log Dmax), the collaborative sampler O(M1M2 log Dmax), and temporal sampling O(T log |E| + TB); cached preprocessing adds no traversal overhead during training.CRW’s default recency truncation caps per-step branching independently of hub degree, while temporal sampling uses a global time-sorted event stream and type-balanced budgets.Source: §A.2.1 · p. 18

A.2.2 Attention Module Time Complexity

  • Local full self-attention costs O(LlocalK^2d), while Perceiver bottlenecks reduce temporal and collaborative cross-attention to O(LpercKd).Batch-shared feature and topology codebook projections are reused across seeds; with batch size, codebook size, and width all 512, the passage estimates roughly 0.5 GB memory saved per codebook.Source: §A.2.2 · pp. 18–19

A.2.3 Empirical Runtime, Memory, and Storage Comparison

  • QUARTET uses 2.17–2.30× RelGT’s parameters, 2.58× average peak GPU memory, and 7.76× average cache size across five larger tasks.Per-epoch time is 1.39× RelGT’s on average (as low as 0.84× on rel-amazon/user-churn); inference throughput favors QUARTET on three of five tasks, and precomputation is 1.3–9.7× faster on four of five. The authors attribute the precompute gap partly to baseline implementation differences, not the sampling algorithm, and note that branch subsets can reduce task-specific costs.Source: §A.2.3 · p. 19, Table 4 · p. 20

A.3.2 Hyperparameter Tuning Strategy and Baseline Comparisons

  • QUARTET uses a two-stage tuning strategy: optimize local parameters first, then search global branch capacities, while applying published HGT and RelGT hyperparameters.Training uses Adam at 1×10^-4 with batch size 512; the appendix lists per-task local hyperparameters and reports the capacity grid across 12 tasks averaged over four seeds.Source: §A.3.1 · p. 20, §A.3.2 · pp. 20–21, §A.3.3 · p. 21

A.4.1 Subgraph Connectivity Analysis: CRW extracts denser, more connected subgraphs compared to BFS2

  • Across all 12 tasks, CRW beats BFS2 on average degree, seed-connected ratio, and average component size, and is more token-efficient on 10 tasks.The two rel-event exceptions involve extreme seed fan-out; CRW still matches BFS2 on average degree and seed-connected ratio there.Source: §A.4.1 · p. 23, Figure 5 · p. 24
  • Average degree and seed-connected ratio show CRW’s advantages across tasks, while edge density can favor BFS2 because its sampled subgraphs are smaller.Clustering is zero for both samplers on 10 of 12 tasks because the schemas generally preclude closed triangles; on the two rel-stack tasks that allow them, the clustering gap is at most 0.24.Source: §A.4.1 · pp. 23–25
  • CRW’s connected subgraphs preserve structural signals for GIN positional encoding and let local attention use cohesive neighborhoods rather than disconnected orphan tokens.In representative examples, CRW found 27 distinct nodes where BFS2 found only 5 for a sparse seed, and achieved about 100% seed connectivity for a dense seed where BFS2 reached 70%.Source: §A.4.1 · pp. 22, 25, Figure 4 · p. 23

A.4.2 Validation and Test Scores for All Baselines

  • Table 8 reports validation and test ROC-AUC for HGT, RelGT, and QUARTET across 12 classification tasks, averaged over four seeds under a shared protocol.HGT and RelGT are reproduced baselines, and QUARTET’s test rows match Table 1.Source: §A.4.2 · p. 25, Table 8 · p. 26

A.4.3 Full Ablation Results with Seed Variability

  • Table 9 reports test ROC-AUC for each QUARTET leave-one-out ablation, marking significant drops when the ablation’s upper confidence bound is below the full model’s lower bound.Results are means and standard deviations over four seeds.Source: §A.4.3 · p. 25, Table 9 · p. 27

A.4.4 RGP Baseline Reproduction

  • QUARTET achieved the highest mean ROC-AUC on six tasks in the RGP reproduction, versus four for RelGT and two for RGP.RGP [37] was reproduced with guidance from its authors, but undocumented mechanisms and architectural differences prevent a guaranteed apples-to-apples comparison, so results are presented as best-effort appendix results.Source: §A.4.4 · p. 28, Table 10 · p. 28

Related papers

Loading 2609.26855v3…