{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T06:55:04Z","timestamp":1768978504186,"version":"3.49.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T00:00:00Z","timestamp":1683849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key RD Program of China","award":["2020YFB1406900 and 2020AAA0107100"],"award-info":[{"award-number":["2020YFB1406900 and 2020AAA0107100"]}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["62072365 and 61772392"],"award-info":[{"award-number":["62072365 and 61772392"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100015401","name":"Key Research and Development Program of Shaanxi","doi-asserted-by":"crossref","award":["2020KW-002"],"award-info":[{"award-number":["2020KW-002"]}],"id":[{"id":"10.13039\/501100015401","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Innovation Capability Support Plan of Shaanxi","award":["2021PT-010"],"award-info":[{"award-number":["2021PT-010"]}]},{"name":"High-performance Computing Platform of Xi\u2019an Jiaotong University"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>Tenuous subgraph finding aims to detect a subgraph with few social interactions and weak relationships among nodes. Despite significant efforts made on this task, they are mostly carried out in view of graph-structured data. These methods depend on calculating the shortest path and need to enumerate all the paths between nodes, which suffer the combinatorial explosion. Moreover, they all lack the integration of neighborhood information. To this end, we propose a novel model named Graph Neural Network with Motif-aware for tenuous subgraph finding (GNNM), a neighborhood aggregation-based GNN framework that can capture the latent relationship between nodes. We design a GNN module to project nodes into a low-dimensional vector combining the higher-order correlation within nodes based on a motif-aware module. Then we design greedy algorithms in vector space to obtain a tenuous subgraph whose size is greater than a specified constraint. Particularly, considering that existing evaluation indicators cannot capture the latent friendship between nodes, we introduce a novel Potential Friend concept to measure the tenuity of a graph from a new perspective. Experimental results on the real-world and synthetic datasets demonstrate that our proposed method GNNM outperforms existing algorithms in efficiency and subgraph quality.<\/jats:p>","DOI":"10.1145\/3589643","type":"journal-article","created":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T11:59:33Z","timestamp":1680350373000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Graph Neural Networks with Motisf-aware for Tenuous Subgraph Finding"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2765-6582","authenticated-orcid":false,"given":"Heli","family":"Sun","sequence":"first","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1427-2472","authenticated-orcid":false,"given":"Miaomiao","family":"Sun","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5616-5822","authenticated-orcid":false,"given":"Xuechun","family":"Liu","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7312-6534","authenticated-orcid":false,"given":"Linlin","family":"Zhu","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6463-5158","authenticated-orcid":false,"given":"Liang","family":"He","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6641-7807","authenticated-orcid":false,"given":"Xiaolin","family":"Jia","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, Xi\u2019an, China"}]},{"given":"Yuan","family":"Chen","sequence":"additional","affiliation":[{"name":"Information Center of Ministry of Science and Technology, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2023,5,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_3_2_3_2","doi-asserted-by":"crossref","unstructured":"Cecile Bothorel Juan David Cruz Matteo Magnani and Barbora Micenkova. 2015. Clustering attributed graphs: models measures and methods. arXiv:1501.01676 [cs.SI]","DOI":"10.1017\/nws.2015.9"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-04298-5_14"},{"key":"e_1_3_2_5_2","unstructured":"Giorgos Bouritsas Fabrizio Frasca Stefanos Zafeiriou and Michael M. Bronstein. 2020. Improving graph neural network expressivity via subgraph isomorphism counting. Retrieved from https:\/\/arXiv:2006.09252."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807452"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10179"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219947"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10462-017-9590-2"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","unstructured":"Guyue Han and Harish Sethu. 2016. Waddling random walk: Fast and accurate sampling of motif statistics in large graphs. Retrieved from https:\/\/arXiv:1605.09776.","DOI":"10.1109\/ICDM.2016.0029"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2018.2859580"},{"key":"e_1_3_2_16_2","unstructured":"Xie Jierui Stephen Kelley and Boleslaw K. Szymanski. 2011. Overlapping community detection in networks: The state of the art and comparative study. Retrieved from https:\/\/arXiv:1110.5813."},{"key":"e_1_3_2_17_2","unstructured":"Thomas N. Kipf and Max Welling. 2016. Variational graph auto-encoders. Retrieved from https:\/\/arXiv:1611.07308."},{"key":"e_1_3_2_18_2","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. Retrieved from https:\/\/arXiv:cs.LG\/1609.02907."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357880"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxaa115"},{"key":"e_1_3_2_21_2","unstructured":"Fanzhen Liu Shan Xue Jia Wu and Chuan Zhou. 2020. Deep learning for community detection: Progress challenges and opportunities. Retrieved from https:\/\/arXiv:2005.08225."},{"key":"e_1_3_2_22_2","unstructured":"Fanzhen Liu Shan Xue Jia Wu Chuan Zhou Wenbin Hu C\u00e9cile Paris Surya Nepal Jian Yang and Philip S. Yu. 2020. Deep learning for community detection: Progress challenges and opportunities. Retrieved from https:\/\/arXiv:2005.08225."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403150"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052597"},{"key":"e_1_3_2_28_2","unstructured":"Yu Rong Wenbing Huang Tingyang Xu and Junzhou Huang. 2019. Dropedge: Towards deep graph convolutional networks on node classification. Retrieved from https:\/\/arXiv:1907.10903."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"Rahmtin Rotabi Krishna Kamath Jon M. Kleinberg and Aneesh Sharma. 2017. Detecting strong ties using network motifs. Retrieved from https:\/\/arXiv:1702.07390.","DOI":"10.1145\/3041021.3055139"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622352"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.302591"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806423"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385415"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741093"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"J. Ugander L. Backstrom and J. Kleinberg. 2013. Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections. Retrieved from https:\/\/arXiv:abs\/1304.1548.","DOI":"10.1145\/2488388.2488502"},{"key":"e_1_3_2_36_2","article-title":"Graph attention networks","author":"Veli\u010dkovi\u0107 Petar","year":"2018","unstructured":"Petar Veli\u010dkovi\u0107, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Li\u00f2, and Yoshua Bengio. 2018. Graph attention networks. In Proceedings of the International Conference on Learning Representations.","journal-title":"Proceedings of the International Conference on Learning Representations"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939753"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00014"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2018.00048"},{"key":"e_1_3_2_40_2","unstructured":"Felix Wu Tianyi Zhang Amauri Holanda de Souza Jr. Christopher Fifty Tao Yu and Kilian Q. Weinberger. 2019. Simplifying Graph Convolutional Networks. arXiv:1902.07153 [cs.LG]."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.1145\/2588555.2610495","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Xin Huang","year":"2014","unstructured":"Huang Xin, Cheng Hong, Qin Lu, Tian Wentao, and Yu Jeffrey Xu. 2014. Querying k-truss community in large and dynamic graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 1311\u20131322."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/2832415.2832542"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_3_2_46_2","unstructured":"Ziwei Zhang Peng Cui and Wenwu Zhu. 2020. Deep Learning on Graphs: A Survey. Retrieved from https:\/\/arXiv:cs.LG\/1812.04202."},{"key":"e_1_3_2_47_2","unstructured":"Jie Zhou Ganqu Cui Shengding Hu Zhengyan Zhang Cheng Yang Zhiyuan Liu Lifeng Wang Changcheng Li and Maosong Sun. 2021. Graph Neural Networks: A Review of Methods and Applications. Retrieved from https:\/\/arXiv:cs.LG\/1812.08434."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589643","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589643","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:45Z","timestamp":1750291425000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,12]]},"references-count":46,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3589643"],"URL":"https:\/\/doi.org\/10.1145\/3589643","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,12]]},"assertion":[{"value":"2021-11-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}