먼저 이웃 그래프를 정하기
각 점의 가까운 이웃을 연결하고 유사도를 간선 가중치 Wᵢⱼ로 정한다. 정한 거리 안의 점을 연결하거나 최근접 이웃을 이용하는 방식이 있다. 고차원 좌표를 그대로 비교하기 전에 변수 스케일과 거리 함수가 의미 있는지 확인해야 한다. 그래프를 다르게 만들면 결과 좌표도 달라진다.
이웃 좌표 차이의 비용
1차원 좌표 yᵢ에 대해 ΣWᵢⱼ(yᵢ−yⱼ)²를 작게 하면 강한 간선으로 연결된 점이 가까워진다. 모든 점을 한곳에 모으는 자명한 해를 피하려고 크기와 중심에 제약을 둔다. 차수 행렬 D와 L=D−W를 사용하면 Ly=λDy라는 일반화 고유값 문제로 연결된다.
세 점 경로의 예제
단위 가중치로 1번과 2번, 2번과 3번만 연결한 그래프를 생각하자. D의 대각은 (1,2,1)이고 y=(−1,0,1)에 대해 Ly=y, Dy=y이므로 λ=1이다. 상수 벡터는 λ=0에 대응하므로 이를 제외한 좌표를 이용하면 세 점의 연결 순서를 표현할 수 있다. 정규화 배율과 전체 부호는 별도로 정할 수 있다.
전체 거리를 보존하지는 않는다
가까운 이웃의 관계를 강조하므로 멀리 떨어진 두 점 사이의 원래 유클리드 거리가 그대로 유지될 필요는 없다. 그래프가 끊어지면 0 고유값이 여러 개 생겨 연결 성분 처리가 중요해진다. 낮은 차원에서 멀어 보이거나 겹쳐 보인다는 사실만으로 원자료의 전체 관계를 단정하지 않는다.