Mạng nơ-ron đồ thị dựa trên độ phân cực cho dự đoán dấu trong đồ thị lưỡng phân có dấu

Springer Science and Business Media LLC - Tập 25 - Trang 471-487 - 2022
Xianhang Zhang1, Hanchen Wang2,1, Jianke Yu2, Chen Chen2, Xiaoyang Wang2, Wenjie Zhang1
1University of New South Wales, Sydney, Australia
2Zhejiang Gongshang University, Hangzhou, China

Tóm tắt

Dưới dạng cấu trúc dữ liệu cơ bản, đồ thị xuất hiện phổ biến trong nhiều ứng dụng khác nhau. Trong số tất cả các loại đồ thị, đồ thị lưỡng phân có dấu chứa các cấu trúc phức tạp với các liên kết tích cực và tiêu cực cũng như các thiết lập lưỡng phân, trên đó các thuật toán phân tích đồ thị thông thường không còn khả thi. Các công trình trước đây chủ yếu tập trung vào đồ thị có dấu đơn phần hoặc đồ thị lưỡng phân không có dấu một cách riêng biệt. Nhiều mô hình được đề xuất cho các ứng dụng trên đồ thị lưỡng phân có dấu bằng cách tận dụng thông tin cấu trúc trực giác. Tuy nhiên, các phương pháp này có khả năng hạn chế trong việc nắm bắt toàn bộ thông tin ẩn chứa trong những đồ thị này. Trong bài báo này, chúng tôi đề xuất mạng nơ-ron đồ thị đầu tiên trên đồ thị lưỡng phân có dấu, có tên là Mạng Chập Đồ Thị Dựa Trên Độ Phân Cực (PbGCN), cho nhiệm vụ dự đoán dấu với sự trợ giúp của lý thuyết cân bằng. Chúng tôi giới thiệu thuộc tính độ phân cực mới cho đồ thị lưỡng phân có dấu, dựa trên đó chúng tôi xây dựng các đồ thị chiếu một chế độ để cho phép các GNNs tổng hợp thông tin giữa các nút cùng loại. Các thử nghiệm rộng rãi trên năm tập dữ liệu chứng minh hiệu quả của các kỹ thuật mà chúng tôi đề xuất.

Từ khóa

#đồ thị lưỡng phân có dấu #mạng nơ-ron đồ thị #dự đoán dấu #lý thuyết cân bằng #đồ thị chiếu một chế độ

Tài liệu tham khảo

Akoglu, L.: Quantifying political polarity based on bipartite opinion networks. In: Proceedings of the International AAAI Conference on Web and Social Media (2014) Aksoy, S.G., Kolda, T.G., Pinar, A.: Measuring and modeling bipartite graphs with community structure. Journal of Complex Networks 5(4), 581–603 (2017) Banerjee, S., Sarkar, K., Gokalp, S., Sen, A., Davulcu, H.: Partitioning signed bipartite graphs for classification of individuals and organizations. In: SBP, pp. 196–204. Springer (2012) Chen, C., Wu, Y., Sun, R., Wang, X.: Maximum signed \(\theta\)-clique identification in large signed graphs. TKDE (2021) Chen, C., Zhu, Q., Wu, Y., Sun, R., Wang, X., Liu, X.: Efficient critical relationships identification in bipartite networks. World Wide Web (2021) Derr, T., Johnson, C., Chang, Y., Tang, J.: Balance in signed bipartite networks. In: CIKM, pp. 1221–1230. ACM (2019) Derr, T., Ma, Y., Tang, J.: Signed graph convolutional networks. In: ICDM, pp. 929–934. IEEE (2018) Derr, T., Tang, J.: Congressional vote analysis using signed networks. In: ICDM workshop, pp. 1501–1502. IEEE (2018) Gao, J., Lyu, T., Xiong, F., Wang, J., Ke, W., Li, Z.: Mgnn: A multimodal graph neural network for predicting the survival of cancer patients. In: SIGIR, pp. 1697–1700 (2020) Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: SIGKDD, pp. 855–864 (2016) Gu, K., Fan, Y., Zeng, A., Zhou, J., Di, Z.: Analysis on large-scale rating systems based on the signed network. Physica A: Statistical Mechanics and its Applications 507, 99–109 (2018) Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: NIPS, pp. 1024–1034 (2017) Hu, J., Zheng, W.X.: Bipartite consensus for multi-agent systems on directed signed networks. In: 52nd IEEE Conference on Decision and Control, pp. 3451–3456. IEEE (2013) Javari, A., Derr, T., Esmailian, P., Tang, J., Chang, K.C.C.: Rose: Role-based signed network embedding. In: WWW, pp. 2782–2788 (2020) Kim, J., Park, H., Lee, J.E., Kang, U.: Side: representation learning in signed directed networks. In: WWW, pp. 509–518 (2018) Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: ICLR 2017 (2017) Lee, Y.C., Son, J., Kim, T., Park, D., Kim, S.W.: Exploiting uninteresting items for effective graph-based one-class collaborative filtering. The Journal of Supercomputing, 1–20 (2021) Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: WWW, pp. 641–650 (2010) Li, C., Jia, K., Shen, D., Shi, C.J.R., Yang, H.: Hierarchical representation learning for bipartite graphs. In: IJCAI, pp. 2873–2879 (2019) Li, Y., Tian, Y., Zhang, J., Chang, Y.: Learning signed network embedding via graph attention. In: AAAI, pp. 4772–4779 (2020) Li, Z., Shen, X., Jiao, Y., Pan, X., Zou, P., Meng, X., Yao, C., Bu, J.: Hierarchical bipartite graph neural networks: Towards large-scale e-commerce applications. In: ICDE, pp. 1677–1688. IEEE (2020) Papaoikonomou, A., Kardara, M., Tserpes, K., Varvarigou, D.: Edge sign prediction in social networks via frequent subgraph discovery. IEEE Internet Computing 18(5), 36–43 (2014) Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: SIGKDD, pp. 701–710 (2014) Shams, B., Haratizadeh, S.: Sibrank: Signed bipartite network analysis for neighbor-based collaborative ranking. Physica A: Statistical Mechanics and its Applications 458, 364–377 (2016) Sun, R., Chen, C., Wang, X., Zhang, Y., Wang, X.: Stable community detection in signed social networks. TKDE (2020) Sun, R., Zhu, Q., Chen, C., Wang, X., Zhang, Y., Wang, X.: Discovering cliques in signed networks based on balance theory. In: DASFAA, pp. 666–674 (2020) Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv:1710.10903 (2017) Wang, H., Lian, D., Liu, W., Wen, D., Chen, C., Wang, X.: Powerful graph of graphs neural network for structured entity analysis. World Wide Web, 1–21 (2021) Wang, H., Lian, D., Zhang, Y., Qin, L., He, X., Lin, Y., Lin, X.: Binarized graph neural network. World Wide Web 24(3), 825–848 (2021) Wang, H., Lian, D., Zhang, Y., Qin, L., Lin, X.: Gognn: Graph of graphs neural network for predicting structured entity interactions. arXiv:2005.05537 (2020) Wang, K., Lin, X., Qin, L., Zhang, W., Zhang, Y.: Vertex priority based butterfly counting for large-scale bipartite networks. PVLDB (2019) Wang, X., Zhang, Y., Zhang, W., Lin, X.: Efficient distance-aware influence maximization in geo-social networks. TKDE 29(3), 599–612 (2017) Wang, X., Zhang, Y., Zhang, W., Lin, X., Chen, C.: Bring order into the samples: A novel scalable method for influence maximization. TKDE 29(2), 243–256 (2017) Wang, Z., Zhou, M., Arnold, C.: Toward heterogeneous information fusion: bipartite graph convolutional networks for in silico drug repurposing. Bioinformatics 36(Supplement_1), i525–i533 (2020) Yang, F., Fan, K., Song, D., Lin, H.: Graph-based prediction of protein-protein interactions with attributed signed graph embedding. BMC bioinformatics 21(1), 1–16 (2020) Yang, P., Wang, H., Zhang, Y., Qin, L., Zhang, W., Lin, X.: T3s: Effective representation learning for trajectory similarity computation. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 2183–2188. IEEE (2021) Zhang, T., Jiang, H., Bao, Z., Zhang, Y.: Characterization and edge sign prediction in signed networks. Journal of Industrial and Intelligent Information 1(1), 19–24 (2013) Zhou, T., Ren, J., Medo, M., Zhang, Y.C.: Bipartite network projection and personal recommendation. Physical Review E 76(4), 046115 (2007)