Similarity Graph

When data points are hard to separate with simple geometric shapes, it helps to stop thinking of them as dots in space and start thinking of them as a network. A similarity graph does exactly that: it turns a dataset into nodes connected by edges, where each edge says how strongly two points resemble each other.

Each observation becomes a node. Then you define a similarity measure between pairs of points, such as Euclidean-distance-based affinity or cosine similarity. The result is a weighted graph, usually stored as an affinity matrix or adjacency matrix. Stronger edges mean “these two points belong together” more than weaker ones. Common ways to build the graph include:

• k-nearest neighbor graph: connect each point to its k closest neighbors.
• ε-neighborhood graph: connect points within a fixed distance threshold.
• Fully connected graph: connect every pair, with weights like exp(-||x-y||² / 2σ²).

This graph is the raw material for spectral clustering. Instead of clustering directly in the original feature space, the algorithm studies the graph structure through the graph Laplacian and its eigenvectors. That lets it find curved, intertwined, or non-convex groups that methods like k-means would split incorrectly. If the similarity graph is poorly built—wrong distance metric, bad choice of k, or badly scaled features—the clustering can fail because the graph no longer reflects the true neighborhood structure.

In customer segmentation, a similarity graph can connect customers with similar browsing and purchase behavior. In image segmentation, nearby pixels with similar color get linked, making object boundaries easier to recover. In document analysis, articles with similar word distributions form graph neighborhoods that reveal topics. In practice, tools like scikit-learn build this internally for spectral clustering, using functions such as nearest-neighbor graph construction and RBF affinities.