Mining the space of graph properties

Abstract

Existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. While such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. In this paper, we develop a foundation for mining the properties themselves. We present a theoretical framework defining the space of graph properties, a variety of mining queries enabled by the framework, techniques to handle the enormous size of the query space, and an experimental system called F-Miner that demonstrates the utility and feasibility of property mining.