_graph_is_connected consumes too much memory

[rudimeier]

Hi,

_graph_is_connected from sklearn.manifold.spectral_embedding_ consumes about 5 times as much memory as the input matrix. Could this be improved?

networkx.is_connected does not need any addional memory, maybe you may have a look at how they do it
https://networkx.github.io/documentation/latest/_modules/networkx/algorithms/components/connected.html#is_connected

(I haven't yet carefully checked if networkx.is_conneted does the same like sklearn!)

[jakevdp]

Did you observe this for a sparse input, or a dense input? The two lead to completely different code paths.

[rudimeier]

I've observed this only for the dense case.

[jakevdp]

I believe this is the offending line:

_, node_to_add = np.where(graph[connected_components_matrix] != 0)

It allocates ~4 temporary arrays which are on the same order as the size of the input.
It's one of the hazards of using NumPy, unfortunately: the fast & terse way to do vectorized computations often obtains speed at the expense of memory use.

[amueller]

The scipy stuff all works only on sparse matrices, right? A cython version for checking whether a dense matrix is connected is probably pretty short. Is it worth it?

@rudimeier is this really the bottleneck? How large is your matrix? I would imagine that even if we improve this particular part, there are other parts that will take more memory.

[AlexandreAbraham]

I'm working on it.