Implicit Neural Representations for Variational Problems on Graphons

AI summary

Overview

Research area: Machine learning for mathematical discovery, specifically neural optimisation over graphons — the limit objects of dense graph sequences — with applications to extremal graph theory and the large deviation theory of dense random graphs. Published in stat.ML (arXiv:2610.32147v1, 23 Oct 2026).

Technical level: Advanced. The method itself is a fairly compact deep-learning pipeline, but the problem statements, baselines and evaluation criteria come from graph-limit theory, extremal combinatorics and large-deviation theory; the paper assumes familiarity with homomorphism densities, Turán-type problems and the Chatterjee–Varadhan variational principle.

Scope (one sentence): The paper proposes an implicit-neural-representation framework for constrained optimisation problems over graphons, and reports that it recovers classical optima, produces candidate optima for open instances, improves on a best-known reference construction for the triangle upper-tail problem, and has led to new theorems.

What This Paper Is About

Many questions about very large graphs become continuous optimisation problems once the graph is replaced by its limit object, a graphon: a symmetric measurable function from the unit square to [0,1] that specifies edge probabilities. Two important sources of such problems are extremal graph theory (e.g. minimise the density of a pattern while holding the edge density fixed) and the large deviation theory of Erdős–Rényi random graphs (find the graphon closest in KL divergence to a constant graphon that explains an atypically high or low pattern density).

Solving these problems analytically is hard and often open — the clique cases are settled, but many small patterns remain unresolved. The paper's goal is to attack them numerically: represent the unknown graphon by a neural network, enforce the constraint exactly on sampled data, and descend on the objective, so that candidate optima and structural conjectures can be produced automatically rather than by hand.

Key Contributions

1. A graphon parameterisation built for step-like solutions. A residual MLP that re-injects a sinusoidal encoding of the input at every layer, with an encoding scale that grows with depth (the paper uses s(ℓ) = 2^(ℓ−1)). Symmetry of the graphon is guaranteed by feeding (min(x₁,x₂), max(x₁,x₂)) to the network, and the [0,1] range by a sigmoid output.

2. An embedded constraint solver with implicit differentiation. Rather than a penalty term, the single scalar density constraint is enforced by solving for a distinguished scalar bias c such that the empirical density equals the target. The solution exists and is unique because the empirical density is continuous and strictly increasing in c, tending to 0 and 1 at the extremes; it is found by a clipped Newton method and differentiated through in closed form (Lemma 3.1).

3. Symmetry-aware Monte Carlo estimators for homomorphism densities. An estimator averaged over a set of vertex permutations of the pattern graph, which is unbiased for any choice of that set, typically lowers variance for the same number of independent tuples, and allows caching of network evaluations — reducing the count from N·|S|·e(H) to N·C·e(H) for some C ≤ |S|.

4. Evidence that the framework is a useful exploratory tool for mathematics. It rediscovers classical optima, generates candidates for open instances (including a previously unreported family of extremal structures), improves on the Lubetzky–Zhao construction for the triangle upper tail, and the structures it found led to new theorems stated in Appendix D.

Main Findings

• Clique densities are recovered to within 0.1%. For K₃ density minimisation under t(K₂,W) = p, the method reaches 0.22232803 against the optimum 0.22222222 at p = 2/3 (+0.05%), 0.48010290 against 0.48 at p = 4/5 (+0.02%), 0.10299835 against 0.10298638 at p = 4/7 (+0.01%), 0.17362659 against 0.17361111 at p = 5/8 (+0.01%), 0.31370832 against 0.31363508 at p = 5/7 (+0.02%), and 0.00008130 at p = 1/2 where the optimum is 0.

• Larger cliques match theory closely. For t(K_k,W) = 1 − 1/k: k = 4 gives (0.09403727, 0.09411154) against an optimum of 0.09375; k = 5 gives (0.03868024, 0.03872081) against 0.0384; k = 6 gives (0.01565511, 0.01568170) against 0.01543210 (bootstrap intervals in parentheses).

• Odd cycles track known or conjectured optima. For C₅ the gaps range from +0.01% (p = 4/5, 0.32644549 vs 0.3264) to +0.06% (p = 4/7, 0.04590020 vs 0.04587149). For C₇ they range from +0.01% (p = 4/5, 0.20967621 vs 0.209664) to +0.09% (p = 4/7, 0.01715017 vs 0.01713510).

• A structural nuance at p = 5/7 for K₃. The learnt graphon does not match the standard W_p construction, but its bipartite middle-block structure matches the characterisation of all optimal graphons in Pikhurko and Razborov (2017).

• A previously unreported family of extremal structures. A systematic sweep over 117 non-bipartite graphs with v(H) ≤ 6 uncovered, for a six-vertex graph H₆ (six vertices, nine edges), a family of extremal structures that do not match the complete k-partite pattern of classical examples. Its densities beat both the k-partite construction and the constant graphon: 0.02476414 vs 0.03292181 and 0.02601229 at p = 2/3; 0.07218717 vs 0.07617188 and 0.07508469 at p = 3/4; 0.12985603 vs 0.13056 and 0.13421773 at p = 4/5.

• Improvement over the best-known reference construction in the triangle upper tail. For K₃, relative entropy h_q(W) is lower than the Lubetzky–Zhao tripartite construction W_LZ across all six reported (q,r) settings, and stays above the paper's own lower bound: 0.464208 vs 0.556057 (lower bound 0.460284) at (0.05, 0.4); 0.727881 vs 0.830366 (0.725284) at (0.05, 0.5); 1.051203 vs 1.144945 (1.049172) at (0.05, 0.6); 0.309109 vs 0.311239 (0.306561) at (0.10, 0.4); 0.506060 vs 0.510826 (0.504311) at (0.10, 0.5); 0.747694 vs 0.750684 (0.746006) at (0.10, 0.6).

• New candidates across pattern graphs and tails. Candidate optimal graphons are reported for four pattern graphs in the upper-tail regime (K₃, C₄, C₅, K₁,₃, illustrated at q = 0.1, r = 0.5) and for K₃ in the lower-tail regime.

• New theorems driven by the discovered structures (Appendix D). For the first problem family, the balanced complete k-partite graphon minimises the density of every odd cycle at p = 1 − 1/k for every k ≥ 3, and of every connected chordal graph whose maximal cliques have a common size r ≥ 3 at p = 1 − 1/k for every k ≥ r. For the second, close to the boundary of the region where the constant graphon is optimal, the upper-tail problem for regular graphs has a unique optimal graphon, which is bipodal.

• Ablation and protocol. The same architecture, solver and training loop are used throughout; only the enforced constraint and the estimated objective change. Results are reported as the best of 8 runs over (φ, η) ∈ {GELU, sin} × {10⁻³, 5×10⁻⁴, 10⁻⁴, 5×10⁻⁵}, with cosine annealing; values are described as candidate upper bounds, and the 95% bootstrap intervals (2²⁸ samples, used where discretisation into an M×M matrix is infeasible) quantify Monte Carlo error, not run-to-run variability.

Methodology in Plain English

The unknown graphon is a two-input neural network: feed it a pair of points from the unit square and it outputs an edge probability. Two design choices make it behave like the step functions that optima in this literature tend to be. First, the network keeps re-injecting sine waves of the raw input at every layer, at increasing frequencies in deeper layers, which gives late layers the high-frequency tools needed to draw sharp boundaries while early layers hold the coarse structure. Second, the inputs are sorted (smaller first, larger second), which forces the output to be symmetric with no extra effort.

The constraint is the delicate part. Both problem families impose exactly one scalar condition — a fixed edge density, or a fixed density of the pattern graph. Instead of adding a soft penalty, the network has one distinguished scalar bias held out of the ordinary parameter set. At each training step the framework solves, on the sampled batch, for the value of that scalar that makes the empirical density hit the target exactly. This has a unique solution and is found by a clipped Newton iteration. To train, one then needs to know how that solved value changes as the network weights change; the paper derives this in closed form via implicit differentiation, which avoids backpropagating through every Newton step and is far cheaper in memory. The same recipe works for any pattern graph, because raising the bias raises every edge probability and so the density stays monotone.

Objectives and constraints are integrals over the unit square, estimated by Monte Carlo. The estimator for a pattern graph averages over several relabellings of the pattern's vertices, reusing the same random tuples. This is unbiased for any set of relabellings, tends to reduce variance, and lets the same network evaluations be cached across relabellings, cutting the number of forward passes. Training samples are redrawn every iteration to avoid overfitting to a particular draw, and the learning rate follows a cosine-annealing schedule that alternates between coarse structure discovery and sharp boundary refinement.

For the large-deviation family, only two things change: the edge-density solver becomes a solver for the pattern-graph density targeting r^(e(H)), and the objective becomes a Monte Carlo estimate of the integrated KL divergence from the constant graphon ≣ q. Reported densities come either from discretising the learnt graphon into an M×M weighted matrix or from 2²⁸ samples with a 95% bootstrap interval; learnt graphons are shown as Viridis heatmaps.

Why This Matters

The paper is a case study in using neural optimisation as a discovery tool for hard continuous problems in pure mathematics, complementing rigorous lower-bound machinery such as flag algebras. The frameworks produce candidate upper bounds and concrete minimisers, and the paper explicitly positions them as generating structural conjectures that can be inspected, refined, or subsequently certified — a role already demonstrated by the new theorems the discovered structures inspired. The improvement over the Lubetzky–Zhao construction for the triangle upper tail is the strongest single signal that the approach can beat human-designed reference constructions rather than merely reproduce them.

The paper does not report deployed applications or industrial experiments; the following are areas where the underlying objects and problems arise rather than claims made by the authors.

• Network science and community structure: graphons are the limit objects of stochastic block models and dense graph limits, so constrained graphon optimisation relates to reasoning about large-scale community structure.
• Information theory and rare-event modelling: the large-deviation objective is an integrated KL divergence, mirroring maximum-entropy modelling, which is relevant to assessing how likely extreme density patterns are in random graph models.
• Extremal design and constraint satisfaction: results on the maximum edge density of triangle-free or pattern-free structures bear on how dense a system can be while avoiding a forbidden local configuration.
• Scientific computing with hard constraints: the embedded-solver-plus-implicit-differentiation pattern generalises to any differentiable model with a single scalar equality constraint, a common shape in physics-informed and constrained generative modelling.

Industry relevance: the transferable techniques — enforcing a hard scalar constraint through a solved bias rather than a penalty, differentiating through that solve in closed form, and exploiting symmetry to cut Monte Carlo variance and network evaluations — are directly applicable to constrained neural optimisation in engineering design, resource allocation and any setting where a learned function must hit an exact aggregate target.

Future Directions

• Certifying the candidates. The paper frames its outputs as candidate upper bounds and conjectures; the natural next step is to formalise the new candidates — particularly the six-vertex extremal family and the lower-tail K₃ structures — into theorems, and to close the visible gap to the reported lower bounds in the K₃ upper-tail table.
• Resolving the remaining cycle cases. C₅ is known only at p = 1 − 1/k and C₇ minimisation is open; the framework's candidates at intermediate p values (e.g. p = 5/7 for K₃, where the learnt solution differed from W_p yet matched the Pikhurko–Razborov characterisation) suggest structural questions worth pursuing.
• Scaling to larger patterns. The permutation-based estimator and caching scheme already enable work on larger graphs (the Petersen graph is examined in Appendix G); pushing to patterns where density estimation becomes the bottleneck is the obvious limit to test.
• Beyond a single constraint. Both problem families carry exactly one scalar equality constraint, which is what makes the embedded solver viable; extending the approach to multiple simultaneous constraints is an open methodological question the paper's design leaves untouched.

Target Audience

Researchers at the intersection of machine learning and combinatorics — particularly those working on neural methods for mathematical discovery, graph-limit theory, extremal graph theory, or the large deviation theory of random graphs. It will also interest practitioners of constrained neural optimisation who want a concrete, well-motivated example of replacing penalty terms with a differentiated embedded solver, and mathematically literate readers who want to see what a learned representation can contribute to problems where hand-derived constructions have been the norm. Readers without background in homomorphism densities and graphons will find the problem statements hard going, even though the optimisation machinery itself is not complicated.

Authors’ abstract

We propose a neural exploratory framework for variational problems over graphons, i.e., symmetric measurable functions $[0,1]^2 \to [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.