Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs
Pages 3081 - 3091
Abstract
Graph representation learning (GRL) is to encode graph elements into informative vector representations, which can be used in downstream tasks for analyzing graph-structured data and has seen extensive applications in various domains. However, the majority of extant studies on GRL are geared towards generating node representations, which cannot be readily employed to perform edge-based analytics tasks in edge-attributed bipartite graphs (EABGs) that pervade the real world, e.g., spam review detection in customer-product reviews and identifying fraudulent transactions in user-merchant networks. Compared to node-wise GRL, learning edge representations (ERL) on such graphs is challenging due to the need to incorporate the structure and attribute semantics from the perspective of edges while considering the separate influence of two heterogeneous node sets U and V in bipartite graphs. To our knowledge, despite its importance, limited research has been devoted to this frontier, and existing workarounds all suffer from sub-par results.
Motivated by this, this paper designs EAGLE, an effective ERL method for EABGs. Building on an in-depth and rigorous theoretical analysis, we propose the factorized feature propagation (FFP) scheme for edge representations with adequate incorporation of long-range dependencies of edges/features without incurring tremendous computation overheads. We further ameliorate FFP as a dual-view FFP by taking into account the influences from nodes in U and V severally in ERL. Extensive experiments on 5 real datasets showcase the effectiveness of the proposed EAGLE models in semi-supervised edge classification tasks. In particular, EAGLE can attain a considerable gain of at most 38.11% in AP and 1.86% in AUC when compared to the best baselines.
Supplemental Material
MP4 File - Promo Video
Promo Video of Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs
- Download
- 146.52 MB
References
[1]
2023. SketchNE: Embedding Billion-Scale Networks Accurately in One Hour. IEEE Transactions on Knowledge and Data Engineering 35, 10 (oct 2023), 10666--10680. https://doi.org/10.1109/TKDE.2023.3250703
[2]
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V Chawla. 2022. Attre2vec: Unsupervised attributed edge representation learning. Information Sciences 592 (2022), 82--96.
[3]
Shaked Brody, Uri Alon, and Eran Yahav. 2022. How Attentive are Graph Attention Networks?. In ICLR. arXiv:2105.14491
[4]
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 14th ACM International Conference on Web Search and Data Mining (WSDM '21). Association for Computing Machinery, New York, NY, USA, 635--643. https://doi.org/10.1145/3437963.3441783
[5]
Rizal Fathony, Jenn Ng, and Jia Chen. 2023. Interaction-Focused Anomaly Detection on Bipartite Node-and-Edge-Attributed Graphs. In 2023 International Joint Conference on Neural Networks (IJCNN). IEEE, 1--10.
[6]
Zheng Gao, Gang Fu, Chunping Ouyang, Satoshi Tsutsui, Xiaozhong Liu, Jeremy Yang, Christopher Gessner, Brian Foote, David Wild, Ying Ding, et al. 2019. edge2vec: Representation learning using edge semantics for biomedical knowledge discovery. BMC bioinformatics 20, 1 (2019), 1--15.
[7]
Mathieu Garchery and Michael Granitzer. 2020. Adsage: Anomaly detection in sequences of attributed graph edges applied to insider threat detection at fine-grained level. arXiv preprint arXiv:2007.06985 (2020).
[8]
Edward Giamphy, Jean-Loup Guillaume, Antoine Doucet, and Kevin Sanchis. 2023. A survey on bipartite graphs embedding. Social Network Analysis and Mining 13, 1 (2023), 54. https://doi.org/10.1007/s13278-023-01058-z
[9]
Gene H Gloub and Charles F Van Loan. 1996. Matrix computations. Johns Hopkins Universtiy Press, 3rd edtion (1996).
[10]
Liyu Gong and Qiang Cheng. 2019. Exploiting edge features for graph neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 9211--9219.
[11]
Aditya Grover and Jure Leskovec. 2016. Node2vec: Scalable feature learning for networks. KDD 13--17-Augu (2016), 855--864. arXiv:1607.00653
[12]
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review 53, 2 (2011), 217--288.
[13]
William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS, Vol. 2017-Decem. 1025--1035. arXiv:1706.02216
[14]
William L Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation learning on graphs: Methods and applications. arXiv preprint arXiv:1709.05584 (2017).
[15]
Chaoyang He, Tian Xie, Yu Rong, Wenbing Huang, Junzhou Huang, Xiang Ren, Cyrus Shahabi, and Xi-Ang Ren. 2020. Cascade-BGNN: Toward Efficient Self-supervised Representation Learning on Large-scale Bipartite Graphs. Technical Report. https://doi.org/10.1145/1122445.1122456 arXiv:1906.11994v3
[16]
Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press.
[17]
Keke Huang, Jing Tang, Juncheng Liu, Renchi Yang, and Xiaokui Xiao. 2023. Node-wise diffusion for scalable graph learning. In Proceedings of the ACM Web Conference 2023. 1723--1733.
[18]
Wentao Huang, Yuchen Li, Yuan Fang, Ju Fan, and Hongxia Yang. 2020. BiANE: Bipartite Attributed Network Embedding. SIGIR 2020 - Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval 10, 20 (2020), 149--158. https://doi.org/10.1145/3397271.3401068
[19]
Jaehyeong Jo, Jinheon Baek, Seul Lee, Dongki Kim, Minki Kang, and Sung Ju Hwang. 2021. Edge representation learning with hypergraphs. Advances in Neural Information Processing Systems 34 (2021), 7534--7546.
[20]
Diederik P. Kingma and Jimmy Lei Ba. 2015. Adam: A method for stochastic optimization. In arXiv Prepr. arXiv1412.6980. arXiv. arXiv:1412.6980
[21]
Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. ICLR 2017 (sep 2017).
[22]
David A Levin and Yuval Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Soc.
[23]
Jiacheng Li, Jingbo Shang, and Julian McAuley. 2022. UCTopic: Unsupervised Contrastive Learning for Phrase Representations and Topic Mining. Proceedings of the Annual Meeting of the Association for Computational Linguistics 1 (2022), 6159--6169. https://doi.org/10.18653/v1/2022.acl-long.426 arXiv:2202.13469
[24]
Suxue Li, Haixia Zhang, Dalei Wu, Chuanting Zhang, and Dongfeng Yuan. 2018. Edge representation learning for community detection in large scale information networks. In Mobility Analytics for Spatio-Temporal and Social Data: First International Workshop, MATES 2017, Munich, Germany, September 1, 2017, Revised Selected Papers 1. Springer, 54--72.
[25]
Yiming Li, Siyue Xie, Xiaxin Liu, Qiu Fang Ying, Wing Cheong Lau, Dah Ming Chiu, Shou Zhi Chen, et al. 2021. Temporal graph representation learning for detecting anomalies in e-payment systems. In 2021 International Conference on Data Mining Workshops (ICDMW). IEEE, 983--990.
[26]
Yirui Liu, Xinghao Qiao, Liying Wang, and Jessica Lam. 2023. EEGNN: Edge Enhanced Graph Neural Network with a Bayesian Nonparametric Graph Model. In International Conference on Artificial Intelligence and Statistics. PMLR, 2132--2146.
[27]
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. 2021. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1202--1211.
[28]
Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized algorithms. Cambridge university press.
[29]
Jianmo Ni, Jiacheng Li, and Julian McAuley. 2019. Justifying recommendations using distantly-labeled reviews and fine-grained aspects. EMNLP-IJCNLP 2019 - 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing, Proceedings of the Conference (2019), 188--197. https://doi.org/10.18653/v1/d19--1018
[30]
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. 2016. Asymmetric transitivity preserving graph embedding. KDD 13--17-Augu (2016), 1105--1114.
[31]
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: Online learning of social representations. SIGKDD (2014), 701--710. arXiv:1403.6652
[32]
Nils Reimers and Iryna Gurevych. 2020. Sentence-BERT: Sentence embeddings using siamese BERT-networks. EMNLP-IJCNLP 2019 - 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing, Proceedings of the Conference (2020), 3982--3992. https://doi.org/10.18653/v1/d19--1410 arXiv:1908.10084
[33]
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-june Paul Hsu, and Kuansan Wang. 2015. An overview of microsoft academic service (mas) and applications. In WWW. ACM, 243--246.
[34]
Gilbert Strang. 2022. Introduction to linear algebra. SIAM.
[35]
Guolei Sun and Xiangliang Zhang. 2019. A novel framework for node/edge attributed graph embedding. In Advances in Knowledge Discovery and Data Mining: 23rd Pacific-Asia Conference, PAKDD 2019, Macau, China, April 14--17, 2019, Proceedings, Part III 23. Springer, 169--182.
[36]
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale information network embedding. WWW 2015 (2015), 1067--1077. arXiv:1503.03578
[37]
Jie Tang, Duo Zhang, and Limin Yao. 2007. Social Network Extraction of Academic Researchers. In ICDM'07. 292--301.
[38]
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. ArnetMiner: Extraction and mining of academic social networks. SIGKDD (2008), 990--998.
[39]
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2017. Graph Attention Networks. In ICLR 2018.
[40]
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2018. Deep Graph Infomax. In ICLR.
[41]
Andrew Z Wang, Rex Ying, Pan Li, Nikhil Rao, Karthik Subbian, and Jure Leskovec. 2021. Bipartite dynamic representations for abuse detection. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 3638--3648.
[42]
Hewen Wang, Renchi Yang, Keke Huang, and Xiaokui Xiao. 2023. Efficient and Effective Edge-wise Graph Representation Learning. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2326--2336.
[43]
Hewen Wang, Renchi Yang, and Jieming Shi. 2023. Anomaly Detection in Financial Transactions Via Graph-Based Feature Aggregations. In Big Data Analytics and Knowledge Discovery: 25th International Conference, DaWaK 2023, Penang, Malaysia, August 28--30, 2023, Proceedings. Springer-Verlag, Berlin, Heidelberg, 64--79. https://doi.org/10.1007/978--3-031--39831--5_6
[44]
Jianian Wang, Sheng Zhang, Yanghua Xiao, and Rui Song. 2022. A Review on Graph Neural Network Methods in Financial Applications. Journal of Data Science 20, 2 (2022), 111--134.
[45]
Ziming Wang, Jun Chen, and Haopeng Chen. 2021. EGAT: Edge-featured graph attention network. In Artificial Neural Networks and Machine Learning--ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14--17, 2021, Proceedings, Part I 30. Springer, 253--264.
[46]
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. 2019. Simplifying graph convolutional networks. In arXiv.
[47]
Xueyi Wu, Yuanyuan Xu, Wenjie Zhang, and Ying Zhang. 2023. Billion-Scale Bipartite Graph Embedding: A Global-Local Induced Approach. Proc. VLDB Endow. 17, 2 (2023), 175--183. https://doi.org/10.14778/3626292.3626300
[48]
Yulin Wu, Xiangting Hou, Wen Jun Tan, Zengxiang Li, and Wentong Cai. 2017. Efficient parallel simulation over social contact network with skewed degree distribution. In Proceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation. 65--75.
[49]
Zhanghao Wu, Paras Jain, Matthew Wright, Azalia Mirhoseini, Joseph E Gonzalez, and Ion Stoica. 2021. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems 34 (2021), 13266--13279.
[50]
Hansheng Xue, Luwei Yang, Vaibhav Rajan, Wen Jiang, Yi Wei, and Yu Lin. 2021. Multiplex Bipartite Network Embedding Using Dual Hypergraph Convolutional Networks. In Proceedings of the Web Conference 2021 (WWW '21). Association for Computing Machinery, New York, NY, USA, 1649--1660. https://doi.org/10.1145/3442381.3449954
[51]
An Yan, Zhankui He, Jiacheng Li, Tianyang Zhang, and Julian McAuley. 2023. Personalized Showcases: Generating Multi-Modal Explanations for Recommendations. SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval 5, 23 (2023), 2251--2255. https://doi.org/10.1145/3539618.3592036 arXiv:2207.00422
[52]
Hongqiang Yan, Yan Jiang, and Guannan Liu. 2018. Telecomm fraud detection via attributed bipartite network. In 2018 15th International Conference on Service Systems and Service Management (ICSSSM). IEEE, 1--6.
[53]
Liang Yang, Chuan Wang, Junhua Gu, Xiaochun Cao, and Bingxin Niu. 2021. Why do attributes propagate in graph convolutional neural networks?. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 4590--4598.
[54]
Renchi Yang. 2022. Efficient and Effective Similarity Search over Bipartite Graphs. In Proceedings of the ACM Web Conference 2022. 308--318.
[55]
Renchi Yang and Jieming Shi. 2024. Efficient High-Quality Clustering for Large Bipartite Graphs. Proceedings of the ACM on Management of Data 2, 1 (2024), 1--27.
[56]
Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. 2022. Scalable and Effective Bipartite Network Embedding. In Proceedings of the 2022 International Conference on Management of Data. 1977--1991.
[57]
Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, and Sourav S. Bhowmick. 2020. Homogeneous network embedding for massive graphs via reweighted personalized pagerank. VLDB 13, 5 (2020), 670--683. arXiv:1906.06826
[58]
Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Juncheng Liu, and Sourav S. Bhowmick. 2020. Scaling attributed network embedding to massive graphs. VLDB 14, 1 (2020), 37--49. arXiv:2009.00826
[59]
Renchi Yang, Jieming Shi, Yin Yang, Keke Huang, Shiqi Zhang, and Xiaokui Xiao. 2021. Effective and scalable clustering on massive attributed graphs. In Proceedings of the Web Conference 2021. 3675--3687.
[60]
Wei Yu, Wenkai Wang, Guangquan Xu, Huaming Wu, Hongyan Li, Jun Wang, Xiaoming Li, and Juan Liu. 2023. MRFS: Mining Rating Fraud Subgraph in Bipartite Graph for Users and Products. IEEE Transactions on Computational Social Systems (2023).
[61]
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. 2019. Prone: Fast and scalable network representation learning. In IJCAI. 4278--4284.
[62]
Yao Zhang, Yun Xiong, Xiangnan Kong, and Yangyong Zhu. 2017. Learning node embeddings in interaction graphs. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 397--406.
[63]
Ziwei Zhang, Jian Pei, Peng Cui, Xuanrong Yao, Xiao Wang, and Wenwu Zhu. 2018. Arbitrary-order proximity preserved network embedding. KDD (2018), 2778--2786.
[64]
Tao Zhou, Jie Ren, Matú? Medo, and Yi-Cheng Zhang. 2007. Bipartite network projection and personal recommendation. Physical review E 76, 4 (2007), 046115.
[65]
Yuchen Zhou, Hongtao Huo, Zhiwen Hou, Lingbin Bu, Jingyi Mao, Yifan Wang, Xiaojun Lv, and Fanliang Bu. 2023. Co-embedding of edges and nodes with deep graph convolutional neural networks. Scientific Reports 13, 1 (2023), 16966.
[66]
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. 2021. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021. 1215--1226.
Index Terms
- Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs
Index terms have been assigned to the content through auto-classification.
Recommendations
Efficient and Effective Edge-wise Graph Representation Learning
KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data MiningGraph representation learning (GRL) is a powerful tool for graph analysis, which has gained massive attention from both academia and industry due to its superior performance in various real-world applications. However, the majority of existing works for ...
Interval Non-edge-Colorable Bipartite Graphs and Multigraphs
An edge-coloring of a graph G with colors 1,...,t is called an interval t-coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erdï s constructed a bipartite graph ...
On sum edge-coloring of regular, bipartite and split graphs
An edge-coloring of a graph G with natural numbers is called a sum edge-coloring if the colors of edges incident to any vertex of G are distinct and the sum of the colors of the edges of G is minimum. The edge-chromatic sum of a graph G is the sum of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
6901 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
August 25 - 29, 2024
Barcelona, Spain
Acceptance Rates
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 216Total Downloads
- Downloads (Last 12 months)216
- Downloads (Last 6 weeks)98
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in