A ranking whose order is not determined

Nobody reads a stationary distribution. What is read is the order — which page is first, which is second, which made the top ten — and an order is a set of pairwise comparisons rather than a vector of numbers.

That changes what “accurate” means. Two entries differing by 10⁻⁸ are ordered by digits far below anything else in the pipeline, and no amount of iterating settles a comparison the data does not settle. So the question worth asking is not how accurate the entries are; it is how many of the comparisons are decided by the problem, and by which part of it.

Three kinds of doubt, measured on one graph #

An eighty-page link graph with six dead ends, PageRank at α = 0.85, top fifteen. Fourteen adjacent comparisons. Each source of doubt is applied ten times and a comparison counts as settled if it never reverses:

source of doubt                     entries move by     comparisons settled
the arithmetic (teleport ±10⁻¹⁰)      4.1·10⁻¹¹            14 of 14
α across 0.80 to 0.90                 1.2·10⁻³            11 of 14
one arc removed                       4.4·10⁻³             3 of 14

The gaps between consecutive entries in that top fifteen run from 6.3·10⁻⁵ to 2.3·10⁻³.

Nothing the arithmetic does comes within seven orders of magnitude of the smallest gap. One missing link moves entries by seventy times the smallest gap and reorders eleven of the fourteen places.

This is the opposite of the site’s usual finding #

It is worth stopping on how unusual that is here.

Almost every essay in this collection finds that the computation is the fragile part: a Gram–Schmidt that loses orthogonality, a normal-equations route that squares a condition number, a rank that depends on the thread count, twenty-one answers from one program. The recurring lesson is that the algebra is exact and the arithmetic is not, and the difference is measurable and often large.

Here the difference is measurable and negligible. The computation is backward stable, the problem is well conditioned — 1/(1 − α) is about seven at the usual parameter — and the answer’s entries are settled to eleven digits. Every place in the leaderboard survives it.

What does not survive is the data, and the reason is the shape of the answer rather than the quality of the computation. A ranking’s adjacent gaps are small by construction: entries that are close in value are close in rank, and any list of length k has k − 1 comparisons of which the smallest is very small. So a ranking amplifies whatever uncertainty is in its input into a discrete disagreement, and the input’s uncertainty is not a rounding.

What one link is worth #

The one-link perturbation deserves precision, because it is the honest model of what a link graph is.

A crawl is a sample. A page’s outgoing links are whatever was on it when it was fetched, which may be weeks old; a link may have been added, removed, or missed by a parser; a redirect may or may not have been followed. Removing a single arc from an eighty-page graph is a small version of that — one link in two hundred and fifty-three — and it moves the answer by 4.4·10⁻³, seventy times the smallest gap in the top fifteen.

That is not a criticism of PageRank. It is a statement about the conditioning of a ranking with respect to its input, and the number to compare it against is the backward error of the crawl rather than the backward error of the arithmetic. The machine field’s reframing applies directly: the variation a computation commits is equivalent to a perturbation of the data of a certain size, and the useful question is how that size compares with the data’s own uncertainty. Here the arithmetic’s equivalent perturbation is 10⁻¹¹ and the data’s is 10⁻² — nine orders apart.

Which places, and not just how many #

The count hides something the per-position table shows plainly: the comparisons that survive are not the ones with the largest gaps.

place   gap        reversals under one link   under α
 1      1.13·10⁻³            1                   0
 2      3.14·10⁻⁴            1                   0
 3      2.29·10⁻³            0                   0
 4      2.41·10⁻³            0                   0
 5      1.21·10⁻⁴            4                   1
 6      4.26·10⁻⁴            3                   0
 9      1.09·10⁻³            0                   0
10      6.28·10⁻⁵            3                   1
14      9.01·10⁻⁵            5                   0

Places three, four and nine survive; places one and two do not, although their gaps are larger than place fourteen’s, which also does not. The correlation between gap and survival is real and it is weak.

The reason is that a perturbation is not isotropic. Removing an arc does not move every entry by the same amount; it moves the pages near that arc a great deal and the rest hardly at all. So a comparison between two pages that both depend on the removed link can reverse even with a large gap, and a comparison between two pages far from it survives a small one.

That has a practical consequence. A determinacy cut cannot be computed from the gaps alone. It needs the perturbation actually applied, because which places move depends on where in the graph the uncertainty is. Estimating it from a gap threshold — the obvious cheap approach — gets places one and two wrong in the table above.

The parameter sits between them #

α is the middle row and that is the interesting part of the table.

Moving it from 0.80 to 0.90 — a range nobody would argue about, and narrower than the range in actual use — moves entries by 1.2·10⁻³ and reorders three of the fourteen places. So the choice of teleportation parameter is worth more than the entire arithmetic by eight orders of magnitude, and less than one uncrawled link by a factor of four.

That ordering is the practical content of this essay. A team worried about the reproducibility of a ranking should worry about the crawl first, the parameter second, and the arithmetic not at all — and the usual allocation of attention is the reverse, because the arithmetic is the part that is visible in the code.

Further down, less is settled #

Reading twenty-four places instead of fifteen does not add nine more settled comparisons; it adds nine more comparisons, most of which nothing settles.

The reason is that the gaps shrink as the list is read down. The top two or three entries are separated by an order of magnitude and nothing moves them. Places ten to twenty are separated by less than one link’s worth of doubt, and their order is decided by whichever version of the crawl was used.

So a ranking is not uniformly determined — its top is and its middle is not — and publishing it as a numbered list says otherwise. The honest presentation is a list with a cut in it: these places are determined, and below this line the order is not a property of the data.

That is exactly the presentation this site argues for elsewhere. Rank is a decision makes the case for printing the gap beside the integer; an estimate that can be fooled makes it for printing the spread beside the estimate. A leaderboard with a determinacy cut in it is the same move.

How to compute the cut #

It costs a small multiple of one PageRank run and needs no theory.

Run the computation several times with the input perturbed the way the input is actually uncertain — arcs dropped at the rate the crawl misses them, or two crawls a week apart. Record, for each adjacent pair in the region of interest, whether the order ever reverses. The first pair that reverses is the cut.

The three-column table above is that procedure with three different perturbations, and the only judgement in it is what perturbation to apply. That judgement is the modelling question, and it is the one worth arguing about — an arc dropped uniformly at random is a crude model of a crawl’s error, and a better one would drop arcs from pages that were fetched longest ago.

What is not worth arguing about is the arithmetic’s contribution, which is measurable, is 4.1·10⁻¹¹, and can be reported once and then ignored.

It does not improve with size #

A reasonable hope is that this is a small-graph effect: eighty pages is not a web, the gaps are large in relative terms, and a real graph with billions of entries would concentrate its top so sharply that one link could not move it.

The measurement goes the other way.

pages   arcs   settled by arithmetic   by one link   by α   smallest gap
 40     113          14 of 14              4           10     3.7·10⁻⁴
 80     237          14 of 14              3           11     6.3·10⁻⁵
160     441          14 of 14              3            8     4.1·10⁻⁵

The arithmetic settles everything at every size, as it must — its equivalent perturbation is 10⁻¹¹ and the gaps shrink much more slowly than that. What one link settles does not improve, and what α settles gets worse, from ten of fourteen to eight.

The mechanism is the one above. Growing the graph shrinks the gaps in the top fifteen, because there are more pages competing for those places, and it shrinks the effect of one link roughly in proportion — one arc of 441 matters less than one of 113. The two effects nearly cancel, and neither of them helps the parameter, whose contribution is a fixed relative change to the whole vector.

So a bigger crawl does not buy a more determined leaderboard. It buys a longer one with the same number of settled places at the top, which is worth knowing before an engineering effort is spent on the crawl’s size rather than on its freshness.

The one thing the arithmetic can still ruin #

There is a way to lose the eleven digits, and it is the stopping test.

The power iteration’s change between iterates underestimates the remaining error by 1/(1 − α), which at α = 0.85 is about seven and at α = 0.99 is a hundred. A run stopped when the change falls below 10⁻⁸ at α = 0.99 is 10⁻⁶ from the answer — which is larger than every gap in the top fifteen above, and would reorder the whole list.

So the arithmetic is negligible provided the iteration was actually converged, and whether it was is not something the stopping test reports. That is the one number from this field’s earlier essays that a ranking pipeline genuinely needs: convert the change to an error before comparing it against a tolerance, and the conversion is one division by 1 − α.

What a determinacy cut looks like in an output #

It is worth being concrete about the deliverable, because “report the uncertainty” is easy to agree with and easy to skip.

The output of the procedure above is a list with a horizontal rule in it. Above the rule, the places are a property of the data: they survived every perturbation applied. Below it, the entries are ordered because a sort has to order them, and the order is not information.

Two details make the difference between that being useful and being decorative.

The rule’s position depends on the perturbation, so the perturbation has to be named. “Determined against one dropped link” and “determined against two crawls a week apart” are different statements, and a rule with no caption is an assertion about robustness in general, which nothing supports.

And the entries below the rule should still be shown. Truncating the list at the cut throws away the information that these pages are in the top fifty and merely not orderable within it, which is usually the useful statement. The failure mode to avoid is a list that looks precise, not a list that is short.

This is the same presentation the rank essays argue for: print the integer and print the gap beside it, so that a reader can see whether the integer was read off or decided. A leaderboard with a determinacy cut is that, applied to fourteen comparisons instead of one.

What this says about the field #

The graph field’s characteristic shape is that the answer is discrete, so an error has no continuum to be small in. This essay is the case where that shape produces a reassuring result rather than an alarming one.

The discreteness is still there — a reordered pair is a different answer, not a slightly wrong one — and the amplification is still there, because adjacent gaps in a ranking are small by construction. What is different is where the perturbation comes from. In the partition essays the graph was exact and the perturbation was the arithmetic’s, so the answer was decided by rounding. Here the graph is a sample and the perturbation is the sample’s, so the answer is decided by the data — which is the situation anybody would prefer, because a sample can be improved and a rounding cannot.

The general statement, and it is worth carrying past this field: when an answer is a discrete function of a continuous computation, ask what the computation’s variation is equivalent to as a perturbation of the data, and compare it against the data’s own uncertainty. If it is smaller, the computation is not the problem. Here it is smaller by nine orders, and saying so is more useful than another digit of accuracy would be.

The comparison the site has a name for #

There is one more way to read the table, and it is the reading the machine field supplies.

That field’s actionable measurement is: the run-to-run variation a machine commits is equivalent to a perturbation of the data of a stated size, so a regression tolerance can be chosen — larger than the machine’s equivalent perturbation, smaller than the smallest defect worth catching, and the window between them is a factor of 1.42 on the problem measured there.

The same arithmetic applies here and the window is enormous. The arithmetic’s equivalent perturbation is 4.1·10⁻¹¹ in the entries. One link’s is 4.4·10⁻³. The window is a factor of 10⁸, which means a test that asks whether two runs of the ranking pipeline agree can be set at almost any tolerance in eight orders of magnitude and will pass on correct work while catching any change to the crawl.

That is an unusually comfortable position and it is worth saying so, because the rest of this essay is about a fragility. The ranking is fragile with respect to its input and completely robust with respect to its implementation, and those two facts together make the regression testing of a ranking pipeline easy while making the interpretation of its middle places impossible.

At other settings #