A Novel Knowledge Representation Framework for Computing Sub-Graph Isomorphic Queries in Interaction Network Databases

In emerging applications such as biological networks and evolving social networks, computing sub-graph isomorphism is a necessary artifact for answering many interesting questions. Efficient computation of sub-graph isomorphism, however, has remained a difficult problem in artificial intelligence and databases. In logic programming, isomorphic sub-graph search has met with limited success mainly due to representation hurdles, large memory needs and lack of a suitable procedure. In this paper, we demonstrate that a simple representation of undirected graphs enables logic based computation of isomorphic sub-graphs very efficiently. We also present a graph and query rewriting technique to compute such queries using logic programming languages such as XSB or Prolog. The space and memory requirement for this framework is extremely low even for very large networks due to the representation technique, and the manner in which the procedure functions.