Joint graph diffusion models improve generation by encoding node sociability
When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors
Machine LearningArtificial Intelligence
Summary
Many graph generation methods treat edges independently, resulting in unrealistic graphs that lack meaningful diversity among nodes and higher-level structure. The authors identify that this is due to using a simple random graph as a prior in the diffusion process. They propose a new approach that jointly models node sociability (how likely nodes are to connect) alongside graph structure, preserving node differences without complex encoders. Their method produces more realistic graphs on multiple datasets compared to prior approaches that ignore this joint modeling.
What this means in practice
- •For machine learning engineers: Generate more realistic synthetic graphs without using node features by incorporating latent node sociability into diffusion models.
- •For network analysts: Model complex network data more accurately by using joint diffusion processes that preserve node-level connectivity differences.
Authors
Adarsh Jamadandi, Nicolas Keriven, Aline Roumy
Abstract
Discrete graph diffusion models corrupt graph structure through independent edge updates with a Markovian noise model. Combined with the exchangeability requirement on the output distribution, the terminal prior is necessarily an Erdős--Rényi (E-R) random graph. This has a fundamental consequence for unconditional graph generation without node features: in the large graph limit, any GNN denoiser applied to an E-R graph approximately outputs an E-R graph, making effective denoising difficult. In practice, generated graphs fail to recover meaningful node heterogeneity and higher-order structure. Previous models introduced specialized node features to compensate, framing this as an expressivity problem, while the role of the prior remained unexamined. We instead address the root cause by introducing the Latent Sociability Prior (LSP) and a join} diffusion process that co-evolves latent node sociability variables and graph structure, removing edge independence while preserving exchangeability. Unlike existing latent graph diffusion methods, the sociability mechanism requires no complex encoder: its sole role is to guide edge updates and preserve node heterogeneity throughout the trajectory. We validate our approach on multiple graph generation datasets and show that the proposed framework more accurately captures graph distributions than baseline methods without node features.