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

Resumo

Este trabalho propõe uma abordagem não supervisionada para o Problema do Corte Máximo (Max-Cut) via conversão em tarefa de agrupamento. Combina três representações de vértices (Node2Vec, Spectral e atributos locais) com algoritmos KMeans e hierárquico. Validação em 57 instâncias da Big Mac Library (coeficiente de aglomeração > 0.2) mostra desempenho superior da representação por atributos locais com KMeans (91.4% de similaridade, 41 instâncias > 90%), seguida por Spectral (82%) e Node2Vec (72%). Resultados indicam eficácia em grafos com alta aglomeração, com limitações em estruturas esparsas (coeficiente < 0.2). A abordagem substitui métodos combinatórios por análise vetorial direta, oferecendo solução escalável para Max-Cut em média escala.

Referências

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.