Mining the space of graph properties

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.