When graph learners use eigenvectors of a graph's Laplacian, they usually first regularize it. A Laplacian is the matrix that encodes how each node differs from its neighbors. Regularizing it means adding a constant $\tau$ to every node's degree, or adding a faint uniform background edge between all pairs of nodes. This is the trick that makes spectral clustering work on sparse, hub-heavy networks. It is also, in spirit, what recent "stable" positional encodings for graph neural networks do. This note argues that the trick has a precise logical cost. Once $\tau > 0$, every spectral feature of the regularized operator, computed to precision $\varepsilon$, equals a count of weighted walks of bounded length $k(\tau,\varepsilon)$. Counts of that kind are exactly what constant-depth counting logics and constant-depth arithmetic circuits compute. So a regularized spectral feature cannot robustly tell apart two graphs that a short-horizon counting test already confuses.
The payoff is a pair-by-pair, falsifiable prediction about expressiveness. On the BREC benchmark of hard non-isomorphic graph pairs, a regularized spectral model should separate a pair only if a 3-variable counting refinement separates it within about $k(\tau,\varepsilon)$ rounds. The margin should shrink geometrically beyond that point. Arithmetic precision (float16 versus float64) should shift the boundary by an amount the formula predicts. If this holds, the familiar trade-off between stability and expressiveness becomes a quantitative statement about quantifier depth, and choosing $\tau$ becomes a choice of how many rounds of logic one is willing to pay for.
Core Claim
Write $A$ for the adjacency matrix and $D$ for the diagonal degree matrix. The regularized operator used in regularized spectral clustering (Qin and Rohe) is $M_\tau = (D+\tau I)^{-1/2} A (D+\tau I)^{-1/2}$. Let $\theta = \tau/(d_{\max}+\tau)$ be the relative regularization strength, where $d_{\max}$ is the largest degree. Factor $M_\tau$ as the usual normalized adjacency $D^{-1/2}AD^{-1/2}$, whose eigenvalues lie in $[-1,1]$, scaled on both sides by $\sqrt{d_i/(d_i+\tau)}$. This gives an elementary spectral bound:
$$\|M_\tau\|_2 \le 1-\theta .$$
So the resolvent $R_\tau=(I-M_\tau)^{-1}=\sum_{j\ge 0} M_\tau^j$, and any spectral filter that is analytic on the shrunken spectrum, is captured to precision $\varepsilon$ by its first $k$ terms. Here
$$k(\theta,\varepsilon)=O\!\left(\tfrac{1}{\theta}\log\tfrac{1}{\theta\varepsilon}\right),$$
which follows from the geometric tail $(1-\theta)^{k}/\theta$. Each term $M_\tau^j$ is a degree-weighted count of length-$j$ walks.
The first new statement is the margin lemma. Suppose graphs $G$ and $H$ cannot be told apart by 3-variable counting refinement (the logic matched to 2-WL/3-WL-style tests) for the first $c\cdot k$ rounds, where $c$ is a constant fixed by how many rounds one walk step costs. Then the multisets of their resolvent features agree on the truncated part. Under the best matching, they differ entrywise by at most $2(1-\theta)^{k+1}/\theta$. Distinguishing power therefore decays geometrically in the refinement depth at which a pair first separates, with rate set by $\theta$.
This places regularized spectral features in a definite position across all three directions. The integer walk counts are counts of witnesses (Skolem functions) for a chain of guarded existential formulas. These are $\#\mathrm{AC}^0$ functions in the sense of Durand et al. and Haak and Vollmer, who show that counting proof trees of constant-depth arithmetic circuits equals counting winning strategies in first-order model-checking games. The full real-valued feature, including the $(d_i+\tau)^{-1/2}$ weights, is a formula of first-order logic over the reals with sum and product aggregation. Barlag and Vollmer prove that this logic captures uniform constant-depth real circuits. Two regimes follow. For constant $\theta$ and constant $\varepsilon$, the depth is constant. For polynomial precision $\varepsilon = 1/\mathrm{poly}(n)$, the depth is logarithmic, matching logarithmic-quantifier-depth recursion (Simulating Logspace-Recursion with Logarithmic Quantifier Depth). The second regularizer, background thickening $A+\tfrac{\gamma}{n}\mathbf{1}\mathbf{1}^T$ (Cucuringu et al.), is a rank-one update. Multiplying any vector by it adds one unguarded global sum. In Grohe's terms, it turns edge-guarded counting into counting with a global readout (Grohe).
Relation to Prior Work
Three papers motivate the gap. Zhang, Zhao and Maron prove that spectral invariant networks such as EPNN are strictly below 3-WL. Their analysis uses exact eigenspaces of unregularized operators and says nothing about precision or regularization. Our lemma refines their ceiling: for regularized operators, the bound depends on depth and precision, not just the WL level. Zhou et al. introduce smooth eigenvalue masks (OGE-Aug) to remove instability when eigenvalues split under small perturbations. They argue entirely through symmetry and perturbation theory. We claim that their smoothness is what makes the features short polynomials, and hence low-depth formulas. Feldman et al. use heat-kernel pre-colorings to get past 1-WL, for example on Decalin versus Bicyclopentyl. This is consistent with our picture: closed-walk counts need three variables, not two, so they exceed 1-WL while staying bounded.
The method comes from two lines of work. The descriptive characterizations of Haak and Vollmer, Barlag and Vollmer, and Barlag, Chudigiewitsch and Gaube supply the target logics. The concentration theory of regularized operators (Qin and Rohe; Chung and Tsiatas) supplies the operators and the average-degree heuristic for $\tau$.
One constraint has to be faced directly. Grohe's result that GNNs with random initialization and global readout equal $\mathrm{TC}^0$ means a circuit-class statement alone is weak, because threshold circuits already contain everything here. The content of this proposal is therefore the quantitative margin-versus-depth law, not a new class inclusion. Real circuits are already closed under majority because of sign gates (Barlag and Vollmer), which makes the same point.
Research Program
The theoretical part has three pieces. The first is a proof of the margin lemma for $M_\tau$ and for Chebyshev-approximable filters, with explicit constants. This includes the constant $c$ relating walk length to refinement rounds once degree weights are folded in; degrees are definable at quantifier depth one. The second is a matching lower bound family: pairs whose first separating depth is $k^*$ and whose regularized-feature margin actually decays like $(1-\theta)^{k^*}$. Circulant and CSL-style graphs are natural candidates. The third is the thickened case, showing which pairs that are 1-WL-equivalent but separable by global counting become separable once $\gamma > 0$.
The practical part has one corollary. In power-law graphs, $\theta$ under the average-degree rule is roughly $\bar d/d_{\max}$, so the effective depth grows like $d_{\max}/\bar d$. The theory therefore predicts when the heuristic quietly makes features deep, and hence unstable. We will test this rule against the current heuristic.
On the empirical side, we build a regularized EPNN that feeds eigenspace projections of $M_\tau$ into the EPNN architecture, with $\tau$ swept from $0$ to several multiples of $d_{\max}$. We also build a "walk-truncation" twin, which replaces the spectral computation with explicit degree-weighted walk-count matrices up to length $k(\theta,\varepsilon)$. For every BREC pair, we compute the first separating depth $k^*$ of 3-variable counting refinement. This is the per-pair predictor.
Baselines
The naive reference points are a plain message-passing network (GIN), which is 1-WL-bounded and should fail every non-Basic BREC pair, and unregularized EPNN ($\tau=0$). Zhang et al. report an EPNN BREC total score of 53.8, against 58.2 for PPGN and 19.8 for Graphormer. EPNN is the strongest competitor on the precise question, because it is the spectral architecture whose ceiling we refine. PPGN, a 3-WL-equivalent network, is the upper reference that regularized spectral features should never exceed. The best overall BREC model in the BREC paper, $I^2$-GNN at 70.2%, is reported only for context; it uses subgraph machinery outside our scope.
All spectral variants share the EPNN code path, the BREC Reliable Paired Comparison protocol and threshold, the same seeds, and the same per-model hyperparameter budget. Only $\tau$, $\gamma$ and numerical precision vary.
For downstream tasks, the comparison point is OGE-Aug on ZINC12k, where Zhou et al. report an MAE of 0.064. For clustering, it is regularized spectral clustering on the 2004 political blog network, where Qin and Rohe report roughly 80 of 1,222 nodes mis-clustered. On the signed SSBM, Cucuringu et al. report results via Adjusted Rand Index, but no reported numeric result was found on Lacuna for specific SSBM runs, so we rerun SPONGEsym ourselves.
The key ablation is the walk-truncation twin. If it matches the regularized EPNN pair-for-pair on BREC, then the spectral computation contributes nothing beyond bounded-length walk counting, and the claim is confirmed. "Beating" here means our per-pair predictor forecasts which BREC pairs a $\tau$-regularized model separates better than competing predictors. We do not claim a higher BREC score.
Why not just…?
Why not just say a truncated Neumann series is a polynomial filter, which everyone knows? That part is elementary, and we treat it as a tool. What is not known is the per-pair consequence. Zhang et al. give only a level in the WL hierarchy and no rate. The margin lemma predicts which specific pairs become inseparable at a given $\tau$ and precision. That prediction can fail, and the BREC sweep tests it.
Why not just explain BREC failures with eigengap-based perturbation bounds (Davis–Kahan style)? This is the real competitor. Perturbation bounds explain how one graph's features move under noise, as in Cucuringu et al.'s concentration argument. They do not say which pairs of graphs collapse onto each other. We will fit both predictors to BREC outcomes across the $\tau$ sweep: the minimum eigengap of each pair, and our first separating depth $k^*$ combined with $\theta$. If the eigengap predictor matches ours in held-out ranking quality (AUC), the logical account adds nothing and we will report that.
Why not just grid-search $\tau$ on the downstream task? For supervised tasks this may well be enough, and we include it as a baseline. The theory is not needed to tune performance. It is needed to explain the curve and to set $\tau$ when no labels exist, as in clustering, where all three regularization papers cite parameter choice as open. The test is whether the depth-aware rule matches the grid-search optimum on political blogs and SSBM without labels.
Why not just use 3-WL networks? They subsume all of this expressively, but at cubic cost and with optimization trouble reported in Benchmarking Graph Neural Networks. We use PPGN as a ceiling, not as a competitor.
Decisive Checks
Four results would settle the claim. First, across the $\tau$ sweep, the fraction of BREC Regular and Extension pairs separated by regularized EPNN should fall as $\tau$ grows. Pairs with $k^*$ above $k(\theta,\varepsilon)$ should drop out first, and CFI pairs should stay near the reported 0–10% regardless of $\tau$. Second, changing precision from float64 to float32 to float16 changes $\varepsilon$. It should move the separation boundary in $k^*$ by roughly the predicted $\log(1/\varepsilon)/\theta$ shift. This is the sharpest test, because nothing else in the pipeline changes. Third, the walk-truncation twin should track the regularized EPNN within seed noise on BREC, CSL and ZINC12k. Fourth, the background-thickened operator should recover pairs that are 1-WL-hard but separable by global counting, and should not recover any others.
A clear failure on the second or third check would falsify the account. That would mean regularized spectra carry information that bounded-depth counting misses. That outcome would be informative too.
References
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Descriptive Complexity of #AC0 Functions
- A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
- A Logical Characterization of Constant-Depth Circuits over the Reals
- Simulating Logspace-Recursion with Logarithmic Quantifier Depth
- Regularized spectral methods for clustering signed networks
- The Descriptive Complexity of Graph Neural Networks
- On the Expressive Power of Spectral Invariant Graph Neural Networks
- Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors
- Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
- Logical characterizations of algebraic circuit classes over integral domains
- Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model
- Towards Better Evaluation of GNN Expressiveness with BREC Dataset
- Benchmarking Graph Neural Networks