Efficient dynamic graph construction for inductive semi-supervised learning

Area of Science:

• Machine Learning
• Computer Vision
• Graph Theory

Background:

• Traditional graph construction methods often require the entire dataset upfront (transductive setting).
• Handling sequentially arriving data (inductive setting) with graph construction is less explored and can be computationally expensive if done from scratch.
• Existing methods struggle with dynamic data streams, necessitating efficient updates to graph structures.

Purpose of the Study:

• To develop a generic framework for making existing graph construction methods incremental.
• To enable efficient and dynamic addition of new samples to a pre-existing graph.
• To apply this framework to graph-based label propagation for vision-based recognition tasks.

Main Methods:

• Introduced a generic framework to enable incremental graph construction for any existing method.
• Utilized the Two Phase Weighted Regularized Least Square (TPWRLS) coding scheme to represent new samples and update the graph affinity matrix.
• Applied the framework to graph-based label propagation, updating graph structure and edge weights dynamically.

Main Results:

• The proposed framework allows for efficient, dynamic graph construction by incrementally adding new samples.
• The method updates the entire graph structure, identifying and adjusting affected nodes and edge weights.
• Experimental results demonstrate that the dynamic graph construction is more efficient than batch construction without significant loss in classification accuracy.

Conclusions:

• The developed framework provides an efficient solution for incremental graph construction in inductive settings.
• This dynamic approach is particularly beneficial for large-scale datasets and real-time applications in areas like vision-based recognition.
• The method offers a practical way to maintain and update graph structures as new data becomes available.