Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks

• URL: http://arxiv.org/abs/2107.10957v1
• Date: Thu, 22 Jul 2021 23:42:23 GMT
• Title: Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks
• Authors: Dylan Sandfelder, Priyesh Vijayan, William L. Hamilton
• Abstract summary: We show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs. In particular, we show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs.
• Score: 12.97622530614215
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Graph neural networks (GNNs) have achieved remarkable success as a framework for deep learning on graph-structured data. However, GNNs are fundamentally limited by their tree-structured inductive bias: the WL-subtree kernel formulation bounds the representational capacity of GNNs, and polynomial-time GNNs are provably incapable of recognizing triangles in a graph. In this work, we propose to augment the GNN message-passing operations with information defined on ego graphs (i.e., the induced subgraph surrounding each node). We term these approaches Ego-GNNs and show that Ego-GNNs are provably more powerful than standard message-passing GNNs. In particular, we show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs. We also motivate our approach from the perspective of graph signal processing as a form of multiplex graph convolution. Experimental results on node classification using synthetic and real data highlight the achievable performance gains using this approach.

Related papers

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  Graph Neural Networks (GNNs) combine information from adjacent nodes by successive applications of graph convolutions. We study the generalization gaps of GNNs on both node-level and graph-level tasks. We show that the generalization gaps decrease with the number of nodes in the training graphs.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• Geodesic Graph Neural Network for Efficient Graph Representation Learning [34.047527874184134]
  We propose an efficient GNN framework called Geodesic GNN (GDGNN) It injects conditional relationships between nodes into the model without labeling. Conditioned on the geodesic representations, GDGNN is able to generate node, link, and graph representations that carry much richer structural information than plain GNNs.
  arXiv  Detail & Related papers  (2022-10-06T02:02:35Z)
• Distribution Preserving Graph Representation Learning [11.340722297341788]
  Graph neural network (GNN) is effective to model graphs for distributed representations of nodes and an entire graph. We propose Distribution Preserving GNN (DP-GNN) - a GNN framework that can improve the generalizability of expressive GNN models. We evaluate the proposed DP-GNN framework on multiple benchmark datasets for graph classification tasks.
  arXiv  Detail & Related papers  (2022-02-27T19:16:26Z)
• KerGNNs: Interpretable Graph Neural Networks with Graph Kernels [14.421535610157093]
  Graph neural networks (GNNs) have become the state-of-the-art method in downstream graph-related tasks. We propose a novel GNN framework, termed textit Kernel Graph Neural Networks (KerGNNs) KerGNNs integrate graph kernels into the message passing process of GNNs. We show that our method achieves competitive performance compared with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-01-03T06:16:30Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters.
  arXiv  Detail & Related papers  (2020-08-04T18:57:36Z)
• GPT-GNN: Generative Pre-Training of Graph Neural Networks [93.35945182085948]
  Graph neural networks (GNNs) have been demonstrated to be powerful in modeling graph-structured data. We present the GPT-GNN framework to initialize GNNs by generative pre-training. We show that GPT-GNN significantly outperforms state-of-the-art GNN models without pre-training by up to 9.1% across various downstream tasks.
  arXiv  Detail & Related papers  (2020-06-27T20:12:33Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  Graphs neural networks (GNNs) learn node features by aggregating and combining neighbor information. GNNs are mostly treated as black-boxes and lack human intelligible explanations. We propose a novel approach, known as XGNN, to interpret GNNs at the model-level.
  arXiv  Detail & Related papers  (2020-06-03T23:52:43Z)

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.