{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T16:05:59Z","timestamp":1783440359891,"version":"3.54.6"},"reference-count":43,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,2,17]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The presence of manifolds is a common assumption in many applications, including astronomy and computer vision. For instance, in astronomy, low-dimensional stellar structures, such as streams, shells, and globular clusters, can be found in the neighborhood of big galaxies such as the Milky Way. Since these structures are often buried in very large data sets, an algorithm, which can not only recover the manifold but also remove the background noise (or outliers), is highly desirable. While other works try to recover manifolds either by pushing all points toward manifolds or by downsampling from dense regions, aiming to solve one of the problems, they generally fail to suppress the noise on manifolds and remove background noise simultaneously. Inspired by the collective behavior of biological ants in food-seeking process, we propose a new algorithm that employs several random walkers equipped with a local alignment measure to detect and denoise manifolds. During the walking process, the agents release pheromone on data points, which reinforces future movements. Over time the pheromone concentrates on the manifolds, while it fades in the background noise due to an evaporation procedure. We use the Markov chain (MC) framework to provide a theoretical analysis of the convergence of the algorithm and its performance. Moreover, an empirical analysis, based on synthetic and real-world data sets, is provided to demonstrate its applicability in different areas, such as improving the performance of t-distributed stochastic neighbor embedding (t-SNE) and spectral clustering using the underlying MC formulas, recovering astronomical low-dimensional structures, and improving the performance of the fast Parzen window density estimator.<\/jats:p>","DOI":"10.1162\/neco_a_01478","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T20:23:22Z","timestamp":1642105402000},"page":"595-641","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":4,"title":["Manifold Alignment Aware Ants: A Markovian Process for Manifold Extraction"],"prefix":"10.1162","volume":"34","author":[{"given":"Mohammad","family":"Mohammadi","sequence":"first","affiliation":[{"name":"Faculty of Science and Engineering, University of Groningen, Groningen 9747AA, The Netherlands mohammadimathstar@gmail.com"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Tino","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Birmingham, Birmingham B15 2TT p.tino@cs.bham.ac.uk"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kerstin","family":"Bunte","sequence":"additional","affiliation":[{"name":"Faculty of Science and Engineering, University of Groningen, Groningen 9747 AG, The Netherlands k.bunte@rug.nl"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","published-online":{"date-parts":[[2022,2,17]]},"reference":[{"issue":"6","key":"2022022323294966400_B1","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1162\/089976603321780317","article-title":"Laplacian eigenmaps for dimensionality reduction and data representation","volume":"15","author":"Belkin","year":"2003","journal-title":"Neural Computation"},{"issue":"9","key":"2022022323294966400_B2","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary search trees used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Communications of the ACM"},{"issue":"3","key":"2022022323294966400_B3","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.acha.2015.03.002","article-title":"Local kernels and the geometric structure of data","volume":"40","author":"Berry","year":"2016","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2022022323294966400_B4","unstructured":"Bishop, C. M.\n           (2006). Pattern recognition and machine learning. Berlin: Springer."},{"key":"2022022323294966400_B5","unstructured":"Blum, C., Roli, A., & Dorigo, M. (2001). HC\u2013ACO: The hyper-cube framework for ant colony optimization. In Proceedings of the Metaheuristics International Conference, vol. 2 (pp. 399\u2013403)."},{"key":"2022022323294966400_B6","doi-asserted-by":"crossref","unstructured":"Chu, S.-C., Roddick, J. F., Su, C.-J., & Pan, J.-S. (2004). Constrained ant colony optimization for data clustering. In Proceedings of the Pacific Rim International Conference on Artificial Intelligence (pp. 534\u2013543). Berlin: Springer.","DOI":"10.1007\/978-3-540-28633-2_57"},{"key":"2022022323294966400_B7","unstructured":"Cinlar, E.\n           (2013). Introduction to stochastic processes. North Chelmsford, MA: Courier Corporation."},{"issue":"1","key":"2022022323294966400_B8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.acha.2006.04.006","article-title":"Diffusion maps","volume":"21","author":"Coifman","year":"2006","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"5","key":"2022022323294966400_B9","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1162\/neco_a_01184","article-title":"Introducing user-prescribed constraints in Markov chains for nonlinear dimensionality reduction","volume":"31","author":"Dixit","year":"2019","journal-title":"Neural Computation"},{"issue":"10","key":"2022022323294966400_B10","doi-asserted-by":"publisher","first-page":"5591","DOI":"10.1073\/pnas.1031596100","article-title":"Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data","volume":"100","author":"Donoho","year":"2003","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"2022022323294966400_B11","unstructured":"Dorigo, M.\n           (1992). Optimization, learning and natural algorithms. PhD diss., Politecnico di Milano."},{"key":"2022022323294966400_B12","unstructured":"Dorigo, M., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy (Technical Report 91-016). Politecnico di Milano, Italy."},{"issue":"1","key":"2022022323294966400_B13","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1109\/3477.484436","article-title":"Ant system: Optimization by a colony of cooperating agents","volume":"26","author":"Dorigo","year":"1996","journal-title":"IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)"},{"key":"2022022323294966400_B14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1051\/0004-6361\/201833051","article-title":"Gaia data release 2: Summary of the contents and survey properties","volume":"616","author":"Collaboration","year":"2018","journal-title":"Astronomy and Astrophysics"},{"key":"2022022323294966400_B15","doi-asserted-by":"crossref","unstructured":"Gil, C., Ba\u00f1os, R., Ortega, J., M\u00e1rquez, A. L., Fern\u00e1ndez, A., & Montoya, M. (2011). Ant colony optimization for water distribution network design: A comparative study. In Proceedings of the International Work-Conference on Artificial Neural Networks (pp. 300\u2013307). Berlin: Springer.","DOI":"10.1007\/978-3-642-21498-1_38"},{"key":"2022022323294966400_B16","first-page":"505","volume-title":"Advances in neural information processing systems, 18","author":"Goldberger","year":"2005"},{"key":"2022022323294966400_B17","unstructured":"Golub, G. H., & Van Loan, C. F. (2012). Matrix computations. Baltimore, MD: Johns Hopkins University Press."},{"key":"2022022323294966400_B18","unstructured":"Gong, D., Sha, F., & Medioni, G. (2010). Locally linear denoising on image manifolds. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics (pp. 265\u2013272)."},{"issue":"3","key":"2022022323294966400_B19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1142\/S0129065710002383","article-title":"Principal manifolds and graphs in practice: From molecular biology to dynamical systems","volume":"20","author":"Gorban","year":"2010","journal-title":"International Journal of Neural Systems"},{"key":"2022022323294966400_B20","first-page":"561","volume-title":"Advances in neural information processing systems","author":"Hein","year":"2006"},{"issue":"2","key":"2022022323294966400_B21","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1093\/imaiai\/iau004","article-title":"Non-asymptotic analysis of tangent space perturbation","volume":"3","author":"Kaslovsky","year":"2014","journal-title":"Information and Inference: A Journal of the IMA"},{"key":"2022022323294966400_B22","first-page":"13333","volume-title":"Advances in neural information processing systems","author":"Klicpera","year":"2019"},{"key":"2022022323294966400_B23","doi-asserted-by":"crossref","unstructured":"Kulkarni, V. G.\n           (1999). Modeling, analysis, design, and control of stochastic systems. Berlin: Springer.","DOI":"10.1007\/978-1-4757-3098-2"},{"issue":"2","key":"2022022323294966400_B24","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s10208-014-9221-0","article-title":"Robust computation of linear models by convex relaxation","volume":"15","author":"Lerman","year":"2015","journal-title":"Foundations of Computational Mathematics"},{"key":"2022022323294966400_B25","first-page":"1","article-title":"Path-based spectral clustering: Guarantees, robustness to outliers, and fast algorithms","volume":"21","author":"Little","year":"2020","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"2022022323294966400_B26","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1016\/j.acha.2015.09.009","article-title":"Multiscale geometric methods for data sets I: Multiscale SVD, noise and curvature","volume":"43","author":"Little","year":"2017","journal-title":"Applied and Computational Harmonic Analysis"},{"issue":"4","key":"2022022323294966400_B27","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1287\/ijoc.11.4.358","article-title":"Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem","volume":"11","author":"Maniezzo","year":"1999","journal-title":"INFORMS Journal on Computing"},{"key":"2022022323294966400_B28","doi-asserted-by":"crossref","unstructured":"Mohammadi, M., & Bunte, K. (2020). Multi-agent based manifold denoising. In Proceedings of the International Conference on Intelligent Data Engineering and Automated Learning (pp. 12\u201324). Berlin: Springer.","DOI":"10.1007\/978-3-030-62365-4_2"},{"key":"2022022323294966400_B29","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.neucom.2018.10.081","article-title":"Globular cluster detection in the Gaia survey","volume":"342","author":"Mohammadi","year":"2019","journal-title":"Neurocomputing"},{"issue":"1","key":"2022022323294966400_B30","first-page":"1","article-title":"Ant colony optimisation for vehicle routing problems: From theory to applications","volume":"9","author":"Rizzoli","year":"2004","journal-title":"Galleria Rassegna Bimestrale Di Cultura"},{"issue":"5500","key":"2022022323294966400_B31","doi-asserted-by":"publisher","first-page":"2323","DOI":"10.1126\/science.290.5500.2323","article-title":"Nonlinear dimensionality reduction by locally linear embedding","volume":"290","author":"Roweis","year":"2000","journal-title":"Science"},{"issue":"12","key":"2022022323294966400_B32","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1002\/int.20111","article-title":"Ant colony optimization of clustering models","volume":"20","author":"Runkler","year":"2005","journal-title":"International Journal of Intelligent Systems"},{"issue":"8","key":"2022022323294966400_B33","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","article-title":"Max\u2013min ant system","volume":"16","author":"St\u00fctzle","year":"2000","journal-title":"Future Generation Computer Systems"},{"issue":"1","key":"2022022323294966400_B34","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0164-1212(03)00216-4","article-title":"ACODF: A novel data clustering approach for data mining in large databases","volume":"73","author":"Tsai","year":"2004","journal-title":"Journal of Systems and Software"},{"key":"2022022323294966400_B35","doi-asserted-by":"crossref","unstructured":"Tu, L. W.\n           (2011). An introduction to manifolds. Berlin: Springer.","DOI":"10.1007\/978-1-4419-7400-6"},{"issue":"11","key":"2022022323294966400_B36","first-page":"2579","article-title":"Visualizing data using t-SNE","volume":"9","author":"Van der Maaten","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"2022022323294966400_B37","first-page":"849","volume-title":"Advances in neural information processing systems, 16","author":"Vincent","year":"2003"},{"issue":"4","key":"2022022323294966400_B38","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","author":"Luxburg","year":"2007","journal-title":"Statistics and Computing"},{"key":"2022022323294966400_B39","doi-asserted-by":"crossref","unstructured":"Wang, W., & Carreira-Perpin\u00e1n, M. A. (2010). Manifold blurring mean shift algorithms for manifold denoising. In Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (pp. 1759\u20131766). Piscataway, NJ: IEEE.","DOI":"10.1109\/CVPR.2010.5539845"},{"key":"2022022323294966400_B40","doi-asserted-by":"crossref","unstructured":"Wang, X., Tino, P., & Fardal, M. A. (2008). Multiple manifolds learning framework based on hierarchical mixture density model. In Proceedings of the European Conference on Machine Learning and Principles and Practices of Knowledge Discovery in Databases (pp. 566\u2013581). Berlin: Springer.","DOI":"10.1007\/978-3-540-87481-2_37"},{"key":"2022022323294966400_B41","doi-asserted-by":"crossref","unstructured":"Wang, X., Tino, P., Fardal, M. A., Raychaudhury, S., & Babul, A. (2009). Fast Parzen window density estimator. In Proceedings of the 2009 International Joint Conference on Neural Networks (pp. 3267\u20133274). Piscataway, NJ: IEEE.","DOI":"10.1109\/IJCNN.2009.5178637"},{"issue":"4","key":"2022022323294966400_B42","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TNN.2010.2040835","article-title":"Simplifying mixture models through function approximation","volume":"21","author":"Zhang","year":"2010","journal-title":"IEEE Transactions on Neural Networks"},{"key":"2022022323294966400_B43","doi-asserted-by":"crossref","unstructured":"Zhang, Z., & Zha, H. (2003). Nonlinear dimension reduction via local tangent space alignment. In Proceedings of the International Conference on Intelligent Data Engineering and Automated Learning (pp. 477\u2013481). Berlin: Springer.","DOI":"10.1007\/978-3-540-45080-1_66"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/34\/3\/595\/1989495\/neco_a_01478.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/34\/3\/595\/1989495\/neco_a_01478.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T23:30:21Z","timestamp":1645659021000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/34\/3\/595\/109086\/Manifold-Alignment-Aware-Ants-A-Markovian-Process"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,17]]},"references-count":43,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,2,17]]},"published-print":{"date-parts":[[2022,2,17]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01478","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,3]]},"published":{"date-parts":[[2022,2,17]]}}}