sparse_to_dense requires indices to be lexicographically sorted in 0.7

Question

There was a change in behavior between versions 0.7 and 0.6 in sparse_to_dense that now requires the indices to be lexicographically sorted. This is a somewhat onerous requirement for some of my uses because the way I generate the indices is matched to the way I generate the elements (third arg of sparse_to_dense) and sorting both is a bit of a hassle. I see that the validate_indices option can be set to False to ignore this. Is it safe to do so? Why the requirement in the first place?

Answer 1

Looking at the current implementation for tensorflow::sparse::SparseTensor::ToDense<T>(), it seems that the conversion does not depend on the order of indices. Therefore, you can run tf.sparse_to_dense(sparse_indices, ..., validate_indices=False) on unsorted sparse_indices. A consistent result will be produced as long as there are no duplicate indices (otherwise it looks like the current implementation is last writer wins, but that is not guaranteed in the API).

It looks like the requirement for lexicographically sorted indices arises from a desire to check that there are no duplicates in sparse_indices. You can check the order property and absence of duplicates with a simple scan over the indices tensor (only considering rows i and i - 1), whereas checking for duplicates in an order independent fashion is more expensive. Since there's limited upside to the more conservative check, and a potentially large performance downside, we chose not to implement it, but the documentation could be clearer on this point!