From Uniform to Learned Graph Priors: Diffusion for Structure Discovery

Qi Shao, Hao Guo, Jiawen Chen, Duxin Chen, Wenwu YuarXiv 2026 · DOI · arXiv

TL;DR

Neural Relational Inference (NRI) models often struggle with vague, poorly calibrated graph predictions because they assume edges are completely independent. This paper introduces Diff-prior, a plug-and-play diffusion-based prior that acts as a logit-level denoising calibrator, enforcing global graph consistency and significantly sharpening structure discovery.

What Problem Does This Paper Address?

When trying to understand complex systems—such as multi-agent systems, physical particles, or gene regulation networks—we usually only observe their trajectories over time. Neural Relational Inference (NRI) aims to figure out the underlying "who influences whom" graph structure from this data.

However, standard NRI methods rely on a major simplification: they assume a factorized prior distribution over the graph edges, meaning they treat every potential edge as completely independent. In practice, this usually defaults to a uniform distribution. This mismatch with real-world topology (which exhibits global properties like sparsity, modularity, and specific motifs) leaves the model highly uncertain. As a result, standard NRI produces diffuse, ambiguous edge posteriors and suffers from high calibration errors.

Methods

Instead of using diffusion to generate graphs from scratch, the authors propose Diff-prior, which operates directly on the continuous edge-type logits produced by the encoder before discretization and sampling.

  1. Continuous Latent Space: The encoder's discrete edge logits are mapped to a continuous Gaussianized variational posterior ($Z_0$).
  2. Forward Noising: A standard diffusion noising process corrupts these logits over $S$ steps.
  3. Denoising Calibrator: A lightweight time-conditional MLP denoiser learns to predict the noise, effectively capturing complex cross-edge dependencies without requiring explicit, computationally heavy pairwise modeling.
  4. Residual Refinement: During inference, a single-step residual update nudges the encoder's raw logits toward a globally coherent topological structure.
  5. Joint Optimization: To avoid the mathematical intractability of standard score-matching under joint training, the authors derive a novel joint-KL upper bound (Theorem 5.1) that allows end-to-end training of the encoder, decoder, and diffusion prior simultaneously.
Diff-prior framework overview and training pipeline

Datasets

The framework was evaluated on the standard StructInfer benchmark suite, which includes 15-node configurations across 5 distinct network topologies:

  • VN (Vascular Network)
  • FW (Food Web)
  • BN (Boolean Network)
  • GRN (Gene Regulatory Network)
  • CRNA (CircRNA-miRNA Network)

These networks were simulated under two types of system dynamics: Springs (SP) (linear physical interactions) and Netsims (NS) (complex, non-linear blood oxygenation level-dependent time-series simulations). The authors also validated their method on a real-world dataset, IRMA (a synthetic yeast gene network).

Key Insights and Ideas

  • Prior Integration as Calibration: The core "aha" moment is that a structural prior shouldn't just be a passive penalty term or a standalone generator; it works best as an active calibrator that cleans up the noisy, independent guesses of an encoder.
  • Logit-Level Interface: Operating on continuous logits before Gumbel-Softmax discretization avoids the information loss and brittleness associated with correcting discrete graphs post-hoc.
  • The Uniform Prior Trap: When system dynamics are highly complex (like Netsims), the data alone cannot uniquely constrain the graph. Under a uniform prior, the model defaults to maximum uncertainty. Diff-prior provides the global structural bias needed to break these ties decisively.

Key Results

  • Substantial Performance Boosts: Diff-prior was plugged into three different backbone architectures (NRI, ACD, MPM) and consistently improved structure discovery (AUROC). The gains were massive on the complex Netsims dynamics, increasing average AUROC by up to +6.43% for the MPM backbone.
  • Sharper, More Decisive Posteriors: It drastically reduced both Shannon entropy and Expected Calibration Error (ECE). For instance, on the Netsims Vascular Network (NS_VN), edge posterior entropy dropped from 0.0281 to 0.0011, and ECE plummeted from 0.0226 to 0.0007.
  • Robustness: Diff-prior maintained its edge under challenging conditions, including added observation noise, truncated trajectories, and missing data points.
Confidence distributions showing sharper edge posteriors with Diff-prior

Limitations and Future Work

  • Scope of Evaluation: The current experiments primarily focus on the StructInfer baseline and binary edge inference tasks.
  • Scalability to Massive Graphs: While the MLP denoiser is lightweight, scaling to extremely large graphs with thousands of nodes remains an open challenge due to the quadratic growth ($N^2$) of the edge logit tensor.
  • Future Directions: The authors suggest extending Diff-prior to handle multi-relational graphs more deeply and incorporating more fine-grained reliability and uncertainty analysis.

Summary updated

Abstract

Neural relational inference (NRI) methods discover interaction graphs from trajectories through variational reasoning on discrete potential edges. However, these methods typically rely on oversimplified, factorized graph priors. Such priors, typically nearing uniform distributions, treat edges as independent entities. This systemic misalignment does not match the real-world systems and yields diffuse and indecisive edge posteriors limiting the reliability of structural discovery. To address this, we propose \textit{Diff-prior}, a diffusion-parameterized adaptive prior used to calibrate latent graph distribution rather than generate graphs. Our core insight is to reframe prior integration as a learnable denoising-style calibration that organizes scattered, uncertain edge posteriors into a more reliable overall structure which can be trained by the diffusion model. Diff-prior learns an adaptive structure prior that performs structured calibration on the edge posteriors during inference, guiding it towards a distribution closer to the underlying structure. The diff-prior operates before structural sampling and acts as a denoising calibrator directly on the encoder edge distribution, which provides a generic training paradigm over structured variables. Experiments on standard benchmarks validated our framework, and the results indicate that Diff-prior improves the performance of structure inference and generates more decisive edge posteriors across multiple NRI-family architectures. The code is available on https://github.com/Hardy158118/Diffprior.
BibTeX
@misc{shao2026from,
  author = {Qi Shao and Hao Guo and Jiawen Chen and Duxin Chen and Wenwu Yu},
  title = {{From Uniform to Learned Graph Priors: Diffusion for Structure Discovery}},
  year = {2026},
  eprint = {2606.11831},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.11831},
}

Loading related content...

Figure