Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (3): 90-101.doi: 10.11896/jsjkx.221200029

• Database & Big Data & Data Science • Previous Articles     Next Articles

Community Search Based on Disentangled Graph Neural Network in Heterogeneous Information Networks

CHEN Wei, ZHOU Lihua, WANG Yafeng, WANG Lizhen, CHEN Hongmei   

  1. School of Information Science and Engineering,Yunnan University,Kunming 650500,China
  • Received:2022-12-05 Revised:2023-05-16 Online:2024-03-15 Published:2024-03-13
  • About author:CHEN Wei,born in 1999,postgraduate.His main research interests include data mining and social network analysis.ZHOU Lihua,born in 1968,Ph.D,professor,Ph.D supervisor.Her main research interests include data mining,social network analysis,and artificial intelligence.
  • Supported by:
    National Natural Science Foundation of China(62062066,61762090,61966036,62276227), Yunnan Fundamental Research Projects (202201AS070015),Yunnan Key Laboratory of Intelligent Systems and Computing Project(202205AG070003),Blockchain and Data Security Governance Engineering Research Center Project of Yunnan Provincial Department of Education and University Key Laboratory of Internet of Things Technology and Application Project of Yunnan Province.

PDF (PC)

844

Abstract: Searching the community containing a given query node in heterogeneous information networks(HINs) has a wide range of application values,such as friend recommendation,epidemic monitoring and so on.However,most of the existing HINs community search methods impose strict requirements on the topology of the community based on the predefined subgraph pattern,ignoring the attribute similarity between nodes,which will be difficult to locate the community with weak structural relationship and high attribute similarity.And the global search mode is difficult to effectively deal with large-scale network data.To solve these problems,we design disentangled graph neural network and the local modularity based on meta path to measure the attribute similarity and structural cohesion between nodes respectively.Moreover,we use the 0/1 knapsack problem to optimize the impact of the attribute and structure on the community,define the most valuable c-size community search problem,and then propose a value maximization community search algorithm based on disentangled graph neural network to perform a three-stage search process.In the first stage,we construct candidate subgraphs according to the query in-formation and meta-path,control the search range within the local range of the query vertex to ensure the search efficiency of the whole algorithm.In the second stage,we use the disentangled graph neural network to fuse the heterogeneous information and user label information to calculate the attribute similarity between nodes.In the third stage,we design a greedy algorithm to find the c-size community with high attribute similarity and structural cohesion according to the community definition and cohesion measurement indicator.Finally,we test the performance of algorithm on real homogeneous and heterogeneous data sets,and a large number of experimental results demonstrate the effectiveness and efficiency of the proposed model.

Key words: Heterogeneous information networks, Community search, Disentangled graph neural network, Meta-paths, Local mo-dularity

CLC Number: 

  • TP301
[1]QIAO L,ZHANG Z,YUAN Y,et al.Keyword-Centric Community Search over Large Heterogeneous Information Networks[M]//Lecture Notes in Computer Science:12681 LNCS.2021:158-173.
[2]FANG Y,YANG Y,ZHANG W,et al.Effective and efficientcommunity search over large heterogeneous information networks[J].Proceedings of the VLDB Endowment,2020,13(6):854-867.
[3]ZHU J C,WANG C K.Approaches to community search under complex conditions[J].Journal of Software,2019,30(3):21.
[4]YANG Y,FANG Y,LIN X,et al.Effective and Efficient Truss Computation over Large Heterogeneous Information Networks[C]//2020 IEEE 36th International Conference on Data Engineering(ICDE).IEEE,2020:901-912.
[5]GAO J,CHEN J,LI Z,et al.ICS-GNN:Lightweight Interactive Community Search via Graph Neural Network[J].Proceedings of the VLDB Endowment,2021,14(6):1006-1018.
[6]CLAUSET A.Finding local community structure in networks[J].Physical Review E,2005,72(2):026132.
[7]FANG Y,WANG K,LIN X,et al.Cohesive Subgraph Searchover Big Heterogeneous Information Networks:Applications,Challenges,and Solutions[C]//Proceedings of the 2021 International Conference on Management of Data.New York,NY,USA:ACM,2021:2829-2838.
[8]MA J,CUI P,KUANG K,et al.Disentangled graph convolutional networks[C]//36th International Conference on Machine Learning.ICML,2019:7454-7463.
[9]ZHOU L H,WANG J L,WANG L Z,et al.Heterogeneous Information Network Representation Learning:A Survey[J].Chinese Journal of Computers,2022,45(1):160-189.
[10]LIU B,ZHANG F,ZHANG W,et al.Efficient CommunitySearch with Size Constraint[C]//2021 IEEE 37th International Conference on Data Engineering(ICDE).IEEE,2021:97-108.
[11]HE Y Z,WANG X Z,LI W B,et al.Research on Genetic Algorithms for the Discounted {0-1} Knapsack Problem[J].Chinese Journal of Computers,2022,39(12):2614-2630.
[12]REN Y,LIU B,HUANG C,et al.Heterogeneous Deep GraphInfomax[C]//8th International Conference on Learning Representations.New Orleans:ICLR,2020.
[13]SHI C,WANG R J,WANG X.A Survey of Heterogeneous Information Networks Analysis and Applications[J].Journal of Software,2022,33(2):598-621.
[14]VELIČKOVIĆ P,FEDUS W,HAMILTON W L,et al.Deep Graph Infomax[C]//7th International Conference on Learning Representations.New Orleans:ICLR,2019.
[15]JIANG Y,RONG Y,CHENG H,et al.Query-Driven GraphConvolutional Networks for Attributed Community Search[C]//48th International Conference on Very Large Databases.Sydney:PVLDB,2022.
[16]JIAN X,WANG Y,CHEN L.Effective and efficient relational community detection and search in large dynamic heterogeneous information networks[J].Proceedings of the VLDB Endowment,2020,13(10):1723-1736.
[17]YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[J].Knowledge and Information Systems,2015,42(1):181-213.
[18]FORTUNATO S.Community detection in graphs[J].PhysicsReports,2009,486(3/4/5):27-38.
[19]KIPF T N,WELLING M.Semi-Supervised Classification withGraph Convolutional Networks[C]//5th International Confe-rence on Learning Representations.Toulon,France:ICLR 2017.
[20]HAMILTON W L,YING R,LESKOVEC J.Inductive Representation Learning on Large Graphs[J].Advances in Neural Information Processing Systems.2017,30(1):1025-1035.
[21]DU J,ZHANG S,WU G,et al.Topology Adaptive Graph Con-volutional Networks[J].arXiv.1710.10370,2017.
[22]CHIANG W L,LIU X,SI S,et al.Cluster-GCN:An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York,NY,USA:ACM,2019:257-266.
[23]FANG Y,HUANG X,QIN L,et al.A Survey of Community Search Over Big Graphs[J].The VLDB Journal,2020,29(1):353-392.
[24]CHEN Y Q,QIAN T Y,LI W L,et al.Exploiting Composite Relation Graph Convolution for Attributed Network Embedding[J].Journal of Computer Research and Development,2020,57(8):1674-1682.
[25]LI S S,GUO J F,ZHENG C,et al.Attraction Classification Based on User Reviews and Heterogeneous Graph Neural Network[J].Journal of Chinese Computer Systems,2023,44(9):1884-1891.
[26]ZHAO Y H,HAN L W.Heterogeneous Networks Overlapping Community Discovery Algorithm Based on Network Embedding[J].Journal of Chinese Computer Systems,2021,42(12):2660-2665.
[27]ZHOU Y,FANG Y,LUO W,et al.Influential CommunitySearch over Large Heterogeneous Information Networks[J].Proceedings of the VLDB Endowment,2023,16(8):2047-2060.
[1] DU Ming, YANG Wen, ZHOU Junfeng. Maximum Influential Community Search in Heterogeneous Information Network [J]. Computer Science, 2023, 50(8): 16-26.
[2] WANG Huiyan, YU Minghe, YU Ge. Deep Learning-based Heterogeneous Information Network Representation:A Survey [J]. Computer Science, 2023, 50(5): 103-114.
[3] JIANG Zong-li, FAN Ke, ZHANG Jin-li. Generative Adversarial Network and Meta-path Based Heterogeneous Network Representation Learning [J]. Computer Science, 2022, 49(1): 133-139.
[4] ZHAO Jin-long, ZHAO Zhong-ying. Recommendation Algorithm Based on Heterogeneous Information Network Embedding and Attention Neural Network [J]. Computer Science, 2021, 48(8): 72-79.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.