English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  gBoost: A Mathematical Programming Approach to Graph Classification and Regression

Saigo, H., Nowozin, S., Kadowaki, T., Kudo, T., & Tsuda, K. (2008). gBoost: A Mathematical Programming Approach to Graph Classification and Regression. Machine Learning, 75(1), 69-89. doi:10.1007/s10994-008-5089-z.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-C655-8 Version Permalink: http://hdl.handle.net/21.11116/0000-0003-2C6F-1
Genre: Journal Article

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Saigo, H1, 2, Author              
Nowozin, S1, 2, Author              
Kadowaki, T, Author
Kudo, T, Author
Tsuda, K1, 2, Author              
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s):
 Dates: 2008-11
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/s10994-008-5089-z
BibTex Citekey: 5356
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Machine Learning
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Dordrecht : Springer
Pages: - Volume / Issue: 75 (1) Sequence Number: - Start / End Page: 69 - 89 Identifier: ISSN: 0885-6125
CoNE: https://pure.mpg.de/cone/journals/resource/08856125