A graph of two billion edges will not fit on one machine and the algorithm needs neighbours. How do you partition it?

Short answer

Before distributing a two-billion-edge graph, calculate the raw size because edge pairs may fit on one large machine. If it must be distributed, partition edges and replicate vertices rather than assigning all edges of a high-degree vertex to one machine. Power-law hubs make vertex partitioning skewed, and in bulk-synchronous graph jobs the slowest partition controls every superstep.

Two billion edges is smaller than it sounds

Do the multiplication before accepting the premise, because the premise is often wrong and an interviewer may well have put it there on purpose.

An edge is a pair of vertex identifiers. Two billion of them at 8 bytes each is 32 GB of raw edge data. Add a compressed adjacency structure and per-vertex state and you are somewhere between 40 and 60 GB depending on the algorithm. A single machine with 128 GB of memory holds that, and a purpose-built single-node graph library will run PageRank or a breadth-first search over it faster than any distributed cluster, because no message crosses a network at all.

That is worth saying first, and saying it confidently. Distributing a graph is expensive in a way distributing a table is not, so the bar for choosing to do it should be high. If vertex identifiers can be renumbered into 4-byte integers, the edge set is 16 GB and the argument gets stronger.

The cases where distribution is genuinely forced are worth naming so the rest of the answer has a footing: the graph is a tenth of a trillion edges rather than two billion, or per-vertex state is large enough to dominate the edges, or the graph already lives partitioned across a cluster and moving it would cost more than processing it in place. Take that last case as the premise for the rest of this.

Cutting vertices versus cutting edges

There are two ways to split a graph across machines and they fail differently.

An edge cut partitions the vertices. Each vertex lives on exactly one machine along with its state. An edge whose endpoints land on different machines has to be communicated every time the algorithm passes information along it. So the quantity you are minimising is the number of edges that cross a boundary.

A vertex cut partitions the edges. Each edge lives on exactly one machine. A vertex is replicated to every machine holding one of its edges, and its state must be reconciled across those replicas after each round. So the quantity you are minimising is the replication factor of vertices.

Neither is generically better. Which one wins is decided by the degree distribution of your graph, and that is the analytical step being tested.

Power-law degree is why the answer is edges

Real graphs are not uniform. Social graphs, web graphs, citation graphs and transaction graphs all have a small number of vertices holding an enormous share of the edges, and this changes the arithmetic completely.

Suppose one vertex in your two billion edges has 50 million of them. Under an edge cut, that vertex sits on one machine, and every message along any of its 50 million edges is handled by that one machine. It alone processes 2.5 per cent of all edge traffic in the graph. With 16 machines, an even split would be 6.25 per cent each, so this looks survivable until you notice it is one vertex out of hundreds of millions, and the next dozen hubs behave the same way. Their machines become stragglers, and the rest of the cluster waits.

Under a vertex cut, those 50 million edges are distributed across all 16 machines, so no machine carries the hub's traffic alone. What you pay instead is that the hub vertex is replicated on all 16 and its state must be combined across them each round. Combining one vertex's state 16 ways is cheap. Serialising 50 million edges through one machine is not.

That asymmetry is why edge-partitioning is the default in graph engines built for real-world graphs, and why GraphX partitions the edge set and replicates vertices rather than the reverse. State the reasoning rather than the conclusion, because the conclusion without the degree distribution behind it is a memorised fact.

The barrier is what makes skew fatal

The computation model matters here, because it explains why an imbalance is worse than its size suggests.

Bulk-synchronous processing runs in supersteps. In each one, active vertices receive the messages sent to them last round, update their own state, and send messages for the next round. Then everything stops at a barrier until every partition has finished, and the next superstep begins.

The barrier means the duration of each superstep is the duration of the slowest partition, not the average. So a partition doing three times the work of its peers does not make the job 10 per cent slower, it makes every superstep three times longer, and an algorithm running 30 supersteps pays that penalty 30 times. Balance is therefore not a tidiness concern; it is the dominant term.

It also tells you what to measure when a distributed graph job is slow: per-partition edge counts and per-superstep durations by partition, not total runtime. A histogram of edges per partition with a long right tail is the whole diagnosis.

Bounding how far a hub spreads

A random or hash-based edge partitioner distributes edges evenly, which fixes the straggler problem and maximises replication. A high-degree vertex ends up on close to every machine.

The refinement worth knowing is two-dimensional partitioning. Arrange the machines conceptually as a square grid and place an edge according to the grid cell given by hashing its source for one axis and its destination for the other. Because a given vertex only ever appears in one row and one column of that grid, the number of machines it can be replicated to is bounded, and GraphX documents that bound for its two-dimensional partitioner as 2 * sqrt(numParts) - 1.

Put numbers on what that buys. With 16 partitions, any single vertex touches at most 2 × 4 − 1 = 7 machines rather than all 16. With 100 partitions, at most 19 rather than 100. The bound tightens relative to cluster size as the cluster grows, which is exactly the direction you want, and it holds regardless of degree - a hub with 50 million edges is subject to the same bound as a vertex with three.

Locality-aware partitioning beats all of this when it is available. If your graph has community structure and you can place communities together, most edges stay local and the message volume collapses. The circularity is that finding communities is itself a graph algorithm over the graph you have not partitioned yet. The practical escapes are to compute a partitioning once from a sample and reuse it across many jobs, or to use structure you already know from outside the graph - geography, tenant, time bucket - as a partition key that correlates with connectivity without being derived from it.

What to try before partitioning cleverly

The best answer to a graph that will not fit is often a smaller graph, and the options are worth having ready.

Many questions do not need every edge. Dropping edges below a weight threshold, collapsing degree-one vertices into their neighbour, deduplicating parallel edges, or restricting to a time window can cut an edge set by an order of magnitude while leaving the answer you wanted intact. Whether that is legitimate depends on the algorithm. It is fine for a ranking and wrong for a reachability guarantee, so name the algorithm before you name the reduction.

And some algorithms do not need a distributed traversal at all. A shortest path between two named vertices is a bidirectional search touching a tiny fraction of the graph, and running it as 30 synchronous supersteps over two billion edges is a serious mistake in engine selection. Whole-graph algorithms like PageRank or connected components need the whole graph; point queries do not.

Compute the raw size before agreeing that the graph must be distributed, because 32 GB fits on one machine and beats any cluster. If it must be split, cut the edges rather than the vertices, because a power-law hub under an edge cut becomes the straggler that every barrier waits for.

---

© 2026 Preptima. Originally published at preptima.com.