How are graphs of k-nearest neighbors built? (for clustering)

I’ve seen that there are several clustering algorithms (for example, CHAMELEON or even Spectral Clustering) that work by converting the data into a weighted (or sometimes unweighted) k-nearest neighbor graph based on the distances between points/observations/rows and I was wondering how these graphs are generated.

Are these graphs directed? If a point A has another point B as a near neighbor but point B doesn’t have point A as a near neighbor, is an edge still drawn? How are weights computed?

• added two examples – anymous.asker Aug 7 '15 at 16:16
• CHAMELEON is irreproducible in my opinion, and spectral clustering usually just uses the pairwise distance matrix, doesn't it? – Anony-Mousse Aug 8 '15 at 10:04
• Well I'm no expert on spectral clustering and I know that there are some computational tricks to make its implementation more efficient using the covariance or the distance matrix I think, but in R, if I look at the specClust function in the kknn package rather than in the kernalb, it says it does it with a graph of knn and has the option to specify the number of neighbours. – anymous.asker Aug 8 '15 at 10:55
• @Anony-Mousse why do you think Chameleon is irreducible? We have a working implementation, it's a bit hacky, but works :) – Tombart Dec 16 '15 at 14:03
• @Tombart I have yet to see a working, reliable implementation. The paper seems to be missing essential detail - how to really partition the graph (they simply refer to hMETIS, which is a 4-page abstract overview article). I stand corrected once I see it available in ELKI, sklearn, R, etc. - see also: stackoverflow.com/questions/10958793/… – Anony-Mousse Dec 16 '15 at 14:36

Any normalised (dis)similarity matrix can be converted to the adjacency matrix of an undirected graph (weighted or not). For an unweighted graph you'll want to empirically set a threshold to its adjacency matrix, i.e. a minimum similarity value for a connection to take place between two nodes. For a given partition of the graph, the modularity metric will quantify the total strength of its clusters, therefore by maximising modularity you get the optimal community structure corresponding to that graph (clustering).

• The graph in question will be undirected as long as your similarity matrix is symmetric.
• Weights (when present) are the normalised similarity values.

The modularity function is basically the objective function of a NP-hard combinatorial problem. There are plenty of (meta)heuristics that do the task and if I'm not mistaken the normalised cut algorithm used in spectral clustering is one of them. I don't have experience with Chameleon but the concept of maximising intracluster similarity while minimising intercluster similarity is the same in modularity optimisation.

Unfortunately there is no package (that I know of) that can automate the adjacency matrix conversion since finding the optimal threshold is a manual process. However, once you have that matrix, R and Mathematica have great packages to do the rest.

• Thanks for the answer, although I found some R packages that do it, with a methodologythat seems to be quite different (producing a fixed number of k neighbors in a directed graph). Here's one for example: artax.karlin.mff.cuni.cz/r-help/library/cccd/html/nng.html – anymous.asker Aug 23 '15 at 21:20
• Can you recommend a book I need to study to be able to understand this sentence: "The modularity function is basically the objective function of a NP-hard combinatorial problem." ;) – K.-Michael Aye Feb 1 '17 at 15:49
• @K.-MichaelAye For computational complexity: Computational Complexity by Christos Papadimitriou. For combinatorial optimization: Combinatorial Optimization: Algorithms and Complexity by Christos Papadimitriou. For the method of optimal modularity and its complexity: On Modularity Clustering – Digio Feb 1 '17 at 19:43

Standard Chameleon is initialized using asymmetrical k-NN algorithm, where parameter $k$ could be fixed to sufficiently large number, e.g. $10$ or derived from dataset size, e.g. $k=\sqrt{n}$.

Weight of edge between $A$ and $B$ is set to $w(e) = dist(A,B)$, where distance is defined as Euclidean distance (or any other distance complying triangular inequality). The graph is not directed.

The authors suggest that also a symmetrical k-NN could be used for graph initialization (when a point A has another point B as a near neighbor but point B doesn’t have point A as a near neighbor, then the edge isn't created). However this approach is typically not used due to its high computational complexity.

Some experiments with symmetrical k-NN are presented by Lesna, Shatovska.

Having simple dataset: you create a graph from k-NN: after partitioning the graph will be much simplified (having large $k$ at the begging might not have any influence at all, because most of the edges will be removed during partitioning). 