A Generic Framework for Mining Top-k Representative Subgraph Patterns

  • Sayan Ranu | IIT Delhi

Mining subgraph patterns is an active area of research. Till now, the focus has primarily been on mining all subgraph patterns in the given database. However, due to the exponential subgraph search space, the number of patterns mined, typically, is too large for any human mediated analysis. Consequently, deriving insights from the mined patterns is hard for domain scientists. In addition, subgraph pattern mining is posed in multiple forms: the function that models if a subgraph is a pattern varies based on the application and the database could be over multiple graphs or a single, large graph. A natural question that therefore arises is the following: Given any graph database type and a subgraph importance function, can we develop a technique to mine k subgraph patterns that best represent all other patterns of interest? We will discuss a generic framework called RESLING that answers this question. Experiments show that RESLING is up to 20 times more representative of the pattern space and 2 orders of magnitude faster than the state-of-the-art techniques.

Series: Microsoft Research Talks