Graph querying is the task of finding similar embeddings of a given query graph in a large target graph. Existing techniques employ the use of structural as well as node and edge label similarities to find matches of a query in the target graph. However, these techniques have ignored the presence of context (usually manifested in the form of node edge label distributions) in the query. In this paper, we propose CGQ (Contextual Graph Querying), a context-aware subgraph matching technique for querying real-world graphs. We introduce a novel sub-graph searching paradigm, which involves learning the context prevalent in the query graph. Under the proposed paradigm, we formulate the most contextually-similar subgraph querying problem that, given a query graph and a target graph, aims to identify the (top-k) maximal common subgraph(s) between the query and the target graphs with the highest contextual similarity. The quality of a match is quantized using our proposed contextual similarity function. We prove that the problem is NP-hard and also hard to approximate. Therefore, to efficiently solve the problem, we propose a hierarchical index, CGQ-Tree, with its associated search algorithm. Our experiments show that the proposed CGQ index is effective, efficient and scalable.
Note that although literature has witnessed a plethora of indexing techniques for (sub-)graph querying @cite_53 @cite_59 @cite_43 @cite_10 @cite_34 @cite_39 @cite_54 @cite_46 @cite_5 @cite_41 @cite_52 @cite_57 @cite_42 , we do not compare against any of these methods owing to the reasons that are three fold. First, the notion of context has never been studied in the broad domain of graph querying, and thus, the requirements for index-structures to be flexible and adapt to dynamically changing distance functions with queries has not been met by the existing techniques. Secondly, the index-structures are usually designed keeping a certain requirement of the problem formulation or similarity function in mind, i.e. incorporating capabilities for -- structural matching, label matching etc.; these methods are therefore fine-tuned according to a specific use-case(s) and hence are inherently inextensible to newer similarity functions. Lastly, while one may argue that a host of state-of-the-art methods for searching subgraph isomorphic embeddings of a query graph in a target graph @cite_25 (and the references therein) can be easily extended to new similarity functions and should be used as a baseline, these methods are not capable of finding maximal common subgraphs, which is central to our problem formulation.
@cite_41 @cite_53 @cite_54 @cite_42 @cite_52 @cite_39 @cite_57 @cite_43 @cite_59 @cite_5 @cite_46 @cite_34 @cite_10 @cite_25
1502916507 2423652555 2060072498 2016057533
The nearestor near-neighbor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasing interest in building search index structures for performing similarity search over high-dimensional data, e.g., image databases, document collections, time-series databases, and genome databases. Unfortunately, all known techniques for solving this problem fall prey to the of dimensionality." That is, the data structures scale poorly with data dimensionality; in fact, if the number of dimensions exceeds 10 to 20, searching in k-d trees and related structures involves the inspection of a large fraction of the database, thereby doing no better than brute-force linear search. It has been suggested that since the selection of features and the choice of a distance metric in typical applications is rather heuristic, determining an approximate nearest neighbor should su ce for most practical purposes. In this paper, we examine a novel scheme for approximate similarity search based on hashing. The basic idea is to hash the points Supported by NAVY N00014-96-1-1221 grant and NSF Grant IIS-9811904. Supported by Stanford Graduate Fellowship and NSF NYI Award CCR-9357849. Supported by ARO MURI Grant DAAH04-96-1-0007, NSF Grant IIS-9811904, and NSF Young Investigator Award CCR9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and or special permission from the Endowment. Proceedings of the 25th VLDB Conference, Edinburgh, Scotland, 1999. from the database so as to ensure that the probability of collision is much higher for objects that are close to each other than for those that are far apart. We provide experimental evidence that our method gives signi cant improvement in running time over other methods for searching in highdimensional spaces based on hierarchical tree decomposition. Experimental results also indicate that our scheme scales well even for a relatively large number of dimensions (more than 50). In this paper, we study the problem of subgraph matching that extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. The existing algorithms for subgraph matching follow Ullmann's backtracking approach; that is, iteratively map query vertices to data vertices by following a matching order of query vertices. It has been shown that the matching order of query vertices is a very important aspect to the efficiency of a subgraph matching algorithm. Recently, many advanced techniques, such as enforcing connectivity and merging similar vertices in query or data graphs, have been proposed to provide an effective matching order with the aim to reduce unpromising intermediate results especially the ones caused by redundant Cartesian products. In this paper, for the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. Our second contribution is proposing a new path-based auxiliary data structure, with the size O(|E(G)| x |V(q)|), to generate a matching order and conduct subgraph matching, which significantly reduces the exponential size O(|V(G)||V(q)|-1) of the existing path-based auxiliary data structure, where V (G) and E (G) are the vertex and edge sets of a data graph G, respectively, and V (q) is the vertex set of a query @math . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms by up to @math orders of magnitude. Subgraph querying has been applied in a variety of emerging applications. Traditional subgraph querying based on subgraph isomorphism requires identical label matching, which is often too restrictive to capture the matches that are semantically close to the query graphs. This paper extends subgraph querying to identify semantically related matches by leveraging ontology information. (1) We introduce the ontology-based subgraph querying, which revises subgraph isomorphism by mapping a query to semantically related subgraphs in terms of a given ontology graph. We introduce a metric to measure the similarity of the matches. Based on the metric, we introduce an optimization problem to find top K best matches. (2) We provide a filtering-and-verification framework to identify (top-K) matches for ontology-based subgraph queries. The framework efficiently extracts a small subgraph of the data graph from an ontology index, and further computes the matches by only accessing the extracted subgraph. (3) In addition, we show that the ontology index can be efficiently updated upon the changes to the data graphs, enabling the framework to cope with dynamic data graphs. (4) We experimentally verify the effectiveness and efficiency of our framework using both synthetic and real life graphs, comparing with traditional subgraph querying methods. Given a query graph @math q and a data graph @math G, subgraph similarity matching is to retrieve all matches of @math q in @math G with the number of missing edges bounded by a given threshold @math ∈. Many works have been conducted to study the problem of subgraph similarity matching due to its ability to handle applications involved with noisy or erroneous graph data. In practice, a data graph can be extremely large, e.g., a web-scale graph containing hundreds of millions of vertices and billions of edges. The state-of-the-art approaches employ centralized algorithms to process the subgraph similarity queries, and thus, they are infeasible for such a large graph due to the limited computational power and storage space of a centralized server. To address this problem, in this paper, we investigate subgraph similarity matching for a web-scale graph deployed in a distributed environment. We propose distributed algorithms and optimization techniques that exploit the properties of subgraph similarity matching, so that we can well utilize the parallel computing power and lower the communication cost among the distributed data centers for query processing. Specifically, we first relax and decompose @math q into a minimum number of sub-queries. Next, we send each sub-query to conduct the exact matching in parallel. Finally, we schedule and join the exact matches to obtain final query answers. Moreover, our workload-balance strategy further speeds up the query processing. Our experimental results demonstrate the feasibility of our proposed approach in performing subgraph similarity matching over web-scale graph data.