Graph Neural Networks and Arithmetic Circuits

• URL: http://arxiv.org/abs/2402.17805v2
• Date: Thu, 21 Nov 2024 15:34:06 GMT
• Title: Graph Neural Networks and Arithmetic Circuits
• Authors: Timon Barlag, Vivian Holzapfel, Laura Strieker, Jonni Virtema, Heribert Vollmer,
• Abstract summary: We characterize the computational power of neural networks that follow the graph neural network architecture. We establish an exact correspondence between the expressivity of GNNs using diverse activation functions and arithmetic over real numbers.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular types. We establish an exact correspondence between the expressivity of GNNs using diverse activation functions and arithmetic circuits over real numbers. In our results the activation function of the network becomes a gate type in the circuit. Our result holds for families of constant depth circuits and networks, both uniformly and non-uniformly, for all common activation functions.

Related papers

• Recurrent Graph Neural Networks and Arithmetic Circuits [3.996231905922229]
  We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers.<n>We introduce the model of recurrent arithmetic circuits, which can be seen as arithmetic analogues of sequential or logical circuits.
  arXiv  Detail & Related papers  (2026-03-05T13:10:27Z)
• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN)<n>We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks.
  arXiv  Detail & Related papers  (2025-08-25T21:55:37Z)
• Graph Neural Networks for Learning Equivariant Representations of Neural Networks [55.04145324152541]
  We propose to represent neural networks as computational graphs of parameters. Our approach enables a single model to encode neural computational graphs with diverse architectures. We showcase the effectiveness of our method on a wide range of tasks, including classification and editing of implicit neural representations.
  arXiv  Detail & Related papers  (2024-03-18T18:01:01Z)
• Graph Metanetworks for Processing Diverse Neural Architectures [33.686728709734105]
  Graph Metanetworks (GMNs) generalizes to neural architectures where competing methods struggle. We prove that GMNs are expressive and equivariant to parameter permutation symmetries that leave the input neural network functions.
  arXiv  Detail & Related papers  (2023-12-07T18:21:52Z)
• Exploring the Approximation Capabilities of Multiplicative Neural Networks for Smooth Functions [9.936974568429173]
  We consider two classes of target functions: generalized bandlimited functions and Sobolev-Type balls. Our results demonstrate that multiplicative neural networks can approximate these functions with significantly fewer layers and neurons. These findings suggest that multiplicative gates can outperform standard feed-forward layers and have potential for improving neural network design.
  arXiv  Detail & Related papers  (2023-01-11T17:57:33Z)
• Deep Neural Networks as Complex Networks [1.704936863091649]
  We use Complex Network Theory to represent Deep Neural Networks (DNNs) as directed weighted graphs. We introduce metrics to study DNNs as dynamical systems, with a granularity that spans from weights to layers, including neurons. We show that our metrics discriminate low vs. high performing networks.
  arXiv  Detail & Related papers  (2022-09-12T16:26:04Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Learning Power Control for Cellular Systems with Heterogeneous Graph Neural Network [37.060397377445504]
  We show that the power control policy has a combination of different PI and PE properties, and existing HetGNN does not satisfy these properties. We design a parameter sharing scheme for HetGNN such that the learned relationship satisfies the desired properties.
  arXiv  Detail & Related papers  (2020-11-06T02:41:38Z)
• Stability of Algebraic Neural Networks to Small Perturbations [179.55535781816343]
  Algebraic neural networks (AlgNNs) are composed of a cascade of layers each one associated to and algebraic signal model. We show how any architecture that uses a formal notion of convolution can be stable beyond particular choices of the shift operator.
  arXiv  Detail & Related papers  (2020-10-22T09:10:16Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters.
  arXiv  Detail & Related papers  (2020-08-04T18:57:36Z)
• 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)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  We leverage graph signal processing to characterize the representation space of graph neural networks (GNNs) We discuss the role of graph convolutional filters in GNNs and show that any architecture built with such filters has the fundamental properties of permutation equivariance and stability to changes in the topology. We also study the use of GNNs in recommender systems and learning decentralized controllers for robot swarms.
  arXiv  Detail & Related papers  (2020-03-08T13:02:15Z)

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.