Skip to main content

Arbitrary-order proximity preserved network embedding

Publication ,  Conference
Zhang, Z; Pei, J; Cui, P; Yao, X; Wang, X; Zhu, W
Published in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
July 19, 2018

Network embedding has received increasing research attention in recent years. The existing methods show that the high-order proximity plays a key role in capturing the underlying structure of the network. However, two fundamental problems in preserving the high-order proximity remain unsolved. First, all the existing methods can only preserve fixed-order proximities, despite that proximities of different orders are often desired for distinct networks and target applications. Second, given a certain order proximity, the existing methods cannot guarantee accuracy and efficiency simultaneously. To address these challenges, we propose AROPE (arbitrary-order proximity preserved embedding), a novel network embedding method based on SVD framework. We theoretically prove the eigen-decomposition reweighting theorem, revealing the intrinsic relationship between proximities of different orders. With this theorem, we propose a scalable eigen-decomposition solution to derive the embedding vectors and shift them between proximities of arbitrary orders. Theoretical analysis is provided to guarantee that i) our method has a low marginal cost in shifting the embedding vectors across different orders, ii) given a certain order, our method can get the global optimal solutions, and iii) the overall time complexity of our method is linear with respect to network size. Extensive experimental results on several large-scale networks demonstrate that our proposed method greatly and consistently outperforms the baselines in various tasks including network reconstruction, link prediction and node classification.

Duke Scholars

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

ISBN

9781450355520

Publication Date

July 19, 2018

Start / End Page

2778 / 2786
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Zhang, Z., Pei, J., Cui, P., Yao, X., Wang, X., & Zhu, W. (2018). Arbitrary-order proximity preserved network embedding. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 2778–2786). https://doi.org/10.1145/3219819.3219969
Zhang, Z., J. Pei, P. Cui, X. Yao, X. Wang, and W. Zhu. “Arbitrary-order proximity preserved network embedding.” In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2778–86, 2018. https://doi.org/10.1145/3219819.3219969.
Zhang Z, Pei J, Cui P, Yao X, Wang X, Zhu W. Arbitrary-order proximity preserved network embedding. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2018. p. 2778–86.
Zhang, Z., et al. “Arbitrary-order proximity preserved network embedding.” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2018, pp. 2778–86. Scopus, doi:10.1145/3219819.3219969.
Zhang Z, Pei J, Cui P, Yao X, Wang X, Zhu W. Arbitrary-order proximity preserved network embedding. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2018. p. 2778–2786.

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

ISBN

9781450355520

Publication Date

July 19, 2018

Start / End Page

2778 / 2786