The dominant algorithms for machine learning tasks fall most often in the realm of AI or continuous optimization of intractable problems.  We present combinatorial algorithms for machine learning, data mining, and image segmentation that, unlike the majority of existing machine learning methods, utilize pairwise similarities. These algorithms are efficient and reduce the classification problem to a network flow problem on a graph. One of these algorithms addresses the problem of finding a cluster that is as dissimilar as possible from the complement, while having high similarity within the cluster, is called HNC (Hochbaum’s Normalized Cut). The two objectives are combined either as a ratio or with linear weights. HNC is a variant of normalized cut, which is intractable, and is solved, heuristically, with the spectral technique.  An extensive empirical study demonstrates that incorporating the use of pairwise similarities improves accuracy of classification and clustering.  Another experimental study that compared the performance of HNC to that of the spectral technique, for imaging instances, demonstrates that in practice HNC’s performance dominates the performance of the spectral technique.  To address the quadratic rate of growth in the size of the data with the use of similarities we employ a method called “sparse computation”. It is shown that using “sparse computation” enables the scalability of similarity-based algorithms to very large-scale data sets while maintaining high levels of accuracy. We demonstrate several applications of variants of HNC for data mining, medical imaging, and image segmentation tasks, including the recent use of HNC for cell identification in neuroscience datasets.