Implicit Neural Representations for Variational Problems on Graphons¶
会议: NeurIPS 2026
arXiv: 2610.32147
代码: https://github.com/mekty2012/INR4GraphonVariationalProblem
领域: 其他
关键词: 隐式神经表示, 图元变分问题, 极值图论, 大偏差理论, 隐式微分
一句话总结¶
提出基于隐式神经表示与多尺度正弦残差架构的图元变分优化框架，内嵌隐式微分约束求解器与对称性感知的蒙特卡洛估计，在极值图论广义 Turán 问题与稠密随机图大偏差变分问题中自动重现并发现了全新的极值图元结构。
研究背景与动机¶
极值图论与稠密随机图的大偏差理论在现代离散数学与概率论中占据核心地位，两者的核心问题往往归结为稠密图序列极限对象——图元（Graphon，即定义在单位正方形 \([0,1]^2\) 上的对称可测函数）上的连续变分优化。在极值图论中，经典的广义 Turán 问题试图在给定边密度约束下极小化特定子图的同态密度；在大偏差理论中，Chatterjee-Varadhan 框架将随机图出现异常子图密度的罕见事件概率转化为以图元为变量的相对熵泛函极小化问题。长期以来，这类变分问题的求解高度依赖数学家的人工构造、Flag Algebras（旗代数）半定规划下界松弛，或者在固定节点规模下的离散组合搜索与局部启发式算法。
然而，现存探索方法面临着双重困境。一方面，Flag Algebras 计算复杂度随子图规模呈超指数级暴涨，且本质上只能给出理论下界，无法直接生成直观、平滑或具有几何特征的候选极值图元；另一方面，AlphaZero、强化学习或 PatternBoost 等离散搜索仅在有限节点数 \(n\) 下运作，面对高度对称的离散图难以直接提炼出极限尺度下的连续几何结构。若直接采用深度学习中的常规隐式神经表示（INR，如标准 MLP）对图元参数化，又会遭遇三大核心矛盾：其一，极值图元往往是具有陡峭边界的分块阶跃函数（Step Functions），而标准神经网络具有强烈的低频光滑归纳偏置；其二，边密度或同态密度等严格等式约束难以通过简单的松弛惩罚项精确满足；其三，同态密度积分的高维蒙特卡洛估计方差极大且计算开销高昂。
本文的切入角度是：将图元变分优化直接表征为一个端到端连续可微系统的参数搜索，通过网络归纳偏置定向引导阶跃几何结构的形成，并将严格的标量约束内嵌到前向与反向传播中。核心 idea：构建具有层进高频正弦编码的多尺度残差架构以捕捉尖锐阶跃几何，在前向传播中内嵌基于牛顿法的经验约束求解器并利用隐式微分精确反传梯度，结合对称性感知蒙特卡洛估计实现极值图元的端到端神经变分发现。
方法详解¶
整体框架¶
该方法将图元 \(W: [0,1]^2 \to [0,1]\) 参数化为带有标量动态偏置 \(c\) 的隐式神经网络 \(f_\theta[c](x_1, x_2)\)。为了保证图元内在的对称性，输入坐标首先经过无序对排序 \(\mathbf{x} = (\min(x_1, x_2), \max(x_1, x_2))\) 处理。在每一次变分优化迭代中，系统首先从 \([0,1]\) 均匀采样若干节点坐标构造训练元组集合；接着，内嵌约束求解器以网络深层表征与目标密度标量为输入，通过裁剪牛顿迭代精确求解满足经验约束的唯一标量偏置 \(c_\theta\)；随后，系统计算同态密度或相对熵目标函数的对称性感知蒙特卡洛估计值；最后，利用隐式函数定理推导出的隐式梯度公式，绕过对求解器迭代轨迹的反向传播，端到端更新网络参数 \(\theta\)。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["坐标采样<br/>均匀分布采样点集 D 与边集 E"] --> B["多尺度正弦残差编码<br/>分层递增频率注入与特征累加"]
B --> C["内嵌单约束牛顿求解器<br/>求解使经验密度等于目标值的偏置 c*"]
C --> D["对称性感知同态估计<br/>复用点对并利用自同构置换约减方差"]
D --> E["隐式微分梯度反传<br/>利用隐式定理消除展开迭代开销并更新参数"]关键设计¶
1. 多尺度正弦残差架构：面向尖锐阶跃图元的频域归纳偏置 标准 MLP 倾向于拟合低频光滑曲面，而在极值图论中已知的最优图元多为完全 \(k\)-部图或多块阶跃形式。为了兼顾宏观区域几何划分与微观锐利阶跃边界的拟合，该网络设计了一个深层残差架构（深度 \(L=6\)，隐层维度 \(d=256\)）。在每一层 \(\ell \in [L]\)，网络通过权重初始化尺度按指数递增 \(s(\ell) = 2^{\ell-1}\) 的正弦投影矩阵 \(U^{(\ell)}\)，显式将输入坐标的高频正弦特征注入到隐藏层中： $\(g_\theta^{(1)}(\mathbf{x}) = \sin(U^{(1)}\mathbf{x} + b^{(1)}), \quad g_\theta^{(\ell)}(\mathbf{x}) = g_\theta^{(\ell-1)}(\mathbf{x}) + \phi\bigl(V^{(\ell-1)}g_\theta^{(\ell-1)}(\mathbf{x}) + W^{(\ell)}\sin(U^{(\ell)}\mathbf{x}) + b^{(\ell)}\bigr)\)$ 其中浅层网络（低频尺度）负责稳定大尺度的粗粒度几何分布（如对角线带状或块状划分），而深层网络（高频尺度）通过残差连接自适应锐化块之间的阶跃边缘。输出层结合线性投影与标量偏置 \(c\)，通过 Sigmoid 激活函数映射到 \([0, 1]\)：\(f_\theta[c](x_1, x_2) = \mathrm{sm}\bigl(V g_\theta^{(L)}(\min(x_1, x_2), \max(x_1, x_2)) + c\bigr)\)。
2. 内嵌单约束牛顿求解器：严格等式约束的闭环满足 极值图论问题（P1）受制于严格的边密度约束 \(t(K_2, W) = p\)，而大偏差问题（P2）受制于特定的子图同态密度约束 \(t(H, W) = r^{e(H)}\)。若使用常规拉格朗日乘子法或惩罚项，优化过程极易在违反约束与目标函数震荡之间失衡。该方法将标量偏置 \(c\) 从直接可学习参数中解耦，转而在每次迭代的前向传播中利用采样批次 \(\mathcal{E}\) 求解经验等式约束。由于 Sigmoid 激活的单调性，经验同态密度关于标量偏置 \(c\) 是严格单调递增且连续的，保证了唯一解 \(c^*\) 的存在性。针对图元极值接近 0 或 1 时 Sigmoid 导数饱和引发的牛顿更新发散问题，该求解器引入了动态缩小区间的裁剪牛顿法（Clipped Newton Method）： $\(c_{t+1} \leftarrow c_t - \mathrm{Clip}_{[-D/t, \, D/t]}\left(\frac{f(c_t)}{f'(c_t)}\right)\)$ 其中搜索区间 \(D\) 由网络隐层输出的动态极差自适应初始化，确保了在 5-10 步迭代内稳定且高精度地收敛到目标密度。
3. 隐式微分反向传播：无展开开销的高效解析梯度 若将牛顿求解器的迭代过程展开并通过计算图自动微分，需要显式缓存所有中间迭代变量，带来高昂的显存与时间开销。本文利用隐式函数定理（Implicit Function Theorem），通过解析方式求导经验约束关于网络主干参数 \(\theta\) 的全梯度。在满足经验约束 \(\frac{1}{|\mathcal{E}|}\sum_{\mathbf{y}\in\mathcal{E}} f_\theta[c_\theta](\mathbf{y}) = p\) 的平衡点处，标量偏置对参数的导数满足解析闭式： $\(\nabla_\theta c_\theta = -\sum_{\mathbf{y}\in\mathcal{E}} \frac{\mathrm{sm}'(h_\theta(\mathbf{y})+c_\theta)}{\sum_{\mathbf{z}\in\mathcal{E}}\mathrm{sm}'(h_\theta(\mathbf{z})+c_\theta)} \nabla_\theta h_\theta(\mathbf{y})\)$ 代入链式法则后，图元输出的参数全梯度为： $\(\nabla_\theta f_\theta[c_\theta](\mathbf{x}) = \left.\frac{\partial f_\theta[c](\mathbf{x})}{\partial\theta}\right|_{c=c_\theta} - \mathrm{sm}'(h_\theta(\mathbf{x})+c_\theta)\sum_{\mathbf{y}\in\mathcal{E}} w_\theta(\mathbf{y}) \nabla_\theta h_\theta(\mathbf{y})\)$ 其中权重 \(w_\theta(\mathbf{y})\) 正比于局部 Sigmoid 导数。该闭式梯度不仅严格无偏且具有渐近一致性，更将反向传播的内存复杂度降低至常数级别。
4. 对称性感知蒙特卡洛同态估计：降低高维图积分估计方差 计算高阶子图 \(H\) 的同态密度 \(t(H, W) = \mathbb{E}[\prod_{\{i,j\}\in E(H)} W(x_i, x_j)]\) 需要计算 \(v(H)\) 维空间上的积分。朴素蒙特卡洛采样每次独立抽取点集，方差大且难以承受。该方法引入置换群对称性估计器：预先构造 \(v(H)\) 阶置换群的特定子集 \(\mathcal{S}\)（例如对环图 \(C_k\) 采用商群 \(S_{V(C_k)} / \mathrm{Aut}(C_k)\) 的陪集代表元，规模达 \((k-1)!/2\)；对完全图则采用单位置换），在每次迭代中抽取 \(N\) 组独立顶点元组后，通过对所有置换 \(\pi \in \mathcal{S}\) 取平均： $\(\widehat{t}(H, f_\theta[c]) = \frac{1}{N |\mathcal{S}|} \sum_{k=1}^N \sum_{\pi \in \mathcal{S}} \prod_{\{i,j\} \in E(H)} f_\theta[c](x_{\pi(i)}^{(k)}, x_{\pi(j)}^{(k)})\)$ 通过在相同采样顶点之间共享网络的前向计算缓存，在不增加前向推理开销的前提下成倍降低了高阶同态密度的采样方差。
实验关键数据¶
主实验¶
评估涵盖两类核心变分问题： 1. 广义 Turán 问题（P1）：在固定边密度 \(t(K_2, W) = p\) 条件下极小化 \(H\)-同态密度，包括理论已完全解决的团图 \(K_3, K_k\)、尚未完全获解的奇环 \(C_5, C_7\)、以及对所有 6 顶点非二分图（共 117 个图）的系统扫描。 2. 随机图大偏差变分问题（P2）：在固定同态密度 \(t(H, W) = r^{e(H)}\) 条件下极小化相对熵 \(h_q(W)\)，涵盖上尾与下尾体制。
下表展示了 \(K_3\) 密度极小化（P1）在不同边密度 \(p\) 下，神经表示法与理论已知最优值的对比：
| 边密度 \(p\) | 最优理论值 / 已知结构 | 本文网络求得值 (Ours) | 相对误差 | 结构定性特征 |
|---|---|---|---|---|
| \(1/2\) | \(0.00000000\) (Turán 2-部图) | \(0.00008130\) | \(+0.008\%\) | 恢复出标准的完全二部图阶跃结构 |
| \(2/3\) | \(0.22222222\) (Turán 3-部图) | \(0.22232803\) | \(+0.05\%\) | 恢复出完全三部图等块结构 |
| \(4/5\) | \(0.48000000\) (Turán 5-部图) | \(0.48010290\) | \(+0.02\%\) | 恢复出均匀五部图划分 |
| \(4/7\) | \(0.10298638\) (不等块扩展结构) | \(0.10299835\) | \(+0.01\%\) | 准确捕捉到前 \(k\) 块相等、尾块缩小的极值特征 |
| \(5/8\) | \(0.17361111\) (不等块扩展结构) | \(0.17362659\) | \(+0.01\%\) | 拟合出非对称块几何与平坦零值带 |
| \(5/7\) | \(0.31363508\) (Pikhurko-Razborov) | \(0.31370832\) | \(+0.02\%\) | 成功呈现出中间二部块交叉的精细极值形态 |
在大偏差理论上尾变分问题（P2，针对 \(H=K_3\)）中，本文候选解与 Lubetzky-Zhao (2015) 提出的著名三部图参考构造 \(W_{\mathrm{LZ}}\) 以及理论下界进行了对比（数值越低越优）：
| 参数配置 \((q, r)\) | Lubetzky-Zhao 构造 \(h_q(W_{\mathrm{LZ}})\) | 本文神经解 \(h_q(W_{\mathrm{ours}})\) | 理论下界 (Lower Bound) | 相比 \(W_{\mathrm{LZ}}\) 改善 |
|---|---|---|---|---|
| \((0.05, 0.4)\) | \(0.556057\) | \(0.464208\) | \(0.460284\) | \(-16.52\%\) (显著优于基准构造) |
| \((0.05, 0.5)\) | \(0.830366\) | \(0.727881\) | \(0.725284\) | \(-12.34\%\) (逼近理论下界) |
| \((0.05, 0.6)\) | \(1.144945\) | \(1.051203\) | \(1.049172\) | \(-8.19\%\) (差距收敛至下界边缘) |
| \((0.10, 0.4)\) | \(0.311239\) | \(0.309109\) | \(0.306561\) | \(-0.68\%\) |
| \((0.10, 0.5)\) | \(0.510826\) | \(0.506060\) | \(0.504311\) | \(-0.93\%\) |
| \((0.10, 0.6)\) | \(0.750684\) | \(0.747694\) | \(0.746006\) | \(-0.40\%\) |
消融实验¶
在 \(p = 7/9\) 约束下的三角形密度极小化任务中（已知理论最优为 \(98/225 \approx 0.435556\)），各项架构组件的消融及与非神经网络基线的对比表现如下：
| 配置 / 变体 | 激活函数 / 编码 | 得到 \(t(K_3, W)\) 密度 | 说明 / 结论 |
|---|---|---|---|
| 完整模型 (Ours) | Sin (多尺度残差) | \(0.435712\) | 最逼近理论界限，分块边界锐利清晰 |
| 完整模型 (GELU 激活) | GELU (多尺度残差) | \(0.436066\) | 性能仍极佳，略逊于全正弦变体 |
| 仅首层正弦编码 (ResNet 变体) | Sin / GELU | \(0.435724\) / \(0.436405\) | 丢失深层频率控制，深层分块锐化程度降低 |
| 固定编码尺度 \(s(\ell)=\mathrm{const}\) | Sin | \(0.435689\) | 需仔细调参，对层间渐进几何适应能力不如递增尺度 |
| 约束替换为正则项惩罚 (Regulariser) | Sin | \(0.437085\) | 无法严格贴合约束超曲面，目标值产生明显漂移 |
| 固定学习率 (低学习率 \(10^{-4}\)) | Sin | \(0.437544\) | 易困在次优局域，无法跳出粗粒度局部极值 |
| 固定学习率 (高学习率 \(10^{-3}\)) | Sin | \(0.436174\) | 边界震荡，无法在退火阶段收敛到精密阶跃边界 |
| SBM (256 固定等大块) | 非神经基线 | \(0.435817\) | 产生网格化噪声，无法自适应块边界位置 |
| SBM (5 / 64 可训块尺寸) | 非神经基线 | \(0.470508\) | 优化曲面极端恶劣，块大小训练崩塌为常数图元 |
| 决策树 / 梯度提升决策树 | 非神经基线 | \(0.455558\) / \(0.454485\) | 贪心分裂陷入次优阶跃点，难以逼近真正极值 |
关键发现¶
- 发现全新极值图元形态：在针对 6 顶点 9 条边的图 \(H_6\)（在 \(p=1-1/k\) 时）的扫视中，神经网络发现了既非完全 \(k\)-部图、亦非平坦常数的全新极值结构；其边概率呈现基于 \([0,1]\) 圆周几何距离衰减的连续平滑环状图案。
- 证伪经典构造的全局最优性：在 Erdős–Rényi 随机图三角形大偏差的上尾体制下，该方法找到的双块图元结构在相对熵上全面显著低于 Lubetzky-Zhao 经典三部图结构，促成了相关正则图大偏差最优图元必然是双足图元（Bipodal）的新定理证明。
- 全自动发现的数学理论转化：基于该框架在 \(C_5, C_7\) 与弦图上的实验发现，作者团队成功提炼并用 Lean 4 形式化证明了新定理：对于任意极大团阶数均为 \(r \geq 3\) 的连通弦图，在 \(p=1-1/k\)（\(k \ge r\)）处平衡完全 \(k\)-部图必定为其极小化子。
亮点与洞察¶
- 多尺度正弦残差引导的几何连续化：将传统离散图组合搜索松弛至图元紧致测度空间，通过层进频率注入克服了深度网络拟合阶跃函数的低频偏置，兼顾了连续搜索的平滑性与离散结构的清晰可读性。
- 内嵌数值求解与隐式微分深度结合：针对严格单等式流形约束，巧妙利用单调性构建带裁剪的牛顿求解闭环，并推导紧凑的解析隐式梯度，实现了零内存膨胀且完全满足约束的端到端训练。
- 从 AI 经验搜索到形式化数学定理的闭环：该框架不仅作为数值求解器提供上限，更作为探索工具协助数学家识别极值模式，直接启发了纯数学新定理并在 Lean 4 中完成机器验证，展示了 AI 辅助纯数学发现的高阶范式。
局限与展望¶
- 稀疏图适用性受限：由于图元极限理论本身是稠密图序列（边数 \(O(n^2)\)）的分析工具，该方法无法直接迁移至稀疏图（如边数 \(O(n)\)）的极值组合问题。
- 计算复杂度随子图规模上升：当目标子图基数显著增大（如 Petersen 图）时，同态密度的蒙特卡洛多重积分方差与点对评估缓存内存急剧增长，极小密度下的相对误差较难控制。
- 缺乏理论下界与严格最优性保证：神经变分探索输出的是极值图元的经验候选解（上界），必须结合 Flag Algebras 等凸松弛证明技术才能构建严密的双向数学证明。
相关工作与启发¶
- vs Flag Algebras (旗代数半定规划): Flagmatic 通过枚举子图与半定规划提供严格的理论下界与代数证明，但在 8 顶点以上因组合爆炸受限且无法直观呈现极值函数形态；本文提供紧致候选图元与极值上界，两者互补可形成猜测与证明的闭环。
- vs 离散图组合搜索 (AlphaZero / PatternBoost / Tabu Search): 离散强化学习与局部搜索局限于固定有限节点规模 \(n\)，极值图高度对称且受离散噪声干扰；本文直接在无限规模的渐近连续极限空间寻优，解具有高度可解释的宏观几何结构。
- vs 传统图元学习 (Xia et al. / Azizpour et al.): 传统图元学习旨在从给定的多张离散图样本中经验性拟合未知的生成图元；本文没有任何观测图数据，而是直接在全空间针对抽象数学变分泛函求解极值。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次将隐式神经表示与隐式微分求解器结合引入图元极值变分问题，架构针对阶跃与对称性设计极为精巧。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖经典验证、开问题猜想、117 种小图系统扫描及随机图大偏差，并在 Lean 4 完成定理形式化验证。
- 写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨精炼，问题背景、算法动机与实验分析层层推进，逻辑极佳。
- 价值: ⭐⭐⭐⭐⭐ 为极值图论与大偏差理论提供了革命性的猜想与直观探索工具，成功孵化出真正的纯数学新定理。