TRAINING OF SUPERVISED MODELS WITH STRUCTURAL INSTANCES FOR MAXIMUM SECTION

This study applies supervised Machine Learning algorithms to the Max-Cut Problem, using instances from the Biq Mac Library. Models such as Naive Bayes, kNN, Logistic Regression, and Feedforward Neural Networks were trained on graphs ranging from 20 to 500 vertices, preprocessed with PCA and normalization. Logistic Regression stood out with a 96.34\% approximation to the cut values obtained by the Biq Mac solver, while overall, the models proved effective on graphs with high clustering coefficients and homogeneous betweenness centrality. The analysis revealed that selecting instances with compatible structural features (e.g., density $>$ 0.4) is crucial, with dimensionality reduction via PCA being critical for sparse graphs. The results highlight the potential of specialized models for structural graph subsets, providing a foundation for large-scale combinatorial optimization applications.