Two parameters are not enough either

Two parameters, one bound, no order established this field’s central discipline. With one size parameter the candidate classes are ordered — $n$ beats $n \log n$ beats $n^2$, always — and comparing two bounds is reading them. With two there is no order at all, $E \log V$ and $V^2$ cannot be compared without knowing the density, and every claim on this site since carries a density regime attached.

Two is an improvement on one. It is not enough.

The two graphs are not adversarial constructions. One is the model this field has swept every algorithm over since it started — a random graph at a fixed average degree — and the other is the standard model of how a network grows when new arrivals attach to whatever is already popular. Both are ordinary, both are the sort of thing anybody would benchmark on, and a bound written in $V$ and $E$ is silent about the difference between them.

Where the sum of squared degrees comes from #

The problem is counting triangles, which is a real one — a triangle is a closed triple, its density is the clustering coefficient, and that number is how a social graph, a citation graph or a fraud network is characterised.

The obvious method is direct: for every vertex, look at every pair of its neighbours and ask whether they are joined. The work is

$$\sum_v \binom{d(v)}{2} \approx \tfrac{1}{2}\sum_v d(v)^2$$

and the shape of that expression is the whole of this page. It is the second moment of the degree distribution, not the first. The first moment is fixed by $E$ — the degrees sum to $2E$ whatever the graph looks like — so two graphs with equal $E$ have equal mean degree by construction. Their second moments are free to differ by any amount the vertex count allows.

Measured at a thousand vertices, the two graphs’ squared-degree sums are 43,104 and 90,296. The same first moment, twice the second.

The busiest-vertex column is the mechanism. A vertex of degree 114 contributes $\binom{114}{2} = 6{,}441$ pairs by itself — a fifth of the whole graph’s work, from one vertex out of a thousand. The uniform graph has no such vertex and cannot have one; its maximum degree is about $\log V / \log\log V$, which at this size is sixteen.

It is worth checking that intuition against the other end of the distribution, because the effect could in principle be about the tail rather than about the hub. It is about the hub. The uniform graph’s degrees run from one to sixteen and the skewed graph’s from one to 114, and the skewed graph has more vertices of degree one — a heavy tail at the top is paid for by a heavy concentration at the bottom, since the degrees must still sum to $2E$. Those low-degree vertices cost nothing to enumerate. The whole of the extra work is in a handful of vertices, which is the shape on average is not a number exists to warn about: a mean over vertices hides a cost concentrated in a few of them.

The repair, which introduces the third parameter #

There is a standard fix and it is one line of preparation. Before enumerating, orient every edge from its lower-degree endpoint towards its higher-degree one, breaking ties by index so the orientation is a total order. Then enumerate only pairs of a vertex’s out-neighbours.

Every triangle is still counted, exactly once instead of three times, because in any triangle exactly one vertex is lowest in the order and it is the one that sees both of the others as out-neighbours. And the work is now bounded — not by the degree distribution’s second moment, but by a global property of the graph.

That property is the degeneracy: the largest $d$ such that every subgraph contains a vertex of degree at most $d$. It is computed by repeatedly removing a minimum-degree vertex and recording the largest degree seen at removal, and it takes linear time. The oriented method’s work is $O(E \cdot d)$. An earlier version of this page said that was because the orientation keeps every out-degree at most $d$, and that is not true of the orientation by degree: on the uniform graph below, 136 vertices have more than $d$ out-neighbours. The bound holds by a different route — the pairs are at most the sum over edges of the smaller endpoint degree, which is at most $2\,E$ times the arboricity, which is at most $d$ — and a bound right for the wrong reason measures both the false reason and the orientation that does keep every out-degree at most $d$.

The measured effect is the interesting part:

The orientation does not merely close the gap. It reverses it. The graph with a vertex of degree 114 becomes the cheaper of the two, because that vertex now has almost no out-neighbours — everything it touches has a lower degree than it does, so every one of its edges points inward. A hub is expensive under the naive method for exactly the reason it is free under the oriented one.

And the degeneracy is four on both. The parameter that decides the oriented method’s cost is nearly identical on two graphs whose maximum degrees differ by a factor of seven, which is what makes it the right parameter: it describes the graph’s uniform sparsity rather than its worst vertex.

The orientation is also a good illustration of a habit this collection keeps finding. It changes no answer, adds no data structure, and consists of comparing two integers before deciding which way to walk an edge — and it moves the work by a factor of twelve on the graph that needs it most. Counting on a graph found the same shape in the layout of an adjacency list, and the queue decides the class found it in a structure the pseudocode does not name. In each case the decisive thing is a detail below the level at which the algorithm is described.

Why the reversal is the interesting half #

The gap between 18,480 and 42,076 is a good headline and the reversal underneath it is the better result, so it is worth taking apart.

Under the naive enumeration a vertex of degree $d$ costs $\binom{d}{2}$, so cost is convex in degree and a hub is a disaster. Under the oriented enumeration the same vertex costs $\binom{d^{+}}{2}$ where $d^{+}$ counts only its out-neighbours — the ones with a strictly higher degree, or an equal degree and a higher index. A hub, by definition, has almost nothing above it, so $d^{+}$ is near zero and the hub becomes free.

That is not a bound being tightened. It is the cost being redistributed: the work a hub was doing gets pushed out to its low-degree neighbours, each of which now examines the pairs among its own few out-neighbours. The total falls because a hub’s $\binom{114}{2}$ pairs are replaced by 114 vertices each examining a handful.

And the redistribution is what makes the skewed graph cheaper than the uniform one rather than merely equal to it. A uniform graph has no hubs to relieve; every vertex has about six neighbours and about three of them are above it, so the orientation halves the work and no more. A skewed graph has most of its edges attached to a few vertices, and the orientation moves essentially all of that work onto vertices with almost none of their own. The graph whose structure was the problem becomes the graph whose structure is the opportunity, from one comparison per edge.

Why a two-parameter bound cannot see this #

The failure is not that the bound is loose. It is that the bound is a function of two numbers and the quantity being predicted is not.

Write $W$ for the naive method’s work. Then $W = \frac{1}{2}\sum_v d(v)^2$, and the constraint from the parameters is $\sum_v d(v) = 2E$. By Cauchy–Schwarz, $\sum d^2 \ge (2E)^2/V$, with equality when every degree is the same. There is no upper bound in terms of $V$ and $E$ short of the trivial one: a single vertex joined to everything gives $\sum d^2 \approx V^2$ at $E = V$.

So the range of $W$ consistent with a given $(V, E)$ spans from $4E^2/V$ to about $V^2$, which at these parameters is a factor of a hundred. A bound in $V$ and $E$ must quote the top of that range or be wrong, and the top of the range is a graph nobody has. The published bound for this method is $O(E^{3/2})$, which is 170,000 at these parameters against measurements of 18,480 and 42,076 — right, and describing neither.

That is the same failure this field has now found three times, and setting the three beside each other is worth doing:

• one parameter is not enough: $n$ alone cannot express a graph, so bounds in $n$ are silent about density;
• two are not ordered: $E \log V$ and $V^2$ cannot be compared without a regime, which is the second rung’s finding;
• and two are not enough: the degree distribution decides costs that $V$ and $E$ cannot bound.

Each step adds a parameter and each addition was invisible until something was measured that the previous set could not distinguish.

What this does to a benchmark #

The practical consequence is not about bounds at all; it is about how an algorithm is compared with another one, and it is the reason this page matters to the rest of the field.

Every sweep on this site fixes a graph kind and varies $V$. That is the right experiment for granting a class, and it means every class this field has granted is a class on a uniform random graph at a fixed average degree — the kind whose degree distribution is as tame as the parameters allow.

Run the same sweep on the skewed generator and some of those classes would survive and some would not. A traversal’s would: it examines every arc once whatever the degrees are. Dijkstra’s would, for the same reason with a queue in front. Anything that enumerates a neighbourhood’s pairs would not, and the naive triangle count is the clearest case — it fits $E^{1.5}$ on neither generator and fits the second moment on both, which is not a class in $V$ and $E$ at all.

So the honest statement about this field’s audit plate is narrower than it looks. A class granted on one generator is a claim about that generator, and the fact that every algorithm previously measured here happens to be insensitive to the degree distribution is a property of the algorithms chosen rather than a property of graphs. This rung is the first one where it stops being true, and it is a reason to state the generator alongside the density regime from here on.

What the degree distribution is a fact about #

Neither graph on these plates is arbitrary. Both are generated, both are seeded, and the difference between them is a single modelling decision about how edges arrive.

Uniform pairs: each edge joins two vertices chosen at random. Degrees are concentrated around the mean, the maximum is logarithmic, and the second moment is close to the minimum the parameters allow.

Preferential attachment: each new vertex attaches to existing vertices chosen in proportion to how many edges they already have. Degrees follow a power law, the maximum grows as a power of $V$, and the second moment is unbounded in the limit.

The second is the one that resembles measured networks — citation graphs, web links, protein interactions, social follows all show heavy-tailed degrees — which means the case a two-parameter bound describes worst is the case that occurs. That is an uncomfortable conclusion and it is the honest one: the bound is not merely loose on real graphs, it is loosest precisely there.

It is also the reason the orientation trick is standard in practice and unusual in textbooks. On a uniform graph it buys a factor of 4.5; on a heavy-tailed one it buys 12.6 and reverses the ranking. The technique’s value is a function of exactly the parameter the analysis does not carry.

What a third parameter has to be to be worth having #

Not every quantity that varies between two graphs deserves a place in a bound, and it is worth saying what makes degeneracy one that does.

It is computable in linear time, which is the same requirement the constant that is practically constant leans on for union–find’s own bound. A parameter that costs more to find than the algorithm it bounds is a parameter nobody can use. Degeneracy comes from repeatedly removing a minimum-degree vertex, which with a bucket queue is $O(V + E)$ — cheaper than the enumeration it bounds.

It bounds something, rather than describing it. The maximum degree also varies between the two graphs and is also cheap to compute, and it bounds nothing useful here: the oriented method’s cost has no relation to it, as the reversal on this page shows. Degeneracy bounds the oriented method’s work — through the sum of smaller endpoint degrees for the orientation by degree, and through every out-degree directly for an orientation taken from the degeneracy computation itself.

And it is stable. Both graphs on the hero plate have degeneracy four, at every size drawn, while their maximum degrees diverge. A parameter that takes similar values on graphs that behave similarly under the algorithm is a parameter that is measuring the right thing.

The three requirements together are restrictive, and they are why the list of parameters in this field is short. $V$, $E$, and — for anything that has to enumerate a neighbourhood — degeneracy. Anything else that has been proposed is either uncomputable, unstable, or bounds nothing.

Three ways a bound can be wrong about a graph #

It helps to separate the failures, because “the bound is loose” covers three different situations and only one of them is repaired by a third parameter.

The bound is an upper bound and the algorithm stops early. Bellman–Ford’s $V \cdot E$ describes a version with no early exit; the version everybody runs stops after a handful of passes, and the bound with a precondition measures a factor of 289 between the two on one graph. Nothing is wrong with the bound; it describes a different program. No parameter fixes this — the fix is to state which version is being bounded.

The bound is tight and describes a component that does not dominate. Dijkstra’s $E\log V$ is exactly right about the queue, and on a dense graph the queue is two per cent of the work. The queue decides the class measures it. Again no parameter is missing; what is missing is that a bound on the whole is being read as a description of where the time goes.

Or the bound is in the wrong variables. This page. The quantity being predicted is a function of the degree distribution, the bound is a function of $V$ and $E$, and no amount of care in stating or measuring recovers the difference — because two graphs with the same $(V, E)$ genuinely do different amounts of work and a function of $(V, E)$ must give them the same answer.

Only the third calls for a new parameter, and it is the rarest of the three. The first two are about reading a bound carefully, which this field has been insisting on since its second rung; the third is about the bound not having enough arguments, which is a defect in the statement rather than in its interpretation.

That is worth having as a checklist rather than as a conclusion. Faced with a bound that does not describe a measurement, the question is which of the three is happening — and the answer decides whether the repair is a sentence, a decomposition, or a parameter.

What a two-parameter sweep can still establish #

None of this makes the sweeps in this field worthless, and it would be easy to read the page that way.

A sweep at a fixed density establishes what an algorithm does as a graph of that shape grows, which is a real and useful statement. It is what grants a class here, it is what two parameters, one bound, no order uses to show that $E\log V$ and $V^2$ change places between regimes, and it is what refuses a claim that does not hold.

What it cannot do is compare two graphs of the same size and different shape. That is a comparison across a dimension the sweep holds fixed, and holding a dimension fixed is exactly how a sweep isolates the one it is varying.

So the repair is not to abandon the method. It is to run the sweep on more than one generator and report which classes survive the change — which is a larger experiment than this field currently runs, and which would produce a more useful audit plate than the one it has: not which classes fit, but which classes fit on every generator tried.

What is not measured here #

The generators are models, not data. Preferential attachment produces a power-law degree distribution and a real graph is not a preferential-attachment graph — it has community structure, degree correlations and a clustering coefficient far above what either model gives. The triangle counts here, 30 and 249, are what the models produce; a real graph of this size and density would have far more.

The edge counts are equalised by topping up. Preferential attachment lands a handful of edges short of the target, and the remainder are drawn uniformly so that the two graphs have exactly the same $E$. That dilutes the skew slightly, in the direction that weakens the claim, and it is what makes “identical in both parameters” true to the unit rather than approximately.

And degeneracy is computed the slow way. The linear-time algorithm uses a bucket queue; the version here scans for a minimum-degree vertex each round, which is quadratic and fine at these sizes. Nothing on the plate is a measurement of the degeneracy computation’s own cost, and if it were, the parameter’s practical appeal would need re-examining.

Nor are the layouts compared. A list and a block of memory found the largest gap on this site between two counts of one run, and a heavy-tailed graph’s memory behaviour differs from a uniform one’s for reasons that have nothing to do with the enumeration order. Nothing here measures that.

Nor is the counting itself the interesting problem at scale. Exact triangle counting on a graph of a billion edges is done by sampling or by matrix multiplication rather than by enumeration, and both have parameters of their own. This page is about what the enumeration’s cost depends on, which is a question about bounds rather than about the state of the art.

Where this ladder goes from here: the parameter after the third #

Three parameters now, and the honest position is that the list is not finished either.

Degeneracy bounds the oriented enumeration, and it does not bound everything. A triangle count by matrix multiplication depends on neither the degree distribution nor the degeneracy but on the matrix’s rank; a count by sampling depends on the triangle density itself, which is the answer; and a count on a graph too large to hold depends on the arrangement in memory, which is what a list and a block of memory measures for a traversal and which no structural parameter reaches.

The specific next thing is smaller and is measurable with what is already here. The work is the sum of squared out-degrees, not $E$ times a maximum, so the bound $O(E\cdot d)$ is itself loose in exactly the way the naive bound was — it quotes a maximum where a distribution decides. The measured oriented counts on this page are 4,090 and 3,339 against a bound of $E \cdot d = 12{,}288$ on both, so the bound is three times the measurement on one graph and four times on the other, and the ratio between those two slacknesses is the same kind of quantity this page began by measuring.

Whether a fourth parameter is worth naming for that, or whether the right conclusion is that a distribution cannot be summarised by any fixed number of parameters, is the question the next rung should try to settle rather than assume.