VC dimension of Graph Neural Networks with Pfaffian activation functions

• URL: http://arxiv.org/abs/2401.12362v2
• Date: Tue, 2 Apr 2024 17:30:38 GMT
• Title: VC dimension of Graph Neural Networks with Pfaffian activation functions
• Authors: Giuseppe Alessio D'Inverno, Monica Bianchini, Franco Scarselli,
• Abstract summary: Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains. The aim of our work is to extend this analysis on the VC dimension of GNNs to other commonly used activation functions, such as sigmoid and hyperbolic tangent.
• Score: 4.141514895639094
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) have emerged in recent years as a powerful tool to learn tasks across a wide range of graph domains in a data-driven fashion; based on a message passing mechanism, GNNs have gained increasing popularity due to their intuitive formulation, closely linked with the Weisfeiler-Lehman (WL) test for graph isomorphism, to which they have proven equivalent. From a theoretical point of view, GNNs have been shown to be universal approximators, and their generalization capability (namely, bounds on the Vapnik Chervonekis (VC) dimension) has recently been investigated for GNNs with piecewise polynomial activation functions. The aim of our work is to extend this analysis on the VC dimension of GNNs to other commonly used activation functions, such as sigmoid and hyperbolic tangent, using the framework of Pfaffian function theory. Bounds are provided with respect to architecture parameters (depth, number of neurons, input size) as well as with respect to the number of colors resulting from the 1-WL test applied on the graph domain. The theoretical analysis is supported by a preliminary experimental study.

Related papers

• A note on the VC dimension of 1-dimensional GNNs [6.0757501646966965]
  Graph Neural Networks (GNNs) have become an essential tool for analyzing graph-structured data. This paper focuses on the generalization of GNNs by investigating their Vapnik-Chervonenkis (VC) dimension.
  arXiv  Detail & Related papers  (2024-10-10T11:33:15Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• The Expressive Power of Graph Neural Networks: A Survey [9.08607528905173]
  We conduct a first survey for models for enhancing expressive power under different forms of definition. The models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.
  arXiv  Detail & Related papers  (2023-08-16T09:12:21Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  Graph Neural Networks (GNNs) have emerged as a powerful tool for data-driven learning on various graph domains. We establish new generalization properties and fundamental limits of GNNs in the context of learning so-called identity effects. Our study is motivated by the need to understand the capabilities of GNNs when performing simple cognitive tasks.
  arXiv  Detail & Related papers  (2023-06-30T20:56:38Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows.
  arXiv  Detail & Related papers  (2023-05-24T07:09:53Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  Graph Networks (GNN) are inherently limited in their expressive power. This paper introduces an alternative power hierarchy based on the ability of GNNs to calculate equivariants of certain degree. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.
  arXiv  Detail & Related papers  (2023-02-22T18:53:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models can be regarded as solving a graph denoising problem. We instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes.
  arXiv  Detail & Related papers  (2020-10-05T04:57:18Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30: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.