New and Explicit Constructions of Unbalanced Ramanujan Bipartite Graphs
The objectives of this article are three-fold. Firstly, we present for the first time explicit constructions of an infinite family of \textit{unbalanced} Ramanujan bigraphs. Secondly, we revisit some of the known methods for constructing Ramanujan graphs and discuss the computational work required in actually implementing the various construction methods. The third goal of this article is to address the following question: can we construct a bipartite Ramanujan graph with specified degrees, but with the restriction that the edge set of this graph must be distinct from a given set of "prohibited" edges? We provide an affirmative answer in many cases, as long as the set of prohibited edges is not too large.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Ramanujan Bipartite Graph Products for Efficient Block Sparse Neural Networks
Sparse neural networks are shown to give accurate predictions competitive to denser versions, while also minimizing the number of arithmetic operations performed. However current hardware like GPU's can only exploit stru…
GPUimage-classificationImage ClassificationRevisiting the Lottery Ticket Hypothesis: A Ramanujan Graph Perspective
Neural networks often yield to weight pruning resulting in a sparse subnetwork that is adequate for a given task. Retraining these `lottery ticket' subnetworks from their initialization minimizes the computational burden…
Ramanujan Graph Rewiring with Non Negative Resistance Curvature
Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes of…
ByzShield: An Efficient and Robust System for Distributed Training
Training of large scale models on distributed clusters is a critical component of the machine learning pipeline. However, this training can easily be made to fail if some workers behave in an adversarial (Byzantine) fash…
image-classificationImage ClassificationGauss-Ramanujan Functions: Constructions, Properties, and Applications in Communications and Signal Processing
In this article, I construct a new set of functions based on Ramanujan sequences (RSEs), Gaussian pulse (GP), and its delayed Gaussian pulse (DGP). The motivation for this construction is based on the special properties …
Benchmarking