Abstract
This paper presents Multi-Graph-View Bag Learning (MGVBL), a novel framework for classifying complex objects represented as bags of graphs across multiple feature views. By integrating multi-view learning with multi-instance graph mining, MGVBL captures intricate internal structures and diverse object characteristics. The approach utilizes a column generation-based optimization and an efficient pruning strategy to handle the high-dimensional subgraph search space. Evaluations on DBLP and Corel datasets demonstrate that MGVBL significantly outperforms existing methods in classification accuracy and computational efficiency.
Introduction
Many real-world objects, such as chemical compounds, brain networks, or images, possess rich internal structures that simple feature vectors cannot adequately capture. Representing these objects as graphs is effective, but introduces two major challenges:
- Multiple Perspectives: A single graph view is often insufficient to fully describe an object. For instance, an image might require both color and texture representations.
- Label Ambiguity: Labels are typically assigned to the whole object (a "bag"), while only specific parts of the object may actually correspond to that label—a classic Multi-Instance Learning (MIL) problem.
This paper addresses the "multi-graph-view graph-bag" problem, aiming to identify the most discriminative structural features across multiple views when labels are only available at the bag level.
The MGVBL Framework
The proposed MGVBL algorithm integrates subgraph exploration and model learning into a unified framework.
Technical Components
- Multi-Graph-View Bag Representation: Each object is treated as a "bag" containing multiple graphs, where each graph represents a local characteristic derived from different feature extraction "views."
- Decision Stumps as Weak Classifiers: Discovered subgraphs act as decision stumps. If a graph contains a specific subgraph, it contributes a weight toward the classification label.
- Joint Optimization: Using Column Generation, the algorithm iteratively adds the most discriminative subgraphs. It maximizes the margin between positive and negative bags while ensuring all graphs within negative bags are treated as negative instances.
- Efficient Pruning: To manage the NP-hard search for subgraphs, the authors derived a mathematical upper bound for the discriminative score (mgScore), allowing for effective pruning of the search tree.
Experimental Evaluation
MGVBL was evaluated on two datasets:
- DBLP (Scientific Publication Categorization): 600 papers categorized by AI and Database fields, using abstract text correlations and citation/title relationships as views.
- Corel (Content-Based Image Retrieval): 600 images (Cats vs. others), with graphs built from HSV color features and Local Binary Patterns (LBP) for texture.
Results and Insights
MGVBL consistently outperformed baseline methods, including MIVBL (which ignores graph structure) and MGVGL (which ignores the multi-instance nature).
Key Findings
- Synergy of Structure and Bags: The results prove that both structural information and bag-level constraints are vital for accurate classification of complex objects.
- Efficiency and Convergence: The pruning strategy maintains stable runtimes even at low support thresholds. Furthermore, the model typically converges to high accuracy within 20–40 iterations.
- Cross-View Synergy: Joint regularization across views allows the discovery of the most effective feature combinations rather than just the best features in isolation.
Conclusion
MGVBL provides a robust framework for multi-view, multi-instance graph learning. While the current implementation relies on frequent subgraph mining and faces scaling challenges for massive datasets, it represents a significant step forward in structural object classification. Future work may explore dynamic graph extensions and more scalable heuristic approximations.
Summary updated