A chain with no stationary vector

The definition of PageRank asks for the stationary distribution of a Markov chain. Perron–Frobenius guarantees one exists and is unique — provided the chain is irreducible and aperiodic, and provided its transition matrix is stochastic.

A link graph satisfies none of those three. This essay measures what each failure does, and what the standard repair for it is actually assuming.

The matrix is not stochastic #

A page with no outgoing links contributes a column of zeros. Its column does not sum to one, so the matrix is sub-stochastic, and a walker that arrives there disappears.

Measured directly — the total probability remaining after six hundred steps of the unrepaired iteration on an eighty-page graph:

dangling pages    mass remaining after 600 steps
 0                   1.000
 2                   0.860
 6                   0.672
12                   0.521
20                   0.402

Six dead ends out of eighty cost a third of the probability. Twenty cost sixty per cent. And the loss is not a transient — the iteration is a contraction towards zero, so the vector goes on shrinking for as long as it is run, and every entry shrinks with it.

The rank ratios survive, which is why this can go unnoticed for a long time: a vector shrinking uniformly gives the same ordering. What does not survive is any comparison against a threshold, any sum over a subset, and any statement of the form “this page has 0.4% of the total rank” — because the total is 0.402 and falling.

What the repair assumes #

Every implementation repairs it, and almost all of them the same way: a dangling page’s mass is redistributed according to the teleport vector, which amounts to replacing its empty column with v.

That is a modelling assumption dressed as a bug fix. It says: a walker at a dead end behaves exactly as a bored walker does. It might; it might equally be assumed to stay where it is (replace the column with an indicator, making the page absorbing), or to go back where it came from, or to be removed from the graph before the computation and reattached afterwards.

Those give different answers. They are not close variants of one method; they are four different chains, and which one is being solved is decided by a line in an implementation that usually has no comment on it. The repaired iteration conserves mass exactly — measured at 1.000000000000 for every dangling count above — so nothing downstream reports that a choice was made.

This is the shape the regularisation field is about, arriving in a place where nobody calls it that. The data does not determine the answer, something outside it has to, and the choice is the computation rather than a preliminary to it.

The chain is periodic #

A chain is periodic when its states can be partitioned into groups the walker cycles through in order. On a directed cycle that is the whole graph: from vertex k the walker goes to k + 1 and nowhere else, so its position at time t is determined modulo the cycle length by where it started.

Such a chain has no limiting distribution. Its transition matrix is a permutation matrix, every eigenvalue is on the unit circle, and the iterate rotates forever without settling.

Teleportation is supposed to fix this, and it does, at a rate that is exactly α:

α           iterations to a change below 10⁻¹²
0.85            163
0.99            did not converge in 2,000 — change still 3.4·10⁻¹¹
0.999999        did not converge in 2,000 — change still 1.8·10⁻⁶

At α = 0.85 the chain converges in a hundred and sixty steps. At α = 0.999999 it does not converge in two thousand, because the contraction is 0.999999 a step and two thousand steps buy a factor of 0.998.

So the repair works and its strength is exactly the parameter. As α approaches one — which is the direction “use more of the graph and less of the prior” points in — the repair weakens, and in the limit it is not there at all. That is not a numerical difficulty to be worked around; it is the statement that the object being approached does not exist.

The chain is reducible, and this is the important one #

A chain is reducible when some states cannot be reached from others. Every real link graph is: there is a large strongly connected core, a set of pages that link into it and are not linked back, and a set that it links to and which link nowhere.

The consequence is not subtle, and it is best seen on a graph built to have it. Sixty pages in two halves, with links from the first half into the second and none back:

α          rank in the source half     rank in the sink half
0.500            0.333333                  0.666667
0.850            0.130435                  0.869565
0.990            0.009901                  0.990099
0.999            0.000999                  0.999001

The last column is 1 − α to every digit shown.

The entire rank of half the graph is the teleportation parameter. Not approximately, not asymptotically — the total probability the walker spends in the upstream half is exactly the probability that it teleported there recently, because that is the only way to be there. The link structure of that half contributes nothing to its total, and as α rises towards the value that is supposed to mean “trust the links more”, the upstream half’s rank goes to zero.

That is the case where reading PageRank as “importance according to the link structure” fails completely. Half the graph’s importance is a constant somebody typed, and the graph’s own structure decides only how that constant is divided within the half.

And α is not only setting the answer here — it is setting the rate as well, for the same reason. On a reducible chain the second eigenvalue of P is exactly 1, because each closed part carries its own stationary vector and the pair spans a two-dimensional invariant subspace at eigenvalue one. So the damping is not merely improving the contraction, it is supplying it: the iteration contracts at α and at nothing else.

The two readings of α are therefore in direct opposition, and the measurement prices it. Raising α from 0.5 to 0.9 is meant to mean trust the links more. What it does on this graph is drive the upstream half’s total rank from 0.333 to 0.100 — less of the answer decided by the links, not more — while multiplying the iteration count by six. The parameter that is supposed to buy fidelity to the link structure is, on a reducible graph, buying the opposite at a cost that grows as 1/(1 − α).

The three failures are not equally visible #

It is worth ranking them by how likely each is to be noticed, because the ordering is the reverse of how much attention each gets.

Dangling pages are noticed. The mass falls, and any implementation that prints a total sees it immediately. They are also the failure every account of the method mentions, and the repair is in every implementation.

Periodicity is almost never noticed, because it is almost never present. A real link graph has short cycles everywhere and is aperiodic without any help; the directed cycle above is a constructed object. The repair is free, so nobody minds, but the emphasis it receives in expositions is out of proportion to how often it matters.

Reducibility is present in every real graph and is not noticed at all, because there is no symptom — in the way an undetermined ranking has none either. The iteration converges, the mass is one, the vector is positive, the ordering looks sensible, and every diagnostic reports success. The only way to see it is to compute the strongly connected components — which nobody does, because the method does not require it.

So the failure that is universal and consequential is the one with no symptom, and the two with symptoms are the ones that get the attention. That is a pattern this site has seen: the gate that found fifty-two orphaned pages found them because it asked whether something existed rather than whether something was correct, and every other check asked the second question.

Why this is a property of link graphs specifically #

An undirected graph, whose Laplacian is the object this field started from, cannot be reducible in this way — if there is an edge from A to B there is one from B to A, so every connected component is strongly connected, and a walk restricted to one component has a perfectly good stationary distribution, which is its degree distribution.

Directedness is what creates the sink, and a link is directed. So this failure mode is not an awkward special case of the theory; it is the ordinary structure of the object the method was invented for. The convergence-rate measurement two essays ago is the other side of the same fact: λ₂(P) = 1 exactly because the graph has more than one closed class, and the published convergence rate is right for that reason.

One phenomenon, two consequences. The rate quoted everywhere is correct because the graph is reducible, and the answer for a large part of the graph is meaningless for the same reason.

The three repairs are one repair #

It is worth noticing that teleportation fixes all three problems and is the only thing that does.

Replacing a dangling column with v makes the matrix stochastic. Mixing in (1 − α)v1ᵀ makes every entry positive, which makes the chain irreducible — every page is reachable from every other in one step — and aperiodic, since a positive matrix has no periodic structure. Perron’s theorem then applies in its strongest form: the leading eigenvalue is simple, its eigenvector is strictly positive, and the power iteration converges from any start. The Collatz–Wielandt bracket comes with it — a two-sided enclosure of the eigenvalue from one matrix–vector product, which for the Google matrix says only that the answer is one, and which on an adjacency matrix is the rarest thing on this site.

That economy is the reason the construction is so widely used and it is also why the assumption inside it is so easy to miss. One parameter buys existence, uniqueness, convergence and a rate, and the price is that the answer is a mixture of the graph and a prior in a proportion nobody derived.

What a run should report #

Four numbers, none of which is expensive, and all of which are missing from a typical output.

The number of dangling pages and how they were handled. It is a line of the input’s statistics and a line of the implementation’s, and together they say which of four chains was solved.

The fraction of rank in each closed class. If the graph has a sink that absorbs 99% of the rank at α = 0.99, that is worth knowing before the top ten is read. It costs one strongly-connected-components pass, which is linear.

α, and the error converted. The previous essay makes the case for the first; the second is that the change between iterates underestimates the distance to the answer by 1/(1 − α), which at α = 0.99 is a factor of a hundred.

And whether the iteration converged at all. The α = 0.999999 row above did not, and the only symptom is a change between iterates that is small because the contraction is slow. A run that stops on a change threshold cannot distinguish “converged” from “barely moving”, and the two look identical in every diagnostic the iteration produces.

A note on what “converged” is being measured against #

One more quiet failure belongs here, because it is the one that makes the periodic row of the table above hard to read from inside a run.

The stopping test compares successive iterates. On a chain that is converging slowly the successive iterates are close together because it is converging slowly, so the test’s quantity is small for the same reason the answer is far away. The relationship is exact: for a contraction of factor r, the distance remaining is the change divided by 1 − r.

At α = 0.85 that factor is about seven and nobody is misled. At α = 0.999999 it is a million, so a run stopped when the change falls below 10⁻¹² is 10⁻⁶ from the answer — which is precisely the row of the table that says the iteration did not converge, seen from a stopping test that would have said it had.

The repair looks like a division, and it needs a number the run already has: the observed contraction over the last several steps. Reporting the change alone is the default because it is what the loop computes, and converting it costs nothing.

The identity behind it is exact for a positive real subdominant eigenvalue. With error_k = c λᵏ v the change is error_k(1 − λ), so the distance really is change/(1 − λ). For any other λ the divisor should be |λ − 1|, and the two are the same number only when λ is positive. Measured on a nearly reducible chain, stopping when the max-norm change first falls below 10⁻⁹:

The change is already an over-estimate of the remaining distance — by a factor of 2.03 at the tight end, which is the opposite of the direction the warning above is about. And the correction makes it worse: dividing by 1 − r turns a two-fold over-estimate into a sixty-eight-fold one.

The reason is measurable in one line. Late in the run the successive change vectors have a cosine of −1.0000 with each other — exactly anti-parallel — so λ₂ is negative and near −0.97. The right divisor is |λ − 1| ≈ 1.97 and the formula uses 1 − |λ| ≈ 0.03; they differ by about 2/(1 − r), which is the sixty-eight.

So the repair is right about the shape and wrong about the sign, and the fix for the fix is free: look at whether successive changes point the same way. One inner product says whether the divisor is 1 − r or about two. A run that does not look will over-estimate its remaining error by the whole of 1/(1 − r) on any chain that oscillates — which is every chain whose subdominant eigenvalue is negative, and a nearly bipartite or nearly reducible structure is exactly what produces one.

That does not rescue the α = 0.999999 row of the table, and it changes what is wrong with it. The iteration there is not stopping early because its change under-states the distance; it is failing to converge at all, which is a different complaint and the one the refusal below is written for.

What the refusals are for #

Three assertions in this field are fed cases they must reject, and they are the three failures above.

The first is handed α = 1 — the chain itself, with no teleportation — and must refuse, because the chain has no unique stationary distribution on any graph with more than one closed class. The second is handed the directed cycle at α = 0.999999 and required to declare convergence, which it must refuse because the iterate is still 1.8·10⁻⁶ from settled. The third is handed an unrepaired link matrix and required to conserve probability, which it must refuse because forty per cent of it has gone.

Each of those runs on every build. That matters more here than in most of this collection, because the failures are all quiet: an unrepaired matrix returns a plausible ranking, a periodic chain returns a plausible vector, and a reducible one returns a ranking whose upstream half is a constant. None of them throws, and an assertion that has never been fed the case it must refuse would not have noticed any of them.

What a sink does to the top of the list #

The reducibility measurement above is about totals, and a reader who only looks at the top ten might reasonably ask whether it matters to them.

It does, and in a direction that is easy to get backwards. The rank mass concentrates in the sink, so the top of the list is drawn from the sink — pages that are linked to and link nowhere. Those are, in a web graph, exactly the terminal documents: a PDF, an image page, a redirect target, a page whose outgoing links were never crawled.

So the highest-ranked pages under a large α are systematically the pages the crawl knows least about. That is not a bug in the arithmetic and it is not a bug in the definition; it is what “spends the most time here” means for a walker on a graph with sinks in it. A ranking read as importance has acquired a bias towards terminality, and the size of the bias is set by α.

The usual repairs are outside the linear algebra: treat uncrawled pages as dangling and redistribute them, restrict the computation to the strongly connected core, or damp more heavily. Each changes the answer. None of them is more principled than the others, and the choice between them is made in the same place as every other choice in this essay — an implementation detail with no comment on it.

What survives #

The reassuring half, stated last because it is genuinely reassuring: the repaired computation is correct, well conditioned and cheap, and the two routes to it agree at 4·10⁻¹⁷.

Nothing in this essay is about the arithmetic. Every measurement here would come out the same in exact arithmetic, because every one of them is about which chain was solved rather than about how well it was solved. That is unusual for this site and it is the field’s characteristic shape: when the answer is discrete, or is read as an order, or is a probability whose total is checked, the questions that matter move from the arithmetic to the model, and the arithmetic is the part that works.