Efficient Indexing for Label-Constrained Cohesive Subgraph Queries Over Large Graphs
Xin Deng, Peng Peng, Chuanyu Liu, Xiaoli Xie, Hui Zhou, Zheng Kun Qin · 2025
Many real-world relationships can be effectively represented as edge-labeled graphs, where edge labels encode semantic information vital for graph computations. Analyzing communities within such graphs is of great importance, with cohesive subgraph queries being a fundamental problem in graph analysis. Among these, the k-core model is one of the most widely studied frameworks for cohesive subgraph queries and has attracted significant attention over the past decade. However, most existing k-core models disregard edge labels, limiting their applicability to semantic-aware analyses. In this paper, we propose an index-based method to address the problem of querying k-cores with label constraints in edge-labeled graphs. We first introduce a basic index that maintains core decomposition results for each possible label set. Then, to further optimize performance, we propose an advanced index structure that captures the label containment properties of k- cores by computing canonical label sets for each possible$k$and each vertex. This approach can greatly reduce the index size while ensuring efficient query processing. We also design an optimized algorithm for constructing our index, achieving a significantly faster runtime than naive construction methods. Extensive experiments on real graphs demonstrate the efficiency and effectiveness of our index-based algorithms.