提出稀疏概率图电路，实现高效精确的图生成与推理。
Sparse Probabilistic Graph Circuits
- 基于稀疏图表示，将复杂度从O(n²)降至O(n+m)
- 在药物分子生成中保持与不可行模型相当的性能
- 适合大规模稀疏图数据，提升内存与速度效率
图的深度生成模型虽具强大表达能力，但因非线性结构导致标准概率推断不可计算。最近提出的概率图电路（PGC）虽实现可计算推断，但依赖稠密图表示，复杂度为O(n²)，对大图不友好。本文提出稀疏概率图电路（SPGC），直接处理稀疏图表示，将复杂度降至O(n + m)，尤其适用于边数远小于节点数平方的情况。在从头药物设计任务中，实验表明SPGC保留精确推断能力，显著提升内存效率与推理速度，且关键指标表现与不可行的DGMs相当。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。