PaperlayerView exact revision on arXiv

Source-linked AI summary

Tuffy: Scaling up Statistical Inference in Markov Logic Networks using an RDBMS

Feng Niu, Christopher Ré, AnHai Doan, Jude Shavlik

arXiv:1104.3216v1cs.DB

TL;DR

MLNs combine logical and probabilistic reasoning but existing implementations do not scale to large real-world datasets. Tuffy uses bottom-up RDBMS grounding, hybrid in-memory search, and partitioning techniques to improve scalability. The paper reports better result quality and speed than state-of-the-art implementations across publicly available datasets.

  • Problem

    Current MLN implementations do not scale to large real-world datasets, limiting their use for data-intensive applications.

  • Method

    Tuffy combines bottom-up grounding in an RDBMS, hybrid RDBMS grounding with in-memory search, and partitioning with parallel algorithms.

  • Results

    Tuffy achieves scalability and produces better result quality more quickly while working over larger datasets than state-of-the-art approaches.

  • Takeaways & Limitations

    Partitioning can reduce space and time costs and, under characterized conditions, exponentially improve stochastic local-search efficiency.

  • Takeaways & Limitations

    Fine-grained partitioning increases cut sizes, especially for dense graphs, which can slow the Gauss-Seidel inference scheme.

Abstract

from arXiv · show

Markov Logic Networks (MLNs) have emerged as a powerful framework that combines statistical and logical reasoning; they have been applied to many data intensive problems including information extraction, entity resolution, and text mining. Current implementations of MLNs do not scale to large real-world data sets, which is preventing their wide-spread adoption. We present Tuffy that achieves scalability via three novel contributions: (1) a bottom-up approach to grounding that allows us to leverage the full power of the relational optimizer, (2) a novel hybrid architecture that allows us to perform AI-style local search efficiently using an RDBMS, and (3) a theoretical insight that shows when one can (exponentially) improve the efficiency of stochastic local search. We leverage (3) to build novel partitioning, loading, and parallel algorithms. We show that our approach outperforms state-of-the-art implementations in both quality and speed on several publicly available datasets.

1. INTRODUCTION

MLNs combine logical and probabilistic reasoning for data-intensive applications, but existing implementations struggle with large datasets. Tuffy addresses this through database-backed grounding, hybrid inference, and partitioned search.

  • MLNs combine logical and probabilistic reasoning and support applications including information extraction, entity resolution, and text mining.
  • Existing MLN implementations generally do not scale beyond relatively small datasets and can take hours even on some smaller datasets.In-memory implementations may crash or thrash when intermediate structures exceed main memory.
  • Alchemy spends over 96% of execution time grounding on the RC classification benchmark, motivating Tuffy’s bottom-up grounding strategy.The strategy is designed to exploit the RDBMS optimizer and speed grounding.
  • Tuffy combines RDBMS-based grounding with in-memory local search because database-backed search can perform three to five orders of magnitude fewer steps.The hybrid architecture keeps local search in main memory whenever possible.
  • Partitioning reduces memory use, introduces parallelism, and can exponentially accelerate search when local-search subproblems are independent.The approach includes a sufficient condition for exponential improvement and applies partitioning to arbitrary MLNs.
  • Tuffy’s experiments evaluate whether it achieves better quality more quickly and supports larger datasets than state-of-the-art approaches.

2. PRELIMINARIES

MLNs represent weighted first-order formulas as probability distributions over possible worlds. MAP inference grounds formulas into weighted clauses and searches for a low-cost assignment, commonly using WalkSAT.

  • 2.1 The Syntax of MLNs: An MLN program supplies relations, evidence, and weighted rules to infer unknown labels or other missing data.The sample program classifies papers by area from author, citation, and partial category information.
  • 2.1 The Syntax of MLNs: A soft rule may be violated, with its weight indicating how strongly the rule is expected to hold in a possible world.The example rule assigns weight 5 to favor papers having at most one category.
  • 2.2 MLN Semantics: Grounding substitutes domain constants for formula variables to create weighted ground clauses and atoms.For a formula with m free variables, grounding considers assignments from D^m; each ground clause inherits its formula’s weight.
  • 2.2 MLN Semantics: MLNs define a probability distribution over possible worlds, and MAP inference seeks a most likely world with minimum cost.The paper focuses on MAP inference in the main text while noting that Tuffy also supports marginal inference.
  • 2.2 MLN Semantics: The grounded clauses form a Markov Random Field in which atoms are nodes and clauses are hyperedges.
  • 2.3 MLN Inference: WalkSAT repeatedly selects a random violated clause and flips an atom to search for a low-cost assignment, without guaranteeing optimality.Finding a most likely MLN world generalizes the NP-hard MaxSAT problem.

3. TUFFY SYSTEMS

Tuffy combines RDBMS-based grounding with in-memory search and partition-aware inference to improve scalability, memory use, and search speed. Its partitioning analysis explains when decomposing MLN inference can yield exponential speedups, while also exposing a granularity tradeoff.

  • Grounding: Tuffy uses bottom-up grounding expressed as SQL queries, allowing the RDBMS optimizer to accelerate grounding by orders of magnitude.Predicate relations provide grounding inputs, and SQL joins produce ground-clause atom identifiers and weights.
  • Hybrid architecture: A hybrid architecture retains RDBMS-based grounding while performing WalkSAT search in memory, avoiding the bottleneck of sequential random accesses through the database.Unlike purely in-memory systems, Tuffy needs main memory primarily for search, allowing some workloads to run when prior systems crash.
  • Partitioning: Partitioning reduces memory requirements and introduces parallelism by decomposing grounded MLN graphs into connected components that can be searched and merged independently.Component detection occurs between grounding and search using an in-memory union-find structure over clause-table nodes.
  • Partitioning: Component-aware processing can exponentially accelerate search because independently solving subproblems avoids the difficulty of reaching a global optimum through sequential local-search interactions.For connected components, processing each component individually produces solutions no worse than processing the whole graph at once.
  • Partitioning: Theorem 3.1 bounds the expected advantage of component-aware WalkSAT by at least 2^|H|r/(2+r) steps for suitable component subsets H.The bound applies when |H| ≥ 2 and r(H) > 0.
  • Partitioning: On an information extraction benchmark, |H| = 1196 and r(H) = 0.5 imply a gap of at least 2^200 ≈ 10^60, while fine-grained partitions can enlarge cut sizes and slow Gauss-Seidel inference.Thus partition granularity trades per-partition speed and space efficiency against larger cross-partition cuts.

4. EXPERIMENTS

Experiments on four MLN datasets compare Tuffy with Alchemy and internal variants, showing gains in grounding speed, search efficiency, memory usage, and sometimes solution quality. Ablations further show benefits from bottom-up grounding, hybrid memory management, partitioning, batch loading, and parallelism.

  • Experimental setup: Tuffy and Alchemy were evaluated on four datasets—Link Prediction, Information Extraction, Entity Resolution, and Relational Classification—using 7500-second runs that tracked best-so-far solution cost.Partitioning was applied to Tuffy on the multi-component IE and RC datasets.
  • High-level performance: Tuffy’s RDBMS-based grounding outperformed Alchemy by orders of magnitude, including a 225× runtime advantage on the ER dataset.Sort joins, hash joins, and predicate pushdown were identified as key contributors to the grounding speedup.
  • Effect of hybrid architecture: Tuffy’s memory footprint was no more than 5% of Alchemy’s on every dataset without partitioning.Alchemy’s intermediate grounding state can greatly exceed its final grounding output; on RC it allocated 2.8 GB to produce 4.8 MB of ground clauses.
  • Effect of partitioning: Partitioning reduced memory use and produced significantly better results than Tuffy-p on multi-component MRFs, while also improving search speed.IE was too small to show notable memory differences, but extended experiments continued to show a gap between component-aware search and whole-MRF WalkSAT.
  • Loading and parallelism: 448s versus 117s: batch loading reduced RC processing time for 10^6 search steps per component, and eight threads reduced it further to 28s.These results support contributions from the loading and partitioning algorithms to processing speed.

5. CONCLUSION

Tuffy addresses MLN inference scalability by combining RDBMS-based grounding with in-memory search and partitioning for larger datasets. The paper also describes grounding MLN formulas in SQL and standard local-search and sampling components.

  • System architecture: Tuffy uses an RDBMS for grounding, which performs many relational operations that bottleneck state-of-the-art in-memory MLN implementations.The grounding phase constructs a large weighted SAT formula before search.
  • System architecture: Tuffy combines RDBMS-based grounding with in-memory search to address the differing performance characteristics of the two inference phases.Inference consists conceptually of grounding followed by search for a low-cost assignment.
  • Partitioning: Partitioning enables in-memory search when the dataset does not fit in memory and can produce higher-quality results in less time.The approach is presented as improving both space and time efficiency.
  • Search: WalkSAT repeatedly selects violated clauses and flips atoms randomly or according to the largest cost decrease.The algorithm iterates across multiple random initializations and flip attempts while retaining the lowest-cost assignment.
  • Marginal inference: MC-SAT estimates marginal atom probabilities by repeatedly invoking SampleSAT, which combines simulated annealing with WalkSAT.Tuffy supports marginal inference through this sampling-based procedure.
  • SQL grounding: MLN grounding can be expressed as SQL queries that join predicate tables, constrain truth values, equate shared variables, and enforce constants.Existential quantifiers are supported using PostgreSQL array aggregation.

B.2 Implementing WalkSAT in RDBMS

Implementing WalkSAT inside an RDBMS is difficult because its stochastic local search requires sequential scans and random data access. Tuffy therefore caches atoms in memory while keeping per-clause structures read-only.

  • Access patterns: WalkSAT requires uniformly sampling unsatisfied clauses, random access to atom and clause data, and traversing clauses involving an atom.These operations are difficult to implement efficiently with on-disk data.
  • Access patterns: Each WalkSAT step scans clauses and performs many random atom accesses, creating a mismatch with efficient RDBMS execution.The implementation caches atoms as in-memory arrays and keeps per-clause structures read-only.
  • Performance boundary: Index maintenance and PostgreSQL MVCC overhead prevented the RDBMS implementation from closing the search-speed gap.The authors report that indexing costs often outweighed the benefit of reading less data per step.

B.3 Illustrating Tuffy’s Hybrid Architecture

Tuffy’s hybrid architecture separates memory management across inference phases, using an RDBMS for grounding and in-memory execution for search. The comparison includes RAM-only Alchemy and an all-RDBMS Tuffy variant.

  • Architecture comparison: Alchemy uses RAM for both grounding and search, whereas Tuffy-mm uses an RDBMS for all memory management.These systems provide the two comparison points for Tuffy’s hybrid design.
  • Architecture comparison: Tuffy combines RDBMS-based grounding with in-memory search rather than using one memory system for both phases.This is the hybrid approach described in the architecture comparison.
  • Data structure: Sparse interactions among entities can produce multiple Markov random field components in real-world MLN data.The paper’s paper-classification example yields hundreds of components in the MRF.

B.5 Theorem 3.1

Theorem 3.1 analyzes when decomposing a stochastic local-search problem into independent components can improve runtime exponentially. The paper connects this result to partitioning Markov random fields under size constraints and evaluates it on an example with 1000 components.

  • Theorem statement: H(x) denotes the expected hitting time of an optimal state from x when WalkSAT runs, while f_k is the minimum H(x) over states with k non-optimal components.The proof partitions the state space into sets Q_k according to the number of non-optimal components.
  • Theorem statement: For all k ≤ rN/(r + 2), g_k−1 ≥ 2g_k, yielding f_1 = g_0 ≥ 2^(rN/(r+2)).The result implies exponential expected time for an unpartitioned search to correct the final bit.
  • Implication: An unpartitioned WalkSAT therefore takes an exponential number of expected steps to reach an optimum in the analyzed setting.The theorem concerns search that is not aware of the independent components.
  • Evaluation: The theorem’s gap on Example 1 is at least 2N/3, and Figure 8 compares Alchemy, Tuffy, and unpartitioned Tuffy on 1000 components.The figure is used to illustrate the empirical behavior associated with the theorem.
  • Partitioning: Finding a minimum MRF bisection is hard because Minimum Graph Bisection reduces to minimum bisection of an MRF generated by an MLN of constant size.The reduction establishes hardness even when the MLN program has size O(1).
  • Partitioning: The partitioning heuristic agglomeratively merges atoms while scanning clauses in descending absolute weight order and enforcing a partition-size bound β.It aims to avoid cutting high-weight clauses and returns per-component atom sets.
  • Partitioning: The implementation keeps only a union-find structure in RAM and uses SQL queries for clause assignment and deriving clause partitions.Other partitioning operations are performed in the RDBMS.

B.8 Tradeoff of MRF Partitioning

Partitioning can speed search when it separates sufficiently independent subproblems, but cut clauses can offset the benefit. Tuffy therefore estimates this tradeoff and finds the estimate conservative in experiments.

  • Tradeoff: Partitioning may improve runtime by decomposing a search space into independent subproblems, but large cut sizes can reduce search speed.The tradeoff balances benefits from independent components against slowdown from clauses split across partitions.
  • Tradeoff: The baseline formula estimates partitioning’s benefit or detriment using the number of positive-cost components, WalkSAT steps, and total clauses.Its first term captures speed-up from independent solving, while its second term captures slowdown from cut clauses.
  • Empirical refinement: Experimental results generally favor more aggressive partitioning than the baseline formula predicts.A more detailed model incorporates connectivity and the influence of individual atoms.

C.1 Alternative Search Algorithms

RDBMS-based WalkSAT search is several orders of magnitude slower than in-memory search because local search requires costly random data accesses. Even optimistic caching assumptions leave disk-based search far behind.

  • Performance limitation: RDBMS-based WalkSAT is several orders of magnitude slower than its in-memory counterpart.The gap is consistent with the performance difference between disk I/O and main-memory access.
  • Performance limitation: Even if each flip required only one random 10 ms I/O operation, RDBMS-based search would reach no more than 100 flips/sec.This estimate makes it highly unlikely that disk-based search can catch up with in-memory search.

C.2 Lesion Study of Tuffy Grounding

The grounding lesion study compares full optimization with fixed join order and fixed join algorithm settings. It concludes that access to varied join algorithms is central to Tuffy’s fast grounding.

  • Experimental design: The lesion study compares full optimization, Alchemy’s fixed join order, and nested-loop-only join algorithms.These settings isolate the contribution of query-plan flexibility to grounding time.
  • Experimental design: The experiment measures grounding time in seconds across the three optimizer settings.The results are reported in Table 6.
  • Finding: Various join algorithms are the key contributor to Tuffy’s fast grounding speed.The study’s conclusion identifies join-algorithm flexibility as the principal factor in the comparison.

C.3 Data Loading and Parallelism

Tuffy combines batch loading and parallelism to reduce component-loading overhead and accelerate execution on the IE and RC datasets. The approach builds on WalkSAT and relates to broader grounding and partitioning methods.

  • Experimental design: Tuffy, Tuffy-batch, and Tuffy+parallelism isolate the effects of batch loading and parallelism on IE and RC.All versions use the same WalkSAT parameters and run on an 8-core Xeon machine.
  • Results: Roughly 6time speed up on both IE and RC results from combining batch loading with parallelism.Grounding plus partitioning takes 11 seconds on IE and 35 seconds on RC, while one-by-one loading incurs significant I/O cost.
  • Related methods: WalkSAT is the local-search basis used by Tuffy, while LazySAT applies lazy grounding to WalkSAT in Alchemy.The passage situates Tuffy’s search procedure relative to prior MLN implementations.
  • Related methods: Existing hypergraph partitioning implementations are limited by memory size, motivating Tuffy’s on-disk partitioning algorithm.The cited passage identifies adapting such algorithms to on-disk data as future work and motivation for Tuffy’s design.
  • Broader scope: The grounding-and-search pattern may extend Tuffy’s lessons to probabilistic relational and relational Markov models.The authors express optimism because inference in those frameworks also requires grounding and search.
Loading 1104.3216v1…