用量子退火解决图节点嵌入,提升大规模图学习效率。
A quantum annealing approach to graph node embedding
- 将节点嵌入转为量子退火可解的QUBO问题
- 在100节点图上实现5维嵌入,验证可行性
- 适合关注量子计算与图学习结合的研究者
节点嵌入是将图节点表示为向量以保留结构和关系属性的关键技术,支持特征提取、聚类和分类等机器学习任务。经典方法如DeepWalk、node2vec和图卷积网络虽能捕捉图中模式,但计算开销大,难以扩展至大规模图。量子计算通过利用量子效应和新优化方法为图学习提供潜在替代方案。尽管变分量子电路和量子核方法已被探索,但受限于噪声中等规模量子(NISQ)硬件,其可扩展性仍不足。本文研究量子退火(QA)作为替代方案,缓解基于量子门模型的关键挑战。我们提出数种将节点嵌入问题转化为无约束二次二值优化(QUBO)实例的方法,使其兼容当前量子退火设备(如D-Wave)。我们在D-Wave量子退火器上实现算法,并在最多100个节点、嵌入维度最高达5的图上评估性能。结果表明,量子退火是图学习的一种可行方案,相比先前量子嵌入技术更具可扩展性和效率。
原文摘要 · Abstract (English)
Node embedding is a key technique for representing graph nodes as vectors while preserving structural and relational properties, which enables machine learning tasks like feature extraction, clustering, and classification. While classical methods such as DeepWalk, node2vec, and graph convolutional networks learn node embeddings by capturing structural and relational patterns in graphs, they often require significant computational resources and struggle with scalability on large graphs. Quantum computing provides a promising alternative for graph-based learning by leveraging quantum effects and introducing novel optimization approaches. Variational quantum circuits and quantum kernel methods have been explored for embedding tasks, but their scalability remains limited due to the constraints of noisy intermediate-scale quantum (NISQ) hardware. In this paper, we investigate quantum annealing (QA) as an alternative approach that mitigates key challenges associated with quantum gate-based models. We propose several formulations of the node embedding problem as a quadratic unconstrained binary optimization (QUBO) instance, making it compatible with current quantum annealers such as those developed by D-Wave. We implement our algorithms on a D-Wave quantum annealer and evaluate their performance on graphs with up to 100 nodes and embedding dimensions of up to 5. Our findings indicate that QA is a viable approach for graph-based learning, providing a scalable and efficient alternative to previous quantum embedding techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。