# Inference for Probabilistic Dependency Graphs

arXiv: https://arxiv.org/abs/2311.05580 · HTML: https://mlsanity.com/paper/2311.05580/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 32 references that are in the map.
- First posted on arXiv 9 Nov 2023.

## Builds on (most cited first, 8 of 8)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Faster Matrix Multiplication via Asymmetric Hashing](https://mlsanity.com/paper/2210.10173/) (2022)
- [Loss as the Inconsistency of a Probabilistic Dependency Graph: Choose Your Model, Not Your Loss Function](https://mlsanity.com/paper/2202.11862/) (2022)
- [Probabilistic Dependency Graphs](https://mlsanity.com/paper/2012.10800/) (2020)
- [An Algorithm for Nonsymmetric Conic Optimization Inspired by MOSEK](https://mlsanity.com/paper/2003.01546/) (2020)

## Built on by (most cited first, 1 of 1)

- [Local Inconsistency Resolution: The Interplay between Attention and Control in Probabilistic Models](https://mlsanity.com/paper/2604.17140/) (2026)

## Abstract (arXiv)

Probabilistic dependency graphs (PDGs) are a flexible class of probabilistic graphical models, subsuming Bayesian Networks and Factor Graphs. They can also capture inconsistent beliefs, and provide a way of measuring the degree of this inconsistency. We present the first tractable inference algorithm for PDGs with discrete variables, making the asymptotic complexity of PDG inference similar that of the graphical models they generalize. The key components are: (1) the observation that, in many cases, the distribution a PDG specifies can be formulated as a convex optimization problem (with exponential cone constraints), (2) a construction that allows us to express these problems compactly for PDGs of boundeed treewidth, (3) contributions to the theory of PDGs that justify the construction, and (4) an appeal to interior point methods that can solve such problems in polynomial time. We verify the correctness and complexity of our approach, and provide an implementation of it. We then evaluate our implementation, and demonstrate that it outperforms baseline approaches. Our code is available at http://github.com/orichardson/pdg-infer-uai.