Memory issue for large directed graphs

[MatteoSerafino]

Hello,
I'am trying to use the package on a big network (around 170000 nodes).
However, when I call the contractor:

defining the constructor externally

directed_constructor = constructors.load_constructor('directed', adjacency, alpha=0.85)

I get the following error:
Unable to allocate 241. GiB for an array with shape (179783, 179783) and data type float6

Is there a way to avoid it?

Moreover, could i give as input a weighted adj matrix?

Thanks a lot

[arnaudon]

Hello!
First, the positive answer: you can use weighted!
Second, the negative answer: we cannot use such big networks with markov stability, it requires computing matrix exponential, which is costly from CPU time and memory.

But, @d-schindler just implemented (#68) another variant for computing the matrix exponential with spectral decomposition. As it is done now, it will not work either, but we could try something with sparse matrices and only compute the largest eigenvalues to approximate the matrix exponential.
But, as I see you want to use directed, we're not quite sure yet how to make spectral base computation work with this constructor yet.

You really want to use matrix exponentials for such a large graph? Did you try 'simple' louvain our leiden with modularity? It will not be so easy to scale the code to such large networks, so we need to see if it is worth before jumping into coding this.

[MatteoSerafino]

Hello @arnaudon ,

Thanks a lot for your answer.
I see the problem with matrix exponentials.

I could try the simplest version of the model. Basically you are suggesting to use the default run option:

pygenstability.pygenstability.run(graph=None, constructor='linearized', min_scale=-2.0, max_scale=0.5, n_scale=20, log_scale=True, scales=None, n_tries=100, with_NVI=True, n_NVI=20, with_postprocessing=True, with_ttprime=True, with_spectral_gap=False, result_file='results.pkl', n_workers=4, tqdm_disable=False, with_optimal_scales=True, optimal_scales_kwargs=None, method='louvain')

Which use a linearized constructor and louvain method.
My question, however is:
Can I still consider directed and weighted networks?

I'am basically try to run the following command now:

all_results = run(adjacency, min_scale=-1, max_scale = 1, n_scale=20,n_workers=6)

Which i believe correspond to your suggestion.

[arnaudon]

I'm not expert in directed networks, so I'm not sure how modularity works in this case. For weights, it's perfectly ok. Probably there are some extensions/adaptaions of modularity for directed networks, we can implement one if you want to use it. Also, constructor='linearized' corresponds to modularity with a scaling factor in the null model.

[MatteoSerafino]

I understand.
I can set the constructor to linearized.
Also, setting the method to leiden speed up the process incredibly.

You use the genealied Modularity. So the only point is whether it also works for directed network or needs some modifications.

[juni-schindler]

Hello @MatteoSerafino, our current implementation of linearized Markov Stability is aimed for undirected graphs. It can be extended to directed graphs though and we will try and implement a "linearized directed" constructor ASAP.

[MatteoSerafino]

Hello @d-schindler,
Thanks for your asnwear.
That would be great.

[arnaudon]

@MatteoSerafino could you try the code dominik just implemented, to see if it does something reasonable for you?

[MatteoSerafino]

Hello @arnaudon,
I did test the code as follow:
all_results = run(adjacency, min_scale=-1, max_scale = 1, n_scale=30, method='leiden', n_workers=6, constructor='linearized_directed')

As graphs, I generated some modular directed graph with N nides, m modules and with p_in being the probability that nodes in the same module are connected, and p_out being the probability of connection between nodes of different modules.

I made different tests with different combinations of N, m, p_in and p_out and results seems reasonable.
These were just 'naive tests, and deeper checks should be made.

However, for large network still give an memory error, even with the linearized directed version.

The problem is here:

np.ones((n_nodes, n_nodes)) / n_nodes

[juni-schindler]

Ok, I see. If we use Google teleportation, we necessarily obtain a dense matrix and this leads to memory issues in large graphs. So probably we should turn off teleportation (i.e. set alpha=1) for linearized_directed.

[juni-schindler]

Could you try again now? I set alpha=1 as default. It means that the constructor only works for strongly connected graphs.

[MatteoSerafino]

@d-schindler ,

I got the latest version, where you also fixed the following:

out_degrees = self.graph.toarray().sum(axis=1).flatten()

Which was causing a memory error.

It seems is working fine. I will let it run as follows:

all_results = run(adjacency, min_scale=min_scale_, max_scale = max_scale_, n_scale=n_scale, method='leiden', result_file=pah, n_workers=6, constructor='linearized_directed')

and see it reaches the end.

[juni-schindler]

Hello @MatteoSerafino,

great to hear it's running now. Yes, I had to use scipy.sparse consistently to make it work.

It would be great if you could let us know whether it works fine, once the run is complete.