1 Introduction↩︎

Relational databases (RDBs), housing collections of interrelated tables, are indispensable across wide-ranging enterprise applications and e-commerce platforms [1]. From a machine learning standpoint, the information stored within just a single RDB often contains countless possibilities for predictive modeling, covering targets such as customer retention, user churn, or click-through rates [2]–[5]. Of course retraining a new model from scratch to address each new predictive task of interest may be prohibitively laborious or expensive, which motivates a new class of foundation models (FMs) specifically tailored for RDBs. Among others, these vary from LLM-based approaches that digest serialized RDB content [6], to specialized Transformers pre-trained based on in-context learning (ICL) [7]–[9], the common theme in each case being a frozen architecture capable of making predictions involving arbitrary unseen RDBs.

As a robust and scalable alternative, it has also been demonstrated that certain parameter-free subgraph encoders combined with single-table foundation models can achieve near SOTA performance without requiring any RDB-specific pre-training [10]. And yet significant ambiguity still exists over RDB embedding and pre-training requirements for FMs. This is largely because of recent architectures with parameterized encoders that accept observable neighborhood labels as supplementary discriminative inputs [8], [11], [12], a common technique from graph learning [13], [14]. Performance results using such models point towards the continued efficacy of RDB-specific pre-training to optimally exploit these labels on new tasks.

To help resolve this ambiguity, herein we closely examine notable factors influencing the performance of parameterized versus parameter-free RDB encoders, particularly when observable labels are available as encoder inputs. Our contributions are as follows:

• On the theoretical side, we analyze two complementary roles that labels may fill as encoder inputs, either as standard discriminative features or as a mechanism for determining the importance of other discriminative features. This includes proving limitations on the general ability of trainable encoder parameters to exploit these roles w.r.t. downstream performance.

• Consistent with theory, we provide supporting empirical results demonstrating that even when granted labels occupying available inference-time roles, trainable/parameterized encoders do not hold an unequivocal advantage over much simpler, parameter-free designs.

2 Basics of RDB Foundation Models↩︎

The goal of an RDB foundation model is to retain applicability across unseen RDBs, ideally with no retraining required for each new predictive task. Beyond direct LLM-prompting approaches [6], we now discuss background context and recent pipelines designed for natively handling RDB and/or tabular data.

2.1 Predictive Modeling with Relational Context↩︎

In traditional supervised learning settings, we are given training data \(\calD = \{\bX,\by \} \equiv \{\bx_{i:},y_i \}_{i=1}^{n}\) with instance feature rows \(\bx_{i:} \in \calX^{d}\) and corresponding instance labels \(y_i \in \calY\) for all \(i\). The goal is then to learn a parameterized model \(f_\theta\) such that \(f_\theta(\bx_{\tiny test}) \approx y_{\tiny test}\) at any test point \(\{\bx_{\tiny test}, y_{\tiny test} \}\), where in practice \(y_{\tiny test}\) is unknown. RDB predictive modeling generalizes the above via the inclusion of an additional set of auxiliary data tables \(\calT =\{\bT^k \}_{k=1}^K\), where \(\bT^k \in \mathfrak{T}^{n_k \times d_k}\) denotes the \(k\)-th table associated with a given entity type. Each table row corresponds with a single instance of that entity (e.g., an individual user), and the columns encode heterogeneous instance attributes (e.g., elements of a user profile). Note that without loss of generality, we also assert that \(\bT^K \equiv \bX\). To complete its specification and make use of these auxiliary tables for making predictions, an RDB also includes a set of relations \(\calR\) expressed as primary key (PK) foreign key (FK) pairs [1].

2.2 Computing RDB Embeddings↩︎

To make use of relational context for predictive tasks, the basic strategy is to first convert a given RDB \(\{\calT,\calR \}\) to a heterogeneous graph \(\calG\). This typically involves treating each table \(\bT^k\) as a node type and each row \(i\) within a given \(\bT^k\) as a node with features \(\bt^k_{i:}\) [15]–[19]. Directed edges can then be formed using each PK-FK pair within \(\calR\). We next sample \(H\)-hop subgraphs or ego-networks \(\calG_H(\bx_{i:})\) from \(\calG\) that are centered at each target row \(\bx_{i:}\) within \(\bX\). Importantly, sampling for temporal RDBs should exclude nodes with time-stamps later than \(\bx_{i:}\). These subgraphs form the input to an RDB encoder \(g_\phi\), instantiated as some form of graph neural network (GNN) or graph Transformer architecture with (optional) parameters \(\phi\). This facilitates computation of fixed-length embeddings \(\bz_{i:} = g_\phi[ \calG_H(\bx_{i:}) ] \in \mathbb{R}^{d_z}\).

2.3 Combining with RDB Prediction Heads↩︎

Embeddings obtained via \(g_\phi\) are combined with a parameterized prediction head \(q_\theta\) in two primary ways.

2.3.0.1 Schema-agnostic models.

Provided the encoder \(g_\phi\) is designed to digest a broad spectrum of input RDB schema using a shared representational form, then it is possible to train a single composite model \(q_\theta\big(y ~|~\bz_{\tiny test}) \equiv q_\theta\big(y ~|~ g_\phi\big[ \calG_H(\bx_{\tiny test}) \big] \big)\) to assign high probability to labels \(y = y_{\tiny test}\) (or \(y \approx y_{\tiny test}\) for regression tasks) across a range of real-world RDBs [12], [20], [21]. Here \(\bx_{\tiny test}\) can be viewed as additional unlabeled rows appended to \(\bX\). Such models can in principle be applied to new unseen RDBs without further training.

2.3.0.2 ICL-based models.

A limitation of the schema-agnostic models from above is that the effective context available for making predictions is merely the subgraph \(\calG_H(\bx_{\tiny test})\), which in isolation may not contain sufficient information pertaining to broader labeling patterns across a vast RDB. In-context learning provides a natural workaround by granting the prediction head diverse samples of multiple analogous subgraphs, including past labels where available, extracted from each new RDB of interest. Specifically, ICL-based architectures derive predictions from the revised \[q_\theta\big(y ~|~\bz_{\tiny test}, \calD),~with~ \calD = \{\bz_{i:}, y_i \}_{i=1}^n, ~\bz = g_\phi[ \calG_H(\bx) ], \nonumber \vspace*{-0.1cm}\] where \(\bz_{\tiny test}\) and each \(\bz_{i:}\) are obtained by passing unlabeled and labeled rows of \(\bX\) through the shared encoder \(g_\theta\). Mirroring a growing number of successful single-table foundation model designs [22]–[26], \(q_\theta\) is implemented via various Transformer architectures that grant flexibility over \(n\) and \(d_z\). Finally, model pre-training is conducted using large volumes of synthetically-generated data following single-table pipelines, possibly combined with real-world RDBs [7]–[9], [11].

2.4 Two Foundational Questions↩︎

2.4.0.1 Is RDB-Specific Pre-Training Actually Necessary?

It is initially reasonable to assume that pre-training RDB foundation models specifically using RDB data is absolutely essential for achieving strong inference-time performance. However, recent work [10] has suggested otherwise for ICL-based architectures. The high-level idea is that prior to seeing ICL samples, a necessarily fixed \(g_\theta\) is incapable of adjudicating column roles, which may vary from dataset to dataset (or even task to task within a given RDB). This phenomena advantages RDB encoders that only compress vertically within high-dimensional columns (where shared units facilitate interpretable aggregation), not horizontally across columns, where relevance is largely indeterminate adequate label information. Conditioned on this restriction to vertical compression, [10] formalize how a parameter-free encoder results in a minimal loss of expressiveness. And via the associated RDBLearn toolbox, we can directly pair this class of encoder with the most powerful existing single-table foundation models such that no actual RDB-specific pre-training is required. Empirically, this strategy is shown to match or exceed alternative RDB foundation models on previously-unseen predictive tasks.

2.4.0.2 Does providing the encoder with labels impact pre-training requirements?

Two counter-points challenge the efficacy of parameter-free encoders upon which the training-free approach mentioned above is based. Both involve the use of observable labels as inputs to a trainable \(g_\phi\). We analyze these scenarios next, providing new insights that inform the foundational questions of this section.

3 Labels as Extra Discriminative Features↩︎

Per previously-stated definitions, an RDB neighborhood subgraph \(\calG_H(\bx)\) may include nodes associated with other rows of \(\bT^K \equiv \bX\), provided these rows are reachable within \(H\) PK-FK hops and have an earlier time-stamp to avoid temporal leakage. As these rows have associated labels, it is natural to consider including them as extra node features to improve downstream predictability. We adopt \(\calG_H^*(\bx)\) to reference the resulting subgraph with these labels concatenated as additional node features; we are assuming here that any labels included within \(\calG^*_H(\bx)\) have time-stamps earlier than \(\bx\). In more traditional supervised learning regimes involving graphs, this is a common practice for improving node classification accuracy [27] (akin to a trainable form of label propagation). More recently, analogous ideas have been applied to RDB foundation models, whereby trainable encoders are explicitly designed to process past labels of similar entities within an RDB neighborhood [8], [11], [12].

But to what degree can we actually rely on such neighborhood labels as predictive features, specifically in the context of trainable RDB foundation model encoders \(g_\phi\) applied to \(\calG_H^*(\bx_{\tiny test})\) evaluated at an unlabeled test row of interest \(\bx_{\tiny test}\). To begin, for an arbitrary RDB we define \(\calG^*_{\tiny test}\) as an augmented version of \(\calG\), with \(\bx_{\tiny test}\) appended to \(\bX\), known labels associated with \(\bX\) included as candidate node features, but restricted to entities with timestamps earlier than \(\bx_{\tiny test}\). We also let \(\widetilde{\calG}^*_H(\bx_{\tiny test})\) denote \(\calG^*_{\tiny test} \backslash \calG^*_H(\bx_{\tiny test})\), meaning all RDB context outside of the label-infused \(H\)-hop ego-network centered at test point \(\bx_{\tiny test}\). And lastly, we adopt \(y_H(\bx_{\tiny test})\) to indicate the set of all past labels present within \(\calG^*_H(\bx_{\tiny test})\); this of course does not include the unknown label \(y_{\tiny test}\) associated with \(\bx_{\tiny test}\) itself. We then have the following:

Intuition behind of Proposition 1. Neighborhood labels within \(\calG_H^*(\bx)\) can be highly discriminative in a supervised setting, where training specifically on samples \(\{\calG^*_H(\bx_{i:}), y_i \}_{i=1}^{n}\) extracted from a single RDB predictive task facilitate learning a task-specific discriminative function \(f_\theta\) applicable to test points \(\calG^*_H(\bx_{\tiny test})\) (part 2). And yet it is not generally possible to determine a stable predictive role for these labels within an encoder that must remain fixed across varying datasets/tasks facing a foundation model architecture of the form \(q_\theta\big(y ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big)\) (part 1). Given this implication of Proposition 1, why then are existing schema-agnostic foundation models like the relational Transformer (RT) model from [12] capable of making successful predictions? A simple plausible hypothesis is that, within the handful of real-world RDBs available for pre-training RT models, homophily relationships¹ dominate, so simply adopting the majority label of local neighbors can be a highly discriminative feature. Empirical results from [12][Table 1] support this conclusion, namely, the similar performance of a trivial entity mean predictor explicitly predicated on homophily (66.7 avg AUROC) relative to RT (69.7 avg AUROC).

3.0.0.1 Implications for ICL-based models.

ICL provides one pathway for diversifying label usage effectively beyond the homophily-dominant regimes mentioned above; however, this remains true whether or not a parameter-free encoder is adopted. This is because even without trainable parameters, encoder representations can include diverse label aggregations that are sensitive to both homophily and heterophily relationships; the subsequent ICL-prediction head then sorts which are relevant for any given task. Note that canonical aggregators can trivially handle the parity check example constructed within the proof of Proposition 1 (see Appendix 10). Hence given evidence available thus far, the use of labels as discriminative features does not by itself provide a compelling reason to favor trainable parameterized RDB encoders within ICL-based models.

4 Labels for Adjudicating Feature Importance↩︎

Analysis from [10] indicates that uninformative feature columns within RDBs cannot generally be filtered out using a dataset-agnostic encoder, which reduces the motivation for including trainable encoder parameters. However, follow-up study [8] suggests that this calculus may change if the encoder is provided with local neighborhood labels (as in \(\calG_H^*(\bx)\)). The latter provide task-specific information, which may plausibly facilitate feature-column differentiation on a task-by-task basis as required by RDB foundation models. But is such differentiation generally possible even when \(\calG_H(\bx)\) is switched to \(\calG_H^*(\bx)\)? The answer is negative in the following sense:

4.0.0.1 Implications for ICL-based models.

While not strictly ruling out any benefit of trainable encoders, Proposition 2 does mute confidence in their ability to robustly screen uninformative columns through the use of local neighborhood labels as additional inputs. This plausibly suggests that, at least for RDBs with large numbers of feature columns (many of which are likely uninformative), trainable encoders may be unnecessary, especially given that parameter-free encoders are already structured to naturally handle column-wise feature screening [10]. Empirical results presented next further support these observations.

5 Empirical Support↩︎

5.0.0.1 Models.

We adopt an updated version of RDBLearn [28], the RDB FM pipeline with parameter-free encoder as analyzed by [10]; see Appendix 7 for our RDBLearn update details. For parameterized encoder FMs, we include a variety of both open-source and closed-source options with published results based on author specific tuning. Note that most models only provide results on a subset of available benchmarks. Lastly, we cover a handful of supervised baselines that represent either SOTA performance or classical methodology as a reference point. Appendix 8 includes all baseline model descriptions.

5.0.0.2 Results.

We compare across a suite of six diverse benchmarks from Appendix 8, each composed of multiple RDB predictive tasks. Results are shown in Figure 1 and Appendix 9, where RDBLearn (with just a simple parameter-free encoder) achieves the best overall performance among open-source FMs. And with the exception of two RelBench-v1 benchmarks, RDBLearn even outperforms all closed-source FMs that may involve pre-training with similarly-structured RDB content. We stress that RDBLearn was run directly from the open-source repository for all benchmarks with no task-specific adjustments and zero exposure to RDB data of any kind at any stage, i.e., there is no chance for any implicit test-set alignment on limited public benchmarks.

6 Take-Home Message↩︎

Our empirical results indicate that, at least until further advancements in the field, parameter-free RDB encoding combined with frontier single-table FMs is still competitive with the best closed-source industry architectures equipped with pre-trained, parameterized encoders. These findings are further supported by theoretical study of the encoder representations possible with neighborhood labels.

7 RDBLearn Updates↩︎

We describe a few modest updates to the RDBLearn package, which collectively constitute what we henceforth refer to as RDBLearn version 1.1.² These include the following:

• Aggregations: Because the original RDBLearn package [28] only supports a minimal set of rudimentary aggregation functions for encoding purposes (mean, min/max, standard deviation, counts, median), we explore a broader set that includes \(25\)-th quantiles and \(75\)-th quantiles for continuous feature columns, as well as discrete entropy for categorical feature columns. These increase model expressivity and are shared across all tasks/datasets. We also add the option to treat categorical variables as numerical values, which alters the space of candidate aggregators. When available, the validation set performance is used to select between the original aggregations and the expanded group listed here. See below for handling instances with no validation set.

• Base Model Predictors: One of the advantages of the RDBLearn architecture is that we may seamlessly incorporate any new frontier single-table foundation model. For RDBLearn-v1.1 we add TabICL-v2 [24] and TabPFN-v3 [29].

• Default Setting: For any benchmark with no official validation set, we adopt a simplified RDBLearn default setting. Specifically, the base tabular predictor is fixed as TabPFNv2.5 [30], encoder depth is \(H=4\), and aggregation is the new expanded set mentioned above.

We remark that there are multiple promising directions whereby RDBLearn could plausibly be improved further. For example, presently RDBLearn simply ignores all text-based columns, unlike most other foundation models that adopt some form of text embedding. And secondly, RDBLearn does not as of yet provide its encoder with any local neighborhood labels, the topic of Sections 3 and 4. Note that even though we have argued in the main text that the presence of such labels need not necessarily favor a parameterized encoder over a parameter-free one, our analysis does not suggest that such labels (when available) possess no advantage as extra encoder inputs. In fact, there may well be many instances where their inclusion directly benefits parameter-free encoder models like RDBLearn. Certainly prior analysis from elsewhere indicates that they have discriminative value in broader contexts [27].

8 Experiment Details↩︎

8.1 Description of Baseline Approaches↩︎

We present evaluations across a wide range of RDB predictive architectures, including both foundation models and more traditional supervised learning approaches. For a detailed taxonomy of the FM architectures, please see Figure 2.

8.1.0.1 Closed-Source Foundation Models.

We include the original industry model KumoRFM-1 [7] as well as the more recent version KumoRFM-2 [8] that incorporates task-specific labels to the encoder as discussed in Section 4 of our main text. We also consider TabPFN-REL, which is likely based at least in part on the recently-released TabPFN-v3 [29], although no RDB-specific details of the architecture have been disclosed as of yet. Lastly, we compare with OpenRFM [11]; while this model is presumably intended to be open-sourced at some point, presently the full code is not available. For all of these closed-source approaches we rely on posted performance results from original authors for evaluation purposes, with one exception. We follow [29], who have independently reevaluated KumoRFM-2 performance using API calls for certain datasets using author-provided benchmarking scripts; see further details in Appendix 9.

8.1.0.2 Open-Source Foundation Models.

We compare RDBLearn against a variety of open-source foundation models including the schema-agnostic Griffin [20], RelLLM [21] models, and RT (relational transformer) [12]. On the open-source ICL-based side we include results from PluRel [9], RDB-PFN [31], and our own implemented baseline RandGNN, which combines a random-weight GNN encoder with a single-table FM (see [10] for details). RandGNN represents a form of ablation w.r.t. RDBLearn, in that it explicitly mixes cross-column information in a manner at odds with the theoretical considerations upon which RDBLearn is based. And finally, for pure language model baselines, we evaluate LLM-A [32] (as tested in [12]) and LLM-B [6]; both approaches are predicated on serialized RDB neighborhood representations and/or ICL samples. Although the underlying LLMs are not open-source, we nonetheless categorize these two approaches as open-source in that the prompting needed to reproduce results are publicly available and no hidden fine-tuning steps are involved.

8.1.0.3 Task-Specific Supervised Models.

While our emphasis is on RDB foundation models, it is still useful to contextualize FM performance results w.r.t. methods benefitting from per-task supervised training. On this front, largely following prior work, we include the more classical standards LightGBM, XGBoost, and GraphSage as evaluated in [8]. Meanwhile, for recent SOTA supervised architectures we select RelGNN [33], RelGT [16], and RelAgent [34].

8.2 RDB Benchmarks↩︎

We evaluate RDB predictive modeling approaches over a diverse suite of benchmarks, including regression and binary classification tasks from both RelBench-v1 [35] and RelBench-v2 [36]. Beyond these, we test over the 4DBInfer [37] binary classification datasets used in several recent works, as well as the multi-class predictive tasks from the SALT repository [38] as adopted by [8]. Note that for RelBench-v1, we omit only rel-f1 and rel-event datasets because of potential leakage issues mentioned elsewhere.

8.3 Subtleties of RDB Benchmarking↩︎

8.3.0.1 Language Model Agents.

A growing body of evidence suggests that LLM agents can play a useful role in tabular model development [34], [39]–[41]. That being said, their usage within the context of RDB benchmarking involves notable caveats. One in particular relates to potential leakage issues that may obscure the degree to which we can plausibly extrapolate benchmarking results to expected performance within siloed industry settings. This concern stems from the fact that existing public benchmarks are scarce, largely because of privacy concerns with real-world data. And yet predictive solutions addressing the few RDB datasets that do exist, often involving feature engineering and human expertise, are readily visible to frontier LLM agents during their pre-training process. Hence agent-based solutions may simply lean on problem-specific prior human knowledge to a degree that may not be possible on less-familiar or esoteric tasks within private RDB repositories. Of course this is not meant to discourage LLM-based RDB frameworks, and certainly RDBLearn is a natural fit for agentic enhancements [10]. We only advocate that some caution is warranted when interpreting results, especially when extrapolating to new domains. While similar concerns have certainly been raised with other data modalities, we would argue that the situation is more acute in RDB regimes with only limited, relatively well-known benchmarking sources that are susceptible to memorized solutions.

8.3.0.2 Validation Set Usage within Foundation Models.

[8] mention that as an RDB foundation model, KumoRFM-2 does not require a validation set for task-specific training. Consequently, for reported results they merge official training-set and validaion-set splits for constructing ICL samples. This can provide an advantage, since for temporal datasets (the norm with RDBs), validation-set splits are often closer in time to the test set. But this same strategy can be applied to other RDB foundation models, including parameter-free encoder architectures like RDBLearn. In preliminary testing with this approach, we observe that RDBLearn can indeed incur benefits, although further study is warranted to explore how to balance training-set and validation-set contributions within ICL sample batches. We also note that KumoRFM-2 usage depends on a broad set of explicit hyperparameters, the default settings of which vary across tasks and datasets according to author-provided scripts.³ However, it remains unclear how these were chosen, e.g., using validation set performance (which might entangle with the ICL-sample selection mentioned above) or else via some other undisclosed criteria. Without such a prescription, it is also uncertain how these hyperparameters should be adapted for new user-provided RDB predictive tasks.

9 Extended Empirical Results↩︎

In this section we provide the full set of experimental results upon which the final rankings shown in Figure 1 from the main text are based. Overall, RDBLearn is consistently competitive against other approaches that possess more sophisticated pre-trained parameterized encoders. In fact, RDBLearn is superior to all foundation models on all tasks, with the exception of only the closed-source TabPFN-REL, and conditionally KumoRFM-2 (see Tables 5 and 6 below), restricted to RelBench-v1 datasets. We remark that many enhancements potentially adopted by these models (e.g., intelligent ensembling, post-processing, ICL sampling strategies, and/or text-field handling as mentioned by [8]) could equally-well benefit RDBLearn, and need not undermine the utility of a parameter-free encoder design.

5pt

5.5pt

5.5pt

5.5pt

5.5pt

10 Technical Proofs↩︎

10.1 Proof of Proposition 1↩︎

10.1.0.1 High-Level Intuition.

To illustrate the gist of this result, assume that the ground-truth label \(y_{\tiny test}\) for any \(\bx_{\tiny test}\) is given by a parity check on available labels in \(\calG_H^*(\bx_{\tiny test})\). This labeling rule is impossible to determine from \(y_H(\bx_{\tiny test})\) alone, since for any node \(\bx'\) associated with a label \(y' \in y_H(\bx_{\tiny test})\), the corresponding set \(y_H(\bx')\) need not be fully observed, i.e., the overlap between \(y_H(\bx')\) (with a known label for \(\bx'\)) and \(y_H(\bx_{\tiny test})\) (with an unknown label for \(\bx_{\tiny test}\)) is only partial. Hence the parity rule is not identifiable, as even a single missing label can flip the result. This disrupts inductive inference from the information available within \(\calG^*_H(\bx_{\tiny test})\), which is all a fixed FM encoder has access too. In contrast, if per-dataset training is allowed over RDB instances formed via a given parity-based labeling rule, it is straightforward to learn the associated mapping on a dataset-by-dataset or task-by-task basis. We remark that, although the proof below relies on parity checks for illustrative convenience, the underlying phenomena is emblematic of quite broad scenarios where diverse heterophilic (as opposed to homophilic) relationships are dominant.

10.1.0.2 Basic Setup.

The basic proof follows from the construction of a suitable joint distribution over context \(\widetilde{\calG}_H^*(\bx_{\tiny test})\) and test label \(y_{\tiny test}\). Meanwhile, by assumption we have that \(\calG_H^*(\bx_{\tiny test})\) is fixed and given. To begin, we introduce a latent indicator variable \(z \in \{0,1\}\) that selects among two deterministic generative processes for \(\{\widetilde{\calG}^*_H(\bx_{\tiny test}), y_{\tiny test} \}\). In this way, all randomness in the joint distribution \(p(\widetilde{\calG}^*_H(\bx_{\tiny test}), y_{\tiny test} ~|~\calG_H^*(\bx_{\tiny test}))\) will ultimately reduce to randomness from \(p(z)\). We emphasize that this is not meant to exclude broader sources of randomness that naturally describe RDB content; instead, we are merely distilling down to a minimal design case that nonetheless still allows us to establish the proposition. Other latent sources of variation associated with real-world RDBs then become largely orthogonal to our result and need not be explicitly specified.

10.1.0.3 Label Assumptions.

We assume that all labels are binary, namely, \(y \in \{0,1\}\). While generalization to broader label domains \(\calY\) is feasible, it introduces superfluous complexity given that the binary case is already sufficient for establishing the proof. For any \(y_H(\bx) \neq \emptyset\), where \(y_H(\bx)\) indicates the set of all past labels present within \(\calG^*_H(\bx)\) for some arbitrary \(\bx\), we define conditional label generation via a parity function and its negative given by \[\begin{align} \label{eq:label95assign} \pi\big[ y_H(\bx) ~;~z = 1 \big] & := & \left[ \sum_{y \in y_H(\bx)} y \right]\mod 2 \nonumber \\ \pi\big[ y_H(\bx) ~;~z = 0 \big] & := & \neg \pi \big[ y_H(\bx); z = 1 \big], \end{align}\tag{1}\] both of which output a label \(y \in \{0,1\}\).

10.1.0.4 Context Assumptions.

We specify a function \(h\big( \calG_H^*(\bx_{\tiny test}) ; z\big)\) for context generation. To ensure no conflicting labels, for \(z=1\) we define this \(h\) such that \(\widetilde{\calG}^*_H(\bx_{\tiny test})\) has label assignments consistent with both \(y_H(\bx_{\tiny test})\) and the label assignment rule \(\pi\big[ ~ \cdot ~;~z = 1 \big]\) from (1 ). This will always be achievable by introducing new appropriately-labeled neighbors to specific nodes of \(\calG_H^*(\bx_{\tiny test})\) associated with elements of \(y_H(\bx_{\tiny test})\).

To establish this possibility, assume an arbitrary trial arrangement of node features, edges, and labels within \(\widetilde{\calG}^*_H(\bx_{\tiny test})\), but following the typing of \(\calG^*_H(\bx_{\tiny test})\) for consistency. Then consider any \(y' \in y_H(\bx_{\tiny test})\) with corresponding \(\bx'\) extracted from the associated row of \(\bX \equiv \bT^K\) (per original definitions in the main text). For consistency with the labeling rule (1 ) with \(z=1\), we require that \(y' = \pi\big[ y_H(\bx') ~;~z = 1 \big]\), which may not initially be the case since labeling assignments were thus far assumed arbitrary. However, for any node where this is not the case, we can add a single additional labeled neighbor to \(\widetilde{\calG}^*_H(\bx_{\tiny test})\), with an earlier time-stamp and a label selected to flip the parity check, such that we obtain the necessary equality.

Such a neighbor can be added in multiple ways given that \(H \geq 2\) (note that if \(H=1\) then \(|y_H(\bx_{\tiny test})| = 0\), i.e., no labels within one hop, which is not allowed by assumption). First, assume \(H=2\), if some table \(T^k\) exists with at least two FK columns pointing to the PK column associated with \(T^K \equiv \bX\), we can trivially add such a neighbor by adding a new labeled row to \(T^K\) and a new row to \(T^k\) that links the former to \(\bx' \in T^K\). Meanwhile, if such a \(T^k\) does not exist, we can simply add such a table to \(\widetilde{\calG}^*_H(\bx_{\tiny test})\). Moreover, when supplied with an earlier time-stamp, the added labeled node/row need not introduce any additional constraints vis-à-vis (1 ). With regard to the latter, if \(\bx''\) indicates the added node, we can directly enforce \(y_H(\bx'') = \emptyset\) as no nodes with earlier time-steps exist, and so \(y''\) can be selected free of any constraint from (1 ), which would only apply if \(y_H(\bx'') \neq \emptyset\). Lastly, because this added label will by design be two hops from \(\bx'\) and three or more hops from any other labeled rows, it will not introduce new conflicts per (1 ) if \(H =2\). For \(H > 2\) an analogous procedure can be applied pushing the new labeled node to \(H\) hops away from \(\bx'\) so as to achieve the same effect.

In an analogous manner we can also define \(h\) when \(z=0\), handling label consistency via the introduction of neighboring nodes to adjust parity accordingly. Again, we are granted this flexibility by assumption, since only \(\calG^*_H(\bx_{\tiny test})\) is fixed and given.

10.1.0.5 Finalizing Part 1.

Per the assumptions stated above and the appropriate counting measure, it directly follows that \(\int p\left(y_{\tiny test} | \calG^*_{\tiny test} \right) \log p\left(y_{\tiny test} | \calG^*_{\tiny test} \right) d y_{\tiny test} ~=~0\) trivially establishing that \(y_{\tiny test}\) is a deterministic function of \(\calG^*_{\tiny test}\). Furthermore, given \(\calG^*_{\tiny test} = \left\{\widetilde{\calG}^*_H(\bx_{\tiny test}), \calG^*_H(\bx_{\tiny test}) \right\}\) by definition, we also have that \[\begin{align} \label{eq:KL95stuff1} &&\mathbb{E}_{p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}) | \calG^*_H(\bx_{\tiny test}) \right)} \left[ \mathbb{KL}\Big[ p(y_{\tiny test} |\calG^*_{\tiny test}) ~||~ q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) \Big] \right] \nonumber \\ &&= \int p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}) | \calG^*_H(\bx_{\tiny test}) \right) \int p\left(y_{\tiny test} | \calG^*_{\tiny test} \right) \log \frac{p\left(y_{\tiny test} | \calG^*_{\tiny test} \right)}{q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big)} d y_{\tiny test} d \widetilde{\calG}^*_H(\bx_{\tiny test}) \nonumber \\ &&= - \int p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}) | \calG^*_H(\bx_{\tiny test}) \right) \int p\left(y_{\tiny test} | \widetilde{\calG}^*_H(\bx_{\tiny test}), \calG^*_H(\bx_{\tiny test}) \right) \log q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) d y_{\tiny test} d \widetilde{\calG}^*_H(\bx_{\tiny test}) \nonumber \\ &&= - \int \int p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}),y_{\tiny test} | \calG^*_H(\bx_{\tiny test}) \right) \log q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) d y_{\tiny test} d \widetilde{\calG}^*_H(\bx_{\tiny test}) \end{align}\tag{2}\]

for any fixed \(g_\phi\) and \(q_\theta\). By construction, \(p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}),y_{\tiny test} | \calG^*_H(\bx_{\tiny test}) \right) \neq 0\) at only two points associated with \(z = 0\) and \(z = 1\). Let \(y_{\tiny test}^{(0)}\) and \(y_{\tiny test}^{(1)}\) denote the value of \(y_{\tiny test}\) at these two points. Moreover, if we assume that \(z\) is drawn uniformly over \(\{0,1\}\), we have \(\calG_H^*(\bx_{\tiny test}) \perp \!\!\! \perp z\) and so we may conclude from (2 ) that \[\begin{align} &&\mathbb{E}_{p\left(\widetilde{\calG}^*_H(\bx_{\tiny test}) | \calG^*_H(\bx_{\tiny test}) \right)} \left[ \mathbb{KL}\Big[ p(y_{\tiny test} |\calG_{\tiny test}) ~||~ q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) \Big] \right] \nonumber \\ &&= ~~ -p(z=0)\log q_\theta\big(y_{\tiny test}^{(0)} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) ~-~ p(z=1)\log q_\theta\big(y_{\tiny test}^{(1)} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big) \nonumber \\ &&\geq ~~ \mathbb{H}[z] ~ = ~ \log 2. \end{align}\] This lower bound is achievable iff \(q_\theta\big(y_{\tiny test} ~|~ g_\phi\big[ \calG^*_H(\bx_{\tiny test}) \big] \big)\) is a uniform distribution over \(\{0,1\}\).

10.1.0.6 Finalizing Part 2.

Assume that some parameter-free encoder \(g\) computes the element-wise sum of \(y_H(\bx)\); other arbitrary features may be computed as well, but they are are ultimately treated as spurious features in what follows. Given this setup, the prediction head \(q_\theta\) need only learn to differentiate even and odd sums associated with \(y_H(\bx)\), while ignoring all other feature columns. For example, if \(z=1\) governs the generative process, then odd values of any sum over \(y_H(\bx)\) will be mapped to \(1\), even values to 0. Such functions can be directly represented by ReLU networks, and while not a requirement for this proof, are even efficiently learnable with additional assumptions [42].

10.2 Proof of Proposition 2↩︎

10.2.0.1 High-Level Intuition.

The proof follows through modifications applied to the original parity setup from Appendix 10.1. For illustrative simplicity, assume a single informative binary RDB feature column, whereby ground-truth labels are a deterministic function, akin to a parity check, on the values of all features from this column contained within \(\calG^*_H(\bx_{\tiny test})\). All other RDB columns are also binary but uninformative. Inclusion of \(y_H(\bx_{\tiny test})\) within \(\calG^*_H(\bx_{\tiny test})\) does not allow for differentiating which column is informative, for analogous reasons to those presented in establishing Proposition 1. In brief, for any node \(\bx'\) associated with a label \(y' \in y_H(\bx_{\tiny test})\), the corresponding set \(y_H(\bx')\) and its associated features need not be fully observed, and so a parity function on any column can produce an arbitrary distribution of \(y_H(\bx_{\tiny test})\). Consequently, the parity rule is not identifiable regardless of whether \(y_H(\bx_{\tiny test})\) is present or not as an encoder input. Note that this line of reasoning is not restricted to binary feature columns, as we can quantize continuous or categorical columns into binary ones in forming deterministic labeling functions for analysis purposes. We now turn to the actual proof.

10.2.0.2 Basic Setup.

As in the proof of Proposition 1, all randomness is encapsulated by a binary latent variable \(z\) that selects between two deterministic generative processes, now over \(\{\widetilde{\calG}^*_H(\bx_{\tiny test}), y_H(\bx_{\tiny test}), y_{\tiny test} \}\), i.e., only \(\calG_H(\bx_{\tiny test})\) as opposed to \(\calG^*_H(\bx_{\tiny test})\) is assumed fixed/given. When granted \(\calG_H(\bx)\) for some arbitrary \(\bx\), we specify the conditional label generation functions \[\begin{align} \label{eq:label95assign2} \pi\big[ \calG_H(\bx) ~;~z = 1 \big] & := & \left[ \sum_{\{i,j,k\} \in S_H^{(1)}(\bx)} \beta\left( t_{ij}^k \right) \right]\mod 2 \nonumber \\ \pi\big[ \calG_H(\bx) ~;~z = 0 \big] & := & \left[ \sum_{\{i,j,k\} \in S_H^{(0)}(\bx)} \beta\left( t_{ij}^k \right) \right]\mod 2, \end{align}\tag{3}\] where \(S_H^{(1)}(\bx)\) and \(S_H^{(0)}(\bx)\), associated with \(z=1\) and \(z=0\) respectively, represent distinct support sets over RDB column elements reachable within \(H\) hops from \(\bx\) following PK-FK pairs. In this way any \(\{i,j,k\} \in S^{(1)}_H(\bx)\) (or analogously, within \(S^{(0)}_H(\bx)\)) indicates the \(i\)-th element within a specific RDB column \(\bt_{:j}^k\), namely column \(j\) in table \(k\). Meanwhile \(\beta\) denotes a mapping from each table element to a binary value (this discretization is by no means necessary, but it facilitates a simplified exposition that is sufficient for establishing the core result). These values are then subsequently combined via the stated parity functions in (3 ) to produce binary labels \(y \in \{0,1\}\).

10.2.0.3 Establishing Part 1.

By adopting (3 ) as the label generating function, we trivially achieve the conditions of part 1 in Proposition 2. Specifically, with all randomness deferred to \(z\), which explicitly fixes the support set, all labels default to a deterministic function of the chosen support set, either \(S_H^{(0)}(\bx)\) or \(S_H^{(1)}(\bx)\) for any \(\bx\).

10.2.0.4 Establishing Part 2.

If we stipulate that \(z\) is drawn uniformly over \(\{0,1\}\) independently of \(\calG_H(\bx_{\tiny test})\), then we have \[p\left(S = S_H^{(0)}(\bx_{\tiny test}) ~|~ \calG_H(\bx_{\tiny test}) \right) ~=~ p\left(S = S_H^{(1)}(\bx_{\tiny test}) ~|~ \calG_H(\bx_{\tiny test}) \right) ~=~ \tfrac{1}{2}.\] However, by design we also have the flexibility to select the distribution over \(\widetilde{\calG}^*_H(\bx_{\tiny test})\) such that \(y_H(\bx_{\tiny test})\) is invariant to \(z\), even while \(y_{\tiny test}\) still depends on \(z\) through (3 ) applied at \(\bx_{\tiny test}\). To see this, note that each \(y' \in y_H(\bx_{\tiny test})\) is computed as \(\pi[\calG_H(\bx'); z]\), where \(\bx'\) is the target table feature row associated with \(y'\). Hence we only need enforce \[\label{eq:needed95equality} \pi\big[\calG_H(\bx');~ z=1 \big] = \pi\big[\calG_H(\bx');~ z=0 \big] ~~~ for each ~~ y' \in y_H(\bx_{\tiny test}).\tag{4}\] But this will always be possible per the following: Suppose the equality from (4 ) does not initially hold. We may add an additional element to either \(S_H^{(1)}(\bx')\) or \(S_H^{(0)}(\bx')\) (but not both) such that the corresponding tuple produces \(\beta(t_{ij}^k) = 1\) to flip the parity and induce equality. This is achievable without disrupting equality elsewhere by placing the added element within \(\widetilde{\calG}^*_H(\bx_{\tiny test})\), at a location \(H\) hops from \(\bx'\) and greater than \(H\) hops from other elements of \(y_H(\bx_{\tiny test})\). This placement mirrors an analogous placement strategy applied in Appendix 10.1, only here labeled nodes are not required.

Lastly, if (4 ) holds, then \[p\big(S | \calG^*_H(\bx_{\tiny test}) \big) = p\big(S | \calG_H(\bx_{\tiny test}), y_H(\bx_{\tiny test}) \big) = p\big(S | \calG_H(\bx_{\tiny test}) \big),\] completing the demonstration of part 2.

References↩︎