A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

• URL: http://arxiv.org/abs/2405.00205v1
• Date: Tue, 30 Apr 2024 21:16:38 GMT
• Title: A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
• Authors: Pierre Nunn, Marco Sälzer, François Schwarzentruber, Nicolas Troquard,
• Abstract summary: We show that each formula can be transformed into an equivalent graph neural network (GNN) We also show that the satisfiability problem is PSPACE-complete.
• Score: 11.313331046805365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a modal logic in which counting modalities appear in linear inequalities. We show that each formula can be transformed into an equivalent graph neural network (GNN). We also show that a broad class of GNNs can be transformed efficiently into a formula, thus significantly improving upon the literature about the logical expressiveness of GNNs. We also show that the satisfiability problem is PSPACE-complete. These results bring together the promise of using standard logical methods for reasoning about GNNs and their properties, particularly in applications such as GNN querying, equivalence checking, etc. We prove that such natural problems can be solved in polynomial space.

Related papers

• Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective [24.729126775414922]
  We provide a theoretical framework to determine the homomorphism counting power of an arbitrary class of graph neural networks (GNNs) As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design.
  arXiv  Detail & Related papers  (2024-10-04T15:36:48Z)
• 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)
• A Modal Logic for Explaining some Graph Neural Networks [0.0]
  We show that each formula can be transformed into an equivalent graph neural network (GNN) We also show that the satisfiability problem is decidable.
  arXiv  Detail & Related papers  (2023-07-11T10:13:25Z)
• The Logic of Graph Neural Networks [0.9355115132408681]
  Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has been shown that the expressiveness of GNNs can be characterised precisely by the Weisfeiler-Leman algorithms and by variable counting logics.
  arXiv  Detail & Related papers  (2021-04-29T19:23:26Z)
• 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)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  We show that Folklore Graph Neural Networks (FGNN) are the most expressive architectures proposed so far for a given tensor order. FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms.
  arXiv  Detail & Related papers  (2020-06-28T16:35:45Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)
• Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
  We study the task of logical generalization using graph neural networks (GNNs) Our benchmark suite, GraphLog, requires that learning algorithms perform rule induction in different synthetic logics. We find that the ability for models to generalize and adapt is strongly determined by the diversity of the logical rules they encounter during training.
  arXiv  Detail & Related papers  (2020-03-14T05:45:55Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  Markov Logic Networks (MLNs) can be used to address many knowledge graph problems. Inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. We propose a graph neural network (GNN) variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model.
  arXiv  Detail & Related papers  (2020-01-29T23:34:36Z)

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.