Boosting for multi-graph classification.

Area of Science:

• Machine Learning
• Graph Theory
• Data Mining

Background:

• Multi-instance learning (MIL) is a supervised learning paradigm where instances are grouped into bags, and labels are assigned to bags.
• Existing MIL methods assume instances share a common feature space, which is not applicable to graph data where features are not readily available.
• Real-world applications like webpage classification require classifying bags of graphs, necessitating a new approach beyond traditional MIL.

Purpose of the Study:

• To introduce and define the novel problem of multi-graph classification (MGC).
• To propose a boosting-based framework (bMGC) for solving the MGC problem.
• To address the challenge of learning from bags of graphs without a shared feature space.

Main Methods:

• Formulation of the multi-graph classification (MGC) problem, where bags are labeled based on the presence of positive graphs.
• Development of a boosting-based multi-graph classification (bMGC) framework utilizing dynamic weight adjustments at both bag and graph levels.
• Iterative selection of subgraphs as weak classifiers, with weights adjusted based on classification accuracy.

Main Results:

• The bMGC framework effectively differentiates graphs within positive and negative bags.
• Dynamic weight adjustment enables the derivation of robust classifiers for MGC.
• Experimental results on real-world tasks demonstrate the superior performance of the proposed bMGC algorithm.

Conclusions:

• The proposed bMGC framework provides an effective solution for multi-graph classification tasks.
• The dynamic weighting strategy is crucial for handling the complexities of learning from bags of graphs.
• This work extends the applicability of graph-based learning to scenarios with complex, multi-graph data structures.