Application Scenarios Biological data analysis [171 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 11
Application Scenarios 11 • 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 [17] – 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
What is Graph Search? 12
12 What is Graph Search?
What is Graph Search? A unified definition (3 (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? 13 A unified definition[3] (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!111 Subgraph isomorphism[) Graph homomorphism and its extensions Graph simulation and its extensions 7, 8 Graph keyword search(2 Neighborhood queries!10 Graph search is a very general concept
What is Graph Search? 14 Different semantics of “match” implies different “types” of graph search, including, but not limited to, the following: • Shortest paths/distances[11] • Subgraph isomorphism[12] • Graph homomorphism and its extensions[9] • Graph simulation and its extensions[7,8] • Graph keyword search[2] • Neighborhood queries[10] • … Graph search is a very general concept!
Three Types of Graph Search Cohesive subgraphs Keyword search on graphs Graph pattern matching
Three Types of Graph Search 15 • Cohesive subgraphs • Keyword search on graphs • Graph pattern matching