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

1 INTRODUCTION

• GBP quickly damps errors that vary sharply between neighbors, while reducing global errors across distant graph regions can require many iterations.The paper identifies this local-versus-global error pattern in SLAM, 3D computer vision, and sensor networks.Source: §1 · p. 2
• H-GBP builds a low-rank coarse space from prominent local eigenmodes to capture low-frequency errors, then alternates coarse corrections with synchronous GBP on the original graph.The framework derives a cycle operator for linear Gaussian factor graphs and uses its spectral radius to predict convergence improvement.Source: §1 · p. 2
• H-GBP combines coarse residual correction with fine-level GBP; experiments report faster convergence on sparse linear graphs and speed and accuracy benefits on PGO and BA.The paper also establishes convergence results for linear factor graphs and local convergence on manifolds.Source: §1 · p. 2

2 RELATED WORK

• Earlier GBP analyses connect its behavior to global coupling structure, and the paper studies those dynamics through a matrix-operator view.The cited background includes walk-sum and linear/quadratic solver perspectives, as well as analyses of vector-valued Gaussian models.Source: §2 · p. 3
• Residual scheduling, damping, and feedback message passing modify updates on the original graph but do not build a coarse representation for long-range, low-frequency errors.These methods can reduce oscillation or avoid unnecessary updates.Source: §2 · p. 3
• H-GBP constructs a hierarchy directly on sparse factor graphs and derives coupled coarse/fine message dynamics, extending multilevel GBP beyond PDE/FEM discretizations.The authors describe it as the first multilevel GBP framework formulated and analyzed for general sparse factor graphs.Source: §2 · p. 3
• H-GBP sits between factor-graph optimization and distributed GBP, preserving GBP’s locality and parallelism while adding abstract-then-recover acceleration.The related work notes GBP applications in multi-robot localization, continuous-time SLAM, and bundle adjustment on graph processors.Source: §2 · p. 3

3.1 FACTOR GRAPHS

• A factor graph is a bipartite representation of a joint distribution, with variable nodes, factor nodes, and edges encoding the factorization.Variables carry marginal beliefs, while factors define joint Gaussian potentials over neighboring states; their canonical parameters form the global precision matrix and information vector.Source: §3.1 · p. 3

3.2 GAUSSIAN BELIEF PROPAGATION

• GBP updates messages between neighboring nodes and combines incoming messages to update variable beliefs; a synchronous iteration updates variable messages, factor messages, then beliefs.The overview presents three update equations for factors of degree two or less and says the Schur complement extends them to higher-degree factors.Source: §3.2 · p. 4, Figure 4 · p. 4

4 HIERARCHY-GBP: ALGORITHM AND MATRIX OPERATORS

• The H-GBP cycle runs synchronous GBP sweeps, solves a coarse residual problem, and injects the correction while preserving messages; its prolongation matrix remains fixed.The cycle operator combines abstraction and recovery, the first post-recovery GBP iteration, and subsequent synchronous GBP iterations.Source: §4 · p. 4, §4.3 · p. 6

4.1 OPERATOR 1: ABSTRACTION & RECOVERY OF A COARSE GRAPH APPROXIMATION

• For abstraction, variables are grouped into supernodes and the smallest eigenmodes of each group’s precision matrix form a blockwise prolongation matrix for the coarse space.The coarse residual equation is (P^TAP)δz = P^T(b − Ax), and the recovered correction updates the variable means.Source: §4.1 · p. 5

4.2 OPERATOR 2: THE FIRST GBP ITERATION AFTER RECOVERY

• Recovery updates variable beliefs without changing graph messages, creating an inconsistency that one GBP iteration repairs; the section derives the operator for that first iteration.The operator describes the updated information-message error using both mean and message errors.Source: §4.2 · pp. 5–6, §4 · p. 5

4.3 OPERATOR 3: THE REMAINING SYNCHRONOUS GBP ITERATIONS

• After beliefs and messages are consistent, synchronous GBP updates follow an affine message operator; subtracting its fixed point yields the error operator Q.The section also combines the remaining GBP iterations and a readout operator that updates mean errors from information-message errors.Source: §4.3 · p. 6

4.4 EXTENSION TO MANIFOLDS

• For nonlinear factor-graph optimization, H-GBP solves a linearized system in the tangent space and retracts the resulting update before repeating.The extension uses right perturbations and repeats until the estimate converges.Source: §4.4 · p. 6

5.1 LINEAR HIERARCHY-GBP

• On fixed Gaussian pose-graph systems, H-GBP removes low-frequency error that local message passing alone struggles to eliminate, with stable error reduction across cycle and GBP-iteration budgets.As precision messages stabilize, successive-cycle error ratios approach the predicted spectral-radius contraction factor.Source: §5.1 · p. 7, Figure 6 · p. 7
• Sparse-Cholesky runtime grows 1.88× across fill-in levels, while H-GBP runtime grows 1.08×.At the same GBP budget, local low-rank abstraction reduces error more strongly than the basic multigrid-style alternative; retaining four local modes per group gives stable correction with little sensitivity above that threshold.Source: §5.1 · p. 7, Figure 5 · p. 7

5.2 HIERARCHY-GBP ON SE(2) AND SE(3) PGO

• On the three largest PGO graphs, 16-thread H-GBP is fastest, with speedups over g2o-Cholesky of approximately 126.6×, 17.5×, and 30.2×.It ranks among the three fastest methods on eight of nine benchmarks, and its final costs match g2o-Cholesky at the reported precision.Source: Table 1 · p. 7, §5.2 · p. 8

5.3 HIERARCHY-GBP ON BUNDLE ADJUSTMENT

• H-GBP is fastest on all ten BA datasets, with approximately 2.0×–4.4× speedups over the fastest competing 16-thread baseline on each dataset.It remains within 3.4% of the lowest reported cost across the suite and has lower final costs than PowerBA on every dataset.Source: §5.3 · p. 8, Table 2 · p. 8

6 MAIN THEORETICAL RESULTS

• Precision messages converge globally at a geometric rate, linking dynamics from initialization to the limiting fixed point.The stated result assumes the paper’s admissible precision initializations.Source: §6 · p. 9
• The reduced cycle operator Mk captures the cycle-boundary dynamics, and its spectral radius gives the geometric convergence criterion for the full iteration.The cycle-boundary subspace is invariant under Taug,k.Source: §6 · p. 9
• For fixed cycle length k, the full H-GBP iteration converges from every admissible initialization if and only if ρ(Mk) < 1, equivalently ρ(Taug,k) < 1.When this condition holds, the fine-level mean converges to x⋆=A−1b.Source: §6 · p. 9
• Under standard local inexact Gauss–Newton conditions, manifold H-GBP converges locally Q-linearly to a stationary point if each tangent system satisfies ρ(Mk,t) < 1 and inner solves meet a sufficiently small fixed relative-residual tolerance.Source: §6 · p. 9

• H-GBP combines local message passing with low-rank coarse correction and is competitive in runtime and solution quality on pose-graph and bundle-adjustment benchmarks.The paper identifies broader sparse factor-graph problems, fully message-passing upper levels, and hierarchy-free distributed abstractions as future work.Source: §7 · p. 9

Supplementary Material

• Appendix A lists a three-node four-factor example and a standard GBP failure case.Source: Supplementary Material · p. 13
• Appendix B covers precision convergence, the MAP-centered message reference, the linear H-GBP cycle, its global convergence criterion, and the manifold extension.Source: Supplementary Material · p. 13
• Appendix D lists implementation details and separate experiment details for linear graphs, pose graphs, and bundle adjustment.Source: Supplementary Material · p. 13

A.1 A THREE-NODE FOUR-FACTOR EXAMPLE

• In the scalar three-variable example, the limiting eta-transfer matrix Q is assembled from local Schur-complement coefficients and consists of two directed three-cycles, each with product 1/2.The unary factor affects the denominator and affine offset, but not the linear message-to-message entry of Q.Source: §A.1 · pp. 14–15

A.2 STANDARD GBP FAILURE CASE

• Standard GBP has ρ(Q) > 1 in the four-variable example, while H-GBP with groups {0,1} and {2,3}, rank r = 3 per group, and k = 8 has ρ(M8) < 1.The example demonstrates a setting where standard GBP does not converge but H-GBP does.Source: §A.2 · p. 16, Figure 8 · p. 16

B THEORY

• For fixed cycle length k, H-GBP converges from every admissible initialization iff ρ(Mk) < 1, equivalently ρ(Taug,k) < 1; when this holds, its fine-level mean converges to the exact MAP solution.Source: B THEORY · p. 17

B.1 CONVERGENCE OF PRECISIONS

• The hierarchy leaves the standard GBP precision recursion unchanged, and every admissible precision initialization converges geometrically to its unique positive-definite fixed point.Near the fixed point, the precision update is a strict contraction.Source: §B.1 · pp. 18–19

B.2 MAP-CENTERED MESSAGE REFERENCE

• The canonical eta-message reference reads out the MAP solution for every precision state and propagates with precision updates, becoming a fixed point at the limiting precision.At that fixed point, the belief mean is the MAP solution.Source: §B.2 · pp. 20–21

B.3 FROZEN LINEAR H-GBP CYCLE

• The coarse residual correction is a Galerkin A-orthogonal projection, and the cycle-boundary reduction yields an operator spectrally equivalent to the augmented cycle operator.Source: §B.3 · p. 22

B.4 FROM THE INITIAL PRECISION TO THE LIMITING CYCLE

• With precision fixed at its limit, the eta-error cycle operator is Mk = Q^(k−1)(JCR + U); before that limit, exact cycle-boundary dynamics use precision-dependent operators.The cycle update combines the readout, Galerkin correction, repair sweep, and remaining GBP sweeps.Source: §B.4 · p. 23
• For every admissible precision initialization and fixed k, the exact cocycle converges exponentially under constants C_M,k < ∞ and θ_M,k ∈ (0, 1).Source: §B.4 · p. 23
• If z_{t+1} = (A + E_t)z_t in finite dimension, E_t → 0, and ρ(A) < 1, then z_t → 0 for every z_0.The proof uses an adapted norm that makes the tail dynamics contractive; the finite prefix is absorbed into a constant.Source: §B.4 · p. 23

B.5 GLOBAL CONVERGENCE CRITERION AND MAP TARGET

• For fixed cycle length k, convergence from every admissible initialization is equivalent to ρ(Mk) < 1 or ρ(Taug,k) < 1; under this criterion the fine mean reaches the exact MAP solution.Source: §B.5 · p. 24

B.6 H-GBP ON MANIFOLDS

• Under standard local inexact Gauss–Newton conditions, tangent H-GBP cycles with ρ(Mk,t) < 1 and a sufficiently small fixed relative-residual tolerance yield local Q-linear convergence to a stationary point.Source: §B.6 · p. 25

The resulting nonlinear outer rate satisfies

• Geometric inner convergence gives finite attainment of the prescribed forcing tolerance, which explicitly controls the nonlinear outer convergence rate.Source: The resulting nonlinear outer rate… · p. 26

C ALGORITHM

• The algorithm builds local bases from the lowest eigenvectors, assembles the coarse system, runs k fine GBP sweeps, then restricts and injects a coarse residual correction.Source: C ALGORITHM · p. 27

D.1 IMPLEMENTATION DETAILS

• For fixed Gaussian models, cached precision gains let eta-only sweeps replace repeated small factorizations with matrix–vector products, reducing per-message arithmetic from O(d3) to O(d2).Caches are refreshed when the linearized model changes.Source: §D.1 · p. 28

D.2 LINEAR EXPERIMENT DETAILS; D.2.1 TWO-LAP TRANSLATION GRAPH

• Linear convergence tests use fixed Gaussian systems and direct MAP references; the two-lap graph uses 200 two-dimensional variables grouped into twenty groups, with dimension reduced from 400 to 80.Source: §D.2 · p. 28, §D.2.1 · p. 28

D.2.2 COARSE-SPACE ABLATION: FIG. 5(A); D.2.3 SPECTRAL CONTRACTION: FIG. 5(B)

• The low-rank coarse space leaves substantially smaller remaining error than the alternatives in the Sphere ablation, while spectral error ratios approach the predicted asymptotic rates as precision messages stabilize.The spectral-radius prediction describes the asymptotic rate, not a universal one-step norm bound.Source: §D.2.2 · p. 29, Table 4 · p. 29, §D.2.3 · p. 29

D.2.4 FILL-IN SENSITIVITY: FIG. 5(C)

• 1.883× for Cholesky versus 1.075× for H-GBP as fill-in increases, an empirical sensitivity comparison at fixed problem size and sparsity.The runtimes cover ten nonlinear outer iterations; this is not an asymptotic complexity claim.Source: §D.2.4 · pp. 29–30, Table 6 · p. 30

D.3 SE2/SE3 POSE-GRAPH EXPERIMENT DETAILS

• The comparison includes Cholesky, g2o-PCG, AMM-PGO, Cycle-PGO, and Schwarz-PGO, with method-specific nonlinear iteration limits.Cholesky’s dominant numerical factorization is serial; AMM-PGO retains native iteration budgets, while Cycle-PGO and Schwarz-PGO allow up to twenty nonlinear iterations.Source: §D.3 · p. 30
• Final poses are rescored with the same full-information, half-quadratic Lie-log cost, although several methods retain different internal objectives and initialization.H-GBP, Cholesky, PCG, and Schwarz use Huber threshold 5; AMM-PGO retains its native scalar-weighted chordal robust objective, while Cycle-PGO uses a non-robust objective.Source: §D.3 · p. 30
• H-GBP uses 20 outer iterations in both SE(2) and SE(3), with different values for c, k, and r across the two spaces.Both settings use group size 20; precision freezing requires three consecutive checks below relative tolerance 10^-8, with rechecks and reactivation rules.Source: §D.3 · p. 30
• H-GBP consistently reduces the objective across nine graphs and avoids pronounced early spikes on Cubicle and Grid in the direct Gauss–Newton reference.Figure 9 presents the archived objective-versus-outer-iteration comparison as a qualitative illustration, separate from current timing runs.Source: §D.3 · p. 30, Figure 9 · p. 31

D.4 BUNDLE ADJUSTMENT EXPERIMENT DETAILS

• The BA comparison uses a twenty-iteration budget, squared two-dimensional reprojection residual cost, and released implementations with identical input files, camera model, and normalization.Table timings exclude loading and common normalization; H-GBP, RootBA, and PowerBA include internal setup, while Ceres reports Solve time excluding wrapper problem construction.Source: §D.4 · p. 31
• Across BA scenes, cameras are grouped to target size max(2, ⌈nc/24⌉), each group retains nine modes, and the fine-graph damping coefficient is one.Camera-system precision messages are computed until relative change is below 10^-6, then cached eta maps are reused across H-GBP applications.Source: §D.4 · p. 31
• H-GBP reaches lower final cost on all ten BA benchmarks while spending less time in nonlinear iterations than PowerBA.Figure 10 compares actual per-outer histories; its time axis excludes one-time setup, loading, and normalization, while the main table reports solver totals separately.Source: §D.4 · p. 31, Figure 10 · p. 32

E DISCUSSION

• Extending the two-level method is nontrivial because GBP on the induced coarse factor graph typically needed many iterations and was slower than a direct sparse solve at that level.The discussion identifies designing message-passing upper levels that retain scalability and locality as an open direction.Source: E DISCUSSION · p. 33
• The abstraction-and-recovery principle may apply beyond pose graphs and BA, including robot-local subgraphs in multi-robot SLAM and grouped pixels, patches, or objects in visual odometry.The discussion presents these as possible applications to explore in broader sparse graphical models.Source: E DISCUSSION · p. 33