PaperlayerView exact revision on arXiv

Source-linked AI summary

Implicit Neural Representations for Variational Problems on Graphons

Taeyoung Kim, Jineon Baek, Joonkyung Lee, Hongseok Yang

arXiv:2610.32147v1stat.MLcs.AIcs.LGmath.CO

TL;DR

The paper targets graphon optimisation problems arising in extremal graph theory and dense-random-graph large deviations. It uses an empirical constraint solver with implicit differentiation to find candidate optima, including a new extremal family and candidates that improve on a reference construction. The resulting structures have also led to new theorems.

  • Problem

    Extremal graph theory and dense-random-graph large deviations both require constrained optimisation over graphons, while optimal structures remain unknown in some regimes.

    Source: §1 · pp. 1–2, §2 · p. 4

  • Method

    The framework estimates graphon objectives and constraints from samples and embeds a solver for the empirical density constraint, differentiating the solver output implicitly.

    Source: §3 · pp. 5–6

  • Results

    The method finds candidates across both problem families, including a previously unreported extremal family and triangle upper-tail candidates that improve on Lubetzky and Zhao [2015].

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The structures found by the framework have led to new theorems on optimal graphons, including results for odd cycles and regular-graph upper-tail problems.

    Source: §1 · p. 3

    For triangle deviations, it remains unresolved when the deviation localises or spreads and how minimisers vary across q and r.

    Source: §2 · p. 4

Abstract

from arXiv · show

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\'an 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\H{o}s--R\'enyi 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.

1 Introduction

The paper brings neural mathematical discovery to continuous optimisation over graphons, motivated by extremal graph theory and dense-random-graph large deviations. It develops a framework for these problems and reports known and new candidate optima, including structures that led to new theorems.

1 Introduction

  • The framework extends machine-learning approaches to mathematical discovery from theorem proving, autoformalisation, and combinatorial construction search to continuous graphon optimisation.The motivating applications are extremal graph theory and large deviations of dense random graphs.Source: §1 · p. 1
  • Graphon optimisation links two problem families: extremal minimisation of homomorphism density at fixed edge density and large-deviation optimisation of relative entropy at fixed homomorphism density.The objectives and constraints are graphon integrals, and known or conjectured optima are typically step-like.Source: §1 · p. 2
  • The method represents graphons with neural networks and uses a multi-scale sinusoidal residual architecture to bias the model toward sharp, step-like solutions.An embedded numerical solver enforces an empirical scalar density constraint, with gradients computed through implicit differentiation; symmetry-aware Monte Carlo estimates graphon integrals.Source: §1 · p. 2
  • The framework rediscovers known generalised Turán optima, proposes candidates for open instances, and uncovers a previously unreported family of extremal structures for a six-vertex graph.For triangle upper-tail problems, its candidates consistently improve on the reference construction of Lubetzky and Zhao [2015]; the discovered structures also led to new theorems.Source: §1 · pp. 2–3
  • For every odd cycle, the stated optimum occurs at p = 1 − 1/k for k ≥ 3; near the constant-graphon boundary, regular-graph upper-tail problems have a unique bipodal optimum.The paper also gives the corresponding result for connected chordal graphs whose maximal cliques share size r ≥ 3, at p = 1 − 1/k for k ≥ r.Source: §1 · p. 3

2 Background

The background introduces graphons as limits of dense graphs and explains how homomorphism densities express extremal graph problems. It then describes the two optimisation families and the open questions motivating the large-deviation application.

2 Background

  • Homomorphism density is a size-normalised pattern statistic that supports comparable extremal objectives across graph sizes and is central to dense graph limit theory.The background frames constrained density minimisation as minimising t(H, W) at fixed edge density p, equivalent to the corresponding asymptotic finite-graph problem.Source: §2 · pp. 3–4
  • A graphon is a symmetric measurable function from [0, 1]^2 to [0, 1] that represents a limit object for dense graph sequences.Discrete graph structure is reflected in graphons, including bipartite graphs as two-block graphons and Erdős–Rényi graphs as constant graphons.Source: §2 · p. 3
  • For constrained density minimisation, the optimum is zero below the Turán threshold; above it, the problem is much harder and is completely solved only for cliques.For C5, the minimiser is known only at p = 1 − 1/k for positive integer k.Source: §2 · p. 4
  • Dense-graph large deviations characterise both the exponential rate of atypical homomorphism densities and the typical conditioned graph through graphon optimisation of averaged KL divergence.The minimiser describes the graphon closest in KL divergence to the base constant graphon that explains the observed excess or deficit.Source: §2 · p. 4
  • Even for triangles, it remains unclear when deviations localise or spread, and what the minimisers look like across base probabilities q and target levels r.This is an unresolved scope boundary for both upper- and lower-tail variational problems.Source: §2 · p. 4

3 Implicit neural representations of graphons

The framework represents graphons with a neural network and optimises its parameters using gradient-based training. Its architecture and estimators address step-like solutions, scalar density constraints, and graphon integrals.

Architecture

  • A residual MLP injects increasingly high-frequency sinusoidal encodings at each layer, biasing the network toward sharp boundaries and step-like graphons.The architecture also uses symmetry-enforcing min and max operations so its output represents a graphon.Source: §3 · p. 5

Constraint solver

  • A scalar bias is solved numerically in the forward pass to satisfy an empirical density constraint, with gradients through the solver computed by implicit differentiation.For edge density, the empirical constraint estimator is monotone in the bias, and the text states its solution exists and is unique.Source: §3 · pp. 5–6

Homomorphism-density estimation

  • Homomorphism densities are estimated by Monte Carlo sampling, with permutation-based reuse of sampled tuples trading off estimator variance against computational cost.The estimator is unbiased for any permutation set; caching repeated network evaluations can reduce computation.Source: §3 · p. 6

Training algorithm

  • Training resamples Monte Carlo inputs each iteration, solves the empirical constraint, and updates network parameters using the estimated objective gradient.Implicit differentiation supplies the gradient of the solver output without storing every intermediate iterate of an unrolled Newton method.Source: §3 · p. 6

Large-deviation problems

  • For large-deviation problems, the same constrained loop replaces the edge-density constraint with a pattern-density constraint and the objective with relative entropy.The entropy objective is estimated over a fresh batch of pairs, and an analogous implicit-differentiation formula handles the constraint.Source: §3 · p. 7

4 Experimental results

Experiments apply the same framework to constrained homomorphism-density minimisation and large-deviation variational problems, testing known cases and open instances. The results include recovered known structures, candidate optima for open problems, and a candidate family of extremal graphons.

Experimental setup

  • Reported objective values are best-found candidate upper bounds, and bootstrap intervals quantify Monte Carlo estimation error rather than variability across runs.The experiments report the lowest-objective run across eight activation and learning-rate configurations.Source: §4 · p. 8

Clique densities (H = Kn)

  • For clique densities at p = 1 − 1/k, the method recovers complete k-partite graphons, with triangle densities within 0.1% of theoretical optima and the same structure recovered for k = 4, 5, 6.For p = 4/7 and 5/8, the learnt graphons capture the core structure of a known optimum; at p = 5/7, they match the characterised bipartite middle-block structure.Source: §4 · p. 9

Open problems: C5 and C7

  • For C5, all tested densities match known or conjectured optima within 0.1%; for C7, tested values match the authors’ conjectured optima within 0.1%.The C5 and C7 graphons show diagonal patterns away from p = 1 − 1/k, while C7 at p = 5/7 has a block-like pattern.Source: Figure 3 · p. 8, Figure 4 · p. 8, §4 · p. 9

Exhaustive study over small graphs

  • The sweep covers 117 non-bipartite graphs on at most six vertices at six edge densities, using three random seeds and flag-algebra lower bounds to assess candidate optimality.The density choices probe breakpoints and an interior segment of the minimum-density curve.Source: §4 · p. 10

Constrained homomorphism-density minimisation

  • In 72.6% of 702 (H, p) instances, the best learnt graphon is within 1% of the flag-algebra lower bound; in 20.8%, a graphon with H-density more than 1% smaller is known.Neither condition holds for the remaining 6.6%.Source: §4 · p. 10
  • The method identifies an H6 candidate minimiser that is neither complete k-partite nor constant, with edge probabilities appearing to depend on circular distance.The systematic sweep also finds convex, concave, and neither-convex-nor-concave minimum curves across the tested graphs.Source: §4 · p. 10

Variational problem from large deviation theory

  • For upper-tail K3 problems, the learnt graphons consistently have lower relative entropy than the Lubetzky–Zhao tripartite construction, indicating that construction is suboptimal in the tested regimes.Across tested upper- and lower-tail problems, the method finds two-block structures; lower-tail solutions are nearly bipartite.Source: §4 · p. 10

Ablation study, baselines, and multi-task variant

  • Replacing sinusoidal features, the constraint solver, or cosine annealing with specified alternatives increases triangle density, while four non-neural baselines reach higher triangle densities than the method.A FiLM-conditioned multi-task variant trained over p ∈ [1/2, 2/3] demonstrates that the architecture extends to multiple K3 instances.Source: §4 · p. 11

A Related work

Prior work applies implicit neural representations to graphon learning and other mathematical search problems, while this paper directly optimises graphons for constrained asymptotic extremal problems. The authors present their method as complementary to rigorous flag-algebra bounds and distinct from fixed-size discrete search.

Graphon learning

  • Unlike graphon learning, which estimates an unknown graphon from observed graphs and may lose sharp details, this method searches directly for constrained graphon optima without a graph dataset or target graphon.Applying graphon learning would first require near-optimal finite graphs, itself a hard discrete optimisation problem.Source: A Related work · p. 16

Flag algebras

  • Flag algebras provide rigorous lower bounds and certificates, whereas this method supplies candidate upper bounds and interpretable candidate minimisers that can inform conjectures.The authors describe the approaches as complementary, not replacements.Source: A Related work · p. 16

Discrete optimisation

  • Discrete search methods can optimise non-differentiable finite-graph objectives, while this method targets asymptotic dense-graph problems and often yields more interpretable structures.The cited discrete approaches include local search, reinforcement learning, the deep cross entropy method, and PatternBoost.Source: A Related work · p. 16

Implicit neural representations

  • Compared with related implicit-neural work on the Hadwiger–Nelson problem, this method targets constrained graphon optimisation and incorporates biases for step-like solutions, explicit constraints, and variance reduction.The related work reports human post-processing of its learned colouring to construct new examples.Source: A Related work · p. 17

B Societal impacts and limitations

The work presents interpretable candidate optima for graphon variational problems and identifies their use in conjecture generation and discovery. Its scope and computational costs are bounded by graphon applicability, lack of rigorous optimality guarantees, and the expense and potential error of density estimation.

Societal impacts

  • Structured, interpretable candidate optima can support mathematical conjecture generation and discovery across extremal graph theory and dense-random-graph large deviations.The authors foresee no major negative societal impacts.Source: B Societal impacts and limitations · p. 17

Limitations

  • The method is tailored to graphon optimisation and does not apply to sparse-graph combinatorial problems, where the graphon limit is degenerate.It also provides no rigorous guarantees of optimality, so the authors recommend pairing it with rigorous lower-bound techniques such as flag algebras.Source: B Societal impacts and limitations · p. 17
  • Density evaluation can be expensive for large motifs: grid discretisation becomes infeasible for motifs such as the Petersen graph, while Monte Carlo estimates can have large relative error when motif density is very small.The method estimates homomorphism densities by discretisation or Monte Carlo.Source: B Societal impacts and limitations · p. 17

C Background on graphons, odd cycles, and large deviations

Graphons provide a continuous representation of limits of large graphs, making asymptotic optimisation over graphs into optimisation over functions. The background also reviews conjectured odd-cycle structures and the graphon variational problems governing large deviations.

Graphons as limits of graphs

  • Graphons represent large-graph limits, and continuity and compactness let asymptotic optimisation over graphs be formulated as optimisation over graphons.Homomorphism densities are compatible with cut-distance convergence, and the graphon optimum is attained for the stated continuous or lower-semicontinuous objectives.Source: C Background on graphons, odd cycles,… · pp. 17–18

Conjectured optima for odd cycles

  • The reviewed odd-cycle conjecture uses a partition into k−1 equal sets and two further sets, with a tunable cross-block value chosen to meet the edge-density constraint.The construction is extended to longer odd cycles by replacing the cycle-density expression with its corresponding expression.Source: C Background on graphons, odd cycles,… · pp. 18–19

Large deviations

  • For dense random graphs, constrained events are dominated by graphons satisfying the constraint with minimum relative entropy.Conditioned on such an event, the random graph is close to these minimisers.Source: C Background on graphons, odd cycles,… · p. 20

Optimal solutions of large deviation problems

  • For regular pattern graphs, the constant graphon is uniquely optimal above the curve qc(r), while below it some graphon has lower objective value.The former and latter regions are called the replica-symmetric and symmetry-breaking phases, respectively.Source: C Background on graphons, odd cycles,… · p. 20

D Proven results on the learnt structures

The learnt graphons motivate theorems identifying optimal structures for odd cycles and certain chordal graphs, and establishing unique bipodal optima in a neighbourhood of a large-deviation boundary. The theorems also formalise several structures found in the experiments.

Odd cycles

  • For every odd m ≥ 3 and edge density p ≥ 2/3, the theorem gives an optimality result for odd-cycle density; at p = 1 − 1/k, Wk minimises every odd-cycle density.The learnt C7 graphons at p ∈ {2/3, 4/5} recover the complete k-partite structure and are optimal.Source: D Proven results on the learnt… · p. 20

Connected chordal graphs

  • For connected chordal H with equal maximal-clique size r ≥ 3, the theorem identifies Wk as a minimiser under its stated density constraint for k ≥ r.The result applies to 16 studied graphs other than cliques and settles 48 instances; its proof is formalised in Lean 4.Source: D Proven results on the learnt… · pp. 20–21

Regular graphs and large deviations

  • Near (qc(r0), r0) on the stated q < qc(r) side, the upper-tail problem for a d-regular graph has a unique nonconstant minimiser up to relabelling, and that minimiser is bipodal.The learnt upper-tail graphons for K3, C4, and C5, which are 2-regular, have this two-block form.Source: D Proven results on the learnt… · p. 21

E Properties of the density estimator and the implicit gradient

The section establishes that the sampled homomorphism-density estimator is unbiased and describes the behaviour of the implicit gradient used to enforce empirical density constraints. The empirical gradient is exact for the sample constraint, though it is generally biased for the population constraint and consistent as sample size grows.

Estimator properties

  • The homomorphism-density estimator is unbiased for t(H, fθ[c]) for any choice of permutation set S.Using multiple permutations reuses sampled tuples and can lower variance, while S controls variance and computational cost.Source: E Properties of the density estimator… · p. 21

Implicit gradient consistency

  • The implicit gradient is exact for the empirical constraint but generally biased for the population-constraint offset gradient, to which it converges as sample size increases.The offset itself converges almost surely to the population-constraint solution under the stated continuity assumptions.Source: E Properties of the density estimator… · p. 22
  • Applying the implicit function theorem to the population constraint yields the stated formula for the gradient of its offset.The derivative with respect to the offset is positive under the conditions described in the proof.Source: E Properties of the density estimator… · p. 23

F Details of experiments

The experiments use a six-layer, width-256 network with increasing input-encoding scales, Monte Carlo sampling, and graph-dependent permutation sets. Solver clipping addresses unstable Newton updates, while motif size and very small true densities constrain computational and estimation performance.

Experimental setup

  • The experiments use width 256 and depth 6, with increasing input-encoding scale; neither sine nor GELU showed a consistent advantage.Training used 20,000 epochs and four tested learning rates; all experiments ran on one RTX A5000 GPU, taking 30 minutes for a triangle to a few hours for the Petersen graph.Source: F Details of experiments · pp. 24–25

Sampling and computation

  • Graph-dependent permutation sets reuse sampled vertex tuples, and training sample counts ranged from 2^12 to 2^16, with an effective 2^16 samples for large graphs.Evaluation used 2^28 samples.Source: F Details of experiments · pp. 24–25
  • Larger motifs reduce feasible batch size under fixed memory, and relative error is harder to control when the true density is extremely small.For bounded integrands, the Monte Carlo estimator retains its O(N^-1/2) absolute-error rate.Source: F Details of experiments · p. 25

Constraint solver

  • Clipped Newton updates address instability caused by small sigmoid derivatives and very small denominators when graphon values approach 0 or 1.The clipping range begins from bounds on the solution and decreases over iterations.Source: F Details of experiments · p. 25

G Additional experimental results

The additional experiments examine Petersen-graph density minimisation and report further results for large-deviation variational problems, including comparisons with available Lubetzky–Zhao constructions and lower bounds.

Petersen graph density minimisation

  • For Petersen-graph density minimisation, the authors report no known results or conjectured optimum and compare their learned graphons with a Razborov-motivated hand-crafted construction.They evaluate edge densities p ∈ {1/2, 2/3, 4/5, 4/7, 5/8, 5/7}.Source: G Additional experimental results · p. 26, Figure 7 · p. 27

Large-deviation variational problems

  • For upper-tail problems on C4 and C5, the comparison includes the learned relative entropy, the Lubetzky–Zhao construction where available, and a lower bound on the optimum.The K1,3 results report learned solutions only because no corresponding Lubetzky–Zhao construction is available.Source: G Additional experimental results · p. 26
  • For lower-tail K3, the authors report only their learnt solutions; for regular K3, C4, and C5, Lubetzky and Zhao [2015] prove an upper-tail optimum lower bound, with the same reported value for all three graphs because the bound is determined by d.Source: G Additional experimental results · p. 27

H Details of hand-crafted graphons

The appendix describes hand-crafted graphons for selected edge densities and presents learned graphons and relative-entropy results for upper- and lower-tail problems.

Hand-crafted graphons

  • For 1 − 1/k < p < 1 − 1/(k + 1), the construction partitions [0, 1] into k + 1 groups and chooses the first k groups’ common size x to satisfy the edge-density constraint.Solving the stated quadratic gives two roots; the root defining W1 yields the optimum for K3 density minimisation, while the other defines W2.Source: H Details of hand-crafted graphons · p. 27
  • The appendix also describes a graphon formed by deleting edges from the complete (k + 1)-partite construction and identifies the constant graphon W(x1, x2) = p as another construction.The four hand-crafted graphons are visualised at p = 0.7.Source: H Details of hand-crafted graphons · pp. 27, 30

Large-deviation graphons

Relative-entropy results

  • Table 8 reports relative entropy for learned graphons and, for C4 and C5, the Lubetzky–Zhao construction and a lower bound; lower values are better.For K1,3, the table reports learned solutions without a corresponding Lubetzky–Zhao construction.Source: Table 8 · p. 30
  • Table 9 reports relative entropy for learned K3 graphons in lower-tail problems across q ∈ {0.7, 0.8, 0.9} and r ∈ {0.05, 0.1}; lower values are better.Source: Table 9 · p. 30

I Ablation study, robustness, non-neural baselines, and multi-task variant

Ablations, robustness checks, non-neural comparisons, and a conditional-network experiment probe the framework’s components and behavior across tasks. The experiments report stable recovery in many runs, difficulties for several baselines, and accurate shared training across a grid of K3 densities.

Ablation study

  • With sinusoidal features, every tested variant reaches a lower K3 density than with GELU; ablations also expose failures in sharp boundaries, constraint details, and training stability.The ten-run GELU-feature comparison has mean 0.435661, below 0.436066 for the method with GELU features; the optimum is 98/225 ≈ 0.435556.Source: I Ablation study, robustness,… · pp. 30, 32, Table 10 · p. 32

Multi-scale encoding

  • Increasing encoding scales give early layers coarse block geometry and later layers higher-frequency boundary refinement; visualisations progress from a smooth gradient to the learned five-block structure.The per-layer visualisation solves the scalar bias separately to maintain t(K2, W) = 7/9.Source: I Ablation study, robustness,… · pp. 32–33

Robustness

  • Across five repeated instances, reported objectives include 0.435661 for K3 at p = 7/9 versus the optimum 98/225 ≈ 0.435556, and 0.727215 for upper-tail K3 versus the lower bound 0.725284.The reported C5, C7, and H6 objectives are also compared with their stated conjectured optima or reference graphons.Source: I Ablation study, robustness,… · p. 33
  • Across seeds, all ten upper-tail runs recover the K3 two-block structure, all ten C5 runs recover a two-block structure, and nine nonconstant C7 runs recover the reported structure.Across 702 exhaustive-study instances, the three seeds have median relative standard deviation 1.4 × 10^-4 and differ by more than 1% in 5.8% of instances.Source: I Ablation study, robustness,… · p. 34
  • Sensitivity checks find C5 objectives within 1.6 × 10^-4 across three permutation-set sizes; for K3 at p = 7/9, scalar-bias constraint violations have standard deviation 1.1 × 10^-3.The maximum violation is 3.4 × 10^-3, and discretisation refinement changes t(K3, W) by 9.7 × 10^-5.Source: I Ablation study, robustness,… · p. 34

Non-neural baselines

  • On triangle-density minimisation, trainable-block SBMs collapse toward constant graphons, while the fixed-block SBM and tree methods produce other structures; the neural method adjusts region values and boundaries jointly.The baselines can approximately represent the optimum, but moving block boundaries is difficult for fixed-block and tree-based methods.Source: I Ablation study, robustness,… · p. 34, Figure 16 · p. 34

Multi-task variant

  • A single FiLM-conditioned K3 network trained across 100 densities from 1/2 to 2/3 achieves maximum absolute error 2.09 × 10^-4 and average absolute error 3.12 × 10^-5.The authors describe this single-graph experiment as indicating that shared training can reduce per-instance burden; fuller multi-task and multi-graph treatment is a natural extension.Source: I Ablation study, robustness,… · pp. 34–35, Figure 17 · p. 35, Figure 18 · p. 35

Related papers

Loading 2610.32147v1…