Technical Summary: FROG – Full-Resolution and Optimizable Graph Structure Learning for Relational Deep Learning

1. Problem Statement

Relational Deep Learning (RDL) aims to perform end-to-end predictive modeling on Relational Databases (RDBs) by representing them as graphs and applying Graph Neural Networks (GNNs). However, existing RDL methods typically adhere to a sequential pipeline: they first construct a Relational Entity Graph (REG) based on a fixed Schema Graph and then train a GNN on this static structure.

The authors identify a critical limitation in this paradigm: fixing the schema graph constrains the information accessible during message passing, potentially hiding implicit, high-order, or task-specific relations. This raises the central question: "Is Fixing Schema Graphs Necessary?"

The challenge lies in optimizing the graph structure without violating two fundamental properties of RDBs:

1. Full-Resolution Property: The graph must faithfully encode every entity and foreign-key link in the RDB. Traditional Graph Structure Learning (GSL) methods that prune or add edges violate this property because they lose information required to uniquely recover the original RDB state.
2. Functional Dependencies (FDs): RDBs contain intrinsic constraints where one entity uniquely determines another (e.g., a review ID uniquely determines a customer ID). Standard GSL approaches often ignore these semantic constraints, leading to representations that violate the database's logical integrity.

Current attempts, such as RDB2G, explore different schema graph constructions but rely on discrete role selection and empirical comparison rather than end-to-end optimization.

2. Methodology: The FROG Framework

The authors propose FROG (Full-Resolution and Optimizable Graph Structure Learning), a framework that treats graph structure learning as a learnable table role modeling problem. Instead of modifying edges directly, FROG optimizes the roles tables play (as nodes or edges) within the schema graph.

2.1. Full-Resolution via Table Roles

FROG reinterprets graph structure learning by allowing tables to function as either nodes or edges in the Schema Graph.

• Theoretical Guarantee: The authors prove (Theorem 4.1) that adaptive mapping, where tables are assigned to either a "Table-as-Node" or "Table-as-Edge" role, satisfies the full-resolution property. This is because the mapping preserves all attributes, foreign-key directions, and entity types, allowing the original RDB to be uniquely recovered from the graph.
• Information-Theoretic Advantage: The paper demonstrates (Theorem 4.2) that modeling a table as an edge (Table-as-Edge) can retain strictly more information about source entities than modeling it as a node (Table-as-Node). In a Table-as-Node scenario, information must pass through two aggregation steps ($u \to v \to w$), potentially introducing information loss. In a Table-as-Edge scenario, the intermediate table acts as a direct edge, allowing the target to access source information in a single step ($u \xrightarrow{v} w$), avoiding intermediate aggregation bottlenecks.

2.2. Relation-Driven Message Passing

To handle the complexity of tables acting as edges, FROG introduces specific message-passing mechanisms for two relational paradigms:

1. Co-Occurrence ($u \leftarrow v \rightarrow w$): Models symmetric roles where $u$ and $w$ appear together in $v$ (e.g., User $\leftarrow$ Review $\rightarrow$ Product). The message aggregates features from $u$, $v$, and $w$ to capture joint co-occurrence.
2. Completion ($u \rightarrow v \rightarrow w$): Models a mediated relationship where $v$ modulates the influence of $u$ on $w$ (e.g., Standing $\rightarrow$ Race $\rightarrow$ Circuit). The message uses a gating mechanism to modulate the influence of the intermediate entity.

A role-aware gating model ($M_{att}$) is employed to adaptively balance the information flow from Table-as-Node and Table-as-Edge paths. This gate is smoothed using an Exponential Moving Average (EMA) to stabilize training, allowing the model to learn the optimal role for each table under specific relations.

2.3. Functional Dependency (FD) Constraints

To ensure the learned representations respect the semantic constraints of the RDB, FROG introduces a Functional Dependency Loss ($\mathcal{L}_{FD}$) optimized in an alternating manner with the GNN. This loss operates at two levels:

• Table-Level ($\mathcal{L}_{emb}$): Regularizes the embedding space by enforcing that the difference vectors between entities linked by the same table relation lie in a shared low-dimensional subspace. This captures consistent transformation patterns across the table.
• Entity-Level ($\mathcal{L}_{pair}$): Uses a contrastive objective (InfoNCE) to ensure that entity pairs satisfying a functional dependency (positive pairs) are scored higher than those that do not (negative pairs).

The total loss is defined as $\mathcal{L}_{main} = \mathcal{L}_{task} + \beta\mathcal{L}_{emb} + \gamma\mathcal{L}_{pair}$.

3. Key Contributions

1. Full-Resolution Graph Structure Learning: The paper is the first to introduce GSL into RDL while strictly preserving the full-resolution property. It formalizes this from an information-theoretic perspective and proves that pruning or adding edges violates this property, whereas optimizing table roles does not.
2. Adaptive Table Role Modeling: The framework optimizes table roles (Node vs. Edge) in a learnable, continuous manner rather than through discrete selection. It provides a theoretical basis for why Table-as-Edge modeling can be superior for retaining long-range dependencies.
3. FD-Constrained Embedding Space: The design of the FD loss ($\mathcal{L}_{FD}$) ensures that the learned graph representations inherently respect the functional dependencies and structural constraints of the underlying RDB.
4. Comprehensive Empirical Validation: Extensive experiments on the RelBench benchmark (6 datasets, 23 tasks) demonstrate that FROG outperforms existing baselines, including statistical methods, LightGBM, and state-of-the-art RDL models like RelGNN.

4. Experimental Results

The authors evaluated FROG on 23 downstream tasks across 6 real-world datasets (e.g., rel-avito, rel-event, rel-hm, rel-trial).

• Performance: FROG achieved state-of-the-art or competitive results across Entity Classification, Regression, and Recommendation tasks. For instance, on the user-repeat task (rel-event), FROG achieved a ROC-AUC of 79.11, outperforming RelGNN (78.15) and RDL (75.90).
• Ablation Studies:
  • Role Modeling: The study confirmed that the optimal role (Node vs. Edge) varies by task and dataset. However, the adaptive learning approach consistently outperformed fixed strategies (all-node or all-edge), validating the necessity of structure optimization.
  • FD Constraints: Removing the FD loss components ($\mathcal{L}_{emb}$ and $\mathcal{L}_{pair}$) led to performance degradation in most tasks, confirming that enforcing functional dependencies improves representation quality.
• Structural Insights: Analysis of the learned structures revealed that intermediate tables in Co-Occurrence paradigms tend to be modeled as nodes for classification/regression but as edges for link prediction. Furthermore, learned structures showed transferability across tasks, suggesting the model captures shared structural characteristics.

5. Significance and Claims

The paper claims to offer a new perspective on graph construction for RDL. By challenging the necessity of fixed schema graphs, FROG demonstrates that graph structures can and should evolve jointly with GNN representations to better capture relational semantics.

The authors emphasize that their approach is not merely a performance improvement but a methodological shift:

• It resolves the tension between optimizing graph structure and preserving data integrity (full-resolution and FDs).
• It provides a theoretical foundation for Table-as-Edge modeling, showing its information-theoretic advantage over traditional node-based aggregation.
• It offers a framework where the "schema" is no longer a static input but a learnable component that adapts to the specific relational patterns required by downstream tasks.

The work concludes that while FROG incurs higher computational costs due to two-hop path calculations, the gains in modeling complex relational dependencies justify the overhead, particularly for tasks involving multi-hop interactions.