# Deep Expander Networks: Efficient Deep Networks from Graph Theory

arXiv: https://arxiv.org/abs/1711.08757 · HTML: https://mlsanity.com/paper/1711.08757/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2017.

## Built on by (most cited first, 23 of 23)

- [The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training](https://mlsanity.com/paper/2202.02643/) (2022)
- [Expander Graph Propagation](https://mlsanity.com/paper/2210.02997/) (2022)
- [PolyLUT: Learning Piecewise Polynomials for Ultra-Low Latency FPGA LUT-based Inference](https://mlsanity.com/paper/2309.02334/) (2023)
- [Selfish Sparse RNN Training](https://mlsanity.com/paper/2101.09048/) (2021)
- [NeuraLUT: Hiding Neural Network Density in Boolean Synthesizable Functions](https://mlsanity.com/paper/2403.00849/) (2024)
- [Truly Sparse Neural Networks at Scale](https://mlsanity.com/paper/2102.01732/) (2021)
- [Sparse Training Theory for Scalable and Efficient Agents](https://mlsanity.com/paper/2103.01636/) (2021)
- [Even Sparser Graph Transformers](https://mlsanity.com/paper/2411.16278/) (2024)
- [N2NSkip: Learning Highly Sparse Networks using Neuron-to-Neuron Skip Connections](https://mlsanity.com/paper/2208.03662/) (2022)
- [Don't Be So Dense: Sparse-to-Sparse GAN Training Without Sacrificing Performance](https://mlsanity.com/paper/2203.02770/) (2022)
- [Superposing Many Tickets into One: A Performance Booster for Sparse Neural Network Training](https://mlsanity.com/paper/2205.15322/) (2022)
- [In defense of parameter sharing for model-compression](https://mlsanity.com/paper/2310.11611/) (2023)
- [Partitioning sparse deep neural networks for scalable training and inference](https://mlsanity.com/paper/2104.11805/) (2021)
- [Brain network science modelling of sparse neural networks enables Transformers and LLMs to perform as fully connected](https://mlsanity.com/paper/2501.19107/) (2025)
- [Pruning Before Training May Improve Generalization, Provably](https://mlsanity.com/paper/2301.00335/) (2023)
- [Sparsifying the Update Step in Graph Neural Networks](https://mlsanity.com/paper/2109.00909/) (2021)
- [Understanding Sparse Neural Networks from their Topology via Multipartite Graph Representations](https://mlsanity.com/paper/2305.16886/) (2023)
- [REST: Enhancing Group Robustness in DNNs through Reweighted Sparse Training](https://mlsanity.com/paper/2312.03044/) (2023)
- [Sparse Super-Regular Networks](https://mlsanity.com/paper/2201.01363/) (2022)
- [Testing RadiX-Nets: Advances in Viable Sparse Topologies](https://mlsanity.com/paper/2311.03609/) (2023)
- [Empowering Precision Medicine: AI-Driven Schizophrenia Diagnosis via EEG Signals: A Comprehensive Review from 2002-2023](https://mlsanity.com/paper/2309.12202/) (2023)
- [Graph Expansion in Pruned Recurrent Neural Network Layers Preserve Performance](https://mlsanity.com/paper/2403.11100/) (2024)
- [EGGS-PTP: An Expander-Graph Guided Structured Post-training Pruning Method for Large Language Models](https://mlsanity.com/paper/2508.09471/) (2025)

## Abstract (arXiv)

Efficient CNN designs like ResNets and DenseNet were proposed to improve accuracy vs efficiency trade-offs. They essentially increased the connectivity, allowing efficient information flow across layers. Inspired by these techniques, we propose to model connections between filters of a CNN using graphs which are simultaneously sparse and well connected. Sparsity results in efficiency while well connectedness can preserve the expressive power of the CNNs. We use a well-studied class of graphs from theoretical computer science that satisfies these properties known as Expander graphs. Expander graphs are used to model connections between filters in CNNs to design networks called X-Nets. We present two guarantees on the connectivity of X-Nets: Each node influences every node in a layer in logarithmic steps, and the number of paths between two sets of nodes is proportional to the product of their sizes. We also propose efficient training and inference algorithms, making it possible to train deeper and wider X-Nets effectively. Expander based models give a 4% improvement in accuracy on MobileNet over grouped convolutions, a popular technique, which has the same sparsity but worse connectivity. X-Nets give better performance trade-offs than the original ResNet and DenseNet-BC architectures. We achieve model sizes comparable to state-of-the-art pruning techniques using our simple architecture design, without any pruning. We hope that this work motivates other approaches to utilize results from graph theory to develop efficient network architectures.