Linear Uncertainty Quantification of Graphical Model Inference
Authors: Chenghua Guo
Han Yu
Jiaxin Liu
Chao Chen
Qi Li
Sihong Xie
Xi Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: graphical models
belief propagation
uncertainty quantification
Primary area: probabilistic_methods
TL;DR: We propose LinUProp, a novel approach that offers accuracy, interpretability, scalability and guaranteed convergence for uncertainty quantification of graphical model inference.

Abstract: Uncertainty Quantification (UQ) is vital for decision makers as it offers insights into the potential reliability of data and model, enabling more informed and risk-aware decision-making. 
Graphical models, capable of representing data with complex dependencies, are widely used across domains.
Existing sampling-based UQ methods are unbiased but cannot guarantee convergence and are time-consuming on large-scale graphs. 
There are fast UQ methods for graphical models with closed-form solutions and convergence guarantee but with uncertainty underestimation.
We propose *LinUProp*, a UQ method that utilizes a novel linear propagation of uncertainty to model uncertainty among related nodes additively instead of multiplicatively, to offer linear scalability, guaranteed convergence, and closed-form solutions without underestimating uncertainty.
Theoretically, we decompose the expected prediction error of the graphical model and prove that the uncertainty computed by *LinUProp* is the *generalized variance component* of the decomposition.
Experimentally, we demonstrate that *LinUProp* is consistent with the sampling-based method but with linear scalability and fast convergence.
Moreover, *LinUProp* outperforms competitors in uncertainty-based active learning on four real-world graph datasets, achieving higher accuracy with a lower labeling budget.

Linear Uncertainty Quantification of Graphical Model Inference
Chenghua Guo",, Han Yu?", Jiaxin Liu', Chao Chen', Qi Sihong Xie Xi Zhang
'Key Laboratory of Trustworthy Distributed Computing and Service (MoE),
Beijing University of Posts and Telecommunications, China
College of Artificial Intelligence, Beijing University of Posts and Telecommunications, China 'Deparmeent of Computer Science and Engineering, Lehigh University, USA
School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), China
$ Department of Computer Science, lowa State University, USA 6 AI Thrust, The Hong Kong University of Science and Technology (Guangzhou), China {chenghuaguo, 2hangx)@bupt. edu. en, yuhan2021@bup edu. en, jilbi701ehigh. edu, cha01nbox@gmail. com, ql Aliiiastate.edii xiesihong @gmail com
Abstract
Uncertainty Quantification (UQ) is vital for decision makers as it offers insights into the potential reliability of data and model, enabling informed and risk-aware maaiiinn Graphical models, capable of representing data with complex de- pendencies, widely used across domains. Existing sampling-hasee based UQ methods are unbiased but cannot guarantee convergence and are time-consuming on large- scale graphs. There fast UQ methods for graphical models with closed-form solutions and convergence guarantee but with uncertainty underestimation. We pro- pose LinUProp, UQ method that utilizes novel linear propagation of uncertainty to model uncertainty among related nodes additively instead of multiplicatively, to offer linear scalability, guaranteed convergence, and closed-form solutions without underestimating uncertainty. Theoretically. we decompose the expected prediction error of the graphical model and prove that the uncertainty computed by LinUProp is the generalized variance component of the decomposition. Experimentally, we demonstrate that LinUProp is consistent with the sampling-based method but with linear scalability and fast convergence. Moreover, LinUProp outperforms competitors in -ncerda active learning on four real-world graph datasets, achieving higher accuracy with lower labeling budget.
1 Introduction
Graphical models are known for their capability to represent data with complex dependencies. These models have been extensively applied to various fields, ranging from social networks [939, fraud
detection [26] 8, recommendation [14] 37 and crowdsourcing [25] [6], to more recent applications
in enhancing graph neural networks (GNNs) I0 28
and large language models (LLMM)) [5] 34
12 17 Belief Propagation (BP) (27 stands out as a powerful iterative passsae--passing algorithm. BP takes an initial guess (or "prior belief")) of each node and refines it using information propagation, resulting in an updated, more accurate estimate called "posterior belief". However, crucial limitation of BP that only provides
Among the many inference techniques in graphical models [19 13
These authors contributed equally.
+ Corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

point estimates for these posterior beliefs [7] and does not capture their potential uncertainty. leading decisions unaware of the underlying data and model unreliability, For example, in a social network, a higher inferred probability of Alice's interest in sports over Bob's may lead to erroneous decisions if, in fact, Alice's 's inferred probability has high uncertainty and only a slightly higher interest.
To handle the uncertainty present in the beliefs, some well-known sampling- based uncertainty quantification (UQ) tools, such as Monte Carlo (MC) simulations, can provide unbiased UQ. However, these techniques are time-consuming for large-scale graphs and cannot ensure convergence within a reasonable time frame in practice [2T] Existing works 77] 33), based on Bayesian theory, have derived UQ methods with provable convergence and scalability by modeling beliefs as Dirichlet distributions and treating neighboring nodes as observations. However, this means that any neighbor of node will necessarily reduce the uncertainty, even neighbors with noise or missing information. As illustrated in Figure I_ consider a user with no preference information about being a music enthusiast, and A has two friends who are music enthusiasts (represented by strong preference with Beta distribution parameters like (33, 1). where the parameters represent positive and negative preference counts). If A gains additional friend D who has no preference information (represented by a uniform distribution (11, the existing methods still reduce A's uncertainty, incorrectly suggesting increased confidence that A is music enthusiast. This results in an underestimation of posterior uncertainty. Furthermore, none of existing works provided a theoretical relationship between the computed uncertainty and the expected model prediction error, making it difficult for decision-maken to understand and trust the UQ results.
To address the challenges mentioned above, we introduce Linear Uncertainty Propagation (Lin- UProp), a method to quantify the uncertainty in posterior beliefs resulting from multiple it- erations of propagation of uncertainty in node priors, which offers the following advantages:
After One Step of Propegation
A's Distribution by NETCONF/SooNL.
A's Interval Width by LinUProp
Graphs and Initial Node Priors
(Larger s+ indicalas lower uncertainty)
(Wider interval indicabea higher uncertainty)
BLL
Methodologically, we propose LinUProd] (Sec. 3 novel linear method that spreads the uncertainty from each node to the entire graph and additively aggregates this uncer- tainty to avoid underestimating posterior un- certainty. LinUProp offers interpretability due to the additive of neighbor uncertainty (Fig. D. enabling tracking the contributions of other nodes to the computed uncertainty and allowing users to understand its sources.
m.
duj
G
Pajo, = Ba + Pa Ac
Tet [
@
G:
Paic, - H/ + Ho Pc Po
Treating Neighbors as Observations Leads Undersstimation of A'a Uncartainty
A Property Incorporates
PMLL
Betalx,))
Neighbora' Uncartainty
Theoretically, LinUProp possesses closed- form solution, provable convergence related the spectral radius of a matrix representing the dependencies between nodes (Sec. 4.1 and proven linear scalability (Appendix A.3 Moreover, by employing the bias-variance decomposition, we demonstrate that the pos- terior uncertainty is a generalized variance component of the expected model prediction error (Sec.
Figure 1: The impact of more neighbors on posterior uncertainty. NETCONF (7) or SocNL (35) underesti- mates posterior uncertainty of A in G2 by considering high-uncertainty node D neighbor that reduce uncer- tainty. LinU/rop represents the uncertainty a posterior using interval widths, where increased uncertainty from more neighbors leads to higher posterior uncertainty. The proposed interval ways be interpret a generalized variance component of the expected prediction error (Sec. 4.2 Furthermore, LinU/Pop is interpretable due to the additive of neighbor uncertainty (Fq. (2)).
Experimentally, we demonstrate the follow- ing with LinUProp: (1) The uncertainty quan- tified by LinUProp is accurate due to its strong positive correlation with MC simu- lations (Fig. in Appendix I (2) LinUProp exhibits both fast convergence and linear scalability (Fig. 4 : (3) LimuProp is interpretable (Fig. B3: (4) When applied to graph active learning guided by uncertainty, LinUProp achieves superior accuracy with a smaller budget compared to the baseline
method that underestimates uncertainty (Figs. 6
Project page including code at ht ccm//cchengghuguuooLLUUoUooog
2

---

2 Preliminaries
iteratively passes messages graph to infer posterior distributions of variables on graphical model. We focus on the uncertainty the inferred posteriors used for node classification Markov Random Field (MRF). Bayesian networks another important type of graphical models that can be converted into MRF (27].
Belief Propagation (BP) 27
Consider graph G = (V) with random variable nodes, each with k possible classes. The prior e, for node 8 a k-dimension probability distribution and (1) specifies the prior probability for node belonging to class Each edge (s, () from represents the dependencies between the two random variables and I. particular, the dependency is represented by a pairwise potential function, which is & x compatibility matrix H and H (i. j) denotes the degree of association between class i of node and class j of node t. We assume that H is a symmetric matrix, as in [1I 7]. Specifically, for binary classification, the compatibility matrix is assumed to be
0.5 + 0.5 6
(1)
0.5 e 0.5 0
Similarly, an example form of H for multi-class problems is setting the diagonal elements to + (A: - 1)e and the other elements to & - c. |e| is typically close to O, and positive/negative e specifies homophilyyhhterophiil relationship between any two connected nodes. Unlike existing methods that require all edges to have the same compatibility matrix, our proposed LinUProp can handle situations where each edge has a different compatibility matrix.
BP updates the k-dimensional message mys sent from node to node s by:
(i) Σ H(i.))e
II mma L,
(2)
MEN(EMS
where (t) is the set of neighboring nodes of t. Eq. (2) is applied iteratively until convergence or a maximum number of iterations is reached. Then the posterior b, for node is
(i) Z,
(t) II mz)(1), i = I,...,k,
(3)
AEA((s
where Z, for normalization such that Σ (i) =1
Centered BP I1 is a linearized version of Eqs. 23
1 mot (1)) (4) 2)) + Σ m)r(1), (5)
mis (i) - k Σ j=1
H (1,5)
be (1)
k
+EN(ss
where (1) = (i) 1. (i) b. 61) mes m A (i, = H (i.j) - } are the
centralized version of the prior, belief, message, and compatibility matrix.
NETCONF ? models both the belief and uncertainty of each node using a Dirichlet distribution.
The certainty of a node is represented by the sum of its Dirichlet parameters, where higher indicates greater certainty. Each node u is initialized with a prior Dirichlet belief vector é The posterior Dirichlet belief b, is updated using multinomial messages from its neighbors:
b +- C..
Σ
moas
m
<- M
é
m
(E)
where my is the message from node to u, and M a modulation matrix derived from H. Problem (Quantifying Uncertainty Posteriors).
Given: (1) An undirected graph G (V,E) consisting of n nodes and an adjacency matrix A, (2) [E] compatibility matrices, where each matrix illustrates the dependency relationship berween pair of connected nodes, and (3) n k-ddiensional prior uncertainty vectors œz = 1...., n)), with each vector representing the uncertainty in prior beliefs for a node as interval widths across the classes. Find n k-dimensional posterior uncertainty vectors by (i=11 1,..., nt), where each vector represents the uncertainty of posterior beliefs for k classes of a node based on interval width, with wider interval indicating higher uncertainty.
3

---

12
Hg
Irputs
Outputs
H2
E, Bg
H
V6C(B)
vec(E)
+
DiageV
vec(E)
Figure 2: An illustration of Lin UPop quantifying uncertainty in posterior belief's for each node in 3-node chain. Inputs: (1) Uncertainty in prior heliefs of each node represented interval widths (#1.02.003) (2) Edge potentials 1H and Hg3, with H21 12 H32 H23 due to the undirected graph). Outputs: uncertainty in posterior beliefs of each node also represented as interval widths. LinU/Prop can set a diffcrent compatibility matrix for each edge, allowing to handle edge-dependent potentials, while previous methods cannot do this.
Linear Bound Propagation
Recall that our objective quickly quantify the uncertainty in posterior beliefs and not assume that neighbors necessarily reduce uncertainty, in order to avoid uncertainty underestimatiin. Interval arithmetic [6] is non-probabilistii method for quantifying uncertainty without assumptions regarding neighbors. However, it is unclear how to directly apply interval arithmetic rules to Eqs. 2 3) of BP
while meeting the above objectives.
A solution to these challenges lies in linearization. The linearized BP is more amenable to interval arithmetic due its exclusive reliance interval addition, sidestepping the interval multiplication that may underestimate uncertainty. Consequently, this facilitates the derivation of closed-form solution, endowing the method with linear scalability, interpretability, and guaranteed convergence.
We will next introduce LinUProp and its iterative variant, which computationally efficient in practical applications. Prior to that, need some additional notation pertinent to LinUProp. Let vec denotes the operation that vertically concatenates the rows of a given matrix into a single column vector, and let Diag denote the transformation of nk x k block matrix into block diagonal matrix. E [01. Ø2 e,," and IB [b1, b...... b,,' respectively represent the uncertainties of prior and posterior beliefs for all n nodes, each of dimension n x k. Q is an nk x & matrix formed by vertically stacking n identity matrices, each of size k x k. V and L nk x nk block matrices formed from H and H respectively. For any given edge (s, t), H denotes the centralized compatibility matrix corresponding to that edge, with entries H defined as A (i.j)
(i. 1 In cases where the edge (s, t) does exist, the matrix defaults zero.
L
H
H
Diag
V
Ln
L
H
H
A
Theorem 3.1 (LinUProp). For multi-class node classification task MRF, given the matrix E which represents the prior belief uncertainty of all nodes, matrices w and V which denote the dependencies among these nodes. The posterior belief uncertainty for all nodes, represented by IB and in terms of interval widths, is determined by the linear equation system:
vec BB] vec(IE) 1
Diag
T (22)) IIC
(6)
Figure 2 illustrates Eq. 6 using 3-node chain example. From this, it can be observed that LinUProp can be implemented using matrix multiplication without computing the uncertainty propagated between each pair of nodes. In practice, more effective strategy for computing the

---

posterior belief interval widths vec(IB) is to use an iterative update version of Prpp
vec (++1)
vee
Vr +
Diag V2Q) vec(IB)()
(7)
where denotes the iteration round and vee IB (0) can set to (E) Although Eq. (6 similar in form to another method, LinBP (Eq. (33)
which is point estimation inference approach rather than UQ method, simply replacing prior and posterior beliefs in LinBP with interval widths does not yield LinUProp. LinUProp is specifically designed to quantify uncertainty through derivations involving the upper and lower bounds of messages and beliefs. For detailed derivations, please refer to Appendix A.I Its guaranteed convergence is proven in Sec. 4.1 The proof of its linear showing that the time complexity per iteration O(VV))
scalability is provided in Appendix AA.3 A.33
when [V] > |8). otherwise O(E))
4 Analysis
We present theoretical analyses of LinUPrrp, including the derivation of a closed-form solution, the proof of its convergence, and the provision of an interpretable approach to the uncertainty quantified by Linp Furthermore, by employing the bias-vate variance decomposition, we addressed the question of what the uncertainty computed by LinUProp represents and established the connection between this uncertainty and the expected prediction error.
4.1 Theoretical Analysis of LinUProp
Closed-form solution. By simplifying Eq. (6). we can derive closed-fore solution for LinUProp:
vec(IB) = (I V Diag V (2Q))² vec vIc(
(8)
where I represents the identity matrix. This closed-fome solution is primarily used for subsequent theoretical analysis; in practice, the iterative version Eq. 7 employed, which does not require the computation of the matrix inverse.
Convergence. Let Vi + Diag Q)QQ) be denoted as T. The sufficient and necessary criteria for the convergence of LinUProp that the spectral radius of T is less than I:
LinUProp converges
P(T) <1
Proof. The closed-form solution of LinUProp (Eq. (8) conforms to a general linear equation system, y (I - P where y, P, and generic terms. Such linear equation systems can be solved by the Jacobi method [29], which converges and only if the spectral radius of is less than D
From the above convergence condition, LinUProp has limitation: in large graphs with strong global (most edges) homophily/heterophii,, p(T) may be large, leading to non-convergence. However, LinU/Prop still converge if such strong homophily/hheerrohhlly is only local (a few edges).
Interpretability. When LinUProp converges, with p (T) < 1, we can expand the closed-form solution Eq. 8 using the Neumann series, yielding:
vec(IB) (I T T + +...) (IE).
(10)
The uncertainty of the posterior belief for certain class of a node, vec(IB), can be expanded as vec = vIc(IE), + T, Vec + (T²), vec(IE) +
(11)
where Ty (E), (T²), vE)( etc. can be expanded to Σn To, vec(E)
En (T²) w,w ... and so on, the subscript represents the e-th row of matrices T, while the subscript w represents the w-th column matrices T, T. and the with component of IIc Finally, we derive the contribution of the prior uncertainty of a certain class of any other variable node vI) towards the posterior belief uncertainty vec(BB) as
Cw-+y T Te. Vec(IECCC)))) + (T²)...
v. vIe(IE),, + ((T)) w.w vec w
(12)
5

---

This linear equation facilitates simple explanations of the uncertainty computed by LinUProp. Since P(T) 1 ensures convergence. the influecce of higher-order terms, such as T and T decays rapidly. Therefore, in practice, considering only the first few terms often provides accurate and interpretable estimate uncertainty contributions.
4.2 Theoretical Connection with Bias-Vase Variance Decomposition
To delve into the theoretical understanding of the uncertainty in the node's posterior belief, we employed the bias-variance decomposition (2), effective tool for analyzing prediction errors and decomposing model uncertainty [41]. We demonstrated that the posterior uncertainty computed by LinUProp generalized variance component of the expected model prediction error, giving LinUProp solid theoretical basis. This relationship between the uncertainty computed by UQ methods and the expected model prediction error has seldom been explored by existing work 7 36
35 To begin with, we first derive linearized BP suitable for edges with distinct potential functions facilitate varianee decomposition.
From the update equation of message m., as shown in Eq. 4 we can derive the update rule for the reverse message m and substitute back. This leads us the stable message tins when the algorithm converges. By inserting the stable message into Eq. ( and simplifying, we can derive the closed-form solution for posterior beliefs where each edge has a distinct potential function (detailed proof in Appendix(A)
vec B) = 1 + Diag L2 22Q))
vec vec(E),
(13)
F
Hn
A
H
H
V
L
F
where vec and Diag are the same as those in Eq. [ēi, e2. e,,"" are n matrices composed of the centralized posterior and prior beliefs of all nodes. Q is an nk x k matrix formed by vertically stacking n identity matrices, each of size k x k. T and 222 are nk x nk block matrices formed from H,, and Ar respectively. For any given edge (s, 1). H., denotes the centralized compatibility matrix corresponding to that edge, with entries H,, defined as (i, = Hi,(i,)) :. If the edge (s, does not exist, the matrix defaults to zero.
6
B [b,, by b I and
This closed-form solution shows that the posterior belief can be regarded as a linear model of the prior belief. Specifically, consider the element vec(B).. e. This element represents the centralized posterior belief of a specific class corresponding to particular node. It is formulated combination of all centralized prior beliefs, represented by F vec Here, F. denotes the e-th row of F. This linear equation enables us to derive a bias- bias-variance variance decomposition of the uncertainty the posterior belief. We define for particular node in an unknown true linear model, and represent the centralized belief about E computed using Eq. 13 as vec(B).. Then, the expected model prediction enror can be decomposed into bias and variance as
linear
(EE) as the centralized posterior belief corresponding to a specific class
- vec (B)))))) (((É)) - E vee (B). +
((vec()) - vee(B), 1)
(Bias)?
Variance
(14)
Expanding the variance term yields
E (vcc(B), [B(ve((B)...)
F.E EvE F".
(15)
where Exec(E) is the covariance matrix vec(E) (proof in Appendix A.4p. we assume that the priors of different nodes and class probabilities within each node's prior are nearly independent, (i can be approximated as diagonal matrix. Consequently, the sign of the elements in F,

---

will not affect the result of Eq. (15) Ignoring the small term Diag(-), the variance component can be approximated as F v F The posterior interval width for e computed by LinUProp is Ve, F (EE) leading to vee . (vec(IB))) that the variance component is a special case of LinUProp where the outer product of the prior interval width vecc is the covariance matrix (ve((b) In other words, the uncertainty computed by LinUProp is generalized variance component of the expected prediction error.
This implies
5 Experiments
We begin with simple case study to illustrate the correctness and interpretability of quantified uncertainty. then present quantitative evidence of our method's ability to accurately quantify uncertainty, and demonstrate the convergence and scalability of our methods on real-world datasets. Finally, we compare the efficacy of LinUProp to other competitors in graph active learning tasks.
5.1 Case Study a Simple Graph
Correctness of quantified uncertainty. To verify the correctness of the uncertainty quantified by LinUProp for posterior beliefs, we first qualitatively analyze the belief bounds on simple graph. Specifically, we conduct the experiment 4 x4 x grid, as shown in Figure 3 Ba), with priors set to
Average Bellef Bound Wilth
(a)
0.8
0.5
0.4
0.3
0.2
2
Iterations
(a)
(b)
(b)
Figure 3: Case Study. (a) A 4x4 grid with two classes. The nodes colored in red and green are labeled, while the rest are unlabeled. The bold unlabeled node indi- cates the node we aim to explain the source of uncer- tainty. (b) An interpretation of the uncertainty in the helief of the hold node computed by LinU/Prop. The colors represent the contribution of each node the uncertainty of the bold node, with warmer colors in- dicating more significant contributions; the radius of the white circles indicates the belief hound width com- puted by Lin LinUPro for each node, with larger radius indicating higher uncertainty the belicfs.
0.04
Time in
Cora
0.02
Citesser
Pubmed
PolBloge
0.00
20000 Number of Edges
Figure 4: (a) Convergence average belief bound width by LinUProp. (b) Scalability. Each data point represents the running time of LinUProp for 10 itera- tions with certain number of edges. The y-axis the running time seconds.
B(9, 1) (red nodes) or B(1, 9) (green node) for labeled nodes, and B(1, 1) for the unlabeled nodes. We use Beta distributions as priors in binary classification because they are a natural choice for binary random variables 2 For each variable node, the prior interval width for each class is set to twice the standard deviation of the corresponding prior Beta distribution. For each edge, the compatibility matrix is set in Eq. ( with 0.1.
Figure (b) shows that the more labeled nodes around each node s, the smaller the uncertainty in the belief; the more unlabeled nodes around s, the larger the uncertainty in the belief, which is intuitive. In addition to the qualitative analysis mentioned above, we also compared the uncertainty quantified by LinUProp with that quantified by MC simulations. MC simulations are adopted as the ground-truth due its ability to provide accurate approximations through a sufficient amount of sampling (30). which are feasible for small-scale graphs. The experimental results show strong positive correlation between the uncertainties quantified by the two methods (PCC=0.9084), which can be found in Appendix B.I
7

---

Interpretability. By Eq. (2). we can compute the contribution of any node t to the uncertainty in the belief of node computed by LinUProp. Figure(3]b) shows that the main source of uncertainty for the bold node is itself because it is an unlabeled node. The unlabeled nodes in the neighborhood are the secondary sources, and the unlaheled nodes within hops are the tertiary sources. demonstrates that the uncertainty in the beliefs quantified by LinUProp has good interpretability, which can enhance users' trust in UQ results computed by LinUProp.
5.2 Experiments on Real Data
We validate the properties of LinUProp on three popular citation networks (Cora, Citeseer, and PubMed) [8] and a political blog hyperlink network (PolBlogs) [T] For further details regarding these datasets and experimental configurations, please refer to Appendix B.2 Our experimental findings can be summarized into the following three aspects.
Convergence. We set node priors based on classification type: Beta distributions for binary and Dirichlet distributions for multi-class (kc classes), both using parameter vector a of length k. In datasets, 30% of nodes are randomly labeled; if labeled as class i, a; 10, otherwise, entries are 1. Unlabeled nodes have = 1. Prior interval widths for each class are twice the standard deviation of the distribution, capturing uncertainty by representing the interval as ttd.
To simulate the diversity of dependencies between nodes, each edge's e is randomly selected from lee4,, 5e-4, Ie-3, 5e-3, le-2] and linked I. + (k= 1)e, and other elements are g e. We monitor LinUProp 's convergence (iterative version
k x k compatibility matrix. Diagonal elements are
in Eq. 7 by measuring the average belief bound width, Σp=1 E q=1 (p. B(p.q)/(rx k).
Figure aa shows that LinUProp converges within 10 iterations across all four datasets, demonstrating its rapid convergence. Using an iterative update version of LinUProp, the posterior belief bound width for each node increases over iterations due uncertainty propagation from other nodes.
Scalability. We initialize the prior interval width for nodes and the compatibility matrix for edges following the same procedure as in the convergence experiment. Then we uniformly sampled different numbers of edges from four datasets and recorded the running time of LinUPrrop for 10 iterations. Figure (b) shows that the running time scales linearly in the number of edges. For more details on the runtime comparison between NETCONF and LinUProp, please refer to Appendix B.4
Effectiveness. For large-scale graphs, MC sampling is computationally impractical due to the signifi- cantly increased time required for each sample. Therefore, we evaluate LinUProp's ' effectiveness using active learning as a downstream task. Specifically, we use uncertainty-basse sampling to select the next node for label acquisition, as detailed in (23]. In this context, users seek labeled dataset with minimal uncertainty, maximum accuracy, and minimal labeling budget.
We simulate realistic scenario as in 40) using training set Virain, validation set Veal, test set Vrest, and unlabeled pool Vutp (node numbers in Table [ Appendix [B.2). with query batch size b. Initially, training set nodes are labeled and others are unlabeled. Node priors follow the convergence experiment procedure. Edge compatibility matrices match the correctness experiment, enabling comparisons with existing methods that cannot handle diverse potential functions. Due to noisy labeling, the unlabeled pool remains unchanged to allow re-labeling [BI]
For each selected node s, we update its Dirichlet prior by incrementing the parameter for the given label class by 1. After each labeling iteration, all nodes undergo inference. Noisy labels may not guarantee improved inference accuracy, so we use the iteration yielding the highest validation accuracy to evaluate the test set, which determines the test accuracy for the current labeling budget. MC-based methods are unsuitable for active learning as it requires time-consuming sampling for each iteration. We use the following strategies in each iteration:
Random: Select nodes randomly.
Least Confidence (L.C): Calculate uncertainty as (L = argmax, b, (d).
Entropy: Calculate uncertainty as Unntropo (s) = Σ, b, (t) (1).
Certainty Score (CS): Let 6, be the parameter vector of the posterior Dirichlet distribution of node & inferred by NETCONF 77. Uncertainty is Ucs(s) - E, (i). Due to assumptions on distribution forms of priors, messages, and posterior beliefs, only applicable with NETCONE.
8

---

[100%][orr
[100%) [Citeseer]
[100%] [PubMed]
[100%] [PolBlogs]
70
45
70
Test accuracy(%
85
60
40
60
80
65
35
50
Random
70
80
30
Entropy
25
30
46
LC+BB
50 100
25
50
75
100
125
20
40
60
10
20
30
40
Size of labeling budget
Size of labeling budget
Size of labeling budget
Size of labeling budget
Figure 5: Test accuracy for varying labeling budgets with BP inferring posterior beliefs. Each subplot title includes two components, which represent the labeling accuracy and dataset. Each column corresponds to dataset. each subplot, the node selection strategies based on LinUProp and its variant are represented by red and purple A. Under the same labeling budget, the higher the test accuracy, the better.
[10%)][ooal
[100%] [Citaseer] [100s]Cittseer]]
[100%] [PubMed]
[100%] [PolBlogs]
80
70
45
86
Random
Test accuracy
85
60
40
60
80
LC
Entropy
68
70
60
50
LC
86
30
45
40
LC+GS
40
50 100
25
25
75
100
125
20
46
02
3G 40
Size of labeling budget
Size of labeling budget
Size of labeling budget
Size of labeling budget
Figure 6: Test accuracy for varying labeling budgets with NETCONF inferring posterior beliefs. Each subplot title includes two components, which represent the labeling accuracy and datasct. Each column corresponds to dataset. In each subplot, the node selection strategies based LinUProp and its variants are represented by and purple 4, while the strategies based on the native UQ method NETCONF and its variants are represented by brown 4 and pink > NETCONF-based strategies (CS/LC++CS) often prioritize labeling low-degree nodes due to their assumption that neighbors serve as evidence, leading to persistent high uncertainty in most nodes and slowly increasing accuracy. Under the same labeling budget, the higher the test accuracy, the better.
Belief Bound (BB): Based on LinUProp with the same prior bound width setting as in the convergence experiment, uncertainty (BB =b..
LCC+S::
Perform Min-Max normalization on ULc(s) and UCS(s) to obtain Uperm(s) and USS Unorm (s). Uncertainty is (LC-Cs(s) = Uhe
Umorm (s) + UCS Unnorm (s).
LC+BB: Combine LC and BB. Compute uncertainty as: ULC+BB(S) (s BB (s).
We set query batch size 6 = 2k (k is the number of classes) and maximum labeling budget to 206. We evaluate node selection strategy performance with annotator labeling accuracy at 70%, 80%, 90%, and 100%. To reduce randomness in results, we repeat each method ten times (re-partitioning datasets and changing random seeds) and record the mean of test set inference accuracies. To demonstrate labeling budget impact, we conduct experiments evaluating various node selection strategies under different labeling budgets on four datasets, varying the budget from 2b to 20b.
As shown Figures 5 and [6] whether using BP or NETCONF for inference, the test accuracy of the LinU/Prop-based node selection strategy (BB) and its variations (LC++B)) generally grow faster than other basclines as the budget increases. This is especially the case when compared to the native UQ method in NETCONF (CS) and its variations (LC+CS). As shown in Figure 6 strategies based on NETCONF (CS/LC+CS) prioritize labeling low-degree nodes due to their inherent assumption that neighbors necessarily reduce the uncertainty. As result, nodes with many neighbors are often mistakenly viewed as having low uncertainty and are left unlabeled, which further leads to high uncertainty in the majority of nodes. This phenomenon is more pronounced in graphs with large number of low-degree nodes, like PolBlogs, leading to a very slow increase in accuracy. Experiments with lower labeling accuracy yielded similar conclusions, shown in Appendix B.3.1
We also evaluate all strategies under a fixed labeling budget of 20b for a fair comparison, with results displayed in Appendix B.3.2 The conclusion is that whether using BP or NETCONF for inference,

---

BB and LC+BB outperform baselines across different labeling accuracies and datasets in most cases. From the results in active learning tasks, we see node selection strategies guided by LinUProp's UQ results achieves higher labeling accuracy with lower labeling budget. This indicates that uncertainty quantified by LipUProp is accurate, effective, and insensitive to the inference method.
Related Work
Uncertainty in posterior belief. In addition to traditional UQ methods like MC simulations, which require extensive sampling, some research focuses on modeling uncertainty in posterior belief by deriving closed-form solutions to incorporate uncertainty into inference results. Existing methods 7,36 35] exhibit scalability but limited as they assume uniform potential functions across all edges. Furthermore, these methods with closed-form solutions assume that any neighbor of node will necessarily reduce the uncertainty even neighbors affected by noise or lacking information, potentially leading uncertainty underestimation. Moreover, few existing studies have theoretically linked calculated uncertainty to the expected model prediction error, making it difficult for decision-maken understand and trust the UQ results.
Existing works [22 20 utilize bound propagation without the aforementioned assumptions regarding neighbors. However, they focus quantifying the error between the posterior beliefss and the true marginal probabilities of the variable nodes, rather than quantifying uncertainty. This fundamen- tally differs from LinU/ropp, which quantifies the posterior uncertainty the generalized variance component of the expected prediction error.
Human understanding of PGM inference. Humans are unlikely to adopt inference outcomes without reasonable interpretation K3 In [24] the authors studied explainable Bayesian networks. Recently, explanations of inference on Bayesian network and MRF were found by differentiation 33 so that a set of important network parameters (potentials) can explain the changes in the inferred posterior distribution of target variable. Interpretable graphical models are also studied under the hood of topic models [ or GNN [38]. None of the aforementioned studies can provide an explanation for the uncertainty in the inference results.
7 Conclusion
In this paper, we proposed LinUProp, a UQ method for graphical model inference that utilizes a novel linear propagation of uncertainty model uncertainty among related nodes additively. LinUProp provides linear scalability, guaranteed convergence, and is interpretable. Unlike its competitors, LinUProp does not assume neighbors necessarily reduce uncertainty and thus avoids uncertainty underestimation. To gain deeper insights, we decompose the expected prediction error of the graphical model and prove that the uncertainty computed by LinUProp the generalized variance component of the decomposition. Experimental analysis shows LinUProp possesses aforementioned properties and outperforms competitors in downstream tasks. However, the study has not yet explored the interpretability of uncertainty with human involvement in real-world decision-making processes, an area we aim address in future research. We would also like apply LinUProp to more applications of graphical models to demonstrate its utility in the future.
Acknowledgments and Disclosure of Funding
Chenghua Guo and Xi Zhang were supported by the Natural Science Foundation of China (No. 62372057). This material is based upon work supported by the National Science Foundation under Grant Number 200815 1008155. Sihong Xie was supported in part by the National Key R&D Program of China (Grant No. 2023YFF0725001). the Baannghou-HKUSTTCE No. A03J0008, and Education Bureau of Guangzhou Municipality. Qi Li was supported in part by the National Science Foundation under NSF Grants IIS 2007941. Chao Chen supported by the National Key Research and Development Program of China (No. 2023YFB31065044 and Pengcheng- Chaic Mobile Jointly Funded Project (No. 2024ZY2B0050).
Joint Funding Program (Grant
10

---

References
[1] L. A. Adamic and N. Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36-43, 2005.
[2] C. M. Bishop and N. M. Nasrabadi. Patlern recognition and machine learning. Springer, 2006.
[3] H. Chan and A. Darwiche. Sensitivity analysis in markov networks. In IJCAI, 2005.
[4] J. Chang. J. Boyd-Graber, C. Wang, S. Gerrish, and D. M. Blei. Reading tea leaves: How humans interpret topic models. In NeurIPS, 2009.
[5] A. Darwiche. A differential approach to inference bayesian networks. Journal of the ACM (JACM), 2003.
[6] H. Dawood. Theories of interval arithmetic: mathematical foundations and applications. LAP Lambert Academic Publishing, 2011.
[7] D. Eswaran, S. Günnemann, and C. Faloutsos. The power of certainty: A dirichler-multiioniial model for belief propagation. In SDM. SIAM, 2017.
[8] D. Eswaran, S. Günnnemann, C. Faloutsos, D. Makhija, and M. Kumar. Zoobp: Belief prop- agation for heterogeneous networks. Proceedings of the VLDB Endowment, 10(5):625-636, 2017.
[9] A. Farasat, A. Nikolaev, S. N. Srihari, and R. H. Blair. Probabilistic graphical models in modern social network analysis. Social Network Analysis and Mining, 5:1-18, 2015.
[10] H. Gao, Pei, and H. Huang. Conditional random field enhanced graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 276-284, 2019.
[11] W. Gatterbauer, Günnemann, D. Koutra, and C. Faloutsos. Linearized and single-pass belief propagation. Proceedings of the VLDB Endowment, 2015.
[12] S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, (6):721-741, 1984.
[13] W. R. Gilks, S. Richardson, and D. Spiegelhalter. Markov chain Monte Carlo in practice. CRC press, 1995.
[14] J. Ha, S.-H. Kwon, S.-W. Kim, C. Faloutsos, and S. Park. Top-n recommendation through belief propagation. In Proceedings of the 2 ACM international conference on Information and knowledge management, pages 2343-2346, 2012.
[15) Z. Hu, G. Wu, S. Mitra, R. Zhang, T. Sun, H. Huang, and V. Swaminathan. Token-level adversarial prompt detection based on perplexity measures and contextual information. arXiv preprint arXiv:2311.11550
2023.
[16] Y. Jin, M. Carman, Y. Zhu, and Y. Xiang. A technical survey on statistical modelling and design methods for crowdsourcing quality control. Artificial Intelligence, 2020.
[17] M. I. Jordan, Z. Ghahramani, S. Jaakkola, and L. K. Saul. An introduction to variational methods for graphical models. Machine learning, 37:183-233, 1999.
[18] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICML, 2017.
[19] S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, 1988.
[20] M. Leisink and B. Kappen. Bound propagation. JAIR, 2003.
[21] Lindsten, J. Helske, and M. Vihola. Graphical model inference: Sequential monte carlo meets deterministic approximations. Advances in Neural Information Processing Systems, 31, 2018.
11

---

[22] J. M. Mooij and H. Kappen. Bounds on marginal probability distributions. NeurIPS, 2008.
[23] V.-A. Nguyen, P. Shi, J. Ramakrishnan, N. Torabi, N. S. Arora, U. Weinsberg, and M. Tingley, Crowdsourcing with contextual uncertainty. In Proceedings of the 28th ACM SIGKDD Confer- ence on Knowledge Discovery and Data Mining, KDD '22, page 3645-3655, New York, NY, USA, 2022. Association for Computing Machinery.
[24] S. W. Norton. An explanation mechanism for bayesian inferencing systems. In UAI, 1986.
[25] J. Ok, S. Oh, J. Shin, and Y. Yi. Optimality of belief propagation for crowdsourced classification. In ICML, 2016.
[26] S. Pandit, D. H. Chau, S. Wang, and C. Faloutsos. Netprobe: a fast and scalable system for fraud detection in online auction networks. In WWW, 2007.
[27] J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan kaufmann, 1988.
[28] M. Qu, Y. Bengio, and J. Tang. Gmnn: Graph markov neural networks. In International conference machine learning, pages 5241-5250. PMLR, 2019.
[29] Y. Saad. Iterative methods for sparse linear systems. SIAM, 2003.
[30] S. S. Sawilowsky. You think you' ve got trivials? Journal of Modern Applied Statistical Methods, 2:218-22 225, 2003.
[31] V. S. Sheng, F. Provost, and P. G. Ipeirotis. Get another label? improving data quality and data mining using multiple, noisy labelers. SIGKDD, 2008
[32] H. J. Suermondt. Explanation in Bayesian networks. Stanford University, 1992.
[33] R. L.. Teach and F. H. Shortliffe. An analysis of physician attitudes regarding computer-based clinical consultation systems. Computers and Biomedical Research, 1981.
[34] R. Tutunov, Grosnit, J. Ziomek, J. Wang, and H. Bou-Ammar. Why can large language models generate correct chain-of of-thoughss?? arXiv preprint arXiv:2310.1333 13571, 2023.
[35] Y. Yamaguchi, C. Faloutsos, and H. Kitagawa. Socnl: Bayesian label propagation with confi- dence. In Advances in Knowledge Discovery and Data Mining: 19th Pacific-Asia Conference, PAKDD 2015, Ho Chi Minh City, Vietnam, May 19-22, 2015, Proceedings, Part 19, pages 633-645. Springer, 2015.
[36] Y. Yamaguchi, C. Faloutsos, and H. Kitagawa. Camlp: Confidence-aware modulated label propagation. In Proceedings of the 2016 SIAM International Conference on Data Mining, pages 513-521. SIAM, 2016.
[37] X. Yang, Y. Guo, and Y. Liu. Bayesian-infferecce--ree recommendation in online social networks. IEEE Transactions on Parallel and Distributed Systems, 24(4):642-651, 2012.
[38] Z. Ying, D. Bourgeois, You, M. Zitnik, and Leskovec. Gnnexplainer: Generating explana- tions for graph neural networks. In NeurIPS. 2019.
[39] J. Yoo, S. Jo, and U. Kang. Supervised belief propagation: Scalable supervised inference on attributed networks. In 2017 IEEE International Conference on Duta Mining (ICDM), pages 595-604. IEBE, 2017.
[40] W. Zhang, Y. Wang, Z. You, M. Cao, P. Huang. J. Shan, Z. Yang, and B. CUL Information gain propagation: a new way to graph active learning with soft labels. In ICLR, 2022.
[41] X. Zhou, H. Liu, F. Pourpanah, T. Zeng, and X. Wang. A survey on epistemic (model) uncertainty in supervised learning: Recent advances and applications. Nearocomputing, 489:449-465. 2022.
12

---

A Proofs
A.1 Proof of Theorem 3.1
Let vec denotes the operation that vertically concatenates the rows of a given matrix into single column vector, and let Diag denote the transformation of an nk x k block matrix into a block diagonal matrix. E [01. 02, e,,] and IB = [b1, b., b,,]" respectively represent the uncertainties of prior and posterior beliefs for all n nodes, each of dimension n x Q is an nk x & matrix formed by vertically stacking n identity matrices, each of size k x k. V and &2 are nk x nk block matrices formed from H., and H respectively. For any given edge (s, t), Ha, denotes the centralized compatibility matrix corresponding to that edge, with entries H defined as Hf (i. (i) # In cases where the edge (s, 1) does not exist, the matrix defaults zero.
L
H n
In
H
Diag
Ln
L
Theorem 3.1 (LinUProp). For a multi-class node classification task on an MRE, given the matrix EE which represents the prior belief uncertainty of all nodes, matrices V and V2 which denote the dependencies among these nodes. The posterior belief uncertainty for all nodes, represented by B and in terms of interval widths, is determined by the linear equation system:
vIc vec(IE) - (vi Diag
V2Q) vec(IB).
(6)
Proof. Based on the linear approximation of BP messages defined in Eq. (4). the lower and upper bounds of BP messages using interval arithmetic rules 6
we can approximate
mis (t) t k Σ Ha (1.5) (i),
(16)
mrs (i) k Σ
Ml (1.5) (i),
(17)
8 (1) {
{ b7 (j) $ m (i),
it (i.j) 0
(18)
bt (j) काक (i),
(i.j) <00
804 (1) { () 1 m ())
(1), A (i.5)
(19)
67 (1) - m (i). 1 (i.j) >
The idea behind Eqs. (6 19) is that the determination of the lower and upper bounds of (1) is contingent upon the sign of Har (i. Specifically,, when determining the lower bound of miz (i), if j) < O, then (i) should be maximized, i.e., taking its upper bound b, (j) 1 1 (j);
(i, > 0, then (i) should be minimized, i.e., taking its lower bound 6, (j) m (i). A
similar idea applies to the computation of the upper bound of vites (i). Then by subtracting Eq. [16)
from Eq. 17). we obtain the interval width (1) to reflect the uncertainty of (i):
mas (i) + k Σ Hes (i.5) (b. + m
(20)
where bb the interval width vector reflecting the posterior belief uncertainty at node i, as defined in the "Problem Definitions" of Sec. 2 Eq. (20) leaves only the interval width, making the specific location irrelevant for subsequent steps. Thus, LinUProp is also unaffected by the exact location of the interval. Similarly, the uncertainty of the message in the opposite direction can be quantified by interval width as:
Mat (i) + A: Σ Mas (i.5) (bolG) + + mmml
(21)
13

---

Substituting Eq.
21
into Eq.
200 leads to
Ha. (1, (De()) + Σ Ha (g. ((b(()) + m)a(()))
k
(22)
When the algorithm converges, all messages are at stable state, so we can treat mys on both sides of Eq. (2) as equal and replace the update formula with the equation:
mea (i) Σ He (i.5) Σ HH (g.5) (g)
(23)
k > Hust (b.5)(b,(i + k Σ lftec (i.5)
Σ HHst (g.5) (b(g).
Let us denote (i.) - t as H (t. j). then the stable state message bound can be simplified as:
(I H m.y kH b. + K
mye k(I-HH3 Hb,
(24)
where the message bound width, denoted as mys, and the posterior belief bound width of nodes and i, denoted as b, and b; respectively, are all k-dimensional vectors. Then the interval width b. reflecting the uncertainty of posterior belief b, can be calculated by subtracting its lower bound b, ē, + EiEN(a) m, from its upper bound b eg + EiEN(e) m
b, e, + K
Σ
mas
(25)
REN())
where @, is the prior bound width vector with k-dimensional. Then plugging Eq.
24 into Eq.
25
b. = e Σ ( H b, +
-
Σ (EN(s)
(I (I- "H....
(EN(G)
Due to H being the centralized matrix, (I H so I, then (I H
H ~o H and we get
b = e, +
Σ H b, +
H&
(26)
(EN(ss
tEN(s)
By using the matrices introduced at the outset of this section, Eq.
26 can be rewritten as Eq. 6
A.2 Proof of Eq. (13)
Proof. Based on the linear approximation of BP messages (Eq. we can similarly get mm
mg (i)
> 1=1
As (i,
6. (i) mise ())
(27)
Substituting Eq.
27 into Eq.
leads to k Σ
Muo
Hse (i,5) (b.6))
1 Em (g.5) (b.(g) - ()))
(28)
When the algorithm converges, all messages are at stable state, so we can treat th, on both sides of Eq. (28) equal and replace the update formula with the equation:
mrs (i) Σ Ha (i. Σ Hot (9.5) ())
(29)
k Σ Hat H.
(i.1)).()) Σ Mas (i. E (g.3))))
This stable state message can be simplified as:
(I H2 m = kH kH? b.
m kII H2) - H (b. H.).
(30)
14

---

Then plugging Eq. 30 into Eq.
5
b, = é +
(I- H ---
Hag by + Σ (I-H,,
H²r)) ( HH,.,..
(=V())
(EV(s)
Due to Hot being the centralized matrix, (I-H,)) ~ I, then (I H2 -1 Hoe 2 His and we get
b, = è, +
H b, +
H.
(31)
(EV(s)
(EN(s)
By using v and 22 introduced at the outset of Sec.
4.2
Eq.
3
can be rewritten as Eq.
13
H
H
H
H
V
V
2
H
Hon
H
H
m1
A.3 Proof of the Linear Scalability of LinUProp
Proof. To demonstrate the linear scalability of LinUPrrp, we will start with the time complexity analysis of the iterative version of LinUProp (Eq. 77):
vee B (++1) vec(IE) + ( Diag (2)0)) vee ())
Before the iteration starts, vec and v + Diag( V2Q) (denoted as T) are known and fixed as input. In the 1-th iteration, we need to compute the matrix-vector multiplication T rec(B) ()))) and then add the result to vec(E). Since to simplify the computation. The number of non-zero elements in T is k2 ([E) [V]). where [ε] is the number of edges, |V] is the number of nodes and is the number of node classes. Then the time complexity of T vec ()) (1) is O(k2 ([ε) + +)))). Adding this result to vec (E.) has complexity of (l)))). Therefore, the time complexity of each iteration of LinUProp is O (1& + (V]) + A V)).
block sparse matrix, we can use sparse matrix operations
From this, we can conclude that the time complexity ((V)) when | [8), otherwise ((E)
which reflects the linear scalability of LinUProp.
A.4 Proof of Eq. 15
In order to expand the variance term, we first apply the property of variance, which states that the variance of a random variable is equal to the difference between the expected value of its square and the square of its expected value. Next, we substitute the linear function vec(B), = F. vEo(E) into the equation and appropriately expand the squared terms. Following this, we manipulate and simplify the terms using the properties of expectation and matrix operations. At this point, we factor out the linear function's coefficient vector F,,. The resulting expression includes the covariance matrix the random vector, denoted as Ev Finally, we present the concise form of the expression, which demonstrates the linear relationship between the variance term of each node and the prior covariances of all nodes. The detailed proof steps are provided below:
E
vec(B)) - (e[vve((B..)
(vec)B)).)
(I [Bcc
F
E F vev) 2
E
Fu vec
E)) (E)
E F (e)) )"
E
F, vec
E vee
2 Fz
EE vec E)
E (vec(B))) ) T F.
F,
vec
FT F. ()c((
E vec((E)) T
F.
E
(e)
- vec((E)
F.
F (e0 F..
15

---

B
Additional Details and Results
B.1 Quantitative Validation of Correctness on a 4x4 Grid
We also quantitatively verify the correctness LinUProp by comparing with the uncertainty computed by MC simulations 4 x grid. Specifically, we first sample prior beliefs based on the prior distributions of each node, and then run BP to infer the posterior beliefs of each node. After repeating the above sampling process for 100,000 times, the posterior belief of each node sampled as an estimation of the ground truth uncertainty.
the empirical standard deviation of
Figure 7 shows that the uncertainties quantified by MC simulation and LinUProp have strong positive correlation, as evidenced by Pearson Correlation Coefficient (PCC) of 0.9084 between the uncertainties obtained for all nodes using both approaches. This confirms the consistency of the uncertainty in the beliefs quantified by our method with that of MC simulation.
PCC=0.3084 (p=1.14e-06)
Ballef bound width by LinUProp
1.5
1.4
1.3
1.2
1.1
1.0
Std. bollef by MC
Figure 7: Correctness. The of the beliefs obtained by MC simulation (an estimation of ground truth uncertainty), and the y-axis is belief bound width computed by LinUPrup. In fact, there are 16 points in this figure, corresponding to the 16 variable nodes in Fig. B(.. Some points appear to overlap because they have similar uncertainties quantified by both methods. The Pearson Correlation Coefficient (PCC) between the uncertaintics quantified by the two methods is 0.9084, indicating a strong positive correlation.
represent UQ methods: the x-axis is the empirical standard deviation
B.2 More Experimental Details
Rumning environment. We conducted convergence and scalability experiments on the Apple M2 chip, and convergence experiments on a 2.2 GHz Intel Xeon CPU.
Datasets. Table shows the statistical information and partitioning of three citation network datasets.
Table 1:
Statistical information and partitioning of datasets. The subsets, Veraen. Veal and Veast sampled from the original node set. The remaining nodes in Vulp- We these subsets in the effectiveness experiments.
Dataset
#Nodes
#Edges
#Classes
#Verain
#V
# #Veest
Cora
2,708
5,429
7
14
500
1,000
Citeseer
3,327
4,732
6
12
500
1,000
PubMed
19,717
44,338
3
500
1,000
PolBlogs
1,490
19,090
2
250
500
16

---

B.3 More Effectiveness Results for LinUProp
B.3.1
Results under Varying Labeling Budgets with More Labeling Accuracy Settings
Test accuracy Test accuracy Test sociracyy Teat accuracy Sooraayyl 1o
(70% [Cora]
[80%] (Cora)
[90%] [Cora]
[100%) (Cora]
50
106
100
50
102
50
102
(70% [Cileseer]
[80%) [Cileseer]
[90%) [Citeseer]
[100%] [Cileseer]
180
125
[70%) [PubMed]]
[80%) [PubMec]
[90%)] [PubMed]
[100%] [PubMed]
(70%) [PolBlogs]
(80%) [PolBlogs]
[90%] [PaiBlogs]
[100%) [PolBlogs)
Rendom
LC
BB
10 20
23
30
14
20
Size labeling budget
labaling budget
Size laboiing budget
of labeling budget
Figure 8: Test accuracy for varying labeling budgets with BP inferring posterior beliefs using noisy labeled nodes. Each subplot title includes two components, which represent labeling accuracy and dataset, Each row corresponds to dataset, and each column corresponds to a labeling accuracy. In each subplot, the node selection strategies based on LinU/Poop and its variant are represented by red and purple A. Under the same labeling budget, the higher the test accuracy, the better.
Test accuracy Teat accurscy(%))
[70%] [Cora]
[80%] [Core]
[90%] [Cora]
[100%) [Cora]
50
50
100
100
50
100
50
103
(70% [Citeseer]
(80%) [Citeseer]
[80%) [Citasear]
[100%] [Citasner]
[70%] [PubMed]
[80%) [PubMed]
[90%)] [PubMed]
[100%] [PubMed]
Teat socuracy Test accurscy
22
20
40
60
(70%) [PolBlogs]
[80%) [PolBlogs]
[90%] [PolBlogs]
[100%) [PolBlogs)
Random
LG
Entraby
LG BB
labeling budget
labeling budgel
Size labeing budgel
LC+CS
Figure 9: Test accuracy for varying laheling budgets with NETCONF inferring posterior beliefs using noisy labeled nodes. Each subplot title includes two components, which represent the laheling accuracy and dataset. Each row corresponds node selection strategies based LinUProp and its variants represented by v and purple 4, while the strategies based the native UQ method NETCONF and variants are represented by brown and pink NETCONT-base strategies (CS/LC+CS) often prioritize labeling low-degree nodes due to their assumption that neighbors serve as evidence, leading to persistent high uncertainty in most nodes and slowly increasing accuracy. Under the same labeling budget, the higher the test accuracy, the better.
datasct, and each column corresponds to labeling accuracy. In each subplot, the
17

---

B.3.2 Results under fixed Labeling Budgets
Tables 2 and 3 show the mean test accuracies and standard deviations for a fixed labeling budget (206) with BP/EECCONF inference on noisy labeled nodes. LinUProp achieves the highest mean accuracy in 28 of 32 cases, consistently outperforming its competitors across all four datasets, two inference methods, and four labeling accuracies. While the performance improvements are not always statistically significant, Lin maintains lower standard deviations (below 7%) and avoids poor accuracy. In contrast, LC achieves only 55% accuracy on Polblogs in Table 3 while LinUProp consistently exceeds 80%. The Entropy method shows high standard deviations (up to 14%) on Polblogs, whereas Lip generally has more stable performance, as underlined in the results.
Table 2: Mcan test accuracies and their standard deviations for a fixed labeling budget (20b) with BP inferring posterior beliefs using noisy labeled nodes. Each cell shows the mean accuracy and standard deviation on the test set for different labeling accuracy and node selection strategies, on different datasets. BB and LC+BB are node selection strategies based on LinUPrup. Bold values indicate the highest mean accuracy. Underlined values emphasize the method with the lower standard deviation between the LinUProp winner and the non-Lin UProp winner. Superscripts indicate sigmificant superiority between the LinUProp winner and the non Pro- winner
(pairwise t-test at a 5% significance level (*), 10% significance level (t)).
Dataset
Random
L.C
Entropy
BB
LC+BB
100%
66.900++1
18
66.590 3.855
60.270++2.451
68,380
1.130
90%
63.280:1:2.66 2.66
63,560++3,463
63.060-3.640
58.230::2.450
65.140=1..748
Cora
80%
60.130:13.031
60.230::37664
60.880=3.894
57.010:12.221
59.970:13.378
70%
56.400-+22.352
56.950++3.798
57.570 -3.793
53.910-+4,266
54.880++-55502
100%
41.450::1.370
39.580-1..26
10.790=1.957
42.1801221444
44.360-1..337
90%
39.120=t1.50
28.200
38.420=3.069
1..570+
41.860+2.669"
Citeseer
80%
37.130+t1.99 1.920
35,560++3,482
36.610-2.678
38.470=+2,410
40.360++2.516
70%
34.600:t1.80
33,990
33.220=3.160
36.800+:2,426
37.340+2.118*
100%
56.360:1:..270
53,440
57.350
1..030=:1.057
1..030
90%
54.070:155003
52.53011.400
55.730=3.071
13.900
13.940-1.993
Pubmed
80%
50.55
50.180
52.750-4.00
60.560++2.666
60.740
2.996
70%
6..350:+6.072
44.740+5.396
48.580-4.511
57.210+2.763"
56.760+t4.201
100%
86.920:E1.80
61.280
80.520+11.685
88. 1.051
88.340 1.230
PolBlogs
90%
$2.200-1-8.00 908
59.540
12.8847
86.600-10.934
1.920-114443
80%
$0.980=+-8.67
59.180#+5.475
14.760
84.560-2.877
82.880+42.685
70%
78.700++7.382
56.740+t-4105
70.520+13.114
80.620-16.167
75.280++67552
Table 3: Mean test accuracies and their standard deviations for fixed labeling budget (206) with NETCONF inferring posterior beliefs using noisy labeled nodes. Each cell shows the mean accuracy and its standard deviation on the test set for different labeling accuracy and node selection strategies, on different datasets. BB and LC+BB are node selection strategies based on LinUProp. CS and LC+CS are node selection strategies based on the native UQ methods of NETCONF. Bold values indicate the highest mean accuracy. Underlined values emphasize the method with the lower standard deviation between the Linp winner and the non-Lin UProp winner. Superscripts indicate significant superiority between the Lin winner and the non-LinU'Prop winner
(pairwise t-test at a 5% significance level (*), 10% significance level (t))
Dataset
Random
L.C
Entropy
BB
LC+BB
CS
LC+CS
100%
67.3801
64.520:1:.241
68.570113373
61.06012.621
68.670 1,311
60,95011.300 300
61.000
90%
64.150=2.727
62.090:15.278
65.110444.112
59.130+2.3844
65.580=1.758
18.170+2.991
58.770=335155
Cora
80%
61.260=3.017
60.16011:.001
61.500113.731
57.85011..500
61.770-3.223
56.450:12.987
57.730==34773
70%
$7.660 2..810
58.310-14.051
54.74014.113
1..720144635
53.91012.5522
55.080:12.740
100%
1..340=1.322
42,600:33.07
44.34012.4800
43.440:2.440
45.250 1.806
32.360:E-.554
32.40024.658
Citeseer
90%
41.740 1.796
41. 41.860:14.742
41.860:1 489
41.950. 9419
42.910 1,980
32.190.1:.5598
32.200-14.635
80%
39.460=2..38
40.370::4.66 609
38.960443.18 186
39.810:12.46
40.980=2.813
32.000:1-.555
31.990-2.636
70%
36.950=-2.916
38.800-14.364
36.980:133544
37.940:1..444
38.690 844
31.840114.595
32.020-14.725
100%
23.730=2.287
65.110:22.633
155
67.8200
67.8200-11030
44,450:53.0 637
44.450=5.637
Pubmed
90%
60.870=:2.950
16.520-12.5446
63.710:12.96
64.790012,438
04.360022222 229
44.3501:5.5
547
44.380=5.622
80%
57.310:1...63
54,700
58.980.14.245
60.980
11.420
44.190.15..9
44,270
70%
54.070=55009
52.760:12.634
15.770++4.171
$7.380:1:.829
57.540=44408
43.850::5.55 528
44.190=5.592
100%
26.360=2.005
55.000::2445
69. 39.3800-9444
87.560-E 3,977
83.240-F1311
35:000+22455
35.000=22475
PolBlogs
90%
81.180=7.844 7,84
$5.0000:24455
68. 780=
86.240=
84.460=
55.000++2.45
55.00002,445
80%
79.540=28.08
55.000::2.455
06.722:199959
2..77
63.140+:2.265
55.000112.75
55.000=2.445
70%
76.800=:7.99
55.000+:2475
67.760+:11.38
81.880-55.860
76.54D=b5.36
55.000++2475
55.000-42.475.
18

---

B.4 Additional Runtime Results
Under the same experimental conditions the linear scalability experiments in Figure 4()), we tested NETCONF on four datasets, comparing its computation time (including all edges) with that of LinUProp. As shown in T the computation times of NETCONF and LinUProp are quite similar. However, LinUProp demonstrates significant performance advantage over the NETCONF-based UQ method, as evident from Table 3 (BB/LC+BB vs. CS/LC+CS).
Table 4: Runtime comparison including all edges across different datasets (in seconds)
Method
Cora
Citeseer
Pubmed
Polblogs
NETCONF 0.0225
0.0216
0.0627
0.0126 0.0084
LinUProp
0.0256
0.0181
0.0559
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction present the main contributions, including theo- retical, methodological, and experimental contributions.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have outlined the limitations in the conclusion and discussed convergence limitations in Sec.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The complete and correct proofs for the theoretical analyses and results are provided in Sec. 4 and Appendix A
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the information needed reproduce all the experimental results disclosed in Sec. 5 and Appendix B.2
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Code is public at http::////gttuuuucccoc///ehuuuuu
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The sufficient information concerning the experimental settings is comprehen- sively disclosed in Sec. 5 and Appendix B.2
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yss]
Justification: All figures and tables related to test accuracy for varying/fixed labeling budgets have provided error bars.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Question:
20

---

Answer:
[Yes]
Justification: The sufficient information concerning the computation resources is compre- hensively disclosed in Appendix B.2
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conforms with the NeurlPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field Machine Learning. There are many potential societal consequences of work, none which we feel must be specifically highlighted here.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The original papers for the datasets are cited properly.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
21


Reviews:
[{"review_id": "OyH4Tz793q", "reviewer": "Reviewer_HCKJ", "summary": "A method for quantifying the uncertainty in the graphical model is proposed. The authors claimed that the method is superior over prior methods including NETCONF and Monte Carlo in the aspects of scalability, interpretability, and unbiasedness. Active learning that uses node uncertainty estimation for unlabeled node selection is conducted to show the benefits of the computed uncertainty.", "questions": "-\tThe uncertainty is defined using interval width. Does the location of the interval matter and why?\n-\tDue to the proof of Eqs. (14) and (15), is it possible to compute the generalized variance component directly without LinUProp?", "limitations": "The clarity of Figure 2 can be improved: what is H_12, H_23, e_1, etc.? The authors should point to the definitions in the main texts or to label these symbols in the figure.\n\nThe GNN models are more popular, while its uncertainty quantification has been studied. Though GNN and probabilistic graphical models are not comparable, but I expect the authors to have certain discussion of GNN and make potential connections between methods for these two sorts of models.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I find the decomposition of the prediction error into bias and generalized variance novel, and the assignment of the interval width to the variance term is creative.\n- The submission is well-prepared and contain necessary components to make it a completed piece of work.\n- The presentation of preliminaries clearly show the background to facilitate the understanding of the more complicated part in Section 3. Overall, the paper is well-organized with clear logics.\n- The proof in Section 4 provide significant insight into the belief propagation algorithm and also the uncertainty quantification. Experiments on various setting proved the usefulness of the studied problem and the LinUProp method.", "weaknesses": "-\tI have doubt about the interpretability of LinUProp, as it involves high-order terms such as $T^2$, $T^3$, etc. that are not easy to be understood.\n-\tEq. (8) seems to be a simple extension of the original LinBP method.\n-\tIt is not clear what are the $\\mathbb{x}$, $\\mathbb{y}$, and $\\mathbb{P}$ terms in the proof in Eq. (9). What’s their relationship to the LinUProp method?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n>I have doubt about the interpretability of LinUProp, as it involves high-order terms such as $T^2$,$T^3$, etc. that are not easy to be understood.\n\nWhen we say that LinUProp is interpretable, we mean that for the posterior uncertainty of each node calculated by LinUProp, we can determine the contribution of each other node to the posterior uncertainty of that node. The matrices $T^2$,$T^3$, etc., are intermediate steps obtained from applying a Neumann series expansion to the closed-form solution of LinUProp. We do not need to understand their specific meanings; we only need to sum them to obtain the contribution of each other node to the current node's uncertainty. This allows us to achieve interpretability for LinUProp. \nMoreover, since the necessary and sufficient condition for LinUProp convergence is that the spectral radius of $T$ is less than 1, when the algorithm converges, the higher-order terms become very small. Therefore, in practice, it's often sufficient to compute only a few lower-order terms to understand the contribution of each other node to the uncertainty of a given node.\n\n>Eq. (8) seems to be a simple extension of the original LinBP method.\n\nEq. (8) is the closed-form solution of LinUProp:\n\n$$\\text{vec}(\\mathbb{B})=(\\mathbf{I}-\\mathbf{\\Psi}_{1}^{'}-\\text{Diag}(\\mathbf{\\Psi_2}^{'}\\mathbf{Q}))^{-1}\\text{vec}(\\mathbb{E}).$$\n\nThe closed-form solution of LinBP is\n\n$$\\text{vec}(\\hat{\\mathbf{B}})=(\\mathbf{I}-\\hat{\\mathbf{H}}\\otimes\\mathbf{A}+\\hat{\\mathbf{H}}^2\\otimes\\mathbf{D})^{-1}\\text{vec}(\\hat{\\mathbf{E}}).$$\n\nAt first glance, Eq. (8) and LinBP appear somewhat similar, as both conform to the form $\\mathbf{y}=(\\mathbf{I-P})^{-1}\\mathbf{x}$. However, simply replacing prior and posterior beliefs in LinBP with interval widths ($\\text{vec}(\\mathbb{E})$ and $\\text{vec}(\\mathbb{B})$) does not yield LinUProp. This is because LinUProp's goal is to calculate the uncertainty of each node's posterior belief, derived from the upper and lower bounds of messages and beliefs through a series of derivations, ultimately leading to Eq. (8). This cannot be achieved by merely extending LinBP; for a detailed derivation, please refer to Appendix A.1.\n\n>It is not clear what are the $\\mathbb{x},\\mathbb{y}$, and $\\mathbb{P}$ terms in the proof in Eq. (9). What’s their relationship to the LinUProp method?\n\nAfter Eq. (9), on line 157, $\\mathbf{y}=(\\mathbf{I-P})^{-1}\\mathbf{x}$ simply represents the general form of a linear equation system that can be solved using the Jacobi method. We merely want to convey that the closed-form solution of LinUProp conforms to this general form. Therefore, the convergence conditions are consistent with the Jacobi method. Specifically, $\\mathbf{y}$ corresponds to $\\text{vec}(\\mathbb{B})$, $\\mathbf{x}$ to $\\text{vec}(\\mathbb{E})$, $\\mathbf{P}$ to $\\mathbf{\\Psi}_{1}^{'}+\\text{Diag}(\\mathbf{\\Psi_2}^{'}\\mathbf{Q})$.\n\n>The uncertainty is defined using interval width. Does the location of the interval matter and why?\n\nThis can be concluded from the derivation of LinUProp. At the beginning of the derivation (Eqs. (16-19)), the upper and lower bounds of the messages and beliefs are involved. However, by Eq. (20), after subtracting the lower bound from the upper bound of the messages, only the interval width remains in the equation, and the specific location of the interval is no longer considered. Therefore, the specific location of the interval is not important for LinUProp.\n\n>Due to the proof of Eqs. (14) and (15), is it possible to compute the generalized variance component directly without LinUProp?\n\nThrough Eqs. (14) and (15), we derived **the variance component** and further proved that the variance component is a special case of LinUProp. This ultimately led to the conclusion that LinUProp is the generalized variance component. It's important to note that \"the generalized variance component\" answers what the uncertainty computed by LinUProp represents; we cannot directly calculate \"the generalized variance component\" itself.\n\n\n>The clarity of Figure 2 can be improved: what is H_12, H_23, e_1, etc.? The authors should point to the definitions in the main texts or to label these symbols in the figure.\n\nWe have stated in the caption of Figure 2 that the inputs to LinUProp include (1) Uncertainty in prior beliefs of each node represented as interval widths (2) Edge potentials. However, we did not explicitly specify in the caption how these symbols correspond to (1) and (2). \n\nIn fact, $\\mathbb{e}_1,\\mathbb{e}_2,\\mathbb{e}_3$ correspond to (1), and \n\n$\\mathbf{H_{12}},\\mathbf{H_{23}}$ correspond to (2). Although these symbols are defined in lines 123-128, explicitly mentioning this correspondence in the figure caption would make it clearer. We will explicitly include this correspondence in the caption of Figure 2 in the camera-ready version.\n\n>The GNN models are more popular, while its uncertainty quantification has been studied. Though GNN and probabilistic graphical models are not comparable, but I expect the authors to have certain discussion of GNN and make potential connections between methods for these two sorts of models.\n\nSome studies have attempted to combine GNNs with probabilistic graphical models to leverage the strengths of both approaches. For instance, this combination can provide interpretability to GNNs [1] or achieve performance that surpasses using GNNs alone in certain tasks [2]. Solely relying on UQ methods for GNNs may be insufficient to compute uncertainties for these hybrid approaches. Therefore, integrating LinUProp with existing UQ methods for GNNs could potentially be more promising.\n\n[1] Vu, Minh, and My T. Thai. \"Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.\" NIPS, 2020.\n\n[2] Qu, Meng, Yoshua Bengio, and Jian Tang. \"Gmnn: Graph markov neural networks.\" ICML, 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2e4J8HhCxc", "reviewer": "Reviewer_XubP", "summary": "This paper considers the problem of calculating uncertainty in the infererence results on probabilistic graphical models. Their method is based on a previously published linearization of the belief propagation method, to provide scalability, interpretability, and unbiasedness. The benefits of the new algorithm is demonstrated through experiments comparing with existing methods including Monte Carlo sampling, and uncertainty-based active learning on graphs.", "questions": "-In Figure 6, the legend shows 7 methods, while in some of the subfigures, there are only 5-6 curves. Can you explain why?\n-In the same figure, LC seems to have performance between that of LC+BB and LC+CS. Is there any explanation about this observation?", "limitations": "Please see the weaknesses", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: the studied problem is unique in that a linearly scalable, interpretable, provably convergence uncertainty quantification methods on graph is still missing. The proposed method is novel with a new definition of uncertainty quantity that is based on interval width that is decomposed into bias and variance. Such a definition is not seen in prior work.\nQuality: Technically, the formula and algorithm are developed rigorously and I don’t find errors therein. Their experiments protocols are designed carefully to evaluate their methods and prove the claimed advantages.\nClarity: the process of conducting the experiments, including datasets, graph constructions, baseline setup, are clearly described and reproducing the results is feasible. Figure 2 helps in understanding the dimension and operations of the linear operators on graphs.\nSignificance: their problem definition targets at gaps in uncertainty quantification on graphical model. In particular, previous methods, such as Monte Carlo and other uncertainty calculation methods on graphs, are either not scalable, biased, without convergence guarantee, or non-interpretable. In this aspect, the work contributes to the need of a scalable, interpretable, provably convergent, and unbiased uncertainty quantification algorithm for graphical models. In terms of theoretical significance, the decomposition of the computed interval width further makes sense of their proposed definition of uncertainty. Unlikely previous work that use variance of a distribution as a notion of uncertainty, the computed uncertainty is in fact a bias and variance term, thus shedding lights on the seemingly unmotivated definition of interval width.", "weaknesses": "-The proposed method is based on a previously developed linearization method, making their innovation limited.\n-In the section of “Correctness of quantified uncertainty”, the correctness is only validated through a small simple graph, and no experiments are conducted on larger-scale graphs. Maybe the authors can explain why it is so designed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n>The proposed method is based on a previously developed linearization method, making their innovation limited. \n\nIndeed, we did use a conclusion from LinBP (Centered BP) in our derivation. However, LinUProp fundamentally differs from LinBP in its goals, and we have several unique contributions:\n\n-   **Different Goals**: The goal of LinBP is to infer the posterior beliefs of nodes, providing a point estimate of these beliefs. In contrast, LinUProp aims to quantify the uncertainty in the posterior beliefs, serving as a UQ method that offers the uncertainty in the form of interval widths.\n-   Since LinBP is not a UQ method, our contributions in the field of UQ are distinct from those of LinBP:\n    -   LinUProp addresses the issue of underestimating posterior uncertainty found in related works (e.g., NETCONF/SocNL).\n    -   The posterior uncertainty of nodes computed by LinUProp is interpretable, meaning we can understand the contribution of each other node to a specific node's posterior uncertainty by applying a Neumann series expansion to LinUProp.\n    -   We decompose the expected prediction error of the graphical model and prove that the uncertainty computed by LinUProp is the generalized variance component of the decomposition.\n\n>In the section of “Correctness of quantified uncertainty”, the correctness is only validated through a small simple graph, and no experiments are conducted on larger-scale graphs. Maybe the authors can explain why it is so designed?\n\nIn the section “Correctness of Quantified Uncertainty,” we explained the reason for directly verifying the correctness of LinUProp on small graphs through MC simulations:\n\n\"MC simulations are adopted as the ground-truth due to their ability to provide accurate approximations through a sufficient amount of sampling [30], which are feasible for small-scale graphs.\"\n\nFor large-scale graphs, each sampling of the posterior belief for all nodes takes significantly longer than for small graphs, and more samples are needed to ensure accurate approximations. For example, on the Pubmed dataset, under the same experimental conditions as on small graphs, a single sampling of the posterior belief takes about 1 minute. Therefore, even maintaining the same number of samples as in the small graph experiment (100,000 times) would take approximately 70 days. Consequently, for large-scale graphs, we, like related works, validate the effectiveness of LinUProp in downstream tasks such as active learning (which we use)[1] , OOD detection [2], and robustness against node feature or edge shift [3].\n\n[1] Kang, Jian, et al. \"JuryGCN: quantifying jackknife uncertainty on graph convolutional networks.\" SIGKDD, 2022.\n\n[2] Zhao, Xujiang, et al. \"Uncertainty aware semi-supervised learning on graph data.\" NIPS, 2020.\n\n[3] Stadler, Maximilian, et al. \"Graph posterior network: Bayesian predictive uncertainty for node classification.\" NIPS, 2021.\n\n>In Figure 6, the legend shows 7 methods, while in some of the subfigures, there are only 5-6 curves. Can you explain why? \n\nThe curves corresponding to the BB and LC+BB methods are almost overlapping, which initially makes them appear as a single curve. However, upon closer inspection of the markers (such as $\\triangle$ and $\\triangledown$), it becomes evident that there are actually two distinct curves. The CS and LC+CS methods ($\\triangleleft$ and $\\triangleright$) exhibit a similar situation, ultimately making the 7 curves appear as only 5.\n\n>In the same figure, LC seems to have performance between that of LC+BB and LC+CS. Is there any explanation about this observation?\n\nThe analysis of Figure 6 in the paper (lines 292-296) has already provided an explanation for this observation. This phenomenon nicely validates the potential issues with NETCONF that we mentioned in Figure 1: NETCONF (CS/LC+CS) prioritizes labeling low-degree nodes due to their inherent assumption that neighbors necessarily reduce uncertainty. As a result, nodes with many neighbors are often mistakenly viewed as having low uncertainty and are left unlabeled, which further leads to high uncertainty in the majority of nodes, ultimately causing LC+CS to perform worse than LC. In contrast, LinUProp (BB/LC+BB), which appropriately incorporates the uncertainty of neighbors, does not have this issue of underestimating uncertainty and thus results in LC+BB performing significantly better than LC.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SYJw3Alnxj", "reviewer": "Reviewer_rPk6", "summary": "[Edit: After discussion, the Authors have addressed my concerns on the presentation and discussion of their results. I have accordingly increased my score (previously 5).]\n\nThe paper proposes an alternative algorithm for message passing for uncertainty quantification in graphical models. The method is linear, with (presumed) computational performance gains over existing methods, less susceptibility to certain kinds of bias, and supporting theoretical justification. The method is empirically explored in simulation studies.", "questions": "I was a little confused on the comparative studies.\n\n1) It isn't clear to me whether the proposed method produces unbiased results (though my guess is that it does not, and I note the content in section 4.2 to this end, and the claim it avoids bias in Section 7). Other methods, as discussed, do provide unbiased results, but perhaps they are very computational or have other downsides. So its ok for the proposed method to be biased if there is a substantial speed gain, for example. (*Is* there a speed gain? Actual comparisons with other methods don't seem to have been made.)  Or, put another way, the method presumably gains lots by designing for linear speed. What did it lose?\n\n2) I couldn't find anywhere which described what \"BP\" or \"NETCONF\" were (Figures 5-6). This somewhat reduces the readers ability to understand the information being presented. \n\n3) Tables 2 and 3 (Appendix) have generously bolded the results corresponding to the papers methodology, but the +/- standard errors of the means presented strongly suggest that in many cases there is no statistically significant difference between many of the methods (bolded, or otherwise). This would seem to undermine the accuracy performance claims.", "limitations": "The paper checklist states that the limitations are outlined in the Conclusion (section 7). However, no limitations of the proposed methods seem to be discussed here. (The statement \"However, ...\" is not a limitation.) I would expect that the authors really ought to have some things to say here. (Presumed) strong computational gains of methods usually have a tradeoff.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Theoretical justification of the method is helpful.", "weaknesses": "Some areas were hard to understand. E.g. the motivating discussion of why some (but not all) existing methods could only reduce uncertainty.\n\nLimitations of the method have not really been addressed. It seems the proposed method is perfect!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n>Some areas were hard to understand. E.g. the motivating discussion of why some (but not all) existing methods could only reduce uncertainty.\n\nThe sentence you mentioned in the original text is: “However, this results in **any neighbor of a node will necessarily reduce the uncertainty**, even neighbors with noise or missing information, thus underestimate posterior uncertainty, as depicted in Figure 1.” In the previous sentence, we explained the reason as “Existing works [7, 35]...modeling beliefs as Dirichlet distributions and **treating neighboring nodes as observations**.” At the end of this sentence, we indicated that Figure 1 provides a further explanation of this point. Existing methods [7, 35] treat neighbors as **\"observations,\"** implicitly assuming that a node’s neighbors **are always evidence** and thus will necessarily reduce uncertainty.\n\n>Limitations of the method have not really been addressed. It seems the proposed method is perfect!\n>The paper checklist states that the limitations are outlined in the Conclusion (section 7). However, no limitations of the proposed methods seem to be discussed here. (The statement \"However, ...\" is not a limitation.) I would expect that the authors really ought to have some things to say here. (Presumed) strong computational gains of methods usually have a tradeoff.\n\nFrom the derived convergence conditions of LinUProp ($\\rho(\\mathbf{\\Psi_{1}}^{'}+\\text{Diag}(\\mathbf{\\Psi_{2}}^{'}\\mathbf{Q}))<1$), we can see that when the graph is very large, if there is strong global (most edges) homophily/heterophily, the norm of the matrix  $T=\\mathbf{\\Psi_{1}}^{'}+\\text{Diag}(\\mathbf{\\Psi_{2}}^{'}\\mathbf{Q})$ will be large, which may cause LinUProp to fail to satisfy the convergence condition of the spectral radius of $T$ being less than 1. However, if only local (a few edges) strong homophily/heterophily exists in a large-scale graph, LinUProp can still converge. This is a limitation of LinUProp, and we will include the above discussion in the camera-ready version.\n\n\n>It isn't clear to me whether the proposed method produces unbiased results ......\n\n The term \"unbiased\" in the abstract was intended to communicate that our method aims to avoid the underestimation of uncertainty, which some other methods might suffer from (NETCONF/SocNL). We didn't mean to claim that our method is mathematically unbiased in the statistical sense without further rigorous proof, although we validated the consistency of LinUProp with MC simulation through the Correctness experiment in Section 5.1. This issue appears only in two sentences in the abstract and one sentence in the conclusion, and is not mentioned elsewhere in the original text. To avoid any confusion, we propose to revise the two sentences in the abstract and the one sentence in the conclusion. Additionally, we have not yet studied the relationship between the speed of LinUProp and its unbiasedness, which might be a worthwhile topic for future research.\n \n - Abstract\n\t- There are fast UQ methods for graphical models with closed-form solutions and convergence guarantee but with ~~biased~~ uncertainty underestimation. \n\t- We propose LinUProp, a UQ method that utilizes a\nnovel linear propagation of uncertainty to model uncertainty among related nodes additively instead of multiplicatively, to offer linear scalability, guaranteed convergence, and ~~unbiased~~ closed-form solutions that do not underestimate uncertainty.\n- Conclusion\n\t- Unlike its competitors, LinUProp does not assume neighbors necessarily reduce uncertainty and thus avoids ~~biased~~ uncertainty underestimation.\n\n>I couldn't find anywhere which described what \"BP\" or \"NETCONF\" were (Figures 5-6). This somewhat reduces the readers ability to understand the information being presented.\n\nAs stated in the captions of Figures 5 and 6, BP and NETCONF are two methods for **inferring posterior beliefs**. We have detailed Belief Propagation (BP) in the Preliminaries and introduced how NETCONF works through a simple case in Figure 1. The key difference between the two is that BP can only provide a point estimate of the posterior beliefs, whereas NETCONF can derive a Dirichlet posterior from which a \"Certainty Score\" can be obtained. This \"Certainty Score\" can be used to estimate the uncertainty of the posterior, and its calculation method is provided in lines 275-277.\n\n>Tables 2 and 3 (Appendix) have generously bolded the results corresponding to the papers methodology, but the +/- standard errors of the means presented strongly suggest that in many cases there is no statistically significant difference between many of the methods (bolded, or otherwise). This would seem to undermine the accuracy performance claims.\n\nThank you for your question regarding standard deviations and statistical significance. We have added annotations addressing these two points to Tables 2 and 3 in the global response PDF. Specifically, we have used $\\underline{\\text{underlined}}$ values to emphasize the method with the lower standard deviation between the LinUProp winner and the non-LinUProp winner. We have also used superscripts to indicate significant superiority between the LinUProp winner and the non-LinUProp winner (pairwise t-test at a 5% significance level (*) and 10% significance level ($\\dagger$)). We can observe that the LinUProp-based methods (BB/LC+BB) consistently maintain low standard deviations across 4 datasets, 2 inference methods, and 4 labeling accuracies. This level of consistency is not exhibited by other methods, even though some approaches may achieve comparable accuracy to LinUProp in certain specific cases.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "frgtiZEIRS", "reviewer": "Reviewer_G7cz", "summary": "This paper proposes an uncertainty quantification method for graphical models that uses linear propagation to model uncertainty. Experiments show that it can achieve competitive results and fast convergence in downstream tasks.", "questions": "Can you please explain the upper part of Figure 2? I'm a bit confused about its meaning.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1: The paper is well-written. The motivation for the paper and the proposed solutions are clear, making it easy for readers to follow.\n\n2: Theoretical analysis is solid. The authors clearly explain the necessary preliminaries and provide detailed proofs.", "weaknesses": "1: Most of the datasets used for validating the properties of the proposed method are datasets with high homophily, which makes the validation less comprehensive. It would be better to conduct experiments on several datasets with high heterophily.\n\n2: The illustrations in some of the figures are vague. For example, Figure 1 is quite inclusive but lacks some necessary explanations. The meaning of distribution Beta and the values of alpha and beta are hard to understand (though I clearly understand the calculation part).\n\n3: The formatting of the paper is less professional, especially in the appendix. In B.3.2, there are large blanks between the title and Table 2. Also, Table 3 is oversized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and constructive reviews.\n\n## Regarding the Formatting Issues\n\n>The formatting of the paper is less professional, especially in the appendix. In B.3.2, there are large blanks between the title and Table 2. Also, Table 3 is oversized.\n\nThank you for pointing out these formatting issues. We will carefully review and address all formatting concerns, especially in the appendix, and make the necessary corrections in the camera-ready version.\n\n## Further Explanation of the Figures\n\n>The illustrations in some of the figures are vague. For example, Figure 1 is quite inclusive but lacks some necessary explanations. The meaning of distribution Beta and the values of alpha and beta are hard to understand (though I clearly understand the calculation part).\n\nLet's understand the meaning of the Beta distribution and its parameters in Figure 1 within the context of an active learning scenario. Consider a graph active learning task where each annotator can label a node as one of two categories. In this case, the Beta distribution can be used to model the uncertainty in the probability of a node belonging to a specific category. When considering a node individually,  $\\alpha$ can be interpreted as the number of times the node is labeled as category A plus one, and $\\beta$ can be interpreted as the number of times the node is labeled as category B plus one. The sum $\\alpha + \\beta$ represents the total number of times the node has been labeled plus two; the larger this sum, the more times the node has been labeled, and thus the lower the uncertainty.\n\nThank you for highlighting the points that might confuse readers. We will address this in the camera-ready version by incorporating the specific scenarios mentioned above to make Figure 1 easier to understand.\n\n>Can you please explain the upper part of Figure 2? I'm a bit confused about its meaning.\n\nThe upper part of Figure 2 illustrates, through a 3-node chain graphical model, what information we need to input if we want to quantify the uncertainty in the posterior belief of each node using LinUProp. To make this easier to understand, we can think of it as a social network.\n\nIn a simple social network with 3 users, each user can be categorized into one of two groups based on whether they are music enthusiasts or not. If we want to know the uncertainty in the posterior probability of each user being a music enthusiast, considering the influence of other users, we need to provide two types of information:\n\n- The interval width representing the uncertainty about whether each user is a music enthusiast when considered individually (i.e., the prior interval widths $\\mathbb{e}_1, \\mathbb{e}_2, \\mathbb{e}_3$). This could be derived from user-filled profiles. If a user hasn't specified their music preferences, we assign a wider interval width; otherwise, we assign a narrower interval width.\n- The \"compatibility matrix\" between every two connected users. For example,\n$$ \\mathbf{H}_{12}=\\begin{bmatrix} 0.8 & 0.2 \\\\\\\\ 0.2 & 0.8 \\end{bmatrix} $$ \n\n$\\mathbf{H}_{12}(i,j)$ denotes the degree of association between class i of user 1 and class j of user 2.\nThis matrix suggests that users 1 and 2 are more likely to either both like or both dislike music, rather than only one of them liking music.\n\n>Most of the datasets used for validating the properties of the proposed method are datasets with high homophily, which makes the validation less comprehensive. It would be better to conduct experiments on several datasets with high heterophily.\n\nLinUProp is a UQ method, so we expect to experimentally verify its performance in uncertainty quantification. We evaluate UQ methods in graph active learning tasks through an uncertainty-based node selection strategy because a good UQ method can prioritize nodes with high uncertainty for labeling, achieving the highest possible accuracy within a limited labeling budget. This approach is reasonable for validating UQ methods on homophily graphs, as prioritizing high-uncertainty nodes can help clarify the categories of neighboring nodes, and after propagation, quickly reduce global uncertainty, achieving higher accuracy with a lower labeling budget. However, on heterophily graphs, even if high-uncertainty nodes are prioritized for labeling, it may not help clarify the categories of neighboring nodes (especially when there are many node categories). In such cases, prioritizing high-uncertainty nodes may not lead to a rapid increase in accuracy, thus failing to appropriately reflect the performance of the UQ method.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Tables 2 and 3 have been updated with annotations for the standard deviation and t-test results.

Meta-review: The reviewers agree that this is a solid, interesting and useful piece of work. There were some concerns about the presentation, the experimental setup and the novelty (relative to another piece of work, LinBP), but the authors have convincingly used their rebuttals to clarify these issues and suggest fairly minor changes to improve the paper. 

To the authors: please look at the reviews and responses again, and please carefully take these into account when preparing the camera-ready version.
Decision: Accept (poster)