Mutual kNN graph about pynndescent HOT 4 CLOSED

I believe the following would work:

from pynndescent import NNDescent
import scipy.sparse
import networkx

index = NNDescent(data)
adj_mat = scipy.sparse.lil_matrix((data.shape[0], data.shape[0]), dtype=np.int16)
adj_mat.rows = index._neighbor_graph[0]
adj_mat.data = np.ones_like(index._neighbor_graph[0], dtype=np.int16)
adj_mat = adj_mat.multiply(adj_mat.transpose())
mutual_knn_graph = networkx.from_scipy_sparse_matrix(adj_mat)

With potentially a little finessing of the sparse matrix (some conversions between sparse matrix formats may be required for example). The key here is that the _neighbor_graph attribute contains an array with the indices of the top k neighbors for each point as the zeroth element (the first element is the corresponding distances); Converting that to a lil matrix is pretty easy and then it's just a matter of requisite manipulations of the adjacency matrix.

from pynndescent.

Thanks!

In pynndescent, after constructing this lil_matrix here:

https://github.com/lmcinnes/pynndescent/blob/master/pynndescent/pynndescent_.py#L1046

I can also do:

result.multiply(result.T).sqrt()

Right?

from pynndescent.

Yes, actually that should work too. Much easier. Thanks.

from pynndescent.

This is old now, and I think the link above is not a permalink.
Anyways for anyone else doing the same thing you can build the adjacency graph like this:

import sparse
indices = list()
indptr = list()
count = 0
indptr.append(count)
for row in index._neighbor_graph[0]:

    for item in row:
        indices.append(item)
        count+=1
    indptr.append(count)
    
adj = sparse.csr_matrix( ( np.ones(len(indices)), indices, indptr))

#assert all the indices in the adjacency are really the ones given in the neighbor graph:
for _ in range(50):
    idx = np.random.choice(adj.shape[0])
    assert np.all(np.isclose(index._neighbor_graph[0][idx], adj[idx].indices))

edit: the above is a directional knn graph, so not all nearest neighbor adjacencies will be returned.

from pynndescent.