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.

Bipartite graphs are ubiquitous, such as E-commerce network and gene networks. Efficient analysis of (p, q)- biclique is one of the important problems over bipartite graphs. However, existing works over (p, q)-biclique suffer from two main challenges. Firstly, most of them only focus on static graphs, while lots of bipartite graph-structured data are constantly created in real world, forming streaming bipartite graphs. Secondly, results of (p, q)-biclique could be of exponential scale, which may overwhelm analysts. Hence, computing top$k$most important (p, q)-bicliques is worth considering. In this paper, we study a new problem to maintain top$k$densest (p, q)-bicliques over a streaming bipartite graph. We propose a new framework, called as TopK-BC, to compute the proposed problem effectively. We design an efficient pruning strategy for edge deletion stage, called IDpruning. In particular, we maintain an intermediate density for each edge to efficiently compute high-density (p, q)-bicliques. Also, we introduce effective optimization technologies to filter out unpromising intermediate results and further enhance the performance. Extensive experiments over real world datasets confirm the efficiency and effectiveness of our solution.

Variable-length path queries are essential for finding paths in a graph that adhere to a specified length constraint, utilizing only edges with labels from a restricted subset of the edge labels. These queries play a crucial role in graph analytics and are supported by practical graph query languages like Cypher in property graph systems and SPARQL 1.1 in RDF graph systems. In this paper, we present a novel solution for efficient evaluation of variable-length path queries, based on worst-case optimal joins. Our solution's core relies on a jumping-like worst-case optimal join technique, allowing us to select a query vertex order that differs completely from existing graph systems based on worst-case optimal joins. Furthermore, we introduce a cost-based dynamic programming optimizer that combines traditional and jumping-like worst-case optimal join techniques. We also propose an optimization technique to leverage intra-query parallelism during query evaluation. Through extensive experiments conducted on numerous synthetic and real RDF and property graphs, we demonstrate that the proposed technique achieves excellent performance.

We propose to design vertex encoding for determinations of no-result edge queries that should not be executed. Edge query is one of the core operations in mainstream graph databases, which is to retrieve edges connecting two given vertices. Real-world graphs may be too large to be stored in memory and frequently accessing edge data on disk usually incurs much overhead. The average degree of real-world graph tends to be much less than the vertex number, and edges may not exist in most pairs of vertices. Efficiently avoiding no-result edge query executions will certainly improve the performance of graph database. In this paper, we propose a new and important problem for determining no-result edge queries: vertex encoding for edge nonexistence determination (VEND, for short). We build a low dimensional vertex encoding for all vertices, and we can efficiently determine most vertex pairs that are connected by no edges just with their corresponding codes. The encoding can be efficiently adjusted when data updates happen. With VEND, we can utilize in-memory efficient operations to filter no-result disk accesses for edge query. We also design SIMD-oriented compression optimizations to further improve performance. Extensive experiments on real-world datasets confirm the effectiveness of our solution.

We propose to design vertex encoding for determinations of no-result edge queries that should not be executed. Edge query is one of the core operations in mainstream graph databases, which is to retrieve the corresponding edges connecting two given vertices. Real-world graphs may be too large to be stored in memory and frequently accessing edge data on disk usually incurs much overhead. Average degree of real-world graph tends to be much less than the vertex number, and edges may not exist in most pairs of vertices. Efficiently avoiding no-result edge query executions will certainly improve performance of graph database. In this paper, we propose a new and important problem for determining no-result edge queries: vertex encoding for edge nonexistence determination (VEND, for short). We build a low dimensional vertex encoding for all vertices, and we can efficiently determine most vertex pairs that are connected by no edges just with their corresponding codes. With VEND, we can utilize in-memory efficient operations to filter no-result disk accesses for edge query. We also design maintenance algorithms for the proposed solution when data updates happen. Extensive experiments on many real-world datasets confirm the ability of our solution on determining a quite high proportion of non-edge vertex pairs, as well as the acceleration for edge queries.