PaperlayerView exact revision on arXiv

Source-linked AI summary

MetaSieve: Faster Relational Deep Learning through SQL-Based Metapath Selection

Fahim Shahriar Khan, Ashraf Aboulnaga

arXiv:2608.25903v1cs.DBcs.LG

TL;DR

RDL training can be expensive because sampled neighborhoods grow along many metapaths, not all of which are useful. MetaSieve uses SQL statistics and task labels to prune low-value extensions, reducing training time while maintaining or improving accuracy. Its scope assumes a fixed schema and database snapshot, with standard samplers limiting prefix-aware pruning.

  • Problem

    RDL training cost depends heavily on sampled subgraph size, while many metapaths are irrelevant, rare, or noisy for the task.

  • Method

    MetaSieve computes metapath statistics with SQL and scores candidate extensions using relevance, sampling cost, and coverage before generating pruning rules.

  • Results

    MetaSieve improves training time and accuracy on RelBench, with particularly strong results using the RelGT backbone.

  • Takeaways & Limitations

    The GNN-agnostic selection layer supports classification and regression and complements diverse RDL architectures.

  • Takeaways & Limitations

    MetaSieve assumes a fixed database schema and task definition, while standard samplers may not track prefixes needed for prefix-aware pruning.

Abstract

from arXiv · show

Relational Deep Learning (RDL) is an effective approach to machine learning over multi-table relational databases. In RDL, a database is modeled as a graph in which each row is a node and each foreign-key relation is an edge, and a graph neural network (GNN) is trained on this graph. Training a GNN requires sampling a subgraph around every seed node in the training set, and the cost of training is largely determined by the size of these subgraphs. This paper aims to reduce subgraph size by leveraging the join and aggregation capabilities of relational database systems. We observe that sampled subgraphs are obtained by following metapaths composed of foreign-key links, and that many of these metapaths can be pruned without loss of accuracy. We present MetaSieve, a metapath selection layer that determines which metapaths to retain and which to prune. For each candidate metapath extension, MetaSieve computes statistics via SQL join and aggregation queries and evaluates the extension based on a novel scoring function that prefers lightweight but informative candidates. Metapaths whose scores fall below a threshold are deemed uninformative and pruned. Metapath selection in MetaSieve is lightweight since it relies only on database statistics and task labels, and it is independent of GNN parameters, so it integrates with diverse GNN architectures for classification and regression. Our evaluation on the RelBench benchmark with multiple GNN backbones shows that MetaSieve consistently reduces per-epoch training time by large margins while maintaining and often improving accuracy.

1 INRODUCTION

MetaSieve targets the cost of RDL subgraph sampling by selecting informative metapaths with SQL-derived statistics and task labels. Experiments on RelBench show faster training while often improving accuracy across classification and regression.

  • Motivation: RDL models relational databases as heterogeneous graphs and train GNNs on sampled neighborhoods around labeled seed rows.Each database row becomes a node, while foreign-key links define graph connections.
  • Motivation: Subgraph size and complexity heavily influence GNN training cost because sampling follows foreign-key links across multiple hops.Metapaths are sequences of foreign-key edge types traversed from seed nodes.
  • Problem: Metapath selection prunes irrelevant, rare, or noisy paths that add sampling cost without label-relevant information.The goal is to restrict sampling to useful metapaths.
  • Approach: MetaSieve gathers metapath statistics through SQL queries and scores candidate extensions using task labels, mutual information, fanout, and frequency.The scoring function favors lightweight but informative candidates without requiring graph materialization.
  • Results: Across RelBench datasets, MetaSieve speeds training by up to an order of magnitude versus random sampling and MPS-GNN while often improving accuracy.The evaluation covers both classification and regression and multiple GNN backbones.

2 RELATED WORK

Related work spans RDL architectures and metapath-selection methods. MetaSieve is positioned as a model-agnostic selection layer within this developing area.

  • Metapath selection: Heterogeneous-graph metapath selection methods either learn importance jointly with representations or perform external search and optimization.Examples include attention-based and automatically learned metapath approaches.
  • Relational deep learning: RDL research includes graph-centric toolboxes, public benchmarks, specialized GNNs, transformer backbones, and relational pretraining methods.RelBench broadens evaluation across larger databases and new prediction settings.
  • Metapath selection: RDL-specific methods such as MP-GNN and MPS-GNN differ in how they represent metapath usefulness and aggregate evidence.MPS-GNN addresses the limitation of treating path existence as sufficient evidence.

3 PROBLEM DEFINITION

The problem is to produce compact sampling rules that expand or prune schema-valid metapath extensions for labeled, temporally scoped seed nodes. MetaSieve evaluates path usefulness through occurrence patterns, predictive dependence, support, and sampling cost.

  • Task setup: Each training instance is a labeled seed node with an identifier, timestamp, and task label, and sampling expands from its source table up to a hop limit.Rows with timestamps are restricted to those preceding the task timestamp.
  • Metapaths: A metapath is a schema-valid sequence of forward and reverse foreign-key traversals starting from the seed-node source table.Forward and reverse joins provide the relational interpretation of each traversal.
  • Selection objective: For each prefix and valid next traversal, MetaSieve defines a candidate extension and assigns a rule to expand or prune it.The output is a compact set of sampling rules R.
  • Path usefulness: A metapath’s occurrence pattern varies across seed nodes and can provide predictive evidence when associated with different task labels.Examples include counts of purchases, reviews, visits, or comments.
  • Path usefulness: Schema-valid paths may still lack discriminative signal, so MetaSieve favors paths with label dependence, sufficient coverage, and justified sampling cost.A path reaching one invariant account-type row per user illustrates a low-signal case.

4 METHOD OVERVIEW

MetaSieve enumerates metapaths, computes candidate statistics with batched SQL queries, scores extensions, and converts low-scoring candidates into sampler rules. The resulting sampler produces smaller subgraphs for GNN training.

  • Schema processing: Schema processing enumerates valid metapaths from the seed-node source table through a maximum hop count.Each partial path is a prefix and each next traversal is a candidate extension.
  • SQL statistics: SQL queries compute statistics for each prefix-extension pair over batched training seed nodes without materializing the full graph.Batching divides seed nodes for the computation.
  • Scoring: Candidate scoring combines metapath statistics with labels and frequency to reflect task relevance, sampling cost, and data support.Extensions with low scores are pruned.
  • Sampling rules: Sampling rules specify which candidate extensions are not sampled and are passed to the subgraph sampler.The sampler produces lightweight seed-node subgraphs retaining task-relevant evidence for GNN training.

5 SCHEMA-GUIDED METAPATH ENUMERATION

MetaSieve enumerates schema-valid metapaths from the seed table up to a hop limit, evaluating every valid next-edge extension while excluding immediate backtracking loops.

  • MetaSieve enumerates all schema-valid metapaths from the seed node source table up to maximum hop count H.
  • At each prefix, the schema supplies valid next relation traversals, and MetaSieve evaluates every candidate extension.
  • Immediate reverse-then-forward backtracking is disallowed because it returns to the same node without adding information.

6 METAPATH STATISTICS USING SQL

MetaSieve uses reusable SQL-materialized frontier tables to summarize reachable rows per seed, then derives complementary log-count and log-rate statistics for candidate extensions.

  • MetaSieve materializes one frontier table per metapath prefix and reuses it for all candidate extensions sharing that prefix.
  • Each frontier stores distinct reachable terminal rows per (SeedId, timestamp), with optional foreign-key columns supporting future forward joins.
  • Forward joins require DISTINCT to remove duplicate destinations, whereas reverse joins are already duplicate-free.
  • Temporal predicates restrict joined timestamped rows to those occurring before the seed timestamp.
  • Log-count measures absolute distinct evidence, while log-rate measures expansion relative to the parent frontier.

7 BATCHWISE EVALUATION OF STATISTICS

MetaSieve evaluates candidate extensions across disjoint seed batches, using batchwise statistics to improve stability, scalability, and label-balance handling.

  • Batchwise score distributions identify signals that are stable across repeated subsets and expose candidates that succeed only sporadically.
  • MetaSieve can subsample a label-aware evaluation set and cap seed nodes per label when training data are large or imbalanced.
  • The evaluation seeds are partitioned into approximately equal-sized batches using deterministic SQL NTILE bucketing.
  • Log-count and log-rate are computed separately for each batch and used to score candidate extensions.
  • Disjoint batches can be evaluated concurrently and independently, improving scalability.

8 SCORING CANDIDATE EXTENSIONS

MetaSieve ranks extensions using task dependence, sampling cost, and coverage, then combines batchwise evidence into a conservative quality score for pruning.

  • MetaSieve treats log-count and log-rate as candidate features and measures their dependence on task labels with mutual information.
  • Mutual information provides a model-agnostic, potentially nonlinear relevance proxy that avoids training separate predictive models for each extension.
  • Batchwise MI is estimated separately for log-count and log-rate, using nonparametric k-nearest-neighbor estimators.
  • Entropy normalization accounts for differing label uncertainty across batches, including discretized quantile bins for regression targets.
  • Cost is derived from average recovered path counts, so high-fanout extensions receive lower cost-aware scores.
  • Coverage measures the fraction of training seeds with non-empty extended frontiers, complementing label-dependent relevance with support.
  • The overall quality score combines lower-confidence summaries of batchwise relevance, cost-aware scores, and coverage to favor reliable candidates.

9 GENERATING SAMPLING RULES

MetaSieve converts candidate-extension clusters into pruning rules for neighborhood sampling, while approximating prefix-aware decisions when samplers cannot track traversal prefixes.

  • Pruning-rule generation: MetaSieve marks an extension expand when its extended metapath or any descendant belongs to the good cluster; otherwise, it prunes the extension.This preserves gateways to strong downstream metapaths while removing branches whose extended metapaths and descendants are all bad.
  • Prefix-aware decisions: Pruning rules are prefix-specific: the same candidate can be expanded or pruned depending on which prefix metapath reached it.The sampler must therefore track both the candidate and the prefix that reached the terminal node.
  • Prefix-aware decisions: Standard PyG sampling cannot distinguish prefix-specific cases because it does not track the prefix used to reach each hop.This prevents direct implementation of the generated rules in the standard framework.
  • Prefix-agnostic approximation: MetaSieve approximates prefix-aware rules by pruning an extension for a terminal table whenever any associated prefix rule says prune.PyG is instructed to sample zero neighbors for that candidate while leaving other extensions unchanged.

10 EXPERIMENTS

MetaSieve is evaluated on diverse, large RelBench databases and across sampling strategies and GNN backbones. It consistently reduces training time, often improves accuracy, and has manageable SQL preprocessing and memory controls.

  • Evaluation setting: MetaSieve is evaluated on five RelBench databases spanning diverse domains, schemas, tasks, sizes, and connectivity patterns.Database sizes range from approximately 100K rows for rel-f1 to approximately 21M rows for rel-avito.
  • Evaluation setting: The experiments compare random m-hop sampling, MPS-GNN, and MetaSieve across HeteroGraphSAGE, HGT, and RelGT backbones.Random sampling uses a fixed fanout identically across edge types and hops, whereas MPS-GNN retains ranked metapaths under search constraints.
  • Training efficiency: MetaSieve consistently improves training time across all GNN backbones, with preprocessing remaining reasonable while MPS-GNN is prohibitively expensive.The study uses matched epoch counts across sampling strategies for each dataset and backbone.
  • Scalability: SQL-query memory for frontier materialization grows linearly with frontier size and can be regulated through workers, batch size, or DuckDB spilling.The paper reports that reducing worker threads, increasing seed-node batches, or limiting DuckDB memory can control SQL-query memory.
  • Training efficiency: MetaSieve can exceed 10× speedup over random sampling and MPS-GNN, reducing beer-churn training time with RelGT from days to hours.It is fastest per epoch on all tasks except a few rel-stack cases where MPS-GNN produces smaller subgraphs.
  • Accuracy: MetaSieve and MPS-GNN often improve accuracy because pruning removes typically uninformative metapaths from the training data.The accuracy effect is more pronounced for RelGT, whose fixed context window can be filled with higher-quality sampled tokens.

10.3 Preprocessing Time for Metapath Selection

MetaSieve’s preprocessing is dominated by parallelized SQL processing, yet remains a small fraction of one training epoch. Compared with MPS-GNN, broader metapath search increases preprocessing cost without reliably improving accuracy.

  • MetaSieve preprocessing: SQL processing dominates MetaSieve preprocessing, while statistics computation, scoring, and rule generation take only 5–36 seconds.The remaining preprocessing stages are substantially smaller than SQL execution.
  • MetaSieve preprocessing: MetaSieve’s total preprocessing cost is only a fraction of one RelGT epoch with random neighborhood sampling.This comparison uses RelGT as the strongest backbone and random sampling as the baseline MetaSieve targets.
  • Comparison with MPS-GNN: MPS-GNN is substantially slower than MetaSieve despite using far fewer training and validation samples.MPS-GNN trains a separate GNN at every decision step, motivating its smaller sample sizes.
  • Comparison with MPS-GNN: Increasing MPS-GNN’s search to retain 30 metapaths further increases its already high preprocessing time, sometimes substantially.The broader configuration uses k = 6 and beam_width = 15 to evaluate more than 30 paths.
  • Comparison with MPS-GNN: Retaining 30 rather than 20 MPS-GNN metapaths enlarges sampled subgraphs and can greatly increase epoch time, while accuracy gains are mixed.One task improves substantially, but other tasks show only moderate gains or degradation.
  • Scoring-function ablation: MetaSieve’s full scoring function consistently produces the best accuracy among variants using only log-count, log-rate, or coverage.The ablation supports retaining all components of Q.

10.6 Tuning Hyperparameter 𝛿

The hyperparameter δ affects MetaSieve’s pruning decisions and performance differently across tasks. Validation accuracy is prioritized for selection, with training time used as a secondary criterion when results are close.

  • Effect of δ: Changing δ can leave the GMM split unchanged, producing nearly unchanged epoch time and validation accuracy.This behavior is observed for study-adverse and user-clicks.
  • Effect of δ: Increasing δ can move borderline extensions across the GMM boundary, changing how many metapaths are pruned and altering epoch time.A smaller bad cluster increases time, while a larger bad cluster decreases it; the effect is not monotonic.
  • Selection procedure: MetaSieve selects task-specific δ values using validation accuracy first and time per epoch second when validation results are close.The method may accept a small accuracy degradation when it yields a substantial training-time reduction.
  • Selection procedure: MetaSieve is not overly sensitive to δ, although achieving the best performance requires tuning it.The authors consider δ = 0.2 a reasonable default across tasks.
  • Prefix-aware sampling rules: Overpruning is more likely in highly connected schemas and at greater hop depths because multiple prefixes can converge on the same terminal table.The issue appears in rel-f1 and is more common in rel-stack.
  • Prefix-aware sampling rules: Less aggressive majority and unanimous heuristics retain more graph structure, increasing training time without materially improving predictive accuracy.Across two four-hop rel-stack tasks, accuracy differences are minimal and the default heuristic offers the strongest balance.

10.8 Scalability of SQL Operations

MetaSieve’s SQL-based frontier materialization scales to large databases but creates memory pressure that must be managed. Fewer workers, more seed batches, and lower per-worker memory limits offer complementary trade-offs among memory, disk usage, and runtime.

  • SQL-operation scalability: Frontier materialization time and memory both grow with database size, but the time remains a fraction of an epoch on large rel-ratebeer and rel-avito databases.The scalability analysis focuses on frontier materialization, followed by aggregation for per-seed log-count and log-rate statistics.
  • Single-frontier memory pressure: RSS increases approximately linearly with materialized child rows, with a best-fit slope of 1.01 across six large RelBench tasks.Small-to-medium frontiers often show only 4 KB growth because DuckDB reuses allocated memory, while sufficiently large frontiers require additional memory.
  • Multi-worker execution: Concurrent Peak Child Rows largely determines Global Peak RSS under multi-worker execution, ranging from 16.73 billion rows and 1,040.22 GB for beer-churn to under 10 million rows and near 12 GB for user-badge and user-engagement.Concurrent Peak Child Rows sums simultaneously materialized child-frontier sizes, while Global Peak RSS measures the combined process memory footprint.
  • Regulating memory pressure: Reducing workers lowers concurrent memory pressure but increases wall-clock time, without producing unmanageable runtime jumps in the reported experiments.Fewer workers limit the number of frontier-materialization queries that execute simultaneously.
  • Regulating memory pressure: Increasing seed-node batches reduces frontier sizes, Concurrent Peak Child Rows, and Global Peak RSS while leaving overall runtime nearly unchanged.The total number of seed nodes remains fixed, so additional batches contain fewer seeds and materialize smaller frontiers.
  • Regulating memory pressure: Lowering each worker’s memory limit reduces Global Peak RSS but increases disk spilling and often execution time, making it the most direct option for a small memory budget.Reduced limits also require fewer threads per worker, and DuckDB spills intermediate data to disk under memory pressure.
  • Regulating memory pressure: The three controls let users choose configurations according to available memory, disk capacity and bandwidth, and desired execution time, but batching alone cannot guarantee a memory budget.Increasing batches can reduce memory without increasing execution time, yet it does not directly control memory usage.

11 CONCLUSION

MetaSieve uses SQL-derived statistics and a scoring function combining mutual information, sampling cost, and coverage to prune uninformative metapaths before GNN training. The framework is GNN-agnostic, supports classification and regression, and improves training time and accuracy on RelBench, while schema changes require rerunning selection.

  • Contribution: MetaSieve prunes uninformative metapaths before GNN training using lightweight SQL-derived statistics and a score combining mutual information, sampling cost, and coverage.The selection layer leverages relational database operations rather than requiring graph materialization.
  • Scope: Because it uses only database statistics and task labels, MetaSieve is GNN-agnostic and supports both classification and regression within one framework.The framework supports temporally scoped prediction under a fixed schema and task definition.
  • Results: RelBench experiments show improved training time and accuracy, with especially strong gains on RelGT, complementing strong GNN architectures.The conclusion reports benefits across the evaluated benchmark rather than for a single task alone.
  • Limitation: Adding or removing tables or foreign-key relationships changes the metapath search space, so MetaSieve must be rerun on the updated schema and data snapshot.Incremental maintenance of sampling rules under schema evolution remains future work, although periodic reruns were practical for the evaluated tasks.
Loading 2608.25903v1…