Learning Latent Graph Structures and their Uncertainty

We appreciate the time and effort taken to provide thoughtful comments and additional references. Thank you for spotting the typos.

Motivation and Q1. Please allow us to clarify that our primary motivation for learning the latent graph distribution (task B) is not to improve the performance on the downstream task (task A). However, while task B is not necessary for solving task A, there are multiple reasons for addressing the two tasks jointly. Learning appropriate models of the data-generating process (calibrating the latent variable without compromising prediction accuracy) can provide valuable insights into the modeled environment. Uncertainty quantification improves explainability and interpretability, ultimately enabling more informed decision-making. Examples of applications are found in the study of infection and information spreading, and biological systems, e.g., see (Gomez Rodriguez et al 2013), (Lokhov 2016), (Deleu et al. 2022).

Contribution. There may be some misunderstanding here. The mentioned piece of contribution (i.e., "optimizing for task $X$ (...) does not inherently lead to solving subtask $Y$ (...).") is just the initial part of our contributions. We also would like to point out that we do not perceive task $Y$ (learning the distribution over the latent adjacency matrix) as a subtask, as it is not necessary for solving task $X$. Our main contribution is showing that it is possible to solve both tasks jointly (Theorem 5.2). In particular, we provide sufficient conditions that grant it and we show that these conditions can be mild for graphs and GNNs. Building on this, we developed a theoretically grounded and empirically validated learning approach (Sections 5 and 6).

Explicit connections between tasks $X$ and $Y$ are established and formulated as the four implications appearing in Theorem 5.2 and Proposition 4.1. We believe these are strong results that suggest that loss functions as defined in Equation 5 may, in general, be preferred.

Scope of experiments.

The choice of $N = 116$ in our experiments does not represent an upper limit of our method. What we meant to say with "Note that for extremely large graphs the ratio between the number of free parameters in $\theta$ and the size of the training set can become prohibitive." (line 448) is that the learning problem in general can get ill-posed as the ratio grows. Therefore it is a potential issue for any GSL method. The exploration of extreme scenarios of a huge number of nodes should be tackled from a general GSL perspective and, in our opinion, out of this paper's scope. So, while very interesting, we defer it to future research.

Additionally, our method is computationally more scalable compared to approaches relying on dense (non-strictly binary) adjacency matrices, as both the forward and backward computations - in our approach - can remain sparse. Please, refer to lines 341-345 and Cini et al. (2023) where it has been empirically validated. Finally, we comment that increasing the feature dimension $d$ provides more training signal, thus it is expected to facilitate learning.

Q1. See above.

Q2. $P_x^*$ is the data distribution of the inputs $x$ as produced by the data-generating process (data collection). There is no particular restriction on $x$, which could be modeled as a continuous, discrete, or even mixed random variable. In this paper, we focused on independent $A$ and $x$ to make the empirical validation and visualization more practical. Nonetheless, modeling $A\sim P_{A|x}$ is indeed possible, e.g., by expressing the distribution parameters $\theta$ of current $P^\theta_A$ in Eq. 2 as input-dependent: $\theta=g_\vartheta(x)$ with $\vartheta$ a new set of learnable parameters.

Q3. To our knowledge, no previous work was designed to solve this joint task. As we have proven, existing methods can succeed or fail depending on the loss they consider. For instance, the mentioned work by Kazi et al. (2022) adopts a type of loss function for which calibration is not guaranteed. In summary, this paper focuses on training losses and shows that output distribution losses (Equation 6) are more appropriate than point-prediction losses (Equation 4), regardless of the considered model.

Q4. Please note that the injectivity we refer to in Theorem 5.2 concerns the function $A\mapsto f^*(x, A)$, rather than the usual $x\mapsto f^*(x, A)$. Indeed, while the latter is often not injective, the former can be. In Appendix A.4, we demonstrate that the injectivity assumption can hold robustly. Furthermore, as noted in lines 236–242, the function does not need to be injective for all input points $x$ if $f^*$ is continuous, but only for one point.

We appreciate your feedback. Please allow us to address your questions and comments.

Baselines. Please note that the focus of this paper is mainly on the type of loss function to optimize, which appears to be fundamental for successfully solving both tasks. Therefore, existing methods can succeed or fail depending on the loss they consider. Besides, none of them were designed to solve this joint task, to our knowledge. What we show is that output distribution losses (Equation 6) are more appropriate than point-prediction losses (Equation 4), and this holds regardless of the considered model as long as Assumption 3.1 is met. Finally, although we show that using the MMD and a score function gradient estimator is an appropriate choice, we are not claiming its superiority over other methods optimizing an output distribution loss.

Benchmarks. Unfortunately, to our knowledge, no dataset provides the ground-truth latent distribution of the graph structure (i.e., $P_A^*$). In the absence of such information, we have no way of evaluating the quality of the learned $P_A^\theta$. For this reason, we constructed a synthetic dataset to validate our claims and approach.

Uncertainty analysis. It seems there may have been a misunderstanding here. Our primary goal is not to model the uncertainty of the output $y$ by calibrating the latent variable $A$. Instead, we aim at calibrating the latent variable $A$ itself. The problem we are addressing is inherently more complex both to solve and evaluate; this is due to the absence of ground truth information about the unknown variable $A$ we intend to learn in real-world scenarios. Our theoretical results address this challenge by providing learning guarantees.

Thank you for the response. In my understanding, this paper proposes a method that primarily focuses on better capturing underlying graph structures while predicting results related to the graph. Although I cannot ensure the practical utility of this method in the real world tasks, the choice of this method may be necessary (compared to existing approaches) for explainability and interpretability, such as understanding underlying biological interactions for determining the output. Thus, I have decided to increase my score from 5 to 6.

Thank you for your review and for acknowledging the novelty and relevance of our work. We now address the raised comments.

Motivation. The main goal of this paper is to provide mathematical guarantees that make the learning process more reliable. Given that latent variables are typically not observed in real-world scenarios (see Real Data comment below), the provided theoretical support copes with the absence of a sound empirical validation framework. Learning appropriate models of the data-generating process can provide valuable insights into the modeled environment, other than accurate predictions of its outcomes. Consider, for instance, the social interactions example. Providing accurate estimates of latent relations governing an epidemic can help health organizations design more effective intervention strategies. Other examples of controllability of systems of interacting entities can be found in sensor networks and cyber-physical systems. Interpretability and explainability are further aspects where uncertainty estimates are valuable. We hope to have addressed your comment and we will expand this discussion in the final version of the paper.

Related Works. Thank you for pointing us to that very recent work. We are reviewing it and the references therein to strengthen our related work section.

Real Data. This is a relevant question. Evaluating the calibration of the latent variables on real data is challenging due to the latent nature of the graph topology -- $P^*_A$ is unknown and no samples from it are observed. This is the reason why (a) we have been developing theoretical guarantees to support the application of the methods to real data, and (b) we have based the empirical validation on synthetic data.

Minor Comments. Thank you for the suggestion.

We appreciate your feedback. We have carefully considered your points and addressed them below.

W1 and W2. Please, note that in Section 4 adjacency matrix $A$ is implicit in the computation of model output $y$ according to Equation 2. In particular, the distribution $P_{y|x}^{\psi,\theta}$ of $y$ is the push-forward distribution of $P_A^{\theta}$ through $f^{\psi}$. Some results indeed extend beyond GNNs and GSL. We perceive this generality as a strength rather than a weakness. Nonetheless, some results remain specific to the graph domain. In particular, the hypothesis $P_{x \sim P_x^*}(I) > 0$ used in Theorem 5.2 is studied for GNNs and shown to be easily satisfied. Please refer to Proposition A.2 and Lemma A.3 in Appendix A.4. In the related proofs, the assumption that $A$ is the (binary) adjacency matrix of a graph is what allows to claim the existence of discrete object $\delta\in\lbrace-1,0,1\rbrace^{1\times N}$ and rely on the finite collection of hyperplanes $I_{\bar g}^C$. We clarify this point in the final version of the paper.

W3. We acknowledge the importance of performing analysis on real-world applications. However, we are not aware of any dataset that allows us to do it. The reason is the following. In order to assess the calibration performance of models, it is necessary to compare the learned graph distribution $P_A^\theta$ with the ground-truth latent (thus, unknown) distribution $P_A^*$. To our knowledge, no real-world datasets provide such ground truth. Without such knowledge of the latent random graphs that generated the data, we could only assess point-prediction performance. Focusing on the single task of point prediction, empirical results show comparable performance, yet they do not validate the joint learning problem addressed in this paper and, therefore, they were omitted from the paper. For this reason, we had to design synthetic experiments in order to validate the paper's theoretical claims and the practical relevance of the devised method.

Q1. Thank you for bringing up this point. First of all, we comment that as the KL and JS divergences satisfy Assumption 5.1 the theorem's conclusion applies to them as well. From a practical perspective, they are valid alternatives as long as they can be computed. However, as they rely on the explicit evaluation of the likelihood of $y$, they are sometimes impractical to compute (Mohamed et al. 2016). Therefore we opted for likelihood-free methods based on the MMD which only requires samples. Finally, note that the MMD is already a broad family of integral probability metrics parametrized by its kernel and the energy distances provide other feasible choices (Székely et al. 2013). We will expand the discussion in the paper. Thank you.

References

Mohamed, Shakir, and Balaji Lakshminarayanan. "Learning in implicit generative models." arXiv preprint arXiv:1610.03483 (2016).

Székely, Gábor J., and Maria L. Rizzo. "Energy statistics: A class of statistics based on distances." Journal of statistical planning and inference 143.8 (2013): 1249-1272.

Thank you for your review. We addressed the raised points and questions below and hope that all confusions are resolved now.

W1. Part of our results can indeed be applied to more general latent variable models and we perceive this broader coverage as a strength rather than a weakness. Nonetheless, as we are interested in GSL, we derived results specifically for adjacency matrices $A$. As correctly noted, we explicitly use the graph structure in Proposition A.2 and Lemma A.3. In the related proofs, the assumption that $A$ is the (binary) adjacency matrix of a graph is what allows us to claim the existence of discrete object $\delta\in \lbrace-1,0,1\rbrace^{1\times N}$ and rely on the finite collection of hyperplanes $I_{\bar g}^C$; this would not have been necessarily possible for other latent variables.

W2. There may be some misunderstanding here. Please allow us to clarify the following two points.

• We are not considering "continuous" adjacency matrices ($A\in[0,1]^{N\times N}$ or $\mathbb R^{N\times N}$). The adjacency matrices are binary: $A\in\lbrace0,1\rbrace^{N\times N}$. Perhaps, the confusion arises from Figures 3, 4, and 5, showing the values of $\theta$, representing the distribution parameters;

• The considered parametrization as a set of Bernoulli distributions allows to cover any distribution over binary adjacency matrices of independent edges; in this sense, the formulation as a set of Bernoulli distributions is maximally expressive and does not impose limitations. Nonetheless, more structured graph distributions could be considered as well (e.g., Niepert et al. 2021), although the setup of independent edges is commonly treated in the GSL literature (e.g., Francheschi et al. 2019, Elinas et al. 2020, Sun et al. 2021, Cini et al. 2023). Finally, we stress that the theoretical results apply to any graph distribution.

W3. This work addresses graph structure learning and, therefore, we decided to focus on graphs; please, refer to W1. We feel that dealing with images and audio signals goes well beyond the scope of a GSL paper. We will consider generalizing the method to additional domains in future work, thank you for the suggestion.

Q1 As mentioned in W2, this is not uncommon, and other distributions can be considered as well, including the ones you suggested. Moreover, most of our theoretical results apply to general graph distributions.

Q2 We reported results for $P(X)$ (denoted as $P_x^*$ in the paper) being a multidimensional normal distribution. However, we stress that there is no particular restriction on the choice of $P(X)$ and virtually any distribution should work. Please also refer to lines 236-238, where we elaborate further.

References

Niepert, Mathias, Pasquale Minervini, and Luca Franceschi. "Implicit MLE: backpropagating through discrete exponential family distributions." Advances in Neural Information Processing Systems 34 (2021): 14567-14579.

Franceschi, Luca, et al. "Learning discrete structures for graph neural networks." International conference on machine learning. PMLR, 2019.

Elinas, Pantelis, Edwin V. Bonilla, and Louis Tiao. "Variational inference for graph convolutional networks in the absence of graph data and adversarial settings." Advances in neural information processing systems 33 (2020): 18648-18660.

Sun, Qingyun, et al. "Graph structure learning with variational information bottleneck." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 4. 2022.

Cini, Andrea, Daniele Zambon, and Cesare Alippi. "Sparse graph learning from spatiotemporal time series." Journal of Machine Learning Research 24.242 (2023): 1-36.