So this seems to be the culprit:

Before this line, _is_sorted_by_data(X) is True, and after this line, it becomes False, and hence the warning.

I'm not really sure how to fix this. Maybe @adam2392 has an idea here?

If there are 0's in the diagonal, and X.setdiag(X.diagonal()) puts the 0's somewhere where they weren't before, doesn't that imply the sparse data structure is not sorted by data anymore?

disclaimer: I have not looked into this explicitly, but this is just my first read intuition.

/take

@yuwei-1 please leave a comment with what you understand the issue is and how you intend to solve it before tagging an issue as taken.

Also, this is not a good first issue. You might want to start with an easier issue.

Apologies, I wasn't aware of this protocol. I had reproduced the error yesterday, and tracked the problem down to the same line. I am not entirely sure why this issue is occurring - I assume it is something to do with how sparse matrices are stored - and when we concretely store the diagonal, this changes the ordering of the data. I was intending to solve it by looking into how the scipy csr matrices are stored, the calculations inside _is_sorted_by_data, and what changes before and after X.setdiag(X.diagonal()).

That sounds great. Thanks. Let us know what you find 😊

Hi @adrinjalali, I think I have found the issue, but I do not know how to go about resolving. The TLDR is that by concretising the diagonal values, I do not believe there is any guarantee in the general case that we can still preserve the data ordering in a per-row basis (which is what _is_sorted_by_data is checking for).

I went through a particular worked example below:

from scipy.sparse import csr_array
from sklearn.neighbors._base import _is_sorted_by_data


docs = [["hello", "world", "hello"], ["goodbye", "cruel", "world"]]
indptr = [0]
indices = []
data = []
vocabulary = {}
for d in docs:
    for term in d:
        index = vocabulary.setdefault(term, len(vocabulary))
        indices.append(index)
        data.append(1)
    indptr.append(len(indices))


sparse_array = csr_array((data, indices, indptr), dtype=int)
print("original array: ", sparse_array.toarray())
print("(data, indices, indptr) for original: ", sparse_array.data, sparse_array.indices, sparse_array.indptr)
print("is sorted by data: ", _is_sorted_by_data(sparse_array))

sparse_array.setdiag(sparse_array.diagonal())
print("concretised array: ", sparse_array.toarray())
print("(data, indices, indptr) for concretised: ", sparse_array.data, sparse_array.indices, sparse_array.indptr)
print("is sorted by data: ", _is_sorted_by_data(sparse_array))


output:

original array:  [[2 1 0 0]
 [0 1 1 1]]
(data, indices, indptr) for original:  [1 1 1 1 1 1] [0 1 0 2 3 1] [0 3 6]
is sorted by data:  True
concretised array:  [[2 1 0 0]
 [0 1 1 1]]
(data, indices, indptr) for concretised:  [2 1 1 1 1] [0 1 1 2 3] [0 2 5]
is sorted by data:  False

From this, we see that concretising the diagonal essentially forces the values on the diagonal ([2, 1]) to be stored explicitly in the graph.data array (instead of before, where the 2 was stored in two separate elements in the data array. This is a problem because it violates the condition inside _is_sorted_by_data, where data on the same row should be equal or ascending in size.

I've checked and the setdiag() line does impact tests passing so it does impact the results of DBSCAN. I'm not exactly sure how concretisation affects the algorithm (as the underlying array should be the same) but we could explore ways of achieving the same thing without having to concretise the diagonal, perhaps? The alternative could be to simply make a more detailed warning for this particular case.

I think figuring out why we need to set the diagonal, and how it affects the algorithm is important. You might need to dig deep into the implementation to figure that out, but it'd be very much appreciated.

Agreed. Will look into this over the next week and let you know what I find!

@adrinjalali @luispedro, would adding X = sort_graph_by_row_values(X, warn_when_not_sorted=False) not be the simplest fix? I added that to my local fork and built sklearn in dev, and I no longer got the warning. After all, the original warning was

/Users/luismbvarona/GitHub/scikit-learn/sklearn/neighbors/_base.py:248: EfficiencyWarning: Precomputed sparse input was not sorted by row values. Use the function sklearn.neighbors.sort_graph_by_row_values to sort the input by row values, with warn_when_not_sorted=False to remove this warning.

Perhaps I'm missing some obvious reason to avoid simply sorting, though… As an alternative to sorting, we can also implement the below solution to replicate the logic from actually setting the diagonal of the X matrix:

-        if self.metric == "precomputed" and sparse.issparse(X):
-            # set the diagonal to explicit values, as a point is its own neighbor
-            X = X.copy()  # copy to avoid in-place modification
-            with warnings.catch_warnings():
-                warnings.simplefilter("ignore", sparse.SparseEfficiencyWarning)
-                X.setdiag(X.diagonal())
 
         neighbors_model = NearestNeighbors(
             radius=self.eps,
             algorithm=self.algorithm,
             leaf_size=self.leaf_size,
             metric=self.metric,
             metric_params=self.metric_params,
             p=self.p,
             n_jobs=self.n_jobs,
         )
         neighbors_model.fit(X)
         # This has worst case O(n^2) memory complexity
         neighborhoods = neighbors_model.radius_neighbors(X, return_distance=False)
 
+        if self.metric == "precomputed" and sparse.issparse(X):
+            # Each point is its own neighbor; update neighborhoods accordingly
+            for i, neighborhood in enumerate(neighborhoods):
+                if i not in neighborhoods[i]:
+                    neighborhoods[i] = np.append(neighborhood, i)

Again, I re-ran the initial example provided by @luispedro on my machine with this change, and it no longer showed the warning. (This approach might actually be better than the first just from the perspective of speed/allocations.) Do let me know if there's some flaw in my logic, though.

If there's an efficiency warning but we turn off the warning, then the process is still "inefficient" tho regardless no?

I could be wrong. Haven't followed too heavily.

If there's an efficiency warning but we turn off the warning, then the process is still "inefficient" tho regardless no?

I could be wrong. Haven't followed too heavily.

The original EfficiencyWarning derives from the sparse X matrix no longer being sorted by row value after explicitly setting the diagonal entries. The first fix I proposed was to sort the X matrix by row value after the entry setting but before the neighborhood fitting, although it is true that this may introduce unnecessary overhead (not 100% sure yet). (To clarify—turning off the warning during the sorting affected a different warning from the one we initially got. It is potentially inefficient for a different reason altogether.)

Hence, my second proposed fix (the one I included in #31337) avoids setting the diagonal entries of the sparse matrix at all in favor of updating the neighborhoods data after the model fitting. Hopefully this is more efficient; your thoughts, @adam2392?

Hi @adrinjalali and @yuwei-1, I have also looked into this issue.
I will break it down and the possible next steps.

Firstly, we do need the X.setdiag(X.diagonal()) line because csr arrays only store non-zero elements explicitly. If diagonal elements are missing (which is common in distance matrices), DBSCAN adds them but also changes the internal structure in the process.
There are documented issues with DBSCAN when diagonal elements are missing
#8306 and #439.

So this means we must sort during or after the internal structure of the matrix is changed.
This is the most efficient way to fix the warning. It has to be an internal change.

Proposed Solution ( I agree with @Luis-Varona )

      X.setdiag(X.diagonal())
      # 2. Re‑sort rows so they are monotone by value again
      from sklearn.neighbors import sort_graph_by_row_values
      sort_graph_by_row_values(X, copy=False, warn_when_not_sorted=False) #<--- This sorts the matrix only if it is not sorted

Observe the structure of the matrix at each point.

from scipy.sparse import csr_array
from sklearn.neighbors._base import _is_sorted_by_data
from sklearn.neighbors import sort_graph_by_row_values

A = csr_array([[0,2],[3,0]], dtype=float)
print(A)
print(_is_sorted_by_data(A))        # True

A.setdiag(A.diagonal())             # materialise zeros
print(A)
print(_is_sorted_by_data(A))        # False

# sort data
sort_graph_by_row_values(A, copy=False, warn_when_not_sorted=False)
print(A)
print(_is_sorted_by_data(A))        # True

Output

<Compressed Sparse Row sparse array of dtype 'float64'
        with 2 stored elements and shape (2, 2)>
  Coords        Values
  (0, 1)        2.0
  (1, 0)        3.0
True
<Compressed Sparse Row sparse array of dtype 'float64'
        with 4 stored elements and shape (2, 2)>
  Coords        Values
  (0, 1)        2.0
  (0, 0)        0.0
  (1, 0)        3.0
  (1, 1)        0.0
False
<Compressed Sparse Row sparse array of dtype 'float64'
        with 4 stored elements and shape (2, 2)>
  Coords        Values
  (0, 0)        0.0
  (0, 1)        2.0
  (1, 1)        0.0
  (1, 0)        3.0
True

@EngineerDanny, my ultimate suggestion is actually not to call sort_graph_by_row_values but rather to do away with explicit entry setting altogether and modify the neighborhoods variable after model fitting. See #31337 for more details. Would appreciate your feedback 🙂

From an initial look, it seems both solutions fix the warning but I would be inclined to choose your second proposal @Luis-Varona since the first just seems like a quick fix (which could potentially be inefficient). Could you explain what exactly it is doing?