Hi,
I try to create a very large graph using random_graph function. My computer
has 128 GB physical memory and 16 GB swap partition. When I try to create a
graph with 50 million for number of vertices, and 80 for both numbers of
incoming and outgoing edges, it consumes all memory space and then crashes.
Do you have any idea how I can overcome the memory limit? Is there any way
to make random_graph function more memory efficient?
Thanks,
Arash
Try to pass the option "random=False". In this case the edges will not
be randomized, but it may need less memory. If it fits your memory, then
you may do random_rewire() with the option strat="erdos", if you don't
have any prescribed degree sequence. This should need less memory, since
a list of the edges does not need to be built internally.
But note that you are dealing with a very large graph indeed, with 4
billion edges. If you use two 64 bit integers to specify an edge, this
already amounts to 80 * 50 * 1e6 * 64 * 2 / (8 * 1024 ** 3) ~ 60 GB.
Since the edge indexes are also needed, this is increased by another 30
GB. Thus, simply the storage of such a thing would require at least 90
GB, but probably even more. If some temporary data structure has a size
O(E), it will cross over your 128 GB limit pretty easily.
The use could be halved by using 32 bit integers instead, but the
library would need to be modified.
But I can't help but wonder if you really need a random graph this
large...
Cheers,
Tiago
Hi Tiago,
Thanks for your useful hints. I do research on distributed algorithms for
subgraph pattern matching on very large datasets; that is way I need such a
large graph for performance measurements.
Before trying your suggestions, I added a very large swap file to the
system. Now, GraphTool has been running for more than 5 hours. Initially,
it was keeping increasing memory usage and its CPU usage was low, but now
the memory usage has become stable (about 125 GB on physical memory and 55
GB on swap) and the average CPU usage is decently high. I hope that the
process will finish in the next few hours; otherwise, I will try your
suggestions.
I wonder if you now any other tool which might be more efficient for
creating very large graphs?
I appreciate your help.
Arash
attachment.html (3.33 KB)
imho build it in C. so use the boost graph libraries natively?. ..... the
graphs your talking about are big enough i don't think libraries are going
to make such a difference considering the memory usage is from the graph
itself rather than any internal structures iirc.... @Tiago? You might want
to try memory mapping since your graph is big enough to not fit in ram. or
have part of it memory mapped ...
attachment.html (4.45 KB)
I don't know about imho! My python task is not yet finished after 11 hours.
I forgot to mention that we halved the number of incoming and outgoing
edges. Actually, we have defined a function which returns a pair of random
integers between 0 and 80 for incoming and outgoing edges, so we expect the
average degree of vertices to be 80.
Monitoring the processes on our system using top, I can see that all RAM
and 80GB on swap is used, and the python program has CPU usage usually
higher than 90%. So, it seems that perhaps the memory is not the main issue
on run time at this moment. I am not sure how much the 2 randint(0,80)
functions we have called for the number of edges are responsible in this
CPU load!
Thanks for your advice,
Arash
attachment.html (5.89 KB)
I don't know about imho! My python task is not yet finished after 11
hours. I forgot to mention that we halved the number of incoming and
outgoing edges. Actually, we have defined a function which returns a
pair of random integers between 0 and 80 for incoming and outgoing
edges, so we expect the average degree of vertices to be 80.
Don't you mean 40?
Monitoring the processes on our system using top, I can see that all
RAM and 80GB on swap is used, and the python program has CPU usage
usually higher than 90%. So, it seems that perhaps the memory is not
the main issue on run time at this moment. I am not sure how much the
2 randint(0,80) functions we have called for the number of edges are
responsible in this CPU load!
If the memory usage has stabilized, then it's possible the graph has
been created, and it is being randomly rewired, so the randint() should
no longer be called.
You should not expect any sort of decent performance if you are using
swap. I guess the best approach for you is either to work with smaller
graphs, or if you can't do that you have to implement your own data
structure which uses less memory. You can use the Boost Graph Library
itself, which has some different graph implementations, and allows you
to create your own. If you are not generating graphs, but reading them
from dist, a very compact representation is the compressed sparse row
format:
Compressed Sparse Row Graph - 1.52.0
You may also look at the web graph people, since they are used to
working with huge graphs:
Cheers,
Tiago
Just a suggestion: I tested webgraph for my purposes after meeting one of
the developers, and I can say that the memory usage is quite amazing (in a
good sense: very low).
However, at least 1 year ago, webgraph was unfit for dynamic graphs, so if
you plan to remove nodes and so on, I don't think it's the best choice.
Giuseppe
2013/2/2 Tiago de Paula Peixoto <tiago(a)skewed.de>
attachment.html (3.2 KB)
The same is true for the compressed sparse row (CSR) graph in BGL. The
graph is essentially immutable.
I've planned to include optional CSR support in graph-tool, but I haven't
found the time yet to do so.
However, things can be improved somewhat easily in graph-tool by a
factor 2 by using 32 bit integers, instead of 64 bits. I'll keep this in
mind for future releases.
Cheers,
Tiago
Thank you all for the information. My python process is still running after
about 17 hours!
@Tiago: I have randint(0,80) separately for incoming and outgoing edges;
hence, I expect average degree of 80 (incoming + outgoing) for vertices.
attachment.html (1.86 KB)
I've modified the internal representation of graph-tool, such that now
less memory is used to represent a graph. I simply dumped boost's
adjacency_list with a light-weight custom made implementation. In my
tests I get a factor of 2 improvement (!). You can try with the current
git version to see if it helps in your case.
Cheers,
Tiago