Graph pattern queries (GPQ) over RDF graphs extend basic graph patterns to support variable-length paths (VLP), thereby enabling complex knowledge retrieval and navigation. Generally, variable-length paths describe the reachability between two vertices via a given property within a specified range. With the increasing scale of RDF graphs, it is necessary to design a partitioning method to achieve efficient distributed queries. Although many partitioning strategies have been proposed for large RDF graphs, most existing methods result in numerous inter-partition joins when processing GPQs, which impacts query performance. In this paper, we formulate a new partitioning problem, MaxLocJoin, aims to minimize inter-partition joins during distributed GPQ processing. For MaxLocJoin, we propose a partitioning framework (PIP) based on property-induced subgraphs, which consist of edges with a specific set of properties. The framework first finds a locally joinable property set using a cost-driven algorithm, LJPS, where the cost depends on the sizes of weakly connected components within its property-induced subgraphs. Subsequently, the graph is partitioned according to the weakly connected components. The framework can achieve two key objectives: first, it enables complete local processing of all variable-length path queries (eliminating inter-partition joins); second, it can minimize the number of inter-partition joins required for traditional graph pattern queries. Moreover, we identify two types of independently executable queries (IEQ): the locally joinable IEQ and the single-property IEQ. After that, a query decomposition algorithm is designed to transform all GPQ into one of them for independent execution in distributed environments. In experiments, we implement two prototype systems based on Jena and Virtuoso, and evaluate them over both real and synthetic RDF graphs. The results show that MaxLocJoin achieves performance improvements from 2.8x to 10.7x over existing methods.

Graph neural networks (GNNs) are powerful deep learning models for graph-structured data, demonstrating remarkable success across diverse domains. Recently, the database (DB) community has increasingly recognized the potentiality of GNNs, prompting a surge of researches focusing on improving database systems through GNN-based approaches. However, despite notable advances, There is a lack of a comprehensive review and understanding of how GNNs could improve DB systems. Therefore, this survey aims to bridge this gap by providing a structured and in-depth overview of GNNs for DB systems. Specifically, we propose a new taxonomy that classifies existing methods into two key categories: (1) Relational Databases, which includes tasks like performance prediction, query optimization, and Text-to-SQL, and (2) Graph Databases, addressing challenges like efficient graph query processing and graph similarity computation. We systematically review key methods in each category, highlighting their contributions and practical implications. Finally, we suggest promising avenues for integrating GNNs into Database systems.

Subgraph matching is one of the fundamental problems in graph analytics. Existing methods generate matching orders to guide their search, which consists of a series of extensions. Each time, they extend smaller partial matches into larger ones until all complete answers are obtained. However, these methods have two significant drawbacks. Firstly, their matching order generations are usually heuristic and challenging to be effective for different queries. Secondly, each extension, serving as its computation unit, is coarse-grained and may hinder performance. This granularity issue stems from merging generation and expansion operations into a single computation unit. To address these challenges, we introduce a pioneering framework for Reinforced Subgraph Matching (RSM) that features a fine-grained operation-based search plan. Initially, RSM proposes a fresh paradigm for search, referred to as operation-level search, where each computation unit is defined as an operation that either generates or expands a candidate set under a query vertex. To deal with the second problem and fully exploit the potential of this novel search paradigm, RSM implements a reinforcement learning strategy to generate operation-level search plans. RSM's reinforcement learning approach for constructing operation-based search plans encompasses three modules. In the first module, we employ graph neural networks to extract query vertex representation from graphs. Then, the other two modules leverage multilayer perceptron and are designed to create the generation and expansion operations, respectively. Extensive experiments on real-world graph datasets validate that RSM cuts down query processing time, outperforming existing algorithms by up to 1 to 2 orders of magnitude.

Subgraph query can be applied in various scenarios, such as fraud detection and cyberattack pattern analysis. However, computing subgraph queries usually traverses a huge search space. Many efforts have been made to reduce this search space. The size of the answer set can be exponential, providing a substantial lower bound for the search space. Additionally, different answers may overlap, and a single vertex can occur multiple times in different matches. In this paper, we propose a new problem to compute the match cover of a subgraph query. We define the match cover as a subset of answers such that the vertices included are exactly the same as those in the entire set. There can be more than one match covers, however, we only return one, as long as we can avoid the huge overhead of searching the entire set. It is inefficient to apply traditional subgraph query methods for computing match cover. Specifically, existing methods do not prune partial matches that could grow into full matches. For match cover computation, if the vertices in those full matches are already included in previously found matches, continuing the computation over such partial matches is a waste of time. We propose a new framework, called MatCo, to compute the match cover. In MatCo, we design a new data structure, called local candidate space, to determine whether the future search scopes of partial matches have been covered. We can easily maintain local candidate space and efficiently conduct the determination. We also reduce some Cartesian products, which are inevitable in existing methods, into linear enumerations, which significantly improves performance. Extensive experiments over various datasets confirm that our method outperforms comparative ones by 1~3 orders of magnitude. Efficiently computing the minimum match cover could be an interesting future work.

Continuous subgraph matching (CSM) is an important problem of graph analysis over dynamic graphs. Given a query graph, existing CSM efforts return numerous matches, which may overwhelm analysts. In addition, they do not consider weighted graphs that are ubiquitous in many real-world applications, such as payment networks where each edge has a weight to represent a transaction amount. Over these weighted graphs, matches of the given query graph have diverse priorities for analysis if they own different densities. In this paper, we propose a new problem of CSM-TopK to compute$k$matches of a given query graph with the highest densities over a dynamic weighted graph and prove it to be NP-hard. To compute the CSM-TopK effectively, we first define a star-structured subquery, based on which we design two lightweight indexes, called global and local MWstar, respectively. In particular, the global MWstar maintains the maximum weights of all partial matches of each specific star-structured subquery. Differently, the local MW star is designed based on the corresponding maximum weight distribution for each specific data vertex. Additionally, a query-dependent graph compacted technique is introduced to further improve the performance on both time and space. Extensive experiments over real-world datasets show that our MW star- based approaches surpass the comparative ones by at least two orders of magnitude.

In this study, we address the problem of unnecessary computations in traditional continuous subgraph matching (CSM) frameworks due to premature expansions of the search space in dynamic graphs. Traditional CSM frameworks expand small partial matches according to a specific matching order until the final results are obtained. This extension involves two sequential steps: computing candidate vertices for an unmapped query vertex and expanding the search space using these candidate data. However, this long-established search model has a potential flaw, as premature expansions of the search space can lead to unnecessary computations. To address this issue, we introduce a novel search process, NewSP. Unlike traditional methods, NewSP emphasizes operations rather than extensions, incorporating a unique feature of postponing expansion at the operation level. This approach prevents premature expansions without compromising the initial pruning power of the selected matching order. Furthermore, NewSP allows for multiple consecutive expansions, paving the way for a multi-expansion strategy for further optimization. Our model also enables the implementation of cache strategies for candidate set reuse, as it does not necessitate immediate expansion of a candidate set once identified. To improve performance, we propose an adaptive index filtering strategy independent of the specific index used. Comprehensive experiments demonstrate that our method improves by up to two to three orders of magnitude compared to traditional algorithms. A case study showed that NewSP can accelerate the majority of subgraph matching algorithms.

Butterfly counting is widely used to analyze bipartite networks, but counting butterflies in original bipartite networks can reveal sensitive data and pose a risk of individual privacy, specifically edge privacy. Current privacy notions do not fully address the needs of both user-user and user-item bipartite networks. In this paper, we propose a novel privacy notion, edge decentralized differential privacy (edge DDP), which preserves edge privacy in any bipartite network. We also design the randomized edge protocol (REP) to perturb real edges in bipartite networks. However, a significant amount of noise in perturbed bipartite networks often leads to an overcount of butterflies. To achieve accurate butterfly counting, we design the randomized group protocol (RGP) to reduce noise. By combining REP and RGP, we propose a two-phase framework called butterfly counting in limitedly synthesized bipartite networks (BC-LimBN) to synthesize networks for accurate butterfly counting. BC-LimBN has been rigorously proven to satisfy edge DDP. Our experiments on various datasets confirm the high accuracy of BC-LimBN in butterfly counting and its superiority over competitors, with a mean relative error of less than 10% at most. Furthermore, our experiments show that BC-LimBN has a low time cost, requiring only a few seconds on our datasets.

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.

Abundant valuable knowledge can be obtained by learning frequencies of relations in a decentralized network, which benefits various further complex tasks, such as range query and commodity recommendation. Nonetheless, counting frequencies in original networks can reveal sensitive data and pose a risk to individual privacy, specifically relation privacy. Current privacy notions do not fully preserve both the privacy of relations’ values and existence. In this paper, we introduce an enhanced privacy notion, relation local differential privacy (relation LDP), which provides comprehensive preservation in relation privacy. However, a significant amount of noise in perturbed networks often leads to severe errors in the accuracy of relation frequencies. To obtain accurate frequencies, we propose a framework called frequency estimation based on combination (Fest-C), which decomposes relation frequencies into two independent parts, the total frequency of relations and relative proportions. Binning relations into hyper-relations, Fest-C reduces errors of total frequency and relative proportions, respectively, and then estimates frequencies by logically multiplying them. Finally, we rigorously prove that Fest-C satisfies relation LDP. Our experiments on various datasets confirm the high accuracy of Fest-C in estimating relation frequencies with a much lower time overhead compared to competitors.

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.

Graph Neural Networks (GNNs) are powerful models for non-Euclidean data, but their training is often accentuated by massive unnecessary computation: on the one hand, training on non-Euclidean data has relatively high computational cost due to its irregular density properties; on the other hand, the class imbalance property often associated with non-Euclidean data cannot be alleviated by the massiveness of the data, thus hindering the generalisation of the models. To address the above issues, theoretically, we start with a hypothesis about the effectiveness of using a subset of training data for GNNs, which is guaranteed by the gradient distance between the subset and the full set. Empirically, we also observe that a subset of the data can provide informative gradients for model optimization and which changes over time dynamically. We name this phenomenon dynamic data sparsity. Additionally, we find that pruned sparse contrastive models may miss valuable information, leading to a large loss value on the informative subset. Motivated by the above findings, we develop a unified data model dynamic sparsity framework called Data Decantation (DataDec) to address the above challenges. The key idea of DataDec is to identify the informative subset dynamically during the training process by applying sparse graph contrastive learning. The effectiveness of DataDec is comprehensively evaluated on graph benchmark datasets and we also verify its generalizability on image data.

Images are commonly used for various information and knowledge applications, such as advertising and recommendation. Automating image caption generation will significantly improve image accessibility. This cross-modal task, which takes image as input and text as output, however, is difficult for learning. Though prior methods achieve good performance for image caption generation, they rely on either supervised learning which requires sufficient labeled data or unsupervised learning which needs external dataset as language pivot. In this paper, we propose SGCL, a novel Scene Graph Contrastive Learning model for self-supervised image caption generation. SGCL adopts the pre-training and fine-tuning pipeline. Specifically, we first apply scene graph generation and objection detection method to encode scene graph and visual information in the image as feature representation. Later, a decoder network based on graph attention network and recurrent neural network is further designed to generate sequential text as caption. To enable contrastive learning in SGCL, we design scene graph augmentations as contrastive views of images and train the model effectively without ground-truth labels through contrastive learning. Additionally, we introduce the pre-trained word embedding and the context projector to enrich the text representation in the decoder network, which benefits model pre-training. Once the pre-training phase is finished, we further fine-tune the model for the image caption generation task with limited labeled data. Extensive experiments on benchmark dataset demonstrate that SGCL outperforms state-of-the-art models (both supervised and unsupervised).

The growing popularity of dynamic applications such as social networks provides a promising way to detect valuable information in real time. These applications create high-speed data that can be easily modeled as streaming graph. Efficient analysis over these data is of great significance. In this paper, we study the subgraph (isomorphism) search over streaming graph data that obeys timing order constraints over the occurrence of edges in the stream. The sliding window model is employed to focus on the most recent data. We propose an efficient solution to answer subgraph search, introduce optimizations to greatly reduce the space cost, and design concurrency management to improve system throughput. Extensive experiments on real network traffic data and synthetic social streaming data shows that our solution outperforms comparative ones by one order of magnitude with less space cost.

The growing popularity of dynamic applications such as social networks provides a promising way to detect valuable information in real time. These applications create high-speed data that can be easily modeled as streaming graph. Efficient analysis over these data is of great significance. In this paper, we study the subgraph (isomorphism) search over streaming graph data that obeys timing order constraints over the occurrence of edges in the stream. We propose a solution to efficiently answer subgraph search, introduce optimizations to greatly reduce the space cost, and design concurrency management to improve system throughput. Extensive experiments on real network traffic data and synthetic social streaming data confirms the efficiency and effectiveness of our solution.

In this paper, we propose a data structure, a quadruple neighbor list (QN-list, for short), to support real time queries of all longest increasing subsequence (LIS) and LIS with constraints over sequential data streams. The QN-List built by our algorithm requires O(w) space, where w is the time window size. The running time for building the initial QN-List takes O(w logw) time. Applying the QN-List, insertion of the new item takes O(logw) time and deletion of the first item takes O(w) time. To the best of our knowledge, this is the first work to support both LIS enumeration and LIS with constraints computation by using a single uniform data structure for real time sequential data streams. Our method outperforms the state-of-the-art methods in both time and space cost, not only theoretically, but also empirically.

BACKGROUND: Recent advances in omics technology have produced a large amount of liver-related data. A comprehensive and up-to-date source of liver-related data is needed to allow biologists to access the latest data. However, current liver-related data sources each cover only a specific part of the liver. It is difficult for them to keep pace with the rapid increase of liver-related data available at those data resources. Integrating diverse liver-related data is a critical yet formidable challenge, as it requires sustained human effort. RESULTS: We present LiverWiki, a first wiki-based database that integrates liver-related genes, homolog genes, gene expressions in microarray datasets and RNA-Seq datasets, proteins, protein interactions, post-translational modifications, associated pathways, diseases, metabolites identified in the metabolomics datasets, and literatures into an easily accessible and searchable resource for community-driven sharing. LiverWiki houses information in a total of 141,897 content pages, including 19,787 liver-related gene pages, 17,077 homolog gene pages, 50,251 liver-related protein pages, 36,122 gene expression pages, 2067 metabolites identified in the metabolomics datasets, 16,366 disease-related molecules, and 227 liver disease pages. Other than assisting users in searching, browsing, reviewing, refining the contents on LiverWiki, the most important contribution of LiverWiki is to allow the community to create and update biological data of liver in visible and editable tables. This integrates newly produced data with existing knowledge. Implemented in mediawiki, LiverWiki provides powerful extensions to support community contributions. CONCLUSIONS: The main goal of LiverWiki is to provide the research community with comprehensive liver-related data, as well as to allow the research community to share their liver-related data flexibly and efficiently. It also enables rapid sharing new discoveries by allowing the discoveries to be integrated and shared immediately, rather than relying on expert curators. The database is available online at http://liverwiki.hupo.org.cn /.

In this paper, we propose a data structure, a quadruple neighbor list (QN-list, for short), to support real time queries of all longest increasing subsequence (LIS) and LIS with constraints over sequential data streams. The QN-List built by our algorithm requires O ( w ) space, where w is the time window size. The running time for building the initial QN-List takes O ( w log w ) time. Applying the QN-List, insertion of the new item takes O (log w ) time and deletion of the first item takes O ( w ) time. To the best of our knowledge, this is the first work to support both LIS enumeration and LIS with constraints computation by using a single uniform data structure for real time sequential data streams. Our method outperforms the state-of-the-art methods in both time and space cost, not only theoretically, but also empirically.

In this demonstration, we present the gStore RDF triple store. gStore is based on graph encoding and subgraph match, distinct from many other systems. More importantly, it can handle, in a uniform manner, different data types (strings and numerical data) and SPARQL queries with wildcards, aggregate, range and top-k operators over dynamic RDF datasets. We will demonstrate the main features of our system, show how to search Wikipedia documents using gStore and how to build users' own application using gStore through C++/Java API.