Application Scenarios Biological data analysis 51 A large amount of biological data can be represented by graphs, and it is significant to analyze biological data with graph search techniques Protein-interaction network(PIN) analysis provides valuable insight into an organisms functional organization and evolutionary behavior.” For example, one can get the topological properties of a Pin formed by high- confidence human protein interactions obtained from various public interaction databases by Pin analysis 6
Application Scenarios 6 • A large amount of biological data can be represented by graphs, and it is significant to analyze biological data with graph search techniques. – “Protein-interaction network (PIN) analysis provides valuable insight into an organism’s functional organization and evolutionary behavior.” Biological data analysis [5] – For example, one can get the topological properties of a PIN formed by highconfidence human protein interactions obtained from various public interaction databases by PIN analysis
Outline What is graph search? Graph search why bother? Three Types of Graph Search Challenges Related techniques Summary
Outline 7 • What is graph search? • Graph search, why bother? • Three Types of Graph Search • Challenges & Related techniques • Summary
What is Graph Search?
8 What is Graph Search?
What is Graph Search? A unified definition [6](in the name of graph matching) Given a pattern graph Gp and a data graph G check whether G."matches"G, and identify all"matched subgraphs Remarks Two classes of queries Boolean queries(Yes or No) Functional queries, which may use Boolean queries as a subroutine Graphs contain a set of nodes and a set of edges, typically with labels Pattern graphs are typically small( e.g., 10), but data graphs are usually huge(e.g, 108)
What is Graph Search? 9 A unified definition [6] (in the name of graph matching): Remarks: • Given a pattern graph Gp and a data graph G: – check whether Gp ‘‘matches’’ G; and – identify all ‘‘matched’’ subgraphs. – Two classes of queries: – Boolean queries (Yes or No) – Functional queries, which may use Boolean queries as a subroutine – Graphs contain a set of nodes and a set of edges, typically with labels – Pattern graphs are typically small (e.g., 10), but data graphs are usually huge (e.g., 108 )
What is Graph Search? Different semantics of"match" implies different" types" of graph search, including, but not limited to, the following Shortest paths/distances!4 Subgraph isomorphism[) Graph homomorphism and its extensions!101 Graph simulation and its extensions 8, 9 Graph keyword search! Neighborhood queries!111 Graph search is a very general concept 10
What is Graph Search? 10 Different semantics of “match” implies different “types” of graph search, including, but not limited to, the following: • Shortest paths/distances[4] • Subgraph isomorphism[12] • Graph homomorphism and its extensions[10] • Graph simulation and its extensions[8,9] • Graph keyword search[7] • Neighborhood queries[11] • … Graph search is a very general concept!