Research map / Graph learning / GNN architectures

Learning Latent Graph Structures and their Uncertainty

ICML 2025 · Graph learning › GNN architectures · approach: Graph structure learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that point-prediction losses do not calibrate the latent graph distribution in graph structure learning, proves that an output-distribution MMD loss yields both calibrated latent graphs and optimal predictions, and proposes a sampling-based score-function training method with control variates.

Problem

Graph structure learning typically learns latent graph topologies only through point-prediction losses, which do not guarantee that the learned latent graph distribution is calibrated or reflects the uncertainty of the relations.

Approach

Minimize a distributional discrepancy (MMD^2 or energy distance/CRPS) between the predicted and true output distributions conditioned on input; under injectivity conditions this simultaneously yields optimal point predictions and a calibrated latent adjacency distribution. Gradients w.r.t. the latent distribution parameters are estimated via score-function estimators with control-variate baselines

Key results

• Training with the proposed MMD distributional loss drives MAE on the latent edge probabilities below 0.01 (0.009 ± 0.001) while reaching near-optimal point-prediction MSE (0.159 ± 0.001).
• Point-prediction losses (MAE or MSE) yield latent-parameter MAE around 0.085, far worse than the proposed distributional losses, even when point predictions are near optimal.
• Variance reduction with control variates speeds up training by roughly 50%.

Measured effects reported in the paper

Surprising findings

• Minimizing point-prediction losses can achieve optimal point predictions while leaving the latent graph distribution miscalibrated (latent MAE ~0.085 vs ~0.01).
• Predictors trained with MSE point loss reach near-optimal MAE and MSE yet are statistically worse at calibration than the distributional losses.

Limitations

• The number of latent edge parameters grows quadratically with the number of nodes, making very large graphs costly to calibrate.
• Theoretical guarantees rely on assumptions (expressive model family, injectivity of f* at some inputs), which are only empirically relaxed.
• Experiments are primarily on a small synthetic dataset; real-world evaluation is only qualitative.

Experimental setup

Datasets: synthetic graph regression dataset (N=12 nodes, Bernoulli latent graph) Beijing air quality data

Benchmarks: synthetic graph regression dataset

Metrics: MAE on theta (latent calibration) MAE on y MSE on y MMD loss

Baselines: point-prediction MSE loss point-prediction MAE loss ELBO-based loss CRPS-based energy distance loss

Builds on: score-function gradient estimator maximum mean discrepancy graph structure learning

Closest papers by meaning

• On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.90)
• Graph Structure of Neural Networks (ICML 2020 · similarity 0.89)
• Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory (ICML 2025 · similarity 0.88)
• Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations (ICLR 2025 · similarity 0.88)
• Graph Neural Networks with a Distribution of Parametrized Graphs (ICML 2024 · similarity 0.88)
• How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.87)