CS Paper Radar

Hierarchy-GBP: Accelerating Factor Graph Inference via Abstraction and Recovery

Yuzhou Cheng, Tom Yates, Ignacio Alzugaray, Danyal Akarca, Pedro A. M. Mediano, Andrew J. Davison

cs.CV cs.LGcs.RO ·submitted 2026-10-04 00:50 UTC · v1
theory

Abstract

Gaussian Belief Propagation (GBP) is a distributed inference algorithm that passes messages in graphical models, making it attractive for scalable spatial intelligence. However, we find GBP most effective locally: it rapidly smooths message errors that vary sharply between neighbor variables, but corrects global errors across distant graph regions incrementally through long-range message propagations. We propose Hierarchy-GBP (H-GBP), an iterative, two-stage framework that accelerates GBP by first solving these global errors with a coarse graph approximation (abstraction) and projecting the results back to the original graph (recovery), then refining the remaining local errors with GBP. We prove H-GBP convergence to the optimum by deriving the combined matrix operator of our abstraction and recovery steps and analyzing its spectral radius. Experiments on linear sparse graphs show that H-GBP converges fundamentally faster than standard GBP. Moreover, we validate H-GBP on two important spatial problems: Pose Graph Optimization (PGO) and Bundle Adjustment (BA). H-GBP markedly accelerates large-scale PGO and achieves state-of-the-art runtime across all tested BA scales.

Comment
33 pages, 10 figures, including appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Extended Neighborhood Message Passing for Inference in Loopy Factor Graphs

eess.SY ·2026-10-09 ·Kuilong Yang, Zengfu Wang, Hua Lan
similarity 0.73
Abstract · 26 pages, 18 figures

Belief propagation (BP) is widely used for inference on probabilistic graphical models but often suffers from non-convergence and poor accuracy on loopy factor graphs, yielding inexact variance estimates in the Gaussian case. Generalized BP (GBP) improves accuracy but relies on manual design or application-specific heuristics for region-graph construction. We propose extended neighborhood message passing (ENMP), which automatically constructs extended neighborhoods of variable nodes from the bipartite factor graph topology, capturing loop-induced correlations without manual region design. The framework applies to general distributions on factor graphs with a tunable accuracy-complexity trade-off. In the exact regime, message updates converge to the unique fixed point of the ENMP equations in finitely many iterations, yielding exact marginals; in the approximate regime, ENMP provides approximate marginals. For Gaussian factor graphs, we derive closed-form update rules enabling exact variance estimation in the exact regime, addressing the long-standing inaccurate variance estimates of loopy Gaussian BP. We evaluate ENMP on densely loopy Gaussian factor graphs from power-grid benchmarks and on a discrete Ising factor graph. Results show accuracy improves with neighborhood size, with exact marginals achieved on several systems in both settings. On larger Gaussian systems, ENMP outperforms regularized Gaussian BP (sGaBP-m) in both mean and variance estimation accuracy.

0.17

Direct Message Approximation (DMA): A Consistency-Based Framework for Tractable Approximate Inference on Factor Graphs

cs.LG cs.AIstat.ML ·2026-09-24 ·Ralf Herbrich, Rainer Schlosser, Jan Lemcke, Johann Ukrow, Anna Kazachkova +9 more
theory similarity 0.63
Abstract · Submitted to ICLR 2027

Approximate message passing on factor graphs underlies two dominant families of probabilistic inference algorithms: expectation propagation (EP) and variational message passing (VMP). Both methods approximate the marginal at each factor edge, forcing an iterative round-robin schedule, risking negative-precision messages, and, for VMP, collapsing to point estimates at Dirac-delta factors. We introduce Direct Message Approximation (DMA), which approximates factor-to-variable messages directly rather than the marginal. For normalisable factors, we define a consistency condition (requiring exactness when all other incoming messages are Dirac deltas) to guide message construction. We prove a master theorem (proper messages, any graph) bounding marginal KL from message KL, with three structural corollaries: Dirac-input consistency, no EP-style inner-loop iteration, and no negative-precision messages. Further, we prove a complementary $O(1/r^2)$ guarantee for the inherently improper backward message of the product factor, whose closed-form treatment has resisted prior work. As a concrete instantiation, we derive explicit DMA messages for the product and leaky-ReLU factors and assemble a Bayesian neural network (BNN) inference algorithm with one forward/backward sweep per training example and no gradient learning-rate hyperparameter, validating that the structural guarantees translate to predictive uncertainty that widens in data-sparse regions, including under model mismatch.

0.42

Scalable GNN-based Knowledge Graph Representation Learning with Efficient Message Passing

cs.LG cs.AI ·2026-09-28 ·Huu Tan Mai, Cuong Xuan Chu, Heiko Paulheim, Daria Stepanova
published similarity 0.62
Abstract · Accepted at the Posters and Demos Track of the International Semantic Web Conference (ISWC) 2026

Graph neural networks (GNNs) excel at representation learning on Knowledge Graphs (KGs), achieving stateof-the-art performance on tasks like link prediction or entity classification. However, their high computational complexity, inherent to their user-defined message passing (MP) algorithm, still prohibits their widespread adoption, especially for large KGs. Current efforts to mitigate the scalability bottlenecks of GNNs on KGs, such as subgraph sampling, are often task- and model-specific, and do not reliably guarantee lossless (if applicable) runtime/space reductions. To address this, we extend Relational Sparse Matrix Multiplication (RSPMM), originally designed to losslessly lower the space complexity of composition-based MP with pointwise composition functions, to support more expressive functions (e.g., 2x2 block-diagonal matrix multiplication, Givens rotation, circular correlation). Our method delivers significant task-independent reductions in runtime and space for current GNNs on KGs and facilitates efficient re-implementations of GNNs that maintain near state-of-the-art performance on challenging KG tasks, for a fraction of computational costs.

0.26

Probabilistic Scene Graphs: Hierarchical Representation and Real-time System

cs.RO ·2026-09-19 ·Waqas Ali, Michele Antonazzi, Timon Homberger, Thien-Minh Nguyen, Lukas Rosenberger Schmid +2 more
similarity 0.62
Abstract

3D scene graphs provide semantically rich and hierarchical representations for robot perception. However, existing systems do not maintain uncertainty as an explicit belief or propagate it through the operations that construct and refine the graph. We introduce Probabilistic Scene Graph (PSG), a generalization of the conventional scene graph that represents a posterior over possible graphs, factorized into a discrete graph structure of entities, relations, and semantic attributes, and continuous states that ground them spatially, with uncertainty maintained over both components. Geometry is carried directly by the nodes rather than selected from a separately constructed metric map, so a metric map, where needed, follows from the graph rather than preceding it. We instantiate PSG's probabilistic spatial grounding with hierarchical graphs of Gaussians (HGG): each object primitive is represented by a full-covariance Gaussian under a Normal-Inverse-Wishart belief, and the same parametrization applied recursively within a node yields a geometry graph that resolves its surface at finer resolution. We then build a mapping pipeline that preserves these beliefs throughout graph construction and refinement: a purely graph-based coarse-to-fine alignment registers observations by comparing node beliefs, while a nested Expectation-Maximization and factor-graph optimization jointly refines poses, object parameters, and internal geometry. Across six datasets spanning indoor RGB-D, outdoor LiDAR, and cross-modality deployment, HGG operates at sensor rate with near-constant memory and achieves state-of-the-art object accuracy and zero-shot graph alignment.

0.16

Graph Learning with Spectral Connectivity Priors for Scarce Data

cs.LG eess.SP ·2026-09-23 ·Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao +1 more
similarity 0.61
Abstract · 5 pages, 1 figure. Submitted to IEEE ICASSP 2027

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

0.24

Beyond Static Graph World Models: Learning Stochastic Latent Dynamics over Evolving Topologies

cs.LG cs.AIcs.SI ·2026-09-23 ·Alex Schutz, Nick Hawes, Victor-Alexandru Darvariu
similarity 0.60
Abstract

Graph-based world models have recently emerged as a means of learning transitions over relational state representations. However, existing approaches are largely limited to fixed-topology graphs or deterministic, fully observable environments. We propose the Graph Dynamics Model (GDM), a world model for graph-structured observations that is designed to handle the more general setting of evolving topologies in stochastic and partially observable environments. The GDM uses a sparse recurrent adjacency matrix to model topology updates and perform message passing, together with a recurrent state-space architecture for modelling stochastic transitions. Furthermore, we identify a gap in the evaluation of graph-based world models, as existing methods do not provide a means of comparing predicted and true distributions over the joint graph state comprising the interdependent topology, node features, and graph features. We therefore introduce the Graph Distribution Distance (GDD) metric, which uses maximum mean discrepancy with a graph kernel to comprehensively compare joint next-state distributions. We evaluate the GDM across several environments, including stochastic and partially observable settings. We demonstrate that GDM outperforms baseline models and displays zero-shot generalisation on large graphs.

0.26

Columnar-Embedder: A Biologically Inspired Cortical Architecture for Binary Sparse Distributed Graph Representations

cs.NE ·2026-08-12 ·Mohamed Abidalrekab, Dan Hammerstrom
similarity 0.60
Abstract

Finding a representative description of graph entities that captures their structural roles and homophily is a challenging goal for graph embedding techniques due to the non-Euclidean nature of graphs. Traditionally, Graph embeddings achieve top performance via random-walk methods and graph neural networks. However, these methods are transductive and utilize an expensive global optimization via softmax or a dense representation trained in an end-to-end pipeline with gradient descent. Nonetheless, other variants of GNNs can map to unseen nodes; they still rely on iterative message passing and backpropagation, incurring high computational and memory costs. Conversely, the mammalian cortex solves structurally similar problems by learning to map its input stream of patterns into a compact representation for downstream regions. We present the biologically inspired Columnar-Embedder architecture for learning binary Sparse Distributed Representations (SDRs) of graph nodes. The learning is driven by a local Bienenstock-Cooper-Munro (BCM) Hebbian rule modulated by positive pointwise mutual information (PPMI) computed from online streams of random walks. Continuous learning from streaming random-walk pairs without labels, backpropagation, or supervision enables the architecture to exhibit natural resistance to catastrophic forgetting. Across five graph benchmarks, the performance of SDRs is competitive with that of real-valued dense embeddings on node classification and link prediction, while the architecture exhibits portability, resilience to noise, and robustness to data corruption.

0.04

Alleviating Limited Effectiveness and Multi-Class Collapse in Deep Graph-level Clustering

cs.LG ·2026-11-04 ·Xiaoyang Lin, Renchi Yang, Yuqi Chen, Xin Huang
benchmarktheoryhot direction similarity 0.59
Abstract

Given a collection of $N$ graphs, graph-level clustering (GLC) seeks to partition the $N$ graphs into semantically meaningful groups, which serves as a fundamental task in analyzing graph-structured data. While Graph Isomorphism Networks (GINs) have become the de facto encoders for GLC, they still fail to distinguish graphs due to their neglect of global topology. On top of that, existing deep clustering frameworks suffer from severe "clustering collapse" issues, particularly in imbalanced multi-class scenarios. To address these challenges, we propose S$^3$GLC, a novel framework that integrates global topological characteristics with local neighborhood features for balanced GLC. Theoretically, we leverage the Hoffman-Wielandt inequality to construct Spectral Signature as a rigorous lower bound for graph edit distance (GED), providing a computationally efficient proxy for global topological features. We additionally propose a joint manifold-preserving sparse regression module to fuse Spectral Signature with Spatial Representation, eliminating noise while preserving the complementary information. Furthermore, to mitigate clustering collapse, we introduce a balanced clustering objective based on optimal transport, harnessing the Sinkhorn-Knopp normalization to enforce equipartition constraints on cluster assignments. Extensive experiments on 10 real-world datasets demonstrate that S$^3$GLC significantly outperforms 15 state-of-the-art baselines, achieving remarkable improvements on benchmark datasets such as REDDIT-12K and OGBG-PPA.

0.23