Sparse Probabilistic Graph Circuits

2025/08/11 by Martin Rektoris, Rektoris, Martin, Milan Papež +5
Computer Science · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2508.07763

openalex publication_date 2025/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 intractable. While recently proposed Probabilistic Graph Circuits (PGCs) address this issue by enabling tractable probabilistic inference, they operate on dense graph representations with O(n²) complexity for graphs with n nodes and 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 O(n + m), which is particularly beneficial for m ≪ n². 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.

Citations

• Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs
• GraphSPNs: Sum-Product Networks Benefit From Canonical Orderings
• Sum-Product-Set Networks: Deep Tractable Models for Tree-Structured Graphs
• Large Generative Graph Models
• Autoregressive Diffusion Model for Graph Generation
• DIFFRACTION—Spectral Conditioning and N-Boundary Interference Modeling in Modern Runtime Systems
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations
• GraphDF: A Discrete Flow Model for Molecular Graph Generation
• GraphEBM: Molecular Graph Generation with Energy-Based Models
• Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic\n Circuits
• Permutation Invariant Graph Generation via Score-Based Generative Modeling
• Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models
• Fréchet ChemNet Distance: A metric for generative models for molecules in drug discovery

Related

• Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs
• Scalable Deep Generative Modeling for Sparse Graphs
• Building Expressive and Tractable Probabilistic Generative Models: A Review
• Sparse Probabilistic Circuits via Pruning and Growing
• Improving Graph Generation by Restricting Graph Bandwidth