Building k edge-disjoint spanning trees of minimum total length for isometric data embedding

Area of Science:

• Data Science
• Graph Theory
• Machine Learning

Background:

• Isometric data embedding relies on neighborhood graphs to estimate geodesic distances.
• Accurate geodesic distance estimation is crucial for various data analysis tasks.

Purpose of the Study:

• To develop a novel approach for constructing k-edge-connected neighborhood graphs.
• To improve the accuracy of geodesic distance estimation in data embedding.

Main Methods:

• The study proposes constructing neighborhood graphs by finding k edge-disjoint spanning trees.
• The objective is to minimize the sum of the total lengths of these spanning trees.

Main Results:

• The proposed method successfully constructs k-edge-connected neighborhood graphs.
• Experimental results demonstrate superior performance in geodesic distance estimation compared to the nearest neighbor approach.

Conclusions:

• The new method for constructing k-edge-connected neighborhood graphs is effective for isometric data embedding.
• This approach offers a more accurate alternative for geodesic distance estimation.