Graph Neural Networks and Applied Linear Algebra
- URL: http://arxiv.org/abs/2310.14084v1
- Date: Sat, 21 Oct 2023 18:37:56 GMT
- Title: Graph Neural Networks and Applied Linear Algebra
- Authors: Nicholas S. Moore and Eric C. Cyr and Peter Ohm and Christopher M.
Siefert and Raymond S. Tuminaro
- Abstract summary: Graph neural networks (GNNs) are an approach suitable to sparse matrix computations.
This paper provides an introduction to GNNs for a numerical linear algebra audience.
Concrete examples are provided to illustrate how many common linear algebra tasks can be accomplished using GNNs.
- Score: 1.8749305679160366
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse matrix computations are ubiquitous in scientific computing. With the
recent interest in scientific machine learning, it is natural to ask how sparse
matrix computations can leverage neural networks (NN). Unfortunately,
multi-layer perceptron (MLP) neural networks are typically not natural for
either graph or sparse matrix computations. The issue lies with the fact that
MLPs require fixed-sized inputs while scientific applications generally
generate sparse matrices with arbitrary dimensions and a wide range of nonzero
patterns (or matrix graph vertex interconnections). While convolutional NNs
could possibly address matrix graphs where all vertices have the same number of
nearest neighbors, a more general approach is needed for arbitrary sparse
matrices, e.g. arising from discretized partial differential equations on
unstructured meshes. Graph neural networks (GNNs) are one approach suitable to
sparse matrices. GNNs define aggregation functions (e.g., summations) that
operate on variable size input data to produce data of a fixed output size so
that MLPs can be applied. The goal of this paper is to provide an introduction
to GNNs for a numerical linear algebra audience. Concrete examples are provided
to illustrate how many common linear algebra tasks can be accomplished using
GNNs. We focus on iterative methods that employ computational kernels such as
matrix-vector products, interpolation, relaxation methods, and
strength-of-connection measures. Our GNN examples include cases where
parameters are determined a-priori as well as cases where parameters must be
learned. The intent with this article is to help computational scientists
understand how GNNs can be used to adapt machine learning concepts to
computational tasks associated with sparse matrices. It is hoped that this
understanding will stimulate data-driven extensions of classical sparse linear
algebra tasks.
Related papers
- Signal Processing in the Retina: Interpretable Graph Classifier to
Predict Ganglion Cell Responses [26.403303281303092]
We learn an interpretable graph-based classifier to predict the firings of ganglion cells in response to visual stimuli.
Our framework can be applied to other biological systems with pre-chosen features that require interpretation.
arXiv Detail & Related papers (2024-01-03T16:15:22Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA.
By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms.
We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
arXiv Detail & Related papers (2023-09-06T14:59:38Z) - A Structured Sparse Neural Network and Its Matrix Calculations Algorithm [0.0]
We introduce a nonsymmetric, tridiagonal matrix with offdiagonal sparse entries and offset sub and super-diagonals.
For the cases where the matrix inverse does not exist, a least square type pseudoinverse is provided.
Results show significant improvement in computational costs specially when the size of matrix increases.
arXiv Detail & Related papers (2022-07-02T19:38:48Z) - 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) - Optimizing Sparse Matrix Multiplications for Graph Neural Networks [8.080228311931261]
Graph neural networks (GNNs) are emerging as a powerful technique for modeling graph structures.
Due to the sparsity of real-world graph data, GNN performance is limited by extensive sparse matrix multiplication operations.
This paper investigates how the choice of sparse matrix storage formats affect the GNN performance.
arXiv Detail & Related papers (2021-10-30T22:08:51Z) - Permute Me Softly: Learning Soft Permutations for Graph Representations [26.581982471005674]
Graph neural networks (GNNs) have emerged as a dominant paradigm for machine learning with graphs.
Research on MPNNs has mainly focused on the family of message passing neural networks (MPNNs)
arXiv Detail & Related papers (2021-10-05T08:20:51Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer.
In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph.
Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
arXiv Detail & Related papers (2021-09-10T07:01:15Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability.
We quantify the relevant structure of the data in terms of a novel notion of mutual complexity.
arXiv Detail & Related papers (2021-07-31T10:25:26Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data.
We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity.
Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
arXiv Detail & Related papers (2020-06-16T21:56:22Z) - Learning Algebraic Multigrid Using Graph Neural Networks [34.32501734380907]
We train a single graph neural network to learn a mapping from an entire class of such matrices to prolongation operators.
Experiments on a broad class of problems demonstrate improved convergence rates compared to classical AMG.
arXiv Detail & Related papers (2020-03-12T12:36:48Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix.
We show that our approach obtains small error and is efficient in both space and time.
arXiv Detail & Related papers (2020-02-23T03:07:31Z)
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.