Neural Community Search with Compressed Graph Embeddings

Neural Community Search with Compressed Graph Embeddings | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Neural Community Search with Compressed Graph Embeddings Yuxiang Wang, Xiangying Wu, Xiaoxuan Gou, Xiaoliang Xu, Tianxing Wu, and 5 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4640804/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Given a graph $G$ and a query node $q$, community search (CS) aims to find a cohesive subgraph from $G$ that contains $q$ as the desired community of $q$. CS is a fundamental problem in graph data analytics that has gained much research interest. Recently, a new thought of using the deep learning model to support CS has emerged. Supervised models using Graph Neural Networks are presented (i.e., neural community search). However, the lack of explicit consideration for community features results in suboptimal graph embeddings for online community inference, which adversely affects search accuracy. This motivates our solutions. (1) We first present an offline community-injected graph embedding method that incorporates community cohesiveness features into the learned node representations, ensuring the effectiveness of CS. Next, we present a self-augmented method based on KL divergence to optimize node representations. Then, we conduct an efficient online community search based on the enhanced node representations, by employing inner product operation between $q$ and other candidate nodes. (2) To reduce the memory usage of online community search, we employ an Encoder-Decoder model that achieves nearly lossless compression of graph embeddings, while maintaining the effectiveness of online CS. Comprehensive experimental studies on eight real-world datasets show our solution's superiority on effectiveness (at least 9.6% improvement) and efficiency (one to two orders of magnitude faster). Notably, the proposed optimized solution with compressed graph embeddings achieves a comparable performance with the one without compression, while using only 15.2% (on average) of the memory usage in online community search. Community Search Graph Neural Networks Compressed Graph Embedding Encoder-Decoder Model Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4640804","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":324912583,"identity":"51039515-9ab1-48e4-bc9f-d17a01aca4cb","order_by":0,"name":"Yuxiang Wang","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAv0lEQVRIiWNgGAWjYBACPghlk8BwAEjxEKOFDUKlka7lMCla+I8/k+ZtO5/HdyOB8cHbNgZ5c4JaJHLMpHnO3C6WvJHAbDi3jcFwZwNBLTxst3kqbiduuJHABrSOIcHgABEOu81jcA6khf03cVoYEsyAthwA28JMnBaJHPOfc84kJ84887BZcs45CcMNhLTw8x9/bPC2zS6x73jywQ9vymzkCdoCAkyQ6GBsABISRKgHqf1BnLpRMApGwSgYqQAARgU/2wT0CNQAAAAASUVORK5CYII=","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":true,"prefix":"","firstName":"Yuxiang","middleName":"","lastName":"Wang","suffix":""},{"id":324912584,"identity":"f37e8976-fbb5-41b1-bf39-ee124fd9f310","order_by":1,"name":"Xiangying Wu","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Xiangying","middleName":"","lastName":"Wu","suffix":""},{"id":324912585,"identity":"bcc3b1bf-e556-49bc-bfcd-f8a99cb8ef88","order_by":2,"name":"Xiaoxuan Gou","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Xiaoxuan","middleName":"","lastName":"Gou","suffix":""},{"id":324912586,"identity":"fc9cd967-51fd-44e8-80db-92b011b15478","order_by":3,"name":"Xiaoliang Xu","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Xiaoliang","middleName":"","lastName":"Xu","suffix":""},{"id":324912587,"identity":"5824ad0b-aedb-4ea4-81a6-30c694ed9d52","order_by":4,"name":"Tianxing Wu","email":"","orcid":"","institution":"Southeast University","correspondingAuthor":false,"prefix":"","firstName":"Tianxing","middleName":"","lastName":"Wu","suffix":""},{"id":324912588,"identity":"90f70e79-e7e9-467b-81bc-6eac329e4195","order_by":5,"name":"Xiangyu Ke","email":"","orcid":"","institution":"Zhejiang University","correspondingAuthor":false,"prefix":"","firstName":"Xiangyu","middleName":"","lastName":"Ke","suffix":""},{"id":324912589,"identity":"7542b1b0-cbbe-43ac-a249-bd72fc4efd72","order_by":6,"name":"Yoshimi Suzuki","email":"","orcid":"","institution":"University of Yamanashi","correspondingAuthor":false,"prefix":"","firstName":"Yoshimi","middleName":"","lastName":"Suzuki","suffix":""},{"id":324912590,"identity":"1d05a427-5379-4996-a61c-437f4d7f9aad","order_by":7,"name":"Yuxia Geng","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Yuxia","middleName":"","lastName":"Geng","suffix":""},{"id":324912591,"identity":"869f3e24-9877-453a-98f2-70a40087e78f","order_by":8,"name":"Runhuai Chen","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Runhuai","middleName":"","lastName":"Chen","suffix":""},{"id":324912592,"identity":"bb91781f-7bdd-421d-a749-411416460ca2","order_by":9,"name":"Zhiyuan Yu","email":"","orcid":"","institution":"Hangzhou Dianzi University","correspondingAuthor":false,"prefix":"","firstName":"Zhiyuan","middleName":"","lastName":"Yu","suffix":""}],"badges":[],"createdAt":"2024-06-26 07:39:00","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4640804/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4640804/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":70320820,"identity":"b91a5c20-9544-422c-898e-13d3c269b83e","added_by":"auto","created_at":"2024-12-02 06:39:20","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1424998,"visible":true,"origin":"","legend":"","description":"","filename":"KAISCSCGE.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4640804/v1_covered_b5a2950d-0d53-432f-b383-6782f8086d38.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Neural Community Search with Compressed Graph Embeddings","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Community Search, Graph Neural Networks, Compressed Graph Embedding, Encoder-Decoder Model","lastPublishedDoi":"10.21203/rs.3.rs-4640804/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4640804/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Given a graph $G$ and a query node $q$, community search (CS) aims to find a cohesive subgraph from $G$ that contains $q$ as the desired community of $q$. CS is a fundamental problem in graph data analytics that has gained much research interest. Recently, a new thought of using the deep learning model to support CS has emerged. Supervised models using Graph Neural Networks are presented (i.e., neural community search). However, the lack of explicit consideration for community features results in suboptimal graph embeddings for online community inference, which adversely affects search accuracy. This motivates our solutions. (1) We first present an offline community-injected graph embedding method that incorporates community cohesiveness features into the learned node representations, ensuring the effectiveness of CS. Next, we present a self-augmented method based on KL divergence to optimize node representations. Then, we conduct an efficient online community search based on the enhanced node representations, by employing inner product operation between $q$ and other candidate nodes. (2) To reduce the memory usage of online community search, we employ an Encoder-Decoder model that achieves nearly lossless compression of graph embeddings, while maintaining the effectiveness of online CS. Comprehensive experimental studies on eight real-world datasets show our solution's superiority on effectiveness (at least 9.6\\% improvement) and efficiency (one to two orders of magnitude faster). Notably, the proposed optimized solution with compressed graph embeddings achieves a comparable performance with the one without compression, while using only 15.2\\% (on average) of the memory usage in online community search.","manuscriptTitle":"Neural Community Search with Compressed Graph Embeddings","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-18 15:02:37","doi":"10.21203/rs.3.rs-4640804/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"e63996a1-15eb-450b-a281-38687540e397","owner":[],"postedDate":"July 18th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2024-12-02T06:38:45+00:00","versionOfRecord":[],"versionCreatedAt":"2024-07-18 15:02:37","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4640804","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4640804","identity":"rs-4640804","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}