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).