Title: Unsupervised Learning of Graph and Hypergraph Clustering
Abstract: Data clustering is an essential unsupervised learningUnsupervised learning problem in data mining, machine learning, and computer vision. In this chapter, we present in more depth our work on clustering, introduced in the first chapter, for which second- or higher order affinities between sets of data points are considered. We introduce our novel, efficient algorithm for graph-based clustering based on a variant of the Integer Projected Fixed Point (IPFP) methodInteger Projected Fixed Point (IPFP) method, adapted for the case of hypergraph clusteringHypergraph clustering. This method has important theoretical properties, such as convergence and satisfaction of first-order necessary optimality conditions. As also discussed in Chap. 1 , the main difference between IPFP applied to graph matchingGraph matching and the case of clustering it is coming from the different mapping constraints on the solution vector. Once the constraints are changed, the clustering algorithm follows directly from IPFP: at each iteration, the objective score is approximated with its first-order Taylor polynomial. Then, a discrete solution, for the resulting linear optimization problem, is found as the optimum. As in the matching case that optimum of the linear approximation, in the real domain of the clustering problem, is discrete. That is a nice property, since the original non-relaxed problem requires a discrete solution, not a real-valued one. Then, the optimum of the original score along the line between the present solution and the discrete one is found in closed form, for second-order (graph) or third-order (hypergraph) clustering tasks. The procedure is repeated several times, until convergence. Usually, convergence happens very soon, after 5–10 iterations, significantly fewer than competing methods. We also present an algorithm for learning the parameters of the higher order affinities in the hypergraph clusteringHypergraph clustering model, which is directly adapted from the approach used for graphGraph matching and hypergraph matchingHypergraph matching. Thus, we learn the affinity functions using gradient ascent, by maximizing the dot product between the ground truth clustering (or the discrete clustering solution in the unsupervised case) and soft clustering solution found by power iteration applied to the hypergraph tensor. In experiments on different model fitting tasks, formulated as third-order clustering, we outperform other top hypergraph clusteringHypergraph clustering methods in the literature, especially in terms of computational speed, but also in terms of accuracy.
Publication Year: 2020
Publication Date: 2020-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot