Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
Discrete graph diffusion models, constrained by independent edge updates and exchangeability, are fundamentally limited to generating Erd\H{o}s--R\'enyi graphs in the large graph limit, hindering the recovery of node heterogeneity and higher-order structure. This work introduces a Latent Sociability Prior (LSP) and a joint diffusion process that co-evolves latent node sociability variables with graph structure, removing edge independence while maintaining exchangeability. The LSP effectively guides edge updates without complex encoders, enabling accurate graph distribution capture without node features.
Unconditional graph generation can now capture complex node heterogeneity and higher-order structures by jointly diffusing graph edges and latent node sociability, bypassing the Erd\H{o}s--R\'enyi graph limitation.
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\H{o}s--R\'enyi (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.