GADDI: distance index based subgraph matching in biological networks

By Shijie Zhang, Shirong Li, Jiong Yang. International Conference on Extending Database Technology, 2009

296 citations recorded by the source corpus.

Currently, a huge amount of biological data can be naturally represented by graphs, e.g., protein interaction networks, gene regulatory networks, etc. The need for indexing large graphs is an urgent research problem of great practical importance. The main challenge is size. Each graph may contain thousands (or more) vertices. Most of the previous work focuses on indexing a set of small or medium sized database graphs (with only tens of vertices) and finding whether a query graph occurs in any of these. In this paper, we are interested in finding all the matches of a query graph in a given large graph of thousands of vertices, which is a very important task in many biological applications. This increases the complexity significantly. We propose a novel distance measurement which reintroduces the idea of frequent substructures in a single large graph. We devise the novel structure distance based approach (GADDI) to efficiently find matches of the query graph. GADDI is further optimized by the use of a dynamic matching scheme to minimize redundant calculations. Last but not least, a number of real and synthetic data sets are used to evaluate the efficiency and scalability of our proposed method.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/2c2f9afe5c89bc460193d24c71c2469a43a318bf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Molecular Biology

Citations in the corpus

The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees (2013, methodology): “The GADDI algorithm [18] on the other hand deals with larger graphs and uses an indexing based on a neighborhood structure, similar to the TALE algorithm [19].”
An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases (2012, methodology): “All datasets and query sets used in [2, 5, 11, 17, 18] are modeled as undirected labeled graphs .”
Efficient Subgraph Matching on Billion Node Graphs (2012, methodology): “Recent work [9, 36, 34, 15, 32, 9, 36, 7] indexes information such as global or lo-cal reachability in the graph.”
Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases (2013, background): “Due to good matching order and the C OMB/PER M strategy, TurboISO outperthe NASA dataset contains only trees, VF2, QuickSI, and GADDI show exponential behaviors at the sizes of query sets 8, 12, and 8, respectively.”