Abstract
Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Luce, R.D., Perry, A.D.: A method for matrix analysis of group structure. Psychometrika 14, 94–114 (1949)
Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6, 281–297 (1999)
Sugihara, G.: Graph theory, homology and food webs. Proc. Symp. Appl. Math. 30, 83–101 (1984)
Prihar, Z.: Topological properties of telecommunication networks. Proc. IRE 44, 927–933 (1956)
Rhodes, N., Willett, P., Calvet, A., Dunbar, J.B., Humblet, C.: CLIP: similarity searching of 3D databases using clique detection. J. Chem. Inf. Comput. Sci. 43(2), 443–448 (2003)
Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos P.M. (eds.) Handbook of Combinatorial Optimization, pp. 1–74. Springer, New York (1999). doi:10.1007/978-1-4757-3023-4
Wu, Q., Hao, J.-K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015)
Grosso, A., Locatelli, M., Pullan, W.: Simple ingredients leading to very efficient heuristics for the maximum clique problem. J. Heuristics 14, 587–612 (2008)
Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turan. Can. J. Math. 17, 533–540 (1965)
Bomze, I.M.: Evolution towards the maximum clique. J. Glob. Optim. 10, 143–164 (1997)
Ding, C., Li, T., Jordan, M.I.: Non-negative matrix factorization for combinatorial optimization: spectral clustering, graph matching and clique finding. IEEE Int. Conf. Data Mining 44, 183–192 (2008)
Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterization of the maximum clique problem. Math. Oper. Res. 22(3), 754–768 (1997)
Pardalos, P.M., Phillips, A.T.: A global optimization approach for solving the maximum clique problem. Int. J. Comput. Math. 17, 533–540 (1990)
Pelillo, M.: Relaxation labeling networks for the maximum clique problem. J. Artif. Neural Netw. 2(4), 313–328 (1995)
Du, G., Gu, J., Pardalos, P.M.: Satisfiability Problem: Theory and Applications, DIMACS Series, vol. 35. American Mathematical Society, Providence (1997)
Horst, R., Pardalos, P.M., Van Thoai, N.: Introduction to Global Optimization. Springer, Berlin (2000)
Pardalos, P.M., Xue, J.: The maximum clique problem. J. Glob. Optim. 4, 301–328 (1992)
Gillis, N., Glineur, F.: Continuous characterization of the maximum-edge biclique problem. J. Glob. Optim. 58, 439–464 (2014)
Belachew, M.T., Gillis N.: Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation. arXiv:1505.07077 (2015)
Ho, N.D.: Non-negative Matrix Factorization Algorithms and Applications. Doctoral dissertation, Université catholique de Louvain (2008)
Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)
Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Math. Prog. 39, 93–116 (1987)
Lin, C.-J., Moré, J.J.: Newton’s method for large bound-constrained optimization problems. SIAM J. Optim. 9(4), 1100–1127 (1999)
Golub, G.H., Loan, C.F.V.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996)
Vandaele, A., Gillis, N., Glineur, F., Tuyttens, D.: Heuristics for exact non-negative matrix factorization. J. Glob. Optim. 65(2), 369–400 (2016)
Berman, A., Plemmons, R.J.: Non-negative Matrices in the Mathematical Sciences. SIAM, Philadelphia (1994)
Acknowledgements
This research was conducted when the first author was visiting the Department of Mathematics and Operational Research at the University of Mons. We would like to thank the reviewers and Prof. Kunal Narayan Chaudhury for their insightful feedback that helped us improve the paper significantly. NG acknowledges the support of the F.R.S–FNRS (incentive Grant for Scientific Research No. F.4501.16) and of the ERC (Starting Grant No. 679515).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Jim Luedtke.
Rights and permissions
About this article
Cite this article
Belachew, M.T., Gillis, N. Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation. J Optim Theory Appl 173, 279–296 (2017). https://doi.org/10.1007/s10957-016-1043-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-016-1043-6
Keywords
- Maximum clique problem
- Motzkin–Straus formulation
- Symmetric rank-one non-negative matrix approximation
- Clique finding algorithm