A ranking that is an eigenvector

A link is not symmetric, so the graph a search engine has is directed and nothing in the previous six essays applies to it directly. There is no symmetric Laplacian, no real spectrum guaranteed by symmetry, and no quadratic form to minimise.

What there is instead is a process. Put a walker on a page; with probability α it follows a link chosen uniformly from that page’s outgoing links, and with probability 1 − α it jumps to a page chosen from a fixed distribution. Run it forever and ask where the walker spends its time. That limiting distribution is PageRank, and it is an eigenvector: the stationary vector of the matrix

G = α P + (1 − α) v 1ᵀ

where P is the column-stochastic link matrix and v is the teleport distribution.

Two routes, and they agree #

An eigenvector for a known eigenvalue is a null space, so there are two obvious ways to get one.

The power iteration. Start uniform, apply G repeatedly, stop when successive iterates stop moving. It costs one sparse matrix–vector product a step and never forms anything.

One elimination. The eigenvector equation x = αP̃x + (1 − α)v rearranges to (I − αP̃)x = (1 − α)v, and I − αP̃ is strictly diagonally dominant for α < 1, so it is nonsingular and can be factorised directly.

On an eighty-page link graph the two agree to within 4·10⁻¹⁷ at every α tested, with the elimination’s own relative residual between 5·10⁻¹⁶ and 1.9·10⁻¹⁴:

α       iterations   |iteration − elimination|   solve residual
0.50        27            1.4·10⁻¹⁷                4.9·10⁻¹⁶
0.70        36            2.1·10⁻¹⁷                6.2·10⁻¹⁶
0.85        46            3.1·10⁻¹⁷                1.7·10⁻¹⁵
0.95        54            3.8·10⁻¹⁷                6.5·10⁻¹⁵
0.99        58            4.2·10⁻¹⁷                1.9·10⁻¹⁴

That is the site’s habit doing what it is for. Two computations sharing no arithmetic beyond the matrix, agreeing at the rounding level, on a problem whose answer nobody knows in closed form. The residual rising with α is the diagonal dominance weakening — the elimination’s matrix is I − αP̃, whose conditioning degrades as α approaches one — and it rises by a factor of forty across the range while the agreement between the routes does not move at all.

Nobody uses the elimination at scale, because the matrix has billions of rows. It is used here for exactly the reason this site uses second routes anywhere: to know that the first one is right.

What α is #

The parameter is usually introduced as a technicality — something to make the chain irreducible and aperiodic so that a unique stationary distribution exists. That is true and it is not what it does to the answer.

α decides how much of the ranking comes from the link structure and how much from the teleport vector. At α = 0 the answer is v exactly and the graph is not consulted. At α = 1 the graph is everything and, on the graphs it was invented for, there is no unique answer at all.

In between it is a mixture, and the mixture is measurable. On the same eighty-page graph, the answer’s spread about the uniform distribution:

α       min entry     max entry    max ÷ min
0.50    6.7·10⁻³      2.1·10⁻²       3.18
0.85    2.8·10⁻³      2.7·10⁻²       9.65
0.99    1.3·10⁻³      2.9·10⁻²      23.32

At α = 0.5 the most important page is three times the least. At α = 0.99 it is twenty-three times. Nothing about the graph changed between those rows.

This is not a technicality; it is a regularisation in the site’s own sense of the word. The data — the link graph — does not determine a unique answer, something outside it has to be chosen, and the choice is the computation rather than a preliminary to it. The regularisation field’s opening argument transfers verbatim, with the teleport vector playing the role of the prior and α playing the role of the regularisation parameter.

And it changes the order #

Whether a parameter matters depends on what is read off the answer, and what is read off this answer is a ranking. Over the same six values of α on the same graph, the top five pages come out as:

α = 0.50    69, 79, 33, 75, 18
α = 0.70    69, 79, 75, 33, 18
α = 0.85    69, 79, 75, 33, 37
α = 0.95    69, 75, 79, 33, 37
α = 0.99    69, 75, 79, 33, 37

The first place is stable. Positions two through five are not: page 75 moves from third to second, page 18 leaves the list, page 37 enters it. Three of the five places change across a range of α that every practitioner would describe as reasonable.

So the honest statement about a PageRank leaderboard is that its top entry is a property of the graph and its next several entries are a property of the graph and a constant somebody picked. The essay on what a ranking is determined by measures that against the other sources of doubt, and finds that α is not even the largest of them.

The teleport vector is the other half of the choice #

α says how much of the prior to use. What the prior is gets much less attention and is the second free parameter in the definition.

The uniform vector is the default and it is a statement: every page is equally plausible a priori. Anything else is a personalisation — a distribution concentrated on one page, on a topic, on a set of trusted sites — and the machinery is identical, since v enters only as the right-hand side of (I − αP̃)x = (1 − α)v.

That linearity is worth noticing, because it makes the parameter’s role explicit. The answer is a linear function of v, so a personalised ranking is a linear combination of the personalised rankings of the pages v is supported on, and the whole family of answers over all possible priors is a convex set spanned by n basis vectors. There is not one PageRank; there is an n-dimensional family, and the uniform one is a single point in it, chosen because nobody had a better idea.

The same object is behind the dangling-node repair. A page with no outgoing links has an empty column, so the link matrix is not stochastic and the walker vanishes when it arrives. Every implementation repairs it by sending that mass to the teleport vector, which is a modelling assumption phrased as a bug fix — a walker at a dead end is assumed to behave exactly as a bored walker does. A chain with no stationary vector measures what happens without the repair, and what the repair is doing.

Where 0.85 comes from #

It is worth saying plainly: nowhere in particular.

The value is the one in the original paper, chosen because it converges fast enough and gives plausible results. It is not the outcome of an optimisation, there is no data-driven rule for selecting it, and no criterion analogous to the regularisation field’s discrepancy principle or L-curve has been widely adopted for it.

That is not a criticism of the choice — a parameter that has to be set and has no principled setting is an ordinary situation, and this site has a whole field about how badly the principled rules for that problem perform when they are scored. It is a criticism of how the number is reported. A ranking published without its α is a ranking published without half its definition, and the table above is what that half is worth.

The cost is a function of α too #

The parameter that decides the answer also decides what it costs, and in the unhelpful direction: more graph and less prior means slower convergence.

The Google matrix’s second eigenvalue is α·λ₂(P), so the power iteration contracts by that factor a step. On a link graph with more than one closed communicating class — which every real one has — λ₂(P) is exactly 1 and the rate is exactly α. Reaching 10⁻¹⁵ then takes log(10⁻¹⁵)/log(α) steps: 121 at α = 0.75, 212 at α = 0.85, 3,436 at α = 0.99.

On that arithmetic the answer at α = 0.99 costs sixteen times the answer at α = 0.85, and it is a different answer rather than a better one. The second half of that sentence is right and the sixteen is not, which the next section measures. That is the shape this site keeps finding in parameter choices — four knobs and one floor makes the general version — and it is particularly stark here because the cost and the answer move together with nothing to trade them against.

The measured rate is α·λ₂(P) to four digits at every stop. At α = 0.5, 0.7, 0.85, 0.9 and 0.95 the contraction comes out 0.4509, 0.6314, 0.7668, 0.8121 and 0.8571 against α·0.9024 = 0.4512, 0.6317, 0.7670, 0.8122 and 0.8573 — the product, not the parameter, and not approximately.

Which prices the parameter properly, and the published arithmetic overstates it. The iteration counts are 36, 63, 137 and 186 across α = 0.5 to 0.95 — a factor of 5.2 — where the α-only formula would predict log(10⁻¹⁵)/log α going from 50 to 673, a factor of 13. The λ₂ < 1 of a connected graph is worth more at the top of the range than at the bottom, because α·λ₂ is further from one than α is and the log of a ratio near one is what the count depends on.

So the rate on this site’s connected test graphs is not α but α·λ₂(P), which is smaller, because a connected undirected graph has λ₂(P) < 1. That discrepancy is the subject of the next essay, and it is the reason the published rate is right: not because the analysis is tight, but because the graph is disconnected.

What the parameter actually costs #

The sixteen is a ratio of two formulas and the essay has already reported a measurement that contradicts it: the two-routes table near the top of this page shows 46 iterations at α = 0.85 and 58 at α = 0.99, a ratio of 1.26. Both cannot be right.

Run to 10⁻¹⁵ on every graph family this site builds for the purpose:

Nothing gives sixteen, and two separate things are wrong with it.

The rate is diluted. On a connected graph the contraction is α·λ₂(P) rather than α, which is the next essay’s subject. At λ₂ = 0.902 the rate moves from 0.767 to 0.893 as α moves from 0.85 to 0.99 — a much smaller relative change than α’s own, because the λ₂ factor is fixed — so the iteration counts move by 2.3 rather than by 16.

And the count is the asymptote plus a constant. This one holds even on the reducible graph, where the folk rate is exactly right. The step count is log(tol)/log(1/rate) plus an offset that depends on where the iteration started, and the offset does not scale with the first term. Measured on the two islands: 176 steps against a predicted 213, and 1,743 against a predicted 3,437. The ratio of the counts is 9.9 where the ratio of the predictions is 16.2, and the discrepancy is largest exactly where the prediction is largest. That is the same additive offset the mixing-time essay measures, arriving in the place where it is most misleading — a ratio, where a constant that looks harmless in one term does not cancel.

So the sixteen is between four and thirteen times too large depending on which graph a reader has, and it is the graph rather than the parameter that decides. assertTheCostRatioIsNeverSixteen holds that the formula does give sixteen, that every graph costs more at the larger α, that none of them costs more than seven-tenths of the sixteen, that the reducible one is the dearest by more than a factor of two over any connected one, and that on the graphs the two-routes table was measured over the parameter costs almost nothing.

There is a reading of the table that goes the other way and is worth stating, because it is the practical one. The graphs on which α is nearly free are the well-connected ones, and the graph on which it is expensive is the reducible one — which is the shape a real link graph has. So a practitioner reading the connected-graph numbers and concluding that α is cheap would be drawing the wrong lesson from the right measurement: the 1.22 belongs to a forty-node graph with a handful of dangling pages, and the 9.90 belongs to the family the parameter was invented for. The correction here is to the arithmetic, not to the advice.

None of which weakens the section it corrects. The argument there is that α decides the answer and the cost together, with nothing to trade them against, and that survives: the cost still rises monotonically with α on every graph tested, and the answer still changes. What was wrong was the size, and the size mattered — sixteen is the difference between a parameter with a price and a parameter nobody can afford to raise, and the honest number is the first.

What the eigenvector is guaranteed to be #

Two properties come free from Perron–Frobenius, and they are worth naming because the second is usually assumed rather than checked.

The eigenvalue is exactly 1. G is column-stochastic — every column sums to one, by construction — so 1ᵀG = 1ᵀ and the spectral radius is 1 with the left eigenvector known. No computation is needed to find the eigenvalue, which is why the power iteration needs no normalisation beyond keeping the sum at one.

The eigenvector is positive. G has every entry strictly positive when v is, so Perron’s theorem applies in its strongest form: the leading eigenvalue is simple and its eigenvector is strictly positive. That is what makes the answer a distribution rather than a vector with signs in it.

The second of those is a theorem about real numbers and the computation is not performed in real numbers. An eigenvector that must not change sign is what happens when the entries a theorem guarantees to be positive fall below the level the arithmetic can represent them at — on a graph with a long tail, four of thirty-six entries of a strictly positive vector come back negative.

What the second route costs, and why it is worth having anyway #

The elimination route is not competitive at scale and it is worth being precise about why, because the reason is not the one people usually give.

Forming I − αP̃ densely is out of the question for a graph of any size, but nobody would: P̃ is sparse, and a sparse direct solve on it is exactly the fill problem this site has a field about. A web graph’s elimination fills catastrophically — its structure has none of the locality that makes a mesh’s elimination affordable — so a sparse LU is not merely slower than the power iteration, it does not finish.

What the elimination gives that the iteration does not is a check. The power iteration has one failure mode that looks exactly like success: stopping early. Its stopping test compares successive iterates, and successive iterates of a slowly converging iteration are close together for the same reason the answer is far away. At α = 0.99 the contraction is 0.99 a step, so a run stopped when the change falls below 10⁻⁸ is still 10⁻⁶ from the answer — the error is the change divided by (1 − α), which is a hundred here and would be ten thousand at α = 0.9999.

That is not a hypothetical: the factor 1/(1 − α) is the condition number of I − αP̃, and it is the same number in both readings. Which is the point of computing the answer twice on a graph small enough to afford both. The agreement at 4·10⁻¹⁷ in the table above is what says the stopping test was not the thing being measured.

The vector nobody looks at #

A last observation about what is actually consumed.

The stationary vector has n entries, each a probability, and on a large graph almost all of them are within a small factor of 1/n. Nobody reads them. What is read is the order, and usually only the top of it.

That changes which computations are worth doing. Accuracy in the entries is not accuracy in the order: two entries that differ by 10⁻⁸ are ordered by digits far below the level anything else in the pipeline is accurate to, and no amount of iterating settles a comparison that the data does not settle. Conversely, an entry accurate only to 10⁻⁴ is perfectly adequate if the pages either side of it are 10⁻³ away.

So the question “how accurately should PageRank be computed” has no answer without the ranking in hand, which is a nuisance and is honest. The ranking essay turns it into a measurement: how many of the top comparisons are settled by the data, and by what.

What to report with a ranking #

Four things follow from the measurements above, and none of them costs more than a line of output.

α, always. The top five change across the ordinary range of it. A ranking without its teleportation parameter is a ranking whose definition is incomplete, in the same way that a regularised solution without its parameter is.

The teleport vector, if it is not uniform. The answer is a linear function of it, so a personalised ranking and a plain one are different objects and the difference is not small.

The stopping criterion, converted. The change between iterates is the quantity a run measures and it is not the error; the error is that change divided by 1 − α. Reporting the change alone understates the error by a hundred at α = 0.99 and by ten thousand at α = 0.9999, and the conversion is one division.

And how the dangling nodes were handled. Every implementation makes an assumption there, most of them make the same one, and the assumption is a statement about what a walker at a dead end does rather than a numerical detail.

None of that makes a ranking more accurate. It makes it a statement somebody else can reproduce, which is a different property and — on the evidence of the α table — the scarcer one.