Structure preserving embedding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Structure preserving embedding

Full text

Pdf (8.28 MB)

Source

ACM International Conference Proceeding Series; Vol. 382 archive
Proceedings of the 26th Annual International Conference on Machine Learning table of contents

Montreal, Quebec, Canada

Pages 937-944

Year of Publication: 2009

ISBN:978-1-60558-516-1

Authors

Blake Shaw	Columbia University, New York, NY
Tony Jebara	Columbia University, New York, NY

Sponsors

: MITACS
: NSF
Microsoft Research : Microsoft Research

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 49, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1553374.1553494 What is a DOI?

ABSTRACT

Structure Preserving Embedding (SPE) is an algorithm for embedding graphs in Euclidean space such that the embedding is low-dimensional and preserves the global topological properties of the input graph. Topology is preserved if a connectivity algorithm, such as k-nearest neighbors, can easily recover the edges of the input graph from only the coordinates of the nodes after embedding. SPE is formulated as a semidefinite program that learns a low-rank kernel matrix constrained by a set of linear inequalities which captures the connectivity structure of the input graph. Traditional graph embedding algorithms do not preserve structure according to our definition, and thus the resulting visualizations can be misleading or less informative. SPE provides significant improvements in terms of visualization and lossless compression of graphs, outperforming popular methods such as spectral embedding and Laplacian eigen-maps. We find that many classical graphs and networks can be properly embedded using only a few dimensions. Furthermore, introducing structure preserving constraints into dimensionality reduction algorithms produces more accurate representations of high-dimensional data.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Adamic, L. A., & Glance, N. (2005). The political blogosphere and the 2004 US election. WWW-2005 Workshop on the Weblogging Ecosystem.
	2	Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
	3	Asuncion, A., & Newman, D. (2007). UCI machine learning repository. http://www.ics.uci.edu/~mlearn/MLRepository.html.
	4	Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
	5	Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
	6	Burer, S., & Monteiro, R. D. C. (2003). A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming (series B), 95(2), 329--357.
	7	Chung, F. R. K. (1997). Spectral graph theory. American Mathematical Society.
	8	Cox, T., & M. Cox (1994). Multidimensional scaling. Chapman & Hall.
	9	Thomas Finley , Thorsten Joachims, Training structural SVMs when exact inference is intractable, Proceedings of the 25th international conference on Machine learning, p.304-311, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390195]
	10	Fremuth-Paeger, C., & Jungnickel, D. (1999). Balanced network flows, a unifying framework for design and analysis of matching algorithms. Networks, 33, 1--28.
	11	Roweis, S., & Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.
	12	Shaw, B., & Jebara, T. (2007). Minimum volume embedding. Proc. of the 11^th International Conference on Artificial Intelligence and Statistics (pp. 460--467).
	13	Snapp, R., & Venkatesh, S. (1998). Asymptotic expansions of the k nearest neighbor risk. The Annals of Statistics, 26, 850--878.
	14	Sontag, D., & Jaakkola, T. (2008). New outer bounds on the marginal polytope. Advances in Neural Information Processing Systems 20 (pp. 1393--1400).
	15	Tenenbaum, J., de Silva, V., & Langford, J. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.
	16	Weinberger, K. Q., Packer, B. D., & Saul, L. K. (2005). Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization. Proc. of the of the 10^th International Workshop on Artificial Intelligence and Statistics (pp. 381--388).