Случайные блуждания и PageRank

Поисковая система видит не «важные страницы», а огромный ориентированный граф. PageRank превращает структуру ссылок в вероятностный эксперимент: где окажется читатель, если очень долго переходить по ссылкам и иногда начинать путь заново? Ответ — стационарное распределение цепи, и почти вся инженерия метода состоит в том, чтобы это распределение существовало, было единственным и считалось быстро.

Голоса, которые имеют разный вес

Пусть каждая веб-страница является вершиной, а гиперссылка — ориентированным ребром. Уже здесь возникает отличие от школьного голосования. Страница $A$, на которую ссылаются сто никому не известных каталогов, не обязательно важнее страницы $B$, на которую ведёт одна ссылка с главной страницы университета. Голос сам имеет вес, а этот вес ещё только предстоит найти.

Формально мы хотим числа $\pi_i\ge 0$, удовлетворяющие рекурсивному условию: важность страницы складывается из важностей тех, кто на неё ссылается, поделённых на число их исходящих ссылок,

$$\pi_j=\sum_{i\to j}\frac{\pi_i}{d_i},$$

где $d_i$ — исходящая степень вершины $i$. Определение выглядит порочным кругом: чтобы узнать $\pi_j$, надо знать $\pi_i$. Весь урок — рассказ о том, почему этот круг не порочен, а разрешим, и что именно превращает его в корректную задачу о собственном векторе.

Матрица переходов и один шаг читателя

Если из вершины $i$ выходит $d_i$ ссылок, простейший случайный читатель выбирает каждую с вероятностью $1/d_i$. Переходы задаёт строко-стохастическая матрица

$$P_{ij}= \begin{cases} 1/d_i,&\text{если }i\to j,\\ 0,&\text{иначе}, \end{cases} \qquad \sum_j P_{ij}=1 .$$

Вектор-строка $p_t$ хранит вероятности положения после $t$ кликов, поэтому

$$p_{t+1}=p_tP,\qquad p_t=p_0P^{\,t}.$$

Эта формула связывает тему с цепями Маркова, а способ многократно умножать вектор на матрицу — со степенным методом для собственных векторов. Никаких меток «хорошая страница» алгоритм не получает. Ранг рождается из геометрии графа и правила движения.

Возьмём три страницы: $A$ ссылается на $B$ и $C$, $B$ — только на $C$, $C$ — только на $A$. Тогда

$$P=\begin{pmatrix} 0&\tfrac12&\tfrac12\\ 0&0&1\\ 1&0&0 \end{pmatrix},$$

и из $p_0=(1,0,0)$ три шага дают

$$p_1=\left(0,\tfrac12,\tfrac12\right),\quad p_2=\left(\tfrac12,0,\tfrac12\right),\quad p_3=\left(\tfrac12,\tfrac14,\tfrac14\right).$$

Никакой мистики: масса просто растекается по стрелкам, деля себя поровну на каждой развилке.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Неподвижное распределение

Если после долгого движения распределение перестаёт заметно меняться, его предел $\pi$ удовлетворяет

$$\pi=\pi P,\qquad \pi_i\ge 0,\qquad \sum_i\pi_i=1.$$

Это левый собственный вектор матрицы $P$ для собственного числа $1$. Компонента $\pi_i$ имеет ясный частотный смысл: доля времени, которую длинная траектория проводит на странице $i$. В отличие от отдельной прогулки, стационарное распределение описывает весь поток сразу.

Для нашего примера баланс потоков даёт систему

$$\pi_A=\pi_C,\qquad \pi_B=\tfrac12\pi_A,\qquad \pi_C=\tfrac12\pi_A+\pi_B,$$

и после нормировки $\pi_A+\pi_B+\pi_C=1$ получаем

$$(\pi_A,\pi_B,\pi_C)=(0{,}4;\ 0{,}2;\ 0{,}4).$$

Входящая степень у $C$ равна двум, а у $A$ — единице, но один из входов $C$ несёт только половину потока. Поэтому просто считать ссылки недостаточно — тезис, к которому мы вернёмся уже на настоящих данных.

Это редкий случай, когда инженерная метафора и математический объект совпадают буквально: «становится скучно» — это телепортация, «нажимает на ссылки» — это матрица $P$, а «доля времени на странице» — это $\pi$.

Тупики: куда утекает вероятность

Реальный граф неудобнее учебного. У страницы без исходящих ссылок строка матрицы состоит из нулей, и суммарная вероятность перестаёт сохраняться. Возьмём цепочку $A\to B\to C$, где у $C$ выходов нет, и стартуем с равномерного $p_0=(1/3,1/3,1/3)$. Суммарная масса $\sum_i p_{t,i}$ падает по шагам как

$$1\ \longrightarrow\ \tfrac23\ \longrightarrow\ \tfrac13\ \longrightarrow\ 0 .$$

Через три шага «читателей» не остаётся вовсе: они провалились в тупик и исчезли из модели. Формально $P$ перестала быть стохастической — это субстохастическая матрица, и единственный её неотрицательный предел нулевой.

Лечение прямое: нулевую строку заменяют на распределение $v$ — равномерное или заданное. Читатель, попавший в тупик, просто начинает заново. В нашем реальном графе такая починка понадобится $24$ раза — ровно столько там вершин без исходящих рёбер.

Ловушки: когда ответ перестаёт быть единственным

Вторая неприятность тоньше. Группа страниц может ссылаться только друг на друга. Попав внутрь такого замкнутого множества, случайный читатель больше не выйдет: множество поглощающее. Тогда предел зависит от начальной точки, а несколько стационарных распределений конкурируют между собой.

Возьмём шесть вершин: $A\to B\to C$, $C\to A$ и $C\to D$, а внутри — цикл $D\to E\to F\to D$. Стартуя с равномерного распределения и не применяя никакой телепортации, после четырёхсот шагов мы получаем

$$\pi_D+\pi_E+\pi_F=1{,}000,$$

то есть весь поток оказался в ловушке, а вершины $A,B,C$ обнулились. Спам-фермы начала двухтысячных эксплуатировали именно это: достаточно построить плотный клубок страниц, ссылающихся только внутрь, чтобы накопить в нём весь ранг.

Телепортация чинит обе болезни сразу

PageRank смешивает следование ссылкам со случайным перезапуском:

$$G=\alpha P+(1-\alpha)\,\mathbf 1v^\top,\qquad 0<\alpha<1,$$

то есть

$$p_{t+1}=\alpha\,p_tP+(1-\alpha)\,v .$$

С вероятностью $\alpha$ читатель нажимает ссылку, а с вероятностью $1-\alpha$ выбирает новую страницу по вектору интересов $v$. При положительных компонентах $v$ из любой вершины можно попасть в любую другую за один прыжок, и матрица $G$ становится строго положительной.

На графе с ловушкой при $\alpha=0{,}85$ ранг перестаёт быть вырожденным: в ловушке остаётся $0{,}763$ вероятности вместо всей, а вершины снаружи получают $\pi_A=0{,}0644$, $\pi_B=0{,}0798$, $\pi_C=0{,}0928$; внутри ловушки $\pi_D=0{,}2689$, $\pi_E=0{,}2536$, $\pi_F=0{,}2405$. Заметьте: перекос не исчез — он стал конечным. Телепортация не объявляет ловушку несуществующей, она лишь мешает ей забрать всё.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Сходимость: почему всё держится на альфе

Пусть $p$ и $q$ — два распределения. Один шаг PageRank не увеличивает расстояние между ними больше чем в $\alpha$ раз:

$$\lVert\bigl(\alpha pP+(1-\alpha)v\bigr)-\bigl(\alpha qP+(1-\alpha)v\bigr)\rVert_1 =\alpha\lVert (p-q)P\rVert_1\le\alpha\lVert p-q\rVert_1 .$$

Отображение сжимающее с коэффициентом $\alpha$, значит по теореме о неподвижной точке решение единственно, а ошибка убывает геометрически:

$$\lVert p_t-\pi\rVert_1\le 2\alpha^{\,t}.$$

Чтобы получить точность $\varepsilon$, достаточно

$$t\ \ge\ \frac{\ln(2/\varepsilon)}{\ln(1/\alpha)}$$

итераций. Это и есть весь секрет масштабируемости: число шагов не зависит от размера графа — только от $\alpha$ и требуемой точности.

На нашем реальном графе счёт до порога $\lVert p_{t+1}-p_t\rVert_1<10^{-12}$ занимает $40$ итераций при $\alpha=0{,}70$, $57$ при $0{,}85$ и $75$ при $0{,}95$. Практика оказалась лучше теории: у матрицы $G$ второе по модулю собственное число равно $0{,}6314$, а не $0{,}85$ — граф хорошо перемешан, и реальная скорость определяется именно этой величиной, $\lVert p_t-\pi\rVert\sim|\lambda_2|^{\,t}$.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Как это считают на миллиарде страниц

Для миллиарда страниц нельзя хранить плотную матрицу $10^9\times10^9$: это $10^{18}$ чисел. Но веб-граф разрежен, каждая страница содержит лишь небольшое число ссылок. На одной итерации достаточно пройти по списку рёбер и распределить массу $p_i$ между соседями:

$$q_j\ \mathrel{+}=\ \alpha\frac{p_i}{d_i}\ \ \text{для каждого ребра } i\to j, \qquad q\ \mathrel{+}=\ (1-\alpha)v .$$

Цена шага близка к $O(|E|)$, память — $O(|V|+|E|)$. В нашем учебном графе плотная матрица заняла бы $146\,689$ клеток, а список рёбер — всего $3582$ записи: в $41$ раз меньше. На веб-масштабе выигрыш становится вопросом принципиальной возможности счёта, а не удобства; та же логика цены матричных операций разбиралась в уроке о стоимости умножения матриц.

Живой граф: фильмы вместо страниц

Настоящего снимка веба у нас под рукой нет, зато есть реальные данные о поведении людей: MovieLens 100K — сто тысяч оценок, поставленных $943$ зрителями. Построим из них честный ориентированный граф. Скажем, что фильм $i$ ссылается на фильм $j$, если из тех, кто поставил $i$ оценку не ниже четырёх, не менее $60\%$ поставили не ниже четырёх и фильму $j$:

$$\mathbb P(j\ \text{нравится}\mid i\ \text{нравится})\ \ge\ 0{,}6 .$$

Это условная вероятность, и она несимметрична: из того, что почти все поклонники нишевого фильма любят блокбастер, не следует обратное. Именно поэтому получается ориентированный граф, а не сеть похожести. Взяв фильмы, набравшие хотя бы $45$ поклонников, получаем $383$ вершины и $3582$ ребра: средняя исходящая степень $9{,}35$, максимальная входящая — $332$, и $24$ вершины оказались тупиками, у которых ни один другой фильм не собирает шестидесяти процентов их аудитории.

Ранг против входящей степени

Теперь главный эксперимент урока. Считаем PageRank при $\alpha=0{,}85$ и равномерном $v$, а рядом — обычный подсчёт входящих ссылок. По всему списку ранговая корреляция Спирмена (со связными рангами: входящих степеней с совпадающими значениями много) высока, $\rho=0{,}996$: в целом популярное остаётся популярным. Но интересна вершина списка, и там согласия нет.

Первое место по числу входящих ссылок занимает Star Wars (1977) с $332$ входами. Первое место по PageRank занимает Return of the Jedi (1983), у которого входов почти вдвое меньше — $177$, зато

$$\pi_{\text{Jedi}}=0{,}2381>\pi_{\text{Star Wars}}=0{,}2169 .$$

Почему? Смотрим на исходящие рёбра. У Star Wars исходящая степень равна единице: единственный фильм, который любят шестьдесят процентов её поклонников, — это как раз Return of the Jedi. Значит вся полученная масса

$$\alpha\,\pi_{\text{Star Wars}}\cdot\frac{1}{1}=0{,}85\cdot0{,}2169=0{,}1844$$

уходит одному адресату. А сам Jedi имеет две исходящие ссылки и делит свой поток пополам, по $0{,}5$ каждому. Побеждает не тот, у кого больше входов, а тот, кому достаётся более концентрированный поток от сильных соседей.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Разброс рангов огромен: от $\pi_{\min}=0{,}00043$ до $\pi_{\max}=0{,}23809$, отношение $554{,}4$. Список из десяти лучших по степени и десяти лучших по PageRank совпадает на девяти позициях из десяти — и всё же расходится там, где решение важнее всего, на первом месте. Именно поэтому спор «зачем считать собственный вектор, если есть счётчик ссылок» решается не корреляцией по всей выборке, а поведением верхушки.

Персонализация и её линейность

Вектор $v$ не обязан быть равномерным. Сосредоточим всю телепортацию на $41$ фильме с жанровой меткой Sci-Fi:

$$v_i=\frac{\mathbb 1\{i\in \text{Sci-Fi}\}}{41}.$$

Первая пятёрка меняет не только числа, но и состав. Return of the Jedi поднимается с $0{,}2381$ до $0{,}2613$, Star Wars — с $0{,}2169$ до $0{,}2299$. Коэффициент Жаккара между старой и новой первой десяткой равен $0{,}667$: два фильма — Contact (1997) и Back to the Future (1985) — входят в неё впервые.

Тонкий эффект: выигрывают и фильмы, которых нет среди источников телепортации. Мультфильм Toy Story (1995), не помеченный как фантастика, прибавляет $16{,}4\%$ ранга (с $0{,}0030$ до $0{,}0035$) — просто потому, что на него ведут рёбра из «фантастического» кластера. Поток идёт по рёбрам, а не по жанровым ярлыкам.

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

У персонализации есть замечательное алгебраическое свойство. Отображение $v\mapsto\pi(v)$ линейно: решая

$$\pi=\alpha\pi P+(1-\alpha)v \quad\Longleftrightarrow\quad \pi=(1-\alpha)\,v\,(I-\alpha P)^{-1},$$

видим, что $\pi$ линейно зависит от $v$. Значит для смеси

$$v=\lambda v^{(1)}+(1-\lambda)v^{(2)}$$

выполняется

$$\pi(v)=\lambda\,\pi(v^{(1)})+(1-\lambda)\,\pi(v^{(2)}).$$

Мы проверили это численно: для $\lambda=1/2$ максимальное расхождение между пересчитанным рангом и полусуммой двух рангов составило $1{,}0\cdot10^{-13}$, то есть чистая ошибка округления. Практическое следствие огромно: можно заранее посчитать несколько тематических векторов и мгновенно комбинировать их под конкретного пользователя, не запуская степенной метод заново.

Чувствительность: насколько устойчив рейтинг

Рейтинг, который переворачивается от смены одного параметра, нельзя подавать как объективную шкалу. Проверим устойчивость первой десятки по $\alpha$. Коэффициент Жаккара с эталонной десяткой при $\alpha=0{,}85$ равен $1{,}000$ для всех $\alpha$ от $0{,}60$ до $0{,}95$ и падает до $0{,}818$ на краях, при $\alpha=0{,}50$ и $\alpha=0{,}99$. Цена итераций при этом растёт монотонно: от $27$ шагов при $\alpha=0{,}50$ до $85$ при $\alpha=0{,}99$.

$$\alpha\ \uparrow\quad\Longrightarrow\quad \text{больше веса ссылкам},\ \ \text{медленнее сходимость},\ \ \text{сильнее влияние ловушек}.$$

Рисунок шире экрана — проведите по немуОткрыть целиком ↗

Такой же анализ полезно проводить по данным, а не только по параметру: удалить одно ребро у лидера, добавить ссылку от середняка к аутсайдеру, превратить страницу в тупик — и посмотреть на

$$\Delta_i=\pi_i^{(\text{new})}-\pi_i^{(0)}$$

и на перестановки в первой пятёрке. Логика та же, что и в разговоре о случайных отклонениях выборочных оценок: прежде чем объявлять разницу содержательной, надо понять, какие возмущения её создают.

Русская линия: Романовский и теория цепей

Язык, на котором записан PageRank, создан задолго до веба. Андрей Андреевич Марков в начале XX века ввёл цепи зависимых испытаний и в 1913 году пересчитал чередование гласных и согласных в «Евгении Онегине», доказывая, что закон больших чисел не требует независимости.

Систематическую же теорию конечных цепей построил Владимир Иванович Романовский (1879–1954), основатель ташкентской математической школы. Его монография «Дискретные цепи Маркова» (1949) — первая в мире книга, целиком посвящённая этому предмету; в ней цепи изучаются именно матричным, спектральным способом: классификация состояний на существенные и несущественные, разложение матрицы переходов на эргодические классы, поведение $P^{\,t}$ через характеристические числа. Всё, что нам понадобилось сегодня — разложимость графа, единственность $\pi$, скорость забывания старта через $|\lambda_2|$, — это словарь Романовского. Разница лишь в том, что он изучал цепи с десятками состояний, а мы применяем те же теоремы к графам с миллиардом вершин.

Лаборатория: поток по живому графу

Сначала выберите граф «ловушка», установите $\alpha=0{,}99$ и запустите прогулку. Серые столбцы — доля времени, которую читатель провёл в вершине; красные точки — точный вектор $\pi$. Вы увидите, как почти вся масса уходит в $D,E,F$. Затем верните $\alpha=0{,}85$ и проследите, как частоты сходятся к новым точкам: это закон больших чисел в действии, только для зависимых испытаний.

Дальше переключите граф на «тупик» и убедитесь, что вершина без исходящих рёбер не обнуляет модель — сработала починка строки. Наконец, включите телепортацию «$70\%$ в $A$» и сравните ранги: персонализация меняет не только величину, но и порядок. Записывайте число итераций степенного метода: оно растёт вместе с $\alpha$ ровно так, как предсказывает оценка $\alpha^{\,t}$.

Не ограничивайтесь первой строкой рейтинга. Отмечайте расхождение $\sum_i|\hat p_i-\pi_i|$ и то, сколько шагов нужно, чтобы оно стало меньше $0{,}05$. Небольшое изменение вероятностей может заметно поменять порядок почти равных страниц — и это не шум измерения, а свойство самой шкалы.

Чего PageRank не измеряет

Авторы метода сказали это в той же работе, где ввели формулу. PageRank измеряет не истину и не качество, а положение вершины в потоке — при данном графе, данном $\alpha$ и данном $v$. Отсюда три честные оговорки.

Во-первых, граф собирает робот, и он видит не весь веб: закрытые разделы, динамические страницы и медленные сайты представлены хуже. Во-вторых, ребро не различает одобрение и осуждение — ссылка в разоблачительной статье поднимает разоблачаемого. В-третьих, персонализация переносит власть на того, кто выбрал $v$: связь с рекомендательными системами прямая, и сужение разнообразия источников здесь такое же реальное, как в ленте новостей.

Алгоритм HITS Клейнберга, появившийся одновременно с PageRank, разделяет две роли: собиратель ссылок и источник. Полезно помнить, что «важность» — не одно число, а семейство определений, и выбор между ними есть проектное решение, а не открытие закона природы.

Что унести с собой

PageRank — не магическая мера истины, а стационарный поток в выбранном графе. Тупики съедают вероятность, ловушки разрушают единственность, и обе болезни лечит одна и та же телепортация, которая заодно превращает задачу в сжимающее отображение с коэффициентом $\alpha$. Разреженный степенной метод делает счёт возможным на миллиардах вершин: цена шага $O(|E|)$, число шагов не зависит от размера графа. Персонализация линейна по $v$ и потому дёшева.

А интерпретация результата требует знать три вещи: как собран граф, что означает ребро и для кого определена релевантность. Первые две задаёте вы, третью — тот, кто выбирает $v$.

Задачи