ProGNNosis: A Data-driven Model to Predict GNN Computation Time Using Graph Metrics

• URL: http://arxiv.org/abs/2206.08258v1
• Date: Thu, 16 Jun 2022 15:58:14 GMT
• Title: ProGNNosis: A Data-driven Model to Predict GNN Computation Time Using Graph Metrics
• Authors: Axel Wassington and Sergi Abadal
• Abstract summary: We propose ProGNNosis, a data-driven model that can predict the GNN training time of a given GNN model running over a graph of arbitrary characteristics. Our results show that ProGNNosis helps achieve an average speedup of 1.22X over randomly selecting a graph representation.
• Score: 1.6942548626426182
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNN) show great promise in problems dealing with graph-structured data. One of the unique points of GNNs is their flexibility to adapt to multiple problems, which not only leads to wide applicability, but also poses important challenges when finding the best model or acceleration technique for a particular problem. An example of such challenges resides in the fact that the accuracy or effectiveness of a GNN model or acceleration technique generally depends on the structure of the underlying graph. In this paper, in an attempt to address the problem of graph-dependent acceleration, we propose ProGNNosis, a data-driven model that can predict the GNN training time of a given GNN model running over a graph of arbitrary characteristics by inspecting the input graph metrics. Such prediction is made based on a regression that was previously trained offline using a diverse synthetic graph dataset. In practice, our method allows making informed decisions on which design to use for a specific problem. In the paper, the methodology to build ProGNNosis is defined and applied for a specific use case, where it helps to decide which graph representation is better. Our results show that ProGNNosis helps achieve an average speedup of 1.22X over randomly selecting a graph representation in multiple widely used GNN models such as GCN, GIN, GAT, or GraphSAGE.

Related papers

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  Graph Neural Networks (GNNs) have emerged as a notorious alternative to address learning problems dealing with non-Euclidean datasets. This work proposes a robust implementation of GNNs that explicitly accounts for the presence of perturbations in the observed topology.
  arXiv  Detail & Related papers  (2023-12-11T17:43:57Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• Graph Anomaly Detection with Graph Neural Networks: Current Status and Challenges [9.076649460696402]
  Graph neural networks (GNNs) have been studied extensively and have successfully performed difficult machine learning tasks. This survey is the first comprehensive review of graph anomaly detection methods based on GNNs.
  arXiv  Detail & Related papers  (2022-09-29T16:47:57Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks [5.008597638379227]
  Graph neural networks (GNNs) have become the de facto model of choice for graph classification. We propose a regularization strategy that can be applied to any GNN to improve its generalization capabilities without requiring access to the test data. Our regularization is based on the idea of simulating a shift in the size of the training graphs using coarsening techniques.
  arXiv  Detail & Related papers  (2022-07-16T09:50:45Z)
• Adaptive Kernel Graph Neural Network [21.863238974404474]
  Graph neural networks (GNNs) have demonstrated great success in representation learning for graph-structured data. In this paper, we propose a novel framework - i.e., namely Adaptive Kernel Graph Neural Network (AKGNN) AKGNN learns to adapt to the optimal graph kernel in a unified manner at the first attempt. Experiments are conducted on acknowledged benchmark datasets and promising results demonstrate the outstanding performance of our proposed AKGNN.
  arXiv  Detail & Related papers  (2021-12-08T20:23:58Z)
• 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)
• 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.