Graph Neural Networks Inspired by Classical Iterative Algorithms

• URL: http://arxiv.org/abs/2103.06064v1
• Date: Wed, 10 Mar 2021 14:08:12 GMT
• Title: Graph Neural Networks Inspired by Classical Iterative Algorithms
• Authors: Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, David Wipf
• Abstract summary: We consider a new family of GNN layers designed to mimic and integrate the update rules of two classical iterative algorithms. A novel attention mechanism is explicitly anchored to an underlying end-toend energy function, contributing stability with respect to edge uncertainty.
• Score: 28.528150667063876
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the recent success of graph neural networks (GNN), common architectures often exhibit significant limitations, including sensitivity to oversmoothing, long-range dependencies, and spurious edges, e.g., as can occur as a result of graph heterophily or adversarial attacks. To at least partially address these issues within a simple transparent framework, we consider a new family of GNN layers designed to mimic and integrate the update rules of two classical iterative algorithms, namely, proximal gradient descent and iterative reweighted least squares (IRLS). The former defines an extensible base GNN architecture that is immune to oversmoothing while nonetheless capturing long-range dependencies by allowing arbitrary propagation steps. In contrast, the latter produces a novel attention mechanism that is explicitly anchored to an underlying end-toend energy function, contributing stability with respect to edge uncertainty. When combined we obtain an extremely simple yet robust model that we evaluate across disparate scenarios including standardized benchmarks, adversarially-perturbated graphs, graphs with heterophily, and graphs involving long-range dependencies. In doing so, we compare against SOTA GNN approaches that have been explicitly designed for the respective task, achieving competitive or superior node classification accuracy.

Related papers

• MuseGNN: Interpretable and Convergent Graph Neural Network Layers at Scale [15.93424606182961]
  We propose a sampling-based energy function and scalable GNN layers that iteratively reduce it, guided by convergence guarantees in certain settings. We also instantiate a full GNN architecture based on these designs, and the model achieves competitive accuracy and scalability when applied to the largest publicly-available node classification benchmark exceeding 1TB in size.
  arXiv  Detail & Related papers  (2023-10-19T04:30:14Z)
• Re-Think and Re-Design Graph Neural Networks in Spaces of Continuous Graph Diffusion Functionals [7.6435511285856865]
  Graph neural networks (GNNs) are widely used in domains like social networks and biological systems. locality assumption of GNNs hampers their ability to capture long-range dependencies and global patterns in graphs. We propose a new inductive bias based on variational analysis, drawing inspiration from the Brachchronistoe problem.
  arXiv  Detail & Related papers  (2023-07-01T04:44:43Z)
• Search to Capture Long-range Dependency with Stacking GNNs for Graph Classification [41.84399177525008]
  shallow GNNs are more common due to the well-known over-smoothing problem facing deeper GNNs. We propose a novel approach with the help of neural architecture search (NAS), which is dubbed LRGNN (Long-Range Graph Neural Networks)
  arXiv  Detail & Related papers  (2023-02-17T03:40:17Z)
• MGNNI: Multiscale Graph Neural Networks with Implicit Layers [53.75421430520501]
  implicit graph neural networks (GNNs) have been proposed to capture long-range dependencies in underlying graphs. We introduce and justify two weaknesses of implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. We propose a multiscale graph neural network with implicit layers (MGNNI) which is able to model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies.
  arXiv  Detail & Related papers  (2022-10-15T18:18:55Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• EIGNN: Efficient Infinite-Depth Graph Neural Networks [51.97361378423152]
  Graph neural networks (GNNs) are widely used for modelling graph-structured data in numerous applications. Motivated by this limitation, we propose a GNN model with infinite depth, which we call Efficient Infinite-Depth Graph Neural Networks (EIGNN) We show that EIGNN has a better ability to capture long-range dependencies than recent baselines, and consistently achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-02-22T08:16:58Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• Hierarchical graph neural nets can capture long-range interactions [8.067880298298185]
  We study hierarchical message passing models that leverage a multi-resolution representation of a given graph. This facilitates learning of features that span large receptive fields without loss of local information. We introduce Hierarchical Graph Net (HGNet), which for any two connected nodes guarantees existence of message-passing paths of at most logarithmic length.
  arXiv  Detail & Related papers  (2021-07-15T16:24:22Z)
• Implicit Graph Neural Networks [46.0589136729616]
  We propose a graph learning framework called Implicit Graph Neural Networks (IGNN) IGNNs consistently capture long-range dependencies and outperform state-of-the-art GNN models.
  arXiv  Detail & Related papers  (2020-09-14T06:04:55Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  We introduce Graph Recurrent Neural Networks (GRNNs) as a general learning framework for graph processes. To address the problem of vanishing gradients, we put forward GRNNs with three different gating mechanisms: time, node and edge gates. The numerical results also show that GRNNs outperform GNNs and RNNs, highlighting the importance of taking both the temporal and graph structures of a graph process into account.
  arXiv  Detail & Related papers  (2020-02-03T22:35:14Z)
• EdgeNets:Edge Varying Graph Neural Networks [179.99395949679547]
  This paper puts forth a general framework that unifies state-of-the-art graph neural networks (GNNs) through the concept of EdgeNet. An EdgeNet is a GNN architecture that allows different nodes to use different parameters to weigh the information of different neighbors. This is a general linear and local operation that a node can perform and encompasses under one formulation all existing graph convolutional neural networks (GCNNs) as well as graph attention networks (GATs)
  arXiv  Detail & Related papers  (2020-01-21T15:51:17Z)

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.