Shengxin Liu

Structural graph queries involving connectivity constraints are fundamental primitives in modern data management and analytics. Compared with degree- and edge-based variants, connectivity-based γ-quasi-cliques (γ-CQCs) impose stronger structural constraints and fault tolerance, where robustness is measured by vertex connectivity, i.e., the minimum number of vertices whose removal disconnects the subgraph. However, processing such queries on large graphs remains computationally challenging. In this paper, we study the efficient execution of the Maximum Connectivity-based γ-Quasi-Clique (MCQC) query, which seeks the γ-CQC with the largest number of vertices. The problem is NP-hard, and the non-hereditary nature of vertex connectivity invalidates many traditional pruning techniques, posing significant challenges for exact query processing. Existing solutions rely on generic optimization formulations and exhibit poor scalability in practice. To address these challenges, we propose MCQC-TD, a specialized exact branch-and-bound framework for the MCQC query. MCQC-TD adopts a top-down search strategy and exploits a novel structural characterization of γ-CQCs to enable effective pruning and guided branching. These techniques substantially reduce the theoretical worst-case complexity compared to existing approaches. We further integrate practical query optimization techniques, including an optimized initialization strategy and a query decomposition framework, to enhance scalability on large graphs. Extensive experiments demonstrate that MCQC-TD consistently outperforms the state-of-the-art solution, achieving speedups of up to five orders of magnitude in query time.

Directed graphs are essential for modeling real-world networks, where edge directionality encodes critical information. Cohesive subgraphs in directed graphs, such as directed $(k,\ell )$-plexes (DPlexes), are widely used in applications including community detection, anomaly detection, and functional group discovery. A DPlex is defined as a subgraph in which each vertex disconnects at most $k$ vertices and is meanwhile not pointed to by at most $\ell$ vertices. However, enumerating all maximal DPlexes is computationally challenging, as finding even one maximum DPlex is NP-hard. Furthermore, existing algorithms for undirected graphs cannot be directly applied to directed graphs due to the complexities introduced by edge directionality. To address these challenges, we propose an efficient branch-and-bound algorithm, DPEnum, which incorporates two key techniques: (1) a pivot technique based on a new concept, out-degeneracy ($\delta$), which quantifies sparseness in directed graphs and satisfies $\delta \lt n$, where $n$ is the number of vertices; and (2) a preprocessing technique that removes reducible vertices and directly identifies several maximal DPlexes. DPEnum achieves a worst-case time complexity of $O^*(\alpha _{k}^\delta )$, where $O^*$ suppresses the polynomial factors and $\alpha _{k} \lt 2$, outperforming the naive $O^*(2^{n})$. Additionally, we propose LDPEnum for enumerating large maximal DPlexes with at least $s$ vertices, which uses the upper-bounding technique to prune search branches. Extensive experiments on real-world datasets show that our algorithms achieve up to four orders of magnitude speedup compared to the baseline.

Temporal graphs are widely used to model dynamic interactions across diverse domains, including social networks, biology, and e-commerce. Querying historical cohesive subgraphs, defined as extracting cohesive subgraphs from the graph snapshot induced by a given time interval, is a fundamental task in temporal graph analytics. Yet, current index-based methods are typically designed for a single model. This specialization yields high performance for a specific target but cannot be reused for others, which limits extensibility. In this paper, we propose a unified index-based framework to address this limitation. We focus on a generalized class of Historical CSMs (His-CSMs), which is characterized by two structural properties: non-overlapping (resultant subgraphs are vertex-disjoint) and monotonic (validity in a time interval implies validity in any super interval). This class includes prominent models such as historical connected components (His-CC) and historical k -cores (His-Core). To address the His-CSM query problem, we reduce queries for different CSMs to a single canonical query, the spanning connected component query, and design an index-based solution to answer this query efficiently. Building on this framework, we provide concrete instantiations for both His-CC and His-Core queries. Extensive experiments on real-world temporal graphs show that our method outperforms state-of-the-art baselines, achieving up to 60X speedups for His-CC and up to 100X speedups for His-Core.