Affinity learning with diffusion on tensor product graph.

Area of Science:

• Machine Learning
• Computer Vision
• Graph Theory

Background:

• Data points are often represented as graphs with potentially unreliable pairwise similarity weights (affinities).
• Existing methods diffuse similarity information on the original graph, which can be limited.
• Higher-order information can yield more reliable similarities but typically incurs higher computational costs.

Purpose of the Study:

• To develop a method for obtaining more reliable data affinities from noisy or uncertain pairwise similarities.
• To introduce an efficient approach for information propagation on tensor product graphs (TPGs).
• To demonstrate the effectiveness of learned affinities in unsupervised learning tasks, specifically image retrieval and segmentation.

Main Methods:

• Proposed utilizing the tensor product graph (TPG) of the original graph with itself to incorporate higher-order information.
• Developed a novel iterative algorithm on the original graph that is equivalent to graph diffusion on the TPG.
• Ensured the proposed method maintains the same computational complexity and storage requirements as propagation on the original graph.

Main Results:

• Achieved a 99.99 percent bull's eye retrieval score on the MPEG-7 shape dataset, surpassing state-of-the-art algorithms.
• Demonstrated significant improvements in Normalized Cut (NCut) segmentation performance when using learned affinities on image patches.
• Outperformed existing state-of-the-art image segmentation methods using the proposed learned affinities.

Conclusions:

• The proposed graph diffusion on TPGs provides a computationally efficient method for learning reliable, unsupervised affinities.
• This approach effectively leverages higher-order data relationships to enhance performance in computer vision tasks.
• The learned affinities offer a robust alternative to original, potentially noisy, similarity measures for manifold learning and segmentation.