Graph Structure Learning with Interpretable Bayesian Neural Networks
Authors: Max Wasserman
Gonzalo Mateos
Venue: Accepted by TMLR ()

Abstract: Graphs serve as generic tools to encode the underlying relational structure of data. Often this graph is not given, and so the task of inferring it from nodal observations becomes important. Traditional approaches formulate a convex inverse problem with a smoothness promoting objective and rely on iterative methods to obtain a solution. In supervised settings where graph labels are available, one can unroll and truncate these iterations into a deep network that is trained end-to-end. Such a network is parameter efficient and inherits inductive bias from the optimization formulation, an appealing aspect for data constrained settings in, e.g., medicine, finance, and the natural sciences. But typically such settings care equally about \textit{uncertainty} over edge predictions, not just point estimates. Here we introduce novel iterations with \textit{independently interpretable parameters}, i.e., parameters whose values - independent of other parameters' settings - proportionally influence characteristics of the estimated graph, such as edge sparsity. After unrolling these iterations, prior knowledge over such graph characteristics shape \textit{prior distributions} over these independently interpretable network parameters to yield a Bayesian neural network (BNN) capable of graph structure learning (GSL) from smooth signal observations. Fast execution and parameter efficiency allow for high-fidelity posterior approximation via Markov Chain Monte Carlo (MCMC) and thus uncertainty quantification on edge predictions. Informative priors unlock modeling tools from Bayesian statistics like prior predictive checks. Synthetic and real data experiments corroborate this model's ability to provide well-calibrated estimates of uncertainty, in test cases that include unveiling economic sector modular structure from S$\&$P$500$ data and recovering pairwise digit similarities from MNIST images. Overall, this framework enables GSL in modest-scale applications where uncertainty on the data structure is paramount.

Published in Transactions Machine Learning Research (09/2024)
Graph Structure Learning with Interpretable Bayesian Neural Networks
Max Wasserman
wwwsserd@Be.rucheeeerr eda
Deportment of Computer Science University of Rochester
Gonzalo Matcos
gmateosb @mae www.e rochester. eda
Deportment of Electrical and Computer Engineering University of Rochester
Reviewed OpenReview: https: o/penreveee......u.u net/ forum? id= 2
Abstract
Graphs serve generic tools to encode the underlying relational structure of data. Often this graph is not given, and so the task of inferring it from nodal observations becomes important. Traditional approaches formulate a convex inverse problem with a smoothness promoting objective and roly itcrative methods to obtain solution. In supervised scttings where graph labels are available, one can unroll and truncate these iterations into a deep network that trained end-to-end. Such a network is parameter efficient and inhorits inductive bias from the optimization formulation, settings in, e.g., medicine, finance, and the natural sciences. But lypically such seltings care equally about uncertainty over edge predictions, not just point estimates. Here we introduce novel iteralions with independently interprelable paramelers, i.c., parameters whose values independent of other parameters' settings proportionally influence characteristics of the estimated graph, such as edge sparsity. After unrolling these iterations, prior knowledge over such graph characteristies shape prior distributions over these independently interpretable network parameters to yield a Bayesian neural network (BNN) capable of graph structure learning (GSL) from smooth signal observations. Fast execution and parameter efficiency allow for high-fidelity posterior approximation via Markov Chain Monte Carlo (MCMC) and thus uncertainty quantification on odge prodictions. Informative priors unlock modeling tools from Bayesian statistics like prior predictive checks. Synthetic and real data experiments corroborate this model's ability to provide well-calibrated estimates of uncertainty, test cases that include unveiling economic sector modular structure from S&P500 data and recovering pairwise digit similaritics from MNIST images. Overall, this framework enables GSL modest-scale applications where uncertainty on the data structure paramount.
appealing aspect for data constrained
1 Introduction
Graphs serve foundational paradigm in machine learning, data science, and network science for modeling complex systems, capturing intricate relationships in data that range from social networks to gene interactions; see e.g., (Kolaczyk] 2009; [Hamilton] 2020). In computational biology, accurate graph structures can offer insights into gene regulatory pathways, enhancing ability to treat diseases at the genetic level (Cai et al. 2013). In finance, the ability to recover precise financial networks can be useful for risk assessment and market stability MMarti et al. 2021). In geometric deep learning (Bronstein al., 2017), , the lack of observed graph structure underlying data often limits the use of efficient learning models such as graph neural networks (GNNs); see c.g., (Cosmo et al.) 2020). Yet, despite their importance, existing methodologics for graph structure learning (GSL) from multivariate nodal data face significant limitations.

---

Published in Transactions on Machine Learning Research (09/2024)
This work addresses the GSL problem where nodal observations are used to predict the completely unob- served graph structure. Traditional approaches summarize the nodal observations with pairwise vertex (dis)similarity matrix, c.g,, correlation or Euclidean distance matrices, and formulate GSL as a regularized convex inverse problem (Mateos al. 2019: Dong et al. 2019). The primary objective encourages data fidelity, according to chosen model linking the nodal observations and the sought latent graph, while the regularization objectives capture prior structural knowledge, such as edge sparsity or desired connectivity paiterns. These model-based methods solve the inverse problem using optimization algorithms, which often come with convergence rate guarantees (Saboksayr & Mateos 2021 Wang et al. 2023). However, as noted in (Pu et al., 2021) their expressiveness is constrained to graph characteristics that can be modcled via convex criteria and they may suffer complexity and scalability issues. Specifically, these model-based approaches typically necessitate an outer loop for grid-based optimization of regularization parameters (and often other algorithm parameters, e.g,, a step-size), and an inner loop that, given this fully defined optimization problem, may demand thousands of iterations to converge on solution. When nodal observalions come with corresponding graph labels, recent supervised GSL approaches partially overcome these obstacles using 'algorithm unrolling' (Shrivastava et al. 2020: Pu ct al. 2021 Wasserman et al. 2023). Unrollings truncate these inner-loop iterations to yield deop network ar architecture that is trained end-to-end to approximate the solution to the inverse problem (Monga et al. 2021). The choice of a custom loss function, which need not be convex, plus optional architectural refinements of already well-motivated initial network tend to improve performance on the task of interest. Truncation depth provides explicit control on the complexity of prediction, now a forward pass in the network. And the use of backpropogated gradicnts makes learning the regula regularization (and step-size) parameters, now network parameters, more scalable. Additionally, the unrolled deep networks tend to inherit appealing aspects from the original model-based formulation, namely inductive bias and low dimensionality, as their outputs are approximations to solutions of the original inverse problem.
1.1 Towards interpretability and uncertainty quantification: Desiderata and contributions
In composite inverse problems with multiple regularizers, understanding how each regularization parameter values affect desirable solution traits (e.g., image sharpness or number of graph edges) may be complex and often beyond the modeler's knowledge. This obscurity necessitates a naive- and consequently costly multi- dimensioanl grid search for suitable parameter values; see e.g., the numerical study in (Dong et al., 2016 Scction V-B). When the relationship between the regularization parameters and solution characteristic is clear, we say the parameters are interpretable with respect to (w.r.t.) the output characteristic. When an output characteristic influenced by a single parameter, independent of all others, we call this parameter independently interpretable w.r.t. the output characteristic. Such instances make interpretability actionable, namely they allow prior knowledge on the solution characteristic to be incorporated onto the value of the independently interpretable parameter. A key contribution of this work is: i) in recognizing optimization problems with independently interpretable parameters as ripe for the adoption of unrollings, which inhorit this interpretability because they approximate inverse problem solutions; and ii) in leveraging the Bayesian framework to seamlessly incorporate such prior knowledge into the parameters of the unrolled network.
An issue unrollings often face (within GSL and beyond) is their tendency to produce layers with pre- activation outputs that are nonlinear functions of the parameters; e-g., parameter products and parameters in denominators (Mouga et al. 2021). This prevents the deep network from being true neural network (NN), i.e., a function compased of layers, where each layer consists of affine transformations of data or intermediate activations followed by non-lincar functions applied pointwise (Bishop) 1995). To address this issuc, network designers may opt for reparameterization but at the expense of parameter interpretability and often degraded empirical performance (Monga et al. 2021 Shrivastava et al. 2020). Unrollings can be impeded by muisance parameters- parameters not of direct interest, but which must be accounted for - like a step-size. Nuisance parameters are typically a vestige of the chosen optimization algorithm rather than being intrinsic to the problem formulation. Nuissance parameters can also undermine training stability (see Appendix [A.1.]] and since they lack clear connection to specific solution characteristics they hinder informative prior modcling. The preceding discussion motivates the need for innovative GSL techniques to produce true NN unrollings amenable to incorporation of prior knowledge on their parameters.

---

Published in Transactions on Machine Learning Research (09/2024)
Providing estimates of uncertainty on an inferred graph structure is important for downstream applications, e.g. in biology, finance, and machine learning with GNNs. In general Bayesian statistics, low-dimensional models with interpretable parameters are constructed using background information on the specific problem. Interpretability allows informative prior modeling and thus access enticing Bayesian modeling tools, e.g., prior predictive checks (Gabry et al., 2017], while the low dimensionality allows tractable high-quality posterior inference, typically via Markov Chain Monte Carlo (MCMC) sampling. For example, traditional Bayesian approaches to GSL tend to address the transductive (tied to single graph) setting by constructing a joint model over parameters, observed data, and latent graph structure, use MCMC to draw samples, and marginalize out all but the graph samples (Butts] 2003 Crawiord] 2015 Gray et al.) 2020). , Stepping back from the specific case of GSL, the inability to specify sufficiently expressive model often motivates the use of Bayesian neural networks (BNNs), an allernative paradigm which typically bypasses domain-specific modeling opting instead feed the output of a performant NN directly into the likelihood function; see e.g., (Jospin let al. 2022). Both traditional Bayesian and BNN approaches derive uncertainly estimates over predictions by marginalizing out the parameter posterior. However, BNNs present notable challenges, especially in the incorporation of prior information and posterior approximation. Due to the non-interpretabiiity of paramcters, priors are often selected for computational convenience, such as a zcro-mean isotropic Gaussian, which can inadvertently bias predictions against prior beliefs, a phenomenon known as 'unintentionally informative priors' (Wenzel et al. 2020), thus negating key benefit of Bayesian methods. Additionally, the parameters' high dimensionnlily and complex posterior geometry make high-quality posterior approximation a formidable lask, often requiring siguificant approximations that undermine the interpretability of the results (Gal & Ghahramani 2016 Wenzel et al., 2020; Monga et al.) 2021). This highlights the need for an inductive GSL method that not only provides reliable uncertainty estimates over edge predictions but also combines the expressive power of BNNSs with the traditional Bayesian approach's 's strengths in integrating prior knowledge, employing robust modeling tools like predictive checks, and ensuring high- fidelity posterior approximation.
Summary of contributions. In this paper, we introduce the first BNN for supervised GSL from smooth signal observations. This BNN produces a distribution over unseen lest. graphs allowing estination of uncortainty over edge predictions. It leverages the independent intepretability of the paramters in the GSL formulation to allow informative prior modeling over the weights of the NN, itself a result of unrolling novel iterations for a model-based formulation with well-documented merits. We make the following technical contributions and offer experimental evidence to support our claims:
In Section we develop a novel optimization algorithm for GSL from smooth signals (Algorithm D which is step-size free and parameterized to yield independent interpretability w.r.t. edge sparsity.
In Section 1 we unroll Algorithm D to produce the first strict unrolling for GSL, from smooth signals, which results a true NN. This is be contrasted with existing supervisee-learaee GSL, where GLAD (Shrivastaava et al. 2020) and Unrolled PDS (Pu et al. 2021) are not true NNs, and GDN (Wasserman et al. 2023) is not a strict unrolling because it resorts to gradient truncation and reparameterization. The proposed unrolled NN is used define our BNN, dubbed 'DPG' since Algorithm is a dual-based proximal gradient method (Beck & Teboulle 2014].
approaches to
In Section 5 we introduce a methodology to integrate prior knowledge into BNN prior distributions, specifically for networks derived from unrolled optimization algorithms for inverse problems with independent interpretability. We show this approach unlocks classical Bayesian modeling tools like predictive checking, which we fruitfully apply to DPG. High-fidelity parameter posterior inference via Hamiltonian Monte Carlo (HMC) sampling enables the first. instance of model for GSL from smooth signals, capable of producing estimates of uncertainty over edge predictions.
In Section f we validate DPG's ability to produce high-quality and well-calibrated uncertainty estimates from synthetic data, stock price time series (S&P500), as well as graphs learnt from images of MNIST digits. The reliability of these estimates is underscored by notable Pearson corrclations between predictive uncertainty and error: 0.70 for the stock data and 0.62 for the MNIST digits. Additional experimental evidence is provided in the appendices.

---

Published in Transactions on Machine Learning Research (09/2024)
2 Related Work
A recent body of work addresses the GSL task via algorithm unrollings under varying data assumptions.
Noteworthy contributions include GLAD (Shrivastava el al. 2020), which unrolls insternaaingmminmmiaa
iterations for Gaussian graphical model selection, Unrolled PDS (Pu et al. splitting (PDS) iterations for the GSL problem from smooth signals, and GDN (Wasserman et all 2023)
2021 which unrolls primal-dua
which unrolls lincarized noximal-gradient iterations for network doconvolution task that posits a polynomial relationship between the observed pairwise vertex distance matrix and the latent graph. Here we deal with the GSL problem from observations of smooth signals as in (Pu et all, 2021), but the optimization algorithm we unroll is different. (ef. DPG in Algorithm [ none of the previous GSL unrollings result in true NNs, provide estimates of uncertainty on their adjacency matrix predictions, nor leverage the interpretability of network parameters in the modeling process.
versus PDS), more compact and devoid of step-sizes. Additionally,
Building a probabilistic model to connect observed network data to latent graph structure has long history in the computer and social network analysis communitics; see e.g., (Coates et al., 2002] Butts 2003 Kolaczyk, 2009). Gibbs sampling was used mostly means efficiently explore the resulting network posterior rather than quantify the uncertainty the model placed on particular edges. Since then, Bayesian methods have been used with alternate network models (e.g., directed acyelic graphs specifying the structure of Bayesian networks), types of observed data (e.g., information cascades and protein-protein interactions), and posterior
approximation approaches: see (Shaghaghian & Coates, 2016 Gray et al. 2020 Jiang & Kolaczyk 2011
Williamson 2016 Pal & Coates 2019 Deleu et al. [0022.. Such approaches are typically transductive tying themselves to single training graph and require expensive joént inference of the model and the latent graph structure. Our approach only requires inference of the BNN model parameters and thus is naturally inductive, i.e., able to generalize to new nodes, or entirely new graphs. Some recent works build on such graph distribution modeling approaches in an approximale Bayesian manner, Lo incorporate the uncertainly
in an observed graph for downstream tasks with GNNs (Zhang et al.] 2019 Pal et al.] 2020). Others forgo modeling the distribution of the observed graph but take approximate Bayesian approachess to modeling with GNNs. For instance, (Opolka & Liō 2022) uses a deep graph convolutional Ganssian process with variational
posterior approximation for link prediction, and (Sevilla & Segarra 2023) pre-trains a score-matching GNN for use in annealed Langevin diffusion to draw approximate samples from the network posterior. All such Bayesian GNN approaches require (partial) observation of graph structure, and rely on approximate inference methods due to large dimensionality, Our DPG approach uses no observed graph structure (except for graph labels during training) and allows for high-fidelity posterior approxination. To the best of our knowledge, BNNs have so far not been used for GSL with uncertainty quantification.
More broadly, unrolling-inspired Bayesian deep networks have recently found success in uncertainty quan- tification for computational imaging (Barbano et al. 2020 Zhang et al. 2021 Ekmekei & Cetin 2022 The inductive bias provided by the original iterations lead to gains in data efficiency, but still have limited parameter interprelabilily and high dimensionality leading to naive priors and coarse posterior approximal ion. This exciting line of work inspired some crucial ideas in this paper, cross-pollinatio benefits to GSL and with the added value of overcoming the aforementioned Bayesian modeling and inference challenges.
3 Model-based Formulation and Optimization Preliminaries
Let G(V,E,A) be an undirected graph, where V= (I.... N}} are the vertices (or nodes), C V V are the edges, and A E RN*N is the symmetric adjacency matrix collecting the non-negative edge weights. For (i,j) & & we have A, = O. We exclude the possibility of self loops, so that A is hollow meaning A& = 0, for all i e V. For the special case of unweighted graphs that will be prominent in our models, then A E (0, 1) N X
In this paper, we consider that A is unknown and we want to estimate the latent graph structure from nodal measurements only[] To this end, we acquire graph signal observations X [NN] e RN,, where 2; denotes the signal value (i.e., a nodal attribute or feature) at vertex i E V. When P such signals are available we construct matrix X == [21 =<x1...,,<p' Ørl E X where each row a. E IR,, i 1,...,,, N, of X represents a
'This is different to the link prediction task, where one given measurements of edge status for a training subset of node pairs (plus, optionally, node attributes), and the transductive goal is to predict teed. links from the same Kolaey (009)

---

Published in Transactions on Machine Learning Research (09/2024)
voctor of features or nodal attributes at vertex i. We can summarize this datasct using pairwise vertex dissimilarity matrix, here the Euclidean distance matrix E E R where Bij = || .,13. Assuming our data lie on a smooth manifold, we interpret G as a discrete representation of this manifold. When nodes i i j E V have large edge weight Ag, reflecting close points the manifold, My will be small. Accordingly, smooth (w.r.t. G) vectors in X have small total variation or Dirichlet energy (Belkin & Nivogi
2001
namely
(X)
E Agl 5.5
n. ,, 1 -1A E
(I)
|2,ز is the entrywise f--norm of matrix Z and o is the Hadamard (entrywisc) product. The prevalence of smooth network data, for instance sensor measurements (Chepuri et al. 2017). protein function annotations (Kolaczyk 2009), and product ratings (Huang al. 2018 justifies using a smoothness criterion for the GSL task.
where 1
3.1 Graph structure learning from smooth signals
Given X assumed to be smooth on G, a popular model-based GSL approach is to minimize the Dirichlet energy in [1] w.r.t. A; see e.g., (Hu et al. 2013; Dong et al. 2016 Kalofolias 2016 Kalofolias & Perraudin The inverse problems posed in these works can be umified under the general composite formulation
2017
= arg arg min A E 11.1 + h(A)):
AEA
where the leasible set is A = E diag( (A) = 0, A., Ait 2 v., E V}, i.e., hollow, symmetric, non-nogative matrices. The regularization term ((A) typically promotes desired structure on the estimated edge set (e-g., sparsity, no isolated nodes) and can be used avoid the trivial solution A O. We henceforth use h(A) = -a1 log(AA)= + 2 || (a, 2 0 are regularization parameters), which excludes the possibility of isolated nodes and has achieved state-of-the-art results (Kalofolias) 2016).
It is convenient to reformulate (2) in uncoustrained, yet equivalent form. We start by compactly representing variable A and data matrix E with their vectorized upper triangular parts a, E le 1x-1/2 implicitly enforcing symmetry and hollowness, while also halving the problem dimension. To enforce non nen-negativity the indicator function 1fa 2 0} = {o if a 2 0 else )o) is included in the objective. Finally, we substitute the nodal degrees d= = A1 with the vectorized equivalent d = Sa, where S E (0, N is fixed binary matrix that maps vectorized edge weights to degroos. The resulting optimization problem is given by
{ 2a {2aTe e - al log((a)) + + + I(a 2 01).
a' a'
arg min
33)
GERNIN 1/2
which is convex and admits unique optimal solution; see e.g., (Saboksayr & Mateos 2021
Next, we comment on the role of the regularization parameters a, 3 and their interpretability properties. We then offer a brief discussion on optimization algorithms tackle problem (3). These ingredients will be essential to build a BNN model for supervised GSL in Sections g and
Independent interprotability of regularization parameters. Definition [ formalizes the notion of independent interpretability of regularization parameters in inverse problems such 13
Definition 1. Let x* (f1,...., E X' be the solution to an inverse problem that depends on regularization parameters pry..., Mag Consider some scalar function of the solution f: X' R. In general, the value f(x*) depends on all , When f(x") depends solely on single regularization parameter pi, then we say that μ is independently interpretable w.r.t. f(x").
The weights a and 8 are not independently interpretable w.r.t. to relevant graph characteristics, frustrating straight forward interpretation of their effect on the solution a ("(e, a, a. 3). Specifically, for fixed a, increasing 8 leads denser edge patterns, as we have (quadratically) increased the relative cost of large edge weights. Indeed, the sparsest graph is obtained for و = 0. But in general, many interesting graph characteristics, e.g., sparsity, connectivity, diameter, and edge weight magnitudo, are non-trivial functions of both a and 3; see also (Dong et al. 2016) for a similar issue.

---

Published in Transactions on Machine Learning Research (09/2024)
To facilitate independent control over the sparsity pattern and scale of the odge weights of recovered graphs, (Kalofolias. 2016 Prop. 2) introduced an equivalent (0, plaaeeaamettiinitooonn of namely
1 a' a',e, a) =V (V = da (Be, 1,
(4)
We can map from the former parameterization to the latter by first scaling e by 0 = V/,,, solving @ with 1, and finally scaling the recovered odges by the constant ó 8= va/S; we refer the reader to (Kalofolias, 2016 Kalofolias & Perraudin 2017) for proof of the equivalence claim. Due to the separable structure of the right-hand-side of [4), any GSI, algorithm would require a single inpul. parameter 0, and the obtained solution a" (0e, 1, 1, can then be scaled by 8 O. All in all, the sparsity level of a" determined solely by 0, making 0 indopendently interpretable w.r.t. sparsity. Indeod, this satisfies Definition ! with the identificattins æ" (JI. Ma)) <- 5a" (0e, 1), X + 12 N 1)/2 M4 +- 0, and f(=") + [16a"(0e; 1, I)llo, where || lo counts the number of non-zero elements of its vector argument. Moreover, is interpretable w.r.t. edge weight magnitude, but not independently so, as larger produces smaller weights [see Figure 3 (bottom-left))
de using a
3.2 Optimization algorithms
Problem (3]
has favorable structure that has been well documented, and several efficient optimization algorithms were proposed to obtain solution a" a'(e, 8) with O(N2) complexity per iteration. Specifically, a sewarrdbackward-Beee
PDS algorithm was first proposed in (Kalofolias 2016). PDS introduces a step-size parameter which must be tuned to yield satisfactory empirical convergence properties, thus increasing the overall computational burden. We find that effective step-size values lend to lie on narrow interval beyond which PDS exhibits divergent behavior, further frustrating tuning; see Appendix A..1I for a supporting discussion. GSL algorithms based on the allernating-diieetions method of multipliers (Wang et al. 2021 or majorizatiion-miiiiizaal
(Fatima et al. 2022) have been developed as well. Recently, (Saboksayr &
Mateos 2021) introduced a fast dual proximal gradient (FDPG) algorithm to solve (3), which devoid step-size parameters and - different from all three previous approaches - it comes with global convergence rate guarantees. For this problem, the strongest convergence results to date are in (Wang et al. 2023
Our starting point in this work is the FDPG optimization framework, but different from (Saboksayr & Mateos 2021) we: (i) develop a solver for the (0, () parammatteriiiionnonnn of ( and (ii) turn-off the Nesterov-type acceleration from the proximal-gradient iterations usod to solve the dual problem of (3). This yickds a dual proximal gradient (DPG) method, tabulated under Algorithm [ In a nutshell, during itcrations k 2,
Algorithm updates the vectorized adjacency matrix estimate a R N(N-1/2 an auxiliary vector of nodal degrees de E R as well as dual variables X E R used to enforce the variable splitting constraint d = Sa. A naive DPG implementation incurs O(N2) computational and memory complexitics, and we note all nonlinear operations involved (i.e., (eI.U(-) = max(0, -), ()), and v()) are pointwise on their vector arguments. As a result of the design choices (i)- the DPG algorithm requires the fewest operations per iteration and the fewest. number of parameters amonn existing solvers of (3), and devoid of any uninterpretable muisance parameters, e.g., step-sizes. FDPG was only considered on the original (a, paa-etarrmtttnnnttooonnn of
3) by instead opting for DPG iterations to solve the (0, 6) --aaammtterization of 3 we reveal independent interprotability of w.r.t. sparsity of the optimal graphs.
Next, we will unroll Algorithm to produce GSL NN which inherits its advantages namely simple, efficient, minimally parameterized layers, with independent interpretability- - forming the backbone of our BNN
4 Graph Structure Learning from Smooth Signals with Bayesian Neural Networks
So far we have described model-based approach to (point) estimation of graphs from smooth signals. In this work, we assume a labeled training dataset is available. We aim to construct a BNN model to produce uncertainty estimates on graph predictions for unseen test data.
Our BNN approach for GSL in nutshell. Here, we restrict ourselves to binary graphs a e (0. NNN(N-1)/2 weighted graphs only require a change to the ensuing likelihood function. We donote all training data as T (Te, Ta (e(0) alt)) It= an unseen test sample as (ě, a), and the collection of

---

Published in Transactions Machine Learning Research (09/2024)
Algorithm 1 Dual Proximal Gradient Descont
A ak-
Inputs: Fixed paramelers 0,6 E R and dala Initialize: an and Ag at random.
Single Layer
a
for 1,2,... ... do
0
dæ = Sa (N - 1
A 2 -1 d:. Vd+² 44N
A ag
ag max 0: 1 d 8c)
Unrolled DPG
a D
r
end for Return: da;
Figure 1: Left: The dual proximal gradient (DPG) algorithm to solve the GSL problem and truncating Algorithm| Mafter 1) iterations produces Unrolled DPG.
3
Right: Unrolling
all parameters of our yet to be defined BNN model as O. Following the principles of BNNs, our goal is to construct posterior predictive distribution p(ä ē, T) by marginalizing out model parameters θ i.e.,
M Σ M
p(a ē, =
f p(a ē. 0) p( a) I
1
p(a à, (()))
(5)
where we use M Monte Carlo draws from the posterior ((m) ~ p(O) T) to approximate the intractable integral. We can then designate our edge-wise point and uncertainty estimates as the first two moments the posterior predictive marginals p(ä; ē, T), respectively, for each candidate edge indexed by E V V.
we first discuss the development of a GSL NN which takes in the vectorized Euclidean distance matrix e of nodal observations X and assigns probability to all possible edges. We do so by unrolling Algorithm producing an GSL NN with an independently interpretable parameter w.r.t. sparsity graph outputs. Treating the model parameters of this unrolled NN as stochastic, choosing a
Roadmap. In Section 4.1
likelihood function (Section 4.2 and sctting appropriate priors (Section 5 we produce BNN. For inference we use HMC (Section 4.3) an unusual choice in BNNs made viable by the low dimensionality and fast execution of our NN, stemming from its origins as an unrolling. Pushing the Lest. inputs through each such GSL NN and averaging the resulting predictive distributions provides provides the approximate (5) posterior predictive, from which we derive edge-wise point and uncerlainty estimates as elaborated in Section 4.4
4.1 Algorithm unrolling: Iterative optimization as a neural network blueprint
Unrollings (also known as deep unfoldings) use itcrative algorithms as templates of neural architectures that are trained to approximate solutions optimization problems. Iterations are truncated and mapped to NN layers, while optimization (e-g,, regularization and step-size) parameters are turned into learnable weights. Originating from convergent iterative procedures, unrolled NNs inherit many desirable properties; namely, a low nunber of parameters, fast layer-wise execution, and favorable generalization environments (Monga et al. 2021). Typical architectural design choices include whether replace intermediate operators with more expressive (possibly pre-trained) learnable modules making them no longer 'strict' unrollings- and whether a common set of parameters should be used all layers, or, to decouple these parameters across layers. Both decisions are context dependent and often driven by the amount of data available as well as complexity considerations. Deviating from strict unrollings with shared parameters can naturally lead gains in expressive power, but often the cost. of inductive bias and training stability.
low-data
Unrolling DPG iterations. Pioneered by (Gregor & LeCun 2010 to efficiently learn sparse codes from data, algorithm unrolling ideas are recently gaining traction for GSL well. Starting from the formulation in Section 3.1 Pu ct al. 2021 unrolls PDS solver of the (a, parraamtttrriationn (3). Unrolled PDS has no independently interpretable parameters, is not a true NN (pre-activation outputs are nonlincar functions the parameters), and includes nuisance step-size parameter arguably a shortcoming gradient-based

---

Published in Transactions on Machine Learning Research (09/2024)
learning can casily produce largo-enough weight values for divergent behavior, and thus NaN's. Attempting to unroll PDS iterates for the (0, pa-aaaaatteiiiiioonn of (3 would not fix these practical problems.
We instead advocate unrolling the DPG iterations (Algorithm D developed to solve the parraaattttttiiiiiiion of (3). This way, obtain true NN without ruisance step-size parometers avoiding the aforementioned issues and reducing the parameter count by a third - while inheriting independently interpretable parameter 0 (w..t. sparsity of graph outputs). Incidentally, layers in Unrolled DPG [depicted in Figure I (right)) are markedly simpler and require fewer operations than Unrolled PDS. We denote the output of a D-layer
unrolling of Amgorithm as orp. As we would like probabilitics over candidate odges, we subtract a learnable mean shift b and drive the output through sigmoid a-),, producing our desired GSL NN output.
p = (e) - b1) E (0, N(N-1)/2
(6)
with parameters e = b). To see that Unrolled DPG is true NN, note that @ is only involved in a linear function de of the imput data. Likewise, 8 and are only involved in an affine mapping of the activations (P))). All non-linear operations (specifically squaring, square root, and max) are pointwise functions of intermediate activations. Going back to the design considerations mentioned at the beginning of this section, here we keep the unrolling strict and share parameters across layers to retain independent interpretability of 0, minimize parameter count, and simplify upcoming Bayesian inference. Tradeolls arising with model expansion using multiple imput and output channels per layer are discussed in Section 6.1
All in all, unrolled DPG is the first true NN for GSL from smooth signals, and the first strict unrolling for GSL which produces a true NN. For the various reasons laid out in the precoding discussion, Unrolled DPG of independent interest as a new model for point estimation of graph structure in a supervised setting. As we show next, it will be an integral component of the stochastic model used to construct a BNN to facilitate uncertainty quantification for adjacency matrix predictions.
4.2 Stochastic model
Here we specify stochastic model for the random variables of interest, namely the binary adjacency matrix a, nodal data entering via the Euclidean distance matrix e, and the BNN weights O. The Bayesian posterior from which we wish to sample satisfies p(O '7) x P(T, Te, ())(O), and a first step in BNN design is to the training data T allows the likelihood factorize over samples P(Ta Te, +) (((")((()))) eltt) (). Moreover, assuming edges within a graph sample (*) are mutually conditionally independent given parameters O leads to further likelihood factorization P(Ta Te, O) = -IL,, (I p(a!") e()), O). We model | e, O ~ Bernoulli(f;), where the success (or edge E V x presence) probability is given by the output the Unrolled DPG network, i.e.,
specify the likelihood p(a| e, Q) and the prior ()).. An iid. assumption
p(a(()
d. = a (TT) b) as in 06 Putting all the pieces together, the final expression for the likelihood is
T N(N-1)/
TTa Ta 9) = II II
10 (1- (0) (1- (1
(7)
We reiterate that, crucially, the Unrolled DPG outputs enter the stochastic model via the likelihood, as the means of the edge distributions. The specification of the prior p(O) will be addressed in Section 5
4.3 Inference
We aim to generate M Monte Carlo draws from the posterior (m)) ~ p(O) T) x p(Ta I Te., ())( In
modern BNNs based overparameterized deep networks, high dimensionality and parameter unidentifiability are prevalent. This translates to highly multi-modal posteriors which make sampling challenging (Izmailoy al., 2021). Even when posterior geometries are more benign, the computational and memory requirements for evaluating the network and its gradients render the generation of Monte Carlo posterior samples impractical. As a typical workaround one can resort to posterior approximation using inexpensive mini-batch methods such mean-field variational inference or stochastic-rradien. MCMC (lanailov al. 2021). In contrast, we

---

Published in Transactions on Machine Learning Research (09/2024)
now argue that generation of high-fidelity Monte Carlo posterior samples using HMC is uniquely compatible with our proposed BNN; for implementation details see Section 6.1
For starters, Unrolled DPG's repetitive layers simplify model construction and allow straightforwwrd com- pilation in automatic differentiation software, significantly boosting runtime efficiency. The low parameter count. of Unrolled DPG facilitates the use of forward-mode auto-differentiation store intermediate activations and perform a backward pass, thus it ensures memory usage does not increase with model depth D. Morcover, as Unrolled DPG can effectively approximate inverse problem solutions with relatively shallow depths (sce Section G) selecting a smaller D significantly reduces runtime complexity. For small- to moderateel-siieed graphs and datasets, our computational and memory requirements for network and gradient evaluation are low; see Section [ for GSL problem instances where inference is attainable in minutes on M2 MacBook laptop. The limited parameter count also aids in sampling elficiency as we avoid the curse of dimensionality that complicates sampling in higher-dimensione models. Finally, the ability to place informative priors over independently interpretable parameters (as we do in Section 5 is known to smoothen the posterior goometry, espocially in data scarce regimes where the likelihood and prior are of comparable magnitude (Gelman et al. 1995
this eliminates the need to
4.4 Prediction
By conditioning on data T and integrating out model parameters θ, we oblain a predictive distribution on unseen graph adjacency matrices given nodal signals é. As the integral is intractable, we use the M posterior samples obtained via HMC in the inference stage to approximate the predictive distribution p(a T) This approximation process is summarized in
Importantly, we generate samples from the posterior predictive by randomly drawing from the sampling distribution with each parameter sample plugged in, i.e. (m)) ~ p(ā é, @(m)). Given the form of our BNN's s stochastic model as introduced in Section 4.2, such a draw reduces sampling Bernoulli distribution for each possible edge. Randomly drawing from the sampling distribution is critical as it accounts for both forms of uncertainty in posterior predictive quantities, namely, sampling uncertainty and estimation uncertainty GGelman et al.) 1995). Using those posterior predictive samples, we can approximate the mean ('prod. mean') and standard deviation ('pred. stdv:") of the edge- marginals of the posterior predictive as
M and Var(a, Tē, xc
M (m)
E Eaa
T R3
Σ (m)
E(a!"h
(a
Elā, ē, T))²
(8)
M
M
m=
Naturally, B[ā; ê, 7] is a Bayesian point estimate for ā,, while Varlā, | ê,, TT offers measure of uncertainty in such prediction edge i.
5 Bayesian Modeling of Unrolling-Base Based BNNs with Independent Interpretability
In this section, present a method for Bayesian modeling for BNNs which use a network produced by unrolling an optimization algorithm to solve an inverse problem with independent interpretability. We instantiale these ideas on the GSL problem (3) where solutions undirected graphs and use prior knowledge over the sparsity of such graphs to shape prior distributions over the corresponding independently interpretable parameter in Unrolled DPG introducod Section 4.1
optimmiss
5.1 Prior modeling
For Bayesian models, priors over unobserved quantities play two main roles: encoding information germane to the problem being analyzed and aiding the ensuing Bayesian inferences. Despite the name, a prior can in general only be interpreted in the context of the likelihood with which it will be paired. There are many types of priors, and we here we list the common ones in order of degree in which it is intended to affect the information in the likelihood: non-informative, reference, structural, regularizing, weakly informative, and strongly informative (Gelman et al. 2017 The more domain specific information present, the further to the

---

Published in Transactions Machine Learning Research (09/2024)
Inputs
Bayesian Modeling
Prior beliefa
Data
T = {e(t) [ I S
Outputs
prior p(6)
Prior 0
Initial p())
Unrolled
Sparsity
NN
1
Prior Pred. Check
Refined p(@)
Sparsity
Independent
Sparsity
Inference
A (m)
p(()) T)
10(1) (0(,,,,(MM)))
{M)
Interpretability
Real
Posterior Pred.
* data statanto
Validate fit
Prior Beliefs
Check
Sparsity
Sparsity
Figure 2: Bayesian workflow with independent interpretability. Inputs: A labeled data set T, inverse problem with independently interpretable parameter 0 w.r.t. some characteristic of the solution, prior beliefs over this solution characteristic, and an unrolled NN which approximate solutions the inverse problem. Bayesian Modeling: We use independent. interpretability of 0 to convert, prior beliefs on solution characteristics to a prior distribution on the independently interpretable parameter. We use prior predictive checks to ensure priors generate data sets which encompass all plausible values of the solution characteristic, while still preferentially generating data sets which we believe are more likely apriori. If not, we can leverage independent interpretability to refine the prior. We then sample from the posterior, and use posterior predictive checks to provide subjective validation of model fit.
end of this list we may be able to move, which often results in better behaved posterior geometries, and thus more stable Bayesian inference. Exactly how this domain specific information is encoded in the prior depends on both the problem and the specific chosen model.
Informative priors with independent interprotability. In the context of the GSL problem dealt with here, independent interpretability makes setting strongly informative prior over DPG's independently interpretable parameter 0 feasible. To this end, one first discretizes 0 over few orders of magnitude. For each value in the grid, we run Algorithm [ on a subset of observed inputs Te and record the relevant data characteristic (edge sparsity) of each recovered solution. We then plot. the histogram of such data characteristic and observe their agreement with prior beliefs. Finally, one chooses an appropriate parametric distribution p(0) which approximates this relative level of agreementt across the range 0 values. We can use the recovered solutions at a priori probabale 0 values to set weakly informative priors over the remaining model parameters. In our setting, that involves the scale of the edge weights of the recovered solutions. In Scction 5.2 we discuss evaluation of this initial p(O) in terms of the predictions makes. For visualization of this prior modeling workflow, see Figure 2 A numerical example is now presented to ground this methodology.
Example (Informative prior modeling of DPG parameters). In this example that continues in Section 5.2 we use a data set T of T = 50 random geometric graphs (N = 20 nodes, connectivity of {), denoted RG and their corresponding analytic Euclidean distance matrices as inputs defined in Section See Appendix A.4 for similar analysis on other random graph distributions. Prior modeling and upcoming prior predictive checks require only the distance matrices e, and we use only 5 such distance matrices from T.
Suppose we have prior beliefs on the sparsity related characteristics of recovered graphs, namely sparsity itself (=1-edgy density) the number of connected components. For example, suppose we believe recovered graphs should have edge densities around [.05,_5] and < connected components. Since Unrolled DPG approximates solutions to (3) and determines such sparsity related characteristics independently of other optimization parameters we can simply run Algorithm I to convergence using the 5 inputs discretizod values across several orders of magnitude, as demonstrated in Figure 3 (top-left). We observe 0 E 1, 104] produces solutions with sparsity characteristics consistent with our prior beliefs. Choosing 0
set of
10

---

Published in Transactions Machine Learning Research (09/2024)
1.0
70
Mean Edge Density
normal cf
10
original prior altered prior posterior labels
0.4
0.2
0.0
1011
0
.25
.5
.75
1
10 207
Figure 3: Left: Prior modeling with independently interpretable parameter 0. We run Algorithm D to couvergence over discretized 0. Top: Larger 0 produces sparser graphs. Bollom: Larger produces smaller edge weight magnitudes. Right: Predictive Checks. The original prior generates very few data sets with densities of ~ .9, a value we feel is plausible. We can use the independent interprctability of 9 w.r.t. edge density to alter its prior accordingly. A prior predictive check with this altered prior now encompasses these plausible data sets. The posterior predictive check ensures the replicated data sets now sampled after conditioning on the training data have similar edge densities to the observed training labels. Indeed, these edge densities, denoted as 'posterior', are lightly distributed around the average edge densily of the labels.
Lognormal(O,44 4) concentrates approximately 75% probability mass on interval [10-1, 104] while still covering broader range of values to accommodate uncertainty stemming from sampling variance (small data set) and approximation error (truncated iterations). Priors are placed over the non-independentll interpretable parameters and with the purpose of guarding against implausible values and stabilizing posterior sampling: such priors sometimes called 'weakly informative' (Gelman et al. 1995). Because (T) b will be driven through a sigmoid, we aim for both terms to be comparable magnitude. Since our graphs are binary, 8 (e) can reasonably be assumed to be x 1. Utilizing Algorithm [ solutions obtained over the 0 grid, we examine the edge weight distribution (prior to scaling by 8) in Figure 3 (bottom-left) to inform p(0). Setting 8 ~ Lognormal(2, 2) brings scaled edge weights close to for high (prior) probability values of 0. Similarly, setting 6 b~ Lognormal(1, 2) ensures b is also approximately 1. Both distributions assign probability mass across several orders of magnitude, both above and below 1, reflecting the breadth of our uncertainty concerning their specific value rauges. Next, we employ prior predictive chocks to validate that with the established priors our model generates graphs that align with our prior beliefs.
5.2 Predictive checking
In Bayesian statisties, predictive checks evaluate model's elficacy in capturing data characteristies like means, standard deviations, and quantiles (Gelman et al., 1995p. Predictive checks leverage the existence of a model of the joint distribution p(T, @) between data and parameters. This model allows us to draw samples from the data marginal- called replicated data - by drawing samples from the joint and simply dropping the parameter samples. Prior predictive checks draw replicated data from the joint. before conditioning on data T, while posterior predictive checks do after. In both cases, apply the chosen statistic capturing data characteristic of interest. to the replicated data, producing a histogram. The goal in prior predictive checking to shape priors that encompass all plausible data sets, while still guiding the model towards data sets we deem more tikely apriori. Thus prior predictive checking often consists of visual inspection of the histogram to ensure this holds, and adjusting the location and/or or scale of prior distributions until does. The goal in posterior predictive checking to subjectively validate model fit; here we compare the statistic.

---

Published in Transactions on Machine Learning Research (09/2024)
on the replicatod data (a histogram) to the same statistic applied to the actual data T (a single scalar). A well-fit model should have a histogram tightly concentrated around the real data statistic.
In typical BNNs, the lack of parameter interpretability prevents effective use of predictive checking. (Wenzel et al. 2020) highlights this issue by demonstrating that an isotropic Gaussian prior on NN weights (ResNet-20)
lails lo generate data consistent with prior expectations in image classification lasks. But the lack of parameter interpretability prevents the use of these findings to modify the prior for improved alignment. Below, we instantiate predictive chocking for DPG, with average edge density as our test statistic.
Example (Prior predictive check over DPG parameters). To perform a prior prodictive check we use the 5 inputs from Te and draw 10t replicated data sets aFP. Figure 3 (right) shows the histogram of average edge densities of replicated data sets under the prior settings laid out in Section [.1] which we call the 'original prior'. We observe that such prior succeeds in producing data sets that coincide with those we deem more likely apriori, but falls short of encompassing all plausible data sels, namely those with edge densities of = 0.9. To address this, we lean on independent interpretability of 0 w.r.t. the sparsity of graph solutions: decrcasing the location of p(0) will increase edge densitics (lower sparsity) of graph solutions, and so we lower p(0)'s 's location parameter from 0 to -2 2. with all other parameters of the prior distribution remaining the same. We call this new prior the 'altered prior' Repeating the prior predictive check with this 'altered prior' we now observe 12% of replicated data sets with edge densities in [.75, 1], as opposed to 4% before, and we confirm through visual inspection that data sels with all possible edge densities are indeed produced. The 'altered prior' thus encompasses all plausible data sets while still preferentially generating data sets we feel are more likely apriori.
Example (Posterior predictive check over DPG parameters). Now, we repeat this procedure, but draw replicated data sets from the joint after conditioning on T. We perform inference drawing M = 10 posterior samples; for each posterior sample we draw a single replicated data set. In Figure 3 (right) we plot the histogram of the average edge densities of these replicated data sets, denoted 'posterior' and compare against the average edge density of the graph labels in T, denoted 'labels'. Because all outcomes are tightly distributed around the mcan edge density of the real data, we can have confidence the model parameters have fit appropriately.
Experiments
We have introduced DPG, the first BNN for GSL from smooth signals, which is capable of providing estimates of uncertainly of its edge predictions. We showed DPG can ellectively incorporate prior information into the prior distribution over its parameters. In this section, we evaluate DPG across synthetic and real datasets, and introduce other bascline models for comparison, including more expressive variant of DPG.
6.1 Models, metrics, and experimental details
Strict unrollings: DPG and PDS. In the following experiments, the prior used for the DPG's parameters (0, 6,6} is the 'altered prior' as developed in Section 0 ~ Loggormall 12, 4), 8 ~ Lognormal(2, 2), and b b~ Lognormal(1, 2). We similarly refer to the BNN with Unrolled PDS as its NN model and no change to the stochastic model as PDS. As none of PDS's parameters (a, 3, y, b} have independent interpretability, we cannot use the prior modeling techniques outlined in Scction 5 Attempting HMC on PDS produces significant number of divergent simulated Hamiltonian trajectories, a phenomenon known to be caused by high postcrior curvature (Betancourt, 2016). This makes HMC run slowly, produce poorly mixed chains, and ultimately non-performant PDS models. Indeed, we find that values of step-size 7 which produce divergent behavior (very low likelihood) are close those which are most performant (very high likelihood), indicating high-curvature in the likelihood function, and thus the posterior; see Figure [ (left). Because Y is not interpretable, il is unclear how to shape p(7) to reduce posterior curvature without first running a discrete search. Indeed, to find performant PDS model amenable to efficient HMC, we first run such a discrete scarch, fix y to found performant value of 0.1, and then set priors a, B ~ LogNormal 10) and b b~ (0, 10"). Both model-basod algorithms in (Wang et al. 2023) and FDPG [aboksaar & Matcos (2021) a characteristic found not to be
come with faster convergence rate guarantees than DPG in Algorithm
12

---

Published in Transactions on Machine Learning Research (09/2024)
critical in the unrolled setting (Monga et al. 2021 They involve complex operations and have not been unrolled in prior work, unlike PDS. Specifically, {Wang et al., 2023) use 6 parameters, including 2 step-sizes, complicating stable unrolling and Bayesian inference, and so we exclude these methods from our comparisons.
Model expansion via MIMO and partial stochasticity: DPG-MIMO and DPG-MIMO-E. Here, we expand the Unrolled DPG NN for more expressive power by making each layer multi-inpul multi-oulput (MIM)), Each MIMO layer maps inputs (At-1 E RNxC, a E IR IRN(NN11/2xC) to outputs (Ae E R R ag E [=N(--1/2XC), where C' is the fixed number of input and output channels across layers, As before, layors share parameters, now A E RCXC In the k-th layer, parameter 85z E IR is used to process A5-1(:: 1] and ax-il:; as in a regular DPG iteration. Doing so for i E fl,...,C C} and averaging the refined A's and a's produces Ax and a [s.],, respectively. We use parameters 8 e R and d E R to produce edge probabilities (gapd - 61). The priors are unchanged from the 'altered prior' developed in the non-MIMO setting from Section [ The increased parameterization and complexity of operations make the posterior geometry significantly more complex, such that we could not find a setup which produced well-mixed posterior sampling via HMC. Instead, we resort to Maximum a Posteriori (MAP) estimation, equivalent to maximizing the posterior with fixed observed data, using full gradient descent. We call this non-stochastic setup DPG-MIMO.
common approach to overcome the intractable posterior inference in BNNs is partial stochasticity, where we learn point estimates of subset of the parameters and distributions over the rest. Recent work has shown partial stochasticity of a BNN can produce similarly useful posterior predictive distributions, even outperforming fully stochastic networks 'decapitate' the MAP trained DPG-MIMO by discarding δMAP and 5MAP; instead we feed each of the C output channels apl::]] of the base MAP DPG-MIMO (only parameterized by MAP)) into a now depth 20 stochastic single channel DPG 8,13,
prediction some setting (Sharma et al.] 2022). Here, we
(apl=>]) 6,130(ap(::)) We average their output, shift by new stochastic b, and drive through a sigmoid: of Σ 1= (anl::))) - 61). We can now run inference on these stochastic head parameters (0,,81,-. Oc, &c, b} keeping OMAP fixed. We denote this model as DPG-MIMO-E. All MIMO models use C = 4: C = 8 offered negligible performance gains and posed (partially stochastic) inference challenges, while C was less performant than C 4.
Metrics. To provide summaries of our models' predictive accuracy and quality of uncertainty we use two proper scoring rules: the Negative Log-Likelihood (NLL) p(a ē, and the Brior Score I E p(a ē e) - a.))). Beyond proper scoring rules, we use Expected Calibration Error (ECE) (Guo et al. 2017 which measures the correspondence between prodicted probabilities and empirical accuracy, and Error, defined as the percentage disagreement between a thresholded pred. mean Eoyr(a (ā ē, T] 0.5 and the actual label a. See Appendix A.2 for full details. Hyperparameters and inference details. Utilizing NumPyro's NUTS implementation of HMC (Phan let al. 2019), our experiments run 4 chains in parallel, each chain taking 500 warm-up sleps before generating 1000 samples, accumulating M = 4000 total samples. We use depth D = 200 for all models unless otherwise specified, as we did not observe significant improvements in predictive performance beyond this depth. We
choose ag- = - -1 (reflocting prior uncertainty of existent edges) and Au = 17 1 (approximate average value of limiting A when running Algorithm I to convergence on RG analytical distance matrices for 0 1) for all experiments. We did not find performance to be sensitive to such choices. Further details can be found in
Appendix A.2
6.2 Synthetic data evaluation
Generative smooth signal model. We build on (Dong et al. 2016 's work on probabilistic smooth graph signal generation to validate our methods using synthetic dala. Let L UAU be the eigendecompasitiinn of the graph Laplacian L = diag(A1) - A, with diagonal eigenvalue matrix A having associated eigenvalues A; sorted in increasing order, u, (i-th column of U) is the eigenvector of L with eigenvalue A;- Further take L to be the Moore-Penrose pseudoinverse of L, with eigenvalues Ai= =- X,- when X; > 0, and X! := 0 otherwise. Dong et al., 2016) proposed that smooth signals can be generated from a colored Ganssian distribution
as x = p + Σ, 6;4,, where &; ~ (O x/) and μ E RN denotes an arbitrary mean vector. Therefore Nn, Lt). To sample such distribution, suffices to draw an initial non-smooth signal an ~ AO I)
13

---

Published in Transactions Machine Learning Research (09/2024)
014
DPS
PDS
.004
DPG -MIDDE
10
Accuracy
012 .044
.012
.001
8
NLL
BS
Error
ECE
Confidence
Figure 4: Effective i.i.d. generalization. Both DPG and PDS are performant and well calibrated BNNs, although PDS requires ss 3x more time for inference. Further performance gains are found with the expanded, partially stochastic DPG-MIMO-E model. The rightmost plot (reliability diagram) indicates high calibration across confidence levels; the left-most bin is least calibrated but contains < 0.4% of edges across all models. This plot shows experiments on = 20 RG graphs. Error bars are scaled by .05 for compact visual effect.
Eorla, l Tl
p
0.91
label
pred. mean pred. stdv
.25 pred. stdv
.75
10
Figure 5: Qualitative i..d. generalization. Left: For random test sample show the label a, and estimated mean (pred. mean) and standard deviation (pred. stdv) of the edge-wise marginal posterior predictive p(ā, ē, T) Comparing pred. mean to the label adds qualitative evidence that the model is well to the data. Right: The edge-wise uncertainty estimate (pred. stdv.) and error (ā, -errlã T] have strong positive Pearson correlation 0.91.
an- When μ this procedure produces signals such that the power on and then compute + 14 V Li
the i-th frequency component is 87 ~ T(k = 2- 217). Thus the expected power B[2;] X} is inversely proportional to associated eigenvalue, concentrating energy on the low frequencies spectrum. We construct the data matrix X (21...., Ørl I RNXP, where Fp drawn i.i.d. from WV L!) as described above. Recalling the definition of the Euclidean distance matrix E in Section g and using the fact that az 2; ~ [[k 2 0 247)) and B| æ,] ΣØ- B[xap";pp = Σ Cov(dip, x L Vi.j), we can show E E = diag Lt)T + diag (tng(L))1> 2L which we call the 'analytic distance matrix'. We henceforth E[E] and finite sample approximations from P signals for evaluation.
the Laplacian
Evaluation of ii.d. genoralization. Here, we train and test DPG, PDS, and DPG-MIMO-E on N 20 RGy graphs and their correspouding analytic distance matrices. We use T graphs for training and 100 for testing. We present the results in Figure 4 DPG and PDS perform comparably; although DPG has marginally better accuracy and calibration. Significant improvement found the more expressive DPG-MIMO-E across all metrics, showing our simple 3-parameter model be effectively expanded. These models are similarly performant across graph distributions (see the experiments reported in Table I and also in Appendix A.2 we show a single graph ensemble here for brevity.
Figure depicts estimates of the first two moments of the posterior predictive distributions produced by DPG on a random test sample. We observe well-calibrated confidence and uncertainty, plus a strong correlation between magnitude and uncertainty; indeed useful uncertainty estimate should be proxy for error.

---

Published in Transactions Machine Learning Research (09/2024)
NLL
BS
Error
ECE
DPG
10-2
PDS
10
10
10
DPG-MIMO DPG-MIMO-E
10
10
10
10
6 10
P
309
10"
1.0 10a
10
P
Figure 6: Detection of covariate shift across models. Using RG2 graphs with N = 20 nodes, we fit models on analytic Euclidean distance matrices and evaluate on corrupted distance matrices in a test set. Fewer signals P used tends to increase corruption magnitude. Log-scaling unintentionally makes error bars appear to grow with P.
Predictive uncortainty under distribution shift. We evaluate two forms of distribution shift: corruptions to the noiseless analytic distance matrix E[E] and label mismatch. To investigate corruptions, we train using = 50 RGg g (N = 20) labels and their analytic distance matrix, and test on 100 RG samples which instead use P signals to compute an Euclidean distance malrix E. Fewer samples P tend to produce larger corruption magnitudess ie., deviations from E E[ Figure shows that indeod, all models display lower predictive accuracy and higher uncertainty on the increasingly shifted imput data, with the simpler models outperforming in the presence of larger corruption. To investigate label mismatch, models are fit to the same training data as above T 50 RG (N- 20) labels with analytic distance matrix input but now tested on 100 test samples from the following different N 20 random graph distributions: (i) random geometric graphs with connectivity radius (RGg), Erdös-Rényi graphs with edge probability p p= 0.5 (ER ). and Barabási-Alben graphs with lower accuracy (f Brier Score) and commensurately higher uncertainty (t NLL) on these mismatched data. DPG methods tend maintain better calibration than PDS.
link per node (BA1). Results are displayed in Table [ All models show
Table 1: Detection of label mismatch. Models are fit to RG y and tested on 100 samples from the same RG as well as three different graph distributions. For each metric, the mean over the test set reported.
NLL
BS (x10 ?)
ECE (x10 9)
RG:
RG:
ER
BA1
RG;
RG:
ER
BA1
RG:
RG:
ER1
BA1
DPG
10.33
17.53
33.01
20.91
1.29
2.29
4.66
2.10
3.42
52.06
171.38
16.60
PDS
10.32
17.70
33.43
20.80
1.29
2.33
4.80
2.10
3.75
52.87
173.53
16.60
MPM-
9.19
17.13
40.49
13.37
1.19
1.74
4.62
2.06
3.50
54.61
161.71
11.24
DPG-MIMO-E
8.35
12.66
37.77
8.35
1.07
1.52
7.82
1.32
2.40
29.17
29.07
2.84
Scaling to larger graphs. Direct inference large graph settings is challenged by substantial memory demands. Specifically, providing gradients for HMC via naive backpropagation nocossitates storing all intermediate outputs, while full Bayesian inference mandates holding the full dats set in memory, cumulatively leading to a memory footprint of O(DNTT) Adopting forward-man mode ditteiiiferntiiaioon partially mitigates this issue by removing depth dependency, effectively reducing memory complexity to O(N2T). The time complexity for MCMC also presents scalability challenges: each forward pass has time complexity of (DD*T), and each posterior sample requires multiple forward passes. Attempting
instead perform transfor learning where inference occurs with smaller graphs to then test. on larger graphs still faces an obstacle. The objective function (3) contains the terms 2a e = 2 2 -NN-1)/2 a,e,, - E|lall = & INN N(N-1)/2
1)/2 af, and -o1 log(Sa) -a EN (og(Sa); The former two terms involve N(N- 1)/2 summands, while the

---

Published in Transactions on Machine Learning Research (09/2024)
latter is a sum over N clements. This results in disparate growth rates for these terms as N increases, which poses challenge for parameter optimization across different graph sizes, iee, find parameters optimized for a graph with N, nodes are not effective for N >> N₁. Moreover, the differing growth rates cause standard cardinaliyy-based normalization schemes (dividing each term by its number summands) to fail, and determining analytically how the parameters should change as a function of size is non-trivial; see Appendix A.3 for a detailed discussion.
In light of this, we perform an adjusted transfer learning experiment by fitting the empirical growth trends of MAP DPG parameter estimates on N = {20, 50, } ERy graphs and their correpooningg analytic distance matrices. By using a moderate depth D 200 and T = 10 training samples, MAP inference on larger graphs with N = 200 nodes takes ~ 1 hour on a M2 MacBook laptop. Using this empirical parameter fit. we can extrapolate parameter values and perform transfer learning on 100 ER2 test graphs of size up to N = 1000; again done locally without any GPU. The transfer learning experiment reveals an expected but graceful decay in performance in NLL as N increases. Further information and plots on these scaling experiments are available in Appendix A.3
6.3 Ablation studies
Prior modeling. To inspect the influence of informative prior modeling on DPG, we define model DPG-U" which replaces DPG's informative priors with the following uninformative priors: log 0 ~ U [10-5, 10 8.6 b.b ~ (0, 10 What we find is that in data-rich regimes an informative prior mostly acts to improve efficiency of posterior inference, e.g., when fitting to T = 50 RG 3 graphs with N = 20 nodes (using analytic distance matrices) and testing on 100 i.idd samplos, it roduces the time needed to generate M 4000 samples by factor of 7.8x and increases the effective sample size- measure of the number of independent samples with the same estimation power as the observed correlated samples (Gelman et. al. 1995) for 0 (FSSe) by a factor of 5x, In data poor regimes it also tends to help slow down performance degradation, e.g., when instead using T = 2 with the same graph dala, NLL and ECE are 37% and 13.7% better with the prior Lhan without. See Table 3 in Appendix A.4 for the full numerical results.
Partial stochasticity. We conducted an ablation study investigating the benefits of adding partial stochasticity to the DPG-MIMO model (C - D, = 200) using MAP point estimates; the partially stochastic setup is described in Section [6.]] The training and test sets identical the i.i.d. generalization experiment above. Our experiments showed that intrudig partial stochasticity in DPG-MIMO-E markedly improved NLL, BS, error, and ECE by 9.1%, 10.3%, 9.0%, and 31.4%, respectively.
6.4 Real data evaluation
Quantifying uncertainty in networks learnt from S&P500 stock prices. To verify that DPG provides useful measures of uncertainty on edge predictions based on real data, we first use the financial dataset presented in (ee Miranda Cardoso et al. 2021). The time scries consist of S&P500 daily stock prices from three sectors (Communication Services, Utilities, and Real Estate), comprising a total of N = 82 stocks. The data spans the period from Jan. 3rd 2014 to Dec. 29th 2017, yielding p 1006 daily observations. We divided these stocks equally into training and testing sets. For both sets, we created log-returns data madrix, denoted as X N/2x/ Specifically, X,, = log SP3, - log SPij- where SP3s siguilies the closing price of the i-th stock on the j-th day. From each matrix (train and test), we derived a matrix of Pearson correlation coefficients Σ. We take the input to be E < 11 [2], thus yielding measure of dissimilarity. We also constructed a binary label graph, assigning an edge weight value of for stocks within the same soctor and 0 for pairs in different sectors Thus, our training and testing datasets each contain single sample. Nodes from the same sector are numbered contiguously creating a block diagonal adjacency matrix structure, displayed with the red outline in Figure 7 (left).
We use DPG with depth D= = 200 and identily a high-performing parameter value range for 0 via predictive checking as in Section 5.2. Such values aligned closely with those found in the synthetic experiments, and so
we keep the priors unchanged. We run Bayesian parameter inference on a M2 MacBook laptop which takes about 2 minutes; we visualize the input, empirical mean, and standard deviation of the postcrior predictive on the test sample in Figure 7 (left.). Notably, while our mean recovery is robust, there are areas where it
16

---

Published in Transactions on Machine Learning Research (09/2024)
input
pred. mean
pred. stdv.
input
pred. mean
pred. stdv.
Figure 7: Quantifying Uncertainty with Financial Data and Images of Digits. Left: S&P500. We randomly split stocks from 3 sectors of the S&P500 and compute their input 11 |Σ], where E is the matrix of Pearson correlation coefficients, using log daily returns over an extended period. The graph label connects stocks of the same sector indicated by red block diagonal outline. There is only a single train and test sample. Here, we display the lest sample inpul and estimates of the mean (pred. mean) and standard deviation (pred. stdv.) of the posterior predictive. In pred. mean, white (black) inside (outside) the block diagonal indicates correct predietion for both experiments. Pred. mean which don't match their label tend to have larger uncertainty. Error and pred. stdv. have a Pearson correlation of 0.70 over the test set. Right: MNIST digits. We construct graphs of MNIST digits '1' and "2", connecting nodes of the same digit, similarly outlined in red ('I's are the first block). The input is the log pairwise Euclidean distance of their vectorized image. Notice 'I's lend to be much closer to each other than "2's. DPG again shows an ability to place higher uncertainty on edges with higher error. Error and pred. stdv. have a Pearson correlation of 0.62 over the test set. Pred. stdv. in both plots are maximum normalized for visual clarily.
deviates from the label. These areas tend to exhibit increased variation in the posterior predictive. The Pearson correlation coelficient between the error and predictive standard deviation on all edges, true positive edges, and true negative edges is 0.70, 0.70, and 0.79, respectively, suggests that our model's uncertainty can be useful proxy for error in the absence of labels in this financial lest case.
Learning the graph of MNIST digits and 2. To further demonstrate DPG's capability to quantify uncertainty on graphs estimated from images of digits, we emulate the experiment from (Kalofolias. 2016) which learns a graph to classify handwritten digits "1" and "2" from the MNIST database (LeCun et al. 1998). Each digit is an image of 28 28 pixels, each pixel taking integer value in O,.... 255. As (Kalofolias
2016 reports, this problem is particular because digits 'I' are much close to each other than '2' are (average square distance of 45 and 102, respectively). A single sample in our dataset is constructed as follows. We randomly sample 25 images of digits "1" and "2". Each image represents node in this graph sample, hence N= 50. We connect nodes of the same digit with binary edge. The image corresponding to each node is vectorized into ã. R228 = I....N,, .N, becoming the nodal feature vector. For case of label visualization, we order the nodes such that all "1" digits come before "2" digits, which creates a block diagonal adjacency matrix, indicated by the red outline in Figure 7 (right). 'he nodal dissimilarity matrix E is computed as the log pairwise Euclidean distance of the node features (vectorized digit images). We construct training and lest set of size T = 5 and 50, respectively.
We use the same modeling and inference setup as in the previous real data experiment; inference takes z 10 minutes. Figure 7 (right) displays the input E, pred. mean, and pred. stdv. on a random test sample. Visual inspection reveals performant mean prediction, and that edges with high errors tend to have high variation. Indeed, across the entire test set the two have strong positive Pearson correlation coefficient over all edges, true positive edges, and true negalive edges of 0.62, 0.72, and 0.51, respectively, suggesting DPG effectively quantifies predictive uncertainty of edges in this image analysis setting.
Concluding summary, limitations, and the road ahead
In this work we identify independent interpretability of (regularization) parameters in inverse problems as a key property, which allows one to incorporate prior information on solution characteristics into prior distributions over the NN parameters of an unrolled optimization algorithm. We investigate an invorse problem with this independent interpretability property in the context of GSL from smooth signals, and
17

---

Published in Transactions Machine Learning Research (09/2024)
introduce an optimization algorithm that is simpler than existing methods, without sacrificing cstimation performance. We unroll this algorithm producing the first true NN for GSL. from smooth signals. We leverage independent interpretability to incorporate prior information about sparsity charactcristics of sought graphs into prior distributions over unrolled network parameters, producing the first BNN for GSL. from smooth signal observations. We lean into the advantages of unrollings low parameter dimensionality, fast compiler and auto-grad friendly layers, as well as the empirical need for shallow networks- - to perform posterior approximation using MCMC sampling. Doing so yields high-quality and well-calibrated uncertainty estimates over edge predictions, as demonstrated via comprehensive experiments with synthetic and real datasets.
The primary limitation of approach lies in its scalability moderate- and large-sized graphs and datasets. The computational and memory requirements to achieve asymptotically exact posterior inference through MCMC sampling are substantial, owing to the necessity for numerous forward network passes per posterior sample and the requirement to store the entire data set in memory. Promising directions of future work include exploration of non-asymptotically exact posterior inference methods, namely variational inference, which typically roquires much less computation and allows for mini-batch training and thus use of larger datasets (Jospin et al. 2022). As we produce distributions over output graphs, future work can explore Bayesian decision analysis with the introduction of a utility function, or even using DPG as a module within a larger system, where propagation of uncertainty over the inferred graph is important.
Acknowledgments
Work in this paper was supported in part by the NSF under award ECCS-2231036. The authors would like to thank Canberk Ekmckei for fruitful discussions during the carly stages of this project.
References
Riccardo Barbano, Zeljko Kereta, Chen Zhang, Andreas Hauptmann, Simon Arridge, and Bangti Jin. Quantifying sources of uncertainty in deep learning based image reconstruction. In NewrIPS Work. Deep Learn. Inverse Probl., 2020.
Amir Bock and Mare Teboulle, A fast dual proximal gradient algorithm for convex minimization and applications. Oper. Res. Lett., 42(1):1 6, 2014.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. NewrIPS, 14, 2001.
Michael Betancourt. Diagnosing suboptimal cotangent disintegrations in hamiltonian monte carlo. Xrviv preprint orXiv:6004.00633 2016.
Christopher M Bishop. Nearal networks for pattern recognition. Oxford university press, 1995.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Sulam, and Pierre Vandergheynst. Geometric deep learning: Going beyond Euclidean data. IEEE Signal Process. Mag., 34(4):18 42, 2017.
Carter T Butts. Network inference, error, and informant (in) accuracy: a Bayesian approach. Soc. Netw., 2003.
Xiaodong Cai, Juan Andrés Bazerque, and Georgios B Giannakis. Inference of gene regulatory networks with sparse structural equation models exploiting genetic pertarbations. PLoS Compul. Biol., 2013.
Sundeop Prabhakar Chepuri, Sijia Liu, Geert Leus, and Alfred O Hero. Learning sparse graphs under hnoothness prior. Proc. Int. Conf. Acoustics, Speech, Signal Process., 2017.
Mark Coates, Rui Castro, Robert Nowak, Manik Gadhiok, Ryan King, and Yolanda Tsang. Maximum likelihood network topology identification from edge-based unicast measurements. ACM SIGMETRICS Perform. Eval. Rew., 2002.
Luca Cosmo, Anees Kazi, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Latent-gran graph learning for disease prediction. In Med. Image Comput. Comput. Assist. Intervent., 2020.
18

---

Published in Transactions Machine Learning Research (09/2024)
Forrest W Crawford. Hidden network reconstruction from information diffusion. In Int. Conf. Inform. Fusion., 2015.
Jose Vinicius de Miranda Cardoso, Jiaxi Ying, and Daniel Palomar. Graphical models in heavy-tailed markets. NewrIPS, 2021.
Tristan Deleu, António Góis, Chris Chinenye Emezue, Mansi Rankawat, Simon Lacoste-Julien, Stefan Bauer, and Yoshua Bengio. Bayesian structure learning with generative flow networks. In AAAI, 2022.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Picrre Vandergheyust. Learning Laplacian matrix smooth graph signal representations. IEEE Trans. Signal Process., (4(23):61606617)) 2016.
Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard. Learning graphs from data: A signal representation perspective. IEEE Signal Process. Mag., 36(3):44 63, 2019.
Canberk Ekmekci and Mujdat Cetin. Uncertainty quantification for deep unrolling based computational imaging. IEEE Trans. Compus. Imaging, 8, 2022.
Ghania Fatima, Aakash Arora, Prabhu Babu, and Petre Stoiea. Learning sparse graphs via majorization- minimization for smooth node signals. IEEE Signal Process. Lett., 29:1022-1088 122022222,,, 2022.
Jonah Gabry, Daniel Simpson, Aki Vehtari, Michael Betancourt, and Andrew Gelman. Visualization in bayesian workflow. arXiv preprint arXiv:1 01499, 2017.
Yarin Gal and Zoubin Ghahramani. Dropout as Bayesian approximation: Representing model uncertainty in deep learning. In ICML, 2016.
Andrew Gelman, John B Carlin, Hal S Stern, and Donald B Rubin. Bayesian Data Analysis. Chapman and Hall/CRC, 3rd edition, 1995.
Andrew Gelman, Daniel Simpson, and Michael Betancourt. The prior can often only be understood in the conlext of the likelihood. Entropy, 2017.
Caitlin Gray, Lewis Mitchell, and Matthew Roughan. Bayesian inference of network structure from information cascades. IEEE Trans. Signal Inf. Process. Netw., 2020.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In JCML, pp. 399-406, 2010.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In ICML, 2017.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligncce and Machine Learning, (4(3):1-159) 2020.
Chenhui Hu, Lin Cheng, Jorge Sepulere, Georges El Fakhri, Yue M Lu, and Quanzheng Li. A graph theoretical regression model for brain connectivity learning of alzheimer's disease. In IEEE 10th Int. Symp. Biomed. Imaging, 2013.
Woiyu Huang, Antonio G Marques, and Alejandro R. Ribeiro. Rating prodiction via graph signal processing. IEEE Trans. Signal Process., 2018.
Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In TCML, 2021.
Xiaoyu Jiang and Eric D. Kolaczyk. A latent cigenprobit model with link uncortainty for prediction of protein protein interactions. Stat. Biosci,, 2011.
V. Jospin, H. Laga, Boussaid, W. Buntine, and M. Bennamoun. Hands-on Bayesian neural networks tutorial for deep learning users. IEEE Comput. Intell. Mag., 17, 2022.
Vassilis Kalofolias. How learn graph from smooth signals. In Int. Conf. Artif. Intell. Stat., 2016.

---

Published in Transactions on Machine Learning Research (09/2024)
Vassilis Kalofolias and Nathanadl Perraudin. Large scale graph learning from smooth signals. In ICLR, 2017.
Eric D. Kolaczyk. Statistical Analysis of Network Data: Methods and Models. Springer, New York, NY, 2009.
Yann LeCun, Léon Boltou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document rocognition. Proc. IEEE, 1998.
Gautier Marti, Frank Nielsen, Mikolaj Binkkwski, and Philippe Donnat. A review of two docades of correlations, hierarchies, networks and clustering in financial markets. Prog. Inf. Geom. Theory Appl., 2021.
Gonzalo Mateos, Santiago Segarra, Antonio G. Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Process. Mag., 36(3):16 43, 2019.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Process. Mag., 38, 2021.
Kevin Murphy. Probabilistic Machine Learning: Advanced Topics. MIT Press, 2023.
Felix Opolka and Pietro Lió. Bayesian link prediction with deep graph convolutional gaussian processes. In PMLR, 2022.
Soumyasundar Pal and Mark Coates. Scalable MCMC in degree corrected stochastic block model. In Proc. Int. Conf. Acoustics, Speech, Signol Process., 2019.
Soumyasundar Pal, Saber Malekmohammadi, Florence Regol, Yingxue Zhang, Yishi Xu, and Mark Coates. Non-parametric graph learning for bayesian graph neural networks. In Proc. Conf. Uncertain, Artif. Intell., PMLR, 2020.
Du Phan, Neeraj Pradhan, and Martin Jankowiak. Composable effects for flexible and accelerated probabilistic programming in numpyro. In NewrIPS Workshop Program Transform. ML, 2019.
Xingyue Pu, Tianyue Cao, Xiaoyun Zhang, Xiaowen Dong, and Siheng Chen. Learning to learn graph topologies. In NewrIPS, 2021.
Seyed Saman Saboksayr and Gonzalo Mateos. Accelerated graph learning from smooth signals. IEEE Signal
Process. Lett., 28, 2021.
Martín Sevilla and Santiago Segarra. Bayesian topology inference partially known networks from input- outpul. pairs. Xiv preprint or Nio:2309.00552 2023.
Shohreh Shaghaghian and Mark Coates. Bayesian inference of diffusion networks with unknown infection limes. In Proc. IEEE Workshop on Statisticul Signal Process., 2016.
Mrinank Sharma, Sebastian Farquhar, Eric Nalisnick, and Tom Rainforth. Do bayesian neural networks need to be fully stochastie? aixio preprind arXiv:2211.0620) 2022.
Harsh Shrivastava, Xinshi Chen, Binghong Chen, Guanghui Lan, Srinivas Aluru, Han Liu, and Le Song. GLAD: Learning sparse graph recovery. In ICLR, 2020.
Xiaolu Wang, Chaorui Yao, Haoyu Lci, and Anthony Man-Cho So. An elficient alternating direction method for graph learning from smooth signals. Proc. Int. Conf. Acoustics, Speech, Signal Process., 2021.
Xiaolu Wang, Chaorui Yao, and Anthony Man-Cho So. linearly convergent optimization framework for learning graphs from smooth signals. IEEE Trans. Signal Inf. Process. Netw., 9, 2023.
Max Wasserman, Saurabh Sihag, Gonzalo Mateos, and Alejandro Ribeiro. Learning graph structure from convolutional mixtures. TMLR, 2023.
Florian Wenzel, Kevin Roth, Bastiaan Veeling, Jakub Swiatkowski, Linh Tran, Stephan Mandt, Jasper Snock, Tim Salimans, Rodolphe Jenatton, and Sebastian Nowozin. How good the Bayes posterior in deep noural networks really? In ICML, 2020.
20

---

Published in Transactions Machine Learning Research (09/2024)
Sincad A. Williamson. Nonparametric network models for link prodiction. JMLRR 2016.
Chen Zhang, Riccardo Barbano, and Bangti Jin. Conditional variational autoencoder for learned image reconstruction. Compulation, 2021.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. In AAAI, 2019.
A Appendix
A.1
Optimization algorithms for model-based GSL methods
A.1.1 Primal-dual splitting (PDS) algorithm
Algorithm was introduced in (Kllofolias 2016) to solve the (a, p..--paaaantttiiationn of (3) and was subsequently unrolled by (Pu al. 2021 on the same objective. Note the increased number operations, intermediate variables, and parameters as compared to Algorithm
2
Algorithm 2 Proximal Dual Splitting (PDS)
Inputs: Fixed parameters o,, 9, y E IR, and data e.
Initialize: dg and vo random. for h: = 1. do
T1, = aş - 77 (2 + 2e + vv)). 22 ts 7yaa.
P1,k = prox.,,, (ri,); where prox,, x) = max r1,).
P2.6 prox,,n, (r where (prox, so (rzx)), = (r2, r3. + 40r)//2
41 Р1. 72.3p1 + 2e + S p2.)).
f = P2.k SSpi,
a ag Fi,k + q1
Ub+1 F2, 42,k
end for Return: 0:+1
Parameter tuning in the convergent setting. The optimization parameters a, 8 and of Algorithm 2 are not interpretable, and so performing parameler tuning incurs a O(K3), where K is the number of discretization values used for each parameter. This is in contrast to Algorithm D which has only two parameters 0 and 8. Since 0 is independently interpretable w.r.t sparsity, we can first tune @ to produce outputs with desired sparsity level, then tune ó appropriate edge weight scale, reducing reducing tuning costs to O(K).
Step size y frustrates Bayesian PDS. Algorithm 2 has nuisance step size parameter which must be properly tuned for convergent and performant iterations; problematically such y values are functions a and B3 values; see [Kalofolias 2016). The step size y introduces several issues for use as a learned parameter in BNN. First, we empirically find that the values which produce convergent iterations of Algorithm 2 (within x 10 iterations) are very close to y values which produce divergent iterations, as shown Figure (left). This presents the practical problem of producing NaNs during Bayesian inference, the sampler will be drawn toward such unstable values of 7; causing the unrolling to diverge. Second, the values of y which produce divergent unrollings are themselves a function of a, 3, and the unrolling depth, frustrating simple solutions prevent divergence, e.g,, setting p()) to be some fixed closed interval. Third, the products 7/3 and na ensure the Unrolled PDS is not a neural network; this causes problems in practice as products of parameters each of which can vary over many orders of magnitude can cause problematic gradients. These obscrvations help explain why we could not find any prior configuration over the three parameters (a, } in PDS which produced convergent postcrior sampling over multiple depths. Fixing y to a scalar value ameliorates tes these three issues, indeed this the only configuration which produced performant
21

---

Published in Transactions Machine Learning Research (09/2024)
10a
[ojon (r) -abia
10a
626 8
10a
304
10
10
10
10 10
7 10
10
PDS
DPG
Figure 8: Left: PDS Step Size y. Rumning both DPG and PDS iterations with a = B = and 0= 1/ 1, 8 va/3=11 for 5 10 iterations, we plot the mean and standard deviation of the normalized l distance between the output of PDS vs DPG. The value of y resulting in the most faithful PDS solution close to va values which yield divergent. iterations, problematic for its use as our NN function. Right: PDS vs DPG inference time using D 200 T 50 RG graphs running NUTS with chains (in parallel), each taking M = 1500 samples.
PDS model. We found y 0.1 worked best. Even so, care has to be taken in setting the priors for and 3: log a and log 3 ~ U [0066 108] produced all divergent paths recall this naive setting for log in DPG worked with no issue in the Ablation Studies of Section 6.3 A successful avenue we followed to produce performant PDS model was to use 3 ~ LogNormal 10) and b ~ (10, 10*).
Comparing Bayesian inference time of PDS vs DPG. Above we show that finding range of reasonable values of the optimisation parameters can be cubic in PDS while linear in DPG, owing to independent interpretability. Further, PDS takes more than twice as long in performing inference as the DPG (and PDS with stochastic y took an order of magnitude longer). This may be due the increased complexity of PDS iterates and the fact that both and 3 occur inside PDS iterations, compared to only 0 for DPG iterates, increasing the complexity of the computational graph required to compute parameter gradients. See Figure g (right) showing the difference in inference runtime for PDS and DPG, both having depth D 200 using T = 50 RGy graphs.
A.2 Experimental Details
A.2.1 Scoring rules and evaluation metrics
Fitting the model to training data T produces samples (m(m)) from the posterior p(O) (T). Given test sample {ē, à) we can ovaluate the quality of fit using proper scoring rules, e.g., Log Predictive Density and Brier Score, and discrete metrics, e.g., the Error.

---

Published in Transactions Machine Learning Research (09/2024)
Log predictive density, i.c., Log Likelihood. The Log Likelihood measures the quality of the probabilistic predictions of the model. It is defined as the predicted probability of the true outcome under the model.
log p(ā T. log f pla è, p)p() T)de
M
log
p(a (()
M
m=1
log
Σ n==1
p é, (m))
log S
exp log p(a (.. log p(ā é, e(dn) log
(9)
The NLL is simply -1- p(ā T). A lower NLL indicates better predictive performance, as it suggests that the model assigns higher probabilitics the observed outcomes.
Brier Score. The Brier Score is used to assess the accuracy of probabilistic predictions. It measures the mean squared difference between the predicted probability and the actual outcome. A lower Brier Score indicates better calibration and accuracy of the probabilistic predictions. Recall the edge-wist wise probabilities output by the model for parameters e (mm) are denoted plmm) = ((8(m) G:m (e) ((m)). Then the Brier Score is
/ 11 P
BS(@ e,
181
M
a
(10)
E
Complementary metrics. The NLL particularly useful for evaluating the overall fit of probabilistic model, emphasizing the accuracy of the assigned probabilities, especially for less likely events. In contrast, the Brier Score provides a more intuilive measure of predictive accuracy and calibration, making it easier to interpret the model's s probabilistic predictions in practical scenarios.
Numerical Concerns. Evaluating log p(ale, (m)) computing log a(m) or log (1 - (!)).. for some edges. This becomes an issue in the covariate shift experiments Section [ where the data becomes very noisy and the model can confidently predict the wrong label. When this underflow occurs, the log evaluates -00. To solve this we use the softplus parametrization of the log likelihood: -softplus(-j) (86m)) gim) (e) - (f,)))), where ý 2y 1, see Equation (10.13) in (Murphy 2023
cause numerical issucs which stem from underflow in
Error. We take the error to be the percentage of incorrectly predicted edges bet our thresholded pred. mean [a à é, T] > 0.5 and the true label à.
Calibration for GSL. We follow the calibration procedure laid out in Guo al. 2017). To fit into this framework, we take our prediction to be the pred. mean thresholded at 0.5, i.c., EejT ā ē, TT > 0.5. Thus the confidence, ie., the prohabilities associated with the predicted label, will thus always be E [0.5, 1]. We A1 m (I....,M] M). an edge confidence in Im, we assign it to bin Bm. We then evaluate the accuracy (oc(Bm)) = [B... [ Σie 1(ā; oz) and average
will thus construct M uniform bins In = (.5 + (5(mm-1) (ix-1),,. .5.+ .5am]
M
confidence conf Bm) = [o... EisBn à; for each bin. The Expected Calibration Error (ECB) is defined as the weighted average the bins" accuracy accuracy/confdeem /confidence differonce:
M
Bml
ECE
Σ
|acc(Bm) conf(B..))
B
where B : MM [Bml are the total number of edges predicted. Thus the ECE provides a measure of calibration over all edges in the evaluation set.
A.2.2 Inference Details
Details HMC. To ensure convergence has been achieved in our posterior sampling simulate multiple
23

---

Published in Transactions Machine Learning Research (09/2024)
166
.15
50
6
5-
.15
.16
50
Iteration
Figure 9: Trace plots and bivariate kernel density estimates of DPGs parameters on RGy graphs.
chains with different starting points in the parameter space, discard the first 500 iterations of each simulation, and monitor relevant diagnostic criteria- namely the Potential Scale Reduction Factor (PSRF) i and Effective Sample Size (ESS). We do not perform thinning on the resulting samples. Unless otherwise stated all inference was achieved without issue, namely with that f = 1 and fesss 2 1000 for each parameter. For visualization of successful HMC inference with DPG, see Figure g which displays the trace plots and bivariate kernel density estimates of DPG with 1) = 30 RG2 graphs using analytic distance matrices.
MAP vs MLE. Due to nonconvexity in the loss, initialization is important in finding MAP and MLE of parameters. We did not alter the default initialization provided in NumPyro with MAP, as it worked without issuc. We found MLE to be more dependant on initialization; we initialized the parameters of MLE models i.e. 0, 6, Rs 0.32, 100,
to the median value of the priors set in Section
Log-normal parameterization. Let % be standard normal variable and let l and > 0 be two real numbers, then the distribution of the random variable x= e"* is called a log-normal distribution with parameters je and σ, i.e. X Lognormal(H,, Parameters j and represent the mean and standard deviation of log X, not X itself. While the normality of log X is true regardless of basc, we will be performing modeling using powers of 10. Thus in the main body when we specify a distribution Lognormal(4. o²), it implics the location paramcter used is In 10", while the scale parameter is unchanged. For cxample, (2g 4) would imply location = In 102 and scale a = 2, and thus would be invoked as call to the probabilistic programming language distribution, here NumPyro, as numpyro. numpyro.distribur distributions. Log.oooallooo In 10², scale = 2).
A.3 Scaling to Large Graphs
Scaling via transfer learning in the convergent setting. In (3 terms 2aTe. Te, || have N(N 1)/2 components while term -al log(Sa) has N components, thus the former terms will tend to dominate the latter as N grows (using fixed o, 3). We thus create new problem where each term normalized by it's number of components; use the notation ā, 3 to indicate the scale invariant parameter values
|Ex1- -N--a1 aoggaa (og)SS) + [Ex1 1a1 +If +I{a 20}
arg min
(11)
='NN -,,N (xx 1-1 correspondence between objective terms and params/inputs argmin invariant to positive scaling, multiply by |Ex|
a' a' N N
(e, 3).
(12)
Intuitively, 12 tells us scale by O(N). This makes sense, as a itself scales the objective term which grows at a factor of (N) slower than the other (finite) terms. This should help correct the differing component sizes as the problem dimension N grows. Eq. (12 formulates the solution to the size normalized problem with
respect to the solutions of original problem This shows that use the original solution procedures,
24

---

Published in Transactions Machine Learning Research (09/2024)
F1 vs 1 for Each Graph Size
Anaietical 8120
Graph Size (N)
Figure 10: Transferring to Larger Graphs. Using T 20 ER graphs of varying sizes, grid search find optimal / for the structure recovery lask using Alg Algorithm [ for each graph size, and show the FPl score for each 0. We also plot the line corresponding to Equation 13 which extrapolates performant values from the N₁ 20 setting. This line coincides with empirically observed highly performant 0 values in problem setting for both smaller and significantly larger graphs.
with scaled a, to produce solutions. To do so, suppose lind optimal parameter values dy 8r to the original problem ( with problem size N,. To find the proper parameter values for different problem size N, we can solve for the scale invariant parameter values, then re-scale to the appropriate size as
a(N) (, 1)) 1)) 5(N 1)
B(N) B.
Note as a sanity check, when N; we have (NN) = a and B(N) = 33, trivial recover similar functions for ((N) and 6(N) by substituting into the definitions of 0 and 8 =
VaB
((N) Va(N)B(N) -5( - 1)) (.5NN 1)) 1)) =biV N
N
(13)
8(N) = (((N) 1)) (5(N 1)) = =b. N
N
(14)
See Figure 10 which empirically validates this derivation on ER; graphs across an order of magnitude difference in problem size N.
Scaling in the unrolled setting. See Figure 12 (left) for the empirical growth trends of MAP estimates of the Unrolled DPG model (D 200) parameters ER; graphs. Parameter 0 scems to follow the trend predicted by our analysis, but 5 does not. Indoed it seems to follow strongly lincar trend, and b scoms to follow a power law. We can extrapolate from these trends to parameterize Unrolled DPG networks on significantly larger graphs with excellent performance; see Figure 12 (left).
Larger ER graphs are smoother. We also notice an interesting trend when constructing smooth graph in Section 3 We find that the analytical distance matrices produced by ERy graphs get smoother their size increases. For instance, Figure 12 (right) where the mean and maximum entries of the analytic

---

Published in Transactions Machine Learning Research (09/2024)
1600
1400
22
1200
1000
6
800
10
0.20
400
0.15
10
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
25
50
75
100
125
150
175
200
N
Figure 11: Learning MAP estimates ② of the DPG parameters on ERg graphs of increasing size shows
that ((N) resemble logarithmic growth, 8(N) linear, while b(N) show sort of power law decay.
Analytic E Entry Characteristics
NLL
0.010
max
0CE
35-
mean NLL
0.006
20
0.004
10
5-
0.000
N
N
Figure 12: Left: Computing MAP estimates of DPG at increasing graph sizes shows improving recovery performance (solid lines). Extrapolating from the trends using the approach outlined Appendix A.3 we perform transfer learning larger graph sizes (dotted lines) with gradual decay in performance. Right: The analytic distance matrix E get smoother for increasingly sized ER graphs, providing an explanation for why graph recovery improves with larger graph sizes.
distance matrix get smaller as N grows larger. This explains why the graph recovery problem gets easier and thus our performance gets better, as shown in Figure 12 (left).
A.4 Further Experiments
Prior modeling. The prior modeling techniques introduced in Section 5 work across multiple random graph ensembles. Here, we replicate the prior modeling experiments done on RG Scction for ERg, and BA
See Figure 13 and Figure 14 and compare to Figure 3 (left).
Li.d. generalization across multiple random graph distributions. Our method is performant across the random graph distributions we've tested. To supplement the results shown in Section we show i.i.d. generalization results across random graph distributions, shown in Table
Data efficiency. To further investigate how robust DPG is to sparse data scttings, in Figure 15 we display i.dd. generalization performance function of training set size T RG2 graphs and their corresponding
26

---

Published in Transactions Machine Learning Research (09/2024)
1.4
1.0
1.0
density
componenes
componentt
compinentts
0.4
03
02
02
10"2
10m1
1003
107
131
10"2
10-1
1001
107
101
13
10" 10-1
10"
107
100
Figure 13: Prior modeling of 0 for synthetic ensembles RGy, ER2, and BA1 from left to right. The edge density and number of connected components do not require the presence of labels, while the error does. A threshold of 10-5 5 is used to decide the existence of an edge in order to remove the influence of small numerical effects.
Edy
Edy:
30
10
101
10-1
12
10
10-1
10"
Figure 14: Prior modeling of b and for syuthetic ensembles RG ER,, and BA, from left to right. We inspect the edge weight distributions recovered rumning the held out data through Algorithm for discretized values of 0. The recovered edge weights are non-negative, and so the relevant scaling of and b is function of the median and maximum values.
analytic distance matrices. We additionally visualize the parameter posterior marginals. We find that past T' as 50, i.d.d generalization did not. significantly improve, while past. T' 102, the parameter posterior marginals converge.
Prior ablation study. In sparse data regimes DPG is more performant and has more efficient inference than DPG with un-informative priors (DPG-U). Indeed when the lack of data weakens the likelihood relative to the prior, a useful prior should maintain efficient Bayesian inference (Gelman et al.) 2017). Table 3 illustrates this using RG graphs and their corresponding analytic distance matrices data sets of varying sizes T; Section 3 for further discussion.

---

Published in Transactions Machine Learning Research (09/2024)
Table LLD.D. Generalization DPG across Random Graph Distributions
Graph Distribation
NLL
BS (x10-3)
Error (%)
ECE (x10
RG
8.993 = 9.516
0.988 = 0.945
1.111 # 1.267
4.37
BA1
14.724 3.704
2.614 + 0.751
2.916 + 1.003
30.63
1R
7.677 + 5.021
0.997 + 0.569
1.237 + 0.879
3.04
ERg
0.962 3.029
0.090 = 0.236
0.084 + 0.265
0.94
Train Size
Brier Score
10
12
20
50
Brier Brier Score
100
NLL
500
11
014
10 10 102
0.2 (b) e
0.4
50
60
70
5 (d) b
10
(a) Training Samples
(c)
Figure 15: Impact of training set size i.i.d. generalization performance. We use DPG with /) 200 on RG graphs with analytic distance matrices to estimate generalization. The leftmost plot shows the generalization performance converge after = 50 samples on these same test graphs (error bars indicate 005sstv for compact visualization). The rightmost. plots depict posterior marginals for the parameters 8, 6, and b for increasing sizes of training data. The observed reduction in variance of the posterior is a reflection of lower epistemic uncertainty. The posterior shows little change after 102 samples.
Table 3: Ablation Study: Removing Informative Priors with Limited Training Data.
Model
Time (s)
NLL
BS (x10-2)
Error (%)
ECE (x10-3)
ESSp
DPG-U
343.97
11.185
1.394
1.721
3.41
3.9
T 50
DPG
44.15
11.183
1.392
1.721
3.32
19.7
DPG-U
15.15
11.476
1.508
1.847
5.62
15.5
T 5
DPG
10.63
11.398
1.506
1.842
4.87
15.7
DPG-U
17.06
12.125
1.540
1.821
8.75
10.5
T
DPG
10.66
11.661
1.522
1.832
7.55
11.3
DPG-U
11.11
11.942
1.673
1.789
7.98
7.1
T=1
DPG
6.59
10.976
1.498
1.642
4.23
7.8
28


Reviews:
[{"review_id": "UzBJotBjbu", "reviewer": "Reviewer_rerB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This is the first work using a BNN for graph structure learning with uncertainty quantification. The BNN is a true BNN, and contains only few interpretable parameters, which makes it possible to apply MCMC methods. It is also positive that the proposed method gets rid of the step-size parameter.\n- The Bayesian treatment goes quite deep, and even includes aspects of prior modeling and (prior and posterior) predictive checking. This is very important in the context of uncertainty quantification.\n- Using the iterative optimization as a neural network blueprint is a clever idea, especially in conjunction with the stochastic model.\n- The experimental evaluation is quite extensive and contains both synthetic and real datasets. Furthermore, the authors provide various examples (backed with experimental evidence) in order to shed light on various theory aspects.\n\nWeaknesses\n- In the equivalent parameterization, $\\theta$ is independently interpretable w.r.t. sparsity, but this is not the case for $\\delta$. So, even though it is true that the equivalent parameterization is more interpretable than the original one, the two parameters are still intertwined.\n- In (1), I think the authors are technically wrong to claim that the norm is the $l_1$-norm of matrix $\\mathbf{Z}$. Indeed, the $l_1$-norm of a matrix is the maximum of the absolute column sums. What the authors instead mean is that $||\\cdot||_{1,1}$ is the elementwise norm-1 of $\\mathbf{Z}$, that is, the norm-1 of the vectorized form of $\\mathbf{Z}$. Notice that (Kalofolias, 2016) explicitly mentions the elementwise character of that norm. This is not a serious error, but it is still good to be accurate and rigorous, in order to distinguish between vector norm and matrix norm.\n- I think the authors introduced the symbol $L^\\dagger$ without explaining what it means. They probably mean the Moore-Penrose pseudoinverse, but this should be stated clearly in the text. Furthermore, it was not clear what $\\lambda^\\dagger_i$ represents.\n- In the empirical evaluation, the main competitor that the authors use is Unrolled PDS. It would be interesting to include more competitors . e.g., the algorithm in (Wang et al., 2023).\n- Overall, in the experimental study the authors do not compare against other Bayesian methods for graph structure learning. Instead, they focus on the GSL literature from smooth signals. However, the topic of GSL with uncertainty quantification is quite big and more general, e.g., (Bayesian Structure Learning with Generative Flow Networks, Deleu et al., UAI 2022). To me, this work would have been much more convincing if the authors also compared the results that they get to the results of other Bayesian GSL frameworks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work considers the problem of learning the structure of a graph from nodal observations alone in a supervised manner, i.e., when nodal observations come with corresponding graph labels. The prior literature has already formulated this problem as a convex optimization problem with a unique optimal solution. The challenge with the standard formulation though is that it depends on intertwined and non-interpretable parameters with respect to relevant graph characteristics, such as sparsity or edge weight magnitude. To deal with this, some prior work has introduced an alternative equivalent parameterization, which partially decouples the parameters. A critical insight of this work is that optimization can be performed on this alternative parameterization in an unrolled manner. In particular, the authors adapt the dual proximal gradient method (DPG) from prior works to the equivalent parameterization. However, the proposed DPG algorithm discards some uninterpretable parameters such as the step size, and requires fewer but interpretable parameters. By unrolling the DPG iterations, the authors argue that they obtain a true neural network (NN), which inherits a minimal number of interpretable parameters, while layers in unrolled DPG are simpler. By imposing prior distributions over the various parameters, we end up with a Bayesian NN (BNN) that additionally quantifies uncertainty. Because of the simpler unrolled network, it is possible to get a good posterior approximation via MCMC with uncertainty quantification. Furthermore, the Bayesian nature enables various tools, such as prior or posterior predictive checks. The authors conduct an extensive experimental study using both real and synthetic data, and show that DPG can produce good uncertainty estimates while outperforming other competitors.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would be eager to raise my score since there are many positive things about this work, but I first need to clarify the scope with the authors. \n- The authors should explain any symbols they have not introduced, such as $L^\\dagger$ or $\\lambda^\\dagger_i$. \n- It would help to clarify that the norm $||\\cdot||_{1,1}$ is essentially a vector norm (or elementwise matrix norm) but not the $l_1$ matrix norm.\n- Why do the authors not compare the proposed method to other methods from the GSL literature on smooth signals? I was thinking in particular about (Wang et al., 2023), which, according to its authors, significantly outperforms both Primal-Dual (Kalofolias, 2016) as well as FDPG (Saboksayr & Mateos, 2021). Wouldn't it make sense to compare the new method to the state-of-the-art algorithms in the GSL literature from smooth signals, i.e., to (Wang et al., 2023)?\n- It indeed seems that this is the first work that uses a Bayesian neural network. But it certainly is not the first work using Bayesian methods for the purpose of graph structure learning. I would have expected to see either some detailed discussion or even experiments detailing how the proposed method does compared to other Bayesian methods on GSL. I believe this is quite important, otherwise the scope of the work is significantly reduced, and this work is only about the GSL literature from smooth signals (where, incidentally, the authors do not even compare to FDPG). I believe it is important for the authors to clearly define the scope of this work, and at least provide some discussion (if not experiments) on how their framework is related to other Bayesian methods for GSL. This will further strengthen the claims made by the authors, as everything will be seen under the right scope.\nAt the end of the day, the question is whether this work should be only seen as a Bayesian adaptation of FDPG, or as a viable framework for Bayesian GSL with the potential to outperform other Bayesian GSL methods.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "T2skXRTb46", "reviewer": "Reviewer_yaD2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths \n \n1. Uncertainty estimate is indeed important for many domains. This paper proposes the first BNN for supervised GSL that could naturally estimate uncertainty over edge predictions.  \n2. The proposed method is novel with sound, theoretical insights.   \n3. Good empirical results are reported on both synthetic and real data. \n\n### Weaknesses\n\nThis paper is generally hard for me to follow, possibly because I am not very familiar with this direction and related works. That being said, I am not confident on my judgement of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a method for graph structure learning (GSL) using Bayesian Neural Networks (BNNs), motivated by the importance of uncertainty estimates in many applications. The introduced method utilizes independently interpretable parameters in a novel iteration process, allowing for Bayesian modeling. Through using BNNs, the proposed approach is able to provide well-calibrated estimates of uncertainty on several benchmarks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "NA", "broader_impact_concerns": "No I don't have concerns on the ethical implications of the work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XgdNTPoE5f", "reviewer": "Reviewer_n2MU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper combines Bayesian principles with neural network architectures to address the GSL problem, offering a new paradigm for uncertainty-aware graph structure inference.\n* Unlike traditional methods that require extensive tuning and lack interpretability in parameter settings, the introduced approach utilizes Bayesian learning to incorporate prior knowledge into the model's parameters, enhancing its applicability in domains where understanding the influence of specific parameters is crucial.\n* The approach relies on standard regularizations on the graph loss and structure, facilitating the use of fast optimization algorithms. This ease of implementation makes the method accessible for large-scale problems.\n\nWeakness:\n* The technical contribution seems to be incremental. The main method is an adaption of (weighted) L1 regularization on the loss as well as the structure, i.e., eq (1) to (4). The dual proximal gradient descent solution algorithm is also pretty standard.\n* A main contribution is the so-called independently interpretable parameters. However, the term \"independence\" does not strictly imply statistical independence as defined in probability theory. Instead, it refers to the interpretability of individual parameters in influencing specific characteristics of the inferred graph structure. In particular, the authors design the parameters to control certain graph properties, such as edge sparsity or connectivity patterns.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces an approach to Graph Structure Learning (GSL) using Bayesian Neural Networks (BNNs) trained on smooth signal observations. Traditionally, GSL infers graph structures from nodal data via convex inverse problems or supervised deep networks. However, these methods often lack robust uncertainty quantification. The proposed method leverages independently interpretable parameters and Bayesian priors to enhance GSL's accuracy and reliability in uncertain data settings, such as medicine and finance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Highlight the technical contribution in the context of related work.\n* Introduce rigorous mathematical definitions of independently interpretable parameters.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The concerns raised by the reviewers were all addressed in a satisfactory manner as also agreed upon by the reviewers raising the issues (rerB).
Decision: Accept (poster)