TY - GEN

T1 - A Study on the Ramanujan Graph Property of Winning Lottery Tickets

AU - Pal, Bithika

AU - Biswas, Arindam

AU - Kolay, Sudeshna

AU - Mitra, Pabitra

AU - Basu, Biswajit

N1 - Publisher Copyright: Copyright © 2022 by the author(s)

PY - 2022

Y1 - 2022

N2 - Winning lottery tickets refer to sparse subgraphs of deep neural networks which have classification accuracy close to the original dense networks. Resilient connectivity properties of such sparse networks play an important role in their performance. The attempt is to identify a sparse and yet well-connected network to guarantee unhindered information flow. Connectivity in a graph is best characterized by its spectral expansion property. Ramanujan graphs are robust expanders which lead to sparse but highly-connected networks, and thus aid in studying the winning tickets. A feed-forward neural network consists of a sequence of bipartite graphs representing its layers. We analyze the Ramanujan graph property of such bipartite layers in terms of their spectral characteristics using the Cheeger's inequality for irregular graphs. It is empirically observed that the winning ticket networks preserve the Ramanujan graph property and achieve a high accuracy even when the layers are sparse. Accuracy and robustness to noise start declining as many of the layers lose the property. Next we find a robust winning lottery ticket by pruning individual layers while retaining their respective Ramanujan graph property. This strategy is observed to improve the performance of existing network pruning algorithms.

AB - Winning lottery tickets refer to sparse subgraphs of deep neural networks which have classification accuracy close to the original dense networks. Resilient connectivity properties of such sparse networks play an important role in their performance. The attempt is to identify a sparse and yet well-connected network to guarantee unhindered information flow. Connectivity in a graph is best characterized by its spectral expansion property. Ramanujan graphs are robust expanders which lead to sparse but highly-connected networks, and thus aid in studying the winning tickets. A feed-forward neural network consists of a sequence of bipartite graphs representing its layers. We analyze the Ramanujan graph property of such bipartite layers in terms of their spectral characteristics using the Cheeger's inequality for irregular graphs. It is empirically observed that the winning ticket networks preserve the Ramanujan graph property and achieve a high accuracy even when the layers are sparse. Accuracy and robustness to noise start declining as many of the layers lose the property. Next we find a robust winning lottery ticket by pruning individual layers while retaining their respective Ramanujan graph property. This strategy is observed to improve the performance of existing network pruning algorithms.

UR - http://www.scopus.com/inward/record.url?scp=85163129717&partnerID=8YFLogxK

M3 - Article in proceedings

AN - SCOPUS:85163129717

VL - 162

T3 - Proceedings of Machine Learning Research

SP - 17186

EP - 17201

BT - Proceedings of the 39 th International Conference on Machine Learning

PB - PMLR

T2 - 39th International Conference on Machine Learning, ICML 2022

Y2 - 17 July 2022 through 23 July 2022

ER -