Cohesive Subgraph Discovery in Hypergraphs: A Locality-Driven Indexing Framework

Song Kim, Dahee Kim, Taejoon Han, Junghoon Kim *, Hyun Ji Jeong, Jungeun Kim · 2025

Read Cohesive Subgraph Discovery in Hypergraphs: A Locality-Driven Indexing Framework by Song Kim, Dahee Kim, Taejoon Han, Junghoon Kim *, Hyun Ji Jeong, Jungeun Kim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-12523.txt.

Introduction

Song Kim and co-authors present a 2025 indexing method for finding tight knit groups inside hypergraphs. A hypergraph links more than two items at once, which suits modern networks with group ties. Finding dense, cohesive subgroups inside one reveals how the network is built. The snag is choosing the right settings for the search, an open problem. The team wanted retrieval that is fast and does not crawl the whole graph each time.

Their index is driven by locality, the idea that nearby structure predicts what a query needs. It lets users pull out cohesive subgroups on demand, within a fair time budget. Tests on real world networks showed the method beating the alternatives they compared it with. The authors say fast, informed retrieval of this kind can support decisions in many fields that rest on network data.

Catalog record

CREATORSong Kim, Dahee Kim, Taejoon Han, Junghoon Kim *, Hyun Ji Jeong, Jungeun Kim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12523

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cohesive Subgraph Discovery in Hypergraphs: A Locality-Driven Indexing Framework DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation emai; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/18/06 Thanks: * Corresponding author. Song Kim, Dahee Kim, Taejoon Han, Junghoon Kim *, Hyun Ji Jeong, Jungeun Kim Abstract . Hypergraphs, increasingly utilised for modelling complex and diverse relationships in modern networks, gain much attention representing intricate higher-order interactions. Among various challenges, cohesive subgraph discovery is one of the fundamental problems and offers deep insights into these structures, yet the task of selecting appropriate parameters is an open question. To handle that question, we aim to design an efficient indexing structure to retrieve cohesive subgraphs in an online manner. The main idea is to enable the discovery of corresponding structures within a reasonable time without the need for exhaustive graph traversals. This work can facilitate efficient and informed decision-making in diverse applications based on a comprehensive understanding of the entire network landscape. Through extensive experiments on real-world networks, we demonstrate the superiority of our proposed indexing technique. 1. INTRODUCTION Modelling relationships among multiple entities intuitively and effectively is a fundamental challenge in network analysis. Hypergraphs offer a powerful solution by capturing higher-order relationships among groups of entities, transcending the pairwise limitations of traditional graphs. Many real-world networks naturally fit into the hypergraph framework, such as co-authorship networks ( Lung et al. 2018 ) , co-purchase networks ( Xia et al. 2021 ) , and location-based social networks ( Kumar et al. 2020 ) . Given the expressive power of hypergraphs, hypergraph mining has attracted significant attention. In particular cohesive subhypergraph discoveriy has been actively researched, with various models being proposed. These include the k -hypercore ( Leng et al. 2013 ) , (k,l) -hypercore ( Limnios et al. 2021 ) , (k,t) -hypercore ( Bu et al. 2023 ) , nbr- k -core ( Arafat et al. 2023 ) , (k,d) -core ( Arafat et al. 2023 ) , and (k,g) -core ( Kim et al. 2023 ) . The most recent model, the (k,g) -core, defines a maximal subhypergraph where each node has at least k neighbours appearing together in at least g hyperedges. Unlike previous models, which primarily focus on hyperedge cardinality, the (k,g) -core captures direct cohesiveness among neighbouring nodes, allowing for the discovery of more densely connected substructures. Given the benefits, the (k,g) -core has broad applicability in various domains: (1) Team formation: In scenarios of collaborative work or developing marketing strategies, the (k,g) -core can identify appropriate groups of participants that are closely connected through multiple shared projects or interactions, helping to form cohesive and effective teams. (2) Community Search: Query-centric community discovery is a central task in social network analysis ( Sozio and Gionis 2010 ) , it mainly relies on models specifically designed for that purpose. Cohesive subgraph models like the (k,g) -core offer a robust framework for identifying tightly-connected substructures within a network ( Kim et al. 2020 ; Akbas and Zhao 2017 ; Fang et al. 2018 ; Liu et al. 2021 ; Yao and Chang 2021 ) . (3) Foundation for other hypergraph mining tasks: The (k,g) -core can support tasks such as identifying densest subhypergraphs ( Huang and Kahng 1995 ) , influence maximisation ( Arafat et al. 2023 ) , and centrality measures ( Busseniers 2014 ) . Its robust structure enables optimising information spread and quantifying node importance in complex networks. Figure 1 . An illustrative example of proposed framework Despite its utility, selecting the appropriate (k,g) parameters for a certain task remains challenging. As studied in prior works ( Chu et al. 2020 ) , choosing suitable parameters for cohesive subgraph models is a difficult open question, especially when varying levels of cohesion are needed. One of the key difficulties arises from the fact that many real-world applications require online query processing ( Garcia-Molina 2008 ) , making it impractical to compute cohesive subgraphs from scratch for each query. The ability to rapidly adjust parameters based on user-specified criteria is critical, particularly in domains like social network analysis and recommendation systems, where timely responses are essential. Online processing also enables interactive exploration of hypergraphs allowing users to refine their queries based on intermediate results without waiting for long recomputation steps. To address these challenges, we propose an indexing-based framework for cohesive subhypergraph discovery. This framework pre-computes an indexing structure over the hypergraph, allowing for efficient query processing by avoiding repetitive subgraph computations. By utilising this structure, we can process online queries for (k,g) -core computation, enabling applications in various domains. Our approach dramatically reduces the time complexity associated with recalculating cohesive subgraphs for different parameter values, providing a scalable solution that is well-suited for large-scale hypergraphs. The applications of indexing-based cohesive subgraph discovery include: (1) Size-Bounded Cohesive Subgraph Discovery: In scenarios like size-bounded team formation, conference planning, or social event organisation, it is crucial to assemble groups of participants who are closely connected and of appropriate community size ( Yao and Chang 2021 ; Liu et al. 2021 ) . The index-based approach can efficiently identify candidate groups that meet these criteria. (2) User Engagement Analysis: Social networks are often analysed to understand user engagement at multiple levels. By using the (k,g) -core and its index structure, we can evaluate user interactions across various dimensions, helping to identify which users are central to the network cohesion at different levels of connectivity. This insight can be useful for recognising influential users, understanding engagement trends, or even detecting abnormal behaviours like bot activity or coordinated misinformation campaigns. (3) Fraud Detection: In domains such as e-commerce or financial networks, fraudsters often operate within tightly knit groups that exhibit suspiciously high levels of interaction ( Pandit et al. 2007 ; He et al. 2022 ) . The (k,g) -core can be applied to identify these densely connected groups of fraudulent actors, based on the frequency and nature of their interactions. By leveraging the indexing-based structure, it becomes feasible to detect such activities in online time, enhancing the ability to prevent fraud before it escalates. Therefore, in this paper, we propose index-based (k,g) -core decomposition techniques, along with efficient online query processing algorithms that leverage these indexing structures. The overall framework of our proposed approach is illustrated in Figure 1 . It has two main phases: In the (1) Indexing Framework: the hypergraph is preprocessed into a memory-efficient index structure; and (2) Query Processing Framework: users can perform online queries by dynamically adjusting parameters based on the precomputed index. Challenges. Constructing an efficient index for the (k,g) -core is challenging due to the interaction of two variables, k and g , which creates significant overlap among nodes with similar coreness values. This results in redundancy and requires careful handling to maintain both space efficiency and query performance. • Space-efficient indexing structure : The indexing structure must be designed to be queryable for all possible (k,g) combinations. The hierarchical property of the (k,g) -core leads to strong locality between cores with similar values, resulting in significant duplication. Constructing a compact structure to address these challenges is crucial. • Scalable query processing : The indexing structure must support fast query processing.

Read the complete text