> pairwise_distances raises an exception only if the metric comes from
> scipy. If the metric is implemented in scikit-learn, it works fine.
> I think it should be quite easy to add sparse matrix support.
> Actually, I haven't checked but your code might even (almost)
> support them already.

I did a quick check with "euclidean" and "cosine" metrics on sparse (csr) matrices: it doesn't work (for different reasons). 
I have not estimated the amount of work required to support sparse matrices, but it does not seem trivial. 
I am under the impression that this function is already useful as-is, and could be merged. Support for sparse matrices could be added later. 
@mblondel, @ogrisel could you give me your impressions?