From Local Structures to Size Generalization in Graph Neural Networks

• URL: http://arxiv.org/abs/2010.08853v3
• Date: Thu, 15 Jul 2021 19:18:06 GMT
• Title: From Local Structures to Size Generalization in Graph Neural Networks
• Authors: Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, Haggai Maron
• Abstract summary: Graph neural networks (GNNs) can process graphs of different sizes. Their ability to generalize across sizes, specifically from small to large graphs, is still not well understood.
• Score: 53.3202754533658
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.

Related papers

• Graph Classification via Reference Distribution Learning: Theory and Practice [24.74871206083017]
  This work introduces Graph Reference Distribution Learning (GRDL), an efficient and accurate graph classification method. GRDL treats each graph's latent node embeddings given by GNN layers as a discrete distribution, enabling direct classification without global pooling. Experiments on moderate-scale and large-scale graph datasets show the superiority of GRDL over the state-of-the-art.
  arXiv  Detail & Related papers  (2024-08-21T06:42:22Z)
• Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learning [7.448831299106425]
  DISGEN is a model-agnostic framework designed to disentangle size factors from graph representations. Our empirical results show that DISGEN outperforms the state-of-the-art models by up to 6% on real-world datasets.
  arXiv  Detail & Related papers  (2024-06-07T03:19:24Z)
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
  This paper introduces the mathematical definition of this novel problem setting. We devise a general framework that coordinates a single graph-shared structure learner and multiple graph-specific GNNs. The well-trained structure learner can directly produce adaptive structures for unseen target graphs without any fine-tuning.
  arXiv  Detail & Related papers  (2023-06-20T03:33:22Z)
• 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)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  We develop a principled approach to the problem of graph learning with weak information (GLWI) We propose D$2$PT, a dual-channel GNN framework that performs long-range information propagation on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities.
  arXiv  Detail & Related papers  (2023-05-29T04:51:09Z)
• Learning Graph Algorithms With Recurrent Graph Neural Networks [8.873449722727026]
  We focus on a recurrent architecture design that can learn simple graph problems end to end on smaller graphs and then extrapolate to larger instances. We use (i) skip connections, (ii) state regularization, and (iii) edge convolutions to guide GNNs toward extrapolation.
  arXiv  Detail & Related papers  (2022-12-09T15:42:22Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Deep Graph Structure Learning for Robust Representations: A Survey [20.564611153151834]
  Graph Neural Networks (GNNs) are widely used for analyzing graph-structured data. To improve the robustness of GNN models, many studies have been proposed around the central concept of Graph Structure Learning.
  arXiv  Detail & Related papers  (2021-03-04T13:49:25Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• The Impact of Global Structural Information in Graph Neural Networks Applications [5.629161809575013]
  Graph Neural Networks (GNNs) rely on the graph structure to define an aggregation strategy. A known limitation of GNNs is that, as the number of layers increases, information gets smoothed and squashed. We give access to global information to several GNN models and observe the impact it has on downstream performance.
  arXiv  Detail & Related papers  (2020-06-06T08:52:18Z)

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.