Abstract
The time complexity of support vector machines (SVMs) prohibits training onhuge data sets with millions of samples. Recently, multilevel approaches totrain SVMs have been developed to allow for time efficient training on hugedata sets. While regular SVMs perform the entire training in one - timeconsuming - optimization step, multilevel SVMs first build a hierarchy ofproblems decreasing in size that resemble the original problem and then trainan SVM model for each hierarchy level benefiting from the solved models ofprevious levels. We present a faster multilevel support vector machine thatuses a label propagation algorithm to construct the problem hierarchy.Extensive experiments show that our new algorithm achieves speed-ups up to twoorders of magnitude while having similar or better classification quality overstate-of-the-art algorithms.