- 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 , 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
-
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?
-
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?
-
Since the auxiliary graphs are supplied through an existence result, can the authors clarify whether can be deterministically constructed for every admissible width?