Mapping Relational Structures to Flat Feature Vectors

26 concepts19 papers

The core algorithms of modern machine learning—from naive Bayes and decision trees to deep neural networks—share a fundamental assumption: they expect data to arrive as a single, flat table. In this standard "attribute-value" format, each row represents an independent observation, and each column represents a fixed, distinct feature.

However, real-world data rarely conforms to this clean, tabular ideal. Instead, it lives in relational databases, nested hierarchical documents (like JSON or XML), biological networks, and complex systems of formal logic. Forcing these rich, interconnected structures into flat feature vectors creates a severe technical challenge. As noted by Jesse Davis et al. in LazyBum: Decision tree learning using lazy propositionalization, real-world data is inherently distributed across multiple tables, making transformation a necessary but computationally intensive prerequisite for standard statistical learners.

This transformation process is known as propositionalization. Rather than rewriting machine learning algorithms to natively handle graphs or logic, propositionalization systematically flattens relational data into independent propositions or features. This approach allows engineers to decouple structural representation from statistical inference, unlocking the full power of standard optimization frameworks.


The Mechanics of Structural Aggregation

How do you compress an entire database schema or a complex graph neighborhood into a single row of numbers? The most direct method relies on relational algebra and structural aggregation.

When dealing with one-to-many or many-to-many relationships, a single target entity (such as a customer or a gene) may be linked to an arbitrary number of related records. To flatten this structure, we must summarize the local neighborhood. Jennifer Neville et al. demonstrate this mechanism in Learning relational probability trees, showing how networked dependencies can be flattened by applying aggregation functions—such as counts, averages, or existence checks—to the attributes of neighboring nodes in a subgraph.

Relational Graph                  Aggregation                 Flat Feature Vector
[User A] --(buys)--> [Item 1]     ===> Count purchases  ===>  [User A: Purchase_Count = 3]
         --(buys)--> [Item 2]     ===> Check existence  ===>  [User A: Bought_Item_3 = False]
         --(buys)--> [Item 4]

This strategy is widely applicable across diverse domains:

Flattening Hierarchies and Layouts

A parallel challenge occurs when data is trapped in human-centric layouts or deeply nested hierarchical standards. In these cases, propositionalization acts as a structural parser:


Logic-Based Propositionalization

While numerical aggregation works well for continuous variables, it struggles to capture complex, symbolic, or rule-based interactions. To solve this, researchers leverage symbolic logic to discover structural patterns, converting those patterns into boolean (true/false) signals.

The theoretical foundation for this approach was established by Roni Khardon et al. in Relational Learning for NLP using Linear Threshold Elements. The authors demonstrated that relational reasoning can be effectively executed by fast propositional learners if first-order logic atoms and quantified predicates are mapped into binary features. This transformation grants statistical models the expressive power of symbolic logic without requiring a computationally heavy symbolic reasoning engine during inference.

First-Order Logic Patterns                           Binary Feature Vector
Clause 1: ∃x (Parent(x, y) ∧ Male(x))       ===>     [Feature 1 (Has_Father): 1]
Clause 2: ∃x,z (Friend(y, x) ∧ LivesIn(x, z)) ===>     [Feature 2 (Has_Local_Friend): 0]

This hybrid approach allows statistical classifiers to ingest deep background knowledge that they cannot natively process:


Why It Works: Decoupling Search from Inference

The primary reason propositionalization works so well is that it separates feature discovery from statistical inference.

Pure relational learning frameworks (such as Inductive Logic Programming) must simultaneously navigate two difficult spaces: the combinatorial space of potential graph structures or logical rules, and the continuous space of statistical parameters or weights. This simultaneous optimization is computationally brutal.

Propositionalization splits these responsibilities. The relational structure is analyzed to generate a static or dynamic set of features. Once the data is flattened, standard statistical models can optimize parameters efficiently because they no longer have to worry about the underlying graph topology.

Interleaving and Lazy Construction

To prevent a combinatorial explosion of features when generating rules upfront, modern frameworks interleave feature construction directly with model training.

For instance, Jesse Davis et al. introduced the SAYU (Score As You Use) framework in An Integrated Approach to Learning Bayesian Networks of Rules. Instead of generating a massive, noisy pool of features beforehand, the system interleaves rule learning with classifier construction, only retaining new propositional features if they directly improve the statistical score of a Bayesian Network classifier.

Similarly, the lazy propositionalization approach developed by the authors in LazyBum constructs relational features on-demand while growing a decision tree. By evaluating features dynamically at the splits rather than statically at the beginning, it eliminates feature noise and dramatically accelerates training times.

Ultimately, platforms like the one proposed by Mattia Fumagalli et al. in LiveSchema: A Gateway to Relational Data Analysis and Transformation act as essential gateways. By transforming raw knowledge representations and ontologies into formats optimized for machine learning, propositionalization provides a practical, scalable bridge between the expressive complexity of relational data and the optimization power of flat statistical models.

Key Foundational Work

Relational Learning for NLP using Linear Threshold Elements (1999) — contributed 2 concept elements to this direction.
Building Intelligent Learning Database Systems (2000) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_relational_to_propositional_mapping_dcfbe937,
  title = {relational-to-propositional mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-to-propositional-mapping/rdr_dcfbe937619a4a5cad437c80d556da50},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_relational_to_propositional_mapping_dcfbe937_v1,
  title = {relational-to-propositional mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-to-propositional-mapping/rdr_dcfbe937619a4a5cad437c80d556da50/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}

See something wrong? Report a mistake