%0 Conference Paper %1 ou_asymmetric_2016 %A Ou, Mingdong %A Cui, Peng %A Pei, Jian %A Zhang, Ziwei %A Zhu, Wenwu %B Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD '16 %C San Francisco, California, USA %D 2016 %I ACM Press %K Embedding_Algorithm Matrix_Factorization Node_Embeddings %P 1105--1114 %R 10.1145/2939672.2939751 %T Asymmetric Transitivity Preserving Graph Embedding %U http://dl.acm.org/citation.cfm?doid=2939672.2939751 %X Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity well, which is a critical property of directed graphs. Asymmetric transitivity depicts the correlation among directed edges, that is, if there is a directed path from u to v, then there is likely a directed edge from u to v. Asymmetric transitivity can help in capturing structures of graphs and recovering from partially observed graphs. To tackle this challenge, we propose the idea of preserving asymmetric transitivity by approximating high-order proximity which are based on asymmetric transitivity. In particular, we develop a novel graph embedding algorithm, High-Order Proximity preserved Embedding (HOPE for short), which is scalable to preserve high-order proximities of large scale graphs and capable of capturing the asymmetric transitivity. More specifically, we first derive a general formulation that cover multiple popular highorder proximity measurements, then propose a scalable embedding algorithm to approximate the high-order proximity measurements based on their general formulation. Moreover, we provide a theoretical upper bound on the RMSE (Root Mean Squared Error) of the approximation. Our empirical experiments on a synthetic dataset and three realworld datasets demonstrate that HOPE can approximate the high-order proximities significantly better than the state-ofart algorithms and outperform the state-of-art algorithms in tasks of reconstruction, link prediction and vertex recommendation. %@ 978-1-4503-4232-2

@inproceedings{ou_asymmetric_2016, abstract = {Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity well, which is a critical property of directed graphs. Asymmetric transitivity depicts the correlation among directed edges, that is, if there is a directed path from u to v, then there is likely a directed edge from u to v. Asymmetric transitivity can help in capturing structures of graphs and recovering from partially observed graphs. To tackle this challenge, we propose the idea of preserving asymmetric transitivity by approximating high-order proximity which are based on asymmetric transitivity. In particular, we develop a novel graph embedding algorithm, High-Order Proximity preserved Embedding (HOPE for short), which is scalable to preserve high-order proximities of large scale graphs and capable of capturing the asymmetric transitivity. More specifically, we first derive a general formulation that cover multiple popular highorder proximity measurements, then propose a scalable embedding algorithm to approximate the high-order proximity measurements based on their general formulation. Moreover, we provide a theoretical upper bound on the RMSE (Root Mean Squared Error) of the approximation. Our empirical experiments on a synthetic dataset and three realworld datasets demonstrate that HOPE can approximate the high-order proximities significantly better than the state-ofart algorithms and outperform the state-of-art algorithms in tasks of reconstruction, link prediction and vertex recommendation.}, added-at = {2020-02-21T16:09:44.000+0100}, address = {San Francisco, California, USA}, author = {Ou, Mingdong and Cui, Peng and Pei, Jian and Zhang, Ziwei and Zhu, Wenwu}, biburl = {https://www.bibsonomy.org/bibtex/20dcff51ab81c3436e8ee744232ecba87/tschumacher}, booktitle = {Proceedings of the 22nd {ACM} {SIGKDD} {International} {Conference} on {Knowledge} {Discovery} and {Data} {Mining} - {KDD} '16}, doi = {10.1145/2939672.2939751}, file = {Ou et al - Asymmetric Transitivity Preserving Graph Embedding.pdf:C\:\\Users\\Admin\\Documents\\Research\\_Paperbase\\Graph Embeddings\\Ou et al - Asymmetric Transitivity Preserving Graph Embedding.pdf:application/pdf}, interhash = {be90a93c2a6af92e63fba65bbe29b91b}, intrahash = {0dcff51ab81c3436e8ee744232ecba87}, isbn = {978-1-4503-4232-2}, keywords = {Embedding_Algorithm Matrix_Factorization Node_Embeddings}, language = {en}, pages = {1105--1114}, publisher = {ACM Press}, timestamp = {2020-02-21T16:09:44.000+0100}, title = {Asymmetric {Transitivity} {Preserving} {Graph} {Embedding}}, url = {http://dl.acm.org/citation.cfm?doid=2939672.2939751}, urldate = {2019-12-10}, year = 2016 }