A Novel Differentiable Loss Function for Unsupervised Graph Neural
  Networks in Graph Partitioning
Vivek Chaudhary
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.