Compute matrix exponential via spectral decomposition

[d-schindler]

This PR is to resolve #66

[d-schindler]

I've implemented a general structure for pre-computing the spectral decomposition and then using it for computing the matrix exponential. I also started to implement it for the continuous combinatorial constructor. When you are happy with this, it's easy to do this with the others.

First experiments are quite impressive. I ran the MS analysis with continuous combinatorial in Example_2 with both options:

• precomputing the constructors as usual took 53s

• precomputing the constructors using spectral decomposition took less than 1s

Although one can surely optimise the way I compute the (full) spectral decomposition, this seems to work very well, as @michaelschaub and @mauriciobarahona anticipated.

[d-schindler]

It would be good to apply the benchmarking to both options. @arnaudon , can you have a look at my code?

[d-schindler]

I think eigen decomposition in the directed case needs to be used with caution because we don't have the guarantee (as with symmetric graphs) that we obtain a diagonalisation but only a solution to a generalised eigen decomposition that might lead to large approximation errors in matrix exponential. Not completely sure about this. I added a warning.

[d-schindler]

In the benchmarking get_constructor_data seems also to speed up significantly (I only tested for SBM) but I can't produce the final figures because I get the following error: qt.qpa.plugin: Could not find the Qt platform plugin "wayland" in ""

@arnaudon , could you have a look at the benchmarking? - maybe we want to update the figure in the paper because it will look better if faster?

[d-schindler]

After installing qt6-wayland it still doesn't work, so I can't do the benchmarking atm. Could somebody else do it?

Also @peach-lucien mentioned that it would be good to do a benchmarking of Leiden, as well.

[arnaudon]

Ah sorry, I'm behind on that now, let me catch up this afternoon!

[d-schindler]

Great, thank you Alexis! The last two commits are just general improvements..

[d-schindler]

After a discussion with @mauriciobarahona, I removed the eigen decomposition option from the directed case because we might run into issues. We should think about the directed case separately in the future (not urgent).

[d-schindler]

I also set computation of exponential via eigen decomposition as a default because it seems much quicker. But this does only affect the combinatorial and normalised contructors (the others don't involve exp and directed is excluded for the moment, see above).

[d-schindler]

@arnaudon, let me know if I should do anything else for you to merge after

[d-schindler]

there was actually a bug in the timing that is fixed now, will produce the benchmarking plot now

[d-schindler]

I've finished the benchmarking and updated the figure in our paper. As expected, the matrix exponential computation implemented here improves things a lot.

[arnaudon]

Really cool @d-schindler ! Let me know if my small fix are ok, then I'll merge! coverage should still be at 100 (codecov is not yet up as I write, it's a bit slow for some reason)

[d-schindler]

Thanks for your improvements, looking good! A couple of remarks:

• Could we have spectral as the default for combinatorial and normalized constructors because it is much faster?
• I tried to include the plt.show() on purpose in plot_optimal_partitions(), and already in previous PRs where you removed it, because people want to see all the plots in the notebooks. And without plt.show() only the last plot is shown. E.g. here we see all optimal partitions which is nice: https://github.com/barahona-research-group/PyGenStability/blob/exponential/docs/source/examples/example.ipynb
• Some files like run_benchmark.py need to be updated with the new arguments; also the notebooks using combinatorial or normalized should specify spectral method if not default (because I updated them using spectral and the results would be different now)
• I forgot to run the notebook above with spectral, we should do it because it is quicker and more convincing for people, here: https://github.com/barahona-research-group/PyGenStability/blob/exponential/docs/source/examples/example.ipynb

[arnaudon]

so I put spectral by default, except for directed, updated all notebooks and added an option to plot the optimal partitions

[codecov-commenter]

Codecov Report

Merging #68 (99df1a1) into master (a280c9d) will not change coverage. The diff coverage is 100.00%.

:mega: This organization is not using Codecov’s GitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories. Learn more

@@            Coverage Diff            @@
##            master       #68   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            7         7           
  Lines          532       552   +20     
=========================================
+ Hits           532       552   +20     

Flag	Coverage Δ
pytest	100.00% <100.00%> (ø)

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
src/pygenstability/plotting.py	100.00% <ø> (ø)
src/pygenstability/constructors.py	100.00% <100.00%> (ø)
src/pygenstability/pygenstability.py	100.00% <100.00%> (ø)

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[d-schindler]

Looks great! I guess we are ready to merge now?