Graph Expansions of Deep Neural Networks and their Universal Scaling Limits

• URL: http://arxiv.org/abs/2407.08459v2
• Date: Thu, 18 Jul 2024 10:33:35 GMT
• Title: Graph Expansions of Deep Neural Networks and their Universal Scaling Limits
• Authors: Nicola Muca Cirone, Jad Hamdan, Cristopher Salvi,
• Abstract summary: We present a unified approach to obtain scaling limits of neural networks. We use the genus expansion technique from random matrix theory. We find formulae for the moments of the limiting singular value distribution of the Jacobian.
• Score: 3.801509221714223
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a unified approach to obtain scaling limits of neural networks using the genus expansion technique from random matrix theory. This approach begins with a novel expansion of neural networks which is reminiscent of Butcher series for ODEs, and is obtained through a generalisation of Fa\`a di Bruno's formula to an arbitrary number of compositions. In this expansion, the role of monomials is played by random multilinear maps indexed by directed graphs whose edges correspond to random matrices, which we call operator graphs. This expansion linearises the effect of the activation functions, allowing for the direct application of Wick's principle to compute the expectation of each of its terms. We then determine the leading contribution to each term by embedding the corresponding graphs onto surfaces, and computing their Euler characteristic. Furthermore, by developing a correspondence between analytic and graphical operations, we obtain similar graph expansions for the neural tangent kernel as well as the input-output Jacobian of the original neural network, and derive their infinite-width limits with relative ease. Notably, we find explicit formulae for the moments of the limiting singular value distribution of the Jacobian. We then show that all of these results hold for networks with more general weights, such as general matrices with i.i.d. entries satisfying moment assumptions, complex matrices and sparse matrices.

Related papers

• A theory of data variability in Neural Network Bayesian inference [0.70224924046445]
  We provide a field-theoretic formalism which covers the generalization properties of infinitely wide networks. We derive the generalization properties from the statistical properties of the input. We show that data variability leads to a non-Gaussian action reminiscent of a ($varphi3+varphi4$)-theory.
  arXiv  Detail & Related papers  (2023-07-31T14:11:32Z)
• Gradient Descent in Neural Networks as Sequential Learning in RKBS [63.011641517977644]
  We construct an exact power-series representation of the neural network in a finite neighborhood of the initial weights. We prove that, regardless of width, the training sequence produced by gradient descent can be exactly replicated by regularized sequential learning.
  arXiv  Detail & Related papers  (2023-02-01T03:18:07Z)
• Graph Convolutional Networks from the Perspective of Sheaves and the Neural Tangent Kernel [0.0]
  Graph convolutional networks are a popular class of deep neural network algorithms. Despite their success, graph convolutional networks exhibit a number of peculiar features, including a bias towards learning oversmoothed and homophilic functions. We propose to bridge this gap by studying the neural tangent kernel of sheaf convolutional networks.
  arXiv  Detail & Related papers  (2022-08-19T12:46:49Z)
• On the Neural Tangent Kernel Analysis of Randomly Pruned Neural Networks [91.3755431537592]
  We study how random pruning of the weights affects a neural network's neural kernel (NTK) In particular, this work establishes an equivalence of the NTKs between a fully-connected neural network and its randomly pruned version.
  arXiv  Detail & Related papers  (2022-03-27T15:22:19Z)
• Non-Vacuous Generalisation Bounds for Shallow Neural Networks [5.799808780731661]
  We focus on a specific class of shallow neural networks with a single hidden layer. We derive new generalisation bounds through the PAC-Bayesian theory. Our bounds are empirically non-vacuous when the network is trained with vanilla gradient descent on MNIST and Fashion-MNIST.
  arXiv  Detail & Related papers  (2022-02-03T14:59:51Z)
• Graph-based Neural Acceleration for Nonnegative Matrix Factorization [0.0]
  We describe a graph-based neural acceleration technique for nonnegative matrix factorization. We train a graph neural network that interleaves bipartite self-attention layers with updates based on the alternating direction method of multipliers. Our evaluation on synthetic and two real-world datasets shows that we attain substantial acceleration, even though we only train in an unsupervised fashion on smaller synthetic instances.
  arXiv  Detail & Related papers  (2022-02-01T07:52:01Z)
• 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)
• Linear approximability of two-layer neural networks: A comprehensive analysis based on spectral decay [4.042159113348107]
  We first consider the case of single neuron and show that the linear approximability, quantified by the Kolmogorov width, is controlled by the eigenvalue decay of an associate kernel. We show that similar results also hold for two-layer neural networks.
  arXiv  Detail & Related papers  (2021-08-10T23:30:29Z)
• 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)
• On the validity of kernel approximations for orthogonally-initialized neural networks [14.23089477635398]
  We extend kernel function approximation results for neural networks with Gaussian-distributed weights to single-layer networks using Haar-distributed random matrices (with possible rescaling).
  arXiv  Detail & Related papers  (2021-04-13T00:57:39Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Non-asymptotic approximations of neural networks by Gaussian processes [7.56714041729893]
  We study the extent to which wide neural networks may be approximated by Gaussian processes when with random weights. As the width of a network goes to infinity, its law converges to that of a Gaussian process.
  arXiv  Detail & Related papers  (2021-02-17T10:19:26Z)
• Double-descent curves in neural networks: a new perspective using Gaussian processes [9.153116600213641]
  Double-descent curves in neural networks describe the phenomenon that the generalisation error initially descends with increasing parameters, then grows after reaching an optimal number of parameters. We use techniques from random matrix theory to characterize the spectral distribution of the empirical feature covariance matrix as a width-dependent of the spectrum of the neural network Gaussian process kernel.
  arXiv  Detail & Related papers  (2021-02-14T20:31:49Z)
• Infinitely Wide Tensor Networks as Gaussian Process [1.7894377200944511]
  In this paper, we show the equivalence of the infinitely wide Networks and the Gaussian Process. We implement the Gaussian Process corresponding to the infinite limit tensor networks and plot the sample paths of these models.
  arXiv  Detail & Related papers  (2021-01-07T02:29:15Z)
• Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
  We introduce graph gamma process (GGP) linear dynamical systems to model real multivariate time series. For temporal pattern discovery, the latent representation under the model is used to decompose the time series into a parsimonious set of multivariate sub-sequences. We use the generated random graph, whose number of nonzero-degree nodes is finite, to define both the sparsity pattern and dimension of the latent state transition matrix.
  arXiv  Detail & Related papers  (2020-07-25T04:16:34Z)
• 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)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)
• Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks [70.15611146583068]
  We develop exact representations of training two-layer neural networks with rectified linear units (ReLUs) Our theory utilizes semi-infinite duality and minimum norm regularization.
  arXiv  Detail & Related papers  (2020-02-24T21:32:41Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• On the Convex Behavior of Deep Neural Networks in Relation to the Layers' Width [99.24399270311069]
  We observe that for wider networks, minimizing the loss with the descent optimization maneuvers through surfaces of positive curvatures at the start and end of training, and close to zero curvatures in between. In other words, it seems that during crucial parts of the training process, the Hessian in wide networks is dominated by the component G.
  arXiv  Detail & Related papers  (2020-01-14T16:30:01Z)

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.