Mining in the Proximity of Subgraphs
Nikhil S. Ketkar, Lawrence B. Holder, Diane J. Cook · 2006
Graphs are a natural way to represent multi-relational data and are extensively used to model a variety of application do-mains in diverse fields ranging from bioinformatics to home-land security. Often, in such graphs, certain subgraphs are known to possess some distinct properties and graph pat-terns in the proximity of these subgraphs can be an indicator of these properties. In this work we focus on the task of min-ing in the proximity of subgraphs, known to possess certain distinct properties and identify patterns which distinguish these subgraphs from other subgraphs without these proper-ties. This task is novel and of considerable interest as it can facilitate the prediction of previously unknown subgraphs possessing the properties under consideration in the graph and can lead to a better understanding of the application domain. We characterize the task of mining in the prox-imity of subgraphs as a supervised learning problem and present a heuristic algorithm for the same. Experimental comparison with the ILP system CProgol on real world and artificial datasets provides a strong indication of the abil-ity and viability of the approach in uncovering interesting patterns. 1.