Module bisect 

Numbering a graph by recursive bisection, which is where the bits are.

csr says it plainly: on soc-LiveJournal1 the encoder is 1.18 bits over the entropy of the gaps it is given, so nothing left in the code is worth having. What is left is in the numbering. A gap between two neighbours is the distance between two node ids, and node ids are ours to choose, so the question is which numbering makes the neighbours of a node land next to each other. order_by_degree answers it with one sort and gets 0.73 bits on that graph. This answers it properly.

What this is

Recursive graph bisection, from Dhulipala, Kabiljo, Karrer, Ottaviano and Pupyrev, “Compressing Graphs and Indexes with Recursive Graph Bisection”, KDD 2016. The graph is read as a bipartite one: every node is a document to be numbered, and the lists it appears in are its terms. Split the documents in half, then repeatedly swap documents between the halves whenever the swap lowers a cost function that stands in for the size of the compressed output, then recurse into each half. The order the documents end up in is the numbering.

The cost of one term split across two halves of sizes n1 and n2, holding d1 and d2 of that term’s occurrences, is

d1 * log2(n1 / (d1 + 1)) + d2 * log2(n2 / (d2 + 1))

which is the paper’s, and is what a list of d ids drawn out of a range of n costs under a log gap code. Minimising the sum of that over every term is minimising an estimate of the whole encoded size, and the estimate is good enough that the real number moves with it.

What it is worth

On the two public graphs, bits an edge through the cold form, against the ids as they arrive and against order_by_degree:

                   as they came   degree ordered   bisected
soc-LiveJournal1          17.99            19.00      15.00
web-Google                23.19            20.21      15.04

Twelve minutes on eight cores of server3 for the LiveJournal one, which is sixty nine million edges, and eight seconds for web-Google.

On R-MAT it wins nothing, 9.72 against degree ordering’s 9.38, and that is the useful control rather than a disappointment. R-MAT’s structure is its hubs: every list contains some of the same few thousand nodes, and giving those the small ids is already close to the best numbering there is. A graph with real communities has a different structure and this finds it. The test below builds one out of sixty four groups of sixty four nodes, all of the same degree so that degree ordering has nothing to sort on, and shuffles the ids so nothing but the edges says where the groups are: 12.34 bits an edge as they came, 12.33 degree ordered, 9.21 bisected.

Why this and not layered label propagation

LLP is what WebGraph uses and it is what the note in csr.rs said was coming. It is not here, and the reason is that the paper above is newer than it, beats it on exactly the kind of graph we are stuck on, and is simpler to be sure of. LLP runs label propagation at a sweep of resolution parameters and keeps the clustering that codes best, so it has a parameter list, a random restart and a quality criterion. Bisection has a leaf size and an iteration cap, its objective is written down above, and every swap it makes lowers that objective by an amount it can print. Facebook reported it beating LLP on social graphs and being several times quicker; the later work on it (Mackenzie and others, 2019 through 2021) is about faster convergence rather than about a better objective, and Zuckerli, which is the strongest published result on these graphs, keeps this ordering and improves the code that runs after it.

What it is not

It is not fast. It is O(m log n) with an iteration count on the front of it, and on a graph with seventy million edges it is minutes rather than the second order_by_degree takes. That is the trade the cold form is for: numbering happens once when a graph settles and the encoded bytes are then read forever.

It is not a clustering. The output is an order and nothing else. Two nodes ending up adjacent means the encoder charges less for the pair, not that anything here believes they are related.

It is not adaptive. A graph that has changed since it was numbered stays numbered the way it was, and the new edges go into the hot form. Renumbering is a rebuild.

Structs

Tuning

The knobs, all three of them.

Functions

order

Number the nodes by recursive bisection, with the defaults.

order_with

The same with the knobs exposed.

shuffled

A numbering that is worth nothing, for the control the tests need.