Sparse Probabilistic Graph Circuits
This addresses scalability for tractable generative models in domains like drug design, but it is incremental as it builds on existing PGCs.
The paper tackled the scalability issue of Probabilistic Graph Circuits (PGCs) by introducing Sparse PGCs, which reduce complexity from O(n^2) to O(n + m) for sparse graphs, and demonstrated in drug design that they retain exact inference, improve efficiency, and match intractable deep generative models in performance.
Deep generative models (DGMs) for graphs achieve impressively high expressive power thanks to very efficient and scalable neural networks. However, these networks contain non-linearities that prevent analytical computation of many standard probabilistic inference queries, i.e., these DGMs are considered \emph{intractable}. While recently proposed Probabilistic Graph Circuits (PGCs) address this issue by enabling \emph{tractable} probabilistic inference, they operate on dense graph representations with $\mathcal{O}(n^2)$ complexity for graphs with $n$ nodes and \emph{$m$ edges}. To address this scalability issue, we introduce Sparse PGCs, a new class of tractable generative models that operate directly on sparse graph representation, reducing the complexity to $\mathcal{O}(n + m)$, which is particularly beneficial for $m \ll n^2$. In the context of de novo drug design, we empirically demonstrate that SPGCs retain exact inference capabilities, improve memory efficiency and inference speed, and match the performance of intractable DGMs in key metrics.