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

research-article

Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach

Authors:

Ying ZhangAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 17, Issue 2

Pages 175 - 183

https://doi.org/10.14778/3626292.3626300

Published: 01 October 2023 Publication History

Abstract

Bipartite graph embedding (BGE), as the fundamental task in bipartite network analysis, is to map each node to compact low-dimensional vectors that preserve intrinsic properties. The existing solutions towards BGE fall into two groups: metric-based methods and graph neural network-based (GNN-based) methods. The latter typically generates higher-quality embeddings than the former due to the strong representation ability of deep learning. Nevertheless, none of the existing GNN-based methods can handle billion-scale bipartite graphs due to the expensive message passing or complex modelling choices. Hence, existing solutions face a challenge in achieving both embedding quality and model scalability. Motivated by this, we propose a novel graph neural network named AnchorGNN based on global-local learning framework, which can generate high-quality BGE and scale to billion-scale bipartite graphs. Concretely, AnchorGNN leverages a novel anchor-based message passing schema for global learning, which enables global knowledge to be incorporated to generate node embeddings. Meanwhile, AnchorGNN offers an efficient one-hop local structure modelling using maximum likelihood estimation for bipartite graphs with rational analysis, avoiding large adjacency matrix construction. Both global information and local structure are integrated to generate distinguishable node embeddings. Extensive experiments demonstrate that AnchorGNN outperforms the best competitor by up to 36% in accuracy and achieves up to 28 times speed-up against the only metric-based baseline on billion-scale bipartite graphs.

References

[1]

2015. LINE. https://github.com/tangjianpku/LINE.

[2]

2016. node2vec. https://github.com/eliorc/node2vec.

[3]

2018. BiNE. https://github.com/clhchtcjj/BiNE.

[4]

2020. LightGCN. https://github.com/gusye1234/LightGCN-PyTorch.

[5]

2021. BiGI. https://github.com/caojiangxia/BiGI.

[6]

2022. GEBEp. https://github.com/AnryYang/GEBEp.

[7]

2022. HCCF. https://github.com/akaxlh/HCCF.

[8]

2022. SHT. https://github.com/akaxlh/SHT.

[9]

Ioannis Antonellis, Hector Garcia-Molina, and Chi-Chao Chang. 2008. Sim-rank++: query rewriting through link analysis of the click graph. Proceedings of the VLDB Endowment 1, 1 (2008), 408--421.

Digital Library

[10]

Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer normalization. arXiv preprint arXiv:1607.06450 (2016).

[11]

Christopher M Bishop and Nasser M Nasrabadi. 2006. Pattern recognition and machine learning. Vol. 4. Springer.

Digital Library

[12]

Jiangxia Cao, Xixun Lin, Shu Guo, Luchen Liu, Tingwen Liu, and Bin Wang. 2021. Bipartite Graph Embedding via Mutual Information Maximization. In Proceedings of the ACM International Conference on Web Search and Data Mining. ACM, 635--643.

Digital Library

[13]

Chaoqi Chen, Jiongcheng Li, Zebiao Zheng, Yue Huang, Xinghao Ding, and Yizhou Yu. 2021. Dual Bipartite Graph Learning: A General Approach for Domain Adaptive Object Detection. In Proceedings of the IEEE/CVF International Conference on Computer Vision. IEEE, 2683--2692.

[14]

Lanting Fang, Kaiyu Feng, Jie Gui, Shanshan Feng, and Aiqun Hu. 2023. Anonymous Edge Representation for Inductive Anomaly Detection in Dynamic Bipartite Graph. Proceedings of the VLDB Endowment 16, 5 (2023), 1154--1167.

Digital Library

[15]

Jun Gao, Jiazun Chen, Zhao Li, and Ji Zhang. 2021. ICS-GNN: lightweight interactive community search via graph neural network. Proceedings of the VLDB Endowment 14, 6 (2021), 1006--1018.

Digital Library

[16]

Ming Gao, Leihui Chen, Xiangnan He, and Aoying Zhou. 2018. BiNE: Bipartite Network Embedding. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 715--724.

Digital Library

[17]

Xavier Glorot and Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, 249--256.

[18]

Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 855--864.

Digital Library

[19]

Qingyu Guo, Fuzhen Zhuang, Chuan Qin, Hengshu Zhu, Xing Xie, Hui Xiong, and Qing He. 2022. A Survey on Knowledge Graph-Based Recommender Systems. IEEE Transactions on Knowledge and Data Engineering 34, 8 (2022), 3549--3568.

[20]

Ruining He and Julian J. McAuley. 2016. VBPR: Visual Bayesian Personalized Ranking from Implicit Feedback. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press, 144--150.

[21]

Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang. 2020. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 639--648.

Digital Library

[22]

Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. 2017. Neural collaborative filtering. In Proceedings of the International Conference on World Wide Web. ACM, 173--182.

Digital Library

[23]

Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference on Learning Representations.

[24]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the International Conference on Learning Representations.

[25]

Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2017. Imagenet classification with deep convolutional neural networks. Commun. ACM 60, 6 (2017), 84--90.

Digital Library

[26]

Zhao Li, Xin Shen, Yuhang Jiao, Xuming Pan, Pengcheng Zou, Xianling Meng, Chengwei Yao, and Jiajun Bu. 2020. Hierarchical Bipartite Graph Neural Networks: Towards Large-Scale E-commerce Applications. In Proceedings of the IEEE International Conference on Data Engineering. IEEE, 1677--1688.

[27]

Shaowen Peng, Kazunari Sugiyama, and Tsunenori Mine. 2022. Less is More: Reweighting Important Spectral Graph Features for Recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1273--1282.

Digital Library

[28]

Susie Xi Rao, Shuai Zhang, Zhichao Han, Zitao Zhang, Wei Min, Zhiyao Chen, Yinan Shan, Yang Zhao, and Ce Zhang. 2021. xFraud: explainable fraud transaction detection. Proceedings of the VLDB Endowment 15, 3 (2021), 427--436.

Digital Library

[29]

Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. 2009. BPR: Bayesian Personalized Ranking from Implicit Feedback. In Proceedings of the Conference on Uncertainty in Artificial Intelligence. AUAI Press, 452--461.

Digital Library

[30]

Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In Proceedings of the International Conference on World Wide Web. ACM, 1067--1077.

Digital Library

[31]

Shreshth Tuli, Giuliano Casale, and Nicholas R. Jennings. 2022. TranAD: Deep Transformer Networks for Anomaly Detection in Multivariate Time Series Data. Proceedings of the VLDB Endowment 15, 6 (2022), 1201--1214.

Digital Library

[32]

Laurens Van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. Journal of machine learning research 9, 11 (2008).

[33]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. Advances in Neural Information Processing Systems 30 (2017).

[34]

Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. 2019. Neural Graph Collaborative Filtering. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 165--174.

Digital Library

[35]

Jiancan Wu, Xiang Wang, Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. 2021. Self-supervised Graph Learning for Recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 726--735.

Digital Library

[36]

Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. 2022. Graph Neural Networks in Recommender Systems: A Survey. Comput. Surveys 55, 5 (2022), 1--37.

Digital Library

[37]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems 32, 1 (2021), 4--24.

[38]

Lianghao Xia, Chao Huang, Yong Xu, Jiashu Zhao, Dawei Yin, and Jimmy X. Huang. 2022. Hypergraph Contrastive Collaborative Filtering. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 70--79.

[39]

Lianghao Xia, Chao Huang, and Chuxu Zhang. 2022. Self-Supervised Hypergraph Transformer for Recommender Systems. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2100--2109.

Digital Library

[40]

Wei Xia, Quanxue Gao, Qianqian Wang, Xinbo Gao, Chris Ding, and Dacheng Tao. 2022. Tensorized Bipartite Graph Learning for Multi-View Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 4 (2022), 5187--5202.

[41]

Xu Xie, Fei Sun, Zhaoyang Liu, Shiwen Wu, Jinyang Gao, Jiandong Zhang, Bolin Ding, and Bin Cui. 2022. Contrastive Learning for Sequential Recommendation. In Proceedings of the IEEE International Conference on Data Engineering. IEEE, 1259--1273.

[42]

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In Proceedings of the International Conference on Learning Representations.

[43]

Hong-Jian Xue, Xinyu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen. 2017. Deep Matrix Factorization Models for Recommender Systems. In Proceedings of the International Joint Conference on Artificial Intelligence. 3203--3209.

[44]

Yoshihiro Yamanishi, Masaaki Kotera, Minoru Kanehisa, and Susumu Goto. 2010. Drug-target interaction prediction from chemical, genomic and pharmacological data in an integrated framework. Bioinformatics 26, 12 (2010), 246--254.

Digital Library

[45]

Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. 2022. Scalable and Effective Bipartite Network Embedding. In Proceedings of the International Conference on Management of Data. ACM, 1977--1991.

Digital Library

[46]

Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 974--983.

Digital Library

[47]

Junliang Yu, Hongzhi Yin, Xin Xia, Tong Chen, Lizhen Cui, and Quoc Viet Hung Nguyen. 2022. Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 1294--1303.

Digital Library

[48]

Wentao Zhang, Xupeng Miao, Yingxia Shao, Jiawei Jiang, Lei Chen, Olivier Ruas, and Bin Cui. 2020. Reliable Data Distillation on Graph Convolutional Network. In Proceedings of the International Conference on Management of Data. ACM, 1399--1414.

Digital Library

Cited By

Ding LHan YLi MGu YLiu TYu S(2024)WePred: Edge Weight-Guided Contrastive Learning for Bipartite Link PredictionElectronics10.3390/electronics1401002014:1(20)Online publication date: 25-Dec-2024
https://doi.org/10.3390/electronics14010020
Wang HYang RXiao XBaeza-Yates RBonchi F(2024)Effective Edge-wise Representation Learning in Edge-Attributed Bipartite GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671805(3081-3091)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671805
Wang HWang KZhang WZhang Y(2024)Bipartite Graph Analytics: Current Techniques and Future Trends2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00405(01-07)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00405
Show More Cited By

Index Terms

Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Neural networks
2. Information systems
  1. Information systems applications

Index terms have been assigned to the content through auto-classification.

Recommendations

Induced Turán problem in bipartite graphs
Abstract
The classical extremal function for a graph H, ex ( K n , H ) is the largest number of edges in a subgraph of K n that contains no subgraph isomorphic to H. Note that defining ex ( K n , H − ind ) by forbidding induced subgraphs isomorphic to H ...
Dominating induced matching in some subclasses of bipartite graphs
Abstract
A subset M ⊆ E of edges of a graph G = ( V , E ) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = ( V , E ) is ...
Forbidden induced bipartite graphs

Given a fixed bipartite graph H, we study the asymptotic speed of growth of the number of bipartite graphs on n vertices which do not contain an induced copy of H. Whenever H contains either a cycle or the bipartite complement of a cycle, the speed of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 17, Issue 2

October 2023

185 pages

ISSN:2150-8097

Editors:
Meihui Zhang
Beijing Institute of Technology
,
Cyrus Shahabi
University of Southern California

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 October 2023

Published in PVLDB Volume 17, Issue 2

Check for updates

Badges

Artifacts Available / v1.1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
152
Total Downloads

Downloads (Last 12 months)147
Downloads (Last 6 weeks)12

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ding LHan YLi MGu YLiu TYu S(2024)WePred: Edge Weight-Guided Contrastive Learning for Bipartite Link PredictionElectronics10.3390/electronics1401002014:1(20)Online publication date: 25-Dec-2024
https://doi.org/10.3390/electronics14010020
Wang HYang RXiao XBaeza-Yates RBonchi F(2024)Effective Edge-wise Representation Learning in Edge-Attributed Bipartite GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671805(3081-3091)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671805
Wang HWang KZhang WZhang Y(2024)Bipartite Graph Analytics: Current Techniques and Future Trends2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00405(01-07)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00405
Xu YZhang WZhang YOrlowska MLin X(2024)TimeSGN: Scalable and Effective Temporal Graph Neural Network2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00255(3297-3310)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00255
Sun HLi XWu ZSu DLi RWang G(2024)Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00188(2379-2392)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00188
Jiang YYu JXu ZChen CChow YZhang Y(2024)SBGMN: A Multi-view Sign Prediction Network for Bipartite GraphsWeb and Big Data10.1007/978-981-97-7238-4_6(81-96)Online publication date: 31-Aug-2024
https://dl.acm.org/doi/10.1007/978-981-97-7238-4_6

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents