Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy

• URL: http://arxiv.org/abs/2601.04456v1
• Date: Thu, 08 Jan 2026 00:03:11 GMT
• Title: Categorical Belief Propagation: Sheaf-Theoretic Inference via Descent and Holonomy
• Authors: Enrique ter Horst, Sridhar Mahadevan, Juan Diego Zambrano,
• Abstract summary: We develop a categorical foundation for belief propagation on factor graphs.<n>Message-passing is formulated using a Grothendieck fibration (int to catFG_) over polarized factor graphs.<n>We introduce HATCC, an algorithm that detects descent obstructions via holonomy on the factor nerve.
• Score: 1.001355398440049
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a categorical foundation for belief propagation on factor graphs. We construct the free hypergraph category \(\Syn_Σ\) on a typed signature and prove its universal property, yielding compositional semantics via a unique functor to the matrix category \(\cat{Mat}_R\). Message-passing is formulated using a Grothendieck fibration \(\int\Msg \to \cat{FG}_Σ\) over polarized factor graphs, with schedule-indexed endomorphisms defining BP updates. We characterize exact inference as effective descent: local beliefs form a descent datum when compatibility conditions hold on overlaps. This framework unifies tree exactness, junction tree algorithms, and loopy BP failures under sheaf-theoretic obstructions. We introduce HATCC (Holonomy-Aware Tree Compilation), an algorithm that detects descent obstructions via holonomy computation on the factor nerve, compiles non-trivial holonomy into mode variables, and reduces to tree BP on an augmented graph. Complexity is \(O(n^2 d_{\max} + c \cdot k_{\max} \cdot δ_{\max}^3 + n \cdot δ_{\max}^2)\) for \(n\) factors and \(c\) fundamental cycles. Experimental results demonstrate exact inference with significant speedup over junction trees on grid MRFs and random graphs, along with UNSAT detection on satisfiability instances.

Related papers

• Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting [18.562483381753804]
  We present the Hinge Regression Tree (HRT), which reframes each split as a non-linear least-squares problem over two linear predictors.<n>We analyze this node-level optimization and, for a backtracking line-search variant, prove that the local objective decreases monotonically and converges.<n>We show on synthetic and real-world benchmarks that HRT matches or outperforms single-tree baselines with more compact structures.
  arXiv  Detail & Related papers  (2026-02-05T06:49:01Z)
• From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks [29.032055397116217]
  Interpretable Graph Neural Networks (GNNs) aim to reveal the underlying reasoning behind model predictions.<n>Existing subgraph-based interpretable methods suffer from an overemphasis on local structure.<n>We introduce a novel Tree-like Interpretable Framework (TIF) for graph classification.
  arXiv  Detail & Related papers  (2025-05-01T07:22:51Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  Graph neural networks (GNNs) for link prediction can loosely be divided into two broad categories.<n>We propose a novel GNN architecture whereby the emphforward pass explicitly depends on emphboth positive (as is typical) and negative (unique to our approach) edges.<n>This is achieved by recasting the embeddings themselves as minimizers of a forward-pass-specific energy function that favors separation of positive and negative samples.
  arXiv  Detail & Related papers  (2023-10-14T07:02:54Z)
• Efficient Computation of Counterfactual Bounds [44.4263314637532]
  We compute exact counterfactual bounds via algorithms for credal nets on a subclass of structural causal models. We evaluate their accuracy by providing credible intervals on the quality of the approximation.
  arXiv  Detail & Related papers  (2023-07-17T07:59:47Z)
• Mixtures of All Trees [28.972995038976745]
  We propose a novel class of generative models called mixtures of all trees: that is, a mixture over all possible ($nn-2$) tree-shaped graphical models over $n$ variables. We show that it is possible to parameterize this Mixture of All Trees (MoAT) model compactly in a way that allows for tractable likelihood and optimization via gradient descent.
  arXiv  Detail & Related papers  (2023-02-27T23:37:03Z)
• EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
  We show that the unique non-trivial point of the population log-likelihood is its global maximum. We establish that the expectation-maximization algorithm is guaranteed to converge to it in the single latent variable case.
  arXiv  Detail & Related papers  (2022-11-21T23:12:58Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering [33.000371053304676]
  We present the first continuous relaxation of Dasgupta's discrete optimization problem with provable quality guarantees. We show that even approximate solutions found with gradient descent have superior quality than agglomerative clusterings. We also highlight the flexibility of HypHC using end-to-end training in a downstream classification task.
  arXiv  Detail & Related papers  (2020-10-01T13:43:19Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.