gBoost: a mathematical programming approach to graph classification and regression

By Hiroto Saigo, Sebastian Nowozin, Tadashi Kadowaki, Taku Kudo, Koji Tsuda. 2009

163 citations recorded by the source corpus.

Graph mining methods enumerate frequently appearing subgraph patterns, which can be used as features for subsequent classification or regression. However, frequent patterns are not necessarily informative for the given learning problem. We propose a mathematical programming boosting method (gBoost) that progressively collects informative patterns. Compared to AdaBoost, gBoost can build the prediction rule with fewer iterations. To apply the boosting method to graph data, a branch-and-bound pattern search algorithm is developed based on the DFS code tree. The constructed search space is reused in later iterations to minimize the computation time. Our method can learn more efficiently than the simpler method based on frequent substructure mining, because the output labels are used as an extra information source for pruning the search space. Furthermore, by engineering the mathematical program, a wide range of machine learning problems can be solved without modifying the pattern search algorithm.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Information Systems

In Signal Processing

Citations in the corpus

Text Categorization as a Graph Classification Problem (2015, methodology): “We used gSpan (graph-based Substructure pattern (Yan and Han, 2002)) as frequent sub-graph miner like (Jiang et al., 2010; Arora et al., 2010) mostly because of its fast available C++ implementation from gBoost (Saigo et al., 2009).”
Ordered Decompositional DAG kernels enhancements (2015, background): “…the ODDST+ and the ODDTANHST+ kernels on CAS, AIDS, NCI1 and GDD datasets with the optimal kernel parameters (reported between brackets). is classified as active (positive class) or inactive (negative class) if the activity score is, respectively, above or below a specified threshold.”
Supervised classification and mathematical optimization (2013, methodology): “For instance, in [77] [206] a column generation approach, [105], is used in the boosting environment, whereas a quadratic programming model is used in [174] .”