Social network analysis often comes down to having to investigate through a great number of connected groups very quickly. We see this with users working on looming court cases, social media emergencies, and active crime & intelligence investigations. The clever group-in-a-box layout algorithm popularized by NodeXL is a great way to systematically work through this kind of analysis. The original algorithm had one issue preventing Graphistry users with big graphs from considering it… until now: it was designed to handle graphs with hundreds of nodes, and would take hours or even crash on bigger graphs.
We are happy to share the latest open source pygraphistry release (v0.34.17) runs group-in-a-box in seconds even on graphs with millions of edges.
To give a sense, in a project with a top law firm, the software they normally used could not perform the layout even after hours of computing. While their existing tools were tolerably slow on a sample of a single day’s worth of data, they need tools that handle their months and years of data. They can now use their favorite group-in-a-box layout in seconds. That’s a big boost to analyst flows and unblocks many use cases.
The what and why of group-in-a-box
The video below shows running group-in-a-box layout on 45,000 bitcoin transactions related to the old Silk Road DEA bust.
Even though not a social media dataset, the scenario is a great example of where group-in-a-box layouts shine. Financial investigators often face many transactions from many interacting entities that they must trace through. With group-in-a-box, they gain a structured way to visually and systematically work through clusters of connected transactions.
Group-in-a-box uses several algorithms. They are useful for understanding both in terms of the work they automate for analysts, and in the next section, what we had to optimize:
- Finds groups in the graph using community detection
- Places each group into an grid cell (box) ordered via a treemap
- Lays out the nodes in each group with a graph layout algorithm
The result is analysts can systematically examine their target groups (e.g., wallets), identify the inflows and outflows to neighboring groups of interest, and then drill in to any individual group. As the groups use independent layouts, they are optimized for independent viewing that is not disrupted by nodes in nearby clusters. In the video, note how it is easy to zoom in and zoom out from the group-level to the node-level as different levels of detail come up.
Good things come in threes: Optimizing group-in-a-box with GPU algorithms
To understand why we GPU accelerated group-in-a-box, consider our bitcoin graph example that has 28,832 nodes. That is 50X+ bigger than the graphs the original group-in-a-box paper described handling in a timely manner. It is not even a big graph — our latest group-in-a-box project is 100X+ bigger than the bitcoin one. Software that runs for hours and crashes is a non-starter for rapid data-intensive investigation iterations, which is the kind of scenario we build Graphistry to solve.
We applied three basic methods to make group-in-a-box reach the interactive speeds needed to unblock analysis:
Native algorithms: The first thing we do is use optimized native algorithms for each step. In CPU mode, we default to calling igraph‘s Louvain algorithm for community detection, which is a favorite in social media analysis, and Fruchterman-Reingold for graph layout. In GPU mode, we use cugraph‘s ecg, which is a more robust community detector, and ForceAtlas2 for layout, which is an accelerated implementation of the best-looking layout algorithms popularized by Gephi. (The Graphistry server uses our alternate GPU implementation of FA2 geared for more live scenarios and with more layout flexibility, but that is unnecessary here.) The result is both CPU and GPU mode are fast on graphs with < 100,000 edges. If the graph was a single group of that size, GPU FA2 would be sub-second.
Vectorization: As a rule, we implement all pygraphistry glue operations as columnar dataframe operations. Think steps like finding bounding boxes. Data analysis and visualization pipelines spend considerable time in seemingly innocuous tasks like data preparation, and achieving subsecond performance requires we take care on there. Columnar analytics makes PyGraphistry fast on CPUs, similar to why Clickhouse and Spark are some of the fastest SQL processors. Even better, we also make sure the columnar operations run in GPU mode when GPUs are available, so we can also saturate the 10,000+ parallel threads of a modern GPU when available.
Bulk layout of groups: The recent customer issue that sent us down this entire adventure was ultimately here. Their 5M+ edges partitioned into 50K+ groups, and even if one GPU layout call is fast, doing 50K+ individual GPU calls from Python took 20 minutes. Worse, many of the groups were small, so each GPU layout call was not doing all that much. We figured out how to instead do one big layout call — see the next section — and reduced the 20 minutes to 26 seconds for all three steps combined.
Processing 50,000 group layouts as just one
Our customer’s graph posed a challenge we had not seen in past group-in-a-box layouts: 50,000 groups of all sizes triggered 50,000 layout calls. Running these layouts individually on the CPU was slow due to scheduling and data transfer overhead. Worse, on a GPU, processing them one at a time uses an embarrassingly small portion of its capacity.
The obvious solution might seem to run 50,000 separate GPU tasks in parallel, one for each group. Consider a low-tier server GPU like the NVIDIA T4—available for around $0.25/hr on AWS, Azure, and GCP — that has 2,560 CUDA cores that can schedule 81,920 threads. However, GPUs are optimized for simple parallel instructions on large arrays, not for handling many tiny independent tasks. It needs the threads to run in coordinated blocks of 32. The GPU FA2 algorithm does exactly this kind of optimization… if the graph is not small.
Our ‘aha!’ was that since each group is independent in a group-in-a-box layout, we could treat all the groups as one big single, disconnected graph. By simply removing cross-group edges, we achieve one large graph composed of multiple disconnected components. We can now send a single massive layout task to the GPU that avoids small task overheads and more easily achieves GPU saturation. Sidenote: Focusing just on the ability to improve per-group layout quality in a big graph, we use a weighted variant of this technique in our modularity weighted layout, which helps for the organic non-grid case.
Attention to detail matters. Notably, standard layout algorithms put a strong gravity well in the center of the screen to prevent nodes from drifting too far out. In big graphs, this causes the disconnected groups to come together, collide, and then interfere with each other enough to distort their shapes. On its own, it looks like a masterfully packed organic molecule, but when the groups are rearranged in the grid, each group looks bizarre. To resolve this, we disabled the gravity settings. This allowed each group to repel others naturally until they stabilized without mutual interference, effectively achieving independent layouts within a single computation.
This optimization dramatically improved performance in both the CPU and GPU cases. The GPU case is especially dramatic. Even better, the speed gains enabled us to employ more sophisticated and computationally expensive algorithms like ForceAtlas2, so the result layout is both faster and better looking.
Screenshot: Algorithm – Regular graph layout where groups interact
Screenshot: Algorithm – Proper per-group layouts by ignoring cross-group edges. Note blue same-group edges are localized.
Screenshot: Group-in-a-box layout (GPU: ecg, fa2)
Show me the code
You can enrich your graph with a group-in-a-box layout in just one line:
# pip install graphistry
import graphistry
import pandas as pd
e_df = pd.read_csv('https://raw.githubusercontent.com/graphistry/pygraphistry/refs/heads/master/demos/data/transactions.csv')
assert 'Source' in e_df.columns and 'Destination' in e_df.columns
g1 = graphistry.edges(e_df, 'Source', 'Destination')
#Works on any graph
g2 = g1.group_in_a_box_layout()
assert isinstance(g2._nodes, pd.DataFrame)
assert 'x' in g2._nodes.columns and 'y' in g2._nodes.columns
g2.plot()With just a bit more, you can run it on a GPU by moving your CPU Pandas dataframe to the GPU as a cuDF one, and letting pygraphsitry’s automatic GPU acceleration kick in:
#Automatic GPU-accelerated mode
g1_gpu = g1.to_cudf()
g2_gpu = g1_gpu.group_in_a_box_layout()
g2_gpu.plot()For the bitcoin example, you can explore for yourself the generated interactive Graphistry session using the ForceAtlas2 layout vs the group-in-a-box layout. Try to identify the different relationships and workflows the different layouts make easier to investigate on graphs with many groups.
Next steps
For more information, check out the Jupyter notebook tutorial and try it out on your own data with your own Graphistry account or server!
Notes from the trenches, monthly.
Graph analytics, GPU viz, and the occasional war story. No spam.
Thanks — we'll be in touch.