We propose a neural exploratory framework for variational problems over graphons, i.e., symmetric measurable functions [0,1]2→[0,1], that arise as limits of dense graph sequences. Such problems are central to two parts of the mathematical literature: extremal graph theory, which studies graph parameter optimisation under given restrictions, often for those graphs with a large number of vertices, and the large deviation theory of dense random graphs, which characterises the structure of rare events through constrained graphon optimisation. We represent graphons by implicit neural networks and optimise graphon objectives by gradient descent. Our design combines three ingredients: a multi-scale sinusoidal residual architecture biased toward sharp, step-like graphons; an embedded solver that enforces a single empirical density constraint and is differentiated by implicit differentiation; and symmetry-aware Monte Carlo estimators. On generalised Turán problems that previously required substantial human effort, our framework rediscovers known optimal graphons without human intervention. Applied to open instances, it produces candidate optima, including a previously unreported family of extremal structures. Applied to the variational problems from the large deviation theory of Erdős--Rényi random graphs, the framework produces new candidate optimal graphons across both upper- and lower-tail regimes for multiple pattern graphs; for the case of the triangle graph and the upper-tail regime, these candidates improve upon the best-known reference construction of Lubetzky and Zhao. The structures found by our framework have also led to new theorems on the optimal graphons for both families of problems.
Figures & tables
Figure 1Figure 2Figure 3Figure 4Figure 5
Figure 6: Learnt graphons for upper-tail variational problems with q=0.1,r=0.5 for H=K3,C4,C5,K1,3 (left to right).
(q,r)
(0.05,0.4)
(0.05,0.5)
(0.05,0.6)
(0.10,0.4)
(0.10,0.5)
(0.10,0.6)
hq(WLZ)
0.556057
0.830366
1.144945
0.311239
0.510826
0.750684
hq(Wours)
0.464208
0.727881
1.051203
0.309109
0.506060
0.747694
Lower bound
0.460284
0.725284
1.049172
0.306561
0.504311
0.746006
Table 6: Relative-entropy hq(W) at our learnt graphon ( Wours ) and at the tripartite construction WLZ of Lubetzky and Zhao (2015) , for (P2) with H=K3 on (q,r)∈{0.05,0.1}×{0.4,0.5,0.6} , together with a lower bound on the optimum ( Appendix G ). Lower is better.
Appendix figures & tables16 assets
Supplementary material from the paper’s appendix.
Appendix
p
Ours (Estimated)
Hand-crafted
1/2
(0.00000000,0.00000000)
0
2/3
(0.00184293,0.00184619)
0.0020322
4/5
(0.03412074,0.03413641)
0.0340869
4/7
(0.00006195,0.00006209)
0.0001736
5/8
(0.00054270,0.00054310)
0.0007531
5/7
(0.00571939,0.00572465)
0.0059452
Appendix
Table 7: Homomorphism densities of the Petersen graph in graphons under the edge-density constraint t(K2,W)=p , found by our method and by a hand-crafted construction.
Figure 7: Graphons found for the Petersen graph density minimisation under the edge-density constraint t(K2,W)=p .
q=0.05
q=0.10
r
0.4
0.5
0.6
0.4
0.5
0.6
hq(WLZ) , H=C4
0.556057
0.830366
1.144945
0.311239
0.510826
0.750684
hq(Wours) , H=C4
0.464162
0.727364
1.050351
0.309184
0.506141
0.747042
hq(WLZ) , H=C5
0.556057
0.830366
1.144945
0.311239
0.510826
0.750684
hq(Wours) , H=C5
0.465644
0.727618
1.052023
0.308858
0.506122
0.746845
Lower bound, H∈{C4,C5}
0.460284
0.725284
1.049172
0.306561
0.504311
0.746006
Appendix
Table 8: Relative-entropy hq(W) at our learnt graphon ( Wours ) and, for H∈{C4,C5} , at the tripartite construction WLZ of Lubetzky and Zhao [2015] , for (P2) on (q,r)∈{0.05,0.1}×{0.4,0.5,0.6} . We also report a lower bound on the optimum for H∈{C4,C5} , and Wours for H=K1,3 (no corresponding WLZ construction is available in the literature for this case). Lower is better.
r=0.05
r=0.10
q
0.7
0.8
0.9
0.7
0.8
0.9
hq(Wours)
0.600882
0.591680
0.804127
0.796391
1.151161
1.144472
Appendix
Table 9: Relative-entropy hq(W) at our learnt graphon ( Wours ) for (P2) with H=K3 on (q,r)∈{0.7,0.8,0.9}×{0.05,0.1} . Lower is better.
Figure 8: Found graphon for upper tail variational problems for K3 , for q=0.05 (top) and q=0.1 (bottom) and r=0.4,0.5,0.6 (left to right).
Figure 9: Found graphon for lower tail variational problems for K3 , for r=0.05 (top) and r=0.1 (bottom) and q=0.7,0.8,0.9 (left to right).
Figure 10: Found graphon for upper tail variational problems for C4 , for q=0.05 (top) and q=0.1 (bottom) and r=0.4,0.5,0.6 (left to right).
Figure 11: Found graphon for upper tail variational problems for C5 , for q=0.05 (top) and q=0.1 (bottom) and r=0.4,0.5,0.6 (left to right).
Figure 12: Found graphon for upper tail variational problems for K1,3 , for q=0.05 (top) and q=0.1 (bottom) and r=0.4,0.5,0.6 (left to right).
Figure 13: Hand-crafted graphons W1,W2,W3,W4 (left to right) with edge density t(K2,W)=0.7 .
t(K3,W)
sin
GELU
Ours
0.435712
0.436066
ResNet
0.435724
0.436405
Constant-scale s
0.435689
0.436347
Regulariser
0.437085
0.437323
Constant LR (low)
0.437544
0.442451
Appendix
Table 10: K3 densities in graphons found by our method, ablations, and non-neural baselines for K3 density minimisation under t(K2,W)=7/9 , with sinusoidal features or with GELU features in the per-layer encoding and activation. The optimum is 98/225≈0.435556 .
Figure 14: Graphons found by our method and its ablations, for K3 density minimisation under the constraint t(K2,W)=7/9 .
Figure 15: Graphons obtained by applying the output layer to the hidden state gθ(ℓ) after layer ℓ of a trained network, for K3 density minimisation under t(K2,W)=7/9 , with the scalar bias c solved separately for each ℓ so that t(K2,W)=7/9 ; ℓ=1,…,6 from left to right, and ℓ=6 is the learnt graphon.
Figure 16: Graphons found by non-neural baselines, fixed-block SBM, trainable-block SBM with 5 / 64 blocks, decision tree, and tree ensemble (left to right), for K3 density minimisation under the constraint t(K2,W)=7/9 .
Figure 17: (Left) Triangle density as a function of p for the conditional network, compared to the known optimum. (Right) Absolute error of the conditional network’s triangle density relative to the known optimum.
Figure 18: Learnt graphons for the conditional network at p∈{1/2,4/7,3/5,5/8,2/3} (left to right).
Graphs play a crucial role in many applications, ranging from drug discovery to social network modeling and astronomy. Generative models for graphs have substantially advanced in recent years, but we identify relatively simple scenarios where state-of-the-art models struggle to converge within a standard compute budget, or exhibit prohibitively slow generation times. We propose a generative architecture that achieves quality competitive with state-of-the-art models and is orders of magnitude faster at generation. Our approach is inspired by the Aldous-Hoover theorem, a classic representation theorem that characterizes any probability distribution of graphs that is invariant to permutations of node indices or exchangeable. This theorem establishes that three ingredients suffice: a graph-level latent variable, a set of exchangeable node-specific latent variables, and a so-called graphon function that maps graph- and node-level variables to the probability of an edge between any node pair. Given a training set of graphs, our exchangeable Variational Graph AutoEncoder (xVGAE) learns an approximation to their underlying graphons, as well as graph- and node-level latent variables. We show that our xVGAE encodes latent representations that correlate with graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.
Daniele Micheletti, Federica Zoe Ricci, Erik B. Sudderth
University of California, Irvine · Swarthmore College
We consider the problem of estimating graph limits, known as graphons, from observations of sequences of sparse finite graphs. In this paper we show a simple method that can shed light on a subset of sparse graphs. The method involves mapping the original graphs to their line graphs. We show that graphs satisfying a particular property, which we call the square-degree property are sparse, but give rise to dense line graphs. This enables the use of results on graph limits of dense graphs to derive convergence. In particular, star graphs satisfy the square-degree property resulting in dense line graphs and non-zero graphons of line graphs. We demonstrate empirically that we can distinguish different numbers of stars (which are sparse) by the graphons of their corresponding line graphs. Whereas in the original graphs, the different number of stars all converge to the zero graphon due to sparsity. Similarly, superlinear preferential attachment graphs give rise to dense line graphs almost surely. In contrast, dense graphs, including Erdos-Renyi graphs make the line graphs sparse, resulting in the zero graphon.
Graph Transformers produce, for each attention head, a dense n×n matrix of learned pairwise interactions. We ask a fundamental question: do these attention-induced graphs converge to a stable limit object as n grows, or does the learned interaction pattern remain unstructured and size-dependent? We answer this using dense graph limit theory, treating each attention matrix as a finite sample from an underlying kernel---an attention graphon---and studying concentration around this limit under the cut-distance. We derive a worst-case variance bound requiring no assumptions on the graphon, and a sharper regularity-aware bound based on nonparametric estimation theory. To operationalize the theory, we propose a canonicalize-then-block-average pipeline for estimating dataset-level attention graphons, and a variance-based diagnostic for testing whether attention admits a stable continuum description. Experiments across multiple graph benchmarks show that learned attention stabilizes to dataset-specific graphon structure on several datasets; that empirical cut-distance and cut-norm variance decreases with n consistent with our bounds; and that attention graphons transfer to larger graph sizes with error decreasing in n.
Caio F. Deberaldini Netto, Moshe Eliasof, Luana Ruiz
Johns Hopkins University Baltimore, MD · University of Cambridge Cambridge, UK