arXiv CSopen access

Gaussian Relational Graph Transformer

Gaussian Relational Graph Transformer

Zezhong Ding1,3,† ,

arXiv:2605.15575v1 [cs.LG] 15 May 2026

1

Jin Li2,3,† ,

Xugang Wang4 ,

Xike Xie2,3∗

School of Artificial Intelligence and Data Science, University of Science and Technology of China (USTC) 2 School of Biomedical Engineering, USTC 3 Data Darkness Lab, Suzhou Institute for Advanced Research, USTC 4 Chinese Academy of Sciences {zezhongding,lijinstu}@mail.ustc.edu.cn, [email protected], [email protected]

Abstract Relational graph learning models relational databases as graphs and has demonstrated superior performance on a wide range of relational predictive tasks. However, existing methods struggle to capture long-range dependencies due to information decay in their message-passing mechanisms, and recent relational graph transformers remain limited in jointly modeling structural, semantic, and temporal information. In this paper, we propose GelGT, a Gaussian relational graph transformer that explicitly addresses these challenges. GelGT introduces a structuresemantic collaborative sampling strategy to preserve structural connectivity while filtering irrelevant semantic information, and incorporates a Gaussian graph attention mechanism with a learnable Gaussian bias on the sampled subgraphs to dynamically encode temporal dependencies. Extensive experiments on various real-world datasets demonstrate that GelGT achieves state-of-the-art downstream task performance, with up to a 13.8% improvement in predictive performance.

1

Introduction

Relational databases are widely used for managing structural data across diverse industries, ranging from e-commerce and finance to healthcare [1, 2, 3]. Traditionally, predictive tasks on such databases have relied on tabular models [4, 5, 6, 7, 8]. However, these models predominantly rely on manual feature engineering to flatten relational tables [9, 10, 11], which limits their ability to capture complex relational structures for downstream tasks. Recent approaches model relational databases as relational graphs [12, 13, 14] acting as a bridge between tabular data and graph learning by projecting tabular rows into nodes and foreign keys into edges. This representation enables information propagation across tables through relational graph learning [15, 14], thereby effectively modeling the relational dependencies. Existing relational graph learning methods (e.g., RDL [12] and RelGNN [13]) are primarily built upon message-passing mechanisms. However, relational graph learning often requires long-range perception to incorporate global tabular information [16]. Due to information decay in message passing, these methods struggle to capture long-range dependencies [17, 18]. More recently, RelGT [16] builds a relational graph transformer and introduces attention mechanisms over sampled subgraphs to alleviate this limitation. While effective, it still suffers from three fundamental issues, as shown in Figure 1. Structurally, it typically relies on random sampling [19, 12, 13], which disregards the connections among entities, leading to structural fragmentation [20], where the relational graph is often sampled into isolated subgraphs. Semantically, its global attention clusters node embeddings before computing attention, inevitably aggregating information from irrelevant clusters and introducing semantic noise. Temporally, it determines temporal importance ∗ Corresponding Author

Preprint.

† Equal Contribution

Noise Node Existing Methods (e.g. RelGT)

WQ

Encoder

WK

Structural Semantic Temporal Numerical

Sampling

Relational Graph

Weaker Attention

Stronger Attention

WV

Q

K

GelGT (ours) Structural-Semantic Collaborative Sampling

Structural Semantic Temporal Numerical

Scale

Timestamp

SoftMax MatMul

V

Less Temporally Relevant Less Temporally Relevant

Standard Attention

Clustering Encoder

MatMul

τ

WQ WK WV

τ Q K

Attention Aggregation

Gaussian Temporal Bias MatMul

Scale

SoftMax

MatMul

V Gaussian Temporal Bias-based Attention

Less Temporally Relevant Less Temporally Relevant

Attention Aggregation

Figure 1: Comparison of existing methods and our proposed GelGT. Structurally, GelGT alleviates structural fragmentation by preserving node connectivity during sampling. Semantically, it mitigates the interference of semantically noisy nodes during sampling. Temporally, it employs Gaussian Temporal Bias to explicitly distinguish between temporally relevant and noisy nodes. solely based on the similarity of entangled embeddings (including temporal, semantic, structural, and numerical embeddings), making it difficult to explicitly distinguish temporally relevant nodes from irrelevant ones. To address the aforementioned limitations, we propose the Gaussian relational graph transformer (GelGT in short), as shown in Figure 1. GelGT incorporates a structural-semantic collaborative sampling strategy to construct subgraphs, mitigating structural fragmentation and semantic irrelevance. On these subgraphs, it uses a Gaussian temporal bias-based attention to effectively distinguish temporally relevant from noisy nodes. However, designing such a relational graph transformer raises two primary challenges. Challenge 1: Subgraph Sampling. Sampling subgraphs that both alleviate structural fragmentation and mitigate the interference of semantically noisy nodes is challenging. Preserving structural connectivity requires sampling a sufficiently large number of nodes, but this also introduces semantic noise [21]. Balancing both objectives is non-trivial: it requires bounding the number of sampled nodes while minimizing structural fragmentation and semantic noise. Challenge 2: Gaussian Bias-based Attention. Applying an appropriate Gaussian bias to attention mechanisms is challenging. The Gaussian bias follows a Gaussian distribution characterized by its mean and variance. As the mean determines the temporal center of the attention distribution, an improper choice may cause the model to attend to irrelevant regions, thus failing to capture critical temporal dependencies. Meanwhile, the variance determines the temporal receptive field [22], where an overly small variance restricts the attention to a narrow local temporal neighborhood and an excessively large variance disperses the attention weights across distant nodes, introducing temporal and semantic noise. Our main contributions are summarized as follows: • We propose Gaussian Relational Graph Transformer (GelGT), a relational graph transformer that jointly addresses structural, semantic, and temporal challenges in relational graph learning through collaborative subgraph sampling and Gaussian graph attention. • We theoretically show that structure-semantic collaborative sampling preserves the vast majority (≥ 99%) of effective structural information and can effectively mitigate semantic noise in seed node embeddings. Additionally, we prove that Gaussian graph attention assigns higher attention scores to temporally relevant nodes and lower attention scores to temporal noise nodes, compared to conventional attention without Gaussian bias (e.g., RelGT). • Extensive experiments on 7 datasets and 21 tasks demonstrate that GelGT achieves the state-of-theart performance on both classification and value regression tasks, with up to a 13.8% improvement in predictive performance.

2

Preliminaries

Relational Database (RDB) [23, 24]. A relational database is formally defined as a collection of tables, denoted by R = {T1 , ..., Tn }, where n represents the total number of tables. Each row in Ti 2

(A) RDB to Graph

(C) Gaussian Graph Attention

Relational Database

ID

User Product ID Amount Timestamp ID

1

2

1

5

Jan 4th

2

2

1

3

Jan 1st

3

2

2

2

Jan 2nd

Prediction Head

1 2

3

2

1 2

①

1

⑥ Fusion

Seed Node

Product Node

User Node

Transaction Node

Temporal Attention Aggregation

1st BFS Hop Path

2nd BFS Hop Reached Nodes

2nd BFS Hop Path

2

1

2

3

SoftMax

2

2

Gather 1-hop and 2-hop Neighbors

2

3

Node Encoder

Scale

3

④ GNN 1

2

𝐞𝐱𝐩 −

Δt=|τquery – τkey|

V Q K WV WQ WK

τ

2

1 2

2-Hop Semantic Similarity

Δt3 3

2

Δt2 2

Δt1 1

Computing Time Difference

Gaussian Temporal Bias-based Attention

Stronger Attention τ3key τquery 3 2

0.6

＞

.

3

2

Δt3 Δt2 Δt1 Gaussian Temporal Bias

⑤

Encoding Embedding

2

𝚫𝒕 − 𝝁 𝟐 𝝈𝟐

MatMul

Temporal Restriction

③ Semantic Refinement 2

Biastime

1

2

1

Add

2 3 1

1 1

μ

σ2

2

② Structural Integrity Sampling 1st BFS Hop Reached Nodes

3

2

MatMul

Task: What is the transaction amount for User 2 after January 3rd?

(B) Structural-Semantic Collaborative Sampling

Future Node

2

Predicted Cell Value

Relational Graph

User Attributes Product Category Price ID ID 1 $200 Book 1 $100 ? 2 2 Food $50 $300 3 Water $150 3

0.5

. Dot Product

τ2key 2

τ1key 1

Weaker Attention

τkey Neighbor Node Timestamp τquery Seed Node Timestamp

Figure 2: Overview of the GelGT Framework. The process consists of six main steps: ① Graph Construction converts the relational database into a relational graph. ② Structural Integrity Sampling. This stage samples subgraphs via BFS while enforcing strict timestamp constraints to mask future nodes for temporal validity. ③ Semantic Refinement. It filters noise by retaining only neighbors with high semantic similarity, calculated through dot products of encoded features. ④ A GNN module aggregates topological structural features. ⑤ Gaussian Temporal Bias-based Attention. It leverages a Gaussian temporal bias to assign high attention scores to temporally relevant nodes while allocating low scores to noisy nodes. ⑥ Finally, the Fusion module adaptively integrates the outputs of the GNN and the Gaussian Temporal Bias-based Attention via a learnable weight [25].

corresponds to an entity, which is uniquely identified by a primary key and may contain references to entities in other tables through foreign keys, together with entity-specific attributes and associated timestamp information. Relational Graph [14]. The structure of a relational database inherently forms a graph representation, referred to as a relational graph. A relational graph is formally defined as a heterogeneous temporal graph G = {V, E, ϕ, ψ, τ }, where nodes V represent entities from database tables, edges E represent primary-foreign key relationships, ϕ maps nodes to their respective types based on source tables, ψ assigns relation types to edges, and τ captures the temporal dimension through timestamps. RDB Task Reformulation. Based on the relational graph construction, predictive tasks on RDBs can be naturally cast as learning problems on G. Let Y denote a target attribute column within a table Ti . Since each row j in Ti corresponds to a unique node vj ∈ V, predicting a value in the j-th row of Ti can be formulated as learning a mapping function f : V → Y that leverages both node attributes and graph topology. Following previous work [16], we focus on two paradigms: (i) node classification, where Y is a finite set of discrete categorical labels, and (ii) node regression, where Y ⊆ R represents a continuous range of numerical values.

3

The Proposed Method: Gaussian Relational Graph Transformer (GelGT)

This section introduces the Gaussian relational graph transformer (GelGT), as illustrated in Figure 2. GelGT consists of two components: structure-semantic collaborative sampling (Steps ①-③) and Gaussian graph attention model (Steps ④-⑥). The former constructs a query-specific computation subgraph, which enables the latter to learn temporally aware representations. Section 3.1 and Section 3.2 describe the two components, respectively. 3

3.1

Structure-Semantic Collaborative Sampling

The goal of our sampling strategy is to construct a subgraph that preserves structural connectivity while filtering out semantically irrelevant nodes. This yields the final subgraph. The resulting subgraph explicitly defines the valid interaction scope for the subsequent attention model, and is constructed via two stages: (1) structural integrity sampling and (2) semantic refinement. Stage 1: Structural Integrity Sampling. The goal of this stage is to capture the complete graph topology around a seed node v. To achieve this, we employ a Breadth-First Search (BFS) strategy to expand the neighborhoods from seed node v. During the expansion, we ensure correctness and efficiency by strictly traversing to neighbors that satisfy temporal causality2 and limit the search depth to 2 hops. This process yields a sampled node set. Finally, we construct the subgraph induced by the sampled node set. Formally, we define the sampled node set Nsampled (v) and the resulting sampled subgraph Gsub (v) as: Nsampled (v) = {v} ∪ {u ∈ V | dist(u, v) ≤ 2}, (1) Gsub (v) = (Nsampled (v), Esub ), where Esub = {(i, j) ∈ E | i, j ∈ Nsampled (v)} (2) where V and E denote the node set and the edge set of the relational graph, respectively, and dist(u, v) is the shortest path distance between nodes u and v. Theoretical Analysis. We theoretically show that the structural integrity sampling effectively preserves the structural information of the relational graph. To quantify this, we use Katz centrality [27] as the topological metric and denote the Katz centrality computed on the full graph and the sampled subgraph as C G (v) and C Gsub (v), respectively. We establish the quantitative relationship between the structural loss ∆C(v) = |C G (v) − C Gsub (v)| arising from structural integrity sampling and the full-graph structural information in Theorem 1. Theorem 1 (Upper Bound of Relative Structural Loss). The ratio of the structural loss ∆C(v) = |C G (v)−C Gsub (v)| arising from structural integrity sampling to the full-graph structural information C G (v) satisfies: |∆C(v)| ≤ 0.01 (3) C G (v) We provide a detailed proof of Theorem 1 in Appendix A.1. Theorem 1 demonstrates that the structural integrity sampling preserves at least 99% of the effective structural information, ensuring that the sampled subgraph provides a reliable structural basis for subsequent modeling. Stage 2: Semantic Refinement. This stage refines the sampled subgraph Gsub (v) constructed in stage 1 to mitigate semantic noise. Specifically, we first encode the raw attributes of all nodes in the subgraph Gsub (v) to low-dimensional embeddings h. Then, we calculate the dot product between the seed node v and each node u in its 2nd -hop neighborhood to measure semantic similarity: s(v, u) = h⊤ v hu .

(4)

We then select the top-ranked 2nd -hop neighbors according to s(v, u) and combine them with all 1st -hop neighbors to form the final sampled subgraph Gfinal . Theoretical Analysis. Since noise nodes tend to exhibit lower semantic similarity to the seed node, semantic refinement excludes them from the final sampled subgraph Gfinal . Let I denote the aggregated information from neighbors of the seed node, decomposed into semantically relevant information Irelevance and noise Inoise . Semantic refinement therefore increases the relevance-to-noise ratio (by amplifying Irelevance and suppressing Inoise ), as formalized in Theorem 2. Theorem 2 (Enhancement of Semantic Relevance-to-Noise Ratio). The semantic relevance-tonoise ratio after refinement strictly exceeds that of the pre-refinement stage. Formally, before after Irelevance Irelevance < before after Inoise Inoise

(5)

2 Temporal causality [26] requires that the timestamp of any sampled neighbor precedes that of the query node (i.e.,

τneighbor < τseed ), to avoid temporal information leakage.

4

before before after after where {Irelevance , Inoise } and {Irelevance , Inoise } denote the semantic relevance and semantic noise before and after the refinement process, respectively.

Theorem 2 demonstrates that our proposed semantic refinement strategy can effectively mitigate semantic noise in seed node embeddings. Detailed proof is in Appendix A.3. Through structural integrity sampling and semantic refinement, we obtain the final sampled subgraph Gfinal . It acts as the structural and semantic base for the subsequent stage, defining the structure and relevance contexts over which the GNN and attention mechanisms perform representation learning. 3.2

Gaussian Temporal Bias-based Attention

This module operates on the computed subgraph Gfinal obtained in Section 3.1. Since the sampling stage ensures the structural and semantic validity of neighbor nodes, this model focuses on modeling temporal relevance between the target node and its neighbors. As shown in Figure 2, we employ a composite framework integrating GNNs and attention mechanisms. Specifically, we introduce an adaptive Gaussian temporal bias into the attention mechanism to modulate attention scores, making the model emphasize temporally relevant information while suppressing temporal noise. Adaptive Gaussian Temporal Bias. A straightforward strategy for capturing temporal information, as in RelGT [16], is to encode timestamps jointly with other node attributes. However, such integrated representations entangle temporal information with structural and semantic information, making it difficult for the attention mechanism to explicitly distinguish temporally relevant nodes from noise. To address this, we introduce a learnable attention bias that parameterizes temporal preference distribution via a continuous Gaussian function, allowing the attention mechanism to selectively focus on relevant temporal information. Formally, given the input feature matrix H ∈ RN ×d (derived from the encoders as shown in Appendix E), we define the standard linear projections for the Query (Q), Key (K), and Value (V) matrices as: Q = WQ H, K = WK H, V = WV H, where WQ , WK , WV are learnable parameter matrices. Different from vanilla self-attention [28], we explicitly inject a temporal bias Biastime into T √ ) before normalization, as shown in Equation 6. the scaled attention score ( QK d   QKT √ + Biastime V. Attention(Q, K, V ) = Softmax (6) d The adaptive temporal bias (Biastime ) is formally defined as:    (∆t − µ)2 . Biastime = Linear exp − σ2

(7)

∆t denotes the time interval between query and key nodes. Mean µ and variance σ are learnable parameters. Temporal long-range perception is critical for relational graph learning [29]. The learned µ serves to identify the most temporally relevant information (i.e., temporal center) within the longrange temporal receptive field of a training node. Besides, the temporal relevance information decays with increasing distance from the temporal center [22]. Thus, the learned σ models the information decay effect, making the temporal bias align with the underlying temporal relevance distribution. Theoretical Analysis. In GelGT, the distribution of attention weights is jointly defined by the temporal center µ and scope σ. This parameterized structure achieves a systematic separation between temporally relevant nodes and temporal noise. First, Lemma 1 proves that the learnable parameter µ converges to the ground-truth relevant timestamp. Based on that, Theorem 3 further proves that our method assigns a higher attention score to temporally relevant nodes than to noise nodes. Lemma 1 (Convergence of Temporal Center). Let t∗ be the ground-truth relevant timestamp. The gradient of the Gaussian temporal bias B(t∗ ) with respect to the learnable temporal center µ satisfies: t∗ −µ ∂B ∗ ∗ ∗ ∂µ = B(t ) · σ 2 . The term (t − µ) drives µ toward t during optimization. Detailed proof of Lemma 1 is in Appendix A.4. Based on the convergence property established in Lemma 1, we further quantify the disparities in attention score assignment between temporally relevant nodes and noise nodes, specifically comparing the mechanisms w/ and w/o Gaussian bias. 5

A A Theorem 3 (Attention Score Ratio Enhancement). Let {αrelevant , αnoise } denote the attention scores that the attention mechanism A assigned to temporally related nodes and noise nodes, respectively. Then, w/ G w/o G αrelevant αrelevant = e · , (8) w/o G w/ G αnoise αnoise

where e is Euler’s number, “w/ G” and “w/o G” indicate the attention mechanism with and without the Gaussian bias, respectively. We provide a detailed proof of Theorem 3 in Appendix A.5. Theorem 3 demonstrates that, compared to vanilla self-attention [28], our attention mechanism achieves a higher attention score of assigning to temporally relevant nodes relative to noise nodes. Consequently, our approach more effectively discriminates between temporally relevant information and temporal noise.

4

Experiments

In this section, we conduct extensive experiments to answer the following research questions: RQ1: Does GelGT outperform existing methods on node classification tasks? RQ2: Does GelGT outperform existing methods on node regression tasks? RQ3: How effective are proposed individual components? RQ4: Do the proposed modules generalize to other baseline frameworks? RQ5: Why is GNN branch necessary in GelGT? RQ6: How does sampling size affect GelGT’s performance? RQ7: How sensitive is GelGT to the number of hops? RQ8: How does GelGT compare to baseline methods in terms of training and inference time? 4.1

Experimental Setup

Datasets GelGT is evaluated on the recently introduced RDL Benchmark (RelBench) [12]. In total, RelBench contains 30 tasks across 7 datasets, covering node classification, node regression, and recommendation. For our evaluation, we focus on 21 tasks on node classification and regression, following the task settings used in RelGT [16]. Baselines We compare GelGT with six baseline methods for node classification and node regression tasks (Tables 1 and 2). Our baselines include graph transformer-based method RelGT [16], as well as the graph-centric relational database foundation model Griffin [30]. Consistent with the experimental settings in prior work [16], we also evaluate two variants of the Heterogeneous Graph Transformer (HGT) [31] as additional baselines to further examine the effectiveness of GelGT relative to existing graph transformer models. In addition, we compare against a strong baseline from the tabular learning literature, namely LightGBM [32]. Evaluation Metrics Node-level classification aims to predict binary labels for a given node at a specific seed time. We use the Area Under the ROC Curve (AUC) [33] as the evaluation metric (higher is better). Node-level regression involves predicting numerical labels for a node at a given seed time. We use Mean Absolute Error (MAE) as the evaluation metric (lower is better). Table 1: Test set results on the node classification tasks in RelBench [12]. Best values (based on mean performance) are in bold, and the second-best values are underlined. Results are reproduced based on available code. ↑: higher is better. Dataset

Task

RDL

HGT

HGT+PE

Griffin

RelGT

LightGBM

Ours

rel-f1 rel-f1 rel-avito rel-avito rel-event rel-event rel-trial rel-amazon rel-amazon rel-stack rel-stack rel-hm

driver-dnf (↑) driver-top3 (↑) user-clicks (↑) user-visits (↑) user-repeat (↑) user-ignore (↑) study-outcome (↑) user-churn (↑) item-churn (↑) user-engagement (↑) user-badge (↑) user-churn (↑)

0.7262±0.0027 0.7554±0.0154 0.6590±0.0195 0.6620±0.0010 0.7689±0.0159 0.8162±0.0111 0.6860±0.0101 0.7042±0.0005 0.8281±0.0003 0.9021±0.0007 0.8986±0.0008 0.6988±0.0021

0.7077±0.0153 0.7765±0.0066 0.6376±0.0298 0.6432±0.0002 0.6496±0.0220 0.8247±0.0096 0.5837±0.0141 0.6643±0.0041 0.7797±0.0039 0.8847±0.0044 0.8608±0.0044 0.6695±0.0067

0.7117±0.0084 0.7340±0.0018 0.6457±0.0099 0.6495±0.0022 0.6536±0.0137 0.8161±0.0007 0.5921±0.0303 0.6619±0.0042 0.7803±0.0053 0.8817±0.0046 0.8566±0.0068 0.6569±0.0109

0.7091±0.0045 0.7795±0.0139 0.6330±0.0025 0.6468±0.0045 0.7709±0.0062 0.8153±0.0038 0.6908±0.0071 0.7000±0.0036 0.8110±0.0051 0.8980±0.0023 0.8700±0.0031 0.6804±0.0014

0.7587±0.0413 0.8352±0.0342 0.6830±0.0602 0.6678±0.0015 0.7609±0.0219 0.8157±0.0040 0.6861±0.0040 0.7039±0.0040 0.8255±0.0006 0.9053±0.0005 0.8632±0.0018 0.6927±0.0019

0.6886±0.0034 0.7393±0.0121 0.5360±0.0032 0.5305±0.0011 0.5305±0.0211 0.7993±0.0154 0.7009±0.0063 0.5222±0.0051 0.6254±0.0044 0.6339±0.0350 0.6343±0.0079 0.5521±0.0025

0.7608±0.0175 0.8408±0.0063 0.6844±0.0600 0.6695±0.0060 0.8357±0.0203 0.8779±0.0122 0.7254±0.0059 0.7050±0.0065 0.8297±0.0096 0.9086±0.0186 0.9044±0.0086 0.6997±0.0017

6

Table 2: Test set results on the node regression tasks in RelBench [12]. Best values (based on mean performance) are in bold, and the second-best values are underlined. Results are reproduced based on available code. Results marked with † are reproduced using the official code and differ from the original paper. ↓: lower is better. Dataset

Task

RDL

HGT

HGT+PE

Griffin

RelGT

LightGBM

Ours

rel-f1 rel-avito rel-event rel-trial rel-trial rel-amazon rel-amazon rel-stack rel-hm

driver-position (↓) ad-ctr (↓) user-attendance (↓) study-adverse (↓) site-success (↓) user-ltv (↓) item-ltv (↓) user-votes (↓) item-sales (↓)

4.022±0.119 0.0410±0.0010 0.258±0.006 44.473±0.209 0.4000±0.0200 14.3130±0.013 50.0530±0.1630 0.0650±0.0000 0.0560±0.0000

4.2263±0.0580 0.0462±0.0021 0.2635±0.0000 45.1692±2.6927 0.4428±0.0047 15.4120±0.0447 55.8683±0.6003 0.0679±0.0000 0.0641±0.0012

4.3921±0.1382 0.0483±0.0027 0.2611±0.0043 42.6484±0.2785 0.4396±0.0083 15.8643±0.0924 55.8493±0.3226 0.0680±0.0000 0.0639±0.0003

3.9315±0.2903 0.0433±0.0004 0.3708±0.0094 59.0902±0.0022 0.3801±0.0041 19.6055±0.0239 66.7938±0.0193 0.1395±0.0076 0.0597±0.0008

3.9170±0.3448 † 0.0420±0.0009 † 0.2502±0.0033 43.9923±0.5928 0.3761±0.0178 † 14.2665±0.0154 54.6626±0.7006 † 0.0654±0.0002 0.0563±0.0006 †

4.1700±0.2200 0.0410 ±0.0041 0.2640±0.0011 44.0110±0.2020 0.4250±0.0008 16.7830±0.0188 60.5690±0.0033 0.0680±0.0065 0.0760±0.0002

3.7345±0.1200 0.0362±0.0009 0.2423±0.0031 42.5699±0.9700 0.3485±0.0200 14.2538±0.0189 49.2109±0.8092 0.0648±0.0025 0.0560±0.0009

Table 3: Ablation study of GelGT components on node classification tasks. ↑: higher is better. Dataset

Task

GelGT (Ours) w/o Structural Integrity Sampling w/o Semantic Refinement w/o Adaptive Gaussian Bias

rel-avito user-clicks (↑) 0.6844±0.0600 rel-avito user-visits (↑) 0.6695±0.0060 rel-event user-ignore (↑) 0.8779±0.0122 rel-trial study-outcome (↑) 0.7254±0.0059 rel-amazon user-churn (↑) 0.7050±0.0065

0.6688±0.0057 0.6612±0.0018 0.8691±0.0073 0.7161±0.0060 0.6812±0.0080

0.6677±0.0031 0.6652±0.0040 0.8699±0.0086 0.7155±0.0040 0.6973±0.0095

0.6669±0.0043 0.6630±0.0028 0.8638±0.0091 0.7192±0.0076 0.6945±0.0089

Table 4: Ablation study of GelGT components on node regression tasks. ↓: lower is better. Dataset

Task

GelGT (Ours) w/o Structural Integrity Sampling w/o Semantic Refinement w/o Adaptive Gaussian Bias

rel-avito ad-ctr (↓) 0.0362±0.0009 rel-trial site-success (↓) 0.3485±0.0200 rel-hm item-sales (↓) 0.0560±0.0009

4.2

0.0372±0.0009 0.3909±0.0048 0.0584±0.0021

0.0368±0.0007 0.3491±0.0178 0.0599±0.0014

0.0370±0.0004 0.3583±0.0034 0.0585±0.0008

Performance

To answer (RQ1), we evaluate GelGT on 12 node classification tasks across 7 datasets. The results in Table 1 demonstrate the strong performance of GelGT compared to baseline methods. Specifically, GelGT surpasses baseline methods by up to 6.2% improvement in AUC. It ranks first in AUC on every evaluated task, indicating its strong ability to effectively distinguish positive nodes from negative ones. To answer (RQ2), we evaluate GelGT on 9 node regression tasks across 7 widely utilized datasets. Table 2 demonstrates the best performance of GelGT compared to baselines, achieving up to a 13.8% improvement in MAE. More experimental results have been included in the Appendix C. 4.3

Ablation Study

To address (RQ3), we perform an ablation study by removing key components of GelGT: (1) w/o Structural Integrity Sampling: We use random sampling instead. This does not preserve the topological structure of the relational graph. (2) w/o Semantic Refinement: We retain all sampled nodes, including the irrelevant ones. (3) w/o Adaptive Gaussian Temporal Bias: We remove the adaptive Gaussian temporal bias, reducing the attention mechanism to vanilla selfattention [28]. Tables 3 and 4 present the ablation study results for the node classification and node regression tasks, respectively. In Tables 3 and 4, removing structural integrity sampling degrades performance, confirming the necessity of the topological structure preserved by our sampling strategy. Eliminating semantic refinement leads to a clear drop, demonstrating that GelGT effectively removes irrelevant information. Finally, excluding the adaptive Gaussian temporal bias results in the observable performance loss, indicating that simply encoding time as features is insufficient. To answer (RQ4), we evaluate the performance of RelGT enhanced with our proposed structuralsemantic collaborative sampling and Gaussian temporal bias across five different tasks to validate their effectiveness. As shown in Figure 3a, this uniform performance gain across diverse tasks demonstrates that our approach effectively addresses the limitations of the original framework. In summary, the results demonstrate that our proposed modules effectively generalize to other baseline frameworks, significantly enhancing their predictive performance. In the Appendix F.2, we further demonstrate through experiments that the proposed sampling strategy is model-agnostic. 7

Table 5: Effect of the GNN branch on node classification tasks. ↑: higher is better. Metric / Dataset

rel-f1

rel-avito

rel-event

rel-trial

rel-amazon

rel-stack

rel-hm

Task

driver-dnf

user-clicks

user-repeat

study-outcome

item-churn

user-badge

user-churn

w/o GNN branch w/ GNN branch

0.7499 0.7608

0.6751 0.6844

0.8173 0.8357

0.7094 0.7254

0.8128 0.8297

0.8917 0.9044

0.6822 0.6997

0.85

Training Efficiency RelGT

200

0.80

AUC

100

0.75 0.70 0.65

ntnteve re el-evepeat rel-r-igno r r-re use use

f1relr--dnf e v i dr

f1rel--top3 r e driv

ltria e relu-tcom dy-o

stu

(a) RelGT w/ all GelGT components vs. RelGT

1.3×

1.1×

50

GelGT (Ours)

1.1× 1.1×

20

Inference Efficiency

0.08

Inference Time (s/batch)

RelGT RelGT w/ all components

Training Time (s/epoch)

0.90

0.06 0.04

RelGT

1.5× 1.1×

GelGT (Ours)

1.3×

1.5×

1.2×

0.02

1.2×

10

al f1 f1 nt nt rel--dnf relt-op3 el-evneore el-evepeat rel-troime er iver- r r-ig r r-re outc v i r -d -dr -use -use study-

Tasks

0.00 al f1 f1 nt nt rel--dnf relt-op3 el-evneore el-evepeat rel-troime er iver- r r-ig r r-re outc v i r -d -dr -use -use study-

Tasks

(b) Efficiency comparison between RelGT and GelGT

Figure 3: Ablation and efficiency evaluation. To address (RQ5), we conduct an ablation study by removing the GNN branch. As shown in the table 5, performance consistently drops across all datasets. This validates the necessity of the GNN branch in GelGT. The attention branch, even with hop-distance embeddings and GNN-based positional encodings, operates on a fully connected sampled subgraph and therefore only captures relative positional information, without explicitly modeling the true PK-FK edges. In contrast, the GNN branch performs message passing directly along PK-FK edges, which preserves the original relational structure and better captures the semantic dependencies encoded in these edges. 4.4

Sampling Size Analysis

To address (RQ6), we evaluate the performance of GelGT across 5 tasks under different sampling sizes. Specifically, we vary the number of sampled nodes within {100, 200, 300, 400, 500}. In Figure 4a, the performance across all tasks reaches its peak at a sampling size of 300. Specifically, when the sampling size is less than 300, the model suffers from an information bottleneck and fails to capture sufficient semantic information. Conversely, when the sampling size exceeds 300, the limited number of truly relevant neighbors forces the similarity-based mechanism to incorporate semantically irrelevant nodes, which obscures the contribution of semantically relevant nodes. Therefore, we set the sampling size to 300, as it ensures sufficient information aggregation while avoiding interference from semantically irrelevant nodes. In the Appendix F.6, we further analyze the sampling budget. 4.5

Sampling Hop Analysis

To answer (RQ7), we evaluate the performance of GelGT across five tasks under different sampling hops. Specifically, we vary the sampling hops from {2, 3, 4, 5}. The experimental results are summarized in Figure 4b. As shown in the results, the performance remains consistent across all tasks with minimal fluctuations, indicating that GelGT is insensitive to the sampling hops parameter. Such stability across varying hop counts carries significant practical implications. First, the capability to attain high performance with a small receptive field (i.e., Sampling Hops = 2) demonstrates GelGT’s efficiency in extracting necessary predictive information from a compact local neighborhood, thereby avoiding the computational overhead associated with deeper sampling. Second, the absence of performance degradation at larger hops (e.g., Sampling Hops = 5) validates GelGT’s ability to effectively filter out irrelevant noise from distant nodes. More analysis is in the Appendix F.1. 4.6

Efficiency.

Beyond predictive performance, computational efficiency is a critical factor for scalability of relational graph learning in real-world applications. To address (RQ8), we evaluate the efficiency of GelGT 8

0.95 0.90 0.85 0.80 0.75 0.70 0.65 100

rel-f1-driver-dnf rel-f1-driver-top3

rel-trial-study-outcome

rel-event-user-ignore rel-event-user-repeat

AUC

AUC

rel-event-user-ignore rel-event-user-repeat

200

300

Sampling Size

400

500

(a) Sampling size

0.95 0.90 0.85 0.80 0.75 0.70 0.65

2

rel-f1-driver-dnf rel-f1-driver-top3

3

rel-trial-study-outcome

4

Sampling Hops

5

(b) Sampling hops

Figure 4: GelGT’s Performance across five tasks under different sampling sizes and sampling hops. across five tasks by comparing its training time per epoch and inference time against state-of-the-art relational graph transformer models. As shown in Figure 3b, GelGT consistently demonstrates lower time costs for both training and inference across all five evaluated tasks compared to baseline methods. This uniform reduction in computational overhead confirms that GelGT is more efficient and scalable for relational graph learning tasks. More experiments are in the Appendix D.

5

Related Work

Traditional Relational Learning. Relational learning on relational databases was heavily reliant on manual feature engineering, requiring domain experts to transform multi-table records into flat feature vectors to accommodate tabular learning methods [16], e.g., LightGBM [32], TabNet [34] and DNF-Net [35]. Specifically, TabNet treats attributes from distinct tables merely as a homogeneous feature set, while DNF-Net models interactions solely as property combinations within a single row. However, these methods will break the relationships between tables in the RDB. This reduction of hierarchical tables to flat vectors transforms Primary Key-Foreign Key connections from explicit referential links to disconnected feature columns, effectively obscuring the hierarchical dependencies between tables. Relational graph learning aims to address these challenges [15, 14]. Relational Graph Learning (RGL). In RGL, the relational database is modeled as a relational graph, which effectively captures the relational dependencies. Most RGL methods are built upon the message-passing-based mechanisms, utilizing message-passing mechanisms to propagate information across tables. For example, RelGNN [13] and RDL [12] adopt an iterative message-passing mechanism where row-level representations are updated by recursively aggregating transformed feature messages from connected neighbors across tables via foreign keys. However, these methods struggle to capture such long-range dependencies effectively [17, 18], limiting their ability to model complex and multi-hop relationships for downstream predictive tasks. Therefore, existing methods shift to graph Transformer-based architectures, including RelGT [16], Griffin [30] and HGT [31]. Nevertheless, current approaches fall short of addressing the complex structural, semantic, and temporal demands of RGL. For example, RelGT relies on random sampling, which disregards explicit connections, leading to structural fragmentation and degrading predictive performance. Although Griffin [30] preserves all connected nodes, such full retention is often impractical in real-world databases, where a single row can be associated with thousands of records [13]. By indiscriminately incorporating such massive neighborhoods without semantic filtering, it inevitably introduce semantic noise [36]. In addition, they commonly flatten dynamic temporal pattern into static latent representations, ignoring the intrinsic temporal pattern and lacking the capacity to capture precise temporal dependencies. Our GelGT explicitly addresses the above challenges, achieving state-of-the-art performance.

6

Conclusion

We propose GelGT, a Gaussian relational graph transformer for relational graph learning. GelGT jointly addresses structural fragmentation, semantic irrelevance, and temporal dependency modeling through structure-semantic collaborative sampling and adaptive Gaussian-biased attention. Theoretical analysis validates the effectiveness of the proposed mechanisms, and extensive experiments demonstrate that GelGT outperforms baselines in both predictive accuracy and training efficiency. 9

References [1] B. Aditya, Gaurav Bhalotia, Soumen Chakrabarti, Arvind Hulgeri, Charuta Nakhe, Parag, and S. Sudarshan. BANKS: browsing and keyword searching in relational databases. In VLDB, pages 1083–1086, 2002. [2] Rakesh Agrawal, Amit Somani, and Yirong Xu. Storage and querying of e-commerce data. In VLDB, pages 149–158, 2001. [3] Terry A. Halpin and Tony Morgan. Information modeling and relational databases (2. ed.). Morgan Kaufmann, 2008. [4] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In SIGKDD, pages 785–794, 2016. [5] Ravid Shwartz-Ziv and Amitai Armon. Tabular data: Deep learning is not all you need. Inf. Fusion, 81:84–90, 2022. [6] Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? In NeurIPS, 2022. [7] Kuan-Yu Chen, Ping-Han Chiang, Hsin-Rung Chou, Ting-Wei Chen, and Tien-Hao Chang. Trompt: Towards a better deep neural network for tabular data. In ICML, 2023. [8] Andreas Voskou, Charalambos Christoforou, and Sotirios Chatzis. Transformers with stochastic competition for tabular data modelling. In ICML Workshop, 2024. [9] Vijay Prakash Dwivedi, Charilaos I. Kanatsoulis, Shenyang Huang, and Jure Leskovec. Relational deep learning: Challenges, foundations and next-generation architectures. In KDD, pages 5999–6009, 2025. [10] James Max Kanter and Kalyan Veeramachaneni. Deep feature synthesis: Towards automating data science endeavors. In DSAA, pages 1–10, 2015. [11] Hoang Thanh Lam, Beat Buesser, Hong Min, Tran Ngoc Minh, Martin Wistuba, Udayan Khurana, Gregory Bramble, Theodoros Salonidis, Dakuo Wang, and Horst Samulowitz. Automated data science for relational data. In ICDE, pages 2689–2692, 2021. [12] Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen, Yiwen Yuan, Zecheng Zhang, Xinwei He, and Jure Leskovec. Relbench: A benchmark for deep learning on relational databases. In NeurIPS, 2024. [13] Tianlang Chen, Charilaos I. Kanatsoulis, and Jure Leskovec. Relgnn: Composite message passing for relational deep learning. In ICML, 2025. [14] Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational deep learning - graph representation learning on relational databases. In ICML, 2024. [15] Milan Cvitkovic. Supervised learning on relational databases with graph neural networks. CoRR, abs/2002.02046, 2020. [16] Vijay Prakash Dwivedi, Sri Jaladi, Yangyi Shen, Federico Lopez, Charilaos I. Kanatsoulis, Rishi Puri, Matthias Fey, and Jure Leskovec. Relational graph transformer. In ICLR, 2026. [17] Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In NeurIPS, 2021. [18] Qitian Wu, Wentao Zhao, Zenan Li, David P. Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. In NeurIPS, 2022. [19] Rishabh Ranjan, Valter Hudovernik, Mark Znidar, Charilaos I. Kanatsoulis, Roshan Reddy Upendra, Mahmoud Mohammadi, Joe Meyer, Tom Palczewski, Carlos Guestrin, and Jure Leskovec. Relational transformer: Toward zero-shot foundation models for relational data. In ICLR, 2026. 10

[20] Dipak Meher and Carlotta Domeniconi. Inside core-kg: Evaluating structured prompting and coreference resolution for knowledge graphs, 2025. [21] Filippo Menczer, Gautam Pant, and Padmini Srinivasan. Topical web crawlers: Evaluating adaptive algorithms. ACM Trans. Internet Techn., 2004. [22] Maosheng Guo, Yu Zhang, and Ting Liu. Gaussian transformer: A lightweight approach for natural language inference. In AAAI, 2019. [23] E. F. Codd. A relational model of data for large shared data banks. Commun. ACM, 13(6):377– 387, 1970. [24] E. F. Codd. Extending the database relational model to capture more meaning. ACM Trans. Database Syst., 4(4):397–434, 1979. [25] Jin Li, Zezhong Ding, and Xike Xie. Duetgraph: Coarse-to-fine knowledge graph reasoning with dual-pathway global-local fusion. In NeurIPS, 2025. [26] Karthir Prabhakar, Sang Min Oh, Ping Wang, Gregory D. Abowd, and James M. Rehg. Temporal causality for the analysis of visual events. In CVPR, 2010. [27] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953. [28] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, 2017. [29] Divyansha Lachi, Mahmoud Mohammadi, Joe Meyer, Vinam Arora, Tom Palczewski, and Eva L Dyer. Integrating temporal and structural context in graph transformers for relational deep learning. arXiv preprint arXiv:2511.04557, 2025. [30] Yanbo Wang, Xiyuan Wang, Quan Gan, Minjie Wang, Qibin Yang, David Wipf, and Muhan Zhang. Griffin: Towards a graph-centric relational database foundation model. In ICML, 2025. [31] Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In WWW, pages 2704–2710, 2020. [32] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In NeurIPS, 2017. [33] J A Hanley and B J Mcneil. A method of comparing the areas under receiver operating characteristic curves derived from the same cases. Radiology, 148(3):839–843, 1983. [34] Sercan Ö Arik and Tomas Pfister. Tabnet: Attentive interpretable tabular learning. In AAAI, 2021. [35] Liran Katzir, Gal Elidan, and Ran El-Yaniv. Net-dnf: Effective deep modeling of tabular data. In ICLR, 2020. [36] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. Heterogeneous graph attention network. In WWW, 2019. [37] Michele Benzi and Christine Klymko. On the limiting behavior of parameter-dependent network centrality measures. SIAM Journal on Matrix Analysis and Applications, 2013. [38] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In ICLR, 2020. [39] Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? In NeurIPS, 2017. [40] DER FAST PERIODISCHEN ZUR THEORIE. Eine verallgemeinerung der theorie der fourierreihen. Acta mathematica, 45:29, 1925. [41] Jiaxuan You, Jonathan Michael Gomes Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In AAAI, 2021. 11

[42] Yiwen Yuan, Zecheng Zhang, Xinwei He, Akihiro Nitta, Weihua Hu, Manan Shah, Blaz Stojanovic, Shenyang Huang, Jan Eric Lenssen, Jure Leskovec, and Matthias Fey. Contextgnn: Beyond two-tower recommendation systems. In ICLR, 2025. [43] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017. [44] Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. CoRR, 2016. [45] D Hendrycks. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415, 2016. [46] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016. [47] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020. [48] Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael M. Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: graph neural diffusion. In ICML, 2021. [49] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, 2019. [50] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018. [51] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurIPS, 2019. [52] Justin Gu, Rishabh Ranjan, Charilaos Kanatsoulis, Haiming Tang, Martin Jurkovic, Valter Hudovernik, Mark Znidar, Pranshu Chaturvedi, Parth Shroff, Fengyu Li, and Jure Leskovec. Relbench v2: A large-scale benchmark and repository for relational data, 2026. [53] Fang Wu, Vijay Prakash Dwivedi, and Jure Leskovec. Large language models are good relational learners. In ACL, pages 7835–7854, 2025. [54] Zezhong Ding, Yongan Xiang, Shangyou Wang, Xike Xie, and S Kevin Zhou. Play like a vertex: A stackelberg game approach for streaming graph partitioning. In Proc. ACM Manag. Data, 2024. [55] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang. Lightgcn: Simplifying and powering graph convolution network for recommendation. In SIGIR, 2020. [56] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020. [57] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In ICLR, 2022. [58] Jiacheng Li, Yujie Wang, and Julian McAuley. Time interval aware self-attention for sequential recommendation. In WSDM, 2020.

12

Appendix Overview In the Appendix, we provide additional details organized as follows: 1. Appendix A: Proofs of Theorems. 2. Appendix B: Experimental Details. 3. Appendix C: Additional Baselines and Datasets. 4. Appendix D: Additional Efficiency Experiments. 5. Appendix E: Detailed Description of Encoder Modules. 6. Appendix F: Additional Analysis and Discussion. 7. Appendix G: Reproducibility and Code Availability Statement. 8. Appendix H: Limitations and Broader Impacts.

A

Proofs of Theorems.

A.1

Upper Bound of Relative Structural Loss

Proof. To characterize the multi-hop topological structure of nodes in the graph, we employ Katz centrality [27] as our analytical tool. As a classic walk-based topological metric, Katz centrality systematically captures the structural reach of a node by computing a weighted sum of all walks of varying lengths associated with it. Formally, let A be the adjacency matrix of the graph, and λ be the attenuation factor determining the weight decay of paths. Let CG denote the vector of Katz centrality for all nodes in the full graph, and let 1 be the vector of all ones. The matrix-vector form of Katz centrality is given by the Neumann series: CG =

∞ X

(λA)k 1.

(9)

k=1

The structural integrity sampling strategy preserves all walks of length k = 1 and k = 2. The structural loss vector ∆C, which consists of all walks of length k ≥ 3, can be expressed as: ∆C =

∞ X

(λA)k 1.

(10)

k=3

We observe a critical recursive relationship between the error vector and the global centrality vector. By factoring out (λA)2 from the error series: ! ∞ X 2 k ∆C = (λA) (λA) 1 = (λA)2 CG . (11) k=1

To quantify the relative magnitude of the loss, we employ the matrix 2-norm (spectral norm). Using the consistency property of matrix norms (∥M x∥ ≤ ∥M ∥∥x∥), we have: ∥∆C∥2 = ∥(λA)2 CG ∥2 ≤ ∥(λA)2 ∥2 ∥CG ∥2 .

(12)

Using the property that the spectral norm of a symmetric matrix is its spectral radius, i.e., ∥A∥2 = ρ(A), and considering the definition λ = c/ρ(A): 2  c ∥(λA)2 ∥2 ≤ (λ∥A∥2 )2 = (λρ(A))2 = · ρ(A) = c2 . (13) ρ(A) Substituting this bound back into the inequality yields: ∥∆C∥2 ≤ c2 ∥CG ∥2 . 13

(14)

Rearranging the terms, we obtain the strict upper bound for the relative structural loss: ∥∆C∥2 ≤ c2 . ∥CG ∥2

(15)

Following the analysis of the local regime by Benzi and Klymko [37], the scaling factor c falls within the range of ≤ 0.1. Substituting this value into Theorem 1, the relative structural loss is upper-bounded by: ∥∆C∥2 ≤ (0.1)2 = 1%. ∥CG ∥2

(16)

This confirms that under standard operating conditions, the structural integrity sampling preserves at least 99% of the effective structural information. A.2

Exponential Decay of Structural Sensitivity

proof. To justify the differentiated pruning strategy in Stage 2, we analyze the sensitivity of the seed node’s structural information to the removal of a specific neighbor at distance k. We define the structural sensitivity ∆C(v, k) as the magnitude of change in the Katz centrality of v when a node u at distance k (i.e., dist(v, u) = k) is removed from the graph. Based on the definition of Katz centrality, the contribution of a node u to v is the weighted sum of all walks between them: X Contr(u → v) = β |γ| , (17) γ:u⇝v

where γ represents a walk from u to v, β ∈ (0, 1) is the attenuation factor determining the weight decay of paths and |γ| is its length. When a neighbor u at distance k is pruned, all walks passing through u are eliminated. The dominant term in this summation corresponds to the shortest path (geodesic) of length k. Higher-order paths (length > k) also contribute, but their weights are dampened by higher powers of β. Therefore, the structural loss is dominated by the leading term: ∆Ck−hop (v) ≈ β k · Npaths (k) + O(β k+1 ),

(18)

where Npaths (k) denotes the number of shortest paths of length k between v and u (typically small for local neighborhoods). Now, we compare the sensitivity at k = 1 (direct neighbors) and k = 2 (two-hop neighbors): ∆C1−hop (v) = β · 1 + O(β 2 ) ∼ O(β), 2

3

(19) 2

∆C2−hop (v) = β · Npaths (2) + O(β ) ∼ O(β ).

(20)

Note that for k = 1, there is exactly one direct edge, so the coefficient is 1. The ratio of structural sensitivity between pruning a 2-hop neighbor and a 1-hop neighbor is: ∆C2−hop (v) O(β 2 ) ≈ = O(β). ∆C1−hop (v) O(β)

(21)

Since the attenuation factor β is typically chosen to be small (satisfying β < 1/ρ(A)), this ratio indicates that the structural perturbation caused by removing a 2-hop neighbor is an order of magnitude smaller than that of removing a 1-hop neighbor. This theoretical result confirms that 1-hop neighbors form the non-negligible structural skeleton (O(β) sensitivity), whereas 2-hop neighbors allow for aggressive semantic pruning with bounded structural risk (O(β 2 ) sensitivity). A.3

Enhancement of Semantic Relevance-to-Noise Ratio

As we prove in Appendix A.2, pruning 2-hop neighbors has a much smaller impact on structural information compared to 1-hop neighbors. Therefore, we apply the following semantic refinement exclusively to 2-hop neighbors. 14

Proof. The features of the sampled neighbors are aggregated to obtain a representation for the seed node, which is then used for downstream tasks. We define a general aggregation formula as follows: X hagg = w(v, u)hu (22) u∈N (v)

In this formulation, v represents the seed node, u is neighbors of v, hu denotes the feature of neighbor u, w(v, u) is the aggregation weight, and hagg corresponds to the aggregated feature. We can decompose the feature of neighbor u, hu , into a part that is semantically relevant to the seed node and a part that corresponds to irrelevant noise: hu = µvu hv + hnoise u

(23)

The first term corresponds to the part of hu that is semantically relevant to the seed node v, with µvu representing the degree of relevance. The second term represents the part unrelated to v, i.e., random 2 noise (e.g., heterophily), assumed to have variance σnoise . By substituting hu into the aggregation formula, we can decompose the aggregated feature into two parts: X X X hagg = w(v, u)hu = w(v, u)µvu hv + w(v, u)hnoise (24) u u∈N (v)

u∈N (v)

u∈N (v)

|

{z

semantically relevant

}

|

{z

noise

}

Following the theoretical analysis in PairNorm [38], which establishes that the information content of node features is strictly proportional to their squared norm, we measure the magnitude of the aggregated information using the L2 -norm. Therefore, the aggregated semantically relevant information is quantified as:    2 2 X X Irelevance =  w(v, u) µvu  hv =  w(v, u)µuv  · ∥hv ∥2 (25) u∈N (v)

u∈N (v)

The variance directly measures the destructive information or uncertainty [39] introduced by irrelevant neighbors. Therefore, we compute the semantically noisy information as: X Inoise = Var(w(v, u)hnoise ) (26) u u∈N (v)

Using the properties of variance, we can factor out the weight w(v, u) to obtain: X Inoise = w(v, u)2 Var(hnoise ) u

(27)

u∈N (v) 2 If the variance of each individual noise is σnoise : X X 2 2 Inoise = w(v, u)2 σnoise = σnoise w(v, u)2 u∈N (v)

(28)

u∈N (v)

Therefore, the ratio of relevant information to noise information is: P 2 P 2 2 w(v, u)µ · ∥h ∥ w(v, u)µ 2 uv v uv u∈N (v) u∈N (v) ∥hv ∥ Irelevance P = = 2 · P (29) SNR = 2 2 2 Inoise σnoise w(v, u) σ w(v, u) u∈N (v) u∈N (v) | noise {z } constant

To demonstrate the effectiveness of our semantic refinement, We denote the refined 2-hop neighbors by Nref ine (v) and remaining subsets is denoted as Nremaining (v). Let A and B denote the relevance term and noise term in SNR of our refinement strategy, respectively: X X A= w(v, u)µvu , B = w(v, u)2 . (30) u∈Nref ine (v)

u∈Nref ine (v)

15

Similarly, for the remaining subset Nremaining (v), we define the relevance term a and noise term b: X X a= w(v, u)µvu , b = w(v, u)2 (31) u∈Nremaining (v)

u∈Nremaining (v)

Nodes in Nremaining (v) have negligible correlation with the seed node, implying µvu ≈ 0 and thus a ≈ 0. However, since these nodes objectively exist in the graph, they contribute a strictly positive noise term, i.e., b > 0. Now, we compare the SNR of our refinement strategy (SNRpost ) against the full 2-hop neighborhood strategy (SNRpre ): I af ter ∥hv ∥2 A2 · = (32) SNRaf ter = relevance 2 af ter σnoise B Inoise SNRbef ore =

bef ore Irelevance bef ore Inoise

=

∥hv ∥2 (A + a)2 A2 ∥hv ∥2 · · ≈ 2 . 2 σnoise B+b σnoise B + b

(33)

Since b is positive and B is positive, the denominator of the full 2-hop neighborhood strategy is strictly larger while the numerator remains approximately unchanged. This leads to the inequality: af ter Irelevance I bef ore A2 A2 < . < =⇒ SNRbef ore < SNRaf ter =⇒ relevance bef ore af ter B+b B Inoise Inoise

(34)

This inequality mathematically guarantees that pruning low-similarity neighbors effectively removes the noise denominator b without sacrificing the relevance term numerator A, thereby strictly maximizing the ratio of relevant information to noise information of the aggregated representation. Consequently, this result rigorously confirms that our semantic refinement strategy functions as an effective denoising filter, eliminating irrelevant nodes to enhance the quality of node representation. A.4

Convergence of Temporal Center

In this subsection, we provide a rigorous theoretical analysis demonstrating that the proposed attention mechanism is able to focus more effectively on temporally relevant nodes compared to existing attention mechanisms. For the model to attend to relevant historical information, the learnable temporal center µ must converge to the ground-truth relevant timestamp t∗ . proof. Consider a simplified objective where the model aims to maximize the alignment score S between a query and a ground-truth relevant event at time t∗ . The optimization follows the gradient ascent direction ∇µ S. The baseline attention logit is derived from the dot product of sinusoidal encodings: ∗

d/2 X

cos(ωj (t∗ − µ)).

(35)

d/2 X ∂Sbase ωj sin(ωj (t∗ − µ)). = ∂µ j=1

(36)

Sbase (t ) ≈

j=1

The gradient with respect to µ is:

This gradient function is a superposition of high-frequency sine waves. Its sign flips repeatedly as the distance |t∗ − µ| changes. If the initialization of µ is far from t∗ , the gradient direction is determined by local periodic behavior rather than the global distance to t∗ . Consequently, the optimization is prone to getting trapped in local optima (false peaks) nearest to the initialization.   ∗ −µ)2 Our method incorporates an adaptive bias term B(t∗ ) = exp − (t 2σ . The gradient contribution 2 from this term is: ∂B t∗ − µ = B(t∗ ) · . (37) ∂µ σ2 Let ∆ = t∗ − µ be the alignment error. The sign of the gradient is determined by sgn(∆): 16

• If µ < t∗ (∆ > 0), the gradient is positive, pushing µ towards t∗ . • If µ > t∗ (∆ < 0), the gradient is negative, pushing µ towards t∗ . Unlike the baseline, the term (t∗ − µ) acts as a linear restoring force. It provides a consistent global gradient direction that guides µ towards t∗ , smoothing the optimization landscape and significantly expanding the basin of attraction for the true timestamp. A.5

Attention Score Ratio Enhancement

Building upon the analysis in Appendix A.4, which guarantees that the learnable temporal center µ converges to the ground-truth relevant timestamp t∗ , we now prove that the proposed attention mechanism effectively concentrates attention scores on these relevant nodes. Specifically, we demonstrate that our method enforces a strict probabilistic preference for events temporally close to t∗ , suppressing distant noise that the baseline model fails to filter. Proof. Let t∗ be the ground-truth relevant timestamp. Based on the gradient guidance property proved in Appendix A.4, we assume the model has successfully learned the optimal temporal reference, i.e., µ ≈ t∗ . Consider a relevant event erel and an irrelevant noise event enoise . We define their respective temporal differences relative to the ground-truth timestamp t∗ as: δrelevant = trelevant − t∗ ,

(38)

and

δnoise = tnoise − t∗ . (39) ∗ The relevant event is temporally proximal to the target t , while the noise event is distant. This structural difference is formalized by the inequality of their magnitudes: |δrelevant | ≪ |δnoise |.

(40)

P The baseline attention logit is Sbase (δ) = cos(ωj δ). According to Bohr’s theorem on almost periodic functions [40], Sbase does not vanish at infinity. Specifically: lim sup Sbase (δ) = sup Sbase (δ). |δ|→∞

(41)

δ∈R

This implies that there exist infinitely many distant timestamps tnoise (where |δnoise | → ∞) such that: Sbase (tnoise ) ≈ Sbase (trelevant ). (42) Consequently, the baseline model cannot structurally guarantee that a relevant node receives a higher score than a distant noise node. The discriminative margin ∆base = Sbase (trelevant ) − Sbase (tnoise ) has a lower bound of approximately 0 (or even negative values due to oscillations), indicating a failure to distinguish relevance from periodic noise. In our method, with µ ≈ t∗ , the Gaussian bias becomes B(δ) = exp(−δ 2 /2σ 2 ). The total logit is Sours (δ) = Sbase (δ) + B(δ). The discriminative margin between the relevant event and the noise event is: ∆ours = Sours (trelevant ) − Sours (tnoise ) = ∆base + [B(δrelevant ) − B(δnoise )] .

(43)

Since |δrelevant | ≪ |δnoise |, and the Gaussian function is strictly monotonically decreasing with respect to distance from the center, we have: B(δrelevant ) ≫ B(δnoise ) ≈ 0.

(44)

Even in the worst-case scenario for the baseline (where ∆base ≤ 0 due to periodic misalignment), the Gaussian term introduces a strictly positive margin enhancement. Specifically, considering the asymptotic limit where the noise becomes infinitely distant (|δnoise | → ∞) and the relevant event is perfectly aligned with the learned center (δrel → 0), we have: lim

|δnoise |→∞

B(δnoise ) = 0

and

17

lim

δrelevant →0

B(δrelevant ) = 1.

(45)

This imposes a strict exponential penalty on the noise in the score ratio: w/ G αw/o G αnoise = exp (Sbase (noise) − Sbase (relevant) − 1) = e−1 · w/onoise . w/ G G αrelevant αrelevant

(46)

where αnoise and αrelevant denote the attention scores for temporal noise and related nodes, respectively; e is Euler’s number; and w/ G” and w/o G” distinguish the attention mechanisms with and without Gaussian bias. Combining the result that µ converges to t∗ (Appendix A.4) with the Gaussian decay property, we prove that our method effectively assigns significantly higher attention scores to strictly temporally relevant nodes. Unlike the baseline, which is susceptible to distant "periodic ghosts," our mechanism imposes a structural envelope that filters out irrelevant temporal information, ensuring that the model’s focus remains robustly on the learned temporal context.

B

Experimental Details.

B.1

Training Setting

GelGT is trained in an end-to-end manner without any pre-training stage to ensure a fair comparison with baseline methods such as RelGT. We do not adopt pre-training in our setting for two reasons: (i) it introduces significant computational overhead, and (ii) it often fails to transfer effectively across relational graphs (e.g., Griffin still underperforms even after fine-tuning). In contrast, direct supervised training allows the model to better adapt to the target relational structure, leading to more stable and competitive performance. B.2

Benchmark Details.

In this section, we present a comprehensive overview of the datasets and evaluation tasks sourced from RelBench [12]. RelBench encompasses seven datasets spanning diverse relational database domains, such as e-commerce, clinical records, social networks, and sports. These datasets are meticulously curated from their respective domains, with training set sizes ranging from 1.3K to 5.4M records, totaling 47M training instances. Each dataset supports various predictive tasks, including modeling user engagement with advertisements within a four-day window or forecasting the primary outcomes of clinical trials over a year. Collectively, RelBench defines 30 tasks categorized into entity classification, entity regression, and recommendation. Our evaluation focuses on 21 classification and regression tasks, as GelGT is primarily designed as a node representation learning framework for Relational Deep Learning (RDL). Following pror work [16], We exclude recommendation tasks in this study due to their specific requirements, such as target node identification [41] or the adoption of pair-wise learning architectures [42]. Detailed statistics for all evaluated datasets and tasks are summarized in Table 6. B.3

Datasets

In this section, we include the details on the datasets in RelBench [12] which we use for our evaluation. • rel-amazon. The Amazon E-commerce dataset consists of product details, user information, and review interactions from Amazon’s platform, including metadata like pricing and categories, along with review ratings and content. • rel-avito. Avito’s marketplace dataset contains search queries, advertisement characteristics, and contextual information from this major online trading platform that facilitates transactions across various categories including real estate and vehicles. • rel-event. The Event Recommendation dataset from Hangtime mobile app tracks users’ social planning, capturing interactions, event details, demographic data, and social connections to reveal how relationships impact user behavior. • rel-f1. The F1 dataset provides comprehensive Formula 1 racing information since 1950, documenting drivers, constructors, manufacturers, and circuits with detailed records of race results, standings, and specific data on various racing sessions and pit stops. 18

Table 6: Dataset and task statistics from RelBench [12] used for our evaluation. Dataset

Task name

user-churn item-churn user-ltv rel-amazon item-ltv user-item-purchase user-item-rate user-item-review

Task type

#Rows of training table Train Validation Test

#Unique Entities

%train/test #Dst Entity Overlap Entities

entity-cls entity-cls entity-reg entity-reg recommendation recommendation recommendation

4,732,555 2,559,264 4,732,555 2,707,679 5,112,803 3,667,157 2,324,177

409,792 177,689 409,792 166,978 351,876 257,939 116,970

351,885 166,842 351,885 178,334 393,985 292,609 127,021

1,585,983 416,352 1,585,983 427,537 1,632,909 1,481,360 894,136

88.0 93.1 88.0 93.5 87.4 81.0 74.1

— — — — 12,562,384 7,665,611 5,406,835

rel-avito

ad-ctr user-clicks user-visits user-ad-visit

entity-reg entity-cls entity-cls recommendation

5,100 59,454 86,619 86,616

1,766 21,183 29,979 29,979

1,816 47,996 36,129 36,129

4,997 66,449 63,405 63,402

59.8 45.3 64.6 64.6

— — — 3,616,174

rel-event

user-attendance user-repeat user-ignore

entity-reg entity-cls entity-cls

19,261 3,842 19,239

2,014 268 4,185

2,006 246 4,010

9,694 1,514 9,799

14.6 11.5 21.1

— — —

rel-f1

driver-dnf driver-top3 driver-position

entity-cls entity-cls entity-reg

11,411 1,353 7,453

566 588 499

702 726 760

821 134 826

50.0 50.0 44.6

— — —

rel-hm

user-churn item-sales user-item-purchase

entity-cls 3,871,410 entity-reg 5,488,184 recommendation 3,878,451

76,556 105,542 74,575

74,575 1,002,984 89.7 105,542 105,542 100.0 67,144 1,004,046 89.2

— — 13,428,473

rel-stack

user-engagement user-badge post-votes user-post-comment post-post-related

entity-cls 1,360,850 entity-cls 3,386,276 entity-reg 2,453,921 recommendation 21,239 recommendation 5,855

85,838 247,398 156,216 825 226

88,137 255,360 160,903 758 258

88,137 255,360 160,903 11,453 5,924

97.4 96.9 97.1 59.9 8.5

— — — 44,940 7,456

rel-trial

study-outcome study-adverse site-success condition-sponsor-run site-sponsor-run

entity-cls entity-reg entity-reg recommendation recommendation

960 3,596 19,740 2,081 37,003

825 3,098 22,617 2,057 27,428

13,779 50,029 129,542 3,956 445,513

0.0 0.0 42.0 98.4 48.3

— — — 533,624 1,565,463

11,994 43,335 151,407 36,934 669,310

• rel-hm. H&M’s dataset contains customer-product interactions from their e-commerce platform, featuring customer demographics, product descriptions, and purchase histories. • rel-stack. The Stack Exchange dataset documents activity from this network of Q&A websites, including user biographies, posts, comments, edits, votes, and question relationships where users earn reputation through contributions. • rel-trial. The clinical trial dataset from the AACT initiative has study protocols and outcomes, containing trial designs, participant information, intervention details, and results metrics, serving as a key resource for medical research. B.4

Tasks

The following entity classification and regression tasks are defined in RelBench for the above datasets. 1. rel-amazon (a) user-churn: Predict whether a user will discontinue reviewing products within the next three months. (b) item-churn: Predict if a product will have no reviews in the next three months. (c) user-ltv: Estimate the total monetary value of merchandise in dollars that a user will purchase and review within the next three months. (d) item-ltv: Estimate the total monetary value of purchases and reviews a product will receive during the next three months. 2. rel-avito (a) user-visits: Predict if a user will engage with several (advertisements) ads within the upcoming four days. (b) user-clicks: Predict whether a user will interact with multiple ads through clicking within the upcoming four days. 19

(c) ad-ctr: Estimate the interaction probability for an ad, assuming it receives an interaction within four days. 3. rel-event (a) user-attendance: Estimate the number of events a user will confirm attendance to (RSVP yes or maybe) within the upcoming seven days. (b) user-repeat: Predict whether a user will join an event (RSVP yes or maybe) within the upcoming seven days, provided they attended in an event during the previous fourteen days. (c) user-ignore: Predict whether a user will disregard or ignore more than two events invitations within the upcoming seven days. 4. rel-f1 (a) driver-dnf: Predict if a driver will not finish a race within the upcoming month. (b) driver-top3: Determine if a driver will achieve a top-three qualifying position in a race within the upcoming month. (c) driver-position: Estimate a driver’s average finishing placement across all races in the upcoming two months. 5. rel-hm (a) user-churn: Predict whether a customer will not perform any transactions in the upcoming week. (b) item-sales: Estimate total revenue generated by a product in the upcoming week. 6. rel-stack (a) user-engagement: Predict whether a user will contribute through voting, posting, or commenting within the upcoming three months. (b) user-badge: Predict whether a user will secure a new badge within the upcoming three months. (c) post-votes: Estimate the number of votes a user’s post will accumulate over the upcoming three months. 7. rel-trial (a) study-outcome: Predict whether a clinical trial will achieve its principal outcome within the upcoming year. (b) study-adverse: Estimate the number of patients who will experience significant adverse effects or mortality in a clinical trial over the upcoming year. (c) site-success: Estimate the success rate of a clinical trial site in the upcoming year. B.5

Hyperparameter Settings

Sampling Module. In our experimental setup, to accommodate the varying demands for neighborhood information density across different downstream tasks, we employ a two-stage neighborhood sampling strategy. Specifically, for both node classification and node regression tasks, we consistently define the sampling scope as the 2-hop neighborhood of the central node to capture sufficient local structural information. However, we implement differentiated configurations for sampling sizes based on task characteristics. For the node classification task, we initially sample 300 candidate neighbors in the first stage, followed by a filtering mechanism that retains 200 nodes as input. Conversely, for the node regression task—to address potentially more complex feature dependencies—we increase the initial sampling budget to 500 nodes, ultimately selecting 300 nodes for model training. This tailored configuration aims to strike an optimal balance between computational efficiency and model performance. Model Module. Our proposed model adopts a unified hybrid architecture designed to capture both local structural topology and global temporal-semantic dependencies. To effectively handle the heterogeneous and temporal nature of the relational graph, we employ a set of domain-specific encoders [16] to project diverse input features into a unified latent space Rd . Specifically, we utilize learnable embedding layers to encode node type heterogeneity and 20

relative hop distances from the central node. Furthermore, continuous timestamps are processed via a TimeEncoder to preserve temporal dynamics, while raw tabular node features are encoded using a TabularEncoder based on feature statistics. To enhance subgraph structural awareness, a learnable positional encoding is also incorporated. All resulting embeddings are normalized via LayerNorm, concatenated, and projected to a dimension of d = 512 through a 2-layer MLP mixture network. The core processing layer, GelGTLayer, processes the refined subgraph sequence Xin through two parallel branches to extract complementary features. The GNN Branch is designed to explicitly capture local neighborhood topology using a 3-layer GraphSAGE [43] backbone. Each layer applies message passing followed by LayerNorm [44], GELU [45] activation, and Dropout (p = 0.1). Crucially, residual connections [46] are incorporated at each layer to facilitate gradient flow and prevent over-smoothing [47, 48, 49, 50], yielding a structure-aware representation Hgnn . Parallel to the GNN, the Attention Branch employs a Transformer-based LocalModule to capture long-range dependencies and temporal interactions. By utilizing Multi-Head Self-Attention (Heads=4) integrated with temporal embeddings, this branch allows the model to dynamically weigh neighbors based on both semantic similarity and temporal proximity, producing a context-aware representation Hattn . To optimally combine the structural and semantic representations, we introduce a learnable gating parameter η. The final representation Hf inal is computed as a dynamic weighted sum: Hf inal = η · Hattn + (1 − η) · Hgnn

(47)

where σ(·) denotes the Sigmoid function. This mechanism allows the model to adaptively balance the contribution of GNN and Transformer modules based on the specific requirements of the downstream task. Finally, a 2-layer MLP head generates the prediction. The detailed hyperparameter configurations and implementation specifications are summarized in Table 7. B.6

Hardcore Configurations

We conduct all experiments with: • Operating System: Ubuntu 20.04.6 LTS. • CPU: Intel(R) Xeon(R) Platinum 8358 CPU @ 2.60GHz. • GPU: NVIDIA Tesla A100 SMX4 with 80GB of Memory. • Software: CUDA 12.1, Python 3.10.18, PyTorch [51] 2.5.1.

C

Additional Baselines and Datasets

To further validate the robustness, generalizability, and architectural superiority of the Gaussian Relational Graph Transformer (GelGT), we expand our empirical evaluation to include the highly challenging SALT dataset [52] and benchmark against a broader spectrum of emerging and advanced baseline models, including Rel-LLM [53], Nodeformer [18], RelGNN [13], and RGP [29]. The SALT dataset presents a significantly more complex environment for relational deep learning. To ensure a direct and rigorous comparison with existing temporal neighbor sampling methods such as RGP, we evaluated GelGT across multiple classification tasks within the SALT dataset. We report the Mean Reciprocal Rank (MRR) to align with standard evaluation metrics used in recent literature. As demonstrated in Table 8, GelGT consistently achieves state-of-the-art performance across all tasks. The substantial performance gap confirms that our approach—specifically the Gaussian temporal bias combined with structure-aware sampling—captures long-range relational dependencies more effectively than traditional heterogeneous methods (HGT) and recent temporal sampling strategies (RGP). We further isolate the specific advantages of our structural-semantic-temporal collaborative modeling by comparing GelGT against two advanced architectures: Rel-LLM and Nodeformer. We evaluated our model against Rel-LLM, a recent method leveraging large language models for relational graphs, and Nodeformer, an architecture specifically optimized for long-range dependencies. 21

Table 7: Detailed hyperparameter settings and implementation specifications. Hyperparameter

Value

Description / Note

Model Architecture Hidden Dimension (d) Global Layers (Lglobal ) Local GNN Depth Attention Heads Feed-forward Network (FFN) Ratio Positional Encoding Dim Number of Centroids VQ Decay

512 4 3 4 2 128 4096 0.99

Embedding size for all encoders Number of model layers (from script) Layers within internal GNNStack Multi-head attention mechanism Hidden dim expansion in FFN Learnable structural PE For vector quantization (VQ) EMA decay rate for codebook update

Optimization & Training Optimizer Learning Rate Weight Decay Batch Size Dropout Rate Max Training Steps Total Epochs Warmup Steps

Adam 1 × 10−4 1 × 10−5 64 0.3 500 10 10

Standard optimization algorithm Base learning rate L2 regularization coefficient Adjusted for memory constraints Applied to FFN and Attention Number of steps per epoch Total training duration Linear warmup strategy

Data Sampling & Processing 2-hop 300 → 200 500 → 300

Neighborhood Scope Classification Configuration Regression Configuration

Maximum hop distance sampled Sample 300, select top-200 Sample 500, select top-300

As shown in Table 9 (evaluated via AUC), GelGT consistently outperforms both baselines. This confirms that GelGT’s success is not merely a byproduct of general model capacity, but fundamentally stems from our decoupled continuous Gaussian temporal bias, which precisely focuses on temporal patterns without distorting semantic embeddings. Table 8: Test set results on the SALT dataset classification tasks. Best values are in bold. ↑: higher is better.

Table 9: Performance comparison with emerging graph learning architectures. Best values are in bold. ↑: higher is better.

Task ↑

RDL

HGT

RelGT

RGP

Ours

Task ↑

rel-salt-sales-group rel-salt-sales-incoterms rel-salt-sales-payterms rel-salt-sales-office rel-salt-sales-shipcond rel-salt-item-incoterms rel-salt-item-plant rel-salt-item-shippoint

0.20 0.70 0.39 0.93 0.59 0.64 0.90 0.94

0.20 0.75 0.60 0.96 0.76 0.75 0.91 0.93

0.35 0.73 0.61 0.98 0.75 0.84 0.97 0.98

0.34 0.58 0.81 0.81 -

0.38 0.77 0.64 0.99 0.83 0.87 0.99 0.99

rel-f1-driver-top3 rel-avito-user-clicks rel-event-user-repeat rel-event-user-ignore rel-trial-study-outcome rel-stack-user-badge rel-hm-user-churn

D

Rel-LLM

Nodeformer

Ours

0.82 0.66 0.79 0.83 0.71 0.89 0.55

0.82 0.66 0.79 0.83 0.71 0.89 0.61

0.84 0.68 0.83 0.87 0.72 0.90 0.69

Additional Efficiency Experiments

In this section, we provide a detailed analysis of the computational efficiency of the proposed GelGT architecture. We specifically evaluate the overhead introduced by our structure-semantic collaborative sampling strategy and the Gaussian temporal bias-based attention mechanism, comparing them against standard baselines and optimized kernels. 22

D.1

Sampling Efficiency

A potential concern regarding our proposed sampling mechanism is whether the Breadth-First Search (BFS) combined with semantic similarity-based refinement introduces significant computational latency compared to naive Random Sampling. However, empirical results demonstrate that our approach maintains a cost highly comparable to Random Sampling. The efficiency of our sampling strategy stems from its dual-stage design: • Stage 1 (Structural Integrity Sampling): Under our standard configuration (e.g., a 2-hop depth and a 300-node limit), the overhead of managing the BFS queue is marginal. It remains on the same scale as the random number generation and deduplication operations required by Random Sampling. • Stage 2 (Semantic Refinement): The similarity calculation and selection process are executed in parallel for all subgraphs within a batch, ensuring minimal additional latency. To validate this, we measured the single-node sampling times across two RelBench [52] datasets, including rel-ratebeer, a massive-scale graph with tens of millions of nodes. As shown in Table 10, our method remains just as efficient as Random Sampling, proving its feasibility for large-scale relational databases. Table 10: Comparison of per-node sampling time between random sampling and the proposed method. Task Random Sampling Ours rel-trial-study-outcome rel-ratebeer-beer_rating-total_score

D.2

14ms 87ms

14ms 88ms

Attention Efficiency

We also analyze the computational cost of our Gaussian Temporal Bias-based Attention. While modern optimized attention kernels like FlashAttention significantly accelerate vanilla attention, they are often less compatible with arbitrary pairwise biases. We demonstrate that our method remains highly competitive through two key perspectives: practical scalability and context size requirements. We compared the training runtime (Epoch Time) and GPU memory consumption of our attention mechanism against FlashAttention across different context sizes (Table 11). For our standard context size of 300 nodes, FlashAttention yields only a marginal 1.07× speedup, as the small context does not trigger typical memory bottlenecks. When aggressively scaling the sample size up to 3,000, our method’s runtime remains in the same order of magnitude as FlashAttention. At an extreme scale of 30,000 nodes, both methods inevitably face Out-Of-Memory (OOM) errors due to hardware limitations. This confirms that the practical training overhead of our attention mechanism scales similarly to optimized vanilla attention. A common assumption is that larger graphs inherently require substantially more context (e.g., thousands of nodes). However, our structure-semantic collaborative sampling effectively filters out irrelevant noise, eliminating the need for massive context windows. As demonstrated on the rel-ratebeer regression task (a dataset with over 13.7 million nodes), GelGT successfully captures the necessary structural information and achieves SOTA performance (Table 12) while strictly maintaining an extremely small context size of 300 nodes. By improving sampling quality and strictly controlling the sample size, GelGT fundamentally avoids the quadratic computational bottlenecks of attention mechanisms, rendering the lack of FlashAttention compatibility a non-issue in practical deployments. D.3

Efficiency on Extreme Graph Structures

Our sampling strategy is constrained by dual factors: a maximum BFS depth and a fixed candidate budget. This design ensures consistent efficiency across graph structures with varying densities. 23

Table 11: Scalability comparison between our proposed attention and FlashAttention across varying sampled node sizes. Context Size Size 300 Size 3000 Size 30000

Ours

Table 12: Performance comparison on the relratebeer dataset (regression task). Best values (in terms of mean performance) are in bold. ↓ indicates lower is better.

FlashAttention

Epoch Time

GPU Mem

Epoch Time

GPU Mem

225ms 1376ms — OOM —

2.2GB 70.0GB — OOM —

210ms 1004ms — OOM —

1.9GB 53.9GB — OOM —

Task ↓

RDL

RelGT

LightGBM

Ours

rel-beer_ratings-total_score

0.36

0.33

0.47

0.32

In dense graphs, BFS quickly reaches the fixed budget (300 nodes), which bounds the cost of subsequent semantic filtering. In sparse graphs, the BFS traversal terminates earlier due to depth limitation, naturally reducing the candidate pool and further accelerating computation. To validate this behavior, we construct extreme graph settings following the skewness-based generation protocol in [54]. We report the average sampling time in Table 13. Table 13: Sampling efficiency under extreme graph structures. Sparse Graph trial-study-outcome Dense Graph 11 ms 14 ms 15 ms The results indicate that our sampling strategy maintains stable efficiency under dense conditions and even improves slightly in sparse settings, demonstrating robustness across graph distributions.

E

Detailed Description of Encoder Modules

In this section, we describe the specific encoder modules designed to process the heterogeneous attributes associated with nodes in our relational graph framework. Follow previous work [16], these encoders transform raw input features—including node types, hop distances, temporal information, tabular attributes, and structural positions—into dense vector representations suitable for downstream learning tasks. Neighbor Node Type Encode. The Neighbor Node Type Encoder maps discrete heterogeneity information into a continuous latent space using a learnable lookup table (Embedding Layer). It instantiates a parameter matrix Etype ∈ R|T |×d , where |T | is the number of node types. The encoder takes integer indices as input and performs a direct embedding lookup to project categorical entity constraints into dense vector representations. Neighbor Hop Encoder. The Neighbor Hop Encoder introduces structural inductive bias by encoding the shortest-path distance using a dedicated Embedding Layer. To accommodate 0based or 1-based indexing, the scalar hop counts are shifted and mapped via an embedding matrix Ehop ∈ RKmax ×d . This non-linear mapping allows the model to learn distance-dependent feature transformations rather than treating distance merely as a scalar weight. Neighbor Time Encoder. The Neighbor Time Encoder transforms continuous scalar time intervals using a Sinusoidal Positional Encoding (PE) mechanism followed by a Linear Projection. Specifically, the module first projects scalar time differences ∆t into Rd using fixed Fourier feature frequencies (Sinusoidal PE). The output is then passed through a learnable Linear Layer (nn.Linear). To handle invalid temporal data (e.g., negative time deltas), the module utilizes a learnable Mask Parameter, combining the linear output and the mask vector via a gating mechanism. Neighbor Tabular Feature Encoder. The Neighbor Tabular Feature Encoder processes heterogeneous tabular attributes (numerical, categorical, and timestamps) using a ResNet backbone adapted for tabular data via the torch frame library. For each node type, the encoder first applies specific column encoders—Linear Encoders for numerical features and Embedding Encoders for categorical features. These processed features are then fed into a deep ResNet architecture (consisting of multiple residual blocks with Linear, BatchNorm, and ReLU layers) to extract high-order interactions between columns. 24

Table 14: Performance comparison (AUC) between RelGNN and RelGNN with the proposed sampling strategy. Dataset RelGNN RelGNN (w/ Ours) rel-avito-user-visits rel-event-user-repeat rel-trial-study-outcome rel-amazon-item-churn rel-stack-user-engagement

0.6517 0.7661 0.7003 0.8043 0.8975

0.6673 0.7898 0.7290 0.8118 0.9088

GNN Positional Encoder. The GNN-based Positional Encoder captures local topological structures using a Graph Isomorphism Network (GIN) backbone. Node features are initialized either with random noise or Laplacian Eigenvector Positional Encodings (LapPE) projected via a Linear layer. The structure is processed by stacked GIN Convolutional Layers, where each layer utilizes a MultiLayer Perceptron (MLP) as the aggregation function. This MLP is composed of Linear → BatchNorm → ReLU → Linear blocks. Residual connections are applied across layers, and the final embedding is obtained by aggregating layer-wise outputs via a generic pooling function (e.g., concatenation or max-pooling) followed by a final linear transformation.

F

Additional Analysis and Discussion

F.1

Semantic Refinement Design

We describe the design of semantic refinement from two aspects: (1) its exclusion at 1-hop neighbors, and (2) its behavior under non-homophilic settings. Exclusion at 1-hop neighbors. Semantic refinement is not applied to 1-hop neighbors in order to preserve high-quality first-order signals. In relational databases, 1-hop neighbors correspond to direct PK-FK relations and provide the most reliable structural and semantic information for the target node. Filtering at this stage may remove essential information and degrade the quality of initial node representations. Preserving complete first-order neighborhoods is also consistent with prior findings (e.g., LightGCN [55]), which emphasize the importance of retaining full local connectivity for effective representation learning. Behavior under non-homophilic settings. Semantic refinement is designed to operate beyond strict homophily assumptions. Instead of relying on node-type similarity, the method evaluates neighbors in a shared latent space [36] constructed from tabular attributes and positional encodings. In this space, similarity reflects task-relevant semantic correlation. Consequently, heterogeneous neighbors are retained as long as they contribute useful information to the target task. The refinement mechanism mainly acts on higher-hop neighbors to suppress less relevant or noisy signals, while preserving informative dependencies even in heterophilic scenarios. Overall, semantic refinement balances information preservation and noise reduction by maintaining complete first-order neighborhoods and selectively filtering higher-order neighbors based on taskrelevant semantic signals. F.2

Generality of the Sampling Strategy

To demonstrate the generality of the proposed sampling strategy, we further evaluate it on another relational graph learning architecture, RelGNN. We integrate our sampling strategy into RelGNN without modifying its original model design, and compare the performance with its vanilla version. The results are summarized in Table 14. We observe that the proposed sampling strategy consistently improves the performance of RelGNN across multiple tasks. This suggests that the effectiveness of our method is not tied to a specific model architecture. We attribute these gains to the ability of our semantic similarity-based filtering to reduce noisy or less informative neighbors, thereby providing cleaner and more relevant neighborhood signals for downstream relational learning. 25

Table 15: Edge homophily ratio across datasets. Task Edge Homophily Ratio rel-f1-driver-dnf rel-avito-user-clicks rel-event-user-repeat rel-trial-study-outcome rel-amazon-item-churn rel-stack-user-badge rel-hm-user-churn

F.3

0.23 0.17 0.13 0.22 0.21 0.21 0.25

Homophily vs. Heterophily in Relational Graphs

In this section, we investigate whether relational graphs derived from databases exhibit homophilic or heterophilic properties, and clarify the role of low-similarity neighbors in our learning framework. Heterophily of relational graphs. As discussed in the main paper (Line 90) and established in prior studies [56, 12, 16], relational graphs constructed from real-world databases are typically heterogeneous and temporal in nature. To further quantify this property, we compute the Edge Homophily Ratio [56] on all evaluated datasets. As shown in Table 15, all datasets consistently exhibit low homophily ratios (all < 0.5), indicating strong heterophily. This empirical evidence supports the conclusion that relational graphs in our setting are inherently heterophilous rather than homophilous. Role of low-similarity neighbors. A key design choice in our method is to filter out low-similarity neighbors, which are treated as noisy or less informative connections. This design is supported by both empirical observations and the underlying modeling mechanism. From an empirical perspective, as shown in Figure 4a of the main paper, increasing the number of sampled neighbors—thereby introducing more low-similarity neighbors—leads to a consistent degradation in performance. This indicates that such neighbors tend to introduce noise rather than useful signal for prediction. From a mechanistic perspective, following the formulation in [36], our model projects tabular attributes and positional encodings into a shared semantic latent space, where similarity reflects task-relevant semantic correlation rather than structural homophily. Under this view, neighbors with low similarity in the learned space are more likely to be task-irrelevant and thus act as noise. Filtering them therefore improves representation quality and predictive performance. Overall, these results suggest that low-similarity neighbors are generally not beneficial for the considered tasks under our semantic similarity space, and instead may negatively affect model performance when included indiscriminately. F.4

Analysis of Gaussian Temporal Bias

In this section, we analyze the design choice of the proposed Gaussian temporal bias and compare it with alternative temporal modeling strategies to better understand its advantages. Comparison with alternative temporal bias mechanisms. We first compare our method with two representative alternatives: (1) scaled linear temporal biases [57], and (2) learnable temporal embeddings [58]. Scaled linear biases impose a monotonically increasing penalty with respect to temporal distance, effectively favoring recent interactions. However, such a design is limited in modeling non-monotonic or periodic temporal dependencies commonly observed in real-world relational data. In contrast, our Gaussian formulation introduces a learnable mean parameter, which allows the attention peak to shift adaptively toward task-relevant historical periods rather than strictly prioritizing recent events. Learnable temporal embeddings, on the other hand, discretize time into bins and assign independent parameters to each interval. While expressive, this approach increases parameter complexity linearly 26

Table 16: Performance comparison (AUC) of different temporal bias mechanisms. Task Scaled Linear Bias Temporal Embedding Ours f1-driver-dnf avito-user-clicks event-user-repeat trial-study-outcome amazon-item-churn stack-user-badge hm-user-churn

0.75 0.67 0.75 0.70 0.69 0.89 0.68

0.75 0.67 0.74 0.71 0.69 0.88 0.67

0.76 0.68 0.76 0.72 0.70 0.90 0.69

with the temporal range and may introduce redundancy. In comparison, our Gaussian bias only introduces two learnable scalars per attention head (mean and variance), making it significantly more parameter-efficient and scalable across varying time spans. Empirical comparison. We further evaluate the effectiveness of different temporal bias designs across multiple tasks. As shown in Table 16, our Gaussian temporal bias consistently outperforms both baselines. Discussion. The results demonstrate that the Gaussian temporal bias effectively captures more flexible temporal patterns compared to monotonic or discretized formulations. This flexibility, together with its parameter efficiency, enables consistent improvements across diverse relational prediction tasks. F.5

Additional Discussion on Design Choices

In this section, we further clarify the design motivations behind the proposed components and highlight their relevance to the unique challenges of relational deep learning (RDL). Gaussian temporal modeling. Timestamped interactions in relational databases often exhibit continuous, irregular, and non-monotonic temporal dynamics. To effectively capture such patterns, we propose a Gaussian temporal bias mechanism, which introduces only two learnable scalar parameters per attention head. Compared to scaled linear biases [57], which enforce a strictly monotonic temporal decay, and learnable temporal embeddings [58], which discretize time and scale parameters with temporal granularity, our formulation provides a more flexible and compact representation of temporal influence. In particular, the learnable mean enables adaptive shifting of the attention peak toward task-relevant historical periods, while the variance controls the temporal sensitivity range. This design offers a principled and parameter-efficient alternative for continuous temporal modeling in relational graphs. Temporal-aware BFS sampling. Our sampling strategy is also carefully designed for relational databases and is not a direct application of standard BFS. Instead, we incorporate explicit temporal constraints into the BFS traversal process. This design ensures that sampled subgraphs preserve both (i) complete primary–foreign key relational structures and (ii) strict temporal causality. Unlike prior RDL sampling methods [56, 12, 16], which either ignore temporal ordering or fail to jointly preserve structural and temporal consistency, our approach enables the extraction of causally valid relational subgraphs. This makes it particularly suitable for learning over dynamic relational systems where both structure and time are critical. Summary. Overall, the proposed designs are specifically motivated by the characteristics of relational databases, where both temporal irregularity and schema-driven structure play central roles. These components jointly provide a unified and efficient framework for relational representation learning. 27

F.6

Sampling Budget Analysis

To justify the choice of a fixed candidate size in our original design, we analyze the effect of sampling budget on both performance and efficiency. To better understand the effective neighborhood size, we additionally introduce an auxiliary diagnostic mechanism with adaptive soft-gating, which is used solely for analysis and is not involved in training or inference of the proposed model. This analysis reveals that the effective number of retained neighbors consistently stabilizes around a fixed range, providing empirical support for our initial design choice. As shown in Table 17, the average number of retained effective neighbors across datasets ranges between 249 and 347, with a mean value close to 300. This indicates that a sampling budget around 300 is sufficient to capture informative relational semantics while avoiding excessive redundancy.

Table 17: Average effective number of retained neighbors under adaptive soft-gating. Dataset Avg. Effective Neighbors f1-driver-dnf 298 avito-user-clicks 275 event-user-repeat 324 trial-study-outcome 307 amazon-item-churn 249 stack-user-badge 333 hm-user-churn 347 From an efficiency perspective, increasing the sampling budget beyond 300 yields marginal performance gains but significantly increases computational and memory overhead due to quadratic attention complexity. In contrast, smaller budgets (e.g., below 200) tend to truncate informative relational signals, particularly in dense or heterogeneous graphs. Overall, a budget of 300 achieves a favorable trade-off between semantic coverage, efficiency, and cross-dataset stability. This also aligns with our adaptive mechanism, where the learned effective neighborhood size naturally stabilizes around this range.

F.7

Stability of Gaussian Bias Parameters

We empirically study the optimization behavior of the Gaussian temporal bias parameters. The results show that these parameters exhibit fast and stable convergence during training, rather than instability. From a theoretical perspective, as shown in Lemma 3.3, the gradient contains a linear restoring term that provides a global directional force towards a stable equilibrium. This design ensures well-conditioned optimization dynamics and prevents oscillatory updates. We further track the parameter evolution on the trial-study-outcome dataset. As shown in Table 18, the parameters rapidly converge within the first few epochs and remain stable thereafter.

Table 18: Evolution of Gaussian bias parameters during training. Epoch µ σ 1 33.31 9.98 3 33.27 9.94 5 33.24 9.90 7 33.20 9.86 9 33.16 9.83 10 33.16 9.83 These results demonstrate that the Gaussian bias parameters are not sensitive to optimization instability and instead converge reliably to a stable region. 28

G

Reproducibility and Code Availability

To ensure the reproducibility of our results, we have provided the complete source code and scripts in https://github.com/USTC-DataDarknessLab/GelGT. Detailed instructions for setting up the environment and running the experiments are included in the attached README file.

H

Limitations and Broader Impacts

H.1

Limitations

While GelGT achieves state-of-the-art predictive performance and strong computational efficiency on standard relational databases, its deployment in extreme ultra-high-frequency scenarios—such as millisecond-level financial trading—remains an open challenge. Such specialized environments impose extreme physical latency constraints that fall outside the typical scope of current relational graph learning frameworks, presenting an interesting direction for future engineering efforts. H.2

Broader Impacts

Our work proposes a novel graph transformer architecture for relational graph learning, offering robust support for predictive tasks in relational databases and advancing the field of Machine Learning. This work is foundational research in Machine Learning. We do not foresee any immediate negative societal impacts specific to this work.

29

Related documents

• FPT=PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns#1006936
• kgsteward: a tool for building, reproducing and maintaining distributed knowledge graphs#1006937
• The Stochastic Shift: A New Evaluation Paradigm for Text-to-SQL with AI Operators#1006938
• SKYE: Write-Optimized Key-Value Store with Fine-Grained Control over Persistent Memory Accesses#1006939
• BI-Agent and BI-Bench: Towards Automating End-to-End Business Intelligence#1006940