Memory-Efficient Inference in Relational Domains

Parag Singla, Pedro M. DomingosAAAI 2006

Abstract

Relational domains, characterized by objects and their complex interrelationships, present a significant challenge for Boolean satisfiability (SAT) solvers. The standard process of propositionalization often leads to a "memory wall," where the number of generated clauses grows exponentially, exhausting available RAM. This paper presents LazySAT, a memory-efficient variant of the WalkSAT algorithm. By leveraging the extreme sparseness of real-world relational data—where most relations are false and most rules are trivially satisfied—LazySAT materializes atoms and clauses only as they become relevant to the search. Experimental results demonstrate that LazySAT can reduce memory usage by orders of magnitude without compromising solution quality or execution speed.

Introduction: The Memory Wall in Relational AI

In Artificial Intelligence, relational domains involve modeling objects and the predicates that define their interactions (e.g., Author(person, paper)). To utilize the power of modern SAT solvers, these domains are typically "propositionalized," converting every possible relationship into a Boolean variable and every rule into a set of propositional clauses.

However, this approach scales poorly. For $n$ objects and a rule involving $r$ variables, the number of clauses scales at $O(n^r)$. In large-scale datasets, such as scientific citation databases, this leads to an exponential explosion in memory requirements. For instance, while a person only authors a few papers, the solver might ground every possible person-paper combination, most of which are false. This "memory wall" often prevents solvers from even beginning the search process.

Methodology: Lazy Grounding with LazySAT

LazySAT addresses the memory bottleneck by implementing a "lazy" version of the WalkSAT algorithm. Unlike standard WalkSAT, which grounds all possible clauses upfront, LazySAT only materializes variables and clauses on-the-fly. It maintains two dynamic sets:

  1. Active Atoms: Boolean variables that are either true in the initial state or have been modified (flipped) during the search.
  2. Active Clauses: Clauses that are potentially unsatisfied given the current set of active atoms.

As the search progresses, LazySAT "activates" new atoms and clauses as they become relevant. Because relational data is typically sparse, the vast majority of clauses remain "trivially satisfied" and are never stored in memory. This approach ensures that memory consumption scales with the complexity of the search path rather than the total size of the potential state space. Crucially, LazySAT is mathematically guaranteed to produce the same results as WalkSAT for a given random seed.

Experimental Evaluation

The effectiveness of LazySAT was evaluated on two primary tasks: Entity Resolution (de-duplication) and Planning.

Blocks World Planning

In the classic Blocks World domain, the goal is to find a sequence of moves to achieve a specific stack configuration. Standard WalkSAT quickly hits the memory wall as the number of blocks increases.

Scaling in Blocks World: Clause count vs. blocks (left) and flips per second (right).

As shown in Figure 1, WalkSAT's memory usage (represented by the number of clauses) explodes as the number of blocks reaches 50, requiring approximately 1.6 GB of RAM. In contrast, LazySAT handles the same problem with only 203 MB and continues to scale linearly.

Entity Resolution

The authors also tested LazySAT on citation databases (Cora and BibServ) to identify duplicate entities.

Scaling in Entity Resolution: Clause count vs. records (left) and flips per second (right).

On the Cora dataset, LazySAT achieved an order-of-magnitude reduction in memory. For the larger BibServ dataset, projections indicated that LazySAT would reduce memory usage by a factor of over 400,000 compared to standard WalkSAT. Despite the overhead of just-in-time grounding, LazySAT's performance (flips per second) remained competitive with WalkSAT, and in some cases, was faster due to the avoidance of massive initial grounding overhead.

Discussion and Future Work

The primary insight of this work is that the "curse of dimensionality" in relational domains is mitigated by sparseness. By treating sparseness as a feature, LazySAT enables inference in domains previously considered unreachable.

However, some limitations remain. Currently, LazySAT does not "deactivate" atoms, meaning memory usage grows monotonically over time. Future work could involve periodic re-initialization of active sets to reclaim memory. Additionally, the lazy grounding approach could be extended to other inference methods, such as Markov Chain Monte Carlo (MCMC) for probabilistic reasoning in Markov Logic Networks.

Summary updated

BibTeX
@inproceedings{singla2006memory,
  author = {Parag Singla and Pedro M. Domingos},
  title = {{Memory-Efficient Inference in Relational Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure