scalable tools to build kNN graph over sparse data
I think what you might be looking for is,

L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning

They have multiple runtime options specifically for different kinds of datasets (including sparse data). The link for the same is : http://glaros.dtc.umn.edu/gkhome/node/1162