How hard is to distinguish graphs with graph neural networks?

• URL: http://arxiv.org/abs/2005.06649v2
• Date: Fri, 16 Oct 2020 12:48:57 GMT
• Title: How hard is to distinguish graphs with graph neural networks?
• Authors: Andreas Loukas
• Abstract summary: This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN) MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.
• Score: 32.09819774228997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. The analysis relies on the introduced measure of communication capacity. Capacity measures how much information the nodes of a network can exchange during the forward pass and depends on the depth, message-size, global state, and width of the architecture. It is shown that the capacity of MPNN needs to grow linearly with the number of nodes so that a network can distinguish trees and quadratically for general connected graphs. The derived bounds concern both worst- and average-case behavior and apply to networks with/without unique features and adaptive architecture -- they are also up to two orders of magnitude tighter than those given by simpler arguments. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.

Related papers

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Knowledge Enhanced Graph Neural Networks for Graph Completion [0.0]
  Knowledge Enhanced Graph Neural Networks (KeGNN) is a neuro-symbolic framework for graph completion. KeGNN consists of a graph neural network as a base upon which knowledge enhancement layers are stacked. We instantiate KeGNN in conjunction with two state-of-the-art graph neural networks, Graph Convolutional Networks and Graph Attention Networks.
  arXiv  Detail & Related papers  (2023-03-27T07:53:43Z)
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations [26.77596449192451]
  Graph neural networks (GNNs) have emerged as a promising tool for solving machine learning problems on graphs. In this paper, we define a distance function between nodes which is based on the hierarchy produced by the Weisfeiler-Leman (WL) algorithm. We propose a model that learns representations which preserve those distances between nodes.
  arXiv  Detail & Related papers  (2022-11-04T15:03:41Z)
• 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)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  A major issue with arbitrary graphs is the absence of canonical positional information of nodes. We introduce Positional nodes (PE) of nodes, and inject it into the input layer, like in Transformers. We observe a performance increase for molecular datasets, from 2.87% up to 64.14% when considering learnable PE for both GNN classes.
  arXiv  Detail & Related papers  (2021-10-15T05:59:15Z)
• CopulaGNN: Towards Integrating Representational and Correlational Roles of Graphs in Graph Neural Networks [23.115288017590093]
  We investigate how Graph Neural Network (GNN) models can effectively leverage both types of information. The proposed Copula Graph Neural Network (CopulaGNN) can take a wide range of GNN models as base models.
  arXiv  Detail & Related papers  (2020-10-05T15:20:04Z)
• Graph Structure of Neural Networks [104.33754950606298]
  We show how the graph structure of neural networks affect their predictive performance. A "sweet spot" of relational graphs leads to neural networks with significantly improved predictive performance. Top-performing neural networks have graph structure surprisingly similar to those of real biological neural networks.
  arXiv  Detail & Related papers  (2020-07-13T17:59:31Z)
• 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)
• Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
  We perform a massive evaluation of neural networks with architectures corresponding to random graphs of various types. We find that none of the classical numerical graph invariants by itself allows to single out the best networks. We also find that networks with primarily short-range connections perform better than networks which allow for many long-range connections.
  arXiv  Detail & Related papers  (2020-02-19T11:04:49Z)

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.