ABSTRACT
This chapter reviews some of the most prominent dimensionality reduction (DR) methods that rely on graphs. These include several techniques based on geodesic distances, such as Isomap and its variants. The chapter introduces the necessary notations and classical methods such as principal component analysis and classical metric multidimensional scaling. DR proves to be a powerful tool for data visualization and exploratory analysis. The use of graphs is an important breakthrough in the domain and largely contributes to a significant performance leap. The chapter details how graphs can help introducing nonlinearities in the DR methods. It reviews some of the major DR methods that perform manifold learning by using either distances (global methods) or similarities (local methods). The chapter also deals with graph embedding, another paradigm used in nonlinear DR. It compares the methods on a few examples. Finally, the chapter draws the conclusions and sketches some perspectives for the near future.
