Neighbourhood graph

At the heart of Isomap is the computation of the manifold inter-point distances which is achieved by estimating the geodesic distances across a neighbourhood graph. The geodesic distance between two points is represented as Sy = [Pg.12]

Abstract In this chapter, an overview of some of the key issues associated with modelling manifolds are provided. This covers the constmction of neighbourhood graphs, and automatic estimation of relevant parameters how manifold modelling techniques deal with various topologies of the data and the problem of noise. Each of these aspects are supported by an illustrative example. The interaction between these key issues is also discussed. 

Keywords Neighbourhood graphs Manifold approximations Noise and outliers Data topologies... 

Fig. 3.1 A set of points are sampled from a 1-dimensional manifold curled up on itself in 2-dimensional space a. A good approximation of the neighbourhood graph is shown in b where there are no gaps in the graph and no jumps that short-circuit the manifold, (c) shows an example of where the neighbourhood graph is inadequately estimated there are multiple short-circuits where points are joined as neighbours but do not lie on the same patch of the manifold...

The goal of the -edge disjoint spanning tree algorithm (Min- -ST) [9] is to find a neighbourhood graph, G = (V, E), that is minimally -edge connected. 

To obtain a low-dimensional embedding using Isomap, three steps are followed a fc-nearest neighbour graph is built the shortest path matrix of the neighbourhood graph is computed Anally, eigendecomposition of the shortest path matrix is computed. As such, the computational complexity of each of these parts are considered separately before an overall complexity for Isomap can be obtained. 

---