×

Continuation methods for approximate large scale object sequencing. (English) Zbl 1485.90109

Summary: We propose a set of highly scalable algorithms for the combinatorial data analysis problem of seriating similarity matrices. Seriation consists of finding a permutation of data instances, such that similar instances are nearby in the ordering. Applications of the seriation problem can be found in various disciplines such as in bioinformatics for genome sequencing, data visualization and exploratory data analysis. Our algorithms attempt to minimize certain \(p\)-SUM objectives, which also arise in the problem of envelope reduction of sparse matrices. In particular, we present a set of graduated non-convexity algorithms for vector-based relaxations of the general \(p\)-SUM problem for \(p \in \left\{ 2, 1, \tfrac{1}{2}\right\} \) that can scale to very large problem sizes. Different choices of \(p\) emphasize global versus local similarity pattern structure. We conduct a number of experiments to compare our algorithms to various state-of-the-art combinatorial optimization methods on real and synthetic datasets. The experimental results demonstrate that compared to other approaches, the proposed algorithms are very competitive and scale well with large problem sizes.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alter, O., Brown, P. O., & Botstein, D. (2000). Singular value decomposition for genome-wide expression data processing and modeling. Proceedings of the National Academy of Sciences, 97(18), 10,101-10,106.
[2] Anstreicher, K. M. (2003). Recent advances in the solution of quadratic assignment problems. Mathematical Programming, 97(1-2), 27-42. · Zbl 1035.90067
[3] Atkins, J. E., Boman, E. G., & Hendrickson, B. (1998). A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing, 28, 297-310. · Zbl 0930.05064
[4] Barnard, S. T., Pothen, A., & Simon, H. D. (1993). A spectral algorithm for envelope reduction of sparse matrices. In Supercomputing ’93, ACM/IEEE (pp. 493-502). · Zbl 0833.65038
[5] Basak, J. (2008). A least square kernel machine with box constraints. In 19th International conference on pattern recognition (pp. 1-4).
[6] Baudat, G., & Anouar, F. (2001). Kernel-based methods and function approximation. In Proceedings of the international joint conference on neural networks, 2001 (Vol. 2, pp. 1244-1249).
[7] Bazaraa, M. S., & Sherali, H. D. (1982). On the use of exact and heuristic cutting plane methods for the quadratic assignment problem. Journal of the Operational Research Society, 33(11), 991-1003. · Zbl 0497.90042
[8] Bertsekas, D. P. (1995). Nonlinear programming. Belmont: Athena Scientific. · Zbl 0935.90037
[9] Blake, A. (1983). The least-disturbance principle and weak constraints. Pattern Recognition Letters, 1(5), 393-399.
[10] Brusco, M. J., & Stahl, S. (2000). Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. Journal of Classification, 17(2), 197-223. · Zbl 1137.91602
[11] Brusco, M. J., & Stahl, S. (2001). Compact integer-programming models for extracting subsets of stimuli from confusion matrices. Psychometrika, 66(3), 405-419. · Zbl 1293.62239
[12] Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4), 231-357. · Zbl 1365.90196
[13] Burkard, R., & Çela, E. (1999). Linear assignment problems and extensions. In D.-Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 75-149). Alphen aan den Rijn: Kluwer. · Zbl 1253.90131
[14] Burkard, RE; Çela, E.; Pardalos, PM; Pitsoulis, LS; Du, D-Z (ed.); Pardalos, PM (ed.), The quadratic assignment problem, 1713-1809 (1999), Boston, MA
[15] Çela, E. (2013). The quadratic assignment problem: Theory and algorithms (Vol. 1). New York: Springer. · Zbl 0909.90226
[16] Christofides, N., & Benavent, E. (1989). An exact algorithm for the quadratic assignment problem on a tree. Operations Research, 37(5), 760-768. · Zbl 0682.90064
[17] Critchlow, D. E. (2012). Metric methods for analyzing partially ranked data (Vol. 34). New York: Springer. · Zbl 0589.62041
[18] Csurka, G., Dance, C., Fan, L., Willamowski, J., & Bray, C. (2004). Visual categorization with bags of keypoints. In Workshop on statistical learning in computer vision, ECCV, Prague (Vol. 1, pp. 1-22).
[19] Davis, T. A., & Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software38(1), 1-25, URL: http://www.cise.ufl.edu/research/sparse/matrices. · Zbl 1365.65123
[20] Dheeru, D., & Taniskidou, E. K. (2017). UCI machine learning repository. Retrieved April, 2018, from http://archive.ics.uci.edu/ml.
[21] Ding, C., & He, X. (2004). Linearized cluster assignment via spectral ordering. In Proceedings of the 21st international conference on machine learning (pp. 30-37).
[22] Earle, D., & Hurley, C. B. (2015). Advances in dendrogram seriation for application to visualization. Journal of Computational and Graphical Statistics, 24(1), 1-25.
[23] Evangelopoulos, X., Brockmeier, A. J., Mu, T., & Goulermas, J. Y. (2017). A graduated non-convexity relaxation for large scale seriation. In Proceedings of SIAM international conference on data mining, 2017. · Zbl 1485.90109
[24] Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298-305. · Zbl 0265.05119
[25] Fogel, F.; Jenatton, R.; Bach, F.; d’Aspremont, A.; Burges, CJC (ed.); Bottou, L. (ed.); Welling, M. (ed.); Ghahramani, Z. (ed.); Weinberger, KQ (ed.), Convex relaxations for permutation problems, 1016-1024 (2013), Red Hook
[26] Fogel, F., Jenatton, R., Bach, F., & d’Aspremont, A. (2015). Convex relaxations for permutation problems. SIAM Journal on Matrix Analysis and Applications, 36(4), 1465-1488. · Zbl 1338.90336
[27] Fountoulakis, K., & Gondzio, J. (2016). A second-order method for strongly convex \[\ell_1\] ℓ1-regularization problems. Mathematical Programming, 156(1-2), 189-219. · Zbl 1364.90255
[28] Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1-2), 95-110.
[29] Fulkerson, D., & Gross, O. (1965). Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3), 835-855. · Zbl 0132.21001
[30] George, A., & Liu, J. W. (1981). Computer solution of large sparse positive definite systems. Upper Saddle River: Prentice Hall. · Zbl 0516.65010
[31] George, A., & Pothen, A. (1994). An analysis of spectral envelope reduction via quadratic assignment problems. SIAM Journal of Matrix Analysis and Application, 18, 706-732. · Zbl 0874.65032
[32] Glover, F., & Laguna, M. (1997). Tabu Search. Norwell, MA: Kluwer Academic Publishers. · Zbl 0930.90083
[33] Goemans, M. X. (2015). Smallest compact formulation for the permutahedron. Mathematical Programming, 153(1), 5-11. · Zbl 1322.90048
[34] González-Recio, O., & Forni, S. (2011). Genome-wide prediction of discrete traits using Bayesian regressions and machine learning. Genetics Selection Evolution, 43(1), 7.
[35] Goulermas, J. Y., Kostopoulos, A., & Mu, T. (2016). A new measure for analyzing and fusing sequences of objects. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(5), 833-848.
[36] Hahsler, M. (2017). An experimental comparison of seriation methods for one-mode two-way data. European Journal of Operational Research, 257(1), 133-143. · Zbl 1394.90482
[37] Hahsler, M., Hornik, K., & Buchta, C. (2008). Getting things in order: An introduction to the R package seriation. Journal of Statistical Software, 25(3), 1-34.
[38] Hardy, G. H., Littlewood, J. E., & Pólya, G. (1952). Inequalities. Cambridge: Cambridge University Press. · Zbl 0047.05302
[39] Hartley, R. I., & Zisserman, A. (2004). Multiple view geometry in computer vision (2nd ed.). Cambridge: Cambridge University Press. · Zbl 1072.68104
[40] Havens, T. C., & Bezdek, J. C. (2012). An efficient formulation of the improved visual assessment of cluster tendency (iVAT) algorithm. IEEE Transactions on Knowledge and Data Engineering, 24(5), 813-822.
[41] Helmberg, C., Rendl, F., Mohar, B., & Poljak, S. (1995). A spectral approach to bandwidth and separator problems in graphs. Linear and Multilinear Algebra, 39(1-2), 73-90. · Zbl 0832.05093
[42] Hodson, F. R. (1968). The La Tène cemetery at Münsingen-Rain: Catalogue and relative chronology (Vol. 5). Bern: Stämpfli.
[43] Huber, P. J. (1992). Robust estimation of a location parameter. In S. Kotz & N. L. Johnson (Eds.), Breakthroughs in statistics: Methodology and distribution (pp. 492-518). New York, NY: Springer.
[44] Jaggi, M. (2013). Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceedings of the 30th international conference on machine learning, , PMLR, Atlanta, Georgia, USA (Vol. 28, pp. 427-435).
[45] Juvan, M., & Mohar, B. (1992). Optimal linear labelings and eigenvalues of graphs. Discrete Applied Mathematics, 36(2), 153-168. · Zbl 0759.05087
[46] Juvan, M., & Mohar, B. (1993). Laplace eigenvalues and bandwidth-type invariants of graphs. Journal of Graph Theory, 17(3), 393-407. · Zbl 0785.05077
[47] Kendall, D. G. (1971). Abundance matrices and seriation in archaeology. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 17(2), 104-112. · Zbl 0203.30903
[48] Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, 4, 1942-1948.
[49] Lacoste-Julien, S. (2016). Convergence Rate of Frank-Wolfe for non-convex objectives. ArXiv e-prints arXiv:1607.00345.
[50] Lacoste-Julien, S., & Jaggi, M. (2015). On the global linear convergence of Frank-Wolfe optimization variants. In Proceedings of the 28th international conference on neural information processing systems, MIT Press, Cambridge, MA (pp. 496-504).
[51] Laurent, M., & Seminaroti, M. (2015). The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. Operations Research Letters, 43(1), 103-109. · Zbl 1408.90164
[52] Leskovec, J., & Krevl, A. (2014). SNAP datasets: Stanford large network dataset collection. Retrieved April, 2018, from http://snap.stanford.edu/data.
[53] Liiv, I. (2010). Seriation and matrix reordering methods: An historical overview. Statistical Analysis and Data Mining, 3(2), 70-91. · Zbl 07260234
[54] Lim, C. H., & Wright, S. (2014). Beyond the Birkhoff polytope: Convex relaxations for vector permutation problems. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in neural information processing systems (pp. 2168-2176).
[55] Lim, C. H., & Wright, S. (2016a). A box-constrained approach for hard permutation problems. In M. F. Balcan & K. Q. Weinberger (Eds.), Proceedings of the 33rd international conference on machine learning (pp. 2454-2463).
[56] Lim, C. H., & Wright, S. J. (2014). Sorting network relaxations for vector permutation problems. ArXiv e-prints arXiv:1407.6609.
[57] Lim, C. H., & Wright, S. J. (2016b). Efficient Bregman projections onto the permutahedron and related polytopes. In A. Gretton & C. C. Robert (Eds.), Proceedings of the 19th international conference on artificial intelligence and statistics, PMLR, Cadiz, Spain, Proceedings of machine learning research (Vol. 51, pp. 1205-1213).
[58] Liu, Z. Y., & Qiao, H. (2014). GNCCP: Graduated nonconvexity and concavity procedure. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(6), 1258-1267.
[59] Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007). A survey for the quadratic assignment problem. European Journal of Operational Research, 176(2), 657-690. · Zbl 1103.90058
[60] Lowe, D. G. (2004). Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2), 91-110.
[61] Lyzinski, V., Fishkind, D. E., Fiori, M., Vogelstein, J. T., Priebe, C. E., & Sapiro, G. (2016). Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis Machine Intelligence, 38(1), 60-73.
[62] Mavroeidis, D., & Bingham, E. (2010). Enhancing the stability and efficiency of spectral ordering with partial supervision and feature selection. Knowledge and Information Systems, 23(2), 243-265.
[63] McAuley, J., & Leskovec, J. (2012). Learning to discover social circles in ego networks. In Proceedings of the 25th international conference on neural information processing systems, Curran Associates Inc., USA (pp. 539-547).
[64] Mühlenbein, H. (1989). Parallel genetic algorithms population genetics and combinatorial optimization. In Proceedings of the 3rd international conference on genetic algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA (pp. 416-421).
[65] Quadrianto, N., Smola, A. J., Song, L., & Tuytelaars, T. (2010). Kernelized sorting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(10), 1809-1821.
[66] Rangarajan, A., & Chellappa, R. (1990). Generalized graduated nonconvexity algorithm for maximum a posteriori image estimation. In Proceedings of the 10th international conference on pattern recognition (Vol. 2, pp. 127-133).
[67] Recanati, A., Brüls, T., & d’Aspremont, A. (2017). A spectral algorithm for fast de novo layout of uncorrected long nanopore reads. Bioinformatics, 33(20), 3188-3194.
[68] Recanati, A., Servant, N., Vert, J. P., & d’Aspremont, A. (2018). Robust seriation and applications to cancer genomics. ArXiv e-prints arXiv:1806.00664.
[69] Robinson, W. S. (1951). A method for chronologically ordering archaeological deposits. American Antiquity, 16(4), 293-301.
[70] Tien, Y. J., Lee, Y. S., Wu, H. M., & Chen, C. H. (2008). Methods for simultaneously identifying coherent local clusters with smooth global patterns in gene expression profiles. BMC Bioinformatics, 9(1), 155.
[71] Tsafrir, D., Tsafrir, I., Ein-Dor, L., Zuk, O., Notterman, D. A., & Domany, E. (2005). Sorting points into neighborhoods (SPIN): Data analysis and visualization by ordering distance matrices. Bioinformatics, 21(10), 2301-2308.
[72] Tuytelaars, T. (2010). Dense interest points. In IEEE computer society conference on computer vision and pattern recognition (pp. 2281-2288).
[73] Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, E. T., et al. (2015). Fast approximate quadratic programming for graph matching. PLOS ONE, 10(4), 1-17.
[74] Weinberger, K. Q., & Saul, L. K. (2004). Unsupervised learning of image manifolds by semidefinite programming. In Proceedings of the 2004 IEEE computer society conference on computer vision and pattern recognition, IEEE computer society, Washington, DC (pp. 988-995).
[75] Xia, Y. (2010). An efficient continuation method for quadratic assignment problems. Computers & Operations Research, 37(6), 1027-1032. · Zbl 1178.90220
[76] Yang, X. S. (2008). Nature-inspired metaheuristic algorithms. Bristol: Luniver Press.
[77] Zaslavskiy, M., Bach, F., & Vert, J. P. (2009). A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227-2242.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.