Ramanujan Bipartite Graph Products for Efficient Block Sparse Neural
Networks
- URL: http://arxiv.org/abs/2006.13486v2
- Date: Thu, 2 Jul 2020 12:22:52 GMT
- Title: Ramanujan Bipartite Graph Products for Efficient Block Sparse Neural
Networks
- Authors: Dharma Teja Vooturi, Girish Varma, Kishore Kothapalli
- Abstract summary: We propose framework for generating structured multi level block sparse neural networks by using the theory of Graph products.
We also propose to use products of Ramanujan graphs which gives the best connectivity for a given level of sparsity.
We benchmark our approach by experimenting on image classification task over CIFAR dataset using VGG19 and WideResnet-40-4 networks.
- Score: 2.4235475271758076
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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 structured
sparsity patterns for better efficiency. Hence the run time of a sparse neural
network may not correspond to the arithmetic operations required.
In this work, we propose RBGP( Ramanujan Bipartite Graph Product) framework
for generating structured multi level block sparse neural networks by using the
theory of Graph products. We also propose to use products of Ramanujan graphs
which gives the best connectivity for a given level of sparsity. This
essentially ensures that the i.) the networks has the structured block sparsity
for which runtime efficient algorithms exists ii.) the model gives high
prediction accuracy, due to the better expressive power derived from the
connectivity of the graph iii.) the graph data structure has a succinct
representation that can be stored efficiently in memory. We use our framework
to design a specific connectivity pattern called RBGP4 which makes efficient
use of the memory hierarchy available on GPU. We benchmark our approach by
experimenting on image classification task over CIFAR dataset using VGG19 and
WideResnet-40-4 networks and achieve 5-9x and 2-5x runtime gains over
unstructured and block sparsity patterns respectively, while achieving the same
level of accuracy.
Related papers
- Hector: An Efficient Programming and Compilation Framework for Implementing Relational Graph Neural Networks in GPU Architectures [24.841128441671234]
RGNNs are graph neural networks with dedicated structures for modeling the different types of nodes and edges in heterogeneous graphs.
We propose Hector, a novel two-level intermediate representation and its code generator framework, to capture the key properties of RGNN models.
Hector achieves up to 9.9x speed-up in inference and 43.7x speed-up in training compared with the state-of-the-art public systems.
arXiv Detail & Related papers (2023-01-16T06:53:18Z) - Dynamic Graph Message Passing Networks for Visual Recognition [112.49513303433606]
Modelling long-range dependencies is critical for scene understanding tasks in computer vision.
A fully-connected graph is beneficial for such modelling, but its computational overhead is prohibitive.
We propose a dynamic graph message passing network, that significantly reduces the computational complexity.
arXiv Detail & Related papers (2022-09-20T14:41:37Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
Graph Neural Networks (GNNs) with numerical node features and graph structure as inputs have demonstrated superior performance on various supervised learning tasks with graph data.
The best models for such data types in most standard supervised learning settings with IID (non-graph) data are not easily incorporated into a GNN.
Here we propose a robust stacking framework that fuses graph-aware propagation with arbitrary models intended for IID data.
arXiv Detail & Related papers (2022-06-16T22:46:33Z) - Graph Kernel Neural Networks [53.91024360329517]
We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain.
This allows us to define an entirely structural model that does not require computing the embedding of the input graph.
Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
arXiv Detail & Related papers (2021-12-14T14:48:08Z) - Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction [22.974348682859322]
We propose a framework that can directly learn embeddings for the given netlist to enhance the quality of our node features.
By combining the learned embedding on top of the netlist with the GNNs, our method improves prediction performance, generalizes to new circuit lines, and is efficient in training, potentially saving over $90 %$ of runtime.
arXiv Detail & Related papers (2021-11-10T20:56:29Z) - Binary Graph Neural Networks [69.51765073772226]
Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data.
In this paper, we present and evaluate different strategies for the binarization of graph neural networks.
We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks.
arXiv Detail & Related papers (2020-12-31T18:48:58Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data.
Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks.
In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
arXiv Detail & Related papers (2020-11-19T06:03:35Z) - Fast Graph Attention Networks Using Effective Resistance Based Graph
Sparsification [70.50751397870972]
FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph.
We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
arXiv Detail & Related papers (2020-06-15T22:07:54Z) - Binarized Graph Neural Network [65.20589262811677]
We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters.
Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches.
Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
arXiv Detail & Related papers (2020-04-19T09:43:14Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.