A hybrid GNN-heuristic approach for unsupervised partitioning of featureless graphs

Abstract

Graph partitioning is a fundamental problem in parallel scientific computing, particularly important for efficiently distributing Finite Element Method (FEM) meshes across multiple processors or GPUs. In this context, the dual graph representation, where nodes correspond to mesh elements and edges capture topological adjacency, is widely adopted to minimize inter-partition communication. This work proposes an unsupervised learning framework based on Graph Neural Networks (GNNs) for partitioning dual graphs derived from FEM meshes. Our method integrates spectral graph theory with deep learning by employing Laplacian Eigenmaps as positional encoders. Specifically, we use the Fiedler vector (the eigenvector associated with the second smallest Laplacian eigenvalue) to provide global structural information, mitigating the limitations of purely local encoders and the issues inherent to sign-invariant architectures such as SignNet. The proposed model is built upon the Graph Isomorphism Network (GIN) architecture, chosen for its expressive power in distinguishing graph structures. It is trained end-to-end using a differentiable relaxation of the Min-Max Cut (MMCut) objective, which encourages balanced and well-separated partitions. To further enhance partition quality, we introduce a hybrid variant (GNN-FM) that refines GNN predictions using the linear-time Fiduccia-Mattheyses algorithm as a post-processing step. Experiments were conducted on a large-scale industrial dataset (Fusion 360), comprising thousands of triangular meshes, as well as on a separate set of unseen evaluation meshes provided by an industrial partner. Our approach was benchmarked against nine classical and modern algorithms, including METIS, Spectral Clustering, and recursive bisection methods. The GNN-FM model achieved highly competitive results, outperforming METIS in 4 out of 6 test meshes by reducing the number of cut edges, while maintaining a perfect balance ratio of 1,0. These results demonstrate that combining spectral encodings with unsupervised GNNs and heuristic refinement yields a powerful and scalable solution for graph partitioning in scientific computing scenarios.