A bound right for the wrong reason

Two parameters are not enough either counted triangles on two graphs with the same number of vertices and the same number of edges, and found that enumerating every pair of every vertex’s neighbours cost 18,480 examinations on one and 42,076 on the other. The difference was the second moment of the degree distribution, which no bound written in $V$ and $E$ can see. The repair it measured is the standard one: point every edge from its lower-degree endpoint to its higher-degree one, and enumerate only pairs of out-neighbours. That cut the work to 4,090 and 3,339.

To explain why the repair works, the essay introduced a third parameter, the degeneracy $d$: the largest number such that every subgraph has a vertex of degree at most $d$. And it gave the reason the degeneracy was the right parameter in one sentence — that the degree orientation bounds every vertex’s out-degree by $d$, so no vertex examines more than $\binom{d}{2}$ pairs and the work is $O(E \cdot d)$.

That sentence is false for the orientation it was about. The conclusion is true. This page measures both halves, explains why the bound holds anyway, and measures the orientation that does have the property the sentence described.

The pairs examined are this field’s counted unit for the enumeration — counting on a graph set up the primitives, an adjacency scanned and a relaxation tried, and the triangle count charges one relaxation per pair of out-neighbours tested — so every number below is a count of the same operation the earlier essay counted, on the same two generators, at the same seeds.

The out-degrees, counted #

On every one of the six graphs the orientation by degree gives some vertex more out-neighbours than the degeneracy — by one on the sparsest preferential-attachment graph, by four on the preferential-attachment graph at degree six, which is one of the two graphs the earlier essay drew. On the uniform graph at degree six, 136 of the 1,024 vertices have more out-neighbours than the degeneracy permits under the claimed bound.

The excess is not an artefact of one generator or one density. It appears at every average degree drawn on both generators, it is largest in absolute terms on the densest uniform graph, where the largest out-degree reaches ten against a degeneracy of seven, and it is smallest where degree and arrival order nearly coincide. A reader who took the one-sentence argument at its word would expect every one of these six bars to stop at its dashed line.

The second bar in each row is an orientation built differently, and it never crosses the line. It is the subject of the second half of this page.

Why ordering by degree does not bound out-degrees #

The degeneracy is computed by repeatedly deleting a vertex of minimum degree in what remains of the graph, and recording the largest degree any vertex has at the moment it is deleted. So a graph of degeneracy four always contains a vertex of degree at most four, and after deleting it, another, and so on. The bound is a statement about that deletion sequence, and every degree in it is a degree in a shrinking graph.

Ordering by degree uses the degrees in the whole graph, once, and that is a different sequence. A vertex’s out-neighbours under it are its neighbours of higher degree. Nothing stops a vertex of degree seven from having all seven of its neighbours at degree eight or more, and in a random graph at average degree six there are many such vertices — degree seven is above average, and a neighbour chosen by following an edge is more likely than a random vertex to have a high degree, because high-degree vertices are at the end of more edges. That vertex has out-degree seven, and the degeneracy is four.

That effect has a name in network science — a random neighbour’s degree is on average larger than a random vertex’s — and it is the same bias on average is not a number warns about in any mean: which vertices are being averaged over decides the answer. Averaged over vertices, a degree is six; averaged over the ends of edges, it is higher, and the out-degree under the degree order is a count of neighbours on the high side of that second average.

A small example makes the gap unmistakable. A tree has degeneracy one: delete a leaf, and what remains is a tree. Take a tree in which one vertex has three neighbours and each of those has three further neighbours. The central vertex has degree three and its three neighbours have degree four, so ordering by degree points all three of the centre’s edges outward: out-degree three, in a graph whose degeneracy is one.

What the out-degrees look like #

On the preferential-attachment graph the orientation by degree is nearly a good one. Most vertices sit at three, the number of edges each new vertex brings when the graph is grown, and only 22 are above four. The degeneracy order is almost a picture of the construction: 1,005 of the 1,024 vertices have exactly three out-neighbours, because deleting vertices in minimum-degree order is very nearly un-growing the graph, removing the latest arrivals first.

The uniform graph is where the degree order is furthest from its reputation. Its degrees are all close to the mean, so ordering by degree separates vertices by small, almost arbitrary differences, and a vertex’s out-degree is roughly how many of its neighbours happened to draw a slightly higher degree. That spreads the out-degrees from zero to seven. A hundred and thirty-six vertices sit above four — 116 at five, 19 at six, one at seven — and at the other end, 56 vertices have no out-neighbours at all.

Why the bound is still true #

A false reason does not make a conclusion false, and the orientation by degree really does examine $O(E \cdot d)$ pairs. The argument runs through a different quantity.

Under the degree orientation, a vertex $v$ with out-degree $d^+(v)$ examines $\binom{d^+(v)}{2}$ pairs, which is less than $d^+(v)$ times $d^+(v)$. One factor of $d^+(v)$ can be spread over $v$’s out-edges — one per edge — and the other is at most $v$’s own degree $d(v)$, since out-neighbours are neighbours. So the pairs are at most the sum, over out-edges from $v$ to $u$, of $d(v)$. On each such edge $v$ is the endpoint of lower degree, so $d(v) = \min(d(u), d(v))$, and the whole sum is at most

$$\sum_{\{u,v\} \in E} \min\bigl(d(u), d(v)\bigr).$$

That sum over edges of the smaller endpoint degree is a quantity Chiba and Nishizeki bounded in 1985: it is at most twice $E$ times the graph’s arboricity, the fewest forests its edges can be divided into, and the arboricity is at most the degeneracy. So the pairs are at most $2\,E\,d$, and the work is $O(E \cdot d)$ — with a factor of two the one-sentence argument did not have, and by a route that never mentions any single vertex’s out-degree.

Every measured count sits under both lines, and the two lines are in the opposite order from what their roles suggest. $E \cdot d$ is the smaller number on every graph drawn — 12,288 against 17,120 — and it is not the one that is proved for this orientation; the sum of smaller degrees is larger, and it is. The degree orientation’s pairs are under $E \cdot d$ on these graphs, as they must be under $2\,E\,d$, with room to spare: the measured counts are about a third of $E \cdot d$. So the earlier essay’s numerical comparison — 4,090 and 3,339 against 12,288 — was right, and the bound it quoted holds here without the factor of two. What it rested on did not hold.

The orientation that has the property #

The orientation that keeps every out-degree at or below $d$ is the one the definition of degeneracy suggests. Run the deletion that computes $d$, and point every edge at whichever endpoint is deleted later. When a vertex is deleted, its remaining neighbours are exactly the ones deleted after it, and by the choice of vertex there are at most $d$ of them. So every out-degree is at most $d$, by construction rather than by argument, and the pairs a vertex examines are at most $\binom{d}{2}$.

On every graph drawn it also examines fewer pairs, and the saving follows the degree distribution: 25%, 18% and 12% on the uniform graphs, where ordering by degree is nearly arbitrary, and 13%, 8% and 5% on the preferential-attachment graphs, where degree and arrival order are close to the same thing. As the preferential-attachment graph grows, the ratio stays at about 1.08 while the number of vertices above the degeneracy under the degree order grows in proportion to the graph. The degree order’s excess is a fixed fraction, not a growing one, on these random graphs.

Both orientations cost linear time to compute. Ordering by degree needs the degrees and a bucket sort of them; the degeneracy order needs a bucket queue that follows degrees as vertices are deleted, which is a little more bookkeeping. That bookkeeping is the same kind of amortised argument the constant that is practically constant leans on for union–find: each deletion lowers a handful of neighbours’ degrees by one, and a degree can only fall as many times as it started high. So the practical choice between them is between a slightly simpler preparation and one to a quarter fewer pairs — and the standard implementation takes the simpler one, which is reasonable, with the stated justification of the other, which is not.

Three bounds that were true of something else #

This shape has turned up before, and setting the cases beside each other shows what kind of error it is.

The bound with a precondition found that Bellman–Ford’s $O(V \cdot E)$ describes a version of the algorithm with no early exit, and the version everybody runs stops after seven passes of the 2,047 the bound allows on a graph of 2,048 vertices. The bound was true and its subject was a different program. The queue decides the class found that Dijkstra’s $O(E \log V)$ is exactly right about the priority queue and that on a dense graph the queue is two per cent of the work. The bound was true and its subject was a component that did not dominate.

And the invariant that was wrong for seven years is the closest relative of this page. Timsort’s merge rule inspected the top three entries of its run stack in order to keep the stack shallow, the belief that it did so was stated and relied on for years, and the rule does not imply it; thirty-three elements break it, and the array still comes out sorted. The result — a sorted array — was checked by everyone who ran the sort. The reason — that the stack stayed shallow — was checked by nobody until a proof failed.

The orientation argument is the same failure at a smaller scale. The result, a total count under $O(E \cdot d)$, was checked. The reason, every out-degree under $d$, was not, and it was false on the very graphs drawn beside it.

How the false sentence survived #

The claim was checked on the site in the only way a numerical claim about a bound is usually checked: the measured work was compared with the bound, and it was under it. A bound on a total can be satisfied for many reasons, and a check that the total is under the bound cannot distinguish the stated reason from any other.

What would have caught it is a check on the intermediate claim — that every out-degree is at most $d$ — and it is a one-line check once someone thinks to write it. The check now runs in both directions: the degree orientation must have some vertex above $d$ on these graphs, the degeneracy order must have none, and a statement that the degree orientation is bounded by $d$ is refused by the graph it was made about. The check must reject is the standard those checks are written to, and this is a case where the rejection is of a sentence in an essay rather than of a bug in code.

The general form is worth writing down, because it is not specific to triangles. A bound verified on its conclusion has not been verified on its argument. An $O(E \cdot d)$ total can hold because every term is at most $d$, or because the terms are small on average, or because a different quantity bounds them; the measurement of the total is the same in all three cases. A guarantee names its model is the collection’s theme for a bound that holds only under stated conditions, and a bound’s reason is one more condition — the one a reader reuses when applying the argument to a new case.

That reuse is where the false reason would have done damage. The one-sentence argument generalises obviously: bound every out-degree by $d$, and any algorithm that does per-vertex work polynomial in out-degree — listing 4-cliques by triples of out-neighbours, say, at $\binom{d^+}{3}$ each — inherits a bound in $d$. Under the degree orientation that generalisation is not justified, because the vertex with out-degree seven on a degeneracy-four graph contributes $\binom{7}{3} = 35$ triples where the argument allowed four, and the smaller-degree sum that rescues the triangle bound does not obviously rescue the higher powers. Under the degeneracy order it is justified exactly.

What this does and does not change #

The earlier essay’s measurements stand. The counts of 18,480 and 42,076 pairs for the naive enumeration, 4,090 and 3,339 for the oriented one, the degeneracy of four on both graphs, and the reversal in which the skewed graph becomes the cheaper one are all unchanged. Its account of why the orientation’s cost follows the degeneracy has been corrected in place to the argument on this page.

The degeneracy is still the right third parameter. It bounds the degree orientation’s work, through the smaller-degree sum, and it bounds the degeneracy orientation’s out-degrees directly. What changed is which of those two statements is the one about the orientation everybody uses. Two parameters, one bound, no order set the discipline that every graph bound names its regime; this page adds that a bound should also name its argument, since the argument is what a reader carries to the next algorithm.

Nor the memory the two orders touch. The degeneracy order visits vertices in deletion order, which on a preferential-attachment graph is roughly reverse arrival order, and the degree order visits them by degree. A list and a block of memory found that the order a graph’s edges are laid out in moves a traversal’s cache misses by a factor of 3.6; which of the two orientations reads its adjacency lists in the kinder order is not measured here.

Nothing here measures the higher-clique case. The paragraph on 4-cliques is an argument about what would follow, not a measurement, and whether the degree orientation’s excess out-degrees make a practical difference to clique listing on real graphs is not settled on this page.

Still open: the pairs a better order could save #

The degeneracy order examines up to a quarter fewer pairs than the degree order, and neither is the fewest possible. The number of pairs is $\sum_v \binom{d^+(v)}{2}$, which depends on how the out-degrees are distributed, not only on their maximum, and an orientation that minimises the sum of squared out-degrees is a different object from one that minimises the largest. Finding the orientation that minimises a sum of convex functions of out-degrees is a flow problem, solvable exactly in polynomial time, and far more expensive than either linear-time order.

That makes it a benchmark rather than a method. The measurement that follows computes the minimum-pairs orientation on the graphs drawn here and asks how far above it each linear-time order sits — whether the degeneracy order’s quarter saving over the degree order is most of what is available, or a small part of it — and, if the gap is large, whether a cheap local improvement to the degeneracy order recovers it.