Learning Latent Graph Structures and their Uncertainty

Claims and Evidence

a. First 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. The 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). This is one of the reasons why Graph Structure Learning emerged as a field. The synthetic dataset - and, ultimately, our theoretical results - serves to overcome this limitation. Nonetheless, we perform the following additional experiment.

a (additional experiment). To 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 we share the graph structure learned by the model with the lowest validation loss. As you can see, our approach learns a reasonable graph.

b. We 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. As shown, the calibration performance is worse than the proposed method.

Other Comments Or Suggestions

Thank you for spotting those typos, we have fixed all of them.

Question For Authors

1. At the moment, we have only partial results for generic multi-layer GNNs. On 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. On the other hand, following the proof of Proposition A.2, if $P_x^*$ is absolutely continuous, then $f(\cdot, A)$ is injective almost surely. While we do not have a proof to offer yet, the two comments above are encouraging that a proof might be found.

2. We 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). We 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.

References

• Zheng et al. "U-air: When urban air quality inference meets big data.", 2013.
• Franceschi et al. "Learning discrete structures for graph neural networks.", 2019.
• Elinas et al. "Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.", 2020.
• Sun et al. "Graph structure learning with variational information bottleneck.", 2021.
• Cini et al. "Sparse graph learning from spatiotemporal time series.", 2023.

Wa. There might be some misunderstanding here, please allow us to clarify that the assumption is indeed satisfiable. Both 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$. $\Delta$ is a dissimilarity measure between distributions over the same set $\mathcal Y$ for both its arguments (i.e., $P_1,P_2$). Assumption 5.1 relates to $\Delta$, and it is known to be satisfied, e.g., by $f$-divergences and some integral probability metrics

Wb. Please 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. The 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. According 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.

Wc. Please 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. Secondly, 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. Nonetheless, 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.

Wd. Parameterizing 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. Furthermore, we stress that the theoretical results are not restricted to Bernoulli distributions.

We. Please 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.

Question

Yes, $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.

References

• Franceschi et al. "Learning discrete structures for graph neural networks.", ICML 2019
• Elinas et al. "Variational inference for graph convolutional networks in the absence of graph data and adversarial settings.", NeurIPS 2020
• Sun et al. "Graph structure learning with variational information bottleneck.", AAAI 2021
• Cini et al. "Sparse graph learning from spatiotemporal time series.", JMLR 2023

W1. We appreciate your suggestion. If the paper is accepted, we will use part of the camera-ready additional page to improve the presentation.

C1. Yes, 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. Section 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. Finally, 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.

C2. Thank 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. We will revise the paper to prevent any possible confusion.

C3. Thank 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.

C4. Thank you for carefully reading the appendices. The more the two terms in the expectation are independent the more the approximation is accurate. The main reason to accept this approximation is that it enables an easy estimation of the optimal $\beta$.

C5. Yes, we are considering $A \not = A'$ in that line. We fixed the typo, thank you. Regarding 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.

W1. Part 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).

W2 W3, W4 and W5. Our paper highlights the critical role of the loss function to effectively achieve calibration; this specific formulation and set of assumptions serve this goal. Some assumptions can be relaxed, broadening the applicability of our findings. However, we believe that our developments lay a solid foundation enabling further developments. We expect - and have validated with different experiments (refer to Sections 6.1 and 6.2) - that the theory remains valid beyond certain assumptions. In the following points, we provide additional evidence to support that our results can be generalized to address your concerns further:

• W2) We 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$. Accordingly, 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). The 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. | Max pert. $\Psi^*$ | MAE on $\theta$ | Max AE on $\theta$ | | --- | --- | --- | | 0 | 0.009 $\pm$ 0.001 | 0.06 $\pm$ 0.01 | | 0.1 | 0.008 $\pm$ 0.001 | 0.05 $\pm$ 0.01 | | 0.2 | 0.012 $\pm$ 0.001 | 0.06 $\pm$ 0.01 | | 0.3 | 0.019 $\pm$ 0.003 | 0.09 $\pm$ 0.01 | | 0.4 | 0.032 $\pm$ 0.003 | 0.13 $\pm$ 0.01 |

• W3) It is indeed possible to parametrize the graph distribution making it input dependent. One 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$.

• W4) Please see our response to Reviewer qZGr's Question 1.

• W5) In 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. Please 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*$).

W6. We are not sure we have fully understood your proposed solution. In 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? Nonetheless, 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.

W7. Respectfully, 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.

References

• Kipf et al. "Neural relational inference for interacting systems.", ICML 2018
• Maddison et al.. "The concrete distribution: A continuous relaxation of discrete random variables.", ICLR 2017