Most deep learning on relational databases predicts each entity's label on its own. A model reads a user, a clinical-trial site, or a patient together with its linked records, then outputs a probability for that one entity. Many practical questions are about groups instead: will at least one site in this trial fail, how many of the users who bought this product will churn, will a patient develop two or more diseases from a given set. A per-entity predictor answers these by multiplying its separate probabilities. That treats group members as independent, which is exactly what relational data is not. Labels of entities that share a transaction, a trial, or a pathway move together.
We propose to put a small joint probability model on top of a standard relational encoder. Each database record that links several entities (a row of a fact or junction table) becomes a hyperedge, meaning a single connection among all the entities it touches rather than a set of pairs. Each hyperedge gets a learned neural "compatibility score" over the joint labels of its members. The result is a neural Markov network whose factors are whole hyperedges. It is trained on the single observed database by pseudolikelihood and queried by sampling. The claim is narrow and testable. On group-level questions, this model should give calibrated answers where products of marginals and pairwise-correlation fixes are systematically wrong. Per-entity accuracy should match the encoder it builds on, and a single trained model should answer any group query after training, without retraining for each one.
Core Claim and Positioning
The three directions play different roles here. Statistical relational learning supplies the core mechanism: a template that ties one set of factor parameters across all groundings, defining a distribution over joint label assignments. Higher-order modeling sets the shape of those factors, which act on hyperedges of variable size and not on pairs. Relational dependency modeling supplies the constraints. We learn from one interconnected database, hubs break the usual independence arguments, and spurious dependence must be ruled out.
The closest work is Neural markov logic networks. It replaces hand-written Markov logic formulas with neural potentials over small, anonymized fragments of a relational structure, and it parallelizes Gibbs sampling by edge coloring. Its potentials act on low-order local fragments, and its experiments target knowledge-base completion and molecule generation. It does not work with schema-defined hyperedges of arbitrary size in large databases, nor does it evaluate group-level calibration. We reuse its two key techniques, permutation-invariant potentials and coloring-based parallel sampling. We change what a factor is: one database record of any arity. We also change what is evaluated: the joint answer about a group.
Two other papers motivate the approach without doing it. Disentangling Latent Risk Pathways via Bayesian Hypergraph Inference models multimorbidity in UK Biobank with latent disease-pathway hyperedges. It shows that rare diseases gain AUC by borrowing strength within a hyperedge. However, its hyperedges are latent, its observation model is linear, and it is built for one domain. Our hyperedges are given by the schema and our potentials are nonlinear, and we test whether the borrowing effect carries over to generic relational databases. Hypergraph Lifting for Structure Learning in Markov Logic Networks uses hypergraphs only as a search heuristic for symbolic clauses. We use them as the factor graph itself.
Two further papers supply the encoders we build on. RelGNN: Composite Message Passing for Relational Deep Learning and Grables: Tabular Learning Beyond Independent Rows are strong discriminative encoders. Grables also proves that row-local models cannot express count and overlap targets. Our argument is the probabilistic analogue of that result. A model that represents relational inputs well can still produce outputs that are conditionally independent across entities, and so it cannot express joint answers about groups.
We considered and rejected a more obvious idea: "encode multi-table joins as native hyperedges" (the file's Gap 4). Standard relational deep learning already turns each fact-table row into a node linked to its foreign keys. That construction is the star expansion of a hyperedge, so two-stage hypergraph message passing would mostly reproduce existing encoders. The higher-order structure that is actually missing sits in the output distribution, not in the input representation.
The Model
Let $y_v$ be the label of entity $v$ and $x$ the full database. The relational encoder produces per-entity potentials $u_\psi(y_v, x)$ and, for every hyperedge $e$, an embedding $h_e$ of the record that defines it. The joint conditional distribution is
$$P(y \mid x) \propto \exp\Big(\sum_v u_\psi(y_v, x) + \sum_{e} \phi_\theta\big(\{y_w\}_{w \in e},\, h_e\big)\Big),$$
where $\phi_\theta$ is a permutation-invariant network over the multiset of member labels. It is built as a sum-then-transform over members, conditioned on $h_e$, so one parameter set covers hyperedges of any size. Setting $\phi_\theta = 0$ recovers the encoder's independent marginals exactly. This gives a clean ablation. Restricting $\phi_\theta$ to a sum of pairwise terms gives the clique-expansion model, which is the second ablation.
Training uses pseudolikelihood. Each entity's label is predicted given the true labels of its hyperedge co-members, which needs only a sum over that one entity's label values. Relational Learning with One Network: An Asymptotic Analysis proves that pseudolikelihood is consistent on a single network under two conditions. The first is local finiteness, meaning bounded degree. The second is weak dependence, meaning correlation between labels fades with network distance. That paper also shows that grouping variables into larger components narrows the efficiency gap to full maximum likelihood.
Both conditions fail around hubs. A best-selling product row or a large trial ties together thousands of entities, and Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph β-Model documents how skewed hypergraph participation is. We therefore cap hyperedge size during training by sampling sub-hyperedges of at most $k$ members. Following the component-construction heuristic of the asymptotic paper, we train on blocks of co-members rather than single entities, and we report how results depend on $k$.
Inference is Gibbs sampling over unlabeled test entities, parallelized by greedily coloring the hypergraph so that no two same-colored entities share a hyperedge. This generalizes the edge-coloring of the NMLN paper. Any group query is then answered by counting over samples.
Guarding Against Spurious Dependence
Hub-driven artifacts are the main threat to validity. Learning relational probability trees showed that high-degree nodes copy their attributes across many links, so ordinary significance tests mistake one hub's peculiarity for a general pattern. RPTs counter this by shuffling labels while keeping the topology fixed, which builds a null distribution for each split.
We adopt this as a diagnostic instead of a split criterion. We retrain $\phi_\theta$ on label-permuted copies of the training database, with the topology and the encoder's unary terms held fixed. We then measure how much group-level log-likelihood the interaction terms add on held-out data. Real dependence should give a gain well outside the permutation null. If the gain on real data is no larger than on shuffled data, the interaction factors are fitting noise, and the claim fails for that dataset.
Research Program
The work proceeds in three stages. The first stage builds the model on top of an existing RelBench encoder. We use RelGNN, with a heterogeneous GraphSAGE as a fallback. Fact and junction tables are lifted into hyperedges directly from the schema, and $\phi_\theta$ is added on top. The encoder and $\phi_\theta$ are trained jointly by blocked pseudolikelihood.
The second stage defines a group-query suite for each dataset. The suite is chosen before training, and a held-out family of queries is never used for model selection. For rel-trial, queries ask whether any site in a study, or at least a given fraction of sites, succeeds or fails. For rel-amazon and rel-hm, they ask what fraction of a product's or store's customers churn. For UK Biobank, they ask for the probability of two or more diseases within a clinically defined set.
The third stage is a synthetic study in which ground-truth joint distributions are known. Labels are generated on a random hypergraph with planted three-way interactions that have zero pairwise correlation, for example a parity constraint within each hyperedge. Hub sizes vary from bounded to heavy-tailed. This stage separates higher-order from pairwise structure, and it tests the weak-dependence assumption directly.
Baselines
The naive reference point is the encoder alone with group answers formed as products of its marginals. This is the $\phi_\theta = 0$ ablation, and it is what practitioners do today. Its per-entity numbers anchor the requirement that we not lose per-entity accuracy. For rel-trial, Grables reports 0.7009 AUC for LightGBM, 0.6860 for a relational GNN, and 0.7486 for a hybrid of LightGBM with GNN embeddings. RelGNN reports beating GraphSAGE, GAT and GIN on 27 of 30 RelBench tasks, with gains above 4% on 17 of them. We will reproduce the encoder on our splits rather than borrow these numbers, and we will use the identical encoder, data, temporal split and tuning budget inside our model.
The strongest existing method for joint label structure is iterative collective inference in the style of Deep Collective Inference. That method feeds neighbors' predicted labels back as inputs and reports up to 12% error reduction over the best alternative and 25% on average. We implement it on the same encoder by adding predicted co-member labels as features. Group answers again come from products of the refined marginals. It gets the same number of training epochs and the same hyperparameter search as our model.
For UK Biobank, the strongest domain baseline is BHPI. It reports an AUC gain of +1.2 over independent logistic regression on rare diseases and an expected calibration error below 0.01. We will run it on the same cohort split. No reported result was found on Lacuna for group-level calibration on any of these benchmarks, so all group-level baseline numbers will be produced here.
Two ablations isolate the key ingredient. The pairwise ablation tests whether higher-order factors matter, and the no-interaction ablation tests whether any joint model matters. Our model beats a baseline under three conditions. Group-query negative log-likelihood and calibration error must improve on the held-out query family by more than the seed-to-seed spread across five seeds. The interaction gain must lie outside the permutation null. Per-entity AUC must stay within the encoder's seed variance.
Why not just…?
Why not just feed predicted neighbor labels back into the GNN, as collective inference does? This sharpens marginals but still outputs one probability per entity. Any group answer built from those probabilities assumes the members are independent given the inputs. The synthetic parity setting makes the difference explicit: every marginal can be exactly 0.5 while the joint is far from uniform, so no amount of marginal refinement recovers it. On real data the question is empirical, which is why this method is our strongest baseline. If it matches us on group calibration, joint modeling is unnecessary there, and we will report that.
Why not just train a separate model directly on each group-level target? This is a real threat. For a single query fixed in advance, a direct regressor may well win, and we will report that comparison honestly. Our claim is amortization: one joint model answers an open family of queries, such as any threshold, any subset, or any conditioning on observed members, without retraining. The held-out query family tests exactly this. We will report the number of distinct queries at which direct models, each trained under the same total budget, stop being competitive.
Why not just correct the products of marginals with an empirical within-group correlation, for example a Gaussian copula? This is cheap and captures pairwise dependence. It cannot represent interactions that are higher-order but pairwise-uncorrelated, and it uses one correlation value for all hyperedges instead of conditioning on the record's content $h_e$. We include it as a baseline. If it matches our model on the real datasets, that would show real database label dependence is mostly pairwise and homogeneous, which is itself a useful finding.
Why not just use a classical Markov logic network with hand-written rules? Rule writing and clause search are the known bottleneck (Bottom-up learning of Markov logic network structure). Grounding over tables with millions of rows also makes sequential inference impractical. Our potentials are learned, and our sampling is parallel.
Proposed Experiments and Decisive Checks
The first decisive check is synthetic. With planted three-way parity interactions, the full model should recover the true group-query probabilities, while the pairwise ablation, the copula baseline and collective inference should all stay at the independent answer. As hub sizes become heavy-tailed, we expect pseudolikelihood without blocking or size capping to degrade, consistent with the weak-dependence conditions. Blocked training should recover much of the loss.
The second check covers rel-trial, rel-amazon, rel-hm and rel-stack from RelBench, plus UK Biobank. On each, we report group-query negative log-likelihood, Brier score and calibration error on held-out queries, together with per-entity AUC. We also report the permutation-null gap for the interaction terms.
The third check targets the rare-label regime highlighted by BHPI. For UK Biobank diseases with prevalence below 2%, and for rare positive classes in RelBench, the joint model should improve per-entity AUC over the encoder by borrowing strength within hyperedges. This would show the BHPI effect carries over beyond latent pathways.
The proposal would be falsified by either of two outcomes. One is that, on real databases, the copula or collective-inference baselines match group calibration within seed variance. The other is that the learned interaction gain falls inside the permutation null. Either would mean that, for these benchmarks, label dependence beyond what the encoder already captures is too weak or too pairwise to justify a joint model.
References
- Neural markov logic networks
- Disentangling Latent Risk Pathways via Bayesian Hypergraph Inference
- Hypergraph Lifting for Structure Learning in Markov Logic Networks
- RelGNN: Composite Message Passing for Relational Deep Learning
- Grables: Tabular Learning Beyond Independent Rows
- Relational Learning with One Network: An Asymptotic Analysis
- Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph β-Model
- Learning relational probability trees
- Deep Collective Inference
- Bottom-up learning of Markov logic network structure
- RelBench: A Benchmark for Deep Learning on Relational Databases