Learning Latent Graph Structures and their Uncertainty
Authors: Alessandro Manenti
Daniele Zambon
Cesare Alippi
Venue: ICML 2025 poster (2025)
Keywords: Graph Structure Learning
Graph Neural Networks
Primary area: deep_learning->graph_neural_networks
TL;DR: Accurate probabilistic graph structure learning requires specific loss functions. We identify a broad class supported by learning guarantees.

Abstract: Graph neural networks use relational information as an inductive bias to enhance prediction performance. Not rarely, task-relevant relations are unknown and graph structure learning approaches have been proposed to learn them from data. Given their latent nature, no graph observations are available to provide a direct training signal to the learnable relations. Therefore, graph topologies are typically learned on the prediction task alongside the other graph neural network parameters.
In this paper, we demonstrate that minimizing point-prediction losses does not guarantee proper learning of the latent relational information and its associated uncertainty. Conversely, we prove that suitable loss functions on the stochastic model outputs simultaneously grant solving two tasks: (i) learning the unknown distribution of the latent graph and (ii) achieving optimal predictions of the target variable. 
Finally, we propose a sampling-based method that solves this joint learning task. Empirical results validate our theoretical claims and demonstrate the effectiveness of the proposed approach.

Learning Latent Graph Structures and their Uncertainty
Alessandro Manenti Daniele Zambon' Cesare Alippi 12
Abstract
and its parameters in & is conditioned the relational information encoded in variable A. Graph Neural Networks (GNNs) (Scarselli et al., 2008) are one example of models of this kind that rely on graph structure represented as an adjacency matrix A and have been demonstrated successful in a plethora of applications (Fout et al., 2017; Shlomi et al., 2020).
Graph neural networks use relational informa- tion as an inductive bias to enhance prediction performance. Not rarely, task-relevant relations are unknown and graph structure learning ap- proaches have been proposed to learn them from data. Given their latent nature, no graph obser- vations are available to provide direct training signal the learnable relations. Therefore, graph topologies are typically learned on the prediction task alongside the other graph neural network pa- rameters. In this paper, we demonstrate that mini- mizing point-por cont-prediction losses does not guarantee proper learning of the latent relational informa- tion and its associated uncertainty. Conversely, we prove that suitable loss functions on the stochastic model outputs simultaneously grant solving two tasks: (i) learning the unknown distribution of the latent graph and (ii) achieving optimal predic- tions of the target variable. Finally, propose sampling based method that solves this joint learning task !. Empirical results validate our the- oretical claims and demonstrate the effectiveness of the proposed approach.
Indeed, relational information is needed to implement such relational inductive bias and, in some cases, it is provided at the application design phase. However, more frequently, such topological information is not rich enough to address the problem at hand, and - not seldom - it is completely unavailable. Therefore, Graph Structure Learning (GSL) emerges as an approach to learn the graph topology (Kipf et al., 2018; Franceschi al., 2019; Yu et al., 2021; Fatemi et al., 2021; ;; Zhu et al., 2021; Cini et al., 2023) alongside the predictive model fg. This entails formulating joint learning process that learns the adjacency matrix A - or pa- rameterization of it - along with the predictor's 's parameters tb. This is usually achieved by optimizing a loss function on the model output y, e-g., a point prediction measure based on the square or the absolute prediction error.
Different sources of uncertainty affect the graph structure learning process, including epistemic uncertainty in the data and variability inherent in the data-generating process. Learning appropriate models of the data- gettratenerainngggg process can provide valuable insights into the modeled environment with uncertainty quantification enhancing explainability and interpretability, ultimately enabling more informed decision- making. Examples of applications found in the study of infection and information spreading. well biologi- cal systems (Gomez Rodriguez et al., 2013; Lokhov, 2016; Deleu et al., 2022). It follows that a probabilistic framework is appropriate to accurately capture the uncertainty in the learned relations whenever randomness affects the graph topology. Probabilistic approaches have been devised in re- cent years. For instance, research carried out by Franceschi et al. (2019); Zhang al. (2019); Elinas et al. (2020); Cini et al. (2023) propose methods that learn parametric dis- tribution Pd over the latent graph structure A. However, none of them have studied whether these approaches were able to learn a calibrated latent distribution Pd for A, prop- erly reflecting the uncertainty associated with the learned topology.
1. Introduction
Relational information processing has provided break- throughs in the analysis of rich and complex data coming from, e.g., social networks, natural language, and biology. This side information takes various forms, from structuring the data into clusters to defining causal relations and hier- archies, and enables machine learning models to condition their predictions on dependency-related observations. In this context, predictive models take the form y = (ar A), where the input-output relation
modeled by J
'Università della Svizzera italiana, IDSIA, Lugano, Switzer- land "Politecnico di Milano, Milan, Italy. Correspondence to: Alessandro Manenti <alessandro..o manenti @usi.ch>>.
Proceedings of the 4rnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 hy the author(s).
Cooee available https//ggthhu..commallemaanni/i Calibrated-Se StruutuueSStucuresss

---

Learning Latent Graph Structures and their Uncertainty
In this paper, we fill this gap by addressing the joint prob- lem of learning a predictive model yielding optimal point- prediction performance of the output and, contextually, calibrated distribution for the latent adjacency matrix A. In particular, the novel contributions can be summarized as:
(2019) utilize straight-through gradient estimations, Cini et al. (2023) rely on score-based based gradient estimators, while Niepert et al. (2021) design implicit maximum likelihood estimation strategy. A different line of research is rooted in graph signal processing, where the graph is estimated from a constrained optimization problem and the smoothness as- sumption of the signals (Kalofolias, 2016; Dong et al., 2016; Mateos et al., 2019; Coutino et al., 2020; Pu al., 2021). A few works from the Bayesian literature have tackled the task of estimating uncertainties associated with graph edges. The model-based approaches by Lokhov (2016) and Gray et al. (2020) are two examples tackling relevant applications benefiting from uncertainty quantification. Within the deep learning literature, Zhang et al. (2019) propose a Bayesian Neural Network (BNN) modeling the random graph realiza- tions. Differently, Wasserman & Mateos (2024) develop an interpretable BNN designed over graph signal processing principles using unrolled dual proximal gradient iterations. While some results on the output calibration are exhibited, to the best of our knowledge, no guarantee or evidence of calibration of the latent variable is provided, which we study in this paper instead.
1. We demonstrate that models trained to achieve optimal point predictions do not guarantee calibration of the adjacency matrix distribution [Section 4].
2. We provide theoretical conditions on the predictive model and loss function that guarantee simultaneous calibration of the latent variable and optimal point pre- dictions [Section 5].
3. We propose a theoretically grounded sampling- baaeed learning method to address the joint learning problem [Section 5].
4. We empirically validate the theoretical developments and claims presented in this paper and show that the proposed approach outperforms existing methods in solving the joint learning task [Section 6].
Finally, we emphasize the significance of our contribution. The inherent latent nature of A presents substantial learning challenges. Real-world applications rarely provide direct observations of the (latent) graph structure, making it im- possible to use such data as learning signals for training the graph distribution Po. This lack of real-world observa- tions not only hampers model training but also complicates empirical evaluation of the learned latent distribution. Con- sequently, flawed decisions may be derived from learned models. This work addresses these limitations by (i) estab- lishing theoretical guarantees for more robust learning of the latent variable to mitigate the need for evaluation on real data, and (ii) conducting rigorous empirical analysis on synthetic datasets that provide the otherwise missing ground-truth knowledge required for an accurate validation of our claims.
Calibration of the model's output Research on model calibration has primarily focused on obtaining accurate and consistent predictions of the statistical properties of the tar- get (random) variables y. from which uncertainty estimates on the model's predictions are derived. For discrete outputs, such as in classification tasks, Guo et al. (2017) investigated the calibration of modern deep learning models and pro- posed temperature scaling as a solution. Other techniques in the same context include Histogram Binning (Zadrozny & Elkan, 2001), Cross Entropy loss with label smoothing (Müller et al., 2019), and Focal Loss (Mukhoti et al., 2020). For continuous output distributions, Laves et al. (2020) pro- posed scaling, while Kuleshov et al. (2018) developed technique inspired by Platt scaling. More recently, con- formal prediction techniques (Shafer & Vovk, 2008) have gained popularity for providing confidence intervals in pre- dictions. We stress that within this paper, we are mainly concerned with latent variable calibration, rather than output calibration, although the two are related to each other.
2. Related Work
Graph Structure Learning GSL is often employed end- to-end with predictive model to better solve a downstream task. Examples include applications within graph deep learn- ing methods for static (Jiang et al., 2019; Yu et al., 2021; Kazi al., 2022) and temporal data (Wu al., 2019: 2020: Cini et al., 2023; De Felice et al., 2024); a recent review is provided by Zhu et al. (2021). Some approaches from the literature model the latent graph structure as stochas- tic (Kipf et al., 2018; Franceschi et al., 2019; Elinas et al., 2020; Shang et al., 2021; Cini et al., 2023), mainly as a way to enforce sparsity of the adjacency matrix. To oper- ate on discrete latent random variables, Franceschi et al.
Deep latent variable models Latent variables are exten- sively used in deep generative modeling (Kingma & Welling, 2013; Rezende et al., 2), both with continuous and dis- crete latent variables (Van Den Oord et al., 2017: Bartler et al., 2019). In deep models, latent random variables often lack direct physical meaning, with only the outputs being collected for training. Therefore, studies mainly focused on maximizing the likelihood of the observed outputs in the training set, rather than calibrating the latent distribution. A few works proposed regularization of the latent space to im- prove stability and accuracy (Xu & Durrett, 2018; Joo et al.,
2

---

when A and are inde- Learning Latent Graph Structures and their Uncertainty
2020), facilitate smoother transitions in the output when the latent variable is slightly modified (Hadjeres et al., 2017), and apply other techniques aimed at enhancing data gener- ation or improving model performance in general (Connor et al., 2021).
Optimal point predictions Outputs y and of proba- bilistic model (1) and (2) are random variables following push-forward distributions 2 P file and p respectively. A single point prediction ypP E 3 can be obtained through
an appropriate functional 7[-] as
To the best of our knowledge, no prior work has studied the joint learning problem of calibrating the latent graph distribution while achieving optimal point predictions.
UPP = UPP( 8, () =
pM g/
For example, T can be the expected value or the value at specific quantile. We then define an optimal predictor as one whose parameters 0 and da minimize the expected point-prediction loss
3. Problem Formulation
Consider a set of N interacting entities and the data- generating process
Croint .) = Eg By-r; ((V.vrr(z, 8, 0.4)]]
(4)
Px PA y = A2)
A~~
between the system output y and the point-prediction ypr. as measured by of loss function y x y R...
Statistical functional T is coupled with the loss & as the optimal functional T to employ given a specific loss f is often known (Berger, 1990; Gneiting, 2011), when gir approximates well pale. For instance, if E is the Mean Absolute Error (MAÉ) the associated functional T is the median, if f is the Mean Squared Error (MSH) the associated functional is the expected value.
where y E y' is the system output obtained from input x E X' through function f* and conditioned on a realiza- tion of the latent adjacency matrix A E A C {0, 1)NNN drawn from distribution PA: input x is assumed to be drawn from any distribution Pe and superscript * refers to un- known entities. Each entry of the adjacency matrix A is binary value encoding the existence of pairwise relation between two nodes. In the sequel, y E y C I Xdouut are stacks of N node-level feature vec- tors of dimension din and dout, respectively, representing continuous inputs and outputs.
X C R.Nxd. and
Latent distribution calibration Calibration of a parametrized distribution PA requires learning parameters 6, so that Pa aligns with true distribution Pã- Quantita- tively, a dissimilarity measure A Pa x PA + R,, defined over a set PA of distributions on A, assesses how close two distributions are. The family of f-divergences (Rényi, 1961), such as the Kullback-Leible divergence, and the integral probability metries (Müller, 1997), such as the maximum mean discrepancy (Gretton et al., 2012) are examples of such dissimilarity measures. In this paper, we are interested in those discrepancies for which A A (Pi, Pa) =0 < Pi = P3 holds. It follows that the latent distribution Pa is calibrated on PA if it minimizes the latent distribution loss
Given a training dataset D = {(x) w)))²= of n input- output observations from (I), we aim at learning a prob- abilistic predictive model
A ~ Pa 0 = (1, A)
from D, while learning at the same time distribution Pa approximating P7. The two parameter vectors 9 and s are trained to approximate distinct entities in (1), namely the distribution PA and function f", respectively. We assume Assumption 3.1. The family {P&) of probability distribu- tions 1% parametrized by 0 and the family of predictive functions } are expressive enough to contain the true latent distribution PA and function f", respectively.
Lool = ExNPE cal (P%, Pi)]
(5)
or simply Loal_ Acal pendent.
The problem of designing a predictive model (2) that both yields optimal point predictions (i.e., minimizes poinnt in (4)) and calibrates the latent distribution (i.e., minimizes Loal in (5)) is non-trivial for two main reasons. At first, as the latent distribution Pa is unknown (and no samples from it are available), we cannot directly estimate Loa!, Second, as shown in Section 4, multiple sets of e parameters may minimize Eroint without minimizing Loal
Assumption 3.1 implies that f E [fe} and PA E (PA) but does not request uniqueness of the parameters vectors 2 and 0" such that fw- = f and p = -PA- Under such assumption the minimum function approximation error is null and we can focus on the theoretical conditions requested to guarantee successful learning. i.c., achieving both opti- mal point predictions and latent distribution calibration. In Section 6.2, we empirically show that the theoretical results can extend beyond this assumption in practice.
"The distribution of = f" A) originated from PA and of 9 = [o, A) originated from Ph.
3

---

Learning Latent Graph Structures and their Uncertainty
4. Limitations of Point-Prediction Optimization
is injective. Under Assumptions 3.1 and 5.1, ifT xN (1)
O and ap is such that f f", then
In this section, we demonstrate that the optimization of point prediction loss (Equation (4)) does not generally grant calibration of the latent random variable A.
Croint 16*) is minimal
Caist (0, (0)="==-- =0 =
Lool (0) = 0.
Proposition 4.1. Consider Assumption 3.1. Loss func- tion Luoint (0, 1)) in (4) is minimized by all 0 and up s.t.
Theorem 5.2 is proven in Appendix A.3. Under the theo- rem's hypotheses. a predictor that minimizes C is both calibrated on the latent random distribution and provides optimal point predictions. This overcomes limits of Proposi- tion 4.1 where optimization of C (0, x²) does not grant C (0) = 0.
T p0.0 T |1l almost surely on and, in particular,
Eroint (0, v) is minimal
= Pi u/2
The proof of the proposition is given in Appendix A.1; we provide a counterexample for which calibration is not granted even when the processing function fa is equal to f* in Appendix A.2.
The hypotheses under which Theorem 5.2 holds are rather mild. In fact, condition Pz-r: (T) > 0 pertains to the data- generating process and intuitively ensures that, for some z, different latent random variables produce different out- puts. A sufficient condition for PP2-pp (T) > O to hold is the existence of point E in the support of P such that A + [", A) is injective with I continuous w.r.t. I; see Corollary A.1 in Appendix A.3. Although only a single point E is required, having more points that satisfy the con- dition simplifies the training of the parameters. Corollary A.1 holds for arbitrarily complex processing functions f* More specifically, when considering simple GNN layers and discrete latent matrices A, we can prove that the con- dition Pa-P: (7) > O is - except from pathological cases always satisfied (see Proposition A.2 in Appendix A.3). Instead, condition fø = f is set to avoid scenarios of dif- ferent. yet equivalent, representations of the latent distribu- tion. An empirical analysis of the theorem's assumptions is provided in Section 6.2, demonstrating that the theoretical results hold in practice, even when those assumptions do not strictly apply.
The limitation of point- ceitt-preiictio losses is also empirically demonstrated in Section 6.3, Table 2, where it is shown that losses does not grant calibration
optimizing
Given the provided negative result and the impossibility of assessing loss Ceal in (5), in the next section, we propose another optimization objective that, as we will prove, allows us to both calibrate the latent random variable and to have optimal point predictions.
5. Predictive Distribution Optimization: Two Birds with One Stone
In this section, we show that we can achieve an optimal point predictor (2) and a calibrated latent distribution Pd by comparing push-forward distributions 1y and vlz of the outputs y conditioned on input x. In particular, The- orem 5.2 below proves that, under appropriate conditions, minimization of the output distribution loss
Assumptions 3.1 and 5.1 can be met with an appropriate choice of model (2) and measure A; as such they are control- lable by the designer. Assumption 5.1 prevents from obtain- ing mismatched output distributions when (dist( v) 0 and can be easily satisfied. As mentioned above, popular measures, e.g., the Kullback- divergence, meet the theorem's 's assumptions and therefore can be adopted as A. However, as f-divergences rely on the explicit evaluation of the likelihood of y, they are not always practical to compute (Mohamed & Lakshminarayanan, 2016). For this reason, we propose considering the Maximum Mean Discrepancy (MMD) (Gretton et al., 2012) as a versatile alternative that allows Monte Carlo computation without requiring evalua- tions of the likelihood w.r.t. the output distributions y/ and pd. wfa Energy distances (Székely & Rizzo, 2013) provide an alternative feasible choice.
Cdist(O, x/) = Ee-Pe
A(Pr g/a gla :0
(6)
provides calibrated P2. even when PA is not available; A P, x Py + R2 is a dissimilarity measure between distributions over space y. We assume the following on dissimilarity measure A.
Assumption 5.1. A(PI, 2 0 for all distributions P1 and Pg Py and A(Pi, P2) if and only if P1 = Pz.
Several choices of A meet Assumption 5.1, e.g., f- divergences and some integral probability metries (Müller, 1997); the dissimilarity measure A employed in this paper is discussed in Section 5.1.
Theorem 5.2. Let I = {x : A+ (z, A) is injective] C X be the set of points x E X such that map A + (x, A)
FE.g. (A, = f. A,x) and PA encoding the absence of edges instead of their presence as PA-
4

---

Learning Latent Graph Structures and their Uncertainty
5.1. Maximum Mean Diserepancy
(Williams, 1992; Mohamed et al., 2020) which uses the log
derivative trick to rewrite the gradient of an expected loss L as A- [L(A)] -ー~ (L(A) log (A)), with pd (A) denoting the likelihood of A ~ P Applying the
Given two distributions P2 E Pa. the MMD can be defined as
MMD = sup (Ey~r [a(v)] - Eyyrss (o())) gEg
SFE to our problem the gradient w.r.t. 0 reads:
(7) i.e. the supremum, taken over a set G of functions y + R. of the difference between expected values w.r.t. P1 and P2- An equivalent form is derived for generic kernel function
V C
E 2.1""
E 91.
<( Ve log (Ph P vla
y/r (Be))
-((;)) y x y I::
2 moyy" 9) Vo log P (0)
(10)
MMD S..
[P1, Pa]
E M.
[elen vi']
where 01, 12. 9
pl. An apparent setback of SFEs wia
- 2 E (K(g). m P2
+
1c (V 16)1
(8)
is their high variance (Mohamed et al., 2020), which we address in Section 5.3 by deriving a variance-reduction tech- nique based on control variates that requires negligible com- putational overhead.
P3
and it is associated with the unit-ball Gy of functions in the reproducing kernel Hilbert space of k; note that (8) is the square of (7). Moreover, when universal kernels are considered (e.g., the Gaussian one), then (8) fulfills Assumption 5.1 (see Theorem 5 in (Gretton et al., 2012)). Dissimilarity in (8) can be conveniently estimated via Monte Carlo (MC) and employed within deep learning framework. Accordingly, we set A = MMD?, and learn parameter vectors &b and 0 by minimizing Edset(0 (0, v)) via gradient- descent methods.
5.3. Variance-Reduced Loss for SFE
Two natural approaches to reduce the variance of MC esti- mates of (10) involve (i) increasing the number B of training data points in the mini-batch used for each gradient estimate and (ii) increasing the number Nadý of adjacency matrices sampled for each data point in (9). These techniques act on two different sources of noise. Increasing B decreases the variance coming from the data-generating process, whereas increasing Nadj improves the approximation of the predic- tive distribution p&.y. Nonetheless, by fixing B and Nadj- it is possible to further reduce the latter source of variance by employing the control variates method (Mohamed et al., 2020) that, in our case, requires only negligible compu- tational overhead but sensibly improves the training speed (see Section 6).
5.2. Fimite-Sample Computation of the Loss
To compute the gradient of (dist(O, v)) [po.
ylæ"
ExWP: MMDD._
[
y/ar vio w.r.t. parameter vec-
tors v and 0, we rely MC sampling to estimate in (6)
expectations over input ~ Pt, target output y P
and model output i ~ pe.y This amounts to substitute MMD3 with
Consider the expectation EA [(A) log P (A)] of the SFE both terms in (10) can be cast into that form. With the control variates method, function with null ex- pectation is subtracted from L(A) log (A)).
INet m(ji, Uj)
Eimeo nly, 0i) Nadj
MMD 0. (I, v) = 2 Nody (Nudj 1)
2
(9)
= L(A)o (A( s (M(A)) - EAN (AA))
In (9), Nady > 1 is the number of adjacency matrices sam- pled from PAA to obtain output samples ú. ( A+) ~ p
(11)
that leads to a reduced variance in the MC estimator of the gradient while maintaining it unbiased. In this paper, set function ((A)) to Vo log pd (A) and show how to compute opar-oltimal choice for scalar value 3, often called baseline in the literature. As the expected value of Va log pd (A) is zero gradient (10) rewrites as
yla: whereas the pair (r. y) is pair from the training set D. We remark that in (9) the third term of (8) - i.e., the one
associated with the double expectation with respect to p is neglected as it does not depend on &p and 0.
Gradient V Cdist (0, +b) is computed via automatic differen- 2 tiation by averaging V MMD (8, æ)) within mini-batch of observed data pairs (2i, vı) E D. For VoL (0, vb), the same approach is not feasible. This limitation arises because the gradient is computed with respect to the same parameter vector 0 that defines the integrated distribution. Here, we rely on score-function gradient estimator (SFE)
V VoL x.y²
E
2T((n(U ,0) 82) Vo log P4 (A]]
E 11
(M(().02)) Bi) Vo log (P8(A))
(12)
5

---

Learning Latent Graph Structures and their Uncertainty
In Appendix B, we show that in our setup the best values of 31 and f2 are approximated by
we develop, demonstrating appropriate calibration of the la- tent distribution even in scenarios where the assumptions of Theorem 5.2 do not hold. Section 6.3 demonstrates that the proposed approach is more effective than existing methods in solving the joint learning task. As a last experiment, in Appendix C.5 we test our approach and show that sensible graph distributions can be learned in real-world settings.
31 = Ex E AA 12 pa
r: (fv(z, A1), fo (e))]
3. = Eu
EA BA
K6 (y"" So ])
(13)
which can be efficiently computed via MC reusing the kernel values already computed for (12).
Dataset and models Consider silla-ggneratngg process (I) with latent distribution PA = P producing --node adjacency matrices. Random graph A ~ PA is given as a set of independent edges (i, for i = 1.....,, N, each of which is sampled with probability 01.. Function f. fu- is a generic GNN with node-level readout, i... f (:; A) Nxd... - R xdoue_ The components 0 are set to either 0 or 3/4 according to the pattern depicted in Fig- ure 1; additional specifics are detailed in Appendix C. We result in a dataset of 35k input-output pairs (zz y), 80% of which are used as training set, 10% as validation set, and the remaining 10% as test set. As predictive model family (2), we follow the same architecture of f and pd ensuring that during all the experiments Assumption 3.1 is fulfilled; similar models have been used in the literature (Franceschi et al., 2019; Elinas et al., 2020; Kazi et al., 2022; Cini et al., 2023). In Section 6.2 we test the method's 's validity beyond this assumption. The model parameters are trained by opti- mizing the expected squared MMD in (9) with the rational quadratic kernel (Binkkoski et al., 2018).
5.4. Computational Complexity
Focusing on the most significant terms, for every data pair (z. y) in the training set, computing the loss Cdist requires O(N2g)) ady) kernel evaluations <()., U2) in (9), (Naa)) for- ward passes through the GNN DJ = (x, A2) in (9) and (Nad)) likelihood computations (A:) in (12). The computation of baselines 31 and (3 in (13) requires vir- tually no overhead, as commented in previous Section 5.3. Similarly, computing the loss gradients requires ((Naa)) ody) derivatives for what concerns the kernels, ((Nad)) gradi- ents Ved; and Vo log P7 (A)). We empirically observed that for Not 2 16, both the latent distribution loss Coal and the point prediction loss groint of final models are equiva- lent for the considered problem. This suggests that Nadj is not a critical hyperparameter.
Since can employ sparse representations of adjacency matrices, the GNN processing costs scale linearly in the number of nodes N for bounded-degree graphs. From our experience, the GNN processing is the most demanding operation and the cost of quadratic components, such as the parameterization of 0ig. do not pose significant overhead.
6.1. Graph Structure Learning & Optimal Point Predictions
To test our method's ability to both calibrate the latent dis- tribution and make optimal predictions, we train the model minimizing dist described in Section 5.2.
6. Experiments
This section empirically validates the proposed technique and the main claims of the paper. While point predictions can be evaluated on observed input-output pairs (xr, v) pro- vided as a test set, assessing latent-variable calibration per- formance - the discrepancy between PA and the learned PA requires knowledge of the ground-truth latent distribution itself or of observation thereof. Such ground-truth knowl- edge, however, is not available in real-world datasets, as the latent distribution is indeed unknown. Therefore, to validate the theoretical results, we designed a synthetic dataset that allows us to evaluate different performance metrics on both y and A. We remark that the latent distribution is used only to assess performance and does not drive the model training in any way.
Figure 2 reports the validation losses during training: MMD loss Edist as in (6), MAE between the learned parameters and the ground truth #* as L (5), and woint-prediction loss Cooint as in (4) with É being the MSE. The results are averaged over 8 different model initializations and error bars report 1 standard deviations from the mean. Results are reported with and without applying the variance reduction (Section 5.3), by training only parameters 0 while freezing & to vi" (same setting of Theorem 5.2), and by jointly training both v and O.
Solving the joint learning problem Figure 2a shows that the training succeeded and the MMD loss dist converged to its minimum value. 4 Having minimized Ldist from Figure 2b we see that also the calibration of latent distri-
Section 6.1 demonstrates that the proposed approach can successfully solve the joint learning problem across dif- ferent graph sizes and highlights the effectiveness of the proposed variance reduction technique. Section 6.2 empir- ically investigates the generality of the theoretical results
'Numerical estimation shows that the minimum value of e for the given kernel is approximately -0.088; note that although the MMD 2 0, the third term in (8) is dropped from (9).
6

---

Learning Latent Graph Structures and their Uncertainty
Table I. Calibration of P under varying levels of misconfigura- tion for predictive function fg. Results are the mean +: standard deviation assessed over 8 independent runs.
Max pert. V
MAE on 0
Max AE on 0
0
8
5
0
0.009 + 0.001
0.06 + 0.01
0.1
0.010 1 0.001
0.07 = 0.01
True theta parameters
14
0.2
0.012 + 0.004
0.08 + 0,02
0.5 0.028 + 0.011
0.16 - 0.06
0.8
0.047 + 0.009
0.28 = 0.06
0:00 8.00
0.00
0/5
9.5
000 9.0
3.00
0.0 580 0.00
-000
175
0.75
075 0.5
975
0:00 BEL
3.0
D:0
3.0 0.00
66
0:00
8:00000 0.00
0:3
0:13
2:69
300
3.0
0.00
number of free parameters in @ and the size of the training set can become prohibitive. Nonetheless, in Figure 7, we show all ~ 15K parameters of the considered Pa can be effectively learned even for relatively large graphs; the final MAE on parameters is 0.003.
-000
6:0
075 6:75
8:75
0.09
-000 800 0.00 000
8:5
0.75
62
R IAED D:0 0I31 BED CEC DAS DIe
7.7 0.00
44 OCD 842 0.99 000 600 000
000
300
635
375 0.75
11
6.2. Beyond Assumption 3.1
Figure 1. Adjacency matrices sampled from PA = PA" for the experiment of Section are subgraphs of the top graph; in this picture, 3 communities of an arbitrarily large graph are shown. Each edge in orange is independently sampled with probability fg: parameters f defining the edge probabilitics are represented the bottom for a two communities graph.
In this section, we empirically study whether Assumption 3.1 is restrictive in practical applications. Specifically, we consider different degrees of model mismatch between the system model in (1) and the approximating model in (2). Unless otherwise specified, we use the same dataset and ex- perimental setup as described in Appendix C.I. Additional details and results are deferred to Appendix C.3.
bution PA was successful; in particular, the figure shows
Perturbed fe- As a first experiment, we train P while keeping the parameters of the predictive function f& fixed to random perturbation of the data-generating model f far. A perturbed version of f is built by uniformly draw- ing independent perturbation scalar values ó; ~ 2[[ V). one for each parameter eهद of fø-. Then, each parameter of GNN f is given as v/ = (1 5) Table I shows that the learned latent distribution remains reasonably calibrated. Finally, Figures 8-11 show the learned parameter vectors O for randomly extracted runs and highlight that the maximum AE of Table 1 is observed only sporadically.
that the MAE on 0 parameters (N 2 - 0111) approaches zero training proceeds (MAE 0.01). Regarding the point predictions, Figure 2c confirms that groint reached its minimum value; recall that optimal prediction MSE is not 0, as the target variable y is random, and note that a learning rate reduction is applied at epoch number 5. The optimality of the point-prediction is supported also by the performance on separate test data and with respect to the MSE as point-prediction loss f. Moreover, we observe that calibration is achieved regardless of the variance reduction and whether or not parameters 1/2 are trained. Lastly, Figure 5 in Appendix C.2 shows the learned parameters 0 of the la- tent distribution and the corresponding absolute discrepancy resulted from a (randomly chosen) training run.
Generic GNN as fe In this second experiment, we set fe to be generic multilayer GNN which we jointly train with graph distribution pa The model family {fw} employed does not include f", as f uses L-hop adjacency matrices generated from the sampled adjacency matrix A, while fo relies on multiple nonlinear 1-hop layers; additional details are reported in Appendix C.3. Upon convergence, models achieved Croint < 0.19 using the MSE as loss function in (4); The performance is in line with results in Figure 2c. At last, note that as the GNN used adds self- the diag- onal elements of the adjacency matrix are learned as zero resulting in a larger MAE on 0 (see Figure 12). However, this does not impair learning the dia-ooaa 6s, parameters (i.c., for i * j). Notably, in the werst-pe model, these off-diagonal parameters achieve a MAE of less than
Variance reduction effectiveness Figures 2a, 2b and 2c demonstrate that the proposed variance reduction method (Section 5.2) yields notable advantages training speed up (roughly 50% faster). For this reason, the next experiments rely on variance reduction.
Larger graphs The theoretical results developed hold for any number of nodes N. However, the number of possible edges scales quadratically in the number of nodes a po- tential issue inherent to the GSL problem, not our approach. Therefore, for extremely large graphs the ratio between the
7

---

Learning Latent Graph Structures and their Uncertainty
MMD' Loss on Validation
Mean Absolute Error on @ paremeters
Paint Prediction MSE Loss on Validation
-0.02
With varisnre recurtoo
Without veriince reductionn
0.2
Calibration
Callbration Model Leaminn
Numerical opcimal value
-0.05
MSE Loos
0.00
0.3
-007
Spoch
Epoch
(a)
(b)
(c)
Figure 2. Validation losses Gdist, Leal and Croint during training. At epoch 5, the learning rate is decreased to ensure convergence. Edsst Subfigure 2a is negative as the third term (8) constant and not considered.
Considered loss functions Following our approach we consider two distributional losses, based on the MMD L LA: MMD and the energy distance L CRPS As point pre- diction loss, we use Cpaint MSE defined in (4) based on the mean squared error. Additionally, we consider three families of losses used in the GSL literature. The first one, defined as
Table 2. Calibration and point- prediction performance of models trained by minimizing different loss functions. Losses Lastt follow the approach proposed in this paper: Bold numbers indicate the best-performing models (p-value of the Welch's t-test 0.01).
Train loss
MAE on
MAE on y
MSE on y
Cinsrauue
MAE
.087 +: .001
.270 + .003
.180 + .003
2.C. MSE
.087 +: .001
.293 .001
.661 + .002
Cliigratuee = 1,
(z A),"")
(14)
Ceerstrre
2.8: MAE
.086 + .001
270 = .002
.176 = .002
Ciserature
2. MSF
.085 + .001
.295 .001
.161 = .002
has been employed, e.g., in Franceschi et al. (2019) and Cini et al. (2023). Note that, differently from D the expectation over A is taken outside function &. The second family, denoted as 2 is inspired by Kazi et al. (2022). 2,2 Cligranure refines Cljterature focusing its optimization to node- level predictions; further details follow in Appendix C.4. For Ci and C we use both MAE and MSE as f.
.082 1: .001
.30
.191 + .200
Cpain
MSE MSE
.025 + ,001
.77 - .003
.161 = 0022
S. CRPS
.010 + .002
.699 .001
.159 + .001
L. MMD
.009 + .001
269 .01
.159 + .001
Finally, we adapt the loss function used in (Elinas et al., 2020) for the synthetic regression task:
0.03, effectively calibrating the latent distribution.
citerature = - PAPP
log p u/ ((")))
Misconfigured Pd Finally, we violate Assumption 3.1 by fixing fg f and constraining some components of 0 to incorrect values. Specifically, we force parameters 0z.j for all edges j.j associated with nodes with id 2 and 3 in
cloo
+ KL (A))I (15)
where (A() is a prior distribution and PV Gaussian distribution whose mean vector is determined for each node by the GNN output and standard deviation is set as a hyperparameter. We explored different standard deviations and choices of the prior. Details can be found in Appendix C.4
y or "ar..aay""" (v") is a
Figure to 0.25, instead of the correct value of 0i = 0.75 as in Pa- Results indicate that the free parameters in 0 are learned appropriately. Notably, increased uncertainty observed for spurious edges linking to nodes in the first node community (see Figure 1). This is expected given that nearly 60% of the edges in the community were significantly downsampled. Figures 13 and 14 in Appendix C.3 show the learned parameters from randomly selected runs.
Results on point prediction Table shows that mod- els trained with Cliterature C optimal 6 point predictions according to their respective
Cliterature and 2 achieve near-
6.3. Comparison of Loss Functions
As final experiment, we empirically demonstrate that the proposed choice of loss functions (6) is more effective at calibrating the latent graph distribution, while maintaining or sometimes improving point prediction performance com- pared to other commonly used loss functions.
By following Section 5.2, the energy distance reduces to the well-knoww Continuous Ranked Probability Score (CRPS) (Gneit- ing Raftery, 2007).
'Numerical estimates suggest that the ground-truth optimal MAE and MSE achievable by predictor are approximately 0.267 and 0. 0.158, respectively.
8

---

Learning Latent Graph Structures and their Uncertainty
performance metric (MAE or MSE). Namely, optimizing Clisrature and 2,EMAE leads to minimal MAE, but not Clterraure
Acknowledgments
This work was supported by the Swiss National Science Foundation project FNS 204061: HORD GNN: Higher- Order Relations and Dynamics in Graph Neural Networks and partly supported by International Partnership Pro- gram of the Chinese Academy of Sciences under Grant 104GJHZ2022013GC.
minimal MSE; similarly, optimizing Cliterature L,&MSE and 2, MSE results in minimal MSE. Conversely, predictors trained LACCRP achieve optimal prediction performance for both metrics. Interestingly, also LiEMSE leads to near-optimal predictions in terms of both MAE and MSE. We attribute the superiority of greint over Eliternuuee and Ch to the use of functional I' in (3) which enables a more accurate probabilistic modeling of the data-gena aatt-generating process. similar observation holds for the calibration error, discussed the next paragraph.
with either Cdist AMMDD or Cdistt
References
Bartler, A., Wiewel, F., Mauch, L.,, and Yang. B. Training variational autoencoders with discrete latent variables us- ing importance sampling. In 2019 27th European Signal Processing Conference (EUSIPCO), pp. 1-5. IEEE, 2019.
Berger, J. O. Statistical decision theory. In Time Series and Statistics, pp. 277-284. Springer, 1990.
Results calibration Optimizing the proposed losses (Ciis AMMD C yields the smallest calibration errors, as measured by the MAE of the latent distribution param- eters 0 in Pa- In contrast, loss functions commonly used in the literature result statistically worse calibration per- formance. Notably, while the point-prediction loss L outperforms Cli Cliterature and Clitenture in terms of calibration error, it remains statistically inferior the proposed distri- butional loss Ldist.
Binkkwski, M., Sutherland, D. J., Arbel, M., and Gretton, A. Demystifying mmd gans. In International Conference on Learning Representations, 2018.
Cini, A., Zambon, D., and Alippi, C. Sparse graph learning from spatiotemporal time series. Journal of Machine Learning Research, 2-:1-36, 2023.
Connor, M., Canal, G., and Rozell, C. Variational autoen- coder with learned latent structure. In International Con- ference on Artificial Intelligence and Statistics, pp. 2359 2367. PMLR, 2021.
We conclude that the proposed approach was the only one capable of effectively solving the joint learning problem.
7. Conclusions
Coutino, M., Isufi, E., Machara, T., and Leus, G. State-space network topology identification from partial observations. IEEE Transactions on Signal and Information Processing over Networks, 6:211-225, 2020.
Graph structure learning has emerged as research field focused on learning graph topologies in support of solving downstream predictive tasks. Assuming stochastic latent graph structures, we are led to joint optimization objective: (i) accurately learning the distribution of the latent topology while (ii) achieving optimal prediction performance on the downstream task. In this paper, at first, we prove both positive and negative theoretical results to demonstrate that appropriate loss functions must be chosen solve this joint learning problem. Second, we propose a sampling-basee learning method that does not require the computation of the predictive likelihood. Our empirical results demonstrate that this approach achieves optimal point predictions on the considered downstream task while also yielding calibrated latent graph distributions.
De Felice, G., Cini, A., Zambon, D., Gusev, V., and Alippi, C. Graph-based Virtual Sensing from Sparse and Partial Multivariate Observations. In The Twelfth International Conference on Learning Representations, 2024.
Deleu, T., Góis, A., Emezue, C., Rankawat, M., Lacoste- Julien, S., Bauer, S., and Bengio, Y. Bayesian structure learning with generative flow networks. In Uncertainty in Artificial Intelligence, pp. 518-528. PMLR, 2022.
Dong, X., Thanou, D., Frossard, P., and Vandergheynst, P. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23):6160-611 6173, 2016.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Elinas, P., Bonilla, E. V., and Tiao, L. Variational infer- ence for graph convolutional networks in the absence of graph data and adversarial settings. Advances in Neural Information Processing Systems, 33:18645 18648-18660, 2020.

---

Learning Latent Graph Structures and their Uncertainty
Fatemi, B., El Asti, L., and Kazemi, S. M. Slaps: Self- supervision improves structure learning for graph neural networks. Advances in Neural Information Processing Systems, 14:22667-226881 2021.
Hunter, J. D. Matplotii:: A 2d graphics environment. Com- puting in science & engineering, 9(03):90 95, 2007.
Jiang, B., Zhang, 7.,, Lin, D., Tang, J., and Luo, B. Semi- supervised learning with graph learning-convolutinnal networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11313- 11320, 2019.
Fey, M. and Lenssen, Fast graph representatiion learnin learning with pytorch geometric. arXiv preprint arXiv:1903.02242:. 2019.
Fout, A., Byrd, J., Shariat, B., and Ben-Hur, A. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
Joo, W., Lee, W., Park, S.,, and Moon, I.-C. Dirichlet vari- ational autoencoder. Pattern Recognition, 107:107514, 2020.
Kalofolias, V. How to learn a graph from smooth signals. In Artificial intelligence and statistics, pp. 920-929. PMLR, 2016.
Franceschi, L.,, Niepert, M., Pontil, M., and He, X. Learning discrete structures for graph neural networks. In Interna- tional conference on machine learning, pp. 1972-1982. PMLR. 2019.
Kazi, A., Cosmo, L., Ahmadi, S.-A., Navab, N., and Bron- stein, M. M. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transuctions on Pattern Analysis and Machine Intelligence, 45(2); 1606
Gneiting. T. Making and Evaluating Point Forecasts. Journal of the American Statistical Association, 106 (494):746-762, June 2011. ISSN 0162-1459. doi: 10.1 1919//aaa2211.110133..
1617, 2022.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Gneiting, T. and Raftery, A. E. Strictly Proper Scoring Rules, Prediction, and Estimation. Journal of the American Statistical Association, 102(477):359-377 2007. ISSN 0162-1459.
Kingma, D. P. and Welling, M. Auto-encoding variational bayes. arXiv preprint arXiv:1312.61144 2013.
Gomez Rodriguez, M., Leskovec, J., and Schölkopf, B. Structure and dynamics of information pathways in online media. In Proceedings of the sixth ACM international conference Web search and data mining, pp. 23-32, 2013.
Kipf, T., Fetaya, E., Wang, K.-C., Welling, M., and Zemel, R. Neural relational inference for interacting systems. In International conference on machine learning, pp. 2688- 2697. PMLR, 2018.
Kuleshov, V., Fenner, N., and Ermon, S. Accurate uncer- tainties for deep learning using calibrated regression. In International conference machine learning, pp. 2796- 2804. PMLR, 2018.
Gray, C., Mitchell, L., and Roughan, M. Bayesian inference of network structure from information cascades. IEEE Transactions Signal and Information Processing over Networks, 6:371-381. 2020.
Laves, M.-H., Ihler, S., Fast, J. F., Kahrs, L. A., and Ort- maier, T. Well-calibrated regression uncertainty in medi- cal imaging with deep learning. In Medical imaging with deep learning, pp. 393-412. PMLR, 2020.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. A kerne two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Lokhov, A. Reconstructing parameters of spreading models from partial observations. Advances Neural Informa- tion Processing Systems, 29, 2016
Mateos, G., Segarra, S., Marques, A. G., and Ribeiro, A. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Maga- zine, 36(3): 43, 2019.
Hadjeres, G., Nielsen, F., and Pachet, F. Glsr-vae: Geodesic latent space regularization for variational autoencoder architectures. In 2017 IEFE symposium series on compu- tational intelligence (SSCI), pp. 1-7. IEEE, 2017.
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D.,. and Kavukcuoglu, K. Asyn- chronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928- 1937. PMLR, 2016.
Harris, C. R., Millman, K. J., Van Der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J.. et al. Array programming with numpy. Nature, 585(7825):357-362 2020.
10

---

Learning Latent Graph Structures and their Uncertainty
Mohamed, S. and Lakshninarayanan, B. Learn- ing in implicit generative models. arXiv preprint 1111v:161,.03483, 2016.
Shafer, G. and Vovk, V. A tutorial on conformal prediction.
Journal of Machine Learning Research, 9(3), 2008.
Shang, C., Chen, J., and Bi, J. Discrete graph structure learn-
Mohamed, S., Rosca, M., Figurnov, M., and Mnih, A. Monte carlo gradient estimation in machine learning. The Journal of Machine Learning Research, 21 21()):18335224 2020.
ing for forecasting multiple time series. In International Conference on Learning Representations, 2021.
Shlomi, J., Battaglia, P., and Vlimant, J.-R. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L.,, Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems, 12, 1999.
Mukhoti, J., Kulharia, V., Sanyal, A., Golodetz, S., Torr, P., and Dokania, P. Calibrating deep neural networks using focal loss. Advances in Neural Information Processing Systems, 33:15288-15222 152999 2020.
Székely, G. J. and Rizzo, M. L.. Energy statisties: A class of statistics based on distances. Journal of statistical planning and inference, (338))1249-11777 2013.
Müller, A. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29 (2):429 443, 1997.
Van Den Oord, A., Vinyals, O., et al. Neural discrete rep- resentation learning. Advances in neural information processing systems, 30, 2017.
Müller, R., Kornblith, S., and Hinton, G. E. When does label smoothing help? Advances in neural information processing systems, 32, 2019.
Wasserman, M. and Mateos, G. Graph structure learning with interpretable bayesian neural networks. Transactions on machine learning research, 2024.
Niepert, M., Minervini, P., and Franceschi, L. Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions. Advances in Neural Information Pro- cessing Systems, volume 34, pp. 14567-14579. Curran Associates, Inc., 2021.
Williams, R. J. Simple statistical gradient-following algo- rithms for connectionist reinforcement learning. Machine learning, 8:229 256,, 1992.
Wu, Z., Pan, S., Long, G., Jiang, J., and Zhang, C. Graph wavenet for deep pertial-tempral graph modeling. In Proceedings of the 28th International Joint Conference Artificial Intelligence, pp. 1907-1913, 2019.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et Pytorch: An imperative style, perforrrfomeeee deep learning library. Advances in neural information processing systems, 32, 2019.
Wu, 7.,, Pan, S., Long, G., Jiang. J., Chang, X., and Zhang, C. Connecting the dots: Multivariate time series forecasting with graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining, pp. 753-763, 2020.
Pu, X., Cao, T., Zhang. X., Dong. X., and Chen, S. Learning to learn graph topologies. Advances in Neural Informa- tion Processing Systems, 34:4249 4262, 2021.
Xu, J. and Durrett, G. Spherical latent spaces for stable vari- ational autoencoders. arXiv preprint arXiv: 10805, 2018.
Rényi, A. On measures of entropy and information. In Pro- ceedings of the fourth Berkeley symposium on mathemati- cal statistics and probability, volume contributions to the theory of statistics, volume 4, pp. 547-562. University of California Press, 1961.
Yu, D., Zhang, R., Jiang, Z., Wu, Y., and Yang, Y. Graph- revised convolutional network. In Machine Learning and Knowledge Discovery in Databases: European Confer- ence, ECML PKDD 2020, Ghent, Belgium, September 14- 18, 2020, Proceedings, Part III, pp. 378-393. Springer, 2021.
Rezende, D. J., Mohamed. S., and Wierstra, D. Stochastic backpropagation and approximate inference in deep gen- erative models. In International conference on machine learning, pp. 1278-1286. PMLR, 2014.
Zadrozny, B. and Elkan, C. Obtaining calibrated probability estimates from decision trees and naive bayesian clas- sifiers. In Proceedings of the Eighteenth International Conference on Machine Learning, pp. 609-616, 2001.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. JEEE transactions on neural networks, 20(1):61-80) 2008.

---

Learning Latent Graph Structures and their Uncertainty
Zhang, Y., Pal, S., Coates, M., and Ustebay, D. Bayesian graph convolutional neural networks for semi-supervised classification. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 5829-5836 2019.
Zheng, Y., Liu, F., and Hsieh, H.-P. U-air: When urban air quality inference meets big data. In Proceedings of the 19th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 1444, 2013.
Zhu, Y., Xu, W., Zhang, J., Liu, Q. Wu, S., and Wang, L. Deep graph structure learning for robust representa- tions: A survey. arXiv preprint arXiv:2103.0300:3 14: 1-1, 2021.
12

---

Learning Latent Graph Structures and their Uncertainty
A. Proofs of the Theoretical Results
A.1. Minimizing Ceoint does not guarantee calibration
In this section, we prove Proposition 4.1.
Proof of Proposition 4.1. Recall the definition of Lroint in (4) using (3)
Croint (vb, 0) = Eer Eny Pm xi T ((
Given loss function E, is, by definition (Berger, 1990; Gneiting, 2011), the functional that minimizes
By By-rP (
Therefore, p0.v
u/z = P v/e =
Coontt is minimal. If another distribution over y, namely, par .0' a/e parametrized by O' and df
satisfies:
pab".0' .0 T pat y/1 = Pole
almost surely on then,
Cooint (8',
EE
By ~ yin
{(y', "(v",T[P') -[ppe [p
E2
Eyg pin
{(y", (T
Thus, pv',0' '0' vio
minimizes groint
Appendix A.2 discusses graph distributions as counterexamples where T[pe' .81 [[[P y/2
but pe '0'
*
Py
By this,
u/1
we conclude that reaching the minimum of g (v). 0) does not always imply pv.0
y/æ P
A.2. Minimizing Cooitt does not guarantee calibration: an example with MAE
This section shows that Croint equipped with MAE as admits multiple global minima for different parameters 0, even for simple models and fo f
Consider single Bernoulli of parameter 0* > 1/2 latent variable A and scalar function f" A) such that f" 1) (z, 0) for all æ. Given input the value of functional (a) that minimizes
Ey-P Die || T [ or (x [ + (1 (0)-)))((x,)))))) ()) -T[[M
is ((P))) = 1); this derives from the fact that range of f is (x, 0), (xx and the likelihood of f (x 1) is larger than that of (z, 0).
Note that [(P (x, for all therefore also gooint is minimized by such T. Moreover, [(P;.] is function of 0 and equal f (x:, 1) for all 0 1/2. We conclude that for any 0 + 0" distributions them minimize groint 0 1/2.
p0.ú and P are different, yet both of v/
similar reasoning applies for < 1/2.
A.3. Minimizing dist guarantees calibration and optimal point predictions
This section proves Theorem 5.2 and corollary of it.
Proof of Theorem 5.2. Recall from Equation (6) that
dist (0) E, A(P= w/ g/a
13

---

Learning Latent Graph Structures and their Uncertainty
We start by proving that if Cdist (0,4) vb)
[ (0, 1b) is minimal.
Note that (di (8, 4) 0 implies that A(P pll.)) almost surely on and, particular, T|
almost surely in æ. Then, by Assumption 5.1, Py]= -0.00 y/1
8/2z u/z
y|2ر - T P which leads to Croint (v) being minimal (Proposition 4.1).
y/z
We now prove that if Ldsst (6, x5*)))) =
Loa (0) O.
From the previous step, have that Cdsst (0, v0) 0 implies -/ that f = f- and the injectivity of ʃa in such E I, for any output a single exists such that (I, A) y- Therefore, the probability mass function of y equals that of A. Accordingly, PAJa pa implies PA P1-
_ almost surely for æ E I. Under the assumption y/a
We also prove corollary of Theorem 5.2. Corollary A.1. Under Assumptions 3.1 and 5.1, if
1. 35 Supp((=) S X such that f (æ; :) is injective,
2. (x, A) continuous in H, VA E A.
then
Cooint (0, (0.))) is minimal Coal (0) (0)= =0
Casst (0, =0
The corollary shows that it is sufficient that f* is continuous in and there exists point F where f" -) is injective to meet theorem's 's hypothesis IP= PZ (7) >> 0; we observe that, as A is discrete, the injectivity assumption is not restrictive as if the domain were continuous.
Proof. As A is finite set, the minimum minAzyvelll A) - (" A'III > 0 exists and, by the injectivity assumption, is strictly positive.
By continuity of (- (., for every < jez there exists 6, such that for all E Bi, 8) we have f (z, < follows that, Vz E B,
f
(x, ('I
2 (I, A) - -f" -1 - (t,
11/"(z, A) f A')ll 2E
> (z, - f"(I,A'III -E>0.
Where the second inequality holds for the continuity of x + (x, A) VA. Finally, Supp(P?) and B 8) C I, we conclude that
(2(1) 2 (B 8)) > 0,
therefore, we are in the hypothesis of Theorem 5.2 and can conclude that
Cooint (0, vb*) is minimal dist (0, (0,"))=0 Coal (0) 0.
A.4. Injectivity hypothesis for graph neural networks
Now, we show that hypothesis IP PZ-P: (I) of Theorem 5.2 is always met for certain families of graph neural networks. Proposition A.2. Consider a 1-layer GNN of the form (x, A) : (Ax) = y, with x, y E R and nonlinear bijective activation function a. If the support Supp P of x contains any ball N then Pa (T) > 0.
14

---

Learning Latent Graph Structures and their Uncertainty
To prove Proposition A.2, rely following lemma.
Lemma A.3. Given g(z, a) with E (0,1) and RRXx, Let Ig {a g(x, a) is injective in a} S X be the set of points E X such that map + g(x, a) is injective. The following implication holds:
E f-1,0,01,11
s.t. 8 1118 Z.
(16)
Proof. We prove the two implications separately.
(=) a E Ig then there exist a a" E (0, 1)1xN with a' * a" such that a'v = d²x. This implies that (a' - -a")x x O.
Defining ó as (a' a"), we have proven that there exist き E (, 10001112200 132xN such that óx = 0, i.c. X.
Assume that 3 8 + E {-1,0, 131x such that å 1 æ. Each component 6, of d can be written as the difference between two values d/ am E [0, As # 0 then there exists at least one index j NV such that d's + a². This implies that 3 a', a',a" E {0, 1 with a' + a" s.t. (a' - =a") 0, which implies that x: 4 Lg.
Proof of Proposition A.2. We begin by considering the projection g(x, a) = ax with (0, (0,1)1xN and x E R.N. Then we extend to A {0, 13 NNN and nonlinear functions.
Let 1 R 1g be the complement in RN of Ig. Recalling Lemma A.3 and its notation, we have 3 possible defining collection of (3 1)/2 hyperplanes of vectors perpendieular at least one o; set 1g is the union of such a finite collection of hyperplanes. By hypothesis, Supp (P:) contains a ball E RN, therefore Supp(P:) &f Ig and
Pa~P; (1g) < 1. We conclude that P=~P; (Ig) = 1 - PawP: (1g) >0
A similar result is proven for G(x, A) = Ax with A E {0, 1J In fact, G stack of N functions above and la 4g- Finally, composing injective function G with injective function a leads to function g( A) o (G((z, A)) being injective in A for the same points x for which G is injective, thus proving the proposition.
B. Estimation of Optimal B1 and B2
Here we show that, when reducing the variance of the SFE via control variates (12), the best 31 and 33 can be approximated by
B1
E P.
(l)
32
E (2,9") J-p
(17)
A1.Ag-PP
ArPA
Consider generic function (AA) depending on sample A of parametric distribution (A) and the surrogate loss ((A) in (11),
G(A) = Vo log (*(A) - 3 (M(A) EA- [b (A))))
(18)
Following existing literature (Sutton et al., 1999; Mnih et al., 2016) where ,3 is often referred to as baseline we set M(A) Vo log pd (A). The I-sample MC approximation of the gradient becomes
[LL))) ~ G(A') = (L(A') V log P" (A'',
(19)
with A' sampled from pd. The variance of the estimator is
po [L(AA) B) log Pd (A)] V Ao [L(A)Vo log p8 (A)] +
3 EANPo (VV log po (A)) 2, IE AA (((A) (Vo log P8 (A))
(20)
and the optimal value 3 that minimizes it is
E Ex-po L(A) (Vo log P0 (A)))
(21)
E AA
(Volog p8 (A))²
15

---

Learning Latent Graph Structures and their Uncertainty
If approximate the numerator with ([ log p (A)) obtain that B Rs E[L(A)]. By substituting L(A)
with the two terms of (10) get the values of 31 and 32 in (17).
We experimentally validate the effectiveness of this choice of / in Section 6.
C. Further Experimental Details
C.1. Dataset description and models
In this section, we describe the considered synthetic dataset, generated from the system model (1). The latent graph
distribution PA is multivariate Bernoulli distribution of parameters or Pa = Pe- =I)= A (1 0% (1,)((),),, The components of l" are all null, except for the edges of the graph depicted Figure which are set to 3/4. heatmap the adjacency matrix can be found in Figure 4.
2
4
0
3
5
Figure The adjacency matrices used this paper are sampled from this graph. Each edge in orange is independently sampled with probability 0" In the picture, 3 communities of an arbitrarily large graph shown.
True thete parameters
8.30 000 8.8
0:15
375
0.5
015
0.7
0.00 C50 0:99 0.0 8.88 0.00 0.00
-844
375
022
660
570
000
0:0
0.99 0.0 8.8 300 0.00
9.39
0.0 8:88
015
040
303 0.0
C44
351 010 BED
3 mm
8C0 303 0.0 060 043 000
6:55
100
575
075
810 9/1 mm ArB
mm 6m
Figure 4. 0% parameters for each edge of the latent adjacency matrix. Each square corresponds edge, and the number inside is the probability of sampling that edge each prediction.
Regarding the GNN function f", we use the following system model:
Table 3. Table of the parameters used to generate the synthetic dataset.
Parameter
Values
(A, = tanh Σ 1[A' + 0jæz8
(22)
6* 0.75
A ~ (A)
1.5
N
12
where [:] is the element-wise indicator function: [a) + a is true. E R din are randomly generated inputs: x ~ (10 II).. ob E Bdott x dim are part of the system model parameters. We summarize the parameters considered our experiment in 3.
din
4
dout
1
vi
[0.3, 0.2,
36
[.1.3,0.,
16

---

Learning Latent Graph Structures and their Uncertainty
The approximating model family (2) used in the experiment is the same the data-generating process, with all components of parameter vectors 0 and being trainable. The squared MMD diserepancy is defined over Rational Quadratic kernel (Biríkowski et al., 2018)
11 1 v a
<(y',
1
(23)
200²
of hyper-parameters a = 0.04 and = 0.5 tuned on the validation set.
The model is trained using Adam optimizer (Kingma & Ba, 2014) with parameters 31 = 0.9, 82 = 0.99. Where not specified, the learning rate is set to 0.05 and decreased to 0.01 after 5 epochs. We grouped data points into batches of size 128. Initial values of are independently sampled from the (0.00, 0.1) uniform distribution.
C.2. Additional details on the experiments of Section 6.1
We present here additional figures discussed in Section 6.1. Figure 5 reports the values of the learned parameters 6, while Figure the absolute discrepancy from 0", Figure 7 reports the values of the learned parameters when considering a graph of 120 nodes.
Learned theta parameters
Abselute error on theta parameters
SAN 0.00
600
0:7
0.0
A.C2 941 600 C:1 63) 341 506
3.C5 0:00 EDC CK
031
-OC 5:00 COC CX 040 631 341 300 0.0 0:00 0.3 541
KOE
AAA 550 LUE UX 910 0:0
AAU DOG GOL U. U1D 020 309 300 SW 0.2 084
BEB EEC Ex
031 3E1
BEB EOE SEL BAD
3
Figure 5. The learned parameters for the latent distribution corre- sponding to the stochastic adjacency matrix.
Figure 6. Absolute error made on the parameters of the latent distri- bution.
Learned theta parameters
12
20-
17
40
40
0.6
02
60
85
80
88
58-
0.2
100
116
AARERAR
Figure 7. Learned parameters for a graph with ~ 15K possible edges.
C.3. Additional details on the experiments of Section 6.2
We present here additional details discussed in Section 6.2.
Fixed perturbed fo Figures in this paragraph correspond to the experiment where the processing function fo is fixed on a perturbed version of Figures 8 correspond to runs with increasing perturbation factor V.
17

---

Learning Latent Graph Structures and their Uncertainty
Learned theta parameters
Abs error on theta perameters
Learned theta parameters Sox san
Abso use crror on theta parameters
San
oo Sao
XEI cod
SM MC1 Co
MD O
340
6D C3 9M ML C0 09) 3M MD 60
33C
030
566
030 CcD 281
3 030 Sc1
666
623 OM
ICE CCL 031 3X
(a)
(b)
(a)
(b)
Figure 8. Learned 0,g parameters (a) and Absolute Error (b) for maximum perturbation factor V of 10%.
Figure 9. Learned Bg parameters (a) and Absolute Error (b) for maximum perturbation factor v of 20%.
Learned theta parameters
Absolute thera
Learned theta
Abso use theta parameters
D47
4422 ACL
XE2 031
030 02
-006
380
090
km
1-00 352 MD CD OX OL, 531 K. 6:0 CCP 0M 345
-0000 800 K00
3KC
0.0
-00 340 LO OM 3M KCL C. 055 3M
(a)
(a)
Figure 10. Learned 0gg parameters (a) and Absolute Error (b) for maximum perturbation factor V of 50%.
Figure 11. Learned Bg parameters (a) and Absolute Error (b) for maximum perturbation factor V of 80%.
Generic GNN as f To evaluate our approach in a more realistic setting, we use a generic GNN as fo- Specifically, we implement GNNs from (Morris et al., 2019) with varying numbers of layers and layer sizes. It is important to note that the GNN implementation includes self-loops, which prevents the diagonal elements from being correctly learned. However, this does not impede our method from learning the remaining edges accurately.
Table 4. Network configurations and corresponding convergence re- sults.
Layers dimensions
Convergence
[4. 1]
1,
[4,
[4,8,
M, 2, 1
M. 1,
4. 1,32, 8,
Table 4 presents the network configurations and whether they successfully converged to the ground truth distribu- tion. Since diagonal elements artificially inflate the MAE for 0, we consider model to have converged if the final MAE on 0 is less than 0.11.
4, 64,4 8,
4. 64, 16, 1
4. 62, 1
8,8,8,4,1
Most of the models successfully converged, except those with high bias. This demonstrates that our method is effective even beyond Assumption 3.1. In Figure 12 we show the learned parameters of PM for randomly extracted run.
Misconfigured Po Figures 13 and 14 correspond to the experiment where some O,y values of PÅ are fixed at incorrect values, while the processing function fo is fixed to the true one. In the community affected by the perturbation, free 0, values tend to be sampled more frequently to compensate for the downsampling imposed by the perturbation. Interestingly, all the edges with at least one edge in the second community (75% of the edges) appear unaffected by the perturbation.
18

---

Learning Latent Graph Structures and their Uncertainty
Leamnd theta parameters
Absolute error on theta parameters
B40
G00 COL
-10
(a)
(b)
Figure 12. (a) Learned B, parameters when the parametric processing function f is generic GNN as presented in (Morris et al., 2019) and (b) Absolute Error made with respect to true parameters Oij. As self-loops are deterministically added by the network, the diagonal elements should not be considered.
Learned thota parameters
Absolute ertor on thera parameters
Learned thora parameters
Abso crror theta parameters
040
140
033
64
HUUE K2P 020 280
HoV8 xty C 521
281
K2V C29 020
522 MLL
020 330 521
60E LED D3 0Z)
(a)
(b)
(a)
(b)
Figure 13. Learned O2 parameters (a) and Absolute Error (b) for misconfigured PM
Figure 14. Learned 0yg parameters (a) and Absolute Error (b) for misconfigured PM
C.4. Additional details on the experiments of Section 6.3
All models have been learned using SFE. Croint rely on the following gradient with respect to 0
V Ve = Bz.w- [2(EAl0] - 1² >") log P% (A)]]-
For C Cliterature, the gradient is rewritten
V C litterature -E A ((((),)))) b) log (A)]
with b estimating the expected value Ex. A Al v*)].
The second family of loss functions C Eliterature focuses on node-level prediction rewriting ((g.y' v") as the mean N Em E(Oi, v²) over the prediction error at each node i. The gradient with respect to 0 is then written as
I
N (C(y), vt) - V. (Pg(
V C clterraure Ex, E AmPa
(24)
N
where b; are computed as moving averages of E(y,, V.).
The last family of loss functions (i.e., C ps alue .A (1x") to be set. We consider the following priors and standard deviations, selecting the combination with the lowest validation loss:
Cliterature) requires (i) prior distributions (A(A and (ii) a standard deviations for
ii For the prior distributions, we assume that each edge is sampled independently according to a Bernoulli distribution.
We consider three different prior specifications:
19

---

Learning Latent Graph Structures and their Uncertainty
The first prior is Bernoulli distribution with parameter p 0.01 for all edges.
The second prior is Bernoulli distribution with parameter 0.5 for all edges.
The third prior is defined based on the ground truth graph structure: for edges sometimes present in the ground truth structure (i.e., f * 0), the Bernoulli parameter is p 0.75, while for edges never present in the ground truth structure (i.e., D 0), the parameter is 0.05.
(ii) the standard deviations considered are: {0.001, 0.005, 0.01, 0.05, 0.1, 0.53.
C.5. Real-world experiment
To demonstrate that method learns meaningful graph distributions in real-world settings, train neural network air quality data in Beijing (Zheng et al., 2013). The dataset consists of pollutant measurements collected by sensors in Chinese urban areas across several months. We do not use this dataset as benchmark because the graph structure provided with the data is based on physical distance, and there is no guarantee that it represents the true underlying structure. The neural network we use consists of a GRU unit for processing each time series, followed by a GNN with a learnable graph structure. Figure shows the graph structure learned by our approach, demonstrating its capability to learn meaningful distributions in real-world settings.
Figure 15. Graph structure learned by our approach on Beijing air quality data. The nodes correspond to sensor locations. The thickness of the edges is proportional to the corresponding probability. Map data from OpenStreetMap.
C.6. Compute resources and open-source software
The paper's experiments were run on a workstation with AMD EPYC 7513 processors and NVIDIA RTX A5000 GPUs; on average, single model training terminates in few minutes with a memory usage of about IGB.
The developed code relies on PyTorch (Paszke al., 2019) and the following additional open-source libraries: Py Geometric (Fey & Lenssen, 2019), NumPy (Harris et al., 2020) and Matplotlib (Hunter, 2007).
20


Reviews:
[{"review_id": "0lbIsQmDgj", "reviewer": "Reviewer_uM1K", "summary": "This paper deals with the problem of learning on graph in a setting where the graph (Adj. matrix: A) is unobserved and is to be estimated from the training data (node features: x, node labels/targets: y). It theoretically shows that the optimal point estimate does not guarantee the calibration of the latent graph structure's distribution. However, if a certain type of loss between the ground truth and model's prediction distribution is zero, then that both achieves the optimal point estimate of the targets and recovers the true distribution of the graph structure under restrictive assumptions. A variance reduction strategy using control variates is adapted for the specific setting. Numerical experiments on small scale graphs are conducted to verify the theory presented.\n\nOverall, the theoretical contribution of this work is inadequate and the empirical validation is rather weak (detailed comments/questions/suggestions in later sections).\n\n**Update:** The authors' rebuttal helped in partially addressing some of my concerns, particularly the comparison with one existing baseline on a synthetic dataset shows that the proposed method can generate graphs with similar statistics. However, I still think that **a)** the novel theoretical contribution (the proofs are extremely simple, MMD is an existing loss function, and control variate is another widespread technique for variance reduction) is limited primarily due to unrealistic and restrictive modelling assumptions, **b)** the experiments seriously lack investigation of performance and comparison with existing techniques with various parameterizations of the graph generative models. I am raising my score to 2 to acknowledge the authors' effort during the rebuttal.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1**.\nPart of our results can indeed be applied to more general latent variable models, and we view this broader applicability as a strength rather than a weakness. As shown in the Experiments Section, our theoretical results can be successfully applied to Graph Structure Learning problems, making them relevant to the GNN community. Furthermore, some results are specific to GNNs (e.g., Proposition A.2).\n\n**W2 W3, W4 and W5**.\nOur paper highlights the critical role of the loss function to effectively achieve calibration; this specific formulation and set of assumptions serve this goal. \nSome assumptions can be relaxed, broadening the applicability of our findings. However, we believe that our developments lay a solid foundation enabling further developments. \nWe expect - and have validated with different experiments (refer to Sections 6.1 and 6.2) - that the theory remains valid beyond certain assumptions. \nIn the following points, we provide additional evidence to support that our results can be generalized to address your concerns further:\n\n- **W2)**\nWe performed an additional experiment where $p(y|x,A)$ is a continuous distribution both in the system model (Eq. 1) and the approximating model (Eq. 2). Specifically, we adapt the data-generating process described in Section 6 to include uniform noise $\\eta \\sim \\mathcal{U}(-\\Psi^*, \\Psi^*)$) added to each of the components of the output $y$.\nAccordingly, the approximating model now includes a learnable stochastic variable ($y=f_\\psi(x,A) + \\epsilon$ with $\\epsilon \\sim\\mathcal{U}(-\\Psi, \\Psi)$ and $\\Psi$ learnable).\nThe results (reported below for different values of $\\Psi^*$) demonstrate that our approach is able to approximate the real distribution even if the processing function is not deterministic.\n| Max pert. $\\Psi^*$ | MAE on $\\theta$ | Max AE on $\\theta$ | \n| --- | --- | --- |\n| 0    | 0.009 $\\pm$ 0.001 | 0.06 $\\pm$ 0.01 |\n| 0.1  | 0.008 $\\pm$ 0.001 | 0.05 $\\pm$ 0.01 |\n| 0.2  | 0.012 $\\pm$ 0.001 | 0.06 $\\pm$ 0.01 |\n| 0.3  | 0.019 $\\pm$ 0.003 | 0.09 $\\pm$ 0.01 |\n| 0.4  | 0.032 $\\pm$ 0.003 | 0.13 $\\pm$ 0.01 |\n\n\n- **W3)** \nIt is indeed possible to parametrize the graph distribution making it input dependent.\nOne approach involves parameterizing $\\theta$, the parameters of $P_A^\\theta$, as a function of the input $x$, such as $\\theta = g_{\\theta'}(x)$, where $\\theta'$ denotes an additional set of free parameters. Regarding the theoretical results, Theorem 4.2 can be extended, e.g., to piecewise constant mappings $x \\mapsto p(A|x)$; we conjecture that a proof could be established for $p(A|x)$ smoothly varying with respect to $x$.  \n\n\n- **W4)** \nPlease see our response to Reviewer qZGr's Question 1.\n\n\n- **W5)**\nIn the paper, we conducted various experiments to study this theorem's hypothesis, specifically (a) solving the joint learning problem (Section 6.1), (b) setting the processing function to a different, incorrect function (Section 6.2 \"Perturbed $f_{\\psi^*}$), and (c) using a generic GNN from a different class compared to the true one (Section 6.2 \"Generic GNN as $f_{\\psi}$\"). The empirical evidence gathered demonstrates that, even in these cases, we can still appropriately learn the latent distribution.\nPlease note that we have also demonstrated that point-prediction loss functions often fail to calibrate the latent distribution, even when the true processing function is used (i.e., $\\psi = \\psi*$).\n\n\n**W6**. \nWe are not sure we have fully understood your proposed solution.\nIn real-world applications, $P^*(A)$ is unknown and no samples from it are observed. How do you suggest estimating it? Assuming a priori that one model is better than another and, therefore, that it could serve as a ground truth seems inappropriate to us. If our response does not address your comment, could you elaborate in more detail?\nNonetheless, to provide additional evidence that our method learns sensible graph distributions in real-world settings, we run an extra experiment. Please refer to our response \"**a (additional experiment)**\" to Reviewer qZGr.\n\n\n **W7**.\nRespectfully, we disagree on this point. Kipf et al. (2018) do model the latent relationships as stochastic. Citing from their paper, they use an \"encoder that predicts a probability distribution $q_\\phi(z|x)$ over the latent interactions given input trajectories\", more in detail the encoder \"returns a factorized distribution of $z_{ij}$, where $z_{ij}$ is a discrete categorical variable representing the edge type between object $v_i$ and $v_j$\". In Section 3.2 they further show how they used the Gumbel-Softmax trick (Maddison et al., 2017) to sample from this discrete latent random variable.\n\n**References**\n\n- Kipf et al. \"Neural relational inference for interacting systems.\", ICML 2018\n- Maddison et al.. \"The concrete distribution: A continuous relaxation of discrete random variables.\", ICLR 2017", "claims_and_evidence": "1) Optimal point estimate of the targets does not lead to calibration of  graph distribution: Proposition 4.1 shows that.\n\n2) MMD minimization between the pushforward measures of targets leads to optimal point estimate of the targets and calibration of distribution of A: Theorem 5.2 shows that. (I have some questions about the usefulness of this, which are asked in 'questions to authors' section below)", "methods_and_evaluation_criteria": "Results in Table 2 verifies the theory presented numerically.", "theoretical_claims": "Please see \"Claims And Evidence\" section above.", "experimental_designs_or_analyses": "The experiments numerically verify the theory presented (my questions are written below)", "relation_to_broader_scientific_literature": "While the results are correct, their impact in advancing the field of learning on graphs is minimal in my view, because of impractical and restrictive modelling assumptions and lack of real-data experiments (check the weakness section for detailed comments and questions).\n\nThe discussion of related work is confusing and inaccurate at places (check the weakness section for details).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1) The paper is moderately well written and easy to read.\n\nWeaknesses:\n\n1) Relevance to GNN community: The main theoretical results presented in this paper are only marginally relevant to advancing knowledge in the area of learning on graphs. Specifically, the theoretical results are valid for any latent variable model which can be characterized by eq 1. The stated assumptions are not specific to graph domain in any discernable way as well. It is not clear how the results of this paper can be helpful for any GNN researcher or practitioner in any way.\n\n2) Restrictive modelling assumptions: The model in eq. 1 is rather limited. First, this idea that $y= f(x, A)$ is a deterministic function of $x$ and $A$ limits its applicability to classification problems, where the label is a K-ary variable, sampled from $p(y|x, A)$. Similarly, if the targets are noisy in a regression setting, then a deterministic mapping is inadequate.\n\n3) Impractical modelling assumptions: The model in eq. 1 considers $x$ observed and factorize the joint distribution as follows: \n$p(y, A|x) = p(A) \\times Indicator_fun(y=f(A, x))$. In other words, eq. 1 does not consider any dependency between A and x. But, this is typically not the case in real world graph datasets and for problems of practical interest.  For example, Kalofolias 2016 (https://arxiv.org/pdf/1601.02513) considers learning a graph from smooth signals. Intuitively, if the node features are similar for a node pair $(i,j)$, then $A_{i,j}$ should be higher and vice versa, this type of approach models the dependency between $x$ and $A$ explicitly. Even for the datasets, used extensively for evaluation of GNNs, there is dependency between the graph structure and node features. For example, on homophilic graphs (e.g. Cora, having stochastic block model structure approximately), the node feature similarity is heavily correlated with graph connectivity. It is not clear whether the results in this work can address such setting.\n\n4) Other assumptions: How does the injectivity assumption work for any GNN with more than one layers? Otherwise, theorem 5.2 is of little practical significance.\n\n5) Other comments about theoretical results: The 'proof' of Proposition 4.1 only requires the understanding that two distributions can differ even if a certain moment matches. Given the trivial nature of this results, the choice of stating it as a formal proposition is questionable.\nMoreover, the algorithm does not guarantee that we can obtain $\\phi^*$, so how the requirement of knowledge of the 'true' GNN in Theorem 5.2 is justified?\n\n5) While the authors argue in favor of not including any real data experiments and existing baselines, it is not at all convincing. For example, if the 'true' distribution that generates the graph is unknown, one could still run the proposed method with some chosen parameterization (to capture some useful inductive bias) to perform an estimation of $P(A)$, and then use the learned model for sampling graphs and then check whether graph statistics match with the 'true' distribution. This avenue gives an indirect route to assess calibration. Bayesian GNNs (Zhang et al., 2019) and Variational GNN (Elinas et al., 2020) could serve as baselines with minimal modifications in that setting. \n\n6) Discussion of related work is far from being accurate. For example, the authors write \"Some approaches from\nthe literature model the latent graph structure as stochastic (Kipf et al., 2018; Franceschi et al., 2019; Elinas et al.,\n2020; Shang et al., 2021; Cini et al., 2023), mainly as a\nway to enforce sparsity of the adjacency matrix.\"  Kipf et al., 2018 propose GCN on a fixed graph, they do NOT 'model the latent graph structure as stochastic '.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please address the issues raised in the previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "PBQBxa8c2p", "reviewer": "Reviewer_vKHP", "summary": "This paper carefully studies the problem of how the optimal latent graph can be learned given observational information from both theoretical and empirical perspectives. It proves that optimizing the usual point prediction does not guarantee calibration of the adjacency matrix distribution. It also provides a loss function that guarantees simultaneous calibration of the latent variable and optimal point predictions. A sampling-based strategy with variance reduction is designed to tractably compute the loss functions. Experimental results on carefully designed synthetic datasets verify the theoretical claims, and also demonstrate the advantages when theoretical assumptions are not fully satisfied.\n\n**Update after rebuttal**\n\nI have read the response from the authors. Since my original recommendation was to accept, I will maintain my recommendation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1**.\nWe appreciate your suggestion. If the paper is accepted, we will use part of the camera-ready additional page to improve the presentation. \n\n**C1**.\nYes, this is a relevant point. This is why we run experiments in controlled settings to test our method beyond those assumptions. In particular, Section 6.1 studies the joint learning problem and shows that the processing function can be approximated well.\nSection 6.2 (\"Perturbed $f_{\\psi^*}$\") tests cases of unsuccessful training, showing that even if the GNN makes prediction errors, the graph structure can be learned with good quality. Section 6.2 (\"Generic GNN as $f_{\\psi}$\") considers a family of GNNs that does not fulfill Assumption 3.1. Also in this setting we were able to learn meaningful distributions.\nFinally, we would like to highlight that point-prediction functions simply fail to calibrate the graph structure even when the GNN is fixed to the true (supposed to be known) processing function.\n\n**C2**.\nThank you for pointing out this potential source of misunderstanding. Proposition 4.1 states that calibration is not granted for a generic point-prediction loss, not that for any choice it will necessarily fail. In Appendix A.2, we showed that optimizing a commonly adopted metric, the MAE, can be problematic in that context; other specific metrics are not directly investigated in this paper. \nWe will revise the paper to prevent any possible confusion.\n\n**C3**.\nThank you for your relevant question. For the purpose of Theorem 5.2, Assumption 5.1 can be relaxed to hold almost surely with respect to $P_x^*$  - as you suggested. However, we think the current statement of Assumption 5.1 is easier to grasp.\n\n**C4**.\nThank you for carefully reading the appendices. \nThe more the two terms in the expectation are independent the more the approximation is accurate. \nThe main reason to accept this approximation is that it enables an easy estimation of the optimal $\\beta$.\n\n**C5**.\nYes, we are considering $A \\not = A'$ in that line. We fixed the typo, thank you. \nRegarding the second question, for every $A$ we can find a $\\delta_A$ granting $||f^*(\\bar{x}, A) -  f^*(x, A)||<\\epsilon$; this follows from the continuity of $x\\mapsto f^*(x, A)$. As we have finitely many $A$, we take $\\delta=\\min_{A\\in\\mathcal A} \\delta_A$. Thank you for raising the point, we will clarify it.", "claims_and_evidence": "The claims are well supported by both theoretical and empirical results.", "methods_and_evaluation_criteria": "1. The proposed method is theoretically motivated. \n\n2. Sampling-based estimation of MMD and the control variate for variance reduction are properly derived.\n\n3. The computational complexity is analyzed and it seems acceptable for practice.\n\n4. The method is evaluated comprehensively in experiments. See **Experimental Designs Or Analyses** for detailed comments.", "theoretical_claims": "The theoretical claims on the limitation of point prediction and the optimality of the proposed loss functions are supported by rigorously stated theorems with proofs.", "experimental_designs_or_analyses": "The experimental design is rather comprehensive.\n\n1. The experiments are conducted on synthetic datasets because the ground truth graphs are known and it is easy to manipulate the generation process to create different settings. This is reasonable, because I prefer to consider this paper a theory paper and the experiments are for the proof of concepts.\n\n2. The experimental settings are clearly described and well justified.\n\n3. Under the normal setting, the results show that the MMD loss is suitable for joint learning. The variance reduction component is effective. The method is applicable for large-scale graphs. All these results provide strong support for the theoretical analysis in the main text.\n\n4. Considering that the theoretical analysis relies on Assumption 3.1 which ensures optimal solution, this paper conducts a series of experiments to see what will happen when the assumption is violated. The results show that the proposed method is still effective under different settings.\n\n5. The MMD loss is compared with classical choices of loss functions in GSL. The results show that MMD is advantageous in predicting the target variable and superior in recovering the latent graphs.", "relation_to_broader_scientific_literature": "This paper is related to graph structure learning (GSL), latent graph inference, and distribution calibraction.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\nS1. This paper explains a long-troubling issue in GSL in theory under some simplified assumptions.\n\nS2. The notations are used accurately, theoretical results are clearly stated and the proofs are concise to read.\n\nWeaknesses:\n\nW1. Figure 2-11 appear in the appendix but are mentioned in the main text. Please consider better organizing the presentation of the experimental results to make the main text more self-contained.", "other_comments_or_suggestions": "C1. Even though Assumption 3.1 ensures the existence of optimal parameters, it can be hard to reach in practice. For example, when inferring latent graphs from multivariate time series, prediction error is inevitable, and there could be more than one best graph. The authors can discuss such limitations when applying their theory to real-world applications.\n\nReferences:\n\nA Graph Dynamics Prior for Relational Inference. In AAAI, 2024.\n\nC2. In Appendix A.2, to argue that minimizing $\\mathcal{L}^{point}$ does not guarantee calibration, a counter-example is created based on a specific choice of the loss function, i.e., the MAE. However, in the statement of Proposition 4.1, the authors seem to claim that the conclusion always holds for all choices of $\\ell$. Can you make the statement of Proposition 4.1 more precise or provide any proof or thoughts to support that counter-examples can always be constructed?\n\nC3. In Assumption 5.1, can we relax the statement of \"$\\triangle(P_1,P_2)=0$ if and only if $P_1=P_2$\" to \"$\\triangle(P_1,P_2)=0$ if and only if $P_1=P_2$ almost surely\"?\n\nC4. In Appendix B, why is it reasonable to approximate the numerator of Eq. (10) with $\\mathbb{E}[L(A)]\\mathbb{E}[(\\nabla_\\theta\\log P^\\theta(A))^2]$? When will the approximation be accurate?\n\nC5. In Line 687 of the proof of Corollary A.1, should we write $A\\not=A'$ to ensure that $\\bar{\\epsilon}>0$? Besides, since $\\delta$ is chosen for $f^*(\\cdot,A)$, how can we ensure that $\\lVert f^*(\\bar{x},A')-f^*(x,A')\\rVert<\\epsilon$? That is, why does the second inequality in Line 695 hold? I don't fully understand the proof. Can you provide more explanation?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mVUqpUk8Q2", "reviewer": "Reviewer_Y7sL", "summary": "In this paper, the authors investigate the calibration of latent graph structure distributions in the context of graph structure learning. They propose an optimization procedure for a predictive probability model that ensures not only learning the best predictive model but also calibrating the latent distribution of the underlying graph structure. To compute the gradient of the Maximum Mean Discrepancy (MMD) loss, the authors rely on Monte Carlo (MC) sampling and reduce the variance introduced by MC through a control variates approach. Experimental results demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Wa**.\nThere might be some misunderstanding here, please allow us to clarify that the assumption is indeed satisfiable.\nBoth Equations 1 and 2 can model continuous or discrete outputs, but their respective outputs $y$ and $\\hat y$ take values from the *same* set $\\mathcal Y$. \n$\\Delta$ is a dissimilarity measure between distributions over the same set $\\mathcal Y$ for both its arguments (i.e., $P_1,P_2$).\nAssumption 5.1 relates to $\\Delta$, and it is known to be satisfied, e.g., by $f$-divergences and some integral probability metrics \n\n**Wb**.\nPlease note that our Theorem 4.2 demands only injectivity over a set of inputs with non-zero probability; in the case of Corollary A.1, this reduces to ensuring injectivity at a single point $\\bar x$. The assumption relates to the data-generating process and the associated learning problem.\nThe particular case of graph classification is relevant due to the discrete nature of $\\mathcal Y$. Here, ensuring calibration of the latent variable presents increased complexity, regardless of the chosen loss function.\nAccording to our results, distributional losses should still be favored over point-prediction losses even in this setting, if calibration of the latent variable is among the goals.\n\n\n**Wc**.\nPlease note that Proposition A.2 and Lemma A.3 specifically relate to graph neural networks and we empirically demonstrated that all the developed results are applicable in Graph Structure Learning scenarios.\nSecondly, as commented in the paper, ground-truth knowledge about the latent graph distribution is not available in any real-world datasets we are aware of. Our paper addresses this lack of information in two ways: (i) we derived theoretical guarantees to reduce the need for empirical assessments and (ii) we rigorously validated and tested our approach on synthetic data that provides the required ground truth. \nNonetheless, to provide evidence of the effectiveness of our method in real-world scenarios, we perform an additional experiment.  Please see our response \"**a (additional experiment)**\" to Reviewer qZGr.\n\n\n**Wd**.\nParameterizing the graph structure as a set of Bernoulli distributions allows us to cover *any* distribution over graphs of independent edges. Moreover, this is a common parameterization in the graph structure learning literature (Francheschi et al. 2019, Elinas et al. 2020, Sun et al. 2021, Cini et al. 2023), other than being easier to inspect and visualize. Testing other distributions is indeed possible.\nFurthermore, we stress that the theoretical results are not restricted to Bernoulli distributions.\n\n**We**.\nPlease note that we do provide a comparison with existing literature (see Section 6.3 and Table 2). However, as our paper discusses loss functions, we compared the proposed approach with loss functions used in the literature. \n\n**Question**\n\nYes, $x$ can be understood as the node feature matrix provided as input to the prediction model. It can contain discrete and continuous attributes, as common in GSL setups, but also time series, as in spatiotemporal data analysis. \n\n\n**References**\n\n- Franceschi et al. \"Learning discrete structures for graph neural networks.\", ICML 2019\n- Elinas et al. \"Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.\", NeurIPS 2020\n- Sun et al. \"Graph structure learning with variational information bottleneck.\", AAAI 2021\n- Cini et al. \"Sparse graph learning from spatiotemporal time series.\", JMLR 2023", "claims_and_evidence": "The claims are generally well-supported by theoretical analysis and experimental results.", "methods_and_evaluation_criteria": "The proposed method is reasonable.", "theoretical_claims": "The theoretical claims are clearly presented.", "experimental_designs_or_analyses": "The experimental design and analysis are generally sound. Some concerns can be referred to the below 'Weakness'.", "relation_to_broader_scientific_literature": "NAN", "essential_references_not_discussed": "NAN", "other_strengths_and_weaknesses": "•\tStrengths:\nOverall, I think the problem of calibrating the latent graph structure distribution to be important. The proposed method is grounded in theory and is well organized, and the sampling-based learning approach appears practical. The empirical results are also interesting.\n\n\n•\tWeaknesses: \na.\tIn Equation (1), y is typically considered a discrete graph label, whereas in Equation (2), \\hat{y} (the model output) is usually continuous. The predictive distributions of discrete y and continuous \\hat{y} cannot theoretically be the same, so is Assumption 5.1 satisfiable? \n\nb.\tThe injectivity condition in Theorem 5.2 seems rather strong. For instance, in some graph classification tasks, different subgraph structures A may correspond to the same graph label y. \n\nc.\tThe designed method does not appear to leverage the unique characteristics of graph data. Moreover, all experiments are conducted on synthetic datasets, which raises concerns about the real-world applicability of this method. \n\nd.\tWhen generating synthetic datasets, assuming each edge is generated independently is overly simplistic. Why not employ more commonly used graph generation models? \n\ne.\tThe authors do not compare the performance of their method against existing graph structure learning methods.", "other_comments_or_suggestions": "NAN", "questions_for_authors": "What exactly is x in Equation (1)? Can it be understood as the node feature matrix of the input graph?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fKiDDdgENL", "reviewer": "Reviewer_qZGr", "summary": "Exploiting the structure of the problem of interest is often key to achieve good generalization with the trained model. For real world applications, it might be known that underlying relational information is shaping the observed data but this latent structure remains often hidden. Some previous works have proposed algorithms learning jointly the topology of the data and the model that leverage it to make predictions in the observational space. Over existing approaches do not quantify how close is the learned latent structure to the true one. \nThe authors of this submission propose to fill this gap and consider the latent topology as a random object. They provide an algorithm to jointly learn the distribution of the graph latent structure and the one of the observations that relies on it. Their algorithm is supported by a theoretical result showing that minimizing the population loss lead to a well calibrated latent distribution and optimal point prediction.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Claims and Evidence**\n\n**a**.\nFirst of all, we appreciate your constructive comments. We see your point, but the issue with the proposed approach is not that the graph structure provided in the real-world dataset is not a distribution - we agree that the ground-truth distribution can be a Dirac distribution. \nThe problem is that there are no guarantees that the provided graph structure is, or is close to, the underlying graph distribution that generated the data; many times the graph structure provided with the data is built using some heuristics (e.g., node similarity or physical distance between sensors).\nThis is one of the reasons why Graph Structure Learning emerged as a field. \nThe synthetic dataset - and, ultimately, our theoretical results - serves to overcome this limitation. Nonetheless, we perform the following additional experiment.\n\n**a (additional experiment)**.\nTo demonstrate that our method is able to learn sensible graph distributions in real-world settings, we train a neural network on air quality data in Beijing (Zheng, et al. 2013). The neural network consists of a GRU unit to process each time series, followed by a GNN with a learnable graph structure. At the following [link](https://anonymous.4open.science/r/learning_latent_graph_structures_and_their_uncertainty/README.md) we share the graph structure learned by the model with the lowest validation loss. As you can see, our approach learns a reasonable graph. \n\n**b**.\nWe agree with you, and indeed we ran that experiment in Section 6.3. Note that the first five rows in Table 2 consider either point-prediction losses or losses from the existing literature.\nAs shown, the calibration performance is worse than the proposed method. \n\n**Other Comments Or Suggestions**\n\nThank you for spotting those typos, we have fixed all of them.\n\n\n**Question For Authors**\n\n**1**.\nAt the moment, we have only partial results for generic multi-layer GNNs. \nOn the one hand, Corollary A.1 in Appendix A provides a meaningful insight for continuous GNNs: it states that even if a multi-layer GNN fails to be injective for most inputs, injectivity at a single point $\\bar x$ is sufficient for our results to apply. \nOn the other hand, following the proof of Proposition A.2, if $P_x^*$ is absolutely continuous, then $f(\\cdot, A)$ is injective almost surely. \nWhile we do not have a proof to offer yet, the two comments above are encouraging that a proof might be found.\n\n**2**.\nWe considered the multivariate Bernoulli distribution because it is general enough to model all graph distributions over independent edges; moreover, it is widely used in the Graph Structure Learning literature (e.g., Francheschi et al. 2019, Elinas et al. 2020, Sun et al. 2021, Cini et al. 2023). \nWe agree that considering other distributions, including input-dependent ones, is relevant. Considering the set of experiments already carried out (7 in the paper and 2 during the rebuttal) and that they already rigorously validate our claims, we leave this extension as future work. Finally we stress that the theoretical results apply to more general distributions. Thank you for your relevant comments. \n\n**References**\n\n- Zheng et al. \"U-air: When urban air quality inference meets big data.\", 2013.\n- Franceschi et al. \"Learning discrete structures for graph neural networks.\", 2019.\n- Elinas et al. \"Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.\", 2020.\n- Sun et al. \"Graph structure learning with variational information bottleneck.\", 2021.\n- Cini et al. \"Sparse graph learning from spatiotemporal time series.\", 2023.", "claims_and_evidence": "The theoretical results is validated on a synthetic dataset. The numerical results support the theoretical claims but I think some aspects could be improved:\n\n- I do not totally agree with the authors when they explain that for reall applications, we don't have access to the true distribution of the topology. I think the authors might have considered a case the graph is known and fixed (i.e. the distribution of the latent structure is a Dirac mass) and they could have used their algorithm assuming that the graph is not observed. As the number of observations increased, we expect the learned distribution of the latent graph to converge to this Dirac mass.\n\n- The authors prove Proposition 4.1 by giving a concrete example where calibration is not achieved by minimizing the point-prediction loss. However, this example is very specific and it would have been interesting to run the standard methods (optimizing the point prediction loss) on their synthetic dataset to see if the learned distribution of the latent structure is calibrated or not. This is important since the main contribution claimed by the authors is to propose a way to learn calibrated latent distribution. Therefore it would have been valuable to show that existing methods do not lead to good calibration in most cases.", "methods_and_evaluation_criteria": "Please see my comments in section \"Claims And Evidence\".", "theoretical_claims": "I checked the correctness of the proofs of the theoretical claims.", "experimental_designs_or_analyses": "Please see my comments in section \"Claims And Evidence\".", "relation_to_broader_scientific_literature": "The paper relates to the literature on Graph Structure Learning, and more generally to the problem of identifiability in the statistical literature.", "essential_references_not_discussed": "I am not expert in the field and thus other reviewers will have much more relevant comments for this section.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "Here are a few typos:\n\n- Theorem 5.2 contains some typos.\n\n- In Eq.(10), a probability distribution is missing under the last expectation.\n\n- Before section 6.1: \"additional specifics are detailed\"\n\n- In Section A.3 of the appendix, a $\\phi$ is missing when refering to $P^{\\theta,\\phi}_{y\\mid x}$ at several locations.  In the same section at line 664, I think $\\psi$ should not have a superscript $*$.\n\n- At line 732, R^N should be \\mathbb R^N.\n\n- At line 736: \"therfore\"", "questions_for_authors": "Let me first thank the authors for their work. I really appreciate the effort made to investigate quite deeply both the theoretical (such as in section A.4) and practical (such as section B with the variance reduction method) aspects of their approach.\n\n- Regarding Section A.4, the injectivity hypothesis is discussed for a graph neural network. The analysis shows the assumption is satisfies under mild condition for a very simple GNN. Could you comment on the injectivity assumption for more realistic GNN ? My intuition tells me that the injectivity will be less likely to hold for bigger/deeper network.\n\n- The synthetic dataset considered relies on a probabilistic model to generate graphs which looks a bit adhoc. It would be interesting to consider a more structure and realistic model where probability of connection between two nodes is given by k(x_i,x_j) for some kernel k where x_i and x_j are observed features associated to nodes i and j.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "None"}}]

Author rebuttal:

Meta-review: This paper studies graph structure learning and the associated uncertainty in the learning process, whose goal is to learn a calibrated latent graph distribution to reflect the uncertainty. This paper shows theoretically that, under certain conditions, minimizing output distribution loss yields calibration of latent variables and optimal pointwise prediction. The paper achieves it via MMD minimization and MC sampling is done for optimization.

Main concerns of the paper were mainly about motivation of this paper (no access to the distribution of graphs), theoretical analysis (injectivity, relationship between proposed method and graph structure, independent edge generation, certain proof techniques), application to real-world scenarios, discussions on existing works, and additional experiments about graph/label estimation. I've went through the manuscript, reviewers' concerns, and author-reviewer discussion. Overall, the concerns are adequately addressed with enough theoretical and empirical evidence in my opinion. The topic (calibrated GSL) is of importance to many real-world applications. I recommend acceptance.
Decision: Accept (poster)