acceptodds
Under review as a conference paper at ICLR 2027

Expanders meet Expressivity: Universal Approximation on fixed sparse masks

Abstract

Recent work on pruning and the lottery-ticket hypothesis suggests that the graph topology of a sparse subnetwork matters for its performance. Spectral expanders and Ramanujan graphs have emerged as promising masks: they combine sparsity with strong global connectivity, and empirical studies report high accuracy and, in some settings, robustness to noise, even at high sparsity. Whether such masks are justified by approximation theory has remained open. Prior results establish that sparse masks without a spectral gap can emulate ReLU networks with unbounded depth and signed weights. Can a fixed, constant-degree expander mask do so efficiently, with the connections responsible for expansion carrying the computation themselves? We answer affirmatively for ReLU networks. Using auxiliary Ramanujan graphs, we build for every admissible width a three-regular mask, independent of the target and repeated in every layer, whose connections both give it a width-independent spectral gap and route values through the network. Networks on these masks represent exactly every ReLU network, with width linear in the number of neurons and nonzero weights per layer and polylogarithmic depth overhead per layer. Expansion also makes this representation robust to pruning. In a block version of the mask built from a bipartite expander, exact representation survives the deletion of a fixed fraction of the connections between each pair of connected blocks in every layer, with the remaining weights chosen afterwards; a same-degree construction without expansion loses input dependence under an allowed pruning. We also separate spectral expansion from routing: a width-seven Ramanujan mask, stacked any number of times, cannot realise every permutation of its neurons by moving values along vertex-disjoint paths. Moreover, we give uniform approximation rates with explicit width, depth and accuracy, including constructions with bounded weights and activations. We also obtain encoding lengths of optimal order for H\"older classes with exponent at most one under a fixed decoder, extend the results to compositions of Lipschitz functions that each depend on few variables, and prove stability bounds under perturbation of all weights. These results show that expander topology is compatible with efficient exact representation, complementing the empirical success of expander and Ramanujan masks in pruning and lottery-ticket settings.

Primary area:
learning theory
Keywords:
universal approximation, expressivity, sparse neural networks, spectral expanders, Ramanujan graphs, pruning, ReLU networks

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_w9BKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether a fixed, target-independent sparse connectivity pattern can retain the expressive power of general ReLU networks while also having a width-independent spectral gap. For each admissible width, the authors construct a three-regular mask An=I+C+RA_n = I + C + R, reuse the same mask across all hidden layers, and prove that it can exactly simulate bounded fan-in/fan-out ReLU networks with poly logarithmic depth overhead. General ReLU networks are then handled through a bounded fan-in/fan-out reduction. The paper further derives universal approximation, explicit approximation rates, bounded-weight and encoding results, compositional approximation, pruning robustness, and perturbation stability.

Critical strengths

The main exact-representation result is strong and technically interesting. In particular, the same degree-three mask simultaneously provides a width-independent spectral gap and supports the permutation routing needed for exact ReLU simulation. Degree 3 is also shown to be the smallest regular degree compatible with a uniform spectral gap.

The paper makes a useful distinction between spectral expansion and routing. The paper does not assume that good spectral expansion is sufficient for computation. It gives a Ramanujan counterexample that cannot route every permutation and then proves the required routing property separately for the proposed construction.

Critical weaknesses

My main concern is positioning with respect to closely related expander-based universality results. In particular, Exphormer (Shirzad et al., ICML 2023) uses constant-degree expander structure in sparse attention and proves universal approximation for suitable sparse Transformer architectures. This does not appear to subsume the present result—the degree-three repeated ReLU mask and exact simulation theorem here seem different—but the distinction should be discussed explicitly.

The exact representation theorem is also specific to a carefully engineered mask family. It does not establish guarantees for arbitrary three-regular expanders, random regular masks, or generic Ramanujan masks. The authors acknowledge this and identify these extensions as open problems. The auxiliary graphs are supplied through an existence theorem, so the algorithmic constructivity of the family could be clarified.

Questions for authors
  1. Exphormer also combines constant-degree expander structure with a universal-approximation result for sparse attention. What is the precise distinction between its universality result and the present one?

  2. I understand this is a theoretical paper and do not view the absence of experiments as an issue. Could the authors comment on the practical implications of the proposed mask construction?

  3. Since the auxiliary graphs are supplied through an existence result, can the authors clarify whether AnA_n can be deterministically constructed for every admissible width?

Reviewer_qfXvOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper considers the expressive power and universal approximation for neural networks (with ReLU) and sparse expander masks. Authors show that for a specific type of expanders masks the expressive power does not decrease in these terms, which allows them to show universal approximation. This is a theory paper with no experiments.

Critical strengths

The research direction is interesting, universal approximation for fixed expander masks is underdeveloped and providing results in this direction is important.

The paper makes honest limitations explanation in the end, as well as open questions, which make it valuable for the community.

Critical weaknesses

The masks considered in the paper do not seem to be used in the practice, and it is not clear how important focusing on such masks is.

The presentation of the paper has significant drawbacks, which in a theoretical paper of this form is a crucial gap. In particular, many notions are not explained, statement of theorems is not precise, and so, it is hard to follow the paper and check the correctness of the statements.

For example, the central symbol F_An ,L,θ for Definition 2.1 is never defined. Definition 2.2 is imprecise and confusing; it is not clear what does it mean that positions are “fixed in advance”, and also it is not clear what means that “values depend on target” - there is no target mentioned so far. Furthermore, it is not clear what does it mean that “Every ReLU network can be converted into this bounded fan-in normal form”. The bounded fan-in normal form network needs to have permitted entries fixed in advance, but how is it guaranteed and in what sense by the translation from Appendix G, is not explained. As stated, I do not see how such a statement can be proved.

Theorem 3.1 states that a network is “represented exactly by” a given “constant mask sequence”, but such notions were not defined in the paper. Although after reading the previous parts of the paper a reader can get some intuitions what it could mean, it was never explained what exact representations by a mask means, and what is a constant mask.

The description of the construction in “How the masks are built.“ is complicated and lacks details so that it cannot be understood and does not provide a reader with proper intuitions.

Theorem 3.3 seems to have significant problems. There is both A and A_n but it is not clear what is the relation between them; is it the same? Also it is not specified what is gamma and if it can be any number. Actually, I do not think gamma can be 0 or negative, but it is not stated. Also the way Theorem 3.3 is written without explaining all the assumptions and elements occurring there, by moving all this to the paragraph before the theorem, makes the statement imprecise.

Proposition 3.4 also is unclear. For example it starts by stating “Index rows and columns” but it is not even specified in which matrix we index rows and columns. Also, Heawood graphs were never explained, and “neurons along vertex-disjoint paths” is not defined.

Paper has many other unclear statements, for example in Theorem 5.1 “batch conditions of Theorem 4.2” are not clear. I do not think the paper explains what “batch conditions” are, so it is not clear what exactly conditions are used in this theorem.

Questions for authors

Can you please explain if, and what, connection exists between the masks considered in the paper and those used in practice?

Reviewer_edseOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper shows that a single fixed, sparse, expander-style connectivity pattern, reused in every layer, can exactly reproduce any ReLU network. The cost is a polylogarithmic increase in depth. From this the authors derive a universal approximation with explicit rates and near-optimal encoding lengths. they also show that if one build each connection point from a small group of redundant neurons, one can remove a fraction of the connections and still get the exact same network, as long as one set the weights after the removal. A small example separates good spectral expansion from the ability to route values. The work is purely theoretical, with no experiments beyond a numerical check of the spectral gap.

Critical strengths

The paper answers a clean, open question with explicit proof. The authors build one a simple pattern that repeat in every layer and independent of the task, in which each neuron has exactly three connections. Information still mixes well across the whole network, and this does not degrade as the network gets wider. Networks on this pattern can reproduce any ReLU network exactly, and three connections is the smallest number that makes this possible. The result is simple and verifiable and it shows choosing sparse, well-connected wiring does not rule out good solutions.

Critical weaknesses

I have three main concerns about this paper. First, the construction has little connection to the practical work that motivates it. The empirical papers study random or Ramanujan masks that are subsets of a dense layer at fixed width, whereas this paper builds one custom pattern that is not Ramanujan and needs a network far wider than the one it copies. So the claim that selecting masks by their spectral properties is compatible with full expressivity is overstated, because the result covers only this one family. Second, the pruning theorem is presented as showing that expansion gives robustness, but its tolerance depends only on how well the small block graph mixes. A fully connected block tolerates more deletions at the same connection count, and the paper's counter-example is a disconnected block, which shows that connectivity matters but not expansion. The weights are also re-chosen after the deletions, so the result does not apply to pruning a trained network. Third, the quantitative overheads are too large to mean anything in practice. With the unspecified routing constant set to 1, simulating a single dense layer of width 1024 would take about 7×10⁷ masked layers and about 5.6×10⁸ times the original parameter count.

Questions for authors
  1. I don't see where expansion is needed in the authors' pruning result. A fully connected block tolerates even more deleted connections at the same connection count. What does the expander block give the authors that the fully connected one doesn't? Can they also show a block that is connected but mixes poorly, where an allowed pruning breaks the result? Without one, their counter-example only shows that connectivity matters, not expansion.
  2. The authors' depth bound hides a large constant. What is the actual constant from the routing theorem they use, and how many layers does one simulated layer need at a realistic width, say 1024? I would also like the authors to compute the true routing number for a few small widths, to show how loose the bound is.
  3. The authors are motivated by the empirical work on random and Ramanujan masks, but their construction is one custom pattern that is not Ramanujan. Can they prove anything for random or Ramanujan masks, or for masks that are subsets of a dense layer at fixed width? If not, I am unsure how to read their claim that choosing masks by their spectral properties is compatible with full expressivity.
  4. Expansion seems to shorten routing only from O(n) to O(log² n), while non-expanding switching networks already route in O(log n). I wonder why the authors do not repeat a fixed shuffle-exchange stage and add one extra connection per neuron. That would plausibly give O(log n) overhead at degree 3. Would that change what they say expansion contributes?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.