Vector-Based Approach to the Max-Cut Problem: Conversion to Clustering and Validation on Structured Graphs

• Jailon W. B. Oliveira da Silva UFC
• Carlos V. Dantas Araújo UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/eniac.2025.13098

Abstract

This paper proposes an unsupervised approach for the Maximum Cut Problem (Max-Cut) through conversion to a clustering task. It combines three vertex representations (Node2Vec, Spectral, and local attributes) with KMeans and hierarchical algorithms. Validation on 57 instances from the Big Mac Library (clustering coefficient > 0.2) shows superior performance of local attributes representation with KMeans (91.4% similarity, 41 instances > 90%), followed by Spectral (82%) and Node2Vec (72%). Results indicate effectiveness in highly clustered graphs, with limitations in sparse structures (coefficient < 0.2). The approach replaces combinatorial methods with direct vector analysis, offering a scalable solution for medium-scale Max-Cut.

References

Barahona, F. (1982). On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241.

Barrat, A., Barthélemy, M., Pastor-Satorras, R., and Vespignani, A. (2004). The architecture of complex weighted networks. PNAS, 101(11):3747–3752.

Farhi, E., Goldstone, J., and Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.

Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23(2):298–305.

Freeman, L. C. (1978). Centrality in social networks conceptual clarification. Social networks, 1(3):215–239.

Garey, M. R. and Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. Freeman.

Ghahramani, Z. (2004). Unsupervised learning. Advanced lectures on machine learning, pages 72–112.

Goemans, M. X. and Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145.

Grover, A. and Leskovec, J. (2016). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864.

Hamilton, W. L., Ying, R., and Leskovec, J. (2017). Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3):52–74.

Liers, F., Nieberg, T., and Pardella, G. (2011). Via minimization in vlsi chip design-application of a planar max-cut algorithm.

Lloyd, S. (1982). Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129–137.

Newman, M. (2018). Networks. Oxford university press.

Opsahl, T., Agneessens, F., and Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social networks, 32(3):245–251.

Rendl, F., Rinaldi, G., and Wiegele, A. (2010a). Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming, 121:307–335.

Rendl, F., Rinaldi, G., and Wiegele, A. (2010b). Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Programming, 121(2):307.

Schaeffer, S. E. (2007). Graph clustering. Computer science review, 1(1):27–64.

Tsitsulin, A., Palowitch, J., Perozzi, B., and Müller, E. (2023). Graph clustering with graph neural networks. JMLR, 24:1–21.

Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17:395–416.

Ward Jr, J. H. (1963). Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301):236–244.

Wiegele, A. (2007). Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint, 51.