QUARTET：四分支交叉注意力与随机游走痕迹，用于增强关系图上的Transformer模型

# Quartet: QUad-branch cross-Attention and Random-walk Traces for Enhancing Transformers on Relational Graphs
Source: [https://arxiv.org/html/2609.26855](https://arxiv.org/html/2609.26855)
###### Abstract

Relational Deep Learning \(RDL\) models multi\-table databases as heterogeneous temporal graphs, and graph transformers currently achieve state\-of\-the\-art performance on benchmarks likeRelBench\. 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 introduceQuartet, an expressive graph transformer architecture that applies full self\-attention on local subgraphs while enriching global context through cross\-attention branches\. Specifically,Quartetemploys 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 theRelBenchv1 classification tasks,Quartetconsistently 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\.

11footnotetext:First and corresponding author\.22footnotetext:Equal contribution second authors\.## 1Introduction

*Relational databases*\(RDBs\)\[[1](https://arxiv.org/html/2609.26855#bib.bib25)\]form the backbone of industrial machine learning by archiving extensive real\-world datasets, such as financial logs and medical records\. Through their interconnected, multi\-table architectures, RDBs leverage primary\-foreign key dependencies to explicitly trace how different entities engage and change over time\. Predictive tasks over these databases, such as churn, sales forecasting, and recommendation, are central to modern enterprise machine learning\. Yet extracting predictive signal from this data has historically required flattening its multi\-table structure into a single feature table through labor\-intensive, error\-prone feature engineering\[[2](https://arxiv.org/html/2609.26855#bib.bib12)\]before handing it to tabular learners such as gradient\-boosted decision trees\[[3](https://arxiv.org/html/2609.26855#bib.bib26),[4](https://arxiv.org/html/2609.26855#bib.bib37)\]\.

*Relational Deep Learning*\(RDL\) removes this bottleneck by treating an RDB as a heterogeneous temporal graph\[[5](https://arxiv.org/html/2609.26855#bib.bib5),[6](https://arxiv.org/html/2609.26855#bib.bib6),[7](https://arxiv.org/html/2609.26855#bib.bib7)\]\(rows become nodes and primary\-foreign\-key links become edges\) and learning end\-to\-end over the resulting*relational entity graph*\(REG\)\[[8](https://arxiv.org/html/2609.26855#bib.bib27),[9](https://arxiv.org/html/2609.26855#bib.bib11),[10](https://arxiv.org/html/2609.26855#bib.bib39),[11](https://arxiv.org/html/2609.26855#bib.bib40),[12](https://arxiv.org/html/2609.26855#bib.bib24)\]\. The standard RDL model is a heterogeneous message\-passing GNN with time\-aware neighbor sampling and per\-type tabular encoders\[[13](https://arxiv.org/html/2609.26855#bib.bib1),[14](https://arxiv.org/html/2609.26855#bib.bib33),[15](https://arxiv.org/html/2609.26855#bib.bib3),[16](https://arxiv.org/html/2609.26855#bib.bib4)\]\. While such models capture local structure well, they inherit the documented limitations of message passing: bounded expressiveness\[[17](https://arxiv.org/html/2609.26855#bib.bib28),[18](https://arxiv.org/html/2609.26855#bib.bib29),[19](https://arxiv.org/html/2609.26855#bib.bib30)\]and an inability to model long\-range dependencies without oversquashing information through narrow bottlenecks\[[20](https://arxiv.org/html/2609.26855#bib.bib31)\]\. These limits are acute on REGs, where two rows in the same table interact only through multi\-hop paths that traverse shared parents: a shallow GNN cannot connect them, yet stacking layers to reach them induces over\-smoothing\.

*Graph Transformers*\(GTs\) circumvent these topological constraints by replacing fixed\-hop message passing with attention that reasons across structurally distant parts of the sampled subgraph\[[21](https://arxiv.org/html/2609.26855#bib.bib32),[22](https://arxiv.org/html/2609.26855#bib.bib18),[23](https://arxiv.org/html/2609.26855#bib.bib20),[24](https://arxiv.org/html/2609.26855#bib.bib35),[25](https://arxiv.org/html/2609.26855#bib.bib19),[26](https://arxiv.org/html/2609.26855#bib.bib41),[27](https://arxiv.org/html/2609.26855#bib.bib42),[28](https://arxiv.org/html/2609.26855#bib.bib43),[29](https://arxiv.org/html/2609.26855#bib.bib44),[30](https://arxiv.org/html/2609.26855#bib.bib45),[31](https://arxiv.org/html/2609.26855#bib.bib46),[32](https://arxiv.org/html/2609.26855#bib.bib34)\]\. GTs have thus emerged as a leading supervised RDL model, topping the standardizedRelBenchbenchmark\[[33](https://arxiv.org/html/2609.26855#bib.bib36),[34](https://arxiv.org/html/2609.26855#bib.bib9)\]\. Notable architectures include the Heterogeneous Graph Transformer \(HGT\)\[[35](https://arxiv.org/html/2609.26855#bib.bib2)\], which accommodates relational data using meta\-relation\-dependent attention and relative temporal encodings\. The Relational Graph Transformer \(RelGT\)\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]augments a local\-subgraph transformer with a global module that queries*learnable centroids*maintained by an EMA K\-Means clustering\. Meanwhile, the Relational Graph Perceiver \(RGP\)\[[37](https://arxiv.org/html/2609.26855#bib.bib10)\]compresses structural and temporal context through a Perceiver cross\-attention bottleneck, making time an active modeling signal rather than just a filtering constraint\.

Building upon these advances, our work addresses two specific limitations in the strongest GT baseline, RelGT\. First, its local sampling yields a loosely connected subgraph: RelGT populates each seed’s neighborhood by drawing one\- and two\-hop nodes largely at random, so many sampled nodes end up with no edge to the seed \(or to one another\) inside the subgraph, leaving the local transformer to pass messages across a fragmented, sparsely linked set of nodes\. Second, its global context is narrow: RelGT’s global module attends only over the seed’s features, with no view of the seed’s surrounding topology or of broader signals such as which entities are active at the same time \(temporal context\) or behave in similar ways \(collaborative context\), so relevant context that lives in structurally distant parts of the graph never reaches the model\. The first gap motivates our Causal Random Walk sampler, which concentrates the local subgraph on structurally relevant neighbors; the second motivates our quad\-branch global module, which integrates feature, topological, temporal, and collaborative contexts to enrich the graph representation\.

##### Contributions\.

To address these challenges, we introduceQuartet, a unified architecture that overcomes the limitations of existing relational deep learning models by seamlessly integrating enriched, localized structural dynamics with global, structurally distant graph contexts\. Concretely, our main contributions are:

1. 1\.A Causal Random Walk \(CRW\) Sampler for Enriching Local Subgraphs:We propose a causal graph sampler that ranks a node’s neighbors based on localized random\-walk estimations rather than uniform expansion\. By regularizing against high\-degree hubs and strictly enforcing temporal constraints, this approach extracts highly relevant, densely connected local subgraphs, which improves local message passing\.
2. 2\.Task\-Optimized Global Memory via Differentiable Codebooks:We introduce dual memory banks that capture recurring tabular and structural patterns\. Using branch\-specific cross\-attention, the model assigns each seed node a soft membership to these global archetypes, effectively generalizing across disconnected seeds that share similar features or local topology profiles\.
3. 3\.Asymmetric Cross\-Attention for Distant Relational Context:To capture long\-range temporal and collaborative dynamics, we design two specialized global branches\. A Perceiver\-style bottleneck compresses sprawling sequences of distant neighbors into fixed\-capacity latents, enabling efficient macro\-level reasoning across structurally distant graph nodes\.

## 2Methodology

In this section, we introduceQuartet\(QUad\-branch cross\-Attention and Random\-walk Traces for Enhancing Transformers on relational graphs\), a general\-purpose Transformer architecture designed for representation learning on heterogeneous temporal relational graphs\. By seamlessly integrating fine\-grained, local structural dynamics with global, structurally distant graph contexts,Quartetprovides a highly expressive framework for complex relational data\.

Figure 1:Overview of theQuartetpipeline\.\(1\)Relational tables are converted into a heterogeneous temporal graph \(§[2\.1](https://arxiv.org/html/2609.26855#S2.SS1)\)\.\(2\)Three causal samplers extract complementary context: CRW draws a dense*local*subgraph, while temporal and collaborative samplers gather*global*node sequences \(§[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)\)\.\(3\)Nodes are tokenized into fixed\-length sequences \(§[2\.3](https://arxiv.org/html/2609.26855#S2.SS3)\)\.\(4\)Local subgraphs feed into self\-attention, while global sequences pass through a quad\-branch cross\-attention module before final fusion \(§[2\.5](https://arxiv.org/html/2609.26855#S2.SS5)\)\.Figure[1](https://arxiv.org/html/2609.26855#S2.F1)gives an end\-to\-end overview of theQuartetpipeline \(graph construction, causal local and global sampling, tokenization, and attention\-based prediction\), while Figure[2](https://arxiv.org/html/2609.26855#S2.F2)details the model architecture\. This architecture is driven by three core components: \(1\)a Causal Random\-Walk \(CRW\)subgraph sampler, which constructs a localized subgraph by ranking neighbors according to their recency\-truncated Personalized PageRank \(PPR\)\[[38](https://arxiv.org/html/2609.26855#bib.bib38),[39](https://arxiv.org/html/2609.26855#bib.bib15),[40](https://arxiv.org/html/2609.26855#bib.bib16),[41](https://arxiv.org/html/2609.26855#bib.bib14)\]relative to the seed—accumulated over short restart walks so that only the most topologically relevant neighbors are retained; \(2\)a Local Module, which processes this sampled subgraph with full self\-attention to capture fine\-grained structural and temporal dependencies; \(3\)a Global Module, which captures macro\-level graph dynamics via a quad\-branch design\. Within this module, the feature and topology branches extract global archetypes for the seed nodes, while the temporal and collaborative branches identify similarities across structurally distant nodes\.

We structure this section as follows: §[2\.1](https://arxiv.org/html/2609.26855#S2.SS1)details graph construction, §[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)introduces the causal samplers, §[2\.3](https://arxiv.org/html/2609.26855#S2.SS3)covers tokenization, §[2\.4](https://arxiv.org/html/2609.26855#S2.SS4)and §[2\.5](https://arxiv.org/html/2609.26855#S2.SS5)present the Local and Global Attention Modules, and §[2\.6](https://arxiv.org/html/2609.26855#S2.SS6)outlines their fusion\.

### 2\.1Relational Entity Graphs \(REG\)

To enable end\-to\-end learning without manual feature engineering, we convert relational databases into Relational Entity Graphs \(REGs\), the first stage of the pipeline in Figure[1](https://arxiv.org/html/2609.26855#S2.F1)\. Formally, we model a REG as a heterogeneous temporal graphG=\(V,E,ϕ,ψ,τ\)G=\(V,E,\\phi,\\psi,\\tau\), whereVVis the set of nodes \(entities\) andE⊆V×VE\\subseteq V\\times Vis the set of edges \(primary\-foreign key relationships\)\. The mapping functionsϕ:V→𝒯\\phi:V\\to\\mathcal\{T\}andψ:E→ℛ\\psi:E\\to\\mathcal\{R\}assign nodes and edges to their respective source tables \(node types\) and relation types, where𝒯\\mathcal\{T\}is the set of node types \(with\|𝒯\|\|\\mathcal\{T\}\|their number\) andℛ\\mathcal\{R\}is the set of relation types\. Finally,τ:V∪E→ℝ\\tau:V\\cup E\\to\\mathbb\{R\}assigns timestamps to temporal entities, treating atemporal nodes as universally available and inducing edge timestamps as the maximum of their endpoints,τ⁡\(e\)=max⁡\{τ⁡\(u\),τ⁡\(v\)\}\\tau\(e\)=\\max\\\{\\tau\(u\),\\tau\(v\)\\\}fore=\(u,v\)∈Ee=\(u,v\)\\in E\.

Given a seed nodevi∈Vv\_\{i\}\\in Vand a prediction timetseedt\_\{\\mathrm\{seed\}\}, the objective is to produce an embedding ofviv\_\{i\}strictly conditioned on information available at or beforetseedt\_\{\\mathrm\{seed\}\}, thereby enforcing a strict causal constraint that prevents temporal leakage\. We enforce this constraint uniformly across the three samplers of §[2\.2](https://arxiv.org/html/2609.26855#S2.SS2): every edge traversed during sampling satisfiesτ⁡\(e\)≤tseed\\tau\(e\)\\leq t\_\{\\mathrm\{seed\}\}\.

### 2\.2Causal Samplers for Local and Global Context

Quartetutilizes three seed\-rooted causal samplers: CRW, temporal, and collaborative \[Figure[1](https://arxiv.org/html/2609.26855#S2.F1), stage \(2\)\]\. The CRW sampler extracts the causal local subgraph via random walk with restart and also provides the structural sketch for the topological codebook branch\. In parallel, the temporal and collaborative samplers generate the fixed\-length global neighbor sequences required by their respective Perceiver cross\-attention branches\. Finally, to prevent runtime bottlenecks, all local and global subgraphs are generated once per seed and cached into a memory\-mapped file, eliminating the need for graph traversals during training\.

#### 2\.2\.1Causal Random Walk \(CRW\) Local Subgraph Sampler

Most standard subgraph extractors fill aKK\-token context by uniform neighborhood sampling or rigid per\-type budgeting\[[13](https://arxiv.org/html/2609.26855#bib.bib1),[42](https://arxiv.org/html/2609.26855#bib.bib13),[35](https://arxiv.org/html/2609.26855#bib.bib2)\]\. On graphs with high\-degree hubs these are both computationally prohibitive \(scaling with hub degree\) and structurally blind \(treating all neighbors equally\)\. Consequently, they exhaust the token budget on random, disconnected slices of massive hubs, yielding sparse subgraphs that severely bottleneck downstream message passing\.

To address this limitation, our CRW sampler performs short restart walks from the seed node, ranking neighbors based on a truncated Monte\-Carlo estimate of their causal PPR\[[38](https://arxiv.org/html/2609.26855#bib.bib38),[39](https://arxiv.org/html/2609.26855#bib.bib15),[40](https://arxiv.org/html/2609.26855#bib.bib16),[41](https://arxiv.org/html/2609.26855#bib.bib14)\]\. At each step, the walk either teleports back to the seed with probabilitypp, or transitions to one of up toMMvalid causal neighbors of the current node\. By default, we restrict this transition to theM=50M=50most recent neighbors, thereby injecting a strong temporal prior into the sampling process\. Accumulating visit frequencies acrossWWindependent walks of lengthLLyields an empirical estimate of the seed’s causal PPR, which converges to the exact distribution asM,W→∞M,W\\to\\infty\(Appendix[A\.1\.2](https://arxiv.org/html/2609.26855#A1.SS1.SSS2)\)\.

Crucially, thisMM\-truncation serves as a structural regularizer\. By capping the per\-step branching factor, it bounds the sampling complexity independently of the maximum hub degree and prevents massive hubs from acting as probability sinks\. Consequently, the highest\-ranked nodes, sharing dense structural pathways with the seed, induce a highly connected and relevance\-weighted local subgraph\. Detailed derivations of the walk kernel, PPR equivalence, subgraph connectivity, and sparse\-neighborhood fallback policies are provided in Appendix[A\.1\.2](https://arxiv.org/html/2609.26855#A1.SS1.SSS2)\. The exact per\-seed procedure is detailed in Algorithm[1](https://arxiv.org/html/2609.26855#alg1)\(Appendix[A\.1\.1](https://arxiv.org/html/2609.26855#A1.SS1.SSS1)\), with a full computational cost analysis in Appendix[A\.2\.1](https://arxiv.org/html/2609.26855#A1.SS2.SSS1)\.

#### 2\.2\.2Temporal Global Subgraph Sampler

While the temporal branch requires a global view of recent graph activities, naively selecting the top\-KKmost recent nodes causes high\-frequency tables \(e\.g\., transactions\) to disproportionately bias the sample, thereby starving slower\-moving dimension tables\. To address this, the temporal sampler extracts the most recent causal nodes*per node type*under a uniform type\-specific budgetB=Ktemp/\|𝒯\|B=K\_\{\\mathrm\{temp\}\}/\|\\mathcal\{T\}\|, strictly retaining nodes within a temporal lookback window\[tseed−Δ​t,tseed\]\[t\_\{\\mathrm\{seed\}\}\-\\Delta t,t\_\{\\mathrm\{seed\}\}\]\. By executing a single backward\-in\-time scan, which halts once the time window is exceeded or all per\-type budgets are met, we obtain a fixed\-length, type\-balanced sequence ofKtempK\_\{\\mathrm\{temp\}\}IDs \(Algorithm[2](https://arxiv.org/html/2609.26855#alg2), Appendix[A\.1\.1](https://arxiv.org/html/2609.26855#A1.SS1.SSS1)\)\. We setKtemp=300K\_\{\\mathrm\{temp\}\}=300andΔ​t=365\\Delta t=365days\.

#### 2\.2\.3Collaborative Neighbor Sampler

Complementary to the proximity\- and recency\-biased samplers, the collaborative branch captures long\-horizon “lookalike” peers—nodes that exhibit substantial neighborhood overlap with the seed across its full causal history, independent of recency\. This affinity is estimated using a two\-hop random probe\. By first samplingM1M\_\{1\}of the seed’s causal neighbors and subsequently drawingM2M\_\{2\}peers from each, a peer’s accumulated hit count serves as a Monte Carlo estimate of shared intermediaries \(representing the numerator of a Jaccard similarity coefficient\)\. Peers corresponding to the seed, its direct causal neighbors, or previously sampled entities are discarded\. The topKcollabK\_\{\\mathrm\{collab\}\}remaining peers by hit count are then considered as collaborative neighbors \(Algorithm[3](https://arxiv.org/html/2609.26855#alg3)in Appendix[A\.1\.1](https://arxiv.org/html/2609.26855#A1.SS1.SSS1); derivation in Appendix[A\.1\.3](https://arxiv.org/html/2609.26855#A1.SS1.SSS3)\)\. We setM1=M2=50M\_\{1\}=M\_\{2\}=50andKcollab=300K\_\{\\mathrm\{collab\}\}=300\.

Figure 2:TheQuartetmodel\. Local tokens fuse five encodings \(feature, type, hop, time, positional\) via an MLP\. Then, the full neighbor set is fed into the*Local Module*\(self\-attention\), while the seed token queries the*Global Module*\. This global module cross\-attends the seed over learned feature and topological codebooks \(§[2\.5\.1](https://arxiv.org/html/2609.26855#S2.SS5.SSS1)\) and over Perceiver latents compressing temporal and collaborative neighbors \(§[2\.5\.2](https://arxiv.org/html/2609.26855#S2.SS5.SSS2)\)\. Finally, local and global embeddings are concatenated for downstream prediction\.

### 2\.3Graph Tokenization

With the local subgraph sampled, we tokenize it for Transformer consumption: for each seedviv\_\{i\}the context is a fixed\-size set ofKKtokens—the seed and theK−1K\-1neighbors ranked by CRW visit frequency \(§[2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1)\)\. Rather than compressing all structural information into a single positional encoding, we decompose the token representation to explicitly model the distinct characteristics of relational data\. Each tokenvjv\_\{j\}is a 5\-tuple fused into a single embedding \(Figure[2](https://arxiv.org/html/2609.26855#S2.F2)\)\. Components include: a PyTorch Frame\[[43](https://arxiv.org/html/2609.26855#bib.bib23)\]feature embeddinghfeat​\(vj\)h\_\{\\mathrm\{feat\}\}\(v\_\{j\}\); one\-hot encodings for node typeϕ⁡\(vj\)\\phi\(v\_\{j\}\)and hop distancep⁡\(vi,vj\)p\(v\_\{i\},v\_\{j\}\); a linear projection of relative timeτ⁡\(vj\)−τ⁡\(vi\)\\tau\(v\_\{j\}\)\-\\tau\(v\_\{i\}\); and a Graph Isomorphism Network \(GIN\)\-based positional encoding\[[44](https://arxiv.org/html/2609.26855#bib.bib47),[45](https://arxiv.org/html/2609.26855#bib.bib48)\]over the sampled subgraph using stochastic random features\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]\. These five components are concatenated and mixed viaWmix∈ℝd×5​dW\_\{\\mathrm\{mix\}\}\\in\\mathbb\{R\}^\{d\\times 5d\}to formhtoken​\(vj\)h\_\{\\mathrm\{token\}\}\(v\_\{j\}\)\(exact formulas in Appendix[A\.1\.4](https://arxiv.org/html/2609.26855#A1.SS1.SSS4)\)\. The resulting length\-KKsequence is then processed by the Local Attention Module \(§[2\.4](https://arxiv.org/html/2609.26855#S2.SS4)\)\.

### 2\.4Local Attention Module

We process the tokenized subgraph using anLL\-layer standard Transformer, applying all\-pair self\-attention\[[46](https://arxiv.org/html/2609.26855#bib.bib17)\]across allKKtokens of the CRW\-sampled subgraph\. This unconstrained all\-pair attention circumvents the traditional GNN bottleneck of localized message passing along connected edges, directly capturing long\-range dependencies\. The final local representation is computed as:

hlocal​\(vi\)=Pool⁡\(FFN​\(SelfAttn⁡\(vi,\{vj\}j=1K\)\)L\)h\_\{\\mathrm\{local\}\}\(v\_\{i\}\)=\\mathrm\{Pool\}\(\\mathrm\{FFN\}\(\\mathrm\{SelfAttn\}\(v\_\{i\},\\\{v\_\{j\}\\\}\_\{j=1\}^\{K\}\)\)\_\{L\}\)\(1\)wherePool\\mathrm\{Pool\}aggregates the sequence via a learned linear combination\. The CRW formulation ensures these local self\-attention layers operate on structurally dense, strictly causal neighborhoods, maximizing the token budget\.

### 2\.5Global Attention Module

The Global Attention Module captures long\-range relational context beyond the localized subgraph’s receptive field—such as structurally disconnected seed archetypes, concurrently active entities, and behaviorally similar peers located multiple hops away\. Architecturally, it consists of four seed\-conditioned branches grouped into two functional families with complementary structural goals\. The first family consists of two codebook branches that extract the seed’s intrinsic tabular and topological properties by querying learnable archetype matrices\. The second family consists of two cross\-attention branches that model extrinsic interactions by compressing global temporal and collaborative neighbor sequences via a Perceiver\-style bottleneck\[[47](https://arxiv.org/html/2609.26855#bib.bib21),[48](https://arxiv.org/html/2609.26855#bib.bib22)\]\. Unlike prior approaches, all global branches share a unified query\-driven bottleneck and are optimized end\-to\-end\. A compact, learnable query set reads over a context tensor, ensuring that the output dimensionality is strictly bounded by a fixed query budget rather than scaling with variable neighborhood sizes\. Formally, for a query setQ∈ℝd×nqQ\\in\\mathbb\{R\}^\{d\\times n\_\{q\}\}and contextC∈ℝd×ncC\\in\\mathbb\{R\}^\{d\\times n\_\{c\}\}whose columns are tokens, with projection matricesWQ,WK,WVW\_\{Q\},W\_\{K\},W\_\{V\}acrossHHheads \(dk=d/Hd\_\{k\}=d/H\), the shared multi\-head scaled dot\-product cross\-attention operator\[[46](https://arxiv.org/html/2609.26855#bib.bib17)\]applies each projection on the left and normalizes the softmax over the context axis:

CrossAttn⁡\(Q,C\)=\(WV​C\)​softmax​\(\(WK​C\)⊤​\(WQ​Q\)dk\)\.\\mathrm\{CrossAttn\}\(Q,C\)=\(W\_\{V\}C\)\\,\\mathrm\{softmax\}\\\!\\left\(\\frac\{\(W\_\{K\}C\)^\{\\top\}\(W\_\{Q\}Q\)\}\{\\sqrt\{d\_\{k\}\}\}\\right\)\.\(2\)
#### 2\.5\.1Feature and Topological Codebook Branches

Intuitively, the two codebook branches assign each seed a soft membership over a bank of global archetypes: learned prototypes that summarize recurring feature and structural profiles across the entire database\. Because these archetypes are shared globally rather than read off the seed’s sampled neighborhood, they let the model relate structurally disconnected nodes that never co\-occur in any subgraph\. For example, low\- versus high\-spend customers are routed to different archetypes according to their tabular attributes \(feature codebook\) and their local connectivity signature \(topological codebook\), even when no path in the graph links them\.

Each codebook branch queries a learnable archetype matrix, denoted asEstructE\_\{\\mathrm\{struct\}\}orEfeatE\_\{\\mathrm\{feat\}\}, using the cross\-attention operator where the seed token serves as the query \[Figure[2](https://arxiv.org/html/2609.26855#S2.F2)\]\. To maximize computational efficiency, the key and value projections for both matrices are cached and shared across the batch\. For a given branchb∈\{feat,struct\}b\\in\\\{\\mathrm\{feat\},\\mathrm\{struct\}\\\}, we project a seed queryqbq\_\{b\}through a two\-layer GELU multi\-layer perceptron \(MLP\) and compute the cross\-attention against its corresponding archetype matrixEbE\_\{b\}:

Xb=CrossAttn⁡\(MLPb​\(qb\),Eb\)\.X\_\{b\}=\\mathrm\{CrossAttn\}\\bigl\(\\mathrm\{MLP\}\_\{b\}\(q\_\{b\}\),\\;E\_\{b\}\\bigr\)\.\(3\)The feature query,qfeat=hfeat​\(vi\)q\_\{\\mathrm\{feat\}\}=h\_\{\\mathrm\{feat\}\}\(v\_\{i\}\), reuses the tabular embedding of the seed generated by the local module\. This yields a soft readout of the semantic profile of the seed without introducing additional encoding overhead\. Conversely, the structural query summarizes the causal one\-hop neighborhood of the seed via a structural sketchFsketch​\(vi\)F\_\{\\mathrm\{sketch\}\}\(v\_\{i\}\)\. This sketch concatenates four scalar random\-walk statistics with a per\-type degree histogram𝐜\\mathbf\{c\}, formulated as:

Fsketch​\(vi\)=log⁡\(1\+\[dc,s,ρ,πmax,𝐜\]\)\.F\_\{\\mathrm\{sketch\}\}\(v\_\{i\}\)=\\log\\\!\\bigl\(1\+\[\\,d\_\{c\},\\ s,\\ \\rho,\\ \\pi^\{\\max\},\\ \\mathbf\{c\}\\,\]\\bigr\)\.\(4\)Heredcd\_\{c\}is the causal degree \(the number of one\-hop neighbors withτ⁡\(e\)≤tseed\\tau\(e\)\\leq t\_\{\\mathrm\{seed\}\}\),ssthe temporal span of those neighbors \(tmax−tmint\_\{\\max\}\-t\_\{\\min\}\),ρ=dc/s\\rho=d\_\{c\}/stheir arrival density, andπmax\\pi^\{\\max\}the peak causal\-PPR mass \(the largest CRW visit count\), while𝐜∈ℝ\|𝒯\|\\mathbf\{c\}\\in\\mathbb\{R\}^\{\|\\mathcal\{T\}\|\}is the per\-type degree histogram counting causal neighbors of each node type\. The elementwiselog\(1\+⋅\)\\log\(1\+\\cdot\)compresses these heavy\-tailed statistics and ensure empty neighborhoods are mapped to zero, yielding a compact, permutation\-invariant fingerprint of the seed’s local connectivity: its size, temporal extent, interaction rate, dominant\-neighbor concentration, and type mix\. Applying Batch Normalization and an MLP projection to this sketch yieldsqstruct=BN⁡\(Fsketch​\(vi\)\)q\_\{\\mathrm\{struct\}\}=\\mathrm\{BN\}\\\!\\bigl\(F\_\{\\mathrm\{sketch\}\}\(v\_\{i\}\)\\bigr\), which provides a soft summary over the global topological archetypes to capture structural homophily\.

#### 2\.5\.2Temporal and Collaborative Cross\-Attention Branches

To circumvent the quadratic cost of full self\-attention over extended neighbor sequences, the temporal and collaborative branches each employ an asymmetric cross\-attention bottleneck\. Each trackb∈\{temp,collab\}b\\in\\\{\\mathrm\{temp\},\\mathrm\{collab\}\\\}\(indexed as in §[2\.5\.1](https://arxiv.org/html/2609.26855#S2.SS5.SSS1)\) instantiates its own learnable latent set𝐙0b∈ℝd×Lperc\\mathbf\{Z\}\_\{0\}^\{b\}\\in\\mathbb\{R\}^\{d\\times L\_\{\\mathrm\{perc\}\}\}; the two branches are separate bottlenecks and share no latent tokens\. For branchbb, these latents cross\-attend over the branch context𝐂b\\mathbf\{C\}\_\{b\}—the featurized set of sampled temporal or collaborative neighbors \(§[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)\)—with a residual connection:

𝐙b=𝐙0b\+CrossAttn⁡\(𝐙0b,𝐂b\),b∈\{temp,collab\}\.\\mathbf\{Z\}\_\{b\}=\\mathbf\{Z\}\_\{0\}^\{b\}\+\\mathrm\{CrossAttn\}\(\\mathbf\{Z\}\_\{0\}^\{b\},\\mathbf\{C\}\_\{b\}\),\\qquad b\\in\\\{\\mathrm\{temp\},\\mathrm\{collab\}\\\}\.\(5\)The temporal context𝐂temp\\mathbf\{C\}\_\{\\mathrm\{temp\}\}is constructed from recently active nodes to isolate transient global phenomena, such as transactional waves, independently of spatial topology\. For instance, in the Formula\-1 tasks \(driver\-top3, driver\-dnf\), a driver’s finishing outcome is shaped by conditions that act on the entire grid at once—such as weather or a safety\-car period—signals that live in concurrently active nodes rather than in the driver’s own local neighborhood\. In contrast, the collaborative context𝐂collab\\mathbf\{C\}\_\{\\mathrm\{collab\}\}aggregates highly co\-occurring, multi\-hop peers to distill long\-term behavioral affinities and shared archetypes while strictly bypassing recency bias\. For instance, in e\-commerce \(rel\-amazon\) or fashion retail \(rel\-hm\), two customers who never transact together may still be strong lookalikes if they repeatedly buy the same products, and their history is highly predictive for repeat\-purchase and churn targets\.

Rather than pooling the two blocks in isolation, we let them exchange information before readout: the latent blocks are concatenated along the token axis, jointly reasoned over by a shared stack ofLsaL\_\{\\mathrm\{sa\}\}pre\-LN self\-attention layers \(Lsa=4L\_\{\\mathrm\{sa\}\}=4\), and split back into per\-branch halves,

\[𝐙~collab∥𝐙~temp\]=SelfAttn\(\[𝐙collab∥𝐙temp\]\)\.\[\\,\\tilde\{\\mathbf\{Z\}\}\_\{\\mathrm\{collab\}\}\\parallel\\tilde\{\\mathbf\{Z\}\}\_\{\\mathrm\{temp\}\}\\,\]=\\mathrm\{SelfAttn\}\\bigl\(\[\\,\\mathbf\{Z\}\_\{\\mathrm\{collab\}\}\\parallel\\mathbf\{Z\}\_\{\\mathrm\{temp\}\}\\,\]\\bigr\)\.\(6\)This cross\-branch reasoning step lets the temporal and collaborative latents attend to one another, so each track is refined in the context of the other rather than in isolation\. Each refined block is then collapsed to a flat vector by a seed\-conditioned cross\-attention read that reuses the single\-token query convention of §[2\.5\.1](https://arxiv.org/html/2609.26855#S2.SS5.SSS1), with the projected seed tokenqseedq\_\{\\mathrm\{seed\}\}as the query:

hb=CrossAttn⁡\(qseed,𝐙~b\),b∈\{temp,collab\}\.h\_\{b\}=\\mathrm\{CrossAttn\}\(q\_\{\\mathrm\{seed\}\},\\tilde\{\\mathbf\{Z\}\}\_\{b\}\),\\qquad b\\in\\\{\\mathrm\{temp\},\\mathrm\{collab\}\\\}\.\(7\)The resulting vectorshtemp,hcollab∈ℝdh\_\{\\mathrm\{temp\}\},h\_\{\\mathrm\{collab\}\}\\in\\mathbb\{R\}^\{d\}are forwarded to the final fusion \(§[2\.6](https://arxiv.org/html/2609.26855#S2.SS6)\)\.

### 2\.6Final Fusion

The outputs of the four global branches \(Xstruct,Xfeat,hcollab,htempX\_\{\\mathrm\{struct\}\},X\_\{\\mathrm\{feat\}\},h\_\{\\mathrm\{collab\}\},h\_\{\\mathrm\{temp\}\}\) are normalized via independent LayerNorm \(LN\\mathrm\{LN\}\) layers, concatenated with the local embeddinghlocalh\_\{\\mathrm\{local\}\}, and linearly projected back todddimensions:

hfused=Wproj\[hlocal∥LN\(Xstruct\)∥LN\(Xfeat\)∥LN\(hcollab\)∥LN\(htemp\)\]\.h\_\{\\mathrm\{fused\}\}=W\_\{\\mathrm\{proj\}\}\\bigl\[\\,h\_\{\\mathrm\{local\}\}\\parallel\\mathrm\{LN\}\(X\_\{\\mathrm\{struct\}\}\)\\parallel\\mathrm\{LN\}\(X\_\{\\mathrm\{feat\}\}\)\\parallel\\mathrm\{LN\}\(h\_\{\\mathrm\{collab\}\}\)\\parallel\\mathrm\{LN\}\(h\_\{\\mathrm\{temp\}\}\)\\,\\bigr\]\.\(8\)The prediction head subsequently computes the target output asyvi=head⁡\(FFN⁡\(hfused\)\)y\_\{v\_\{i\}\}=\\mathrm\{head\}\(\\mathrm\{FFN\}\(h\_\{\\mathrm\{fused\}\}\)\)\. By concatenating rather than summing these distinct channels, we preserve their semantic separability and enableWprojW\_\{\\mathrm\{proj\}\}to learn an expressive, per\-branch mixing rule tailored for downstream tasks\.

## 3Experimental Setup

We evaluate our architecture across twelve binary\-classification tasks derived from sevenRelBenchdatasets\[[34](https://arxiv.org/html/2609.26855#bib.bib9)\], which span diverse real\-world domains such as Formula\-1 racing, event recommendation, clinical trials, online advertising, e\-commerce, fashion retail, and Q&A communities\. We use ROC\-AUC as the primary evaluation metric and report test ROC\-AUC for the model selected on the validation split\. All models are trained end\-to\-end using the Adam optimizer\. To accommodate varying computational demands, small tasks \(<1M training nodes\) are trained on a single A100 GPU, whereas large tasks \(\>1M training nodes\) utilize four A100 GPUs\. To eliminate runtime traversal overhead, every subgraph is pre\-computed and cached offline prior to training\. Following a similar hyperparameter tuning strategy to that described in the RelGT paper, we adjust the number of local layers \(LlocalL\_\{\\mathrm\{local\}\}\), dropout, and weight decay on a per\-task basis\. Specifically, we searchLlocal∈\{1,4,8\}L\_\{\\mathrm\{local\}\}\\in\\\{1,4,8\\\}for small datasets, while compute constraints require us to fixLlocal=4L\_\{\\mathrm\{local\}\}=4for large datasets \(detailed in Appendix[A\.3\.3](https://arxiv.org/html/2609.26855#A1.SS3.SSS3)\)\. Furthermore, the quad\-branch capacity—specifically the Perceiver latent budgetLpercL\_\{\\mathrm\{perc\}\}and codebook sizeRstruct=RfeatR\_\{\\mathrm\{struct\}\}=R\_\{\\mathrm\{feat\}\}—is configured per task \(see Appendix[A\.3\.4](https://arxiv.org/html/2609.26855#A1.SS3.SSS4)\), and the CRW local sampler alongside the collaborative and temporal branches each uses token budget ofK=300K=300\. Full configuration grids, sampler settings, and infrastructure details are provided in Appendix[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\. While we retain the twelve classification tasks established inRelBenchv1 to align with prior work, all data processing and feature tokenization are executed through the updated, more rigorousRelBenchv2 pipeline \(using the most up\-to\-date datasets\)\[[34](https://arxiv.org/html/2609.26855#bib.bib9)\]\. To ensure a fair evaluation across all models, we reproduced both graph\-transformer baselines \(HGT and RelGT\) from scratch under this shared v2 pipeline, utilizing the original authors’ reported hyperparameters\. Finally, to account for architectural stochasticity, all experiments for both the baselines andQuartetare averaged acrossn=4n=4random seeds\.

## 4Results and Discussion

We evaluateQuartetin three stages\. First, we isolate the performance improvements of the causal random\-walk sampler \(CRW\) by swapping out the default 2\-hop BFS sampler with CRW in the current state\-of\-the\-art RelGT workflow \(§[4\.1](https://arxiv.org/html/2609.26855#S4.SS1)\)\. Second, we benchmark the completeQuartetmodel against previous SOTA baselines on theRelBenchv1 classification tasks \(§[4\.2](https://arxiv.org/html/2609.26855#S4.SS2)\)\. Finally, we conduct a leave\-one\-out ablation study to determine the specific contributions of the local module, the CRW sampler, and each of the four global branches \(§[4\.3](https://arxiv.org/html/2609.26855#S4.SS3)\)\.

### 4\.1Causal Random\-Walk Sampling Allows Better Graph Representation Learning with Fewer Local Attention Layers

In this section, we test the hypothesis that ranking a seed’s neighbors by causal random walk, yields a more natural, better\-connected subgraph than uniform neighbor selection, and that this structurally relevant local context lets the encoder learn substantially stronger graph representations\. To isolate the sampler from every other design choice, we hold the base RelGT architecture\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]fixed and vary only the neighbor sampler\. The baseline relies on RelGT’s native*naive*sampler, which draws neighbors uniformly at random from the seed’s one\- and two\-hop \(BFS\) neighborhood\. Our system substitutes this with the PPR\-ranked CRW sampler\. To ensure a fair comparison, both configurations utilize the same local attention architecture and follow an identical restricted hyperparameter tuning protocol \(optimizing for layers, dropout, and weight decay\), as detailed in Appendix[A\.3\.3](https://arxiv.org/html/2609.26855#A1.SS3.SSS3)\. We report the test ROC\-AUC for all classification tasks inRelBenchv1\.

Figure 3:Per\-task test ROC\-AUC on theRelBenchclassification tasks for the PPR\-ranked CRW sampler \(*CRW*, blue\) against RelGT’s naive uniform one\-/two\-hop sampler \(*BFS2*, orange\) on a fixed RelGT architecture\. Each bar is annotated with the selected number of local layersLlocalL\_\{\\mathrm\{local\}\}\.Figure[3](https://arxiv.org/html/2609.26855#S4.F3)demonstrates that the CRW sampler matches or outperforms the RelGT baseline while requiring fewer local self\-attention layers \(annotated in green\)\. By concentrating a seed’s most relevant neighbors into a compact, well\-connected subgraph, CRW enables the local module to learn stronger representations with less depth\. Ultimately, this sampler upgrade delivers both improved accuracy and a more efficient local module\. A detailed subgraph connectivity analysis further confirming that CRW extracts denser, more connected subgraphs than the BFS2 baseline is provided in Appendix[A\.4\.1](https://arxiv.org/html/2609.26855#A1.SS4.SSS1)\. For the experiments in the next section, we reused the result of hyperparameter search from this section for number of local layersLlocalL\_\{\\mathrm\{local\}\}, dropout, and weight decay \(see Appendix[A\.3\.3](https://arxiv.org/html/2609.26855#A1.SS3.SSS3)\)\.

### 4\.2QuartetOutperforms RelGT on Most Classification Tasks

Table[1](https://arxiv.org/html/2609.26855#S4.T1)comparesQuartetagainst leading graph transformers \(HGT\[[35](https://arxiv.org/html/2609.26855#bib.bib2)\]and RelGT\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]\) on theRelBenchv1 classification tasks\. Compared directly to its base architecture,Quartetimproves on or matches RelGT on eight of twelve tasks\. RelGT primarily maintains an advantage on large, stationary tasks where dense local topology dominates the predictive signal, rendering additional global branches redundant\. Overall,Quartetis competitive with the strongest graph\-transformer baselines and lifts its RelGT starting point on the classification tasks; the following ablation section \(§[4\.3](https://arxiv.org/html/2609.26855#S4.SS3)\) isolates where these predictive gains originate\.

Table 1:Test ROC\-AUC \(mean±\\pmstd\) on theRelBenchclassification suite\.Δ%\\Delta\\%comparesQuartetwith RelGT \(positive==gain\);boldmarks the best mean in each row\.DatasetTaskHGTRelGTQuartetΔ%\\Delta\\%vs\. RelGTrel\-amazonitem\-churn0\.7758±\\pm0\.00750\.8249±\\pm0\.00050\.8262±\\pm0\.0010\+0\.2\+0\.2user\-churn0\.6626±\\pm0\.00410\.7024±\\pm0\.00150\.7001±\\pm0\.0016−0\.3\-0\.3rel\-avitouser\-clicks0\.6501±\\pm0\.01040\.6425±\\pm0\.01590\.6481±\\pm0\.0122\+0\.9\+0\.9user\-visits0\.6410±\\pm0\.00680\.6639±\\pm0\.00200\.6508±\\pm0\.0050−2\.0\-2\.0rel\-eventuser\-ignore0\.7256±\\pm0\.00800\.7348±\\pm0\.01830\.7392±\\pm0\.0035\+0\.6\+0\.6user\-repeat0\.7539±\\pm0\.01570\.7160±\\pm0\.03160\.7563±\\pm0\.0175\+5\.6\+5\.6rel\-f1driver\-dnf0\.6595±\\pm0\.06270\.7133±\\pm0\.04160\.7044±\\pm0\.0180−1\.2\-1\.2driver\-top30\.7384±\\pm0\.05740\.8067±\\pm0\.04020\.8517±\\pm0\.0156\+5\.6\+5\.6rel\-hmuser\-churn0\.6746±\\pm0\.00360\.6975±\\pm0\.00160\.6976±\\pm0\.0011\+0\.01\+0\.01rel\-stackuser\-badge0\.8688±\\pm0\.00250\.8764±\\pm0\.00160\.8528±\\pm0\.0094−2\.7\-2\.7user\-engagement0\.8899±\\pm0\.00180\.9047±\\pm0\.00090\.9063±\\pm0\.0010\+0\.2\+0\.2rel\-trialstudy\-outcome0\.6345±\\pm0\.02510\.6632±\\pm0\.01770\.7059±\\pm0\.0044\+6\.4\+6\.4

### 4\.3CRW Enriches Local Context While Global Branches Add Complementary Gains

To rigorously isolate the individual contributions of each architectural component, we conduct a leave\-one\-out ablation study \(Table[2](https://arxiv.org/html/2609.26855#S4.T2)\)\. Starting from the fullQuartetmodel, we systematically remove a single component and record the relative changes in test ROC\-AUC\. A performance degradation indicates that the ablated component provided essential predictive signals that the remaining architecture could not independently recover\. Appendix Table[9](https://arxiv.org/html/2609.26855#A1.T9)reports the full mean±\\pmstd values underlying these relative changes, with statistically significant drops highlighted\.

Table 2:Leave\-one\-out ablation ofQuartet: entries are the relative change in test ROC\-AUC \(%\) vs\. the full model\. Cell color encodes the change \(red==decrease,blue==increase; darker is larger in magnitude, with the diverging scale saturating at−10%\-10\\%and\+1%\+1\\%\)\. Columns are grouped into attention variants \(No Local, No Perceiver\), sampler mechanisms \(No CRW, No Hub Trunc\., No Restart\), and global branches \(No Temp\., No Collab\., No Feat\., No Struct\.\)\. For each task, the largest drop among the four global\-branch columns is marked with asolid border\.##### Architecture ablation\.

Removing the local module and CRW sampler \("No Local" configuration\) yields the steepest average performance drop \(6\.7%6\.7\\%\), confirming local topology as the primary predictive signal\. However, this is task\-dependent; for example, removing local context actively improves performance on rel\-event user\-ignore\. We also probe the design of the global module by replacing the Perceiver bottleneck with direct full self\-attention between the seed and its global neighbor sequences \(“No Perceiver”\)\. This variant degrades performance by2\.2%2\.2\\%on average, confirming that the latent bottleneck improves representation quality rather than serving as a mere efficiency shortcut\.

##### Sampler ablation\.

Substituting CRW with a naive BFS2 expansion \(“No CRW”\) degrades performance by1\.6%1\.6\\%on average\. As expected, the tasks that suffer the steepest performance drops largely align with the tasks that saw the largest CRW\-driven gains in our standalone sampler study \(§[4\.1](https://arxiv.org/html/2609.26855#S4.SS1)\), confirming that the local encoder relies heavily on CRW’s structurally dense topology\. To further dissect the CRW sampler, we ablate its two key mechanisms: hub\-degree truncation \(“No Hub Trunc\.”\) and the restart probability \(“No Restart”\)\. Disabling hub truncation degrades performance by1\.8%1\.8\\%on average\. This drop is especially severe in the rel\-event user\-repeat and rel\-f1 driver\-top3 tasks, where high\-degree hub nodes will dominate walk distributions if left unchecked\. Removing the restart mechanism yields a comparable average drop of2\.1%2\.1\\%, most acutely on rel\-avito user\-clicks and rel\-stack user\-badge, indicating that restart\-driven locality is important when the predictive signal concentrates near the seed node\. Because these1\.8%1\.8\\%and2\.1%2\.1\\%drops exceed the1\.6%1\.6\\%penalty of dropping CRW entirely, this confirms both mechanisms are essential; without them, CRW actually underperforms a naive BFS2 sampler\.

##### Quad\-branch ablation\.

The four global branches \(Temporal, Collaborative, Feature, and Structural\) act as complementary boosters, yielding average gains of2\.0%2\.0\\%,1\.8%1\.8\\%,1\.7%1\.7\\%, and1\.5%1\.5\\%, respectively\. No single branch is globally redundant, as the dominant component shifts dynamically across tasks \(solid borders, Table[2](https://arxiv.org/html/2609.26855#S4.T2)\), though the temporal branch sustains the largest drop on half of the evaluation tasks\.

Ultimately, this ablation suggests thatQuartet’s empirical strength stems from resolving hub\-sensitivity via PPR\-ranked sampling and augmenting the local signal with rich, complementary global context\.

## 5Conclusion

In this work, we introducedQuartet, a quad\-branch architecture extending Relational Graph Transformer \(RelGT\) by augmenting local subgraphs with a Causal Random Walk \(CRW\) sampler and incorporating global context via Perceiver\- and codebook\-style cross\-attention branches\. Evaluated on theRelBenchv1 classification benchmark,Quartetachieves competitive performance against strong graph\-transformer baselines, matching or outperforming the original RelGT model on eight of twelve tasks and securing top test ROC\-AUC on seven\. While RelGT retains an edge on a few large, stationary tasks, our ablations demonstrate the distinct utility ofQuartet’s individual components\. Specifically, the CRW sampler ranks neighbors via a causal PPR estimate and serves as a compelling alternative to uniform BFS expansion, markedly improving test performance while requiring fewer attention layers\. Furthermore, leave\-one\-out experiments confirm that global context complements rather than replaces local topology: removing the local module \(and CRW sampler along with it\) causes the most severe performance drop as expected, whereas the four global branches supply complementary and task\-dependent signals\. Together, these findings demonstrate thatQuartetprovides a promising framework for enriching supervised RDL models with global relational context while preserving crucial local attention mechanisms\.

## 6Future Directions

While our current evaluation focuses on twelve binary classification tasks, future work will extend QUARTET to encompass regression modeling and pair\-wise link prediction\. For link prediction, the architecture can be readily adapted by treating candidate entities as independent seed nodes, extracting their enriched graph embeddings through our pipeline, and applying a shallow classifier to evaluate their relational affinity\. Similarly, the model can natively support regression tasks by modifying the final prediction head to output continuous target variables\. Furthermore, to validate the architecture’s scalability and generalizability in highly realistic enterprise resource planning \(ERP\) environments, we plan to comprehensively benchmark QUARTET on the SALT dataset\.

## References

- \[1\]E\. F\. Codd\(1970\)A relational model of data for large shared data banks\.Communications of the ACM13\(6\),pp\. 377–387\.External Links:[Document](https://dx.doi.org/10.1145/362384.362685)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p1.1)\.
- \[2\]J\. M\. Kanter and K\. Veeramachaneni\(2015\)Deep feature synthesis: towards automating data science endeavors\.In2015 IEEE International Conference on Data Science and Advanced Analytics,DSAA ’15,pp\. 1–10\.External Links:[Document](https://dx.doi.org/10.1109/DSAA.2015.7344858)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p1.1)\.
- \[3\]T\. Chen and C\. Guestrin\(2016\)XGBoost: a scalable tree boosting system\.InProceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,KDD ’16,pp\. 785–794\.External Links:[Document](https://dx.doi.org/10.1145/2939672.2939785)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p1.1)\.
- \[4\]G\. Ke, Q\. Meng, T\. Finley, T\. Wang, W\. Chen, W\. Ma, Q\. Ye, and T\. Liu\(2017\)LightGBM: a highly efficient gradient boosting decision tree\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 3146–3154\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p1.1)\.
- \[5\]R\. Trivedi, M\. Farajtabar, P\. Biswal, and H\. Zha\(2019\)DyRep: learning representations over dynamic graphs\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[6\]D\. Xu, C\. Ruan, E\. Korpeoglu, S\. Kumar, and K\. Achan\(2020\)Inductive representation learning on temporal graphs\.InInternational Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[7\]E\. Rossi, B\. Chamberlain, F\. Frasca, D\. Eynard, F\. Monti, and M\. Bronstein\(2020\)Temporal graph networks for deep learning on dynamic graphs\.InICML 2020 Workshop on Graph Representation Learning,External Links:2006\.10637Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[8\]M\. Fey, W\. Hu, K\. Huang, J\. E\. Lenssen, R\. Ranjan, J\. Robinson, R\. Ying, J\. You, and J\. Leskovec\(2024\)Position: relational deep learning – graph representation learning on relational databases\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 13592–13607\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[9\]V\. P\. Dwivedi, C\. Kanatsoulis, S\. Huang, and J\. Leskovec\(2025\)Relational deep learning: challenges, foundations and next\-generation architectures\.arXiv preprint arXiv:2506\.16654\.External Links:2506\.16654Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[10\]T\. Chen, C\. Kanatsoulis, and J\. Leskovec\(2025\)RelGNN: composite message passing for relational deep learning\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267,pp\. 8296–8312\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[11\]Y\. Yuan, Z\. Zhang, X\. He, A\. Nitta, W\. Hu, D\. Wang, M\. Shah, S\. Huang, B\. Stojanovič, A\. Krumholz, J\. E\. Lenssen, J\. Leskovec, and M\. Fey\(2024\)ContextGNN: beyond two\-tower recommendation systems\.arXiv preprint arXiv:2411\.19513\.External Links:2411\.19513Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[12\]V\. Lachi, A\. Longa, B\. Bevilacqua, B\. Lepri, A\. Passerini, and B\. Ribeiro\(2025\)Boosting relational deep learning with pretrained tabular models\.arXiv preprint arXiv:2504\.04934\.External Links:2504\.04934Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[13\]W\. L\. Hamilton, R\. Ying, and J\. Leskovec\(2017\)Inductive representation learning on large graphs\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 1024–1034\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1),[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p1.1)\.
- \[14\]T\. N\. Kipf and M\. Welling\(2017\)Semi\-supervised classification with graph convolutional networks\.InInternational Conference on Learning Representations,External Links:1609\.02907Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[15\]M\. Schlichtkrull, T\. N\. Kipf, P\. Bloem, R\. van den Berg, I\. Titov, and M\. Welling\(2018\)Modeling relational data with graph convolutional networks\.InThe Semantic Web,Lecture Notes in Computer Science, Vol\.10843,pp\. 593–607\.External Links:[Document](https://dx.doi.org/10.1007/978-3-319-93417-4%5F38)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[16\]X\. Wang, H\. Ji, C\. Shi, B\. Wang, Y\. Ye, P\. Cui, and P\. S\. Yu\(2019\)Heterogeneous graph attention network\.InThe World Wide Web Conference,WWW ’19,pp\. 2022–2032\.External Links:[Document](https://dx.doi.org/10.1145/3308558.3313562)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[17\]K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka\(2019\)How powerful are graph neural networks?\.InInternational Conference on Learning Representations,External Links:1810\.00826Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[18\]C\. Morris, M\. Ritzert, M\. Fey, W\. L\. Hamilton, J\. E\. Lenssen, G\. Rattan, and M\. Grohe\(2019\)Weisfeiler and Leman go neural: higher\-order graph neural networks\.InProceedings of the Thirty\-Third AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 4602–4609\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v33i01.33014602)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[19\]A\. Loukas\(2020\)What graph neural networks cannot learn: depth vs width\.InInternational Conference on Learning Representations,External Links:1907\.03199Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[20\]U\. Alon and E\. Yahav\(2021\)On the bottleneck of graph neural networks and its practical implications\.InInternational Conference on Learning Representations,External Links:2006\.05205Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p2.1)\.
- \[21\]V\. P\. Dwivedi and X\. Bresson\(2021\)A generalization of transformer networks to graphs\.InAAAI Workshop on Deep Learning on Graphs: Methods and Applications,External Links:2012\.09699Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[22\]C\. Ying, T\. Cai, S\. Luo, S\. Zheng, G\. Ke, D\. He, Y\. Shen, and T\. Liu\(2021\)Do transformers really perform badly for graph representation?\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 28877–28888\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[23\]L\. Rampasek, M\. Galkin, V\. P\. Dwivedi, A\. T\. Luu, G\. Wolf, and D\. Beaini\(2022\)Recipe for a general, powerful, scalable graph transformer\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 14501–14515\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[24\]D\. Kreuzer, D\. Beaini, W\. L\. Hamilton, V\. Létourneau, and P\. Tossou\(2021\)Rethinking graph transformers with spectral attention\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 21618–21629\.External Links:2106\.03893Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[25\]D\. Chen, L\. O’Bray, and K\. Borgwardt\(2022\)Structure\-aware transformer for graph representation learning\.InProceedings of the 39th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.162,pp\. 3469–3489\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[26\]J\. Chen, K\. Gao, G\. Li, and K\. He\(2023\)NAGphormer: a tokenized graph transformer for node classification in large graphs\.InInternational Conference on Learning Representations,External Links:2206\.04910Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[27\]H\. Shirzad, A\. Velingker, B\. Venkatachalam, D\. J\. Sutherland, and A\. K\. Sinop\(2023\)Exphormer: sparse transformers for graphs\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 31613–31632\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[28\]Q\. Wu, W\. Zhao, C\. Yang, H\. Zhang, F\. Nie, H\. Jiang, Y\. Bian, and J\. Yan\(2023\)SGFormer: simplifying and empowering transformers for large\-graph representations\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 64753–64773\.External Links:2306\.10759Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[29\]K\. Kong, J\. Chen, J\. Kirchenbauer, R\. Ni, C\. B\. Bruss, and T\. Goldstein\(2023\)GOAT: a global transformer on large\-scale graphs\.InProceedings of the 40th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.202,pp\. 17375–17390\.Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[30\]G\. Mialon, D\. Chen, M\. Selosse, and J\. Mairal\(2021\)GraphiT: encoding graph structure in transformers\.arXiv preprint arXiv:2106\.05667\.External Links:2106\.05667Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[31\]Q\. Mao, Z\. Liu, C\. Liu, and J\. Sun\(2023\)HINormer: representation learning on heterogeneous information networks with graph transformer\.InProceedings of the ACM Web Conference 2023,pp\. 599–610\.External Links:[Document](https://dx.doi.org/10.1145/3543507.3583493)Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[32\]P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. Bengio\(2018\)Graph attention networks\.InInternational Conference on Learning Representations,External Links:1710\.10903Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[33\]J\. Robinson, R\. Ranjan, W\. Hu, K\. Huang, J\. Han, A\. Dobles, M\. Fey, J\. E\. Lenssen, Y\. Yuan, Z\. Zhang, X\. He, and J\. Leskovec\(2024\)RelBench: a benchmark for deep learning on relational databases\.InAdvances in Neural Information Processing Systems \(NeurIPS\) Datasets and Benchmarks Track,External Links:2407\.20060Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[34\]J\. Gu, R\. Ranjan, C\. Kanatsoulis, H\. Tang, M\. Jurkovic, V\. Hudovernik, M\. Znidar, P\. Chaturvedi, P\. Shroff, F\. Li, and J\. Leskovec\(2026\)RelBench v2: a large\-scale benchmark and repository for relational data\.arXiv preprint arXiv:2602\.12606\.External Links:2602\.12606Cited by:[§1](https://arxiv.org/html/2609.26855#S1.p3.1),[§3](https://arxiv.org/html/2609.26855#S3.p1.1)\.
- \[35\]Z\. Hu, Y\. Dong, K\. Wang, and Y\. Sun\(2020\)Heterogeneous graph transformer\.InProceedings of The Web Conference 2020,WWW ’20,New York, NY, USA,pp\. 2704–2710\.External Links:[Document](https://dx.doi.org/10.1145/3366423.3380027),ISBN 978\-1\-4503\-7023\-3Cited by:[Table 8](https://arxiv.org/html/2609.26855#A1.T8),[§1](https://arxiv.org/html/2609.26855#S1.p3.1),[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p1.1),[§4\.2](https://arxiv.org/html/2609.26855#S4.SS2.p1.1)\.
- \[36\]V\. P\. Dwivedi, S\. Jaladi, Y\. Shen, F\. López, C\. I\. Kanatsoulis, R\. Puri, M\. Fey, and J\. Leskovec\(2026\)Relational graph transformer\.InInternational Conference on Learning Representations,External Links:2505\.10960Cited by:[item 5](https://arxiv.org/html/2609.26855#A1.I1.i5.p1.1),[§A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1.p1.1),[Table 8](https://arxiv.org/html/2609.26855#A1.T8),[§1](https://arxiv.org/html/2609.26855#S1.p3.1),[§2\.3](https://arxiv.org/html/2609.26855#S2.SS3.p1.1),[§4\.1](https://arxiv.org/html/2609.26855#S4.SS1.p1.1),[§4\.2](https://arxiv.org/html/2609.26855#S4.SS2.p1.1)\.
- \[37\]D\. Lachi, M\. Mohammadi, J\. Meyer, V\. Arora, T\. Palczewski, and E\. L\. Dyer\(2025\)Integrating temporal and structural context in graph transformers for relational deep learning\.arXiv preprint arXiv:2511\.04557\.External Links:2511\.04557Cited by:[§A\.4\.4](https://arxiv.org/html/2609.26855#A1.SS4.SSS4.p1.1),[§1](https://arxiv.org/html/2609.26855#S1.p3.1)\.
- \[38\]L\. Page, S\. Brin, R\. Motwani, and T\. Winograd\(1999\)The PageRank citation ranking: bringing order to the web\.Technical reportTechnical Report1999\-66,Stanford InfoLab\.Cited by:[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p2.1),[§2](https://arxiv.org/html/2609.26855#S2.p2.1)\.
- \[39\]J\. Klicpera, A\. Bojchevski, and S\. Guennemann\(2019\)Predict then propagate: graph neural networks meet personalized PageRank\.InInternational Conference on Learning Representations,External Links:1810\.05997Cited by:[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p2.1),[§2](https://arxiv.org/html/2609.26855#S2.p2.1)\.
- \[40\]A\. Bojchevski, J\. Klicpera, B\. Perozzi, A\. Kapoor, M\. Blais, B\. Rozemberczki, M\. Lukasik, and S\. Guennemann\(2020\)PPRGo: scaling graph neural networks with approximate PageRank\.InProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,KDD ’20,pp\. 2464–2473\.External Links:[Document](https://dx.doi.org/10.1145/3394486.3403296)Cited by:[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p2.1),[§2](https://arxiv.org/html/2609.26855#S2.p2.1)\.
- \[41\]R\. Ying, R\. He, K\. Chen, P\. Eksombatchai, W\. L\. Hamilton, and J\. Leskovec\(2018\)Graph convolutional neural networks for web\-scale recommender systems\.InProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,KDD ’18,pp\. 974–983\.External Links:[Document](https://dx.doi.org/10.1145/3219819.3219890)Cited by:[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p2.1),[§2](https://arxiv.org/html/2609.26855#S2.p2.1)\.
- \[42\]H\. Zeng, H\. Zhou, A\. Srivastava, R\. Kannan, and V\. Prasanna\(2020\)GraphSAINT: graph sampling based inductive learning method\.InInternational Conference on Learning Representations,External Links:1907\.04931Cited by:[§2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1.p1.1)\.
- \[43\]W\. Hu, Y\. Yuan, Z\. Zhang, A\. Nitta, K\. Cao, V\. Kocijan, J\. Sunil, J\. Leskovec, and M\. Fey\(2024\)PyTorch Frame: a modular framework for multi\-modal tabular learning\.arXiv preprint arXiv:2404\.00776\.External Links:2404\.00776Cited by:[item 1](https://arxiv.org/html/2609.26855#A1.I1.i1.p1.1),[§2\.3](https://arxiv.org/html/2609.26855#S2.SS3.p1.1)\.
- \[44\]V\. P\. Dwivedi, A\. T\. Luu, T\. Laurent, Y\. Bengio, and X\. Bresson\(2022\)Graph neural networks with learnable structural and positional representations\.InInternational Conference on Learning Representations,External Links:2110\.07875Cited by:[§2\.3](https://arxiv.org/html/2609.26855#S2.SS3.p1.1)\.
- \[45\]D\. Lim, J\. Robinson, L\. Zhao, T\. Smidt, S\. Sra, H\. Maron, and S\. Jegelka\(2023\)Sign and basis invariant networks for spectral graph representation learning\.InInternational Conference on Learning Representations,External Links:2202\.13013Cited by:[§2\.3](https://arxiv.org/html/2609.26855#S2.SS3.p1.1)\.
- \[46\]A\. Vaswani, N\. Shazeer, N\. Parmar, J\. Uszkoreit, L\. Jones, A\. N\. Gomez, L\. Kaiser, and I\. Polosukhin\(2017\)Attention is all you need\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\. 5998–6008\.Cited by:[§2\.4](https://arxiv.org/html/2609.26855#S2.SS4.p1.1),[§2\.5](https://arxiv.org/html/2609.26855#S2.SS5.p1.1)\.
- \[47\]A\. Jaegle, F\. Gimeno, A\. Brock, O\. Vinyals, A\. Zisserman, and J\. Carreira\(2021\)Perceiver: general perception with iterative attention\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 4651–4664\.Cited by:[§2\.5](https://arxiv.org/html/2609.26855#S2.SS5.p1.1)\.
- \[48\]J\. Lee, Y\. Lee, J\. Kim, A\. Kosiorek, S\. Choi, and Y\. W\. Teh\(2019\)Set transformer: a framework for attention\-based permutation\-invariant neural networks\.InProceedings of the 36th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.97,pp\. 3744–3753\.Cited by:[§2\.5](https://arxiv.org/html/2609.26855#S2.SS5.p1.1)\.
- \[49\]Y\. Gorishniy, I\. Rubachev, V\. Khrulkov, and A\. Babenko\(2021\)Revisiting deep learning models for tabular data\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 18932–18943\.External Links:2106\.11959Cited by:[item 1](https://arxiv.org/html/2609.26855#A1.I1.i1.p1.1)\.
- \[50\]N\. Hollmann, S\. Müller, K\. Eggensperger, and F\. Hutter\(2023\)TabPFN: a transformer that solves small tabular classification problems in a second\.InInternational Conference on Learning Representations,External Links:2207\.01848Cited by:[item 1](https://arxiv.org/html/2609.26855#A1.I1.i1.p1.1)\.
- \[51\]M\. J\. Kim, L\. Grinsztajn, and G\. Varoquaux\(2024\)CARTE: pretraining and transfer for tabular learning\.InProceedings of the 41st International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.235,pp\. 23843–23866\.Cited by:[item 1](https://arxiv.org/html/2609.26855#A1.I1.i1.p1.1)\.
- \[52\]D\. Lachi, M\. Azabou, V\. Arora, and E\. Dyer\(2026\)GraphFM: a generalist graph transformer that learns transferable representations across diverse domains\.External Links:2407\.11907,[Link](https://arxiv.org/abs/2407.11907)Cited by:[2nd item](https://arxiv.org/html/2609.26855#A1.I2.i2.p1.1)\.

## Appendix AAppendix

Table of Contents

### A\.1Model Details

#### A\.1\.1Neighbor Sampling Algorithms

This appendix section provides the algorithms for the three seed\-rooted causal samplers discussed in §[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)\. The procedures are outlined as follows: Algorithm[1](https://arxiv.org/html/2609.26855#alg1)presents the CRW local subgraph sampler \(§[2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1)\); Algorithm[2](https://arxiv.org/html/2609.26855#alg2)outlines the temporal sampler’s single backward\-in\-time scan \(§[2\.2\.2](https://arxiv.org/html/2609.26855#S2.SS2.SSS2)\); and Algorithm[3](https://arxiv.org/html/2609.26855#alg3)illustrates the two\-hop random probe used by the collaborative sampler \(§[2\.2\.3](https://arxiv.org/html/2609.26855#S2.SS2.SSS3)\)\.

Algorithm 1CRW local subgraph sampling for one seed\.1:Graph

GG; seed

s=\(vi,tseed\)s=\(v\_\{i\},t\_\{\\mathrm\{seed\}\}\); walks

WW, length

LL, restart

pp, truncation

MM; budget

KK\.

2:Sampled neighbor list \(

𝚗𝚎𝚒𝚐𝚑𝚋𝚘𝚛𝚜\\mathtt\{neighbors\}\), induced sub\-adjacency \(

ASA\_\{S\}\), hop labels \(

hh\)\.

3:

visit⁡\[⋅\]←0\\mathrm\{visit\}\[\\cdot\]\\leftarrow 0;

hwalk​\[⋅\]←∞h\_\{\\mathrm\{walk\}\}\[\\cdot\]\\leftarrow\\infty
4:for

w=1w=1to

WWdo

5:

u←viu\\leftarrow v\_\{i\},

k←0k\\leftarrow 0
6:for

ℓ=1\\ell=1to

LLdo

7:if

Uniform⁡\(0,1\)<p\\mathrm\{Uniform\}\(0,1\)<por

𝒩M​\(u,s\)=∅\\mathcal\{N\}\_\{M\}\(u;s\)=\\varnothingthen

8:

u←viu\\leftarrow v\_\{i\},

k←0k\\leftarrow 0
9:else

10:

u∼Uniform⁡\(𝒩M​\(u,s\)\)u\\sim\\mathrm\{Uniform\}\(\\mathcal\{N\}\_\{M\}\(u;s\)\);

k←k\+1k\\leftarrow k\+1
11:

visit⁡\[u\]\+=1\\mathrm\{visit\}\[u\]\\mathrel\{\+\}=1;

hwalk​\[u\]←min⁡\(hwalk​\[u\],k\)h\_\{\\mathrm\{walk\}\}\[u\]\\leftarrow\\min\(h\_\{\\mathrm\{walk\}\}\[u\],k\)
12:endif

13:endfor

14:endfor

15:

𝚗𝚎𝚒𝚐𝚑𝚋𝚘𝚛𝚜←\[vi\]∥\\mathtt\{neighbors\}\\leftarrow\[\\,v\_\{i\}\\,\]\\,\\\|\\,\(top

K−1K\-1visited non\-seed neighbors\)

16:

AS←A\_\{S\}\\leftarrowcausal edges of

GGinduced on

𝚗𝚎𝚒𝚐𝚑𝚋𝚘𝚛𝚜\\mathtt\{neighbors\}
17:

hBFS←h\_\{\\mathrm\{BFS\}\}\\leftarrowBFS hop distance from

viv\_\{i\}within

ASA\_\{S\}
18:

h⁡\[v\]←min⁡\(hBFS​\[v\],hwalk​\[v\]\)h\[v\]\\leftarrow\\min\\bigl\(h\_\{\\mathrm\{BFS\}\}\[v\],\\ h\_\{\\mathrm\{walk\}\}\[v\]\\bigr\)for each

v∈𝚗𝚎𝚒𝚐𝚑𝚋𝚘𝚛𝚜v\\in\\mathtt\{neighbors\};

h⁡\[vi\]←0h\[v\_\{i\}\]\\leftarrow 0
19:return

𝚗𝚎𝚒𝚐𝚑𝚋𝚘𝚛𝚜,AS,h\\mathtt\{neighbors\},\\ A\_\{S\},\\ h

Algorithm 2Temporal neighbor sampling for one seed\.1:Seed

s=\(vi,tseed\)s=\(v\_\{i\},t\_\{\\mathrm\{seed\}\}\); per\-type budget

BB; window

Δ​t\\Delta t; types

𝒯\\mathcal\{T\}\.

2:Fixed\-length neighbor list

NtempN\_\{\\mathrm\{temp\}\}of size

B⋅\|𝒯\|B\\cdot\|\\mathcal\{T\}\|\.

3:

ca←0c\_\{a\}\\leftarrow 0for all

a∈𝒯a\\in\\mathcal\{T\};

Ntemp←\[\]N\_\{\\mathrm\{temp\}\}\\leftarrow\[\\,\]
4:forall nodes

\(v,a,t\)\(v,a,t\)in

GGwith

t≤tseedt\\leq t\_\{\\mathrm\{seed\}\}, indecreasing

ttdo

5:if

t<tseed−Δ​tt<t\_\{\\mathrm\{seed\}\}\-\\Delta tor

ca=Bc\_\{a\}=Bfor all

a∈𝒯a\\in\\mathcal\{T\}then

6:break

7:endif

8:if

ca<Bc\_\{a\}<Band

v∉Ntempv\\notin N\_\{\\mathrm\{temp\}\}then

9:append

vvto

NtempN\_\{\\mathrm\{temp\}\};

ca←ca\+1c\_\{a\}\\leftarrow c\_\{a\}\+1
10:endif

11:endfor

12:pad

NtempN\_\{\\mathrm\{temp\}\}to size

B⋅\|𝒯\|B\\cdot\|\\mathcal\{T\}\|via uniform fallback \(see Edge Cases\)

13:return

NtempN\_\{\\mathrm\{temp\}\}

Algorithm 3Collaborative neighbor sampling for one seed\.1:Seed

s=\(vi,tseed\)s=\(v\_\{i\},t\_\{\\mathrm\{seed\}\}\); fan\-outs

M1,M2M\_\{1\},M\_\{2\}; output size

KcollabK\_\{\\mathrm\{collab\}\}\.

2:Fixed\-length ID list

NcollabN\_\{\\mathrm\{collab\}\}of size

KcollabK\_\{\\mathrm\{collab\}\}with validity mask\.

3:

E←M1E\\leftarrow M\_\{1\}uniform samples from the causal neighbors of

viv\_\{i\}
4:multiplicity

m←∅m\\leftarrow\\varnothing
5:foreach entity

r∈Er\\in Edo

6:foreach of

M2M\_\{2\}uniform samples

ppfrom the causal neighbors of

rrdo

7:if

p≠vip\\neq v\_\{i\}and

p∉Ep\\notin Eand

ppis not a

11\-hop neighbor of

viv\_\{i\}then

8:

m⁡\[p\]←m⁡\[p\]\+1m\[p\]\\leftarrow m\[p\]\+1
9:endif

10:endfor

11:endfor

12:

Ncollab←N\_\{\\mathrm\{collab\}\}\\leftarrowtop

KcollabK\_\{\\mathrm\{collab\}\}peers by

mm; pad and mask as needed

13:return

NcollabN\_\{\\mathrm\{collab\}\}

#### A\.1\.2CRW Sampler: Walk Kernel, PPR Equivalence, Connectivity, and Edge Cases

This appendix expands the CRW local subgraph sampler of §[2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1)\(Algorithm[1](https://arxiv.org/html/2609.26855#alg1)\): the walk kernel, its convergence to causal PPR, the connectivity of the induced subgraph, and the fixed\-length padding used when a seed’s causal neighborhood is sparse\.

##### Walk Kernel\.

Fix a seeds=\(vi,tseed\)s=\(v\_\{i\},t\_\{\\mathrm\{seed\}\}\)and a restart probabilityp∈\(0,1\)p\\in\(0,1\)\. To mitigate the fan\-out from high\-degree hubs, we restrict a given nodeuuto a subset of up toMMcausal neighbors\. While this truncation can be performed randomly, we default to a recency\-based approach to prioritize temporally relevant interactions\. Specifically, let𝒩⁡\(u,tseed\)\\mathcal\{N\}\(u;t\_\{\\mathrm\{seed\}\}\)be the set of all temporal neighbors of nodeuuprior to the seed time:

𝒩\(u;tseed\)=\{v∈V∣\(u,v\)∈E,τ\(u,v\)≤tseed\}\\mathcal\{N\}\(u;t\_\{\\mathrm\{seed\}\}\)=\\\{v\\in V\\mid\(u,v\)\\in E,\\,\\tau\(u,v\)\\leq t\_\{\\mathrm\{seed\}\}\\\}We then define the sampled neighborhood𝒩M​\(u,s\)⊆𝒩⁡\(u,tseed\)\\mathcal\{N\}\_\{M\}\(u;s\)\\subseteq\\mathcal\{N\}\(u;t\_\{\\mathrm\{seed\}\}\)as the subset containing theMMnodes with the largestτ⁡\(u,v\)\\tau\(u,v\)values \(i\.e\., the most recent interactions\)\. If\|𝒩⁡\(u,tseed\)\|<M\|\\mathcal\{N\}\(u;t\_\{\\mathrm\{seed\}\}\)\|<M, all valid neighbors are kept\. At each step, a walk currently at nodeuuwill restart to the seed with probabilitypp, or otherwise transition uniformly to one of itsMMvalid causal neighbors:

P⁡\(u→v∣s\)=\{𝕀\[v=vi\],if​𝒩M​\(u,s\)=∅,p𝕀\[v=vi\]\+\(1−p\)𝕀\[v∈𝒩M\(u;s\)\]\|𝒩M​\(u,s\)\|,otherwise\.P\(u\\to v\\mid s\)=\\begin\{cases\}\\mathbb\{I\}\[v=v\_\{i\}\],&\\text\{if \}\\mathcal\{N\}\_\{M\}\(u;s\)=\\varnothing,\\\\\[4\.0pt\] p\\,\\mathbb\{I\}\[v=v\_\{i\}\]\+\(1\-p\)\\,\\frac\{\\mathbb\{I\}\[v\\in\\mathcal\{N\}\_\{M\}\(u;s\)\]\}\{\|\\mathcal\{N\}\_\{M\}\(u;s\)\|\},&\\text\{otherwise\.\}\\end\{cases\}\(9\)
If a dead end is reached where𝒩M​\(u,s\)=∅\\mathcal\{N\}\_\{M\}\(u;s\)=\\varnothing, the walk automatically teleports back toviv\_\{i\}\. We executeWWindependent walks of lengthLLfromviv\_\{i\}, recording the total visit countvisit⁡\[v\]\\mathrm\{visit\}\[v\]and the minimum discovery depthdepth⁡\[v\]\\mathrm\{depth\}\[v\]for every visited node\.

Equivalence to Personalized PageRank\.The Monte Carlo estimate of the visit distribution is governed by three parameters: the number of walksWW, the maximum walk lengthLL, and the branching truncation limitMM\. Normalizing the visit frequencies over theseWWwalks yields an empirical distributionπ^s​\(v\)\\hat\{\\pi\}\_\{s\}\(v\)that asymptotically converges to the exact Personalized PageRank \(PPR\) vectorπs​\(v\)\\pi\_\{s\}\(v\)of the seedviv\_\{i\}when all parameters approach infinity:

π^s​\(v\)=visit​\[v\]∑uvisit​\[u\]→W,L,M→∞πs​\(v\)\\hat\{\\pi\}\_\{s\}\(v\)=\\frac\{\\text\{visit\}\[v\]\}\{\\sum\_\{u\}\\text\{visit\}\[u\]\}\\xrightarrow\{W,L,M\\to\\infty\}\\pi\_\{s\}\(v\)\(10\)
In this limit,L→∞L\\to\\inftyeliminates the finite\-horizon bias,W→∞W\\to\\inftysuppresses the Monte Carlo variance, andM→∞M\\to\\inftyrecovers the exact transition probabilities of a standard random walk with restart\. In practice, however, keepingMMfinite serves as a crucial regularizer: it bounds per\-step complexity independently of hub degree, and our default recency\-based truncation injects a valuable temporal prior for time\-dependent tasks\.

##### Token Selection and Hop Labels\.

The seed fills slot00and the remainingK−1K\-1tokens are the non\-seed nodes of highest visit count—their truncated\-PPR rank\. If the walks yield fewer thanK−1K\-1unique nodes, each is kept once and the rest are resampled in proportion to visit count; a seed with no causal history instead draws uniformly fromVVinto a dedicated fallback hop bin\. Every non\-fallback token is labeledmin⁡\(hBFS,hwalk\)\\min\(h\_\{\\mathrm\{BFS\}\},h\_\{\\mathrm\{walk\}\}\), the tighter of its BFS distance within the induced subgraph and its shallowest walk depthhwalkh\_\{\\mathrm\{walk\}\}\.

##### Subgraph Connectivity\.

A natural concern with PageRank\-based sampling on scale\-free relational graphs is that high\-degree hubs might act as probability sinks, dominating the token budget and inducing a topologically sparse or disconnected subgraph\. Three properties of the walk kernel \([9](https://arxiv.org/html/2609.26855#A1.E9)\) rule this out\. First, the restart probabilityppimposes an exponential decay on the visit distribution with respect to geodesic distance from the seed, so probability mass cannot accumulate at a multi\-hop hub without proportionately weighting the one\-hop nodes that bridge the seed to it\. Second, theMM\-truncation bounds the branching factor at every step: capping the effective degree traversed during a walk curbs the combinatorial path explosion that otherwise skews the stationary distribution toward global hubs\. Third, whereas uniform BFS sampling at a high\-degree node draws an essentially random subset of neighbors—typically inducing a disconnected, star\-like subgraph with near\-zero clustering—CRW aggregates visit frequencies across many short walks, a trace\-based signal that intrinsically favors nodes sharing dense structural corridors with the seed\. The top\-rankedK−1K\-1tokens therefore form a cohesive subgraph with substantially higher internal edge density, preserving the structural integrity that the Local Module’s self\-attention \(§[2\.4](https://arxiv.org/html/2609.26855#S2.SS4)\) relies on\.

##### Handling Sparse Neighborhoods and Edge Cases\.

Because all three branches \(struct, temp and collab\) require fixed\-length sequences, the samplers must gracefully handle structural sparsity\. If a sampler extractsnnunique valid nodes where0<n<K−10<n<K\-1, it first retains allnnnodes and then fills the remainingK−1−nK\-1\-nsequence slots via resampling \(using visit\-count weights for CRW, and uniform weights for the temporal and collaborative branches\)\. In the extreme edge case where a seed possesses absolutely no valid causal history \(n=0n=0\), the sequence is padded using nodes drawn uniformly from the entire graphVV\. To strictly prevent artificial topological leakage, these uniform fallback tokens are explicitly assigned to a dedicated fallback hop\-embedding bin\.

#### A\.1\.3Collaborative Sampler: Two\-Hop Probe as a Jaccard\-Numerator Estimator

This appendix formalizes the claim of §[2\.2\.3](https://arxiv.org/html/2609.26855#S2.SS2.SSS3)that the collaborative sampler’s per\-peer hit count \(Algorithm[3](https://arxiv.org/html/2609.26855#alg3)\) is a Monte Carlo estimate of the Jaccard\-overlap numerator between the seed’s and a candidate peer’s causal neighborhoods\.

##### Causal neighborhoods and target quantity\.

For any nodeuu, its causal neighbor set at the seed time and the corresponding degree are

𝒩\(u;s\)=\{v:\(u,v\)∈E,τ\(u,v\)≤tseed\},du=\|𝒩\(u;s\)\|\.\\mathcal\{N\}\(u;s\)=\\bigl\\\{\\,v:\(u,v\)\\in E,\\ \\tau\(u,v\)\\leq t\_\{\\mathrm\{seed\}\}\\,\\bigr\\\},\\qquad d\_\{u\}=\\bigl\|\\mathcal\{N\}\(u;s\)\\bigr\|\.Writing𝒮⁡\(vi,p\)=𝒩⁡\(vi,s\)∩𝒩⁡\(p,s\)\\mathcal\{S\}\(v\_\{i\},p\)=\\mathcal\{N\}\(v\_\{i\};s\)\\cap\\mathcal\{N\}\(p;s\)for the shared\-intermediary set of the seedviv\_\{i\}and a candidate peerpp, the collaborative affinity we target is the numerator of their neighborhood Jaccard coefficient:

J⁡\(vi,p\)=\|𝒮⁡\(vi,p\)\|\|𝒩⁡\(vi,s\)∪𝒩⁡\(p,s\)\|,num⁡\(vi,p\)=\|𝒮⁡\(vi,p\)\|\.J\(v\_\{i\},p\)=\\frac\{\\bigl\|\\mathcal\{S\}\(v\_\{i\},p\)\\bigr\|\}\{\\bigl\|\\mathcal\{N\}\(v\_\{i\};s\)\\cup\\mathcal\{N\}\(p;s\)\\bigr\|\},\\qquad\\mathrm\{num\}\(v\_\{i\},p\)=\\bigl\|\\mathcal\{S\}\(v\_\{i\},p\)\\bigr\|\.\(11\)

##### Two\-hop probe and hit count\.

Hop 1 draws a setEEofM1M\_\{1\}intermediaries uniformly without replacement from𝒩⁡\(vi,s\)\\mathcal\{N\}\(v\_\{i\};s\), and for eachr∈Er\\in E, Hop 2 drawsM2M\_\{2\}peers uniformly without replacement from𝒩⁡\(r,s\)\\mathcal\{N\}\(r;s\)\. After discarding the seed, the Hop\-1 set, and the seed’s one\-hop neighbors, every surviving peer accumulates the hit count

m\[p\]=∑r∈E𝕀\[p∈Hop2\(r\)\],p∉\{vi\}∪𝒩\(vi;s\),m\[p\]=\\sum\_\{r\\in E\}\\mathbb\{I\}\\bigl\[\\,p\\in\\mathrm\{Hop2\}\(r\)\\,\\bigr\],\\qquad p\\notin\\\{v\_\{i\}\\\}\\cup\\mathcal\{N\}\(v\_\{i\};s\),\(12\)which is nonzero only for shared intermediariesr∈𝒮⁡\(vi,p\)r\\in\\mathcal\{S\}\(v\_\{i\},p\), sincep∈𝒩⁡\(r,s\)⇔r∈𝒩⁡\(p,s\)p\\in\\mathcal\{N\}\(r;s\)\\Leftrightarrow r\\in\\mathcal\{N\}\(p;s\)\.

##### Expected hit count\.

Under simple random sampling without replacement the marginal inclusion probabilities areP⁡\(r∈E\)=M1/dviP\(r\\in E\)=M\_\{1\}/d\_\{v\_\{i\}\}andP⁡\(p∈Hop2⁡\(r\)∣r∈E\)=M2/drP\\bigl\(p\\in\\mathrm\{Hop2\}\(r\)\\mid r\\in E\\bigr\)=M\_\{2\}/d\_\{r\}forp∈𝒩⁡\(r,s\)p\\in\\mathcal\{N\}\(r;s\), so for budgetsM1≤dviM\_\{1\}\\leq d\_\{v\_\{i\}\}andM2≤drM\_\{2\}\\leq d\_\{r\}

𝔼⁡\[m⁡\[p\]\]=∑r∈𝒮⁡\(vi,p\)M1dvi⋅M2dr=M1​M2dvi​∑r∈𝒮⁡\(vi,p\)1dr\.\\mathbb\{E\}\\bigl\[m\[p\]\\bigr\]=\\sum\_\{r\\in\\mathcal\{S\}\(v\_\{i\},p\)\}\\frac\{M\_\{1\}\}\{d\_\{v\_\{i\}\}\}\\cdot\\frac\{M\_\{2\}\}\{d\_\{r\}\}=\\frac\{M\_\{1\}M\_\{2\}\}\{d\_\{v\_\{i\}\}\}\\sum\_\{r\\in\\mathcal\{S\}\(v\_\{i\},p\)\}\\frac\{1\}\{d\_\{r\}\}\.\(13\)

##### Proportionality to the Jaccard numerator\.

Rescaling \([13](https://arxiv.org/html/2609.26855#A1.E13)\) by the peer\-independent seed constantdvi/\(M1​M2\)d\_\{v\_\{i\}\}/\(M\_\{1\}M\_\{2\}\)yields an unbiased estimator of a degree\-discounted common\-neighbor count:

c^​\(p\)=dviM1​M2​m​\[p\],𝔼⁡\[c^​\(p\)\]=∑r∈𝒮⁡\(vi,p\)1dr\.\\hat\{c\}\(p\)=\\frac\{d\_\{v\_\{i\}\}\}\{M\_\{1\}M\_\{2\}\}\\,m\[p\],\\qquad\\mathbb\{E\}\\bigl\[\\hat\{c\}\(p\)\\bigr\]=\\sum\_\{r\\in\\mathcal\{S\}\(v\_\{i\},p\)\}\\frac\{1\}\{d\_\{r\}\}\.\(14\)When shared intermediaries have comparable degreedr≈d¯d\_\{r\}\\approx\\bar\{d\}, this collapses to a scaled Jaccard numerator,

𝔼⁡\[m⁡\[p\]\]≈M1​M2dvi​d¯\|𝒮⁡\(vi,p\)\|∝num⁡\(vi,p\)\.\\mathbb\{E\}\\bigl\[m\[p\]\\bigr\]\\approx\\frac\{M\_\{1\}M\_\{2\}\}\{d\_\{v\_\{i\}\}\\,\\bar\{d\}\}\\,\\bigl\|\\mathcal\{S\}\(v\_\{i\},p\)\\bigr\|\\;\\propto\\;\\mathrm\{num\}\(v\_\{i\},p\)\.\(15\)Sincedvid\_\{v\_\{i\}\}is fixed across all peers of a given seed, ranking candidates bym⁡\[p\]m\[p\]and keeping the topKcollabK\_\{\\mathrm\{collab\}\}\(Algorithm[3](https://arxiv.org/html/2609.26855#alg3)\) selects the peers of largest expected neighborhood overlap, with the1/dr1/d\_\{r\}weighting additionally down\-weighting popular high\-degree intermediaries\.

#### A\.1\.4Token Encoder Details

This appendix gives the exact per\-encoder formulas for the 5\-tuple token construction summarized in §[2\.3](https://arxiv.org/html/2609.26855#S2.SS3)\. Each of theKKsampled tokensvjv\_\{j\}is processed by the following specialized encoders before integration:

1. 1\.Node Feature Encoder:Raw columnar attributesxvjx\_\{v\_\{j\}\}are encoded into add\-dimensional embedding\[[49](https://arxiv.org/html/2609.26855#bib.bib49),[50](https://arxiv.org/html/2609.26855#bib.bib50),[51](https://arxiv.org/html/2609.26855#bib.bib51)\]using a PyTorch Frame\[[43](https://arxiv.org/html/2609.26855#bib.bib23)\]multimodal encoder, which processes and aggregates numerical, categorical, and text modalities: hfeat​\(vj\)=MultiModalEncoder⁡\(xvj\)∈ℝdh\_\{\\mathrm\{feat\}\}\(v\_\{j\}\)=\\mathrm\{MultiModalEncoder\}\(x\_\{v\_\{j\}\}\)\\in\\mathbb\{R\}^\{d\}\(16\)
2. 2\.Node Type Encoder:Converts the table\-specific entity typeϕ⁡\(vj\)\\phi\(v\_\{j\}\)into a learned representation to capture heterogeneous schema semantics: htype​\(vj\)=Wtype⋅onehot⁡\(ϕ⁡\(vj\)\)∈ℝdh\_\{\\mathrm\{type\}\}\(v\_\{j\}\)=W\_\{\\mathrm\{type\}\}\\cdot\\mathrm\{onehot\}\(\\phi\(v\_\{j\}\)\)\\in\\mathbb\{R\}^\{d\}\(17\)whereWtype∈ℝd×\|𝒯\|W\_\{\\mathrm\{type\}\}\\in\\mathbb\{R\}^\{d\\times\|\\mathcal\{T\}\|\}is a learnable weight matrix\.
3. 3\.Hop Encoder:Captures the structural proximityp⁡\(vi,vj\)p\(v\_\{i\},v\_\{j\}\)between the seed nodeviv\_\{i\}and its neighborvjv\_\{j\}: hhop​\(vi,vj\)=Whop⋅onehot⁡\(p⁡\(vi,vj\)\)∈ℝdh\_\{\\mathrm\{hop\}\}\(v\_\{i\},v\_\{j\}\)=W\_\{\\mathrm\{hop\}\}\\cdot\\mathrm\{onehot\}\(p\(v\_\{i\},v\_\{j\}\)\)\\in\\mathbb\{R\}^\{d\}\(18\)Rather than a single shortest\-path distance, the label is the tighter of two causal upper bounds—the BFS distance within the inducedKK\-token subgraph and the CRW walk depth: p⁡\(vi,vj\)=min⁡\(hBFS​\(vi,vj\),hwalk​\(vj\)\),p\(v\_\{i\},v\_\{j\}\)=\\min\\bigl\(h\_\{\\mathrm\{BFS\}\}\(v\_\{i\},v\_\{j\}\),\\ h\_\{\\mathrm\{walk\}\}\(v\_\{j\}\)\\bigr\),\(19\)with a dedicated bin reserved for uniformly\-drawn fallback tokens\.
4. 4\.Time Encoder:Linearly transforms the relative temporal difference to ensure temporal alignment: htime​\(vi,vj\)=Wtime⋅\(τ⁡\(vj\)−τ⁡\(vi\)\)∈ℝdh\_\{\\mathrm\{time\}\}\(v\_\{i\},v\_\{j\}\)=W\_\{\\mathrm\{time\}\}\\cdot\(\\tau\(v\_\{j\}\)\-\\tau\(v\_\{i\}\)\)\\in\\mathbb\{R\}^\{d\}\(20\)whereWtime∈ℝdW\_\{\\mathrm\{time\}\}\\in\\mathbb\{R\}^\{d\}is a learnable parameter\.
5. 5\.Subgraph Positional Encoder \(PE\):Captures local graph topology \(e\.g\., cycles, parent\-child relationships\) by applying a lightweight GIN to the sampled local subgraph’s adjacency matrixAlocalA\_\{\\mathrm\{local\}\}\. To break structural symmetries while preserving permutation equivariance, we inject stochastically resampled random node featuresZrandomZ\_\{\\mathrm\{random\}\}at every training step following the convention in\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]: hpe​\(vj\)=GIN​\(Alocal,Zrandom\)j∈ℝdh\_\{\\mathrm\{pe\}\}\(v\_\{j\}\)=\\mathrm\{GIN\}\(A\_\{\\mathrm\{local\}\},Z\_\{\\mathrm\{random\}\}\)\_\{j\}\\in\\mathbb\{R\}^\{d\}\(21\)

The final token representation is formed by concatenating the five encoded elements and mixing them via a learned projection matrixWmix∈ℝd×5​dW\_\{\\mathrm\{mix\}\}\\in\\mathbb\{R\}^\{d\\times 5d\}:

htoken\(vj\)=Wmix⋅\[hfeat\(vj\)∥htype\(vj\)∥hhop\(vi,vj\)∥htime\(vi,vj\)∥hpe\(vj\)\]h\_\{\\mathrm\{token\}\}\(v\_\{j\}\)=W\_\{\\mathrm\{mix\}\}\\cdot\[h\_\{\\mathrm\{feat\}\}\(v\_\{j\}\)\\parallel h\_\{\\mathrm\{type\}\}\(v\_\{j\}\)\\parallel h\_\{\\mathrm\{hop\}\}\(v\_\{i\},v\_\{j\}\)\\parallel h\_\{\\mathrm\{time\}\}\(v\_\{i\},v\_\{j\}\)\\parallel h\_\{\\mathrm\{pe\}\}\(v\_\{j\}\)\]\(22\)

### A\.2Complexity Analysis

#### A\.2\.1Subgraph Sampler Time Complexity

Table[3](https://arxiv.org/html/2609.26855#A1.T3)reports the per\-seed cost of the three causal samplers of §[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)\. The CRW sampler \(§[2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1)\) runsWWindependent restart walks of lengthLLfrom the seed, giving a per\-seed cost ofO⁡\(W​L​log⁡Dmax\)O\(WL\\log D\_\{\\max\}\), whereDmaxD\_\{\\max\}is the maximum node degree and thelog⁡Dmax\\log D\_\{\\max\}factor is the per\-step causal\-neighbor lookup\. Under the default parameters \(W=100W=100,L=10L=10,p=0\.15p=0\.15,M=50M=50,K=300K=300\) this avoids linear dependence on hub degree, since the recency\-basedMM\-truncation caps the per\-step branching regardless of hub degree\. The collaborative sampler \(§[2\.2\.3](https://arxiv.org/html/2609.26855#S2.SS2.SSS3)\) drawsM1M\_\{1\}first\-hop intermediaries andM2M\_\{2\}second\-hop peers from each, for a per\-seed cost ofO⁡\(M1​M2​log⁡Dmax\)O\(M\_\{1\}M\_\{2\}\\log D\_\{\\max\}\)\. The temporal sampler \(§[2\.2\.2](https://arxiv.org/html/2609.26855#S2.SS2.SSS2)\) scans a seed\-independent, global time\-sorted event stream with type\-balanced budgets: for each of theT=\|𝒯\|T=\|\\mathcal\{T\}\|node types it binary\-searches the stream to locate the causal window \(O⁡\(log⁡\|E\|\)O\(\\log\|E\|\), with\|E\|\|E\|the number of REG edges\), then collects theB=Ktemp/TB=K\_\{\\mathrm\{temp\}\}/Tmost\-recent nodes per type, giving a per\-seed cost ofO⁡\(T​log⁡\|E\|\+T​B\)O\(T\\log\|E\|\+TB\)\. Because the candidate pool is global, this cost is independent of the seed’s degree\. Crucially, because all extracted subgraphs and global neighbor sequences are pre\-computed and cached offline, this cost is heavily amortized; it is paid exactly once prior to training, adding zero traversal overhead to the active training loop\.

Table 3:Per\-seed time complexity of the three causal subgraph samplers \(§[2\.2](https://arxiv.org/html/2609.26855#S2.SS2)\)\.DmaxD\_\{\\max\}: maximum node degree;T=\|𝒯\|T=\|\\mathcal\{T\}\|: number of node types;B=Ktemp/TB=K\_\{\\mathrm\{temp\}\}/T: per\-type temporal budget;\|E\|\|E\|: number of REG edges\.
#### A\.2\.2Attention Module Time Complexity

This appendix collects the per\-seed costs ofQuartet’s attention modules: the local self\-attention module of §[2\.4](https://arxiv.org/html/2609.26855#S2.SS4)and the four global branches of §[2\.5](https://arxiv.org/html/2609.26855#S2.SS5)\.

##### Local attention module\.

The local module appliesLlocalL\_\{\\mathrm\{local\}\}layers of full self\-attention over the fixedKK\-token subgraph, costingO⁡\(Llocal​K2​d\)O\(L\_\{\\mathrm\{local\}\}K^\{2\}d\)per seed\. Because the CRW sampler holdsKKconstant regardless of hub degree \(§[2\.2\.1](https://arxiv.org/html/2609.26855#S2.SS2.SSS1)\), this cost is fixed across seeds and datasets rather than scaling with local density\.

##### Feature and topological codebook branches\.

Both codebook reads \(§[2\.5\.1](https://arxiv.org/html/2609.26855#S2.SS5.SSS1)\) are inexpensive because the archetypes are batch\-shared; letR=Rstruct=RfeatR=R\_\{\\mathrm\{struct\}\}=R\_\{\\mathrm\{feat\}\}denote the shared codebook size\. The key and value projectionsWK​EbW\_\{K\}E\_\{b\}andWV​EbW\_\{V\}E\_\{b\}costO⁡\(R​d2\)O\(Rd^\{2\}\)and are computed once per batch and reused across all seeds, rather than recomputed for every seed as in a naive codebook lookup; each seed then adds only anO⁡\(R​d\)O\(Rd\)query–archetype attention\. The shared projections likewise cap the key/value activation memory atO⁡\(R​d\)O\(Rd\)instead of letting it grow linearly with the number of seeds—saving roughly0\.50\.5GB per codebook when the batch size, archetype countRR, and widthddare all512512\.

##### Temporal and collaborative cross\-attention branches\.

The temporal and collaborative branches \(§[2\.5\.2](https://arxiv.org/html/2609.26855#S2.SS5.SSS2)\) replace theO⁡\(K2​d\)O\(K^\{2\}d\)cost of full self\-attention over their length\-KKcontext𝐂b\\mathbf\{C\}\_\{b\}\(b∈\{temp,collab\}b\\in\\\{\\mathrm\{temp\},\\mathrm\{collab\}\\\}\) with an asymmetric Perceiver bottleneck: a fixed budget ofLperc≪KL\_\{\\mathrm\{perc\}\}\\ll Klatents cross\-attends over the context, reducing each branch’s cost toO⁡\(Lperc​K​d\)O\(L\_\{\\mathrm\{perc\}\}Kd\)—linear in the context length\. WithLperc=32L\_\{\\mathrm\{perc\}\}=32andK=300K=300this holds each branch’s compute and its fusion\-input width constant regardless of how large the underlying temporal or collaborative neighborhood is\.

#### A\.2\.3Empirical Runtime, Memory, and Storage Comparison

To complement the asymptotic analysis above with a direct empirical measurement, we profileQuartetagainst its RelGT base on the five larger classification tasks of §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\(Table[5](https://arxiv.org/html/2609.26855#A1.T5)\), holding batch size, sampler token budgets, and local\-layer depth fixed across both models and running each on a single A100 GPU per model to keep the comparison unconfounded by DDP world size\. Table[4](https://arxiv.org/html/2609.26855#A1.T4)reports, for every task, the ratio ofQuartet’s cost to RelGT’s along five axes: per\-epoch train\+val wall\-clock, inference throughput, one\-time offline precomputation, peak GPU memory, on\-disk cache size, and parameter count\.

##### Parameters and memory scale with the quad\-branch capacity, as expected\.

Parameter count sits in a tight2\.172\.17–2\.30×2\.30\\timesband across every task, consistent with it being a fixed property of the four global branches’ added capacity \(§[2\.5](https://arxiv.org/html/2609.26855#S2.SS5)\) rather than a task\-dependent quantity\. Peak GPU memory follows the same architectural source—the codebook and Perceiver branches’ batch\-shared buffers \(§[A\.2\.2](https://arxiv.org/html/2609.26855#A1.SS2.SSS2)\)—and is higher on every task, averaging2\.58×2\.58\\timesRelGT’s\. On\-disk cache size is the largest relative cost, averaging7\.76×7\.76\\times, because it accumulates the additional per\-seed temporal and collaborative neighbor sequences that RelGT’s local\-only sampler does not cache\.

##### Runtime is favorable on average, but we do not attribute it primarily to the samplers’ asymptotic advantage\.

Per\-epoch time is1\.39×1\.39\\timesRelGT’s on average \(as low as0\.84×0\.84\\timesonrel\-amazon/user\-churn\), and inference throughput favorsQuarteton three of the five tasks, most on the tasks with the largest test sets\. Offline precomputation is faster forQuarteton four of five tasks, by1\.31\.3–9\.7×9\.7\\times\. While §[A\.2\.1](https://arxiv.org/html/2609.26855#A1.SS2.SSS1)shows CRW’s per\-seed cost is bounded independently of hub degree, we traced this specific empirical gap to our profiling harness and found it is driven substantially by implementation differences between the two reproduction pipelines—in particular, an unguarded multi\-process precompute step in the RelGT baseline that re\-derives its adjacency structure from scratch on every worker and every data chunk, rather than once per split\. These differences are orthogonal to the sampling algorithm and would likely narrow this specific gap if fixed on the baseline side; we therefore report the measured numbers without treating them as direct validation of the asymptotic argument in §[A\.2\.1](https://arxiv.org/html/2609.26855#A1.SS2.SSS1)\. The inference\-throughput advantage has a more direct architectural explanation: RelGT’s EMA\-K\-Means global module recomputes each centroid’s current occupancy viaunique\(\)on every forward pass, an operation whose output size is data\-dependent and therefore forces a GPU–host synchronization on every batch, at both train and test time;Quartet’s codebook and Perceiver branches \(§[2\.5\.1](https://arxiv.org/html/2609.26855#S2.SS5.SSS1), §[2\.5\.2](https://arxiv.org/html/2609.26855#S2.SS5.SSS2)\) are static\-shape tensor operations throughout and incur no equivalent stall\. This cost is a small fraction of a backward\-dominated training step but a much larger fraction of a short, forward\-only inference step, which is consistent with the throughput advantage being largest on the tasks with the most test batches and narrowing on the smallest task in our set\.

Table 4:Empirical runtime, memory, and storage ofQuartetrelative to RelGT \(ratioQuartet/RelGT\), measured on the five larger classification tasks of §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\(Table[5](https://arxiv.org/html/2609.26855#A1.T5)\), each run on a single A100 GPU per model for a matched, unconfounded comparison\. Epoch time is mean per\-epoch train\+val wall\-clock; throughput is test\-set samples/sec at inference; precompute is the one\-time offline sampling/caching pass; cache is total on\-disk size of the pre\-cached artefacts\. For Epoch time, Precompute, Peak mem, Cache, and Params,\>1×\>1\\timesmeansQuartetcosts more; for Throughput,\>1×\>1\\timesmeansQuartetis faster\.
##### The added cost is a dial, not a fixed tax\.

GPU memory and cache storage are the costs we attribute with the most confidence to our architecture, and both scale specifically with the four global branches rather than with the local module or samplers\. Crucially,Quartetis not a single fixed\-cost model but a family of configurations—the full quad\-branch model, or any subset of its branches—and the leave\-one\-out ablation of §[4\.3](https://arxiv.org/html/2609.26855#S4.SS3)already quantifies, per task, which branches are worth their share of this cost: no single branch is globally redundant, as the dominant branch shifts across tasks \(§[4\.3](https://arxiv.org/html/2609.26855#S4.SS3)\)\. A practitioner can therefore pay only for the branch\(es\) that carry signal for their specific downstream task and recover most of RelGT’s memory and storage footprint elsewhere, rather than weighing the full\-model cost against the full\-model gain\.

### A\.3Experiment Details

#### A\.3\.1Full Implementation and Training Details

All models are trained end\-to\-end with Adam at a constant learning rate of1×10−41\{\\times\}10^\{\-4\}, batch size 512, and gradient clipping at1\.01\.0; we apply no learning\-rate warmup or decay schedule\. The training budget is set per task: 100 epochs for the seven smaller tasks and 10 epochs for the five larger tasks\. Local\-transformer width follows the RelGT defaults\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]\(c=512c=512channels,h=4h=4heads\)\. The number of local layersLlocalL\_\{\\mathrm\{local\}\}, dropout \(tied across the feed\-forward and attention paths\), and weight decay are tuned per task: on the seven smaller tasks we search a3×3×33\{\\times\}3\{\\times\}3grid ofLlocal∈\{1,4,8\}L\_\{\\mathrm\{local\}\}\\in\\\{1,4,8\\\}, dropout∈\{0\.3,0\.4,0\.5\}\\in\\\{0\.3,0\.4,0\.5\\\}, and weight decay∈\{5×10−5,5×10−4,5×10−3\}\\in\\\{5\{\\times\}10^\{\-5\},5\{\\times\}10^\{\-4\},5\{\\times\}10^\{\-3\}\\\}\(reproducing RelGT’sL×L\{\\times\}dropout grid and adding a weight\-decay axis\), while on the five larger tasks we fixLlocal=4L\_\{\\mathrm\{local\}\}=4and search a3×33\{\\times\}3grid of dropout∈\{0\.1,0\.3,0\.5\}\\in\\\{0\.1,0\.3,0\.5\\\}and weight decay∈\{1×10−5,5×10−5,5×10−4\}\\in\\\{1\{\\times\}10^\{\-5\},5\{\\times\}10^\{\-5\},5\{\\times\}10^\{\-4\}\\\}\. The per\-task best configurations are reported in Appendix[A\.3\.3](https://arxiv.org/html/2609.26855#A1.SS3.SSS3)\. These local hyperparameters were identified on the CRW\-augmented RelGT base \(§[4\.1](https://arxiv.org/html/2609.26855#S4.SS1)\) and held fixed during the subsequent quad\-branch capacity search\. CRW usesW=100W=100walks,L=10L=10steps, restart probabilityp=0\.15p=0\.15, recent\-M=50M=50, and token budgetK=300K=300\.

Quad\-branch capacity—Perceiver latentsLperc∈\{16,32,64\}L\_\{\\mathrm\{perc\}\}\\in\\\{16,32,64\\\}and codebook archetypesRstruct=Rfeat∈\{128,256,512\}R\_\{\\mathrm\{struct\}\}=R\_\{\\mathrm\{feat\}\}\\in\\\{128,256,512\\\}—is configured per task, with the shared self\-attention depth held fixed atLsa=4L\_\{\\mathrm\{sa\}\}=4and the branch outputs fused by concatenation \(the gate\-freenogate\_concatdefault of §[2\.6](https://arxiv.org/html/2609.26855#S2.SS6)\); the full per\-arm capacity results are tabulated in Appendix[A\.3\.4](https://arxiv.org/html/2609.26855#A1.SS3.SSS4)\. The collaborative sampler uses\(M1,M2,Kcollab\)=\(50,50,300\)\(M\_\{1\},M\_\{2\},K\_\{\\mathrm\{collab\}\}\)=\(50,50,300\), and the temporal branch draws itsKtemp=300K\_\{\\mathrm\{temp\}\}=300tokens using the type\-balanced sampler of §[2\.2\.2](https://arxiv.org/html/2609.26855#S2.SS2.SSS2)\(Algorithm[2](https://arxiv.org/html/2609.26855#alg2)\) with per\-type budgetB=Ktemp/\|𝒯\|B=K\_\{\\mathrm\{temp\}\}/\|\\mathcal\{T\}\|over theΔ​t=365\\Delta t=365\-day causal window; the candidate pool is global \(seed\-independent\), but the per\-type budget ensures no single high\-frequency node type dominates the sample\. Both cross\-attention branches thus operate at the sameK=300K=300token budget as the CRW local context\. The pre\-cache pipeline writes the four artifacts per seed to a single HDF5 file atomically \(𝚝𝚖𝚙\\mathtt\{tmp\}\-file \+𝚘𝚜\.𝚛𝚎𝚗𝚊𝚖𝚎\\mathtt\{os\.rename\}\) and is consumed at train time via an𝚖𝚖𝚊𝚙\\mathtt\{mmap\}\-backed loader that performs no on\-line graph traversal\. Checkpoint selection is done by best validation ROC\-AUC\.

#### A\.3\.2Hyperparameter Tuning Strategy and Baseline Comparisons

To ensure a fair and computationally realistic comparison, we adopted a deliberate hyperparameter tuning strategy across all evaluated models\. We directly applied the published optimal hyperparameters for HGT and RelGT\. Re\-tuning was deemed unnecessary because the classification datasets inRelBenchv2 are unchanged to the prior version, aside from a patch to rel\-event user\-ignore that resolved temporal leakage\. ForQuartet, we avoided a computationally prohibitive joint grid search by employing a constrained, decoupled two\-stage approach:

##### Stage 1 \(Local Parameters\)\.

We first optimized the local module’s parameters \(LlocalL\_\{\\mathrm\{local\}\}, dropout, and weight decay\)\. Weight decay was included as an additional dimension specifically because the CRW sampler extracts denser, more highly connected subgraphs, which occasionally necessitated additional regularization to prevent overfitting\.

##### Stage 2 \(Global Parameters\)\.

Once the optimal local parameters were identified and frozen, we conducted a separate, limited search over the global branch capacities \(Perceiver latentsLpercL\_\{\\mathrm\{perc\}\}and codebook sizeRR\)\.

This decoupled strategy significantly restrictedQuartet’s total search budget compared to an exhaustive combinatorial grid, ensuring a fair and equitable comparison against the author\-optimized baselines from the literature\.

#### A\.3\.3Per\-Task Hyperparameters

Table[5](https://arxiv.org/html/2609.26855#A1.T5)lists the best per\-task configuration of the three tuned local hyperparameters—number of local layersLlocalL\_\{\\mathrm\{local\}\}, dropout, and weight decay—for all twelve classification tasks, selected over the grids described in §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\. All remaining local hyperparameters are shared across tasks \(§[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\)\.

Table 5:Per\-task best hyperparameters selected by the per\-task tuning of §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1): number of local layersLlocalL\_\{\\mathrm\{local\}\}, dropout, and weight decay\. Dropout is applied identically to the feed\-forward and attention paths\. The seven smaller tasks searchLlocal∈\{1,4,8\}L\_\{\\mathrm\{local\}\}\\in\\\{1,4,8\\\}; the five larger tasks fixLlocal=4L\_\{\\mathrm\{local\}\}=4\.DatasetTaskLlocalL\_\{\\mathrm\{local\}\}DropoutWeight decay*Smaller tasks*\(3×3×33\{\\times\}3\{\\times\}3grid\)rel\-avitouser\-clicks10\.45×10−35\{\\times\}10^\{\-3\}user\-visits80\.55×10−55\{\\times\}10^\{\-5\}rel\-eventuser\-ignore10\.35×10−55\{\\times\}10^\{\-5\}user\-repeat40\.55×10−35\{\\times\}10^\{\-3\}rel\-f1driver\-dnf40\.45×10−55\{\\times\}10^\{\-5\}driver\-top310\.55×10−35\{\\times\}10^\{\-3\}rel\-trialstudy\-outcome10\.55×10−45\{\\times\}10^\{\-4\}*Larger tasks*\(3×33\{\\times\}3grid,LlocalL\_\{\\mathrm\{local\}\}fixed\)rel\-amazonitem\-churn40\.15×10−55\{\\times\}10^\{\-5\}user\-churn40\.55×10−55\{\\times\}10^\{\-5\}rel\-hmuser\-churn40\.31×10−51\{\\times\}10^\{\-5\}rel\-stackuser\-badge40\.51×10−51\{\\times\}10^\{\-5\}user\-engagement40\.11×10−51\{\\times\}10^\{\-5\}
#### A\.3\.4Quad\-Branch Capacity Search

Table[6](https://arxiv.org/html/2609.26855#A1.T6)reports validation and test ROC\-AUC for every arm of the quad\-branch capacity grid of §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)—Perceiver latent budgetLperc∈\{16,32,64\}L\_\{\\mathrm\{perc\}\}\\in\\\{16,32,64\\\}crossed with codebook sizeRstruct=Rfeat∈\{128,256,512\}R\_\{\\mathrm\{struct\}\}=R\_\{\\mathrm\{feat\}\}\\in\\\{128,256,512\\\}—on all twelve classification tasks, averaged overn=4n=4seeds\. For each task the bold entry marks the configuration reported in theQuartetcolumn of Table[1](https://arxiv.org/html/2609.26855#S4.T1), with validation scores listed alongside\.

Table 6:Quad\-branch capacity search \(companion to §[A\.3\.1](https://arxiv.org/html/2609.26855#A1.SS3.SSS1)\): validation and test ROC\-AUC on the twelveRelBenchclassification tasks across theLperc×RL\_\{\\mathrm\{perc\}\}\\times Rcapacity grid\. Column groups index the Perceiver latent budgetLperc∈\{16,32,64\}L\_\{\\mathrm\{perc\}\}\\in\\\{16,32,64\\\}; sub\-columns \(128/256/512\) index the codebook sizeR=Rstruct=RfeatR=R\_\{\\mathrm\{struct\}\}=R\_\{\\mathrm\{feat\}\}\. Each arm is averaged overn=4n=4seeds\.Boldmarks the configuration reported in theQuartetcolumn of Table[1](https://arxiv.org/html/2609.26855#S4.T1); validation scores are listed alongside for completeness\.

### A\.4Additional Results

#### A\.4\.1Subgraph Connectivity Analysis: CRW extracts denser, more connected subgraphs compared to BFS2

In this section, we provide further evidence to support the claim that Causal Random Walk \(CRW\) sampler yields denser and tightly connected subgraphs compared to the BFS2 baseline in RelGT\. We start with \(I\) a visual comparison of the two samplers, then \(II\) break down the graph\-level statistics for the inducedKK\-token subgraphs \(K=300K=300, retaining causal edges\) across all 12 classification tasks and training seeds\.

##### \(I\) Visual intuition\.

Figure[4](https://arxiv.org/html/2609.26855#A1.F4)contrasts CRW and BFS2 subgraphs on two representative seeds that illustrate complementary regimes\. Panel \(a\) shows a*sparse\-neighborhood*seed, with low causal degree\. Because the seed possesses a low causal degree, BFS2 exhausts its two\-hop frontier after isolating only 5 distinct nodes\. This leaves 295 of the 300 allocated budget slots wasted on duplicates and padding\. Conversely, CRW’s restart\-walk mechanism successfully explores beyond this shallow frontier to extract 27 distinct nodes, forming a single connected component with an average degree ofd¯=1\.9\\bar\{d\}=1\.9and100%100\\%seed connectivity\. Panel \(b\) shows a*dense\-neighborhood*seed\. While both samplers successfully draw 300 distinct nodes, the resulting structural topologies are drastically different\. CRW builds a dense, seed\-anchored cluster comprising only 2 components \(d¯=3\.4\\bar\{d\}=3\.4,≈100%\\approx 100\\%seed\-connected, with only one disconnected node\)\. In contrast, BFS2 fragments the neighborhood into 90 disconnected components and leaves 88 nodes orphaned, resulting in a mere70%70\\%seed connectivity\. This severe fragmentation occurs because the BFS2 sampler selects two\-hop neighbors but omits the crucial one\-hop bridging nodes needed to connect them to the seed\.

The disconnected grey nodes in the BFS2 panel in Figure[4](https://arxiv.org/html/2609.26855#A1.F4)\(b\) are unreachable from the seed, representing a wasted token budget that cannot directly contribute to local message passing\. This structural fragmentation creates two distinct downstream bottlenecks\. First, it directly degrades the GIN\-based positional encoder \(Eq\.[21](https://arxiv.org/html/2609.26855#A1.E21); §[2\.3](https://arxiv.org/html/2609.26855#S2.SS3)\)\. Because GIN propagates information strictly along the edges of the subgraph adjacency matrixAlocalA\_\{\\mathrm\{local\}\}, these orphan nodes receive no neighborhood signals and collapse into identical positional encodings, eliminating the structural disambiguation the encoder is meant to provide\. Second, this collapse severely handicaps the Local Attention Module in Figure[2](https://arxiv.org/html/2609.26855#S2.F2)\. Even though the module applies full all\-pair self\-attention and can theoretically route information between any two tokens, the degraded positional encodings strip away crucial structural priors\. To compensate for the topological context lost during BFS2 sampling, the Transformer is forced to rely on additional self\-attention layers just to infer the basic structural relationships between these disconnected nodes\.

Figure 4:Subgraph visualizations comparing CRW and BFS2 across two representative seeds:\(a\)A sparse\-neighborhood seed\.\(b\)A dense\-neighborhood seed\. Red stars mark the seed node; blue nodes are reachable from the seed within the subgraph; grey nodes are disconnected orphans\. Note that the disconnected grey nodes in \(b\) for BFS2 receive degenerate GIN positional encodings \(Eq\. 21\), as no message\-passing paths exist to differentiate them structurally\.
##### \(II\) Aggregate Graph Metrics\.

Figure[5](https://arxiv.org/html/2609.26855#A1.F5)visualizes four key connectivity metrics across all twelve tasks to illustrate the structural differences between the samplers\. Panel \(a\) demonstrates that CRW consistently achieves a higher average degree, meaning each sampled node maintains more connections to others within the subgraph\. Panel \(b\) shows that CRW outperforms the BFS2 in seed\-connected ratio across the board, meaning more nodes in the subgraph are structurally connected to the seed node\. Panel \(c\) shows that CRW achieves a substantially larger average component size across most tasks, indicating that its sampled nodes coalesce into fewer, more cohesive clusters rather than scattering across many small fragments\. Finally, panel \(d\) illustrates token\-budget efficiency, where CRW proves far more effective at packing distinct, structurally relevant nodes into the fixed context window on the vast majority of tasks\. The only exceptions to this efficiency trend are the rel\-event tasks, where extreme seed fan\-out overwhelms the BFS2 subgraph with a large number of 1\-hop neighbors; in contrast, CRW’s hub truncation actively prevents this over\-sampling\. Even in these edge cases, CRW still matches BFS2 in core connectivity metrics such as average degree and seed\-connected ratio, Figure[5](https://arxiv.org/html/2609.26855#A1.F5)\(a\)\(b\)\.

Figure 5:CRW vs\. BFS2 subgraph structure across all 12RelBenchclassification tasks \(K=300K\{=\}300, causal edges\)\.Error bars show±1\\pm 1standard deviation across training seeds\.\(a\)Average degree: CRW wins on all 12 tasks\.\(b\)Seed\-connected ratio: CRW wins on all 12 tasks\.\(c\)Average component size: CRW produces larger components on all 12 tasks, reflecting greater structural cohesion\.\(d\)Token\-budget efficiency: CRW is more efficient on 10 of 12 tasks; the two rel\-event exceptions are explained by extreme seed fan\-out\.Table[7](https://arxiv.org/html/2609.26855#A1.T7)provides the complete per\-task numerical breakdown of these metrics, alongside raw edge density and clustering coefficients\. Notably, raw edge density is a confounded and unreliable comparison metric in this context\. While it mathematically appears to favor BFS2, this is simply an artifact of BFS2 generating smaller subgraphs\.

Table 7:Per\-task subgraph statistics for CRW vs\. BFS \(K=300K\{=\}300, causal edges, all training seeds\)\. Each cell reportsCRW \| BFSmeans\. Avg\. Degree, Seed\-Conn\. Ratio, \# Components, and Distinct Nodes are the structurally informative metrics\. Edge Density \(\|E\|/\(n2\)\|E\|/\\binom\{n\}\{2\}\) is inflated for BFS by its smaller subgraphs \(see text\), and Clustering Coefficient is near\-zero on 10/12 tasks due to the realational structure of the underlying graphs\.For a subgraph withnnunique nodes andMMedges, edge density and average degree are defined as

edge\_density=Mn⁡\(n−1\)/2,\\text\{edge\\\_density\}=\\frac\{M\}\{\\,n\(n\-1\)/2\\,\},\(23\)avg\_degree=2​Mn\.\\text\{avg\\\_degree\}=\\frac\{2M\}\{n\}\.\(24\)Substituting \([24](https://arxiv.org/html/2609.26855#A1.E24)\) into \([23](https://arxiv.org/html/2609.26855#A1.E23)\) reveals the direct relationship:

edge\_density=avg\_degreen−1\.\\text\{edge\\\_density\}=\\frac\{\\text\{avg\\\_degree\}\}\{n\-1\}\.\(25\)By effectively dividing the average degree byn−1n\-1, the quadratic denominator in \([23](https://arxiv.org/html/2609.26855#A1.E23)\) unfairly penalizes the CRW sampler for successfully extracting a much larger number of unique nodes\. Consequently, average degree \([24](https://arxiv.org/html/2609.26855#A1.E24)\) provides the correct, size\-invariant alternative for measuring structural density, ensuring the sampler isn’t penalized simply for recovering a larger number of relevant nodes\.

The clustering coefficient is not an appropriate measure of local cohesion for these graphs\. The standard clustering coefficient counts closed triangles among a node’s neighbors, but in most of the heterogeneous relational graphs underlying these benchmarks, closed triangles are structurally impossible under the predefined relational schema\. Accordingly, clustering is identically zero for both samplers on 10 of the 12 tasks\. The appropriate size\-invariant measures of local cohesion—average degree and seed\-connected ratio, both reported in Table[7](https://arxiv.org/html/2609.26855#A1.T7)—show clear CRW advantages across all tasks\. On the tworel\-stacktasks whose relational schema contains 3\-cycles and therefore allows closed triangles, the gap between CRW and BFS2 is minimal \(\|d\|≤0\.24\|d\|\\leq 0\.24\), confirming that CRW’s broader exploration does not sacrifice local cohesion\.

##### Summary and downstream impact\.

Ultimately, CRW provides a fundamentally denser and more seed\-connected topology than the uniform BFS2 baseline\. This dense connectivity directly improves the expressiveness of the GIN positional encoder and ensures the Local Attention Module attends over a cohesive neighborhood rather than a disjointed set of redundant orphan tokens\. Consequently, QUARTET, leveraging CRW, can effectively propagate seed\-relevant information while requiring fewer local self\-attention layers compared to RelGT \(as demonstrated in Figure[3](https://arxiv.org/html/2609.26855#S4.F3)\)\.

#### A\.4\.2Validation and Test Scores for All Baselines

Table[8](https://arxiv.org/html/2609.26855#A1.T8)reports both validation and test ROC\-AUC \(mean±\\pmstd\) for HGT, RelGT, andQuarteton all twelve classification tasks, complementing the test\-only summary of Table[1](https://arxiv.org/html/2609.26855#S4.T1)\. All four columns are averaged overn=4n=4seeds; the three baseline columns are our own reproductions, and theQuartetcolumn’s test rows coincide with Table[1](https://arxiv.org/html/2609.26855#S4.T1)\.

Table 8:Validation and test ROC\-AUC \(mean±\\pmstd\) on the twelveRelBenchentity\-classification tasks for the two reproduced graph\-transformer baselines—HGT\[[35](https://arxiv.org/html/2609.26855#bib.bib2)\]and RelGT\[[36](https://arxiv.org/html/2609.26855#bib.bib8)\]—andQuartet\. All three columns are averaged overn=4n=4seeds under a shared protocol; HGT and RelGT are our own reproductions\. The test rows coincide with Table[1](https://arxiv.org/html/2609.26855#S4.T1)\. Bold marks the best value in each \(task, split\) row across the three models\.
#### A\.4\.3Full Ablation Results with Seed Variability

Table[9](https://arxiv.org/html/2609.26855#A1.T9)reports the absolute test ROC\-AUC \(mean±\\pmstd overn=4n\{=\}4seeds\) for every leave\-one\-out ablation arm, complementing the relative\-change summary of Table[2](https://arxiv.org/html/2609.26855#S4.T2)\.

Table 9:Full ablation results: test ROC\-AUC \(mean±\\pmstd,n=4n\{=\}4seeds\) for each leave\-one\-out ablation ofQuartet\. Column groups match Table[2](https://arxiv.org/html/2609.26855#S4.T2)\.Red cellsdenote a statistically significant drop relative to the fullQuartetmodel \(i\.e\., the ablation’s upper confidence boundμabl\+σabl\\mu\_\{\\mathrm\{abl\}\}\+\\sigma\_\{\\mathrm\{abl\}\}falls below the full model’s lower boundμfull−σfull\\mu\_\{\\mathrm\{full\}\}\-\\sigma\_\{\\mathrm\{full\}\}\)\. Bold marks the fullQuartet\(reference\) column\.

#### A\.4\.4RGP Baseline Reproduction

The Relational Graph Perceiver \(RGP\)\[[37](https://arxiv.org/html/2609.26855#bib.bib10)\]is the most architecturally related prior work toQuartet, as both compress structural and temporal context through Perceiver\-style cross\-attention\. Because RGP does not have publicly available code for running benchmark comparisons, we performed a ground\-up reproduction following direct guidance from the original authors\. Our reproduction assembles RGP’s full forward path from three verified sources:

- •Tokenization:RelGT’s structural tokenizer \(feature encoding viaNeighborTfsEncoder\) combined with the RGP paper’s own positional\-encoding formula \(type\+\+centrality\+\+hop\+\+time\), which the author confirmed differs from RelGT’s\.
- •Perceiver core:GraphFM\[[52](https://arxiv.org/html/2609.26855#bib.bib52)\]’s memory\-efficient cross\-attention and feed\-forward blocks \(from the same research group as the RGP authors\) reused as the dual\-branch encoder backbone, as confirmed by the author\.
- •Temporal sampler:Implemented from scratch following the paper’s Algorithm 1 pseudocode\. We use the selection rule \(per\-edge\-type top\-k=10k\{=\}10, strictly causal, no time\-window mode\) as confirmed by the author\.

Because the original paper omitted per\-task hyperparameters, we performed a grid search over Perceiver layersL∈\{2,4,6\}L\\in\\\{2,4,6\\\}and latent tokensn∈\{8,16,32\}n\\in\\\{8,16,32\\\}for each task\.

Table[10](https://arxiv.org/html/2609.26855#A1.T10)presents the completed reproduction results across all twelveRelBenchclassification tasks\. Overall,Quartetmaintains highly competitive performance in this expanded baseline set, achieving the highest mean ROC\-AUC on six tasks, compared to four for RelGT and two for RGP\. We restrict these results to the appendix rather than incorporating them into the main text \(Table[1](https://arxiv.org/html/2609.26855#S4.T1)\) due to remaining methodological ambiguities that prevent a guaranteed apples\-to\-apples comparison\. Specifically, without access to the original codebase, we cannot definitively rule out the use of undocumented mechanisms such as temporal decay, nor can we guarantee that the Perceiver architecture ported from GraphFM is strictly identical to the proprietary RGP model\. Given these constraints, the results in Table[10](https://arxiv.org/html/2609.26855#A1.T10)are provided as a transparent, best\-effort reproduction\.

Table 10:RGP reproduction: test ROC\-AUC \(mean±\\pmstd\) on the twelveRelBenchclassification tasks\. RGP is reproduced following direct guidance from the original authors \(§[A\.4\.4](https://arxiv.org/html/2609.26855#A1.SS4.SSS4)\); HGT and RelGT results are from Table[1](https://arxiv.org/html/2609.26855#S4.T1)\. All results are averaged overn=4n=4seeds\.Boldmarks the best mean in each row\.