Exploring Variational Problems over Graphons with a Tailored Neural Architecture and LLMs

<학부생을 위한 ɛ 강연> Exploring Variational Problems over Graphons with…

107
강연자 양홍석
소속 고등과학원

In this talk, I will describe our neural framework for exploring variational problems over graphons—symmetric measurable functions from [0,1]^2 to [0,1] that serve as limit objects for dense graph sequences. These problems arise in two areas of mathematics: extremal graph theory, which studies the optimisation of graph parameters under constraints, often in the limit as the number of vertices grows; and large-deviation theory for dense random graphs, which uses constrained graphon optimisation to study the probabilities and typical structures of rare events. We represent graphons with implicit neural networks and optimise graphon objectives by gradient descent. Our approach combines three ingredients: a multiscale sinusoidal residual architecture designed to capture sharp, step-like graphons; an embedded solver that enforces a single empirical density constraint, with gradients computed by implicit differentiation; and symmetry-aware Monte Carlo estimators. For generalised Turán problems whose known solutions required substantial human effort, our framework recovers known optimal graphons without human intervention. Applied to open instances, it produces candidate optima, including a previously unreported family of candidate extremal structures. This led us to a Goodman-type conjecture for odd-cycle densities, which we subsequently proved and formalised in Lean with the help of LLMs. For variational problems arising in large-deviation theory for Erdős–Rényi random graphs, the framework produces new candidate optimal graphons in both upper- and lower-tail regimes for several pattern graphs. In the upper-tail regime, these candidates achieve better objective values than the best-known benchmark construction due to Lubetzky and Zhao.

Now

현재 <학부생을 위한 ɛ 강연> Exploring Variational Problems over Graphons with a Tailored Neural Architecture and LLMs

강연자 : 양홍석 | 소속 : 고등과학원

In this talk, I will describe our neural framework for exploring variational problems over graphons—symmetric measurable functions from [0,1]^2 to [0,1] that serve as limit objects for dense graph sequences. These problems arise in two areas of mathematics: extremal graph theory, which studies the optimisation of graph parameters under constraints, often in the limit as the number of vertices grows; and large-deviation theory for dense random graphs, which uses constrained graphon optimisation to study the probabilities and typical structures of rare events. We represent graphons with implicit neural networks and optimise graphon objectives by gradient descent. Our approach combines three ingredients: a multiscale sinusoidal residual architecture designed to capture sharp, step-like graphons; an embedded solver that enforces a single empirical density constraint, with gradients computed by implicit differentiation; and symmetry-aware Monte Carlo estimators. For generalised Turán problems whose known solutions required substantial human effort, our framework recovers known optimal graphons without human intervention. Applied to open instances, it produces candidate optima, including a previously unreported family of candidate extremal structures. This led us to a Goodman-type conjecture for odd-cycle densities, which we subsequently proved and formalised in Lean with the help of LLMs. For variational problems arising in large-deviation theory for Erdős–Rényi random graphs, the framework produces new candidate optimal graphons in both upper- and lower-tail regimes for several pattern graphs. In the upper-tail regime, these candidates achieve better objective values than the best-known benchmark construction due to Lubetzky and Zhao.