Repository: scikit-learn/scikit-learn
Pull request: ENH BaseLabelPropagation to accept sparse matrices
<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/main/CONTRIBUTING.md
-->
Fixes #17085
Closes #17384
#### Reference Issues/PRs
<!--
Example: Fixes #1234. See also #3456.
Please use keywords (e.g., Fixes) to create link to the issues or pull requests
you resolved, so that they will automatically be closed when your pull request
is merged. See https://github.com/blog/1506-closing-issues-via-pull-requests
-->
Also see stale PR on the same issue https://github.com/scikit-learn/scikit-learn/pull/17384

#### What does this implement/fix? Explain your changes.
At present `LabelPropagation` and `LabelSpreading` throw  `TypeError` for sparse matrices.

As per my investigation this error arises because the function `_validate_data` function in `BaseLabelPropagation.fit` method hasn't been called with the `accept_sparse` parameter.

This PR fixes the issue by passing the same parameters to `_validate_data` as passed in `predict_proba` method of the 
`BaseLabelPropagation` class.

In addition, the `test_fit_transduction` func  in `test_label_propagation.py` has been updated to test for sparse metrices
using `pytest.mark.parametrize`.

#### Any other comments?
Most of tests in `test_label_propagation.py` can be parametrized. I have parametrized the func `test_fit_transduction`
in the following format

Firstly the global variable `ESTIMATORS` can be rewritten as follows for (what i believe to be more pythonic) to reduce redundancy.
```python
ESTIMATORS = [
    (label_propagation.LabelPropagation, {'kernel': 'rbf'}),
    (label_propagation.LabelPropagation, {'kernel': 'knn', 'n_neighbors': 2}),
    (label_propagation.LabelPropagation, {
        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
    }),
    (label_propagation.LabelSpreading, {'kernel': 'rbf'}),
    (label_propagation.LabelSpreading, {'kernel': 'knn', 'n_neighbors': 2}),
    (label_propagation.LabelSpreading, {
        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
    }),
]

# TO
ESTIMATOR_CLS = [label_propagation.LabelPropagation,
                 label_propagation.LabelSpreading]


PARAMETERS = [{'kernel': 'rbf'}, {'kernel': 'knn', 'n_neighbors': 2}, {
        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
    }]
```

This breakdown to two globals allows for parametrization using the decorators
```python
@pytest.mark.parametrize("estimator", ESTIMATOR_CLS)
@pytest.mark.parametrize("parameters", PARAMETERS)
def func(estimator, parameters):
    pass
``` 
This is what I have done with the test that I have modified. This same thing can be done to many of the tests. 
And then we can remove the `ESTIMATORS` global variable completely.
But I haven't touched them since this is a deviation from the issue. 
Perhaps this can be done in a separate PR. (or this one)

```python
ESTIMATOR_CLS = [label_propagation.LabelPropagation,
                 label_propagation.LabelSpreading]


PARAMETERS = [{'kernel': 'rbf'}, {'kernel': 'knn', 'n_neighbors': 2}, {
        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
    }]


MATRIX_TYPES = (sp.csc_matrix, sp.csr_matrix, sp.coo_matrix, sp.dok_matrix,
                sp.bsr_matrix, sp.lil_matrix, sp.dia_matrix, np.array)


@pytest.mark.parametrize("matrix_type", MATRIX_TYPES)
@pytest.mark.parametrize("estimator", ESTIMATOR_CLS)
@pytest.mark.parametrize("parameters", PARAMETERS)
def test_fit_transduction(matrix_type, estimator, parameters):
    samples = [[1., 0.], [0., 2.], [1., 3.]]
    labels = [0, 1, -1]
    clf = estimator(**parameters).fit(matrix_type(samples), labels)
    assert clf.transduction_[2] == 1
```

Also, we can take the following as  global and use parametrize
```
ALPHA = [0.1, 0.3, 0.5, 0.7, 0.9]
SAMPLE = [[1., 0.], [0., 1.], [1., 1.]]
LABELS = [0, 1, -1]
```
Just let me know how I should proceed regarding this. Thanks for reading! :)

<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->


Problem statement:
LabelPropagation raises TypeError: A sparse matrix was passed
#### Describe the bug

LabelPropagation (and LabelSpreading) error out for sparse matrices.

#### Steps/Code to Reproduce

```
import sklearn
from scipy.sparse import csr_matrix
from sklearn.datasets import make_classification
from sklearn.semi_supervised import LabelPropagation

print(sklearn.__version__)

X, y = make_classification()
classifier = LabelPropagation(kernel='knn')
classifier.fit(X, y)
y_pred = classifier.predict(X)

X, y = make_classification()
classifier = LabelPropagation(kernel='knn')
classifier.fit(csr_matrix(X), y)
y_pred = classifier.predict(csr_matrix(X))
```

#### Expected Results

Sparse case should work as does the dense one.

#### Actual Results

```
0.22.2.post1
Traceback (most recent call last):
[...]
TypeError: A sparse matrix was passed, but dense data is required. Use X.toarray() to convert to a dense numpy array.
```

#### Fix

Changing 

```
        X, y = check_X_y(X, y)
```

in _label_propagation.py line 224 to 

```
        X, y = check_X_y(X, y, accept_sparse=['csc', 'csr', 'coo', 'dok',
                                              'bsr', 'lil', 'dia'])
```

seems to fix the problem for me (BTW: a similar check accepting sparse matrices is done in BaseLabelPropagations predict_proba at line 189). This fix also heals LabelSpreading.

Hints from issue discussion:
Just checked: the fix seems to work for kernel='rbf', too.
Hi, I would like to take over since this is stalled.
Hi @cozek , sure go ahead: FYI you can comment "take" in this issue and it will automatically assigned to you.

Commit message: fix changelog edit

Patch to review:
diff --git a/doc/whats_new/v0.24.rst b/doc/whats_new/v0.24.rst
index 84e712c05ea79..45919ea77ae2d 100644
--- a/doc/whats_new/v0.24.rst
+++ b/doc/whats_new/v0.24.rst
@@ -12,6 +12,12 @@ Version 0.24.2
 Changelog
 ---------
 
+:mod:`sklearn.semi_supervised`
+..............................
+
+- |Fix| :meth:`BaseLabelPropagation.fit` does not accept sparse matrix.
+  :pr:`19664` by :user:`Kaushik Amar Das <cozek>`.
+
 :mod:`sklearn.compose`
 ......................
 
diff --git a/sklearn/semi_supervised/_label_propagation.py b/sklearn/semi_supervised/_label_propagation.py
index 8ba99b9603e05..19ea0f9cd3849 100644
--- a/sklearn/semi_supervised/_label_propagation.py
+++ b/sklearn/semi_supervised/_label_propagation.py
@@ -226,7 +226,10 @@ def fit(self, X, y):
         -------
         self : object
         """
-        X, y = self._validate_data(X, y)
+        X, y = self._validate_data(
+            X, y, accept_sparse=['csc', 'csr',
+                                 'coo', 'dok', 'bsr', 'lil', 'dia'],
+            reset=True)
         self.X_ = X
         check_classification_targets(y)
 
diff --git a/sklearn/semi_supervised/tests/test_label_propagation.py b/sklearn/semi_supervised/tests/test_label_propagation.py
index 9f355281d9881..0fbe090165572 100644
--- a/sklearn/semi_supervised/tests/test_label_propagation.py
+++ b/sklearn/semi_supervised/tests/test_label_propagation.py
@@ -2,6 +2,7 @@
 
 import numpy as np
 import pytest
+import scipy.sparse as sp
 
 from scipy.sparse import issparse
 from sklearn.semi_supervised import _label_propagation as label_propagation
@@ -26,13 +27,27 @@
     }),
 ]
 
+ESTIMATOR_CLS = [label_propagation.LabelPropagation,
+                 label_propagation.LabelSpreading]
 
-def test_fit_transduction():
+
+PARAMETERS = [{'kernel': 'rbf'}, {'kernel': 'knn', 'n_neighbors': 2}, {
+        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
+    }]
+
+
+MATRIX_TYPES = (sp.csc_matrix, sp.csr_matrix, sp.coo_matrix, sp.dok_matrix,
+                sp.bsr_matrix, sp.lil_matrix, sp.dia_matrix, np.array)
+
+
+@pytest.mark.parametrize("matrix_type", MATRIX_TYPES)
+@pytest.mark.parametrize("estimator", ESTIMATOR_CLS)
+@pytest.mark.parametrize("parameters", PARAMETERS)
+def test_fit_transduction(matrix_type, estimator, parameters):
     samples = [[1., 0.], [0., 2.], [1., 3.]]
     labels = [0, 1, -1]
-    for estimator, parameters in ESTIMATORS:
-        clf = estimator(**parameters).fit(samples, labels)
-        assert clf.transduction_[2] == 1
+    clf = estimator(**parameters).fit(matrix_type(samples), labels)
+    assert clf.transduction_[2] == 1
 
 
 def test_distribution():
@@ -101,7 +116,7 @@ def test_label_propagation_closed_form():
     # adopting notation from Zhu et al 2002
     T_bar = clf._build_graph()
     Tuu = T_bar[tuple(np.meshgrid(unlabelled_idx, unlabelled_idx,
-                      indexing='ij'))]
+                                  indexing='ij'))]
     Tul = T_bar[tuple(np.meshgrid(unlabelled_idx, labelled_idx,
                                   indexing='ij'))]
     Y = Y[:, :-1]


Code review comments:
diff_hunk: @@ -12,6 +12,12 @@ Version 0.24.2
 Changelog
 ---------
 
+:mod:`sklearn.semi_supervised`
+..............................
+
+- |Fix| :meth:`BaseLabelPropagation.fit` does not accept sparse matrix.
+  :pr:`19664` by :user:`Kaushik Amar Das <cozek>`.
+
path: doc/whats_new/v0.24.rst
text: @user2:
As @user1 indicated, this has to be moved to `doc/whats_new/v1.0.rst`.
```suggestion
:mod:`sklearn.semi_supervised`
..............................

- |Fix| :meth:`BaseLabelPropagation.fit` now accepts sparse matrices.
  :pr:`19664` by :user:`Kaushik Amar Das <cozek>`.

```

diff_hunk: @@ -26,13 +27,27 @@
     }),
 ]
 
+ESTIMATOR_CLS = [label_propagation.LabelPropagation,
+                 label_propagation.LabelSpreading]
 
-def test_fit_transduction():
+
+PARAMETERS = [{'kernel': 'rbf'}, {'kernel': 'knn', 'n_neighbors': 2}, {
+        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
+    }]
+
+
+MATRIX_TYPES = (sp.csc_matrix, sp.csr_matrix, sp.coo_matrix, sp.dok_matrix,
+                sp.bsr_matrix, sp.lil_matrix, sp.dia_matrix, np.array)
path: sklearn/semi_supervised/tests/test_label_propagation.py
text: @user1:
I agree with your point and this setup: using test parametrization definitely would be better. :+1: 

You can proceed in two steps in different commits (at least two but not necessarily) to:
 - adapt the other tests to assert the correct behavior of `fit` on sparse matrices
 - if all the tests pass, adapt the test to use parametrisation as you started to do with `test_fit_transduction`
 
If we judge that it would be better having a dedicated PR for this second step, we can discard them here but cherry-pick them on another PR branch. :slightly_smiling_face: 

@author:
I did this due the reviewer comments in the stalled PR that this PR takes-over
https://github.com/scikit-learn/scikit-learn/pull/17384#discussion_r454514567

I agree that we should have a dedicated PR instead. I will revert these edits and only focus only on the main the tests/funcs.

diff_hunk: @@ -26,13 +27,27 @@
     }),
 ]
 
+ESTIMATOR_CLS = [label_propagation.LabelPropagation,
+                 label_propagation.LabelSpreading]
 
-def test_fit_transduction():
+
+PARAMETERS = [{'kernel': 'rbf'}, {'kernel': 'knn', 'n_neighbors': 2}, {
+        'kernel': lambda x, y: rbf_kernel(x, y, gamma=20)
+    }]
+
+
+MATRIX_TYPES = (sp.csc_matrix, sp.csr_matrix, sp.coo_matrix, sp.dok_matrix,
+                sp.bsr_matrix, sp.lil_matrix, sp.dia_matrix, np.array)
+
+
+@pytest.mark.parametrize("matrix_type", MATRIX_TYPES)
+@pytest.mark.parametrize("estimator", ESTIMATOR_CLS)
+@pytest.mark.parametrize("parameters", PARAMETERS)
+def test_fit_transduction(matrix_type, estimator, parameters):
     samples = [[1., 0.], [0., 2.], [1., 3.]]
     labels = [0, 1, -1]
-    for estimator, parameters in ESTIMATORS:
-        clf = estimator(**parameters).fit(samples, labels)
-        assert clf.transduction_[2] == 1
+    clf = estimator(**parameters).fit(matrix_type(samples), labels)
path: sklearn/semi_supervised/tests/test_label_propagation.py
text: @user1:
I can suggest on this patch, but it's easier to see the matrix type this way, I think.
```python 
    samples = matrix_type([[1., 0.], [0., 2.], [1., 3.]])
    labels = [0, 1, -1]
    clf = estimator(**parameters).fit(samples, labels)
```

diff_hunk: @@ -226,7 +226,10 @@ def fit(self, X, y):
         -------
         self : object
         """
-        X, y = self._validate_data(X, y)
+        X, y = self._validate_data(
+            X, y, accept_sparse=['csc', 'csr',
+                                 'coo', 'dok', 'bsr', 'lil', 'dia'],
+            reset=True)
path: sklearn/semi_supervised/_label_propagation.py
text: @user1:
```suggestion
        X, y = self._validate_data(
            X, y, accept_sparse=['csc', 'csr', 'coo', 'dok',
                                 'bsr', 'lil', 'dia'],
            reset=True)
```