Shortest Path Networks for Graph Property Prediction

• URL: http://arxiv.org/abs/2206.01003v1
• Date: Thu, 2 Jun 2022 12:04:29 GMT
• Title: Shortest Path Networks for Graph Property Prediction
• Authors: Ralph Abboud, Radoslav Dimitrov, \.Ismail \.Ilkan Ceylan
• Abstract summary: Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. We propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. Our framework generalizes message passing neural networks, resulting in provably more expressive models.
• Score: 13.986963122264632
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood. While very prominent, this paradigm leads to information propagation bottlenecks, as information is repeatedly compressed at intermediary node representations, which causes loss of information, making it practically impossible to gather meaningful signals from distant nodes. To address this issue, we propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods. In this setting, nodes can directly communicate between each other even if they are not neighbors, breaking the information bottleneck and hence leading to more adequately learned representations. Theoretically, our framework generalizes message passing neural networks, resulting in provably more expressive models. Empirically, we verify the capacity of a basic model of this framework on dedicated synthetic experiments, and on real-world graph classification and regression benchmarks, obtaining several state-of-the-art results.

Related papers

• SF-GNN: Self Filter for Message Lossless Propagation in Deep Graph Neural Network [38.669815079957566]
  Graph Neural Network (GNN) with the main idea of encoding graph structure information of graphs by propagation and aggregation has developed rapidly. It achieved excellent performance in representation learning of multiple types of graphs such as homogeneous graphs, heterogeneous graphs, and more complex graphs like knowledge graphs. For the phenomenon of performance degradation in deep GNNs, we propose a new perspective.
  arXiv  Detail & Related papers  (2024-07-03T02:40:39Z)
• Message Detouring: A Simple Yet Effective Cycle Representation for Expressive Graph Learning [4.085624738017079]
  We introduce the concept of textitmessage detouring to hierarchically characterize cycle representation throughout the entire graph. Message detouring can significantly outperform current counterpart approaches on various benchmark datasets.
  arXiv  Detail & Related papers  (2024-02-12T22:06:37Z)
• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection [51.608147732998994]
  Graph neural networks are increasingly becoming the framework of choice for graph-based machine learning. We propose a new graph neural network architecture that substitutes classical message passing with an analysis of the local distribution of node features.
  arXiv  Detail & Related papers  (2024-01-17T13:04:23Z)
• Cooperative Graph Neural Networks [7.2459816681395095]
  A class of graph neural networks follow a standard message-passing paradigm. We propose a novel framework for training graph neural networks. Our approach offers a more flexible and dynamic message-passing paradigm.
  arXiv  Detail & Related papers  (2023-10-02T15:08:52Z)
• Half-Hop: A graph upsampling approach for slowing down message passing [31.26080679115766]
  We introduce a framework for improving learning in message passing neural networks. Our approach essentially upsamples edges in the original graph by adding "slow nodes" at each edge. Our method only modifies the input graph, making it plug-and-play and easy to use with existing models.
  arXiv  Detail & Related papers  (2023-08-17T22:24:15Z)
• 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)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• Uniting Heterogeneity, Inductiveness, and Efficiency for Graph Representation Learning [68.97378785686723]
  graph neural networks (GNNs) have greatly advanced the performance of node representation learning on graphs. A majority class of GNNs are only designed for homogeneous graphs, leading to inferior adaptivity to the more informative heterogeneous graphs. We propose a novel inductive, meta path-free message passing scheme that packs up heterogeneous node features with their associated edges from both low- and high-order neighbor nodes.
  arXiv  Detail & Related papers  (2021-04-04T23:31:39Z)
• Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
  Existing representation learning methods in graph convolutional networks are mainly designed by describing the neighborhood of each node as a perceptual whole. We propose a Semantic Graph Convolutional Networks (SGCN) that explores the implicit semantics by learning latent semantic-paths in graphs.
  arXiv  Detail & Related papers  (2021-01-16T16:18:43Z)
• Graph Fairing Convolutional Networks for Anomaly Detection [7.070726553564701]
  We introduce a graph convolutional network with skip connections for semi-supervised anomaly detection. The effectiveness of our model is demonstrated through extensive experiments on five benchmark datasets.
  arXiv  Detail & Related papers  (2020-10-20T13:45:47Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)

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.