PageRank Through the Lens of Grammar

16.1 The surfer as a grammar

The random surfer of Chapter 15 has two moves, follow and teleport, applied at random. As an operational grammar its states are pages, its moves are relations — follow maps $u$ to its out-neighbours, teleport maps $u$ to every page — and its semantics is probabilistic: each move carries a probability distribution over successors instead of a set. The PageRank vector is the long-run frequency with which the moves’ composition visits each page. Nothing is gained by renaming the model; the reason to read it this way is that the operational-grammar toolkit of Part II — and in particular admissibility languages and the product construction — applies to it directly.

16.2 Constraining the surfer

On a graph whose links carry labels (a citation that supports or refutes, a link between people that is colleague or family, a hyperlink in navigation or content), one may want a ranking driven only by certain patterns of links. Admissibility languages express such patterns, and the product construction of Chapter 8 turns them into a Markov chain.

The status badge reads proposed: the model is defined here, its properties are elementary, and its novelty is unknown. Products of Markov chains with automata are standard in probabilistic model checking [Baier & Katoen 2008], and similarity measures driven by label patterns (“meta-paths”) are established for heterogeneous information networks [Sun et al. 2011]; whether this exact ranking model has been published is an open literature question (CGT-OPEN-011).

import random
from cgtsdk import DFA, Cost, compile_regex
from cgtsdk.algorithms import constrained_pagerank, pagerank_power

rng = random.Random(10)
n = 2000
E = [(u, rng.choice("abc"), int(rng.random() ** 2 * n)) for u in range(n) for _ in range(rng.randrange(0, 7))]
E = [(u, a, w) for (u, a, w) in E if u != w]
adj = [[] for _ in range(n)]
for u, _, w in E:
    adj[u].append(w)
plain_cost = Cost()
plain = pagerank_power(adj, 0.85, tol=1e-10, cost=plain_cost)
top = lambda s: [i for i, _ in sorted(enumerate(s), key=lambda t: (-t[1], t[0]))[:10]]
for name, dfa in [("universal", DFA.universal("abc")), ("no c: (a | b)*", compile_regex("(a | b)*")),
                  ("alternate: (a b)* (a | ε)", compile_regex("(a b)* (a | ε)"))]:
    c = Cost()
    scores, res, N = constrained_pagerank(n, E, dfa, 0.85, 1e-10, cost=c)
    l1 = sum(abs(x - y) for x, y in zip(scores, plain.scores))
    print(f"{name:26s} |Q|={dfa.size}  product states={N:5d}  cost ratio={c.counts['edge'] / plain_cost.counts['edge']:.2f}"
          f"  top-10 overlap={len(set(top(scores)) & set(top(plain.scores)))}  L1 distance={l1:.3f}")

universal                  |Q|=1  product states= 2000  cost ratio=1.03  top-10 overlap=10  L1 distance=0.000
no c: (a | b)*             |Q|=1  product states= 2000  cost ratio=0.80  top-10 overlap=7  L1 distance=0.338
alternate: (a b)* (a | ε)  |Q|=2  product states= 3118  cost ratio=0.67  top-10 overlap=8  L1 distance=0.411

The universal language reproduces PageRank exactly, at a small overhead for building the product. A one-state language that forbids c links is cheaper than PageRank (fewer admissible edges), is at $L_1$ distance $0.34$ from it — so about $17\%$ of the probability mass moves, since $L_1$ distance is twice the total-variation distance — and changes three of the top ten pages; the alternating language uses about $1.6 n$ product states, moves about $21\%$ of the mass and changes two of the top ten. The ledger’s experiment (CGT-EXP-010) found the same pattern on other graphs and languages, with costs from $0.46\times$ to $6.4\times$ PageRank, and validated each constrained ranking against a direct linear solve of the materialized product chain (CGT-OBS-018).

16.3 Block structure as a structural grammar

Web graphs are not random: most links stay within a host. BlockRank exploits this by computing local rankings inside hosts, combining them by host importance, and using the result to start a global power iteration, reporting a speed-up by a small factor [Kamvar et al. 2003]. In this book’s taxonomy the host partition is a structural grammar of the graph (a two-level grammar: hosts, then pages), and the method combines M-SHARE (local computations reused as a starting vector), ordering, and M-PRE (warm starts). The general lesson of Chapter 15 applies: power iteration’s cost per iteration is invariant under reordering, and what structure buys is a better starting point or a better sweep order for Gauss–Seidel-like methods — and fewer cut edges when the graph is distributed.

16.4 What the grammatical view does not provide

It is important to be explicit:

• No faster PageRank. Every iteration still reads every admissible edge. The constrained surfer can be cheaper than PageRank only because it ranks a different, smaller chain.
• No change to convergence theory. Rates, bounds and solver behaviour are those of Chapter 15.
• No evidence about ranking quality. See the boundary above.
• No claim about production search. Modern search engines rank with many signals beyond link analysis; nothing here addresses them.

What it does provide is a uniform way to state constrained and structured link analyses — as languages over link labels and grammars over graph structure — together with cost bounds that follow from the product construction rather than having to be derived afresh for each variant. Related ranking problems — personalized and topic-sensitive rankings [Haveliwala 2002], hub-and-authority methods, ranking in heterogeneous networks [Sun et al. 2011] — fit the same pattern, and are directions rather than results of this book.

Report an erratum or an unclear passage in this chapter