SMGRL: Scalable Multi-resolution Graph Representation Learning

• URL: http://arxiv.org/abs/2201.12670v3
• Date: Tue, 15 Aug 2023 18:55:42 GMT
• Title: SMGRL: Scalable Multi-resolution Graph Representation Learning
• Authors: Reza Namazi, Elahe Ghalebi, Sinead Williamson, Hamidreza Mahyar
• Abstract summary: Graph convolutional networks (GCNs) allow us to learn topologically-aware node embeddings. They are unable to capture long-range dependencies between nodes without adding additional layers. We propose a Scalable Multi-resolution Graph Representation Learning framework that enables us to learn multi-resolution node embeddings efficiently.
• Score: 1.878741798127168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph convolutional networks (GCNs) allow us to learn topologically-aware node embeddings, which can be useful for classification or link prediction. However, they are unable to capture long-range dependencies between nodes without adding additional layers -- which in turn leads to over-smoothing and increased time and space complexity. Further, the complex dependencies between nodes make mini-batching challenging, limiting their applicability to large graphs. We propose a Scalable Multi-resolution Graph Representation Learning (SMGRL) framework that enables us to learn multi-resolution node embeddings efficiently. Our framework is model-agnostic and can be applied to any existing GCN model. We dramatically reduce training costs by training only on a reduced-dimension coarsening of the original graph, then exploit self-similarity to apply the resulting algorithm at multiple resolutions. The resulting multi-resolution embeddings can be aggregated to yield high-quality node embeddings that capture both long- and short-range dependencies. Our experiments show that this leads to improved classification accuracy, without incurring high computational costs.

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)
• AGNN: Alternating Graph-Regularized Neural Networks to Alleviate Over-Smoothing [29.618952407794776]
  We propose an Alternating Graph-regularized Neural Network (AGNN) composed of Graph Convolutional Layer (GCL) and Graph Embedding Layer (GEL) GEL is derived from the graph-regularized optimization containing Laplacian embedding term, which can alleviate the over-smoothing problem. AGNN is evaluated via a large number of experiments including performance comparison with some multi-layer or multi-order graph neural networks.
  arXiv  Detail & Related papers  (2023-04-14T09:20:03Z)
• 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)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• 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)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.