Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Linear Uncertainty Quantification of Graphical Model Inference
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LinUProp, a closed-form, linearly scalable, convergent uncertainty quantification method for belief propagation on graphical models that propagates uncertainty additively, avoiding the underestimation of prior closed-form UQ methods like NETCONF.
Problem
Quantifying posterior belief uncertainty in graphical model inference (e.g., BP on MRFs) in a way that is scalable, convergent, and does not underestimate uncertainty when neighbors add noise or missing information.
Approach
Linearizes centered belief propagation and propagates interval-width uncertainty additively through edges, yielding a closed-form linear system (LinUProp) that supports edge-specific compatibility matrices and whose uncertainty equals a generalized variance term of the bias-variance decomposition of prediction error.
Key results
- LinUProp belief bound widths correlate strongly with Monte Carlo standard deviations on a 4x4 grid (PCC=0.9084).
- LinUProp converges within 10 iterations on all four datasets and its runtime scales linearly with the number of edges.
- BB and LC+BB selection achieve the highest mean accuracy in 28 of 32 fixed-budget (20b) cases with BP inference, e.g., 68.38% on Cora at 100% labeling accuracy for LC+BB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LinUProp belief bounds combined with least confidence instead of random node selection | BP active learning · Cora, 100% labeling accuracy, budget 20b | test accuracy: 66.900±1.987 -> 68.380±1.130 | Helped |
| Use LinUProp belief bounds combined with least confidence instead of random node selection | BP active learning · Citeseer, 100% labeling accuracy, budget 20b | test accuracy: 41.450±1.370 -> 44.360±1.737 | Helped |
| Use LinUProp belief bounds instead of entropy sampling | BP active learning · PubMed, 100% labeling accuracy, budget 20b | test accuracy: 57.350±1.827 -> 67.030±1.057 | Helped |
| Use LinUProp belief bounds combined with least confidence instead of random node selection | BP active learning · PolBlogs, 100% labeling accuracy, budget 20b | test accuracy: 86.920±1.847 -> 88.340±1.230 | Helped |
| Use LinUProp belief bounds combined with least confidence instead of entropy sampling | NETCONF active learning · Cora, 100% labeling accuracy, budget 20b | test accuracy: 68.570±3.373 -> 68.670±1.311 | No clear effect |
| Use LinUProp belief bounds combined with least confidence instead of random node selection | NETCONF active learning · Citeseer, 100% labeling accuracy, budget 20b | test accuracy: 44.340±1.322 -> 45.250±1.806 | Helped |
| Use LinUProp belief bounds combined with least confidence instead of entropy sampling | NETCONF active learning · PubMed, 100% labeling accuracy, budget 20b | test accuracy: 64.180±2.755 -> 67.820±1.036 | Helped |
| Use LinUProp belief bounds combined with least confidence instead of random node selection | NETCONF active learning · PolBlogs, 100% labeling accuracy, budget 20b | test accuracy: 86.360±2.095 -> 88.240±1.311 | Helped |
| Replace NETCONF with LinUProp for uncertainty quantification | Uncertainty quantification runtime · Cora | runtime (seconds): 0.0225 -> 0.0256 | Hurt |
| Replace NETCONF with LinUProp for uncertainty quantification | Uncertainty quantification runtime · Citeseer | runtime (seconds): 0.0216 -> 0.0181 | Helped |
| Replace NETCONF with LinUProp for uncertainty quantification | Uncertainty quantification runtime · PubMed | runtime (seconds): 0.0627 -> 0.0559 | Helped |
| Replace NETCONF with LinUProp for uncertainty quantification | Uncertainty quantification runtime · PolBlogs | runtime (seconds): 0.0126 -> 0.0084 | Helped |
Surprising findings
- Existing NETCONF/SocNL-style closed-form UQ can reduce uncertainty when adding high-uncertainty neighbors, underestimating posterior uncertainty.
- NETCONF-based certainty-score selection tends to prioritize low-degree nodes, leaving most nodes with persistent high uncertainty.
Limitations
- Convergence requires spectral radius of T below 1, which can fail for large graphs with strong global homophily or heterophily.
- Interpretability with human involvement in real decision-making is not explored.
- Relies on approximations (e.g., centered compatibility matrix making (I - H^2)^-1 approximately I).
Experimental setup
Datasets: Cora Citeseer PubMed PolBlogs
Benchmarks: Cora Citeseer PubMed PolBlogs
Metrics: Pearson correlation coefficient with Monte Carlo std average belief bound width over iterations running time test accuracy under labeling budget mean test accuracy with standard deviation
Baselines: Monte Carlo simulation NETCONF certainty score SocNL Least Confidence Entropy Random selection
Builds on: Belief Propagation Centered BP LinBP NETCONF
Closest papers by meaning
- Uncertainty Quantification with the Empirical Neural Tangent Kernel (NeurIPS 2025 · similarity 0.88)
- Efficient Analytic Uncertainty Quantification for Multimodal Regression (NeurIPS 2026 · similarity 0.87)
- Uncertainty for Active Learning on Graphs (ICML 2024 · similarity 0.86)
- Epistemic Uncertainty Quantification For Pre-Trained Neural Networks (CVPR 2024 · similarity 0.86)
- Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning (NeurIPS 2024 · similarity 0.86)
- Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.