Constructing Sparse Neural Architecture with Deterministic Ramanujan Graphs

TL;DR — A sparse neural architecture based on constructing deterministic Ramanujan graphs

Abstract

We present a sparsely connected neural network architecture constructed using the theory of Ramanujan graphs which provide comparable performance to a dense network. The method can be considered as a before-training, deterministic, weight free, pruning at initialization (PaI) technique. The deterministic Ramanujan graphs occur either as Cayley graphs of certain algebraic groups or as Ramanujan $r$-coverings of the full $(k,l)$ bi-regular bipartite graph on $k + l$ vertices. Sparse networks are constructed for bipartite graphs representing both the convolution and the fully connected layers. We experimentally show that the proposed sparse architecture provides comparable accuracy with a lower sparsity ratio than those achieved by previous approaches based on non-deterministic methods for benchmark datasets. In addition, they retain other desirable properties such as path connectivity and symmetricity.