Hyperbolic Belief Propagation

Zehua Cheng, Wei Dai, Jiahao Sun
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1230-1248, 2026.

Abstract

Belief Propagation (BP) has operated in {Euclidean} space for four decades, yet the polynomial volume growth of $\mathbb{R}^d$ is fundamentally mismatched to hierarchical graphs: faithful embedding of exponentially branching structure demands $d = \Omega(\log n)$ dimensions and prohibitive $\mathcal{O}(d^3)$ covariance costs, while truncating $d$ corrupts marginal estimates. We introduce Continuous Hyperbolic Belief Propagation ({CHBP}), formulated natively on the Lorentz hyperboloid $\mathbb{H}^n_K$, whose exponential volume growth eliminates this bottleneck. {CHBP} parameterises beliefs as Jacobian-corrected Wrapped Normals, approximates message integrals via Gauss–{Hermite} quadrature, and transports covariance tensors between tangent spaces via closed-form Levi-Civita parallel transport, with a curvature annealing schedule ensuring stable convergence. On hierarchical graphs, {CHBP} at $d{=}5$ reduces marginal KL divergence by $25\times$ versus {Euclidean} BP at $d{=}50$ and achieves up to 91.45% accuracy on real-world taxonomies, outperforming all baselines including Hyperbolic GCNs. On flat topologies, {CHBP} predictably underperforms {Euclidean} methods, confirming a topology-specific rather than universal advantage.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-cheng26a, title = {Hyperbolic Belief Propagation}, author = {Cheng, Zehua and Dai, Wei and Sun, Jiahao}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1230--1248}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/cheng26a/cheng26a.pdf}, url = {https://proceedings.mlr.press/v337/cheng26a.html}, abstract = {Belief Propagation (BP) has operated in {Euclidean} space for four decades, yet the polynomial volume growth of $\mathbb{R}^d$ is fundamentally mismatched to hierarchical graphs: faithful embedding of exponentially branching structure demands $d = \Omega(\log n)$ dimensions and prohibitive $\mathcal{O}(d^3)$ covariance costs, while truncating $d$ corrupts marginal estimates. We introduce Continuous Hyperbolic Belief Propagation ({CHBP}), formulated natively on the Lorentz hyperboloid $\mathbb{H}^n_K$, whose exponential volume growth eliminates this bottleneck. {CHBP} parameterises beliefs as Jacobian-corrected Wrapped Normals, approximates message integrals via Gauss–{Hermite} quadrature, and transports covariance tensors between tangent spaces via closed-form Levi-Civita parallel transport, with a curvature annealing schedule ensuring stable convergence. On hierarchical graphs, {CHBP} at $d{=}5$ reduces marginal KL divergence by $25\times$ versus {Euclidean} BP at $d{=}50$ and achieves up to 91.45% accuracy on real-world taxonomies, outperforming all baselines including Hyperbolic GCNs. On flat topologies, {CHBP} predictably underperforms {Euclidean} methods, confirming a topology-specific rather than universal advantage.} }
Endnote
%0 Conference Paper %T Hyperbolic Belief Propagation %A Zehua Cheng %A Wei Dai %A Jiahao Sun %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-cheng26a %I PMLR %P 1230--1248 %U https://proceedings.mlr.press/v337/cheng26a.html %V 337 %X Belief Propagation (BP) has operated in {Euclidean} space for four decades, yet the polynomial volume growth of $\mathbb{R}^d$ is fundamentally mismatched to hierarchical graphs: faithful embedding of exponentially branching structure demands $d = \Omega(\log n)$ dimensions and prohibitive $\mathcal{O}(d^3)$ covariance costs, while truncating $d$ corrupts marginal estimates. We introduce Continuous Hyperbolic Belief Propagation ({CHBP}), formulated natively on the Lorentz hyperboloid $\mathbb{H}^n_K$, whose exponential volume growth eliminates this bottleneck. {CHBP} parameterises beliefs as Jacobian-corrected Wrapped Normals, approximates message integrals via Gauss–{Hermite} quadrature, and transports covariance tensors between tangent spaces via closed-form Levi-Civita parallel transport, with a curvature annealing schedule ensuring stable convergence. On hierarchical graphs, {CHBP} at $d{=}5$ reduces marginal KL divergence by $25\times$ versus {Euclidean} BP at $d{=}50$ and achieves up to 91.45% accuracy on real-world taxonomies, outperforming all baselines including Hyperbolic GCNs. On flat topologies, {CHBP} predictably underperforms {Euclidean} methods, confirming a topology-specific rather than universal advantage.
APA
Cheng, Z., Dai, W. & Sun, J.. (2026). Hyperbolic Belief Propagation. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1230-1248 Available from https://proceedings.mlr.press/v337/cheng26a.html.

Related Material