EMBEDDING SIGNALS ON GRAPHS WITH UNBALANCED DIFFUSION EARTH MOVER'S DISTANCE.

Area of Science:

• Machine Learning
• Graph Signal Processing
• Computational Statistics

Background:

• Relational machine learning frequently analyzes large graphs representing interactions or similarities.
• Target entities for analysis are often signals defined on these graphs.
• Comparing and organizing datasets of graph signals is crucial for various applications.

Purpose of the Study:

• To propose an efficient method for comparing and organizing datasets of graph signals.
• To introduce a novel metric, unbalanced diffusion earth mover's distance (UDEMD), for graph signal comparison.
• To demonstrate the robustness and efficiency of UDEMD in diverse applications.

Main Methods:

• Utilizing an earth mover's distance (EMD) with geodesic cost over graphs.
• Developing an unbalanced graph EMD that embeds into an L^1 space, termed UDEMD.
• Applying UDEMD to measure distances between graph signals, ensuring noise robustness.

Main Results:

• UDEMD provides efficient and accurate distance embeddings for graph signals.
• The method demonstrates robustness to noise in distance calculations.
• UDEMD-based embeddings show high efficiency compared to existing methods.

Conclusions:

• UDEMD offers a significant advancement in comparing and organizing graph signals.
• The method is effective across diverse applications, including patient data, cell-gene graphs, and gene-cell graphs.
• UDEMD enables more efficient and accurate analysis of complex relational data.