A graphical heuristic constructs an information graph via approximate nearest neighbors and applies clustering to reduce or partition training data, achieving faster training than LIBSVM's shrinking heuristic with comparable or better prediction accuracy.
Spectrally approximating large graphs with smaller graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
How does coarsening affect the spectrum of a general graph? We provide conditions such that the principal eigenvalues and eigenspaces of a coarsened and original graph Laplacian matrices are close. The achieved approximation is shown to depend on standard graph-theoretic properties, such as the degree and eigenvalue distributions, as well as on the ratio between the coarsened and actual graph sizes. Our results carry implications for learning methods that utilize coarsening. For the particular case of spectral clustering, they imply that coarse eigenvectors can be used to derive good quality assignments even without refinement---this phenomenon was previously observed, but lacked formal justification.
fields
cs.LG 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A graphical heuristic for reduction and partitioning of large datasets for scalable supervised training
A graphical heuristic constructs an information graph via approximate nearest neighbors and applies clustering to reduce or partition training data, achieving faster training than LIBSVM's shrinking heuristic with comparable or better prediction accuracy.