ЭКСПЕРИМЕНТ 03 · ОПИСАНИЕ

Археология знания

Трёхмерный атлас показывает исторический граф русской Википедии и проверяет, можно ли по его структуре предсказать появление статей, названия которых уже упоминались в существующих текстах.

СТАТЬИ1 000СВЯЗИ5 382КАНДИДАТЫ133ПРОВЕРКА ИСХОДОВ2008–2014

ЗАДАЧА

Можно ли увидеть будущую статью?

Ссылка может вести к названию, для которого ещё нет отдельной статьи. Эксперимент сравнивает четыре способа ранжировать такие названия и проверяет, помогают ли волновые признаки графа найти будущие статьи точнее, чем локальные связи и диффузия.

ВХОДНЫЕ ДАННЫЕ

Восстановленный граф до 2008 года

Граф восстановлен по доступным публичным редакциям на конец 2007 года. В выборке — 1 000 статей из тематического обхода математики и информатики. Кандидаты — названия, отсутствовавшие в реконструкции, но упомянутые как минимум двумя историческими статьями.

МЕТОД

Как устроена проверка временем

Обучение на прошлом. Из исторического графа искусственно удаляются узлы, чтобы модели учились оценивать отсутствующие статьи.
Четыре модели. M1 использует локальные признаки; M2 добавляет граф и диффузию; M3 — волновые признаки; M2+ расширяет набор диффузионных признаков.
Фиксация прогнозов. Кандидаты ранжируются по прошлому графу до проверки их будущих исходов.
Историческая проверка. Для каждого названия проверяется устойчивое появление статьи под этим точным названием до конца 2014 года.

ВИЗУАЛИЗАЦИЯ

Как читать трёхмерную карту

Голубые точки обозначают исторические статьи, линии — ссылки между ними, контуры — кандидатов. Ромб отмечает подтверждённое появление статьи. Кандидат связан со статьями, которые упоминали его название.

Вращайте сцену перетаскиванием и меняйте масштаб колесом. Поиск и выбор кандидата открывают его источники и места в рейтингах моделей. Шкала времени раскрывает исходы кандидатов при неизменном прошлом графе.

РЕЗУЛЬТАТ

Что показал эксперимент

В отображаемой выборке подтверждены 29 появлений и 9 отрицательных исходов. Ещё 95 исходов остаются неопределёнными и не участвуют в оценке. По 38 известным исходам добавление волновых признаков не улучшило ранжирование относительно модели с графом и диффузией.

Атлас показывает проверку устойчивости после исключения одного артефакта реконструкции исторического названия. Это исключение сделано после проверки исходов; модели не переобучались.

ФОРМАЛИЗАЦИЯ

Используемые математические методы

Прогноз строится по структуре исторических ссылок. Сначала рассчитываются признаки пар статей, затем обученная модель оценивает эти пары и объединяет их оценки в рейтинг названий. Тексты, смысловые эмбеддинги и 3D-координаты в признаки предсказания не входят.

01 · МАТРИЦА ГРАФА

Нормированный лапласиан

\begin{aligned} d_i&=\sum_j B_{ij},\quad D=\operatorname{diag}(d_i)\\ L&=\operatorname{diag}(\mathbf1_{d_i>0})-D^{-1/2}BD^{-1/2}\\ L&=U\Lambda U^\top \end{aligned}

B — бинарная симметричная матрица ссылок без петель, dᵢ — степень вершины. Для изолированных вершин обратная степень принимается равной нулю. Собственные векторы U и собственные значения Λ задают графовые моды, по которым рассчитываются диффузия и волны.

При искусственном удалении статей все степени, компоненты и спектральные признаки заново вычисляются по оставшемуся графу. Связи скрытых узлов не поступают в признаки.

02 · ЛОКАЛЬНАЯ СВЯЗНОСТЬ

Общие соседи и их вес

\begin{aligned} \mathrm{CN}_{ij}&=|N(i)\cap N(j)|\\ J_{ij}&=\frac{\mathrm{CN}_{ij}}{d_i+d_j-\mathrm{CN}_{ij}}\\ \mathrm{RA}_{ij}&=\sum_{v\in N(i)\cap N(j)}\frac1{d_v}\\ \mathrm{AA}_{ij}&=\sum_{v\in N(i)\cap N(j)}\frac1{\log d_v} \end{aligned}

N(i) — соседи статьи i. CN считает общих соседей, коэффициент Жаккара учитывает размер обоих окружений, а resource allocation и Adamic–Adar уменьшают вклад общих узлов с большим числом связей.

В девять локальных признаков также входят минимум и максимум степеней, их произведение и минимум и максимум коэффициентов кластеризации. Степени, произведение, CN, RA и AA преобразуются через log(1 + x).

03 · ДИФФУЗИЯ

Тепловое ядро и резольвента

\begin{aligned} H_t&=e^{-tL}=U\operatorname{diag}(e^{-t\lambda_k})U^\top\\ R_s&=(I+sL)^{-1}\\ &=U\operatorname{diag}\!\left(\frac1{1+s\lambda_k}\right)U^\top \end{aligned}

Элемент Hₜ(i, j) описывает распространение теплового импульса по графу, а Rₛ(i, j) — сглаженную связь на масштабе s. Малые масштабы подчёркивают ближайшее окружение; большие учитывают более дальние пути.

Используются восемь времён t от 0,1 до 100 и восемь масштабов s от 0,03 до 100. Контрольная модель M2+ получает ещё 19 тепловых масштабов от 0,07 до 70 — столько же дополнительных признаков, сколько волн получает M3.

04 · ГЛОБАЛЬНАЯ СВЯЗНОСТЬ

Пути и эффективное сопротивление

\begin{aligned} z_{ij}&=D^{-1/2}(e_i-e_j)\\ r_{ij}&=z_{ij}^{\top}L^{+}z_{ij}\\ L^{+}&=U\operatorname{diag}(\lambda_k^{+})U^\top\\ \lambda_k^{+}&=\begin{cases}1/\lambda_k,&\lambda_k>0\\0,&\lambda_k=0\end{cases} \end{aligned}

Кратчайший путь считает минимальное число переходов между статьями. Эффективное сопротивление учитывает все альтернативные пути: граф трактуется как сеть единичных резисторов. eᵢ — единичный вектор, L⁺ — псевдообратная матрица.

Формула сопротивления применяется внутри одной компоненты. Для несвязанных пар отдельно записывается признак разрыва; числовое поле сопротивления заполняется нулём, что не означает нулевого физического сопротивления.

05 · ВОЛНОВАЯ ДИНАМИКА

Затухающий импульс на графе

\begin{aligned} \ddot u+2\gamma\dot u+Lu&=0\\ u(0)&=0\\ \dot u(0)&=\frac{\Pi_+e_i}{\|\Pi_+e_i\|_2}\\ \Pi_+&=I-U_0U_0^\top \end{aligned}

В отличие от диффузии, это уравнение допускает колебания и смену знака отклика. γ управляет затуханием. U₀ содержит все нулевые моды лапласиана; их исключение убирает стационарную составляющую, а начальный импульс нормируется.

Уравнение решается в собственном базисе L: для каждой моды используется точное решение колебательного, критического или апериодического режима. Проверяются γ = 0,05; 0,15; 0,4 на сетке времени от 0 до 30 с шагом 0,5.

06 · ОТКЛИК ПАРЫ

От спектральных мод к сигналу

\begin{aligned} q_i&=\|\Pi_+e_i\|_2\\ c_{ij,k}&=\tfrac12(q_i^{-1}+q_j^{-1})U_{ik}U_{jk}\\ h_{ij}(t)&=\sum_{\lambda_k>0}c_{ij,k}\,g_\gamma(\lambda_k,t)\\ \ddot g+2\gamma\dot g+\lambda g&=0,\quad g(0)=0,\ \dot g(0)=1 \end{aligned}

hᵢⱼ — средний отклик двух направлений: импульса из i в j и из j в i. Такая нормировка делает признаки симметричными. Функция g задаёт временной отклик одной спектральной моды.

Для каждого затухания извлекаются пять характеристик: время первого пересечения порога |h| ≥ 0,001, делённое на 30; флаг отсутствия пересечения; логарифм интеграла h²; число выраженных пиков; логарифм максимума |h|. Задержка здесь не является физическим временем распространения.

07 · ЧАСТОТНЫЕ ПРИЗНАКИ

Интенсивность и частотный отклик

\begin{aligned} E_{ij}&=\int_0^{30}h_{ij}(t)^2\,dt\\ F_{ij}(\omega)&=\sum_{\lambda_k>0}\frac{c_{ij,k}}{\lambda_k-\omega^2+2\mathrm{i}\gamma_f\omega}\\ x_\omega&=\log_{10}(|F_{ij}(\omega)|+10^{-12}) \end{aligned}

Интеграл E вычисляется методом трапеций на временной сетке и характеризует интенсивность отклика, а не полную механическую энергию. Пики считаются по |h|, если достигают хотя бы 10% его максимума.

К 15 временным характеристикам добавляются четыре частотные амплитуды: ω = 0,25; 0,5; 1; 1,4 при частотном затухании 0,15. Всего получается 19 волновых признаков. Для интенсивности и максимума также используются log₁₀(x + 10⁻¹²).

08 · ОБУЧЕНИЕ

Бустинг деревьев на скрытых узлах

\begin{aligned} y_{ij}&=\mathbf1\{\exists h\in H:\ A_{ih}A_{jh}=1\}\\ F_M(x)&=F_0+\eta\sum_{m=1}^{M}T_m(x)\\ \hat p_{ij}&=\frac1{1+\exp(-F_M(x_{ij}))} \end{aligned}

A — исторический граф до искусственного удаления, H — случайно скрытые 10% его узлов. Для пары без прямого ребра целевая метка равна единице, если у неё был общий скрытый сосед. Гистограммный градиентный бустинг деревьев учится предсказывать эту метку по признакам оставшегося графа.

В формуле x — признаки пары, Tₘ — очередное дерево, F₀ — начальный балл. Используются 150 итераций с шагом η = 0,08. Число листьев (4 или 8) и L2-регуляризация (1 или 10) выбираются по среднему AP двух проверочных масок после обучения на четырёх масках. Затем модель обучается заново на объединении этих данных. Будущие появления статей в обучение не входят.

09 · РЕЙТИНГ НАЗВАНИЙ

Как оценивается кандидат

\begin{aligned} P_c&=\{\{i,j\}\subset S_c:\ A_{ij}=0,\ d_i,d_j>0\}\\ s_m(c)&=\frac1{|P_c|}\sum_{\{i,j\}\in P_c}\hat p_m(i,j) \end{aligned}

S_c — статьи, которые упоминали название c в прошлом. Модель оценивает все подходящие пары этих источников, а арифметическое среднее становится баллом кандидата. Степени и связи здесь берутся из исторического графа до искусственного удаления.

M1 использует 9 локальных признаков; M2 — 28 локальных и графово-диффузионных; M3 — 47 с добавлением волн; M2+ — 47 с дополнительной диффузией. Это сравнение способов описать один граф. Балл не откалиброван как вероятность будущего появления статьи.

10 · ГЕОМЕТРИЯ АТЛАСА

Силовая раскладка в 3D

\begin{aligned} k&=(8/n)^{1/3}\\ f_{\mathrm{rep}}(r)&=\frac{k^2}{r},\qquad f_{\mathrm{attr}}(r)=\frac{r^2}{k}\\ X_c&=X-\mathbf1\bar x^\top=U\Sigma V^\top\\ Y&=X_cV \end{aligned}

Алгоритм Fruchterman–Reingold раздвигает вершины и стягивает связанные пары. n — число отображаемых узлов, r — расстояние между ними. В реализации ограничено отталкивание на малых расстояниях, добавлено слабое притяжение к центру и постепенно уменьшается допустимый шаг.

После 220 итераций с фиксированным seed SVD поворачивает центрированные координаты к главным осям, затем применяется общий масштаб. В раскладку входят исторические ссылки и упоминания кандидатов. Сами значения оценок моделей и метки исходов не входят в силы раскладки.

КАК ПРОВЕРЯЕТСЯ ПРОГНОЗ

Метрики и сравнение моделей

Average precision

\mathrm{AP}=\sum_\ell(R_\ell-R_{\ell-1})P_\ell

Средняя точность с весами по приросту полноты: P и R считаются при последовательном снижении порога. Равные баллы объединяются. Это основная метрика ранжирования.

Precision и recall

\begin{aligned} k'&=\min(k,n_{\mathrm{known}})\\ P@k&=\frac{\mathrm{TP}_{k'}}{k'}\\ R@k&=\frac{\mathrm{TP}_{k'}}{n_+} \end{aligned}

TP — число появившихся статей среди первых k′ известных исходов, n₊ — все известные появления. В атласе используются k = 20 и 50; при 38 известных исходах второй срез охватывает всю оцениваемую выборку.

AUROC

\begin{aligned}\mathrm{AUC}&=\Pr(s_+>s_-)\\&\quad+\tfrac12\Pr(s_+=s_-)\end{aligned}

Доля положительно-отрицательных пар, в которых появившаяся статья стоит выше непоявившейся. Равные баллы дают половинный вклад. Чем ближе результат к 1, тем лучше разделение.

Добавочная польза волн

\Delta\mathrm{AP}=\mathrm{AP}_{M3}-\mathrm{AP}_{M2}

Разница AP на одних и тех же известных исходах. Заранее выбранный практически заметный прирост — +0,03. В отображаемой выборке ΔAP ≈ −0,037; преимущество волн не получено. Дополнительно сравниваются M2+ и число источников.