The first step in Laplacian Eigenmaps is to translate your high-dimensional data points into a graph. This graph should capture the local relationships and underlying manifold structure of the data. Instead of looking at all possible connections, we build an adjacency matrix, $W$, that represents only the most meaningful neighborly connections. The core task is deciding what constitutes a 'neighbor'.

There are two primary strategies for defining which points get connected in the graph. Your choice here has significant implications for the final embedding.

The first method is the $\epsilon$-neighborhood graph. You choose a radius, $\epsilon$, and connect any two points, $x_i$ and $x_j$, if the distance between them is less than $\epsilon$. This approach is intuitive and respects the local geometry of the data. If two points are close in the original space, they are connected. However, its main drawback is sensitivity to the choice of $\epsilon$. If $\epsilon$ is too small, you risk creating a graph with multiple disconnected components, isolating clusters of points. If it's too large, you might over-connect the graph, losing the fine local structure.

The second method uses k-nearest neighbors. Instead of a fixed radius, you choose an integer, $k$. For each point, you find its $k$ closest neighbors and create edges connecting them. This method is more adaptive to varying data densities and guarantees that every point will be connected, avoiding the issue of isolated nodes. The trade-off is that in regions of sparse data, a point might be connected to neighbors that are quite far away, potentially distorting the local geometric picture.

A subtle but important issue with the k-NN approach is symmetry. If point A is one of the $k$-nearest neighbors of point B, it doesn't guarantee that B is a neighbor of A. This results in a directed graph. For spectral methods, we need an undirected graph, meaning a symmetric adjacency matrix ($W_{ij} = W_{ji}$). To enforce this, you can define an edge between $i$ and $j$ if either is a neighbor of the other. A more conservative approach is to create an edge only if they are mutual neighbors.

Once you've decided which points are neighbors, you need to assign a weight to their connection. This weight reflects the 'strength' of the neighborhood relationship.

The simplest method is binary weighting. If nodes $i$ and $j$ are neighbors, set the weight $W_{ij} = 1$; otherwise, set it to 0. This is computationally cheap but treats all neighbors equally, ignoring the fact that some are much closer than others.

A more nuanced approach uses a heat kernel to assign weights. This function gives higher weights to closer neighbors, with the weight decaying exponentially as the distance increases. It effectively says that nearby points are much more similar than distant ones.

Choosing the parameter $t$ for the heat kernel is a critical tuning step. A common heuristic is to set it based on the average distance of neighbors in the graph. If you've defined your neighborhood with k-NN, you might set $t$ to the average distance to the $k$-th neighbor across all points.

Once these weights are calculated for all neighboring pairs, you have constructed your weighted adjacency matrix $W$. This matrix is the foundational input for the next steps in Laplacian Eigenmaps, where we will use it to compute the graph Laplacian.