Propagation and Optimization of Low-Frequency Spectral Alignment in ReLU Networks on a Fixed Sample Graph

Setting and notation

Let $X \in\mathbb{R}^{d \times n}$ be the sample and $f \in\mathbb{R}^{n}$ the target values. Let $G(X)$ be a weighted undirected graph on the $n$ samples with symmetric nonnegative weights $w_{ij}$, degrees $d_i = \sum_j w_{ij} > 0$, $D = \operatorname{diag}(d_1,\ldots,d_n)$ and $W = (w_{ij})$. We consider the use of Laplacians such as the combinatorial or symmetric normalized:

see [2, 3]. Their quadratic forms are

Throughout, $\mathcal{L}$ denotes either $L$ or $L_{\mathrm{sym}}$ unless stated otherwise. Write $\mathcal{L} = U\Lambda U^{\mathsf{T}}$ with $U = [u_1,\ldots,u_n]$ orthogonal and $0 = \lambda_1 \le\lambda_2 \le\cdots\le\lambda_n$. Let $U_K = [u_1,\ldots,u_K]$, $P_K = U_KU_K^{\mathsf{T}}$ and $P_K^\perp= I-P_K$.

Network. Let $\sigma(t)=\max(t,0)$ act entrywise. Set $H_0=X^{\mathsf{T}}\in\mathbb{R}^{n\times d}$ and, for $\ell=1,\ldots,p$,

The readout features are $Z=[H_p,\mathbf{1}]$, $\beta=Z^{+}f$, $g=Z\beta=\Pi_Zf$ where $\Pi_Z$ is the orthogonal projector onto $\operatorname{col}(Z)$, and the residual is $r=g-f$.

Single neuron. For a neuron in layer $\ell$ let $\Phi=[H_{\ell-1},\mathbf{1}]\in\mathbb{R}^{n\times m}$, $\theta\in\mathbb{R}^{m}$, $z=\Phi\theta$ the pre-activation and

For vectors and matrices, $|\cdot|$ is the entrywise absolute value and inequalities between vectors are entrywise.

Coverage. For a matrix $Z$ define the coverage gap

When $\operatorname{rank}Z\ge K$, $s_K(Z)$ is the sine of the largest principal angle between $\operatorname{span}(U_K)$ and its closest $K$-dimensional subspace of $\operatorname{col}(Z)$ [6, 7, 5].

Preliminaries

Coverage of the low frequencies

The least-squares error splits into a low-frequency part, controlled by how well $\operatorname{col}(Z)$ contains $\operatorname{span}(U_K)$ as measured by the coverage gap $s_K(Z)$, and a high-frequency part, controlled by the smoothness of $f$.

Proof. (a) holds entrywise: $\max(t,0)-\max(-t,0)=t$. (b) $\sigma(H_{\ell-1}e_k)=H_{\ell-1}e_k$ since $H_{\ell-1}\ge0$. (c) By (a), $X^{\mathsf{T}}e_k=\sigma(X^{\mathsf{T}}e_k)-\sigma(-X^{\mathsf{T}}e_k)$ lies in $\operatorname{col}(H_1)$. The consequence follows from Lemma 3.2. □

Proof. (i) The singular values of $U_K^{\mathsf{T}}Q_H$ are the cosines of the principal angles [6]. (ii) There are $\min(K,\operatorname{rank}H)$ principal angles and each $\cos^2\theta_i\in[0,1]$. (iii) Take $Q_H=h/\lVert h\rVert$. (iv) $\lVert\Pi_HU_K\rVert_F^2=\operatorname{tr}(U_K^{\mathsf{T}}\Pi_HU_K)=N_K(H)$ and $\lVert U_K\rVert_F^2=K$, so Pythagoras gives the identity; then $\lVert\cdot\rVert_F^2/K\le\lVert\cdot\rVert_2^2\le\lVert\cdot\rVert_F^2$. □

Optimizing neurons to capture low frequencies

By Lemma 3.5(iii) a single neuron captures at most one low-frequency dimension; capturing many is a property of a layer. We first bound what a single gated neuron can achieve, then give a fixed-gating formulation for a single neuron and for the marginal gain of adding a neuron to a layer.

Proof. Write $h_A$ for the restriction of $h$ to $A$. Then $\lVert P_Kh\rVert^2=\lVert U_K[A,:]^{\mathsf{T}}h_A\rVert^2\le\lVert U_K[A,:]\rVert_2^2\lVert h\rVert^2$. The spectral norm is at most $1$ because $U_K$ has orthonormal columns, and at most the Frobenius norm, whose square is $\sum_{i\in A}\ell_i$. Next, $h^{\mathsf{T}}\mathcal{L}h=h_A^{\mathsf{T}}\mathcal{L}_{AA}h_A\ge\lambda_{\min}(\mathcal{L}_{AA})\lVert h\rVert^2$. Finally, Cauchy interlacing [4] for an $|A|\times|A|$ principal submatrix gives $\lambda_1(\mathcal{L}_{AA})\le\lambda_{1+n-|A|}(\mathcal{L})=\lambda_{|B|+1}$. □

Remark 4.2. Since $\sum_i\ell_i=K$, for delocalized eigenvectors $\ell_i\approx K/n$ and a neuron active on $|A|$ vertices captures at most about $K|A|/n$. Small active sets cap low-frequency capture, formalizing why dead or very sparse ReLUs hurt coverage. The bound $R(h)\ge\lambda_{\min}(\mathcal{L}_{AA})$ is a Dirichlet eigenvalue: the inactive set $B$ acts as a boundary on which $h(B)=0$, in the spirit of the harmonic-extension theorem [1 Thm. 11.6.1]. Conversely, by Proposition 3.3(a), the pair $\sigma(u_k),\sigma(-u_k)$, supported on the positive and negative nodal domains of $u_k$, recovers $u_k$; discrete nodal domain theorems [13] bound how many such domains $u_k$ has.

where $Q_S$ is an orthonormal basis of $\operatorname{col}(S\Phi)$, with equality if a maximizer of the unconstrained ratio lies in $C_S$. The global problem $\max_\theta N_K(\sigma(\Phi\theta))$ equals the maximum of the cone-constrained problems over the finitely many gating patterns realized by $\Phi$.

Proof. If $S_{ii}=1$ and $(\Phi\theta)_i\ge0$ then $\sigma(\Phi\theta)_i=(\Phi\theta)_i=(S\Phi\theta)_i$; if $S_{ii}=0$ and $(\Phi\theta)_i\le0$ then $\sigma(\Phi\theta)_i=0=(S\Phi\theta)_i$. So on $C_S$ the neuron is the linear map $\theta\mapsto S\Phi\theta$, and Lemma 3.5(iii) with $S^2=S=S^\top$ gives the ratio. Dropping the cone constraint, the ratio ranges over $\lVert P_Kv\rVert_2^2/\lVert v\rVert_2^2$ for nonzero $v\in\operatorname{col}(S\Phi)$, whose maximum is $\lVert U_K^\top Q_S\rVert_2^2$, the squared cosine of the smallest principal angle [6]. Every $\theta$ lies in $C_{S(\theta)}$, which proves the last claim; the number of realized patterns is finite and, for fixed rank $\Phi$, polynomial in $n$ [10, 11].

Remark 4.4. A maximizer $v^\star=Q_Sy^\star$ of the unconstrained ratio ($y^\star$ a top right singular vector of $U_K^\top Q_S$) is realizable in $C_S$ iff, for one choice of sign, $\pm v_A^\star\ge0$ and the linear program $\{\theta:\Phi_A\theta=\pm v_A^\star,\ \Phi_B\theta\le0\}$ is feasible, where $A,B$ are the active and inactive index sets of $S$. Maximizing a Rayleigh quotient over a cone is a cone-constrained (Pareto) eigenvalue problem [12]. The cone $C_S$ and the enumeration over patterns are the same objects as in the convex reformulation of two-layer ReLU networks [11].

Increasing coverage across layers

Proposition 3.3 shows that coverage need not decrease from one layer to the next. This section asks when, and how fast, the remaining neurons of a layer can increase it. Fix a layer $\ell$ and $\Phi=[H_{\ell-1},1]$. For a feature matrix $H$ built in this layer write

so that $\delta(H)$ is the coverage deficit (Lemma 3.5(iv)) and, by Proposition 4.5, $G_H(h)$ is the increase of $N_K$ obtained by appending $h\notin\operatorname{col}(H)$. Since $G_H(h)=\lVert M_H^\top\hat{y}\rVert_2^2$ for the unit vector $\hat{y}=(I-\Pi_H)h/\lVert(I-\Pi_H)h\rVert$, we always have $G_H(h)\le\lVert M_H\rVert_2^2=s_K(H)^2$. We also use that $N_K$ is monotone: if $\operatorname{col}(A)\subseteq\operatorname{col}(B)$ then $\Pi_B-\Pi_A\succeq0$, so $N_K(B)-N_K(A)=\operatorname{tr}((\Pi_B-\Pi_A)P_K)\ge0$.

When can a layer increase coverage?

What a layer can add is determined by which samples it can still tell apart.

Proof. (a) Samples with identical rows receive identical pre-activations. (b) Choose one representative per class. Their rows are distinct, so a generic $w \in\mathbb{R}^{m_{\ell-1}}$ (one avoiding the finitely many hyperplanes on which two representatives have equal projection) gives distinct projections, which we order as $t_1 < \cdots< t_q$. Choose $b_1 < t_1$ and $b_k \in(t_{k-1},t_k)$ for $k \ge2$, and let $v_k = \sigma(H_{\ell-1}w-b_k\mathbf{1})$, the neuron with $\theta=(w,-b_k)$. On class $c$, $v_k$ equals $(t_c-b_k)_+$, which is $0$ for $c<k$ and positive for $c\ge k$. In the basis of class indicators, $v_1,\ldots,v_q$ therefore form a triangular matrix with positive diagonal, so they are linearly independent and span the $q$-dimensional space $V_P$. This is the interpolation construction of [14]. □

and $H_\ell$ has pairwise distinct rows.

Proof. By Proposition 3.3(a), $p_i=\sigma(p_i)-\sigma(-p_i)\in\operatorname{col}(H_\ell)$, so $W=\operatorname{span}\{p_1,\ldots,p_r\}\subseteq\operatorname{col}(H_\ell)$. The matrix $U_K^{\mathsf T}Q\Phi$ has at most $r$ nonzero singular values $\cos\theta_i$, and $U_K^{\mathsf T}QW=U_K^{\mathsf T}Q\Phi[y_1,\ldots,y_r]$ retains all of them, so $N_K(W)=\sum_{i\le r}\cos^2\theta_i=N_K(\Phi)$ by Lemma 3.5(i). If $r=K$, then $s_K(W)^2=1-\sigma_{\min}(U_K^{\mathsf T}QW)^2=1-\sigma_{\min}(U_K^{\mathsf T}Q\Phi)^2=s_K(\Phi)^2$; if $r<K$, then $\operatorname{rank}\Phi<K$, so some unit vector in $\operatorname{span}(U_K)$ is orthogonal to $\operatorname{col}(\Phi)$ and $s_K(\Phi)=1$. Monotonicity of $N_K$ and Lemma 3.2 give the two inequalities. A direction $w$ exists because the rows of $\Phi$ are distinct and a generic $w$ avoids finitely many hyperplanes. If rows $i\ne j$ of $H_\ell$ were equal, then $(\Phi w)_i=\sigma(\Phi w)_i-\sigma(-\Phi w)_i$ would equal $(\Phi w)_j$, a contradiction. □

Remark 5.6. A layer of width $2K+2+t$ therefore preserves coverage, keeps Theorem 5.1 applicable at the next layer, and leaves $t$ neurons free to add coverage. Under the hypotheses of Corollary 5.4, width $2r+1$ already gives a strict increase: either the $2r$ principal-vector neurons alone give $N_K=K>N_K(\Phi)$, or Theorem 5.3(a) applies to them. The inequality $N_K([H_\ell,1])\ge N_K(\Phi)$ is typically strict, because the pieces $\sigma(\pm p_i)$ span more than $p_i$.

Remark 5.7. (Skip connections). Propositions 3.3 and 5.5 spend $m_{\ell-1}$, $2d$ or $2K+2$ neurons of every layer only on preserving coverage. Skip connections, as in residual networks [18], do this for free. We consider the concatenated form of [19],

with $\Theta_\ell\in\mathbb{R}^{(m_{\ell-1}+1)\times k_\ell}$, so that the columns of $R_\ell$ are $k_\ell$ neurons of the form (2). The skip path preserves coverage, while the ReLU branch tries to increase it. Indeed, $\operatorname{col}([H_\ell,1])\supseteq\operatorname{col}(\Phi)$ for every $\Theta_\ell$, so $s_K$ is nonincreasing (Lemma 3.2) and $N_K$ nondecreasing in $\ell$. Rows that are distinct in $H_{\ell-1}$ stay distinct, so the ceiling of Corollary 5.2 never drops and Theorem 5.1 applies at every layer. The branch contributes exactly the marginal gains $G_\Phi$ of Proposition 4.5: all $k_\ell$ branch neurons are free to add coverage, Theorem 5.3(a) with $H=\Phi$ guarantees that one can unless $N_K(\Phi)=N_K(V_P)$, and Theorem 5.10 applies with $H^{(0)}=\Phi$. The additive skip $H_\ell=H_{\ell-1}+R_\ell\Omega_\ell$ of residual networks mixes the branch into the existing features, so $\operatorname{col}([H_\ell,1])$ need not contain $\operatorname{col}(\Phi)$; we leave its analysis to future work.

How fast can a layer increase coverage?

Theorem 5.3 guarantees a positive gain but not its size. Width $q$ trivially attains the ceiling (Theorem 5.1(b)), and for distinct rows $q=n$, which makes $\operatorname{col}(Z)=\mathbb{R}^n$ and $g=f$. The relevant question is therefore how much coverage $t\ll n$ neurons provide. This depends on how economically ReLU features represent the low eigenvectors.

Proof. For every $d \in A_{\Phi}$ we have $\lVert M_H^{\mathsf T}d\rVert\le\sqrt{G^{*}}\lVert(I-\Pi_H)d\rVert\le\sqrt{G^{*}}$; this also holds if $d \in\operatorname{col}(H)$, since then $M_H^{\mathsf T}d=U_K^{\mathsf T}(I-\Pi_H)d=0$. Let $x$ be a unit vector with $M_H^{\mathsf T}M_Hx=s^2x$, and write $U_Kx=v+e$ with $v=\sum_j a_jd_j$, $\sum_j\lvert a_j\rvert\le\kappa+\eta$ for arbitrary $\eta>0$, and $\lVert e\rVert\le\varepsilon$. Since $M_H^{\mathsf T}M_H=U_K^{\mathsf T}(I-\Pi_H)U_K=M_H^{\mathsf T}U_K$,

Let $\eta\to0$ and rearrange.

Proof. By Lemma 3.2, $s_t$ is nonincreasing, so the steps with $s_t\ge2\varepsilon$ form an initial segment. On it, $s_t-\varepsilon\ge s_t/2$, and Lemma 3.5(iv) with $\operatorname{rank}M_{H^{(t)}}\le K$ gives $s_t^2\ge\delta_t/K$. Lemma 5.9 then gives a gain of at least $\alpha s_t^4/(4\kappa^2)\ge c\delta_t^2$ with $c=\alpha/(4K^2\kappa^2)$, so $\delta_{t+1}\le\delta_t-c\delta_t^2$. If $\delta_{t+1}>0$ then $c\delta_t<1$ and

and induction gives the bound on $\delta_t$. If $\delta_{t+1}=0$, all later deficits and gaps vanish. Hence on the initial segment $s_t^2\le\delta_t\le1/(ct)=4K^2\kappa^2/(\alpha t)$, and after it $s_t<2\varepsilon$. The final claim is Corollary 3.1 combined with Lemma 3.2, which gives $s_K(Z)\le s_t$.

Remark 5.11. Theorem 5.10 is the $O(1/t)$ rate of greedy approximation in Hilbert space [15, 16, 17], applied to subspace coverage rather than to a single target. The candidate neurons can be produced by the fixed-gating formulation of Propositions 4.3 and 4.5, but the theorem requires an $\alpha$-approximate maximizer of the gain over all gating patterns, which a local method does not certify. The bound is informative only when $\kappa$ is small enough that $4K^2\kappa^2/\alpha\ll n$.

Here $\varepsilon$ measures how far the low eigenvectors are from piecewise constant on the clusters, and Davis–Kahan bounds [8] control it through the between-cluster edge weight relative to $\lambda_{K+1}$. By Theorem 5.10, about $16K^3 \max_c \omega_c^2/(\alpha s^2)$ greedy neurons reach coverage gap $s \ge2\varepsilon$, independently of $n$.

What no layer can do

Proof. By monotonicity of $N_K$ and Lemma 3.2, it suffices to treat $\operatorname{col}(Z)=\operatorname{col}(\Phi)+T$. Let $Q_T$ be an orthonormal basis of $(I-\Pi_\Phi)T$, so $Q_T$ has at most $t$ columns and $\Pi_Z=\Pi_\Phi+Q_TQ_T^\top$. Then $I-\Pi_Z=(I-Q_TQ_T^\top)(I-\Pi_\Phi)$, so $M_Z=(I-Q_TQ_T^\top)M_\Phi$ and

a positive semidefinite downdate of rank at most $t$. Weyl’s inequality [4] gives $\lambda_i(M_Z^\top M_Z)\ge\lambda_{i+t}(M_\Phi^\top M_\Phi)=\eta_{i+t}^2$ for every $i$. Taking $i=1$ gives the bound on $s_K$. Summing over $i\le K$ gives $\delta(Z)\ge\sum_{i>t}\eta_i^2$, and since $\delta(\Phi)=\sum_i\eta_i^2$, this is the bound on $N_K$. For attainment, the left singular vectors of $M_\Phi$ lie in $\operatorname{col}(\Phi)^\perp$, and removing the top $t$ of them leaves exactly the singular values $\eta_{t+1},\eta_{t+2},\ldots$.

Remark 5.14. Increasing $N_K$ and decreasing $s_K$ are different goals. A single neuron can strictly decrease $s_K$ only if the largest singular value of $M_\Phi$ is simple, and pushing $s_K$ below a level $c$ requires at least as many new neurons as there are $\eta_i>c$. Theorem 5.13 is the unconstrained (Ky Fan) benchmark; Theorem 5.10 quantifies how closely ReLU neurons approach it. Together with Theorem 5.3, this is the precise sense in which the neurons left free by Proposition 3.3 add coverage.

Concluding remarks

Remark 6.1 (Reduction to the smoothness of the target, and future work). By Lemma 3.5(iv), $s_K(Z)^2 \le K-N_K(Z)$, so Corollary 3.1 gives, for $\lambda_{K+1}>0$,

Hence $s_K(Z)\to0$ as $N_K(Z)\to K$, and the error reduces to the smoothness component: once $N_K(Z)=K$, $\lVert g-f\rVert\le E(f)/\sqrt{\lambda_{K+1}}$. By Corollary 5.2 this is attainable whenever the rows of $H_{p-1}$ are distinct, and Theorem 5.10 bounds how many greedily chosen neurons it takes. Two directions remain for future work. First, the remaining term $E(f)/\sqrt{\lambda_{K+1}}$ depends only on $f$ and the graph, so we will investigate how to choose the graph, and hence the Laplacian $\mathcal{L}$, to minimize this smoothness component; since $\mathcal{L}$ also determines $U_K$, this has to be balanced against the coverage the network can achieve. Second, Theorem 5.10 assumes an $\alpha$-approximate maximizer of the gain over all gating patterns (Remark 5.11); we will develop methods that find maximal-gain neurons using the fixed-gating formulation of Proposition 4.3, applied to the marginal gain through Proposition 4.5, by searching over gating patterns and solving the resulting cone-constrained generalized eigenvalue problems.

References