On Projectivity in Markov Logic Networks

Sagar Malhotra, Luciano SerafiniECML/PKDD 2022 · OpenReview

TL;DR

This paper tackles the challenge of making Markov Logic Networks (MLNs) generalize well across different domain sizes, a common issue in relational learning. They introduce a precise characterization of "projective" MLNs in a simplified two-variable setting, identifying a special model called the Relational Block Model (RBM) that achieves optimal learning performance and consistent parameter estimation regardless of domain size.

What Problem Does This Paper Address?

Relational learning models, like Markov Logic Networks (MLNs), are powerful for representing complex relationships in data. However, a significant problem arises when these models need to operate on or be learned from data with varying numbers of entities (domain sizes). MLNs, in their standard form, suffer from "domain size dependence," meaning that inferences and learned parameters can change drastically if the number of objects in the domain changes. This makes models trained on one domain size unreliable for others. This issue is particularly problematic for learning from sub-sampled data, where the training domain might be much smaller than the target inference domain. The concept of "projectivity" has emerged as a desirable property for relational models, ensuring that marginal probabilities are independent of the domain size, thus enabling consistent inference and learning across different scales. However, characterizing projectivity for rich models like MLNs has been an open challenge.

Methods

The authors focus on the two-variable fragment of First-Order Logic (FO2) for MLNs. This simplification allows for a tractable analysis. They first establish a parametric normal form for these FO2 MLNs, rewriting them in terms of parameters related to 1-types (properties of single entities) and 2-tables (relationships between pairs of entities).

The core of their contribution lies in deriving necessary and sufficient conditions for projectivity within this FO2 fragment. These conditions are expressed in terms of the equality of certain parameters derived from the 2-tables.

They then introduce and analyze the Relational Block Model (RBM), a specific type of projective MLN. They demonstrate that RBMs are not only projective but also uniquely characterize the probability distributions of projective MLNs in the FO2 fragment.

Finally, they explore maximum likelihood learning for these projective MLNs and RBMs, showing that RBMs offer superior performance in terms of data likelihood maximization and admit consistent parameter estimation even from sub-sampled domains.

Datasets

Not discussed in the paper. The paper focuses on theoretical characterization and algorithmic properties rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Projectivity is key for domain generalization: The paper solidifies the importance of projectivity for building robust relational models that can handle varying domain sizes, a crucial aspect for real-world applications where data scales can change.
  • FO2 fragment is tractable for projectivity analysis: By restricting to two variables, the authors unlock a precise characterization of projectivity, which is significantly harder for full FOL.
  • Relational Block Model (RBM) as the "ideal" projective model: The RBM emerges as a special, highly desirable class of projective MLNs. It's not just projective but also uniquely represents the distributions of all projective MLNs in the FO2 fragment.
  • RBMs offer optimal learning: In terms of maximizing data likelihood, RBMs are shown to be the best possible projective MLNs in the two-variable setting. This is a strong claim for practical model selection.
  • Consistent learning from sub-sampled data: A major practical benefit highlighted is that RBMs allow for consistent parameter estimation even when trained on smaller domains, making them suitable for large-scale or incomplete data scenarios.

Key Results

  • Characterization of Projectivity: The paper provides a precise set of necessary and sufficient conditions for an MLN in the two-variable fragment to be projective, expressed as equality constraints on parameters related to 2-tables ($f_{ij} = f_{i'j'}$).
  • RBM as a unique representation: Any projective MLN in the FO2 fragment can be expressed as an RBM, and conversely, any RBM corresponds to a projective MLN.
  • RBMs maximize likelihood: For a given dataset, an RBM achieves the highest possible likelihood among all projective MLNs in the two-variable fragment.
  • Consistent parameter estimation: RBMs admit consistent parameter learning from sub-sampled domains, a critical property for scalability.

Limitations and Future Work

  • Two-Variable Fragment: The primary limitation is that the characterization and results are specific to the two-variable fragment of FOL. Extending these findings to MLNs with more variables or full FOL remains an open challenge.
  • Comparison to σ-determinate MLNs: The paper shows that their characterization of projectivity is strictly more expressive than the σ-determinate MLNs proposed by Jaeger and Schulte [4], but it doesn't fully explore the spectrum of projective models beyond this.
  • Future Work: The authors suggest investigating the capabilities of RBMs and projective MLNs in future work, particularly in comparison to adaptive MLNs and domain-size aware MLNs. They also aim to generalize their work to capture complete projectivity criteria for all MLNs, not just the two-variable fragment. The theoretical resemblance to AHK models is also noted as a direction for future research.

Summary updated

Abstract

Markov Logic Networks (MLNs) define a probability distribution on relational structures over varying domain sizes. Many works have noticed that MLNs, like many other relational models, do not admit consistent marginal inference over varying domain sizes. Furthermore, MLNs learnt on a certain domain do not generalize to new domains of varied sizes. In recent works, connections have emerged between domain size dependence, lifted inference and learning from sub-sampled domains. The central idea to these works is the notion of projectivity. The probability distributions ascribed by projective models render the marginal probabilities of sub-structures independent of the domain cardinality. Hence, projective models admit efficient marginal inference, removing any dependence on the domain size. Furthermore, projective models potentially allow efficient and consistent parameter learning from sub-sampled domains. In this paper, we characterize the necessary and sufficient conditions for a two-variable MLN to be projective. We then isolate a special model in this class of MLNs, namely Relational Block Model (RBM). We show that, in terms of data likelihood maximization, RBM is the best possible projective MLN in the two-variable fragment. Finally, we show that RBMs also admit consistent parameter learning over sub-sampled domains.
BibTeX
@inproceedings{malhotra2022projectivity,
  author = {Sagar Malhotra and Luciano Serafini},
  title = {{On Projectivity in Markov Logic Networks}},
  booktitle = {ECML/PKDD},
  year = {2022},
  url = {https://openreview.net/forum?id=FN1SEusg8Nf},
}
Figure