Why a special case in this common check? Once the remaining sign switch is fixed (the constant abs values case), SpectralEmbedding should be fully deterministic and there would be no need for a specific dataset in the checks, right?

Currently 2 things cause the o/p to be non-deterministic...

Major one is when the data produces an adjacency graph which is not fully connected. (But a warning is raised stating spectral embedding may not behave correctly since the adj. graph is not fully connected, so I am not quite sure if non-deterministic output is to be expected here)

Minor one is when there are multiple max abs values where the sign has to be arbitrarily given to the first index etc... (I'll fix this and push the commit soon...)

So yes if the 1st one is to be fixed then we should not special case the input... :)

Well but the first should also be deterministic! There is no reason that a non-connected graph gives non-deterministic results.

Okay! So I've (or I think I've) narrowed down the issue to a nearly singular graph laplacian when the graph is not fully connected...

• arpack's eigen solver seems to produce the non-deterministic eigen vectors when the laplacian matrix has a very low determinant... (order e-50) ( only "lobpcg" handles this perfectly producing deterministic output everytime... "amg" is not quite stable with nearly sigular matrices ( raises LinAlgError randomly ) Wrong observation both "lobpcg" and "amg" also tend to throw errors with nearly / fully singular matrices.)
• When this particular S_X, S_y is used the determinant of the laplacian is of the order e-20 which seems to be handled perfectly by "arpack", "lobpcg" as well as "amg" eigen_solvers.

Could you kindly confirm if my observations are true?

We could fix this by reverting to "lobpcg" when the determinant of laplacian is very low (but involves an additional determinant computation step).

(Also note that we currently fall back to "lobpcg" solver when arpack raises LigAlgErrorRuntimeError... which is when the laplacian is perfectly singular)

NOTE: I made a wrong observation that lobpcg handles singular matrices perfectly. Both "lobpcg" and "amg" also tend to throw errors with nearly / fully singular matrices ( I hadn't tested it for different random states back then )

What is the change in the result from the solver? Are the eigenvalues too close? And what is the behavior then?

arpack can take a v0 to seed the random vector. Unfortunately, passing a gaussian distributed v0 is not correct. The correct way to do it would be to replicate:

https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/ARPACK/SRC/dgetv0.f

That looks complicated though. I am no fortran developer myself.

thanks for the comments... This is just a minor confirmation that the arpacks eigsh does not raise RuntimeError but instead just gives out random values, which is the root cause of the the current issue at hand...

>>> N = np.array([[0,]*5]*5, dtype=float)
>>> print eigsh(N, k=1)
(array([ 0.]), array([[-0.32529456],
       [ 0.29618396],
       [ 0.794161  ],
       [-0.04909478],
       [-0.41636105]]))
>>> print eigsh(N, k=1)
(array([ 0.]), array([[-0.34134676],
       [-0.71507399],
       [ 0.00610712],
       [-0.58006083],
       [ 0.18879544]]))

Thanks for confirming @ragv. Let's try to make the common tests use the deterministic dense solver then.

Note: np.array([[0,]*5]*5, dtype=float) is better written np.zeros(shape=(5, 5), dtype=np.float64).

Note: np.array([[0,]*5]*5, dtype=float) is better written np.zeros(shape=(5, 5), dtype=np.float64) .

Ah thanks!! :)

Let's try to make the common tests use the deterministic dense solver then.

Do you mean to say that in the set_fast_parameters we could set eigen_solver to "lobpcg"?

lobpcg or dense depending on the models. I don't think the notation is consistent.

Why the double underscore?