||July 19, 2013
||Dr. Hiroto Saigo, Kyushu Institute of Technology
||Multiple response regression for graph mining
Graph data are becoming increasingly common in machine learning and data mining, and its application field pervades to bioinformatics, natural language processing and social network analysis. Accordingly, methods to extract patterns from graph data; graph mining has been studied and developed rapidly these years. Since the number of patterns in graph data is huge, a central issue in graph mining community is how to efficiently collect informative patterns suitable for subsequent tasks such as classification or regression.
In this paper we consider a multiple response regression problem on graph data, in which each graph example has several target response values. We propose an efficient iterative mining algorithm by taking into account the eigen- structure of the target response matrix. Our algorithm is efficient since it automatically collects subgraph patterns corresponding to a few major eigenvectors only, compared to existing approaches that need to collect subgraph patterns separately from each target response vector.
We also present a greedy approach that can decrease the number of graph mining calls, leading to further efficiency. In extensive computational experiments based on both synthetic and real-world data, we verify the effectiveness of the proposed method.