Iterative subgraph mining for principal component analysis

Graph mining methods enumerate frequent subgraphs efficiently, but, it is often problematic to summarize the large number of obtained patterns. Thus it makes sense to combine frequent graph mining with principal component analysis to reduce dimensionality and collect a smaller number of characteristic patterns. We present a novel iterative mining algorithm that captures informative patterns corresponding to major entries of top principal components. It repeatedly calls weighted substructure mining where example weights are updated in each iteration. The Lanczos algorithm, a standard algorithm of eigendecomposition, is employed to update the weights. In experiments, our patterns are shown to approximate the principal components obtained by frequent mining.