%0 Conference Paper %1 shaw_structure_2009 %A Shaw, Blake %A Jebara, Tony %B Proceedings of the 26th Annual International Conference on Machine Learning - ICML '09 %C Montreal, Quebec, Canada %D 2009 %I ACM Press %K Embedding_Algorithm Matrix_Factorization Node_Embeddings %P 1--8 %R 10.1145/1553374.1553494 %T Structure preserving embedding %U http://portal.acm.org/citation.cfm?doid=1553374.1553494 %X Structure Preserving Embedding (SPE) is an algorithm for embedding graphs in Euclidean space such that the embedding is lowdimensional 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 eigenmaps. 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 highdimensional data. %@ 978-1-60558-516-1

@inproceedings{shaw_structure_2009, abstract = {Structure Preserving Embedding (SPE) is an algorithm for embedding graphs in Euclidean space such that the embedding is lowdimensional 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 eigenmaps. 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 highdimensional data.}, added-at = {2020-02-21T16:09:44.000+0100}, address = {Montreal, Quebec, Canada}, author = {Shaw, Blake and Jebara, Tony}, biburl = {https://www.bibsonomy.org/bibtex/271a1cb1f55a6caecd8b690ce3d665628/tschumacher}, booktitle = {Proceedings of the 26th {Annual} {International} {Conference} on {Machine} {Learning} - {ICML} '09}, doi = {10.1145/1553374.1553494}, file = {Shaw, Jebara - Structure Preserving Embedding.pdf:C\:\\Users\\Admin\\Documents\\Research\\_Paperbase\\Graph Embeddings\\Shaw, Jebara - Structure Preserving Embedding.pdf:application/pdf}, interhash = {e24515bc82063e2ed55838863e901f4d}, intrahash = {71a1cb1f55a6caecd8b690ce3d665628}, isbn = {978-1-60558-516-1}, keywords = {Embedding_Algorithm Matrix_Factorization Node_Embeddings}, language = {en}, pages = {1--8}, publisher = {ACM Press}, timestamp = {2020-02-21T16:09:44.000+0100}, title = {Structure preserving embedding}, url = {http://portal.acm.org/citation.cfm?doid=1553374.1553494}, urldate = {2020-01-31}, year = 2009 }