More Web Proxy on the site http://driver.im/

research-article

High-order Proximity Preserving Information Network Hashing

Authors:

Vincent W. Zheng,

Xing XieAuthors Info & Claims

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 1744 - 1753

https://doi.org/10.1145/3219819.3220034

Published: 19 July 2018 Publication History

Abstract

Information network embedding is an effective way for efficient graph analytics. However, it still faces with computational challenges in problems such as link prediction and node recommendation, particularly with increasing scale of networks. Hashing is a promising approach for accelerating these problems by orders of magnitude. However, no prior studies have been focused on seeking binary codes for information networks to preserve high-order proximity. Since matrix factorization (MF) unifies and outperforms several well-known embedding methods with high-order proximity preserved, we propose a MF-based \underlineI nformation \underlineN etwork \underlineH ashing (INH-MF) algorithm, to learn binary codes which can preserve high-order proximity. We also suggest Hamming subspace learning, which only updates partial binary codes each time, to scale up INH-MF. We finally evaluate INH-MF on four real-world information network datasets with respect to the tasks of node classification and node recommendation. The results demonstrate that INH-MF can perform significantly better than competing learning to hash baselines in both tasks, and surprisingly outperforms network embedding methods, including DeepWalk, LINE and NetMF, in the task of node recommendation. The source code of INH-MF is available online\footnote\urlhttps://github.com/DefuLian/network .

Supplementary Material

MP4 File (lian_proximity_information.mp4)

Download
337.07 MB

References

[1]

Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola . 2013. Distributed large-scale natural graph factorization Proceedings of WWW'13. ACM, 37--48.

Digital Library

[2]

Lars Backstrom and Jure Leskovec . 2011. Supervised random walks: predicting and recommending links in social networks. In Proceedings of WSDM'11. ACM, 635--644.

Digital Library

[3]

Avrim Blum, John Hopcroft, and Ravindran Kannan . 2016. Foundations of data science. Vorabversion eines Lehrbuchs (2016).

[4]

Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang . 2017. A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications. arXiv preprint arXiv:1709.07604 (2017).

[5]

Jie Cao, Zhiang Wu, Youquan Wang, and Yi Zhuang . 2013 a. Hybrid collaborative filtering algorithm for bidirectional web service recommendation. Knowledge and information systems Vol. 36, 3 (2013), 607--627.

Digital Library

[6]

Jie Cao, Zhiang Wu, Junjie Wu, and Hui Xiong . 2013 b. SAIL: Summation-based incremental learning for information-theoretic text clustering. IEEE Transactions on Cybernetics Vol. 43, 2 (2013), 570--584.

[7]

Shaosheng Cao, Wei Lu, and Qiongkai Xu . 2015. Grarep: Learning graph representations with global structural information Proceedings of CIKM'15. ACM, 891--900.

Digital Library

[8]

Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu . 2017. A Survey on Network Embedding. arXiv preprint arXiv:1711.08752 (2017).

[9]

Hanjun Dai, Bo Dai, and Le Song . 2016. Discriminative embeddings of latent variable models for structured data Proceedings of ICML'16. 2702--2711.

Digital Library

[10]

Lars Eldén and Haesun Park . 1999. A Procrustes problem on the Stiefel manifold. Numer. Math. Vol. 82, 4 (1999), 599--619.

[11]

Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin . 2013. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. IEEE Trans. Pattern Anal. Mach. Intell. Vol. 35, 12 (2013).

Digital Library

[12]

Aditya Grover and Jure Leskovec . 2016. node2vec: Scalable feature learning for networks. In Proceedings of KDD'16. ACM, 855--864.

Digital Library

[13]

Will Hamilton, Zhitao Ying, and Jure Leskovec . 2017. Inductive representation learning on large graphs. In Proceedings of NIPS'17. 1025--1035.

[14]

Johan Håstad . 2001. Some optimal inapproximability results. Journal of the ACM (JACM) Vol. 48, 4 (2001), 798--859.

Digital Library

[15]

Roger A Horn and Charles R Johnson . 1990. Matrix analysis. Cambridge press.

Digital Library

[16]

Y. Hu, Y. Koren, and C. Volinsky . 2008. Collaborative filtering for implicit feedback datasets Proceedings of ICDM'08. IEEE, 263--272.

Digital Library

[17]

Qing-Yuan Jiang and Wu-Jun Li . 2015. Scalable Graph Hashing with Feature Transformation. Proceedings of IJCAI'15. 2248--2254.

Digital Library

[18]

Thomas N Kipf and Max Welling . 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).

[19]

Weihao Kong and Wu-Jun Li . 2012. Isotropic hashing. In Proceedings of NIPS'12. 1646--1654.

Digital Library

[20]

Xuelong Li, Di Hu, and Feiping Nie . 2017. Large Graph Hashing with Spectral Rotation. In Proceedings of AAAI'17. 2203--2209.

[21]

Defu Lian, Rui Liu, Yong Ge, Kai Zheng, Xing Xie, and Longbing Cao . 2017. Discrete Content-aware Matrix Factorization. In Proceedings of KDD'17. 325--334.

Digital Library

[22]

Wei Liu, Cun Mu, Sanjiv Kumar, and Shih-Fu Chang . 2014. Discrete graph hashing. In Proceedings of NIPS'14. 3419--3427.

Digital Library

[23]

Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang . 2011. Hashing with graphs. In Proceedings of ICML'11. 1--8.

Digital Library

[24]

Chao Ma, Ivor W Tsang, Furong Peng, and Chuancai Liu . 2017. Partial hash update via hamming subspace learning. IEEE Transactions on Image Processing Vol. 26, 4 (2017), 1939--1951.

Digital Library

[25]

Mohammad Norouzi, Ali Punjani, and David J Fleet . 2012. Fast search in hamming space with multi-index hashing Proceedings of CVPR'12. IEEE, 3108--3115.

Digital Library

[26]

Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu . 2016. Asymmetric transitivity preserving graph embedding Proceedings of KDD'16. ACM, 1105--1114.

Digital Library

[27]

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena . 2014. Deepwalk: Online learning of social representations Proceedings of KDD'14. ACM, 701--710.

Digital Library

[28]

Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang . 2018. Network Embedding as Matrix Factorization: UnifyingDeepWalk, LINE, PTE, and node2vec. In Proceedings of WSDM'18. ACM.

Digital Library

[29]

Ruslan Salakhutdinov and Geoffrey Hinton . 2009. Semantic hashing. International Journal of Approximate Reasoning Vol. 50, 7 (2009), 969--978.

Digital Library

[30]

Fumin Shen, Chunhua Shen, Wei Liu, and Heng Tao Shen . 2015. Supervised discrete hashing. In Proceedings of CVPR'15. 37--45.

[31]

Fumin Shen, Chunhua Shen, Qinfeng Shi, Anton Van Den Hengel, and Zhenmin Tang . 2013. Inductive hashing on manifolds. In Proceedings of CVPR'13. IEEE, 1562--1569.

Digital Library

[32]

Xiaoshuang Shi, Fuyong Xing, Kaidi Xu, Manish Sapkota, and Lin Yang . 2017. Asymmetric Discrete Graph Hashing. In Proceedings of AAAI'17. 2541--2547.

[33]

N. Srebro and T. Jaakkola . 2003. Weighted low-rank approximations. In Proceedings of ICML'03. 720--727.

Digital Library

[34]

Mingkui Tan, Ivor W. Tsang, and Li Wang . 2014. Towards Ultrahigh Dimensional Feature Selection for Big Data. Journal of Machine Learning Research Vol. 15 (2014).

Digital Library

[35]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei . 2015. Line: Large-scale information network embedding. In Proceedings of WWW'15. 1067--1077.

Digital Library

[36]

Lei Tang and Huan Liu . 2009. Relational learning via latent social dimensions. In Proceedings of KDD'09. ACM, 817--826.

Digital Library

[37]

Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et almbox. . 2017. A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell. (2017).

[38]

Yair Weiss, Antonio Torralba, and Rob Fergus . 2009. Spectral hashing. In Proceedings of NIPS'09. 1753--1760.

Digital Library

[39]

Hanwang Zhang, Fumin Shen, Wei Liu, Xiangnan He, Huanbo Luan, and Tat-Seng Chua . 2016. Discrete collaborative filtering. In Proceedings of SIGIR'16. ACM, 325--334.

Digital Library

[40]

Yan Zhang, Defu Lian, and Guowu Yang . 2017. Discrete Personalized Ranking for Fast Collaborative Filtering from Implicit Feedback. In Proceedings of AAAI'17. 1669--1675.

Cited By

Wu WLi BLuo CNejdl WTan X(2024)MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network EmbeddingIEEE Transactions on Cybernetics10.1109/TCYB.2023.324376354:5(2941-2954)Online publication date: May-2024
https://doi.org/10.1109/TCYB.2023.3243763
He TGao LSong JLi Y(2023)Semisupervised Network Embedding With Differentiable Deep QuantizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.312928034:8(4791-4802)Online publication date: Aug-2023
https://doi.org/10.1109/TNNLS.2021.3129280
Yang DQu BHussein RRosso PCudré-Mauroux PLiu J(2023)Revisiting Embedding Based Graph Analyses: Hyperparameters Matter!IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323074335:11(11830-11845)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2022.3230743
Show More Cited By

Index Terms

High-order Proximity Preserving Information Network Hashing
1. Information systems
  1. Information systems applications
    1. Data mining
  2. World Wide Web
    1. Web applications

Recommendations

Order preserving hashing for approximate nearest neighbor search
MM '13: Proceedings of the 21st ACM international conference on Multimedia

In this paper, we propose a novel method to learn similarity-preserving hash functions for approximate nearest neighbor (NN) search. The key idea is to learn hash functions by maximizing the alignment between the similarity orders computed from the ...
Preference preserving hashing for efficient recommendation
SIGIR '14: Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval

Recommender systems usually need to compare a large number of items before users' most preferred ones can be found This process can be very costly if recommendations are frequently made on large scale datasets. In this paper, a novel hashing algorithm, ...
Arbitrary-Order Proximity Preserved Network Embedding
KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2018

2925 pages

ISBN:9781450355520

DOI:10.1145/3219819

General Chairs:
Yike Guo
Imperial College London
,
Faisal Farooq
IBM

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

KDD '18

Sponsor:

KDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 19 - 23, 2018

London, United Kingdom

Acceptance Rates

KDD '18 Paper Acceptance Rate 107 of 983 submissions, 11%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
1,168
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)8

Reflects downloads up to 09 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu WLi BLuo CNejdl WTan X(2024)MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network EmbeddingIEEE Transactions on Cybernetics10.1109/TCYB.2023.324376354:5(2941-2954)Online publication date: May-2024
https://doi.org/10.1109/TCYB.2023.3243763
He TGao LSong JLi Y(2023)Semisupervised Network Embedding With Differentiable Deep QuantizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.312928034:8(4791-4802)Online publication date: Aug-2023
https://doi.org/10.1109/TNNLS.2021.3129280
Yang DQu BHussein RRosso PCudré-Mauroux PLiu J(2023)Revisiting Embedding Based Graph Analyses: Hyperparameters Matter!IEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323074335:11(11830-11845)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TKDE.2022.3230743
He TGao LSong JLi Y(2023)Transferable and Differentiable Discrete Network Embedding for multi-domains with Hierarchical Knowledge DistillationInformation Sciences10.1016/j.ins.2023.01.146Online publication date: Feb-2023
https://doi.org/10.1016/j.ins.2023.01.146
Sun LZhang ZWen JWang FJi PSu SYu P(2022)Aligning Dynamic Social Networks: An Optimization over Dynamic Graph AutoencoderIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3152502(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3152502
Lian DZhu ZZheng KGe YXie XChen E(2022)Network Representation Lightening from Hashing to QuantizationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3151474(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3151474
Yang DQu BYang JWang LCudre-Mauroux P(2022)Streaming Graph Embeddings via Incremental Neighborhood SketchingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3149999(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3149999
Zhang SLi JZhou WLi TZhang YWang J(2022)Higher-Order Proximity-Based MiRNA-Disease Associations PredictionIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2020.299497119:1(501-512)Online publication date: 1-Jan-2022
https://doi.org/10.1109/TCBB.2020.2994971
Fujiwaray YNakanoy MKumagai AIdaz YKimura AUeda N(2022)Fast Binary Network Hashing via Graph Clustering2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10021047(381-388)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10021047
Çelikkanat AMalliaros FPapadopoulos A(2022)NodeSig: Binary Node Embeddings via Random Walk Diffusion2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)10.1109/ASONAM55673.2022.10068621(68-75)Online publication date: 10-Nov-2022
https://doi.org/10.1109/ASONAM55673.2022.10068621
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents