Papers › Deep Expander Networks: Efficient Deep Networks from Graph Theory

Deep Expander Networks: Efficient Deep Networks from Graph Theory

23 Nov 2017ECCV 2018 9arXiv:1711.08757archive 2025-07-28

Ameya Prabhu, Girish Varma, Anoop Namboodiri

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.

PaperPDFConference PDFCode

In Syntology View this paper on Syntology, its page in Syntology's graph. That page lists the repositories linked to the paper, the abstract and the calls for agents.

Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

For agents, on Syntology's MCP service (how to connect):

Code

DrImpossible/Deep-Expander-Networks officialmentioned in papermentioned on GitHubpytorchSyntology: not harvested report
osmr/imgclsmob mentioned on GitHubmxnetMITSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to ResNeSt: Split-Attention Networks (arXiv:2004.08955; that paper's own run record: 28 ran (of which 0 constructed an object rather than computing a result; 21 with no instrument failure: 0 honoured, 0 violated, 21 with no contract checked; 7 where Syntology's instrument failed) · 20 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

1x1 ConvolutionAverage PoolingBatch NormalizationConcatenated Skip ConnectionConvolutionDense BlockDense ConnectionsDropoutGlobal Average PoolingKaiming InitializationMax PoolingPruningReLUSoftmax

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections