Abstract: 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 PDG inference can be reduced to convex optimization with exponential cone constraints, (2) a construction that allows us to express these problems compactly for PDGs of bounded treewidth, for which we needed to further develop the theory of PDGs, and (3) an appeal to interior point methods that can solve such problems in polynomial time. We verify the correctness and time 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.
Introduction
Probabilistic Dependency Graphs (PDGs) are a powerful generalization of Bayesian Networks (BNs) and Factor Graphs (FGs) that can handle inconsistent or conflicting data. While traditional models assume a single, consistent joint probability distribution, real-world data often provides conflicting conditional probabilities. PDGs treat inference as an optimization problem—finding the distribution that is "closest" to the provided information. However, until now, PDGs lacked an efficient inference algorithm, remaining largely a theoretical curiosity due to the exponential computational cost of previous approaches. This paper introduces the first tractable inference algorithm for PDGs, reducing the problem to a convex optimization task that runs in polynomial time for graphs with bounded treewidth.
Methodology
The proposed approach bridges the gap between PDG theory and practical application through three main pillars:
- Convex Optimization Framework: Inference is framed as minimizing a loss function balancing observational data and structural dependencies.
- Exponential Conic Programming: Non-linear loss functions involving entropy are mapped onto exponential cones, allowing the use of efficient modern solvers like MOSEK.
- Exploiting Graph Structure: By proving a Markov Property for PDGs, the authors utilize tree decompositions to break large graphs into smaller cliques. This reformulates global optimization into local constraints, ensuring polynomial complexity in time and space.
Experimental Setup
The algorithm was evaluated using synthetic PDGs (randomly generated graphs with approximately 10 variables and 15 arcs) to compare accuracy and speed against black-box optimization baselines. Additionally, the authors used the bnlearn repository of standard Bayesian Network benchmarks (e.g., "Alarm" and "Asia") to verify correctness against traditional models.
Theoretical Contributions
A major contribution is the proof that PDGs satisfy the same conditional independence properties as standard graphical models (the Markov Property). This validates the "clique tree" approach. Additionally, the authors developed a method to decompose total entropy into a sum of local cluster entropies, allowing optimization to remain local to the clusters in the tree decomposition.
Results and Discussion
The algorithm achieves a complexity of $O(\tilde{N}^4)$ for graphs with bounded treewidth, representing the first practical inference method for this class. Experiments demonstrate that the convex optimization approach is significantly more accurate and faster than gradient-based optimizers like Adam or L-BFGS.
As illustrated in Figure 1, gradient methods struggle to satisfy strict calibration constraints, whereas the conic solver handled them natively. The method also proves more stable for small values of $\gamma$, where numerical difficulty typically increases. The right panel of the figure confirms the predictable scaling of the proposed methods compared to the more erratic behavior of baseline optimizers.
Conclusion and Future Work
While the current algorithm is limited to discrete variables and has a polynomial overhead of $O(N^4)$, it marks a significant step toward making PDGs a usable tool. Future work includes extending the framework to continuous variables and further optimizing matrix multiplication steps to reduce the computational exponent to approximately 2.87.
Summary updated