  Classification and regression in which the inputs are graphs of arbitrary
size and shape have been paid attention in various fields such as computational
chemistry and bioinformatics. Subgraph indicators are often used as the most
fundamental features, but the number of possible subgraph patterns are
intractably large due to the combinatorial explosion. We propose a novel
efficient algorithm to jointly learn relevant subgraph patterns and nonlinear
models of their indicators. Previous methods for such joint learning of
subgraph features and models are based on search for single best subgraph
features with specific pruning and boosting procedures of adding their
indicators one by one, which result in linear models of subgraph indicators. In
contrast, the proposed approach is based on directly learning regression trees
for graph inputs using a newly derived bound of the total sum of squares for
data partitions by a given subgraph feature, and thus can learn nonlinear
models through standard gradient boosting. An illustrative example we call the
Graph-XOR problem to consider nonlinearity, numerical experiments with real
datasets, and scalability comparisons to naive approaches using explicit
pattern enumeration are also presented.
