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:
- Entity-Relationship Databases: Ai-xia Han et al. in Research on Data Mining Model in the Internet of Things utilize SQL-based operations like conditional logic and joins to deformalize structured records into binary target variables and feature vectors.
- Bioinformatics: In Combining Data and Text Mining Techniques for Yeast Gene Regulation Prediction: A Case Study, Mark-A. Krogel et al. show that joining related tables and aggregating interaction data is key to unlocking the predictive potential of biological data for standard data mining algorithms.
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:
- Document Tables: Jay Pujara et al. in A Common Framework for Developing Table Understanding Models convert multi-dimensional, human-oriented table layouts into standardized relational dataframes by resolving cell types and block relationships.
- Clinical Records: In healthcare, data is often stored in deeply nested interoperability formats. Elena Williams et al. address this in A Standardized Clinical Data Harmonization Pipeline for Scalable AI Application Deployment (FHIR-DHP): Validation and Usability Study by flattening hierarchical clinical data standards into a simplified key-value structure, bridging the gap between complex medical records and the flat tensor inputs required by machine learning frameworks.
- Open Data Ecosystems: Automated flattening pipelines, such as those developed by Leo Lahti et al. in Retrieval and Analysis of Eurostat Open Data with the eurostat Package and Jason Anthony Vander Heiden et al. in AIRR Community Standardized Representations for Annotated Immune Repertoires, systematically reduce multi-dimensional statistical and biological structures into standardized "tidy" data frames where each row signifies a single observation.
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:
- Probabilistic Classifiers: Niels Landwehr et al. in nFOIL: Integrating Naïve Bayes and FOIL treat logical clauses as boolean features that indicate the presence or absence of specific structural patterns, allowing symbolic relational information to be processed by standard probabilistic classifiers.
- Linguistic Disambiguation: In USP-IBM-1 and USP-IBM-2: The ILP-based Systems for Lexical Sample WSD in SemEval-2007, Lucia Specia et al. show that converting complex logical patterns discovered in background knowledge into boolean features yields higher accuracy than using pure logic-based decision lists.
- High-Order Dependencies: Tushar Khot et al. in Relational One-Class Classification: A Non-Parametric Approach map complex relational structures into fixed-length feature vectors by extracting logical rules from the paths of a relational decision tree, treating the derived Horn clauses as binary features.
- Structural Analogy: Daniel T. Halstead et al. in Transforming between Propositions and Features: Bridging the Gap bridge this gap by categorizing structured propositional data into existential, characteristic, and continuous features using structural analogy mapping.
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.