A Graph Isomorphism Neural Network Algorithm For Solving The Maximum Clique Problem

Combinatorial Optimization (CO), as a crucial domain within optimization, has been spanned across a broad spectrum of fields, imparting significant practical relevance to the study of combinatorial optimization problems. Graph Neural Network (GNN) emerged as an algorithmic framework adept at learning from graph-structured data through deep learning techniques. Notably, its outstanding performance has garnered substantial attention from scholars, spurring in-depth investigations. This research specifically delved into the application of graph neural networks in addressing the maximum clique problem, offering a feasible scheme for leveraging GNNs to tackle optimization challenges constrained by various factors. The proposed methodology employed graph neural networks and utilized unsupervised loss functions for training, while weight sharing among networks was implemented to enhance the accuracy in predicting the membership probability of each node within the maximum clique. Ultimately, the optimal solution was derived through a decoder. Comparative analyses conducted on real-world datasets underscored the efficacy of the proposed scheme when juxtaposed against existing approaches.