Characterizing the Discrete Geometry of ReLU Networks¶

会议: ICLR 2026
OpenReview: TgLW2DiRDG
代码: https://github.com/bl-ake/ICLR-2026
领域: 学习理论 / 神经网络几何
关键词: ReLU 网络、多面体复形、连通图、平均度、图直径

一句话总结¶

本文把全连接 ReLU 网络在输入空间切出的多面体复形抽象成一张"连通图"（区域当节点、相邻区域连边），并证明这张图的平均度恒被 $2d$（两倍输入维度）上界约束、与网络宽度深度无关，同时给出图直径不依赖输入维度的上界 $O(m^\ell)$，再用合成数据与 MNIST/CIFAR10 等实验验证这些理论界并揭示"训练数据更爱落在连通度高的区域"。

研究背景与动机¶

领域现状：ReLU 网络实现的是连续分片线性函数，每一"片"都定义在输入空间的一个多面体（polyhedron）上，这些多面体拼成一个完整划分输入空间的多面体复形（polyhedral complex）。网络的非线性只发生在区域交界处，所以这些区域"怎么拼在一起"直接决定了网络的行为。过去十多年，社区在"一个架构最多能切出多少个区域"这个问题上做了大量工作（Montúfar 2014 起），但这些工作只数区域数量、不描述它们的排布方式。

现有痛点：精确算出整个复形对绝大多数网络都是不可行的——区域数随输入维度和网络规模指数增长。于是除了"区域总数的界"之外，关于复形几何（区域之间如何相邻、从一个区域走到另一个要穿过多少个面）几乎一无所知。少数描述排布的工作（如 Fan et al. 2024 给出平均面数的上界）又依赖很强的假设（第一隐层无偏置项或权重低秩），且界是关于网络规模的渐近结果，不适用于一般架构。

核心矛盾：我们想要的是不依赖具体权重值、不依赖架构大小的普适几何性质，但已有工具要么只能数数量、要么需要苛刻假设、要么只能给渐近界。区域指数爆炸让"逐个区域分析"这条路彻底走不通。

本文目标：建立对所有全连接 ReLU 网络都成立的几何性质，具体落在复形的连通图（connectivity graph）上——节点是各个多面体区域，两个共享一个面的区域之间连一条边。围绕这张图回答三个问题：每个区域平均有多少个邻居（节点平均度）？这个数量随网络变大如何变化？从任意区域走到另一区域最远要穿过多少个面（图直径）？

切入角度：作者沿用 Masden (2025) 的拓扑视角，用符号序列（sign sequence）给每个 cell 编码——这把"连续的几何对象"变成了"离散的组合对象"，于是数面、数邻居、判断相邻都能转成对符号序列做组合计数，从而绕开了对几何坐标的直接计算。

核心 idea：用符号序列把多面体复形翻译成连通图，再借助"逐个移除神经元的弯曲超平面 + 归纳法"证明：平均度恒 $\le 2d$、随规模单调逼近 $2d$，且图直径上界与输入维度无关。

方法详解¶

整体框架¶

本文是一篇纯理论论文，主线是"把几何问题离散化 → 证主结论 → 给可计算算法验证"。整体可以拆成三层：(1) 离散化语言——用符号序列把多面体复形和连通图统一表达，使所有关于区域、面、相邻的陈述都能转化为对 $\{-1,0,1\}^n$ 向量的组合计数；(2) 理论结论——在这套语言里证明平均度上界 $2d$、渐近收敛性、度的下界以及连通图直径的上下界；(3) 计算与实证——给出一个基于广度优先搜索（BFS）+ 线性规划（LP）的算法精确枚举多面体并构建连通图，再用它在合成数据与真实数据集上验证理论界、并观察训练数据的分布规律。

记网络输入维度为 $d$、隐藏神经元总数为 $n$、最大层宽为 $m$、深度（隐层数）为 $\ell$。核心对象是连通图 $G=(V,E)$：$V$ 是所有 $d$-cell（网络映射在其上为仿射的极大区域）的符号序列，两个符号序列只在一个位置不同时连边。一个节点的度就等于其区域的面数，也就是它的邻居数。证明的所有重活都压在"如何对这些 cell 做精确计数"上，而符号序列正是让计数变得可归纳的关键。

关键设计¶

1. 符号序列与弯曲超平面：把连续几何翻译成离散组合

要在不碰具体坐标的前提下推理区域如何相邻，作者借用 Masden (2025) 的编码方式。对输入空间中的点 $x$，每个隐藏神经元 $i$ 先做仿射变换 $w_i^T x_{p_i}+b_i$ 再过 ReLU：若该值 $>0$ 则符号 $S(x)_i=1$，$=0$ 则为 $0$，$<0$ 则为 $-1$。于是 $x$ 拿到一个长度 $n$ 的符号序列 $S(x)\in\{-1,0,1\}^n$。在第一隐层，$S(x)_i=0$ 的点落在一张超平面上；在更深的层，由于 $x_{p_i}$ 是前面各层的分片线性函数算出来的，$S(x)_i=0$ 的点集变成一张可以自交、甚至断开的弯曲超平面（Bent Hyperplane, BH）。每条 BH 把空间分成 $S(x)_i=1$ 和 $S(x)_i=-1$ 两侧，所有 BH 一起把输入空间划成多面体复形。

这套编码之所以关键，是因为它建立了 cell ↔ 符号序列的一一对应（在排除测度零退化权重的温和假设下，映射 $S:\mathcal C\to\{-1,0,1\}^n$ 良定义且单射）：一个 $k$-cell 的符号序列恰好有 $d-k$ 个 $0$（对应包含它的 $d-k$ 条 BH 的交）和 $k$ 个非零元；$d$-cell（无零元）就是连通图的节点，两个 $d$-cell 相邻当且仅当符号序列只差一个符号翻转。这样一来，"数一个区域的面数 = 数它的邻居 = 数符号序列里能翻转成合法序列的位置数"，几何问题彻底变成组合计数问题。

2. 逐神经元剥离 + 归纳：证明平均度上界 $2d$

主结论是 Theorem 3.1 的特例 Theorem 3.4：连通图的平均度（$d$-cell 的平均面数）至多为 $2d$，且这与网络的宽度、深度、权重值都无关。证明的核心是一条剥离-计数递推。作者定义 $C-h_i$ 为"删掉神经元 $i$ 的弯曲超平面 $h_i$ 所含全部 cell、并把因此共享被删面的 cell 两两融合"后的复形。Lemma 3.2 证明：对任意神经元 $i$，每个 $k$-cell 恰好属于三类之一——类 1（落在 $h_i$ 上的 cell，符号序列第 $i$ 位为 $0$）、类 2（$C-h_i$ 里不被 $h_i$ 影响的 cell）、类 3（在 $C-h_i$ 里本是一个、被 $h_i$ 劈成两半的 cell）。判定只需看符号序列：第 $i$ 位是否为零、以及把它置零后得到的序列是否仍是复形中的合法 cell。

基于这个分类，Lemma 3.3 给出递推式 $$N_k(\mathcal C)=N_k(h_i)+N_k(\mathcal C-h_i)+N_{k-1}(h_i),$$ 其中 $N_k$ 表示 $k$-cell 的数量：第一项数类 1，第二项数全部类 2 加一半类 3，第三项（用 $h_i$ 里的 $(k-1)$-cell 去数"被劈出来的另一半"）补齐剩下一半类 3。由于每个 $(d-1)$-cell 恰好是两个 $d$-cell 的公共面，平均面数等于 $\frac{2N_{d-1}(\mathcal C)}{N_d(\mathcal C)}$，作者对 BH 数 $n$ 和维度 $d$ 做双重数学归纳，从 $(n-1,d-1)$ 和 $(n-1,d)$ 推出 $(n,d)$ 仍满足 $\le 2d$，从而完成证明。值得强调的是，单层网络（超平面排布）的同款结论早有 Fukuda et al. (1991)，但那套证明无法推广到 BH 排布的深层网络，本文正是靠符号序列的一一对应补上了这个缺口。

3. 渐近收敛与度的下界：上界是紧的、不是空泛的

只证一个上界容易让人怀疑它松不松，所以作者补上紧性与下界。Theorem 3.5 给出下界：若第一隐层有 $n_1$ 个神经元，则每个 $d$-cell 至少有 $\min(n_1,d)$ 个邻居，平均度也因此不低于 $\min(n_1,d)$。Theorem 3.6 证明：往最后一层（或其后新增一层）不断加神经元构造网络序列 $\mathcal C_n$ 时，$d$-cell 的平均面数单调递增。Theorem 3.7 进一步证明对单隐层浅网络，当神经元数 $n\to\infty$ 时平均面数精确收敛到 $2d$： $$\lim_{n\to\infty}\frac{2N_{d-1}(\mathcal C_n)}{N_d(\mathcal C_n)}=2d.$$ 三条放一起说明 $2d$ 这个上界是会被逼近的真界，而不是一个永远够不着的松界。实验中作者还观察到，随深度增加平均面数同样趋向 $2d$。

4. 直径上界与输入维度解耦：穿越复形的代价有多大

最后一个量是连通图的直径——任意两区域之间最短路的最大值，几何上即"从一个多面体走到任意另一个最少要穿过多少个面"。Theorem 3.8 给出 $$\mathrm{diam}(G)=\Omega\!\left(\frac{\ln N_d(\mathcal C)}{\ln n}\right)\ \text{且}\ O(m^\ell).$$ 下界 $\Omega$ 符合直觉：区域越多直径越大；虽然增神经元会让分母 $\ln n$ 变大，但 $\ln N_d(\mathcal C)$ 增长更快，所以 $\ln n$ 只是减缓而非逆转下界增长。真正有意思的是上界 $O(m^\ell)$ ——它只依赖宽度 $m$ 和深度 $\ell$，完全不含输入维度 $d$，尽管区域总数随 $d$ 指数爆炸。这意味着无论输入空间多高维，穿越整个复形的"跳数代价"在架构固定时大体不变。该结论的实际价值在 Discussion 里点明：Ji et al. (2022) 用符号序列的 Hamming 距离作为区域间距离来界定经验训练误差，但 Hamming 距离无法反映"一条 BH 可能被来回穿越多次"的情形，而连通图最短路才是更恰当的度量；配合 Theorem 3.8，就能给出不依赖输入维度的经验误差界。

一个完整示例¶

以论文 Fig. 2 的小网络为例直观感受上述机制：输入 $d=2$，两个隐层，第一层 3 个神经元（对应 BH 1–3）、第二层 1 个神经元（对应 BH 4）。BH 1–3 都是直线，三条相交把平面切成 7 个区域；BH 4 是一条"弯折线"，它每穿过一条前层 BH，输入 $x_{p_i}$ 中对应分量的激活状态就在 $w_j^T x+b_j$ 与 $0$ 之间切换，导致 BH 4 发生弯折，最终甚至自交。BH 4 把它经过的 6 个区域各自再劈成两半，于是从 6 个变 12 个。

接着看证明里的"剥离"：取 $h_i=$ BH 4。$C-h_4$ 就是把 BH 4 抹掉、把被它劈开的区域重新合并回去（Fig. 3a）。再按 Lemma 3.2 给 cell 上色（Fig. 3b/3c）：蓝色是类 1（落在 BH 4 上的线段与顶点，符号序列第 4 位为 0）；绿色是类 2（删掉 BH 4 后不变的 cell，例如中心 $(-1,-1,-1,-1)$ 的 2-cell，把第 4 位置零得到 $(-1,-1,-1,0)$ 并不存在于复形中）；红色是类 3（被 BH 4 劈开的 cell，例如最左 2-cell 符号序列 $(-1,-1,1,1)$，置零后 $(-1,-1,1,0)$ 恰好对应它右边界那段 BH 4）。在连通图里，删除 $h_i$ 等价于把所有对应 $(d-1)$-cell 的边做边收缩，把被劈开的两个节点重新并成一个——这正是递推式 $N_k(\mathcal C)=N_k(h_i)+N_k(\mathcal C-h_i)+N_{k-1}(h_i)$ 的图论化身。

损失函数 / 训练策略¶

本文不涉及新的训练目标。为了实证理论界，作者给出 Algorithm 1：从任一点过网络拿到一个合法符号序列 $s$ 出发，用 BFS 枚举多面体并增量构建连通图。对当前序列 $s$，按公式 $$\Phi^{(j)}=\mathrm{diag}(s^{(j)})\,W^{(j)}\,\mathrm{diag}(\mathrm{ReLU}(s^{(j-1)}))\,\Phi^{(j-1)},\quad \beta^{(j)}=\mathrm{diag}(s^{(j)})\,W^{(j)}\,\mathrm{diag}(\mathrm{ReLU}(s^{(j-1)}))\,\beta^{(j-1)}+b^{(j)}$$ （初始 $\Phi^{(0)}=I_d,\ \beta^{(0)}=0,\ s^{(0)}=\mathbf 1$）逐层拼出该多面体的半空间不等式系统 $\Phi x+\beta\le 0$；再对每个邻居方向解一个 LP（SOLVELP）判断对应不等式是否冗余——非冗余者意味着翻转第 $i$ 位 $s_{-i}$ 给出一个真实邻居，于是加边、未访问过则入队。为减少数值精度误差，判定时对不等式做轻微松弛。该算法的几何遍历思路与 Xu et al. (2022) 等的 BFS 相近，但额外记录了"何时与已发现的多面体共享面"，从而在搜索过程中直接构建出连通图。

实验关键数据¶

主实验¶

作者先在合成数据上验证理论界：用三个各向同性、单位方差的高斯（中心在边长 10 的超立方体内随机取）生成聚类任务，遍历输入维度 $d$、隐层数、每层宽度的组合，每组配置跑 5 次（新数据集），并对小网络做穷举枚举得到完整复形。

配置（$d{=}4$ / $d{=}5$）	多面体数	平均度	直径
深度 1，宽 16	2517 / 6885	7.32 / 9.02	22.5 / 23.2
深度 2，宽 16	4.2e4 / 2.7e5	7.72 / 9.61	41.1 / 42.6
深度 4，宽 16	6.2e5 / 5.0e6	7.85 / 9.80	76.4 / 70.9

可见平均度始终低于上界 $2d$（$d{=}4$ 时 $<8$，$d{=}5$ 时 $<10$），且随网络变大稳步逼近上界；邻居数分布单峰、右偏、峰值略低于 $2d$，与 Theorem 3.1/3.7 完全吻合。

直径与分布分析¶

观察	结果	对应理论
固定架构、只变输入维度 $d$	各 $d$ 下直径估计几乎相同	Theorem 3.8 上界与 $d$ 无关
固定宽度、变深度	直径随理论上界近似对数增长	$O(m^\ell)$ 上界很少被打满
训练数据所在区域 vs 空区域	含数据区域的平均邻居数高于全体上界	5.2 节新发现

直径的实际值用 Magnien et al. (2009) 的上下界算法取中点估计（并未用本文渐近界来估，避免循环论证）。

关键发现¶

平均度的鲁棒性：在所有合成与真实实验（California Housing、MNIST、CIFAR10，均达到 AUC>0.9 或 $R^2>0.6$）中，平均度都严格落在 $2d$ 之下且分布右偏，证实上界既普适又被逼近。
训练数据偏好高连通区域：含训练数据的多面体邻居数普遍高于全体平均上界——由于任意多面体面数被 $n$ 上界约束，这反而压低了分布的右偏程度。作者坦言尚未能完全解释训练为何把数据推向高面数区域。
有界/无界与任务类型相关：邻居数越多的多面体越可能是无界的；分类任务（MNIST/CIFAR10）中含数据区域的无界比例高于整体，回归任务（CA Housing）则相反——作者解释为分类需把复杂度集中在类间决策边界、数据点多落在外围无界区域，而回归要拟合数据值、数据点更多落在有界区域。

亮点与洞察¶

离散化是真正的杠杆：把"区域如何相邻"翻译成"符号序列差一个翻转"，让原本被指数爆炸卡死的几何分析变成可归纳的组合计数——这是全文所有上界证明能跑通的根本原因，也是一种可迁移到其他分片线性结构分析的思路。
$2d$ 上界的"反直觉"之美：平均度只跟输入维度走、和宽度深度完全无关，意味着无论网络多大多深，每个区域平均"邻居数"被牢牢钉在两倍输入维度以内；直径上界更进一步与 $d$ 解耦。这类"架构无关"的不变量在充满架构依赖结论的深度学习理论里相当稀少。
理论直接喂给下游：Theorem 3.8 不只是漂亮，它指出用连通图最短路替代 Hamming 距离能给出不依赖输入维度的经验误差界，把抽象几何性质接到了泛化分析、可解释性、鲁棒性、MIP 验证等一串实际课题上。
算法让理论可证伪：Algorithm 1 把符号序列、半空间公式、LP 冗余判定串成一个能真正跑出连通图的工具，使"平均度逼近 $2d$"这种渐近论断能在 MNIST/CIFAR10 上被直接观测。

局限与展望¶

作者承认的局限：尚无法解释训练为何把数据推向高面数区域、它与网络行为的关系如何；也未能刻画卷积层、跳连这类更具体结构对几何的影响。
激活函数受限：结论只对 ReLU（及可推广的分片线性激活）成立，对 sigmoid/tanh 等非线性激活没有直接含义。
可计算性瓶颈仍在：尽管理论界普适，但精确枚举复形对大网络仍不可行（CIFAR10、CA Housing 实验只能在遍历 800 万个多面体后中止），实证只能在低维隐表示或小网络上做，真实大模型的几何仍是黑箱。
可改进方向：把"数据爱落在高连通区域"与泛化/鲁棒性建立定量联系；将剥离-归纳框架推广到带 skip/conv 的结构；或基于直径界设计输入维度无关的误差/鲁棒性证书。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次对任意全连接 ReLU 网络的连通图给出与宽深无关的平均度上界和与输入维度无关的直径上界。
实验充分度: ⭐⭐⭐⭐ 合成数据穷举 + 三个真实数据集验证理论界，但受可计算性限制只能在小网络/低维隐表示上做。
写作质量: ⭐⭐⭐⭐ 符号序列—弯曲超平面—剥离归纳的脉络清晰，配图（Fig.2/3）把抽象证明讲得直观。
价值: ⭐⭐⭐⭐ 提供稀有的"架构无关"几何不变量，并把直径界直接接到经验误差分析等下游课题。

观察	结果	对应理论
固定架构、只变输入维度 \(d\)	各 \(d\) 下直径估计几乎相同	Theorem 3.8 上界与 \(d\) 无关
固定宽度、变深度	直径随理论上界近似对数增长	\(O(m^\ell)\) 上界很少被打满
训练数据所在区域 vs 空区域	含数据区域的平均邻居数高于全体上界	5.2 节新发现