Fast Graph Construction Using Auction Algorithm
This addresses the need for efficient graph construction in machine learning applications like clustering and classification, though it is incremental as it applies an existing auction algorithm to this specific bottleneck.
The paper tackles the problem of constructing sparse, balanced subgraphs from data vectors, which is computationally expensive with existing methods, and uses an auction algorithm to achieve significantly reduced computational cost while maintaining accuracy.
In practical machine learning systems, graph based data representation has been widely used in various learning paradigms, ranging from unsupervised clustering to supervised classification. Besides those applications with natural graph or network structure data, such as social network analysis and relational learning, many other applications often involve a critical step in converting data vectors to an adjacency graph. In particular, a sparse subgraph extracted from the original graph is often required due to both theoretic and practical needs. Previous study clearly shows that the performance of different learning algorithms, e.g., clustering and classification, benefits from such sparse subgraphs with balanced node connectivity. However, the existing graph construction methods are either computationally expensive or with unsatisfactory performance. In this paper, we utilize a scalable method called auction algorithm and its parallel extension to recover a sparse yet nearly balanced subgraph with significantly reduced computational cost. Empirical study and comparison with the state-ofart approaches clearly demonstrate the superiority of the proposed method in both efficiency and accuracy.