A Novel Differentiable Loss Function for Unsupervised Graph Neural Networks in Graph Partitioning
원문 초록
In this paper, we explore the graph partitioning problem, a pivotal combina-torial optimization challenge with extensive applications in various fields such as science, technology, and business. Recognized as an NP-hard prob-lem, graph partitioning lacks polynomial-time algorithms for its resolution. Recently, there has been a burgeoning interest in leveraging machine learn-ing, particularly approaches like supervised, unsupervised, and reinforce-ment learning, to tackle such NP-hard problems. However, these methods face significant hurdles: supervised learning is constrained by the necessity of labeled solution instances, which are often computationally impractical to obtain; reinforcement learning grapples with instability in the learning pro-cess; and unsupervised learning contends with the absence of a differentia-ble loss function, a consequence of the discrete nature of most combinatorial optimization problems. Addressing these challenges, our research introduces a novel pipeline employing an unsupervised graph neural network to solve the graph partitioning problem. The core innovation of this study is the for-mulation of a differentiable loss function tailored for this purpose. We rigor-ously evaluate our methodology against contemporary state-of-the-art tech-niques, focusing on metrics: cuts and balance, and our findings reveal that our is competitive with these leading methods.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization
STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
Graph Reduction with Unsupervised Learning in Column Generation: A Routing Application
Chi-Square Wavelet Graph Neural Networks for Heterogeneous Graph Anomaly Detection
Long-Short Distance Graph Neural Networks and Improved Curriculum Learning for Emotion Recognition in Conversation
PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training
토론
이 논문과 연결된 포럼 글이 아직 없습니다.