The prevalence of online query services in human life has attracted significant interest from the fields of economics and databases in determining appropriate pricing for such services. Simultaneously, the utilization of graph analytics across various domains has resulted in substantial social and economic benefits in recent years. As the adoption of graph analytics continues to expand, there is a corresponding need to establish fair pricing models for the information contributed by each participant in the data ecosystem. However, current query-based pricing frameworks cannot be applied to price graph statistics, as they fail to consider buyers' affordability and prevent arbitrage trading. To address this gap, in this paper, we propose a novel framework GSHOP for pricing graph statistic queries. Instead of pricing a precise answer for a query, our framework offers the flexibility to price a set of answers injected with noise. Based on the framework, data owners initially create and publish extended local views (ELVs) to represent their graph data. Additionally, it allows buyers to tolerate a certain degree of noise added to the answer to reduce their payments. The framework accurately quantifies the relationship between noise and price to ensure that payment and compensation are reasonable for the buyer and owners, respectively. We also propose algorithms specifically designed for fundamental graph statistics, including node degrees and subgraph counts such as k-stars and k-cliques. Furthermore, we formally prove that the pricing framework is arbitrage-free. Extensive experimental results on real-life graph data validate the good performance of the proposed framework and algorithms.

Data is increasingly being bought and sold online, and data market platforms have emerged to facilitate these activities. However, current mechanisms for pricing data mainly focus on traditional relational data. In this paper, we propose a framework GQP for pricing graph data on the data market platform. Specifically, given a set of graph price points and a graph query, we can efficiently compute the price of the query based on the graph price points. We first identify an important property (called arbitrage-free) GQP should satisfy with, such that GQP can effectively price the graph query. We then study the exact pricing problem (NP-completeness) and develop an efficient approximation algorithm to solve the problem. We also study the approximate pricing when the query cannot be answered by price points exactly. Furthermore, to avoid the expensive computing cost of updating graph price points, we study the dynamic query pricing and propose novel solutions to reuse the computed graph price points to reduce the computational complexity. Finally, we use real-life data and synthetic data to experimentally verify that the proposed algorithms are able to effectively and efficiently price large graph data based on the framework GQP.

A data lake is a repository for massive raw and heterogeneous data, which includes multiple data models with different data schemas and query interfaces. Keyword search can extract valuable information for users without the knowledge of underlying schemas and query languages. However, conventional keyword searches are restricted to a certain data model and cannot easily adapt to a data lake. In this paper, we study a novel keyword search. To achieve high accuracy and efficiency, we introduce canonical graphs and then integrate semantically related vertices based on vertex representations. A matching entity based keyword search algorithm is presented to find answers across multiple data sources. Finally, extensive experimental study shows the effectiveness and efficiency of our solution.

In the area of social network, bioinformatics, e-commerce and so on, the graph model is widely used to present the certain objects and the relations among them. Taking such graph model as the source data, it is significant to extract the compact informative subgraph which can best explain how the given query points are connected. Existing work considers only the connection between individual objects and the returned subgraph is unfavorable when the given query points are far distant each other in the initial graph. In the paper, we will first simplify and present the initial graph by the PeakGraph model in which the graph nodes are divided into different groups based on the density of linkages. Based on the PeakGraph model, we further extract the informative subgraph by two steps, namely local search and global search. In the former step, the local optimal subgraph is extracted for each group; in the latter step, we connect these local optimal subgraphs by some heuristic rules. Our experiments show that our algorithm achieves good performance in both accuracy and efficiency for all kinds of queries.

A significant number of applications on graph require the key relations among a group of query nodes. Given a relational graph such as social network or biochemical interaction, an informative subgraph is urgent, which can best explain the relationships among a group of given query nodes. Based on Particle Swarm Optimization (PSO), a new framework of SISP (Searching the Informative Subgraph based on PSO) is proposed. SISP contains three key stages. In the initialization stage, a random spreading method is proposed, which can effectively guarantee the connectivity of the nodes in each particle; In the calculating stage of fitness, a fitness function is designed by incorporating a sign function with the goodness score; In the update stage, the intersection-based particle extension method and rule-based particle compression method are proposed. To evaluate the qualities of returned subgraphs, the appropriate calculating of goodness score is studied. Considering the importance and relevance of a node together, we present the PNR method, which makes the definition of informativeness more reliable and the returned subgraph more satisfying. At last, we present experiments on a real dataset and a synthetic dataset separately. The experimental results confirm that the proposed methods achieve increased accuracy and are efficient for any query set.