Generating and rendering extremely large graphs

Question

I'm interested in generating and rendering extremely large graphs, i.e., ones having $10^6 \to 10^8$ vertices. (These graphs will ultimately be rendered in PDF or PNG and printed on large, poster-sized paper.) Although the code may work for small graphs, there are inevitably limitations for large graphs due to computer memory (especially when embedding or laying-out the graph, as we'll see).

Consider the small graph generated by the Collatz conjecture with 400000 nodes (see code below, based on the cited problem):

where the GraphLayout -> {"PackingLayout" -> "ClosestPacking"}. This can be computed directly on a Mac laptop. But for larger numbers of vertices, the graph cannot be rendered.

Note especially that this is just a representative graph... I need a solution for many different large graphs, ones without simple geometric structure.

The problem arises when one wants to generate and lay out (or "embed") $10^7$ vertices. The problem is not so much the computation of the vertices and edges (which can be done by writing to a large external file), but instead laying out the graph. The Layout nominally needs all the vertexes in active memory in order to perform the layout, and that is impossible on most machines.

[I've closed all other applications to provide Mathematica with the maximum memory, but even this is not enough for the large graphs I wish to render. Perhaps this entire problem is solved by moving the enormous computation to the Wolfram Cloud... and if this is the case, I guess I'll merely purchase an account and run my code there. But I'm hoping there is a better way... one that can be used on laptops and desktop machines (with large hard memories).]

One might try to layout portions of the overall graph and then "glue" them together, but the local optimization of layout of each portion is likely not appropriate for the full graph: Different branches will ultimately overlap, breaking the rule of the global optimization routine.

My idea is to generate the enormous graph $G$ (but not lay it out). Then select some small random subset of the vertexes, $V_1$, say 1% of those in $G$, to form a smaller, representative graph $G_1$ where the edges in $G_1$ are estimates of the "distance" between each vertex based on their step separation in $G$. Then, layout this representative $G_1$ (which should be no problem because it is small). Then, anchor the vertexes of $G_1$ in place in the final layout and then render all the vertexes of $G$. In this way, the full, final graph $G$ is rendered appropriately, and the memory constraints are not exceeded.

Perhaps there is a way to extract VertexCoordinates and iteratively layout vertices in regions, hopping through the overall graph. (This seems extremely inefficient.)

Or use smart memory management... or another technique.

---

CollatzSequence[list_] := 
  Module[{memory, tmp, chain, result = Internal`Bag[]},
   memory[1] = False;
   memory[n_] := (memory[n] = False; True);
   Do[chain = Internal`Bag[];
    tmp = l;
    While[memory[tmp], Internal`StuffBag[chain, tmp];
     tmp = If[EvenQ[tmp], tmp/2, 3 tmp + 1];];
    Internal`StuffBag[chain, tmp];
    Internal`StuffBag[result, chain], {l, list}];
   Internal`BagPart[#, All] & /@ Internal`BagPart[result, All]];

myCollatzGraph = Rasterize[
   Graph[Flatten[(Rule @@@ Partition[#, 2, 1]) & /@ 
      CollatzSequence[Range[400000]]],
    GraphLayout -> {"PackingLayout" -> "ClosestPacking"},
    VertexStyle -> Opacity[0.2, RGBColor[.9, .1, .1]],
    EdgeStyle -> RGBColor[.1, .1, .9],
    ImageSize -> 2000],
   ImageResolution -> 72];

Answer 1

I suggest not to use Graph to render, as it is slow. Instead, compute the vertex coordinates, then render manually.

The rough steps are as follows:

Create an "index graph", i.e. a graph where the vertex names coincide with the vertex indices:

n = 10000;
g = IndexGraph@Graph[
    Flatten[(Rule @@@ Partition[#, 2, 1]) & /@ 
      CollatzSequence@Range[n]]
    ];

Compute the vertex coordinates:

coord = GraphEmbedding[g, "SpringElectricalEmbedding"];

This is going to be the most expensive step (computationally), but it will likely not take too much memory. Here, you will need to experiment to find a layout that produces a good enough result and finishes in time. "SpringElectricalLayout" will be slow, but it has many sub-options which can be used to find a good compromise between computation time and layout quality. I would start experimenting with Tolerance and MaxIteration.

Finally, render the graphics:

Image@Graphics@GraphicsComplex[coord, Line[List @@@ EdgeList[g]]]

Be sure to use GraphicsComplex and merge all lines and all points into a single Line and Point expression. Finally, we rasterize the result so the front end does not need to keep the vector graphics representation in memory.

---

Example:

n = 400000;
g = IndexGraph@Graph[
    Flatten[(Rule @@@ Partition[#, 2, 1]) & /@ 
      CollatzSequence@Range[n]]
    ];

VertexCount[g]
(* 869322 *)

coord = GraphEmbedding[
    g, {"SpringElectricalEmbedding", "Tolerance" -> 1, 
     "MaxIteration" -> 5}]; // AbsoluteTiming
(* {48.8368, Null} *)

Image@Graphics@GraphicsComplex[coord, Line[List @@@ EdgeList[g]]]

Image@Graphics[{GraphicsComplex[
    coord, {Line[List @@@ EdgeList[g]], Red, AbsolutePointSize[1], 
     Point[coord]}]}, ImageSize -> 1000]

The 32-bit macOS front end with absolutely not run out of memory while rendering graphics of this size, if specified efficiently, as here.

The bottleneck is the computation of coordinates, where you need to find a good compromise between computation time and output quality. This example took just under a minute on my machine. The time would likely stay under 5 minutes if MaxIteration is increased 5-fold (along with a reduction of Tolerance, which also put a limit on how many steps are computed).

---

Note:

I notice you used GraphLayout -> {"PackingLayout" -> "ClosestPacking"}. This makes no sense for a connected graph like this. The PackingLayout controls how connected components are assembled after each one has been laid out. This is a connected graph. It has only one component.