Fitting a Graph to Vector Data

Samuel I. Daitch, Jonathan A. Kelner, Daniel A. Spielman

ICML 2009 pp. 201-208

doi:10.1145/1553374.1553400 /icml/2009/daitch2009icml-fitting/

Abstract

We introduce a measure of how well a combinatorial graph fits a collection of vectors. The optimal graphs under this measure may be computed by solving convex quadratic programs and have many interesting properties. For vectors in d dimensional space, the graphs always have average degree at most 2(d + 1), and for vectors in 2 dimensions they are always planar. We compute these graphs for many standard data sets and show that they can be used to obtain good solutions to classification, regression and clustering problems.

PDF ICML Semantic Scholar

Cite

Text

Daitch et al. "Fitting a Graph to Vector Data." International Conference on Machine Learning, 2009. doi:10.1145/1553374.1553400

Markdown

[Daitch et al. "Fitting a Graph to Vector Data." International Conference on Machine Learning, 2009.](https://mlanthology.org/icml/2009/daitch2009icml-fitting/) doi:10.1145/1553374.1553400

BibTeX

@inproceedings{daitch2009icml-fitting,
  title     = {{Fitting a Graph to Vector Data}},
  author    = {Daitch, Samuel I. and Kelner, Jonathan A. and Spielman, Daniel A.},
  booktitle = {International Conference on Machine Learning},
  year      = {2009},
  pages     = {201-208},
  doi       = {10.1145/1553374.1553400},
  url       = {https://mlanthology.org/icml/2009/daitch2009icml-fitting/}
}