Graph Neural Networks on Quantum Computers

• URL: http://arxiv.org/abs/2405.17060v1
• Date: Mon, 27 May 2024 11:31:08 GMT
• Title: Graph Neural Networks on Quantum Computers
• Authors: Yidong Liao, Xiao-Ming Zhang, Chris Ferrie,
• Abstract summary: Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges.
• Score: 3.8784640343151184
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs, demonstrating remarkable performance in applications like social network analysis and recommendation systems. However, classical GNNs face scalability challenges when dealing with large-scale graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges. We devise quantum algorithms corresponding to the three fundamental types of classical GNNs: Graph Convolutional Networks, Graph Attention Networks, and Message-Passing GNNs. A complexity analysis of our quantum implementation of the Simplified Graph Convolutional (SGC) Network shows potential quantum advantages over its classical counterpart, with significant improvements in time and space complexities. Our complexities can have trade-offs between the two: when optimizing for minimal circuit depth, our quantum SGC achieves logarithmic time complexity in the input sizes (albeit at the cost of linear space complexity). When optimizing for minimal qubit usage, the quantum SGC exhibits space complexity logarithmic in the input sizes, offering an exponential reduction compared to classical SGCs, while still maintaining better time complexity. These results suggest our Quantum GNN frameworks could efficiently process large-scale graphs. This work paves the way for implementing more advanced Graph Neural Network models on quantum computers, opening new possibilities in quantum machine learning for analyzing graph-structured data.

Related papers

• From Graphs to Qubits: A Critical Review of Quantum Graph Neural Networks [56.51893966016221]
  Quantum Graph Neural Networks (QGNNs) represent a novel fusion of quantum computing and Graph Neural Networks (GNNs) This paper critically reviews the state-of-the-art in QGNNs, exploring various architectures. We discuss their applications across diverse fields such as high-energy physics, molecular chemistry, finance and earth sciences, highlighting the potential for quantum advantage.
  arXiv  Detail & Related papers  (2024-08-12T22:53:14Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  We propose Spatio-Spectral Graph Networks (S$2$GNNs) S$2$GNNs combine spatially and spectrally parametrized graph filters. We show that S$2$GNNs vanquish over-squashing and yield strictly tighter approximation-theoretic error bounds than MPGNNs.
  arXiv  Detail & Related papers  (2024-05-29T14:28:08Z)
• Learnability of a hybrid quantum-classical neural network for graph-structured quantum data [0.0]
  We build a hybrid quantum-classical neural network with deep residual learning (Res-HQCNN) with graph-structured quantum data. We show that the using of information about graph structures in quantum data can lead to better learning efficiency compared with the state-of-the-art model.
  arXiv  Detail & Related papers  (2024-01-28T14:06:06Z)
• Enabling Accelerators for Graph Computing [0.0]
  Graph Neural Networks (GNNs) offer a novel paradigm for learning on graph-structured data. GNNs present new computational challenges compared to conventional neural networks. This thesis aims to develop a better understanding of how GNNs interact with the underlying hardware.
  arXiv  Detail & Related papers  (2023-12-16T23:31:20Z)
• A Comparison Between Invariant and Equivariant Classical and Quantum Graph Neural Networks [3.350407101925898]
  Deep geometric methods, such as graph neural networks (GNNs), have been leveraged for various data analysis tasks in high-energy physics. One typical task is jet tagging, where jets are viewed as point clouds with distinct features and edge connections between their constituent particles. In this paper, we perform a fair and comprehensive comparison between classical graph neural networks (GNNs) and their quantum counterparts.
  arXiv  Detail & Related papers  (2023-11-30T16:19:13Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Extending Graph Transformers with Quantum Computed Aggregation [0.0]
  We introduce a GNN architecture where the aggregation weights are computed using the long-range correlations of a quantum system. These correlations are generated by translating the graph topology into the interactions of a set of qubits in a quantum computer.
  arXiv  Detail & Related papers  (2022-10-19T14:56:15Z)
• 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)
• Binary Graph Neural Networks [69.51765073772226]
  Graph Neural Networks (GNNs) have emerged as a powerful and flexible framework for representation learning on irregular data. In this paper, we present and evaluate different strategies for the binarization of graph neural networks. We show that through careful design of the models, and control of the training process, binary graph neural networks can be trained at only a moderate cost in accuracy on challenging benchmarks.
  arXiv  Detail & Related papers  (2020-12-31T18:48:58Z)
• Analyzing the Performance of Graph Neural Networks with Pipe Parallelism [2.269587850533721]
  We focus on Graph Neural Networks (GNNs) that have found great success in tasks such as node or edge classification and link prediction. New approaches for processing larger networks are needed to advance graph techniques. We study how GNNs could be parallelized using existing tools and frameworks that are known to be successful in the deep learning community.
  arXiv  Detail & Related papers  (2020-12-20T04:20:38Z)
• Binarized Graph Neural Network [65.20589262811677]
  We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches. Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
  arXiv  Detail & Related papers  (2020-04-19T09:43: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.