Линейная алгебра
Спектральная теория графов
Google PageRank 1998 - это нахождение главного собственного вектора матрицы 50 миллиардов страниц. GNN, предсказывающие взаимодействие белков в AlphaFold2, работают через умножение на нормализованный лапласиан графа. Граф - это матрица; её спектр - это рентген структуры.
- PageRank: собственный вектор матрицы переходов - степенная итерация на 50B страницах
- Graph Convolutional Network: слой H⁽ˡ⁺¹⁾ = σ(D⁻¹/²ÃD⁻¹/²H⁽ˡ⁾W) - умножение на нормализованный A
- Спектральная кластеризация: вектор Фидлера делит граф - используется в scRNA-seq клеточной биологии
- AlphaFold2: граф взаимодействий остатков аминокислот обрабатывается через attention на графе
- Детекция мошенничества: аномальные узлы в транзакционном графе через спектральный анализ
**Google изменил веб, найдя главный собственный вектор матрицы 50 миллиардов страниц.** Не самую длинную страницу, не самую посещаемую - собственный вектор матрицы гиперссылок. PageRank 1998 года - это спектральная теория графов в чистом виде. Сегодня та же математика лежит в основе GNN (Graph Neural Networks), которые предсказывают взаимодействие белков, трафик на картах Google и мошеннические транзакции.
**О чём этот урок**: граф - это матрица. Собственные векторы этой матрицы кодируют структуру графа: кластеры, узкие места, центральные узлы. Спектральная теория - это рентген графа через линейную алгебру.
Матрица Лапласа: L = D - A
Для графа G = (V, E) строятся три матрицы. **Матрица смежности A**: A[i][j] = 1 если есть ребро (i,j). **Матрица степеней D**: диагональная, D[i][i] = степень вершины i. **Лапласиан L = D - A** - разность двух. Ключевое свойство: для любого вектора x выполняется **x^T L x = sum(x_i - x_j)^2** по всем рёбрам - это сумма квадратов разностей значений на концах каждого ребра.
**Число нулевых собственных значений = число компонент связности**. Для связного графа lambda_0 = 0 единственное. Для графа из двух несвязных частей lambda_0 = lambda_1 = 0. Это алгоритм проверки связности через собственные числа.
Вектор Фидлера: разрез графа через алгебру
**Второе наименьшее собственное значение lambda_1** называется алгебраической связностью (число Фидлера). Оно строго положительно тогда и только тогда, когда граф связен. Соответствующий собственный вектор **v_1** (вектор Фидлера) содержит полную информацию о натуральном разбиении графа: вершины с положительными компонентами v_1 и вершины с отрицательными - это два естественных кластера.
Малое lambda_1 означает, что граф имеет **узкое место** - небольшой разрез, который делит его на крупные части. Теорема Черджера связывает lambda_1 с изопериметрическим числом h(G): lambda_1/2 <= h(G) <= sqrt(2 * lambda_1). Это линейно-алгебраическая версия вопроса "насколько легко разделить граф".
Спектральная кластеризация: k-means в пространстве собственных векторов
Спектральная кластеризация находит k кластеров там, где k-means не справляется - в случаях непрямолинейных, запутанных кластеров (два кольца, луна, спираль). Алгоритм: взять k наименьших ненулевых собственных векторов нормализованного Лапласиана L_sym = D^(-1/2) L D^(-1/2), составить матрицу U из них, применить k-means к строкам U. Каждая вершина теперь представлена точкой в R^k, где геометрия отражает связность.
GCN: свёртка как умножение на нормализованный Лапласиан
Graph Convolutional Networks (Kipf & Welling, 2016) вычисляют новые признаки каждой вершины как взвешенную сумму признаков соседей. Это операция **H_new = A_hat H W**, где A_hat = D^(-1/2) (A + I) D^(-1/2) - нормализованная матрица смежности с добавленными self-loops. Каждый слой GCN - это матричное умножение плюс нелинейность. Глубина = радиус рецептивного поля на графе.
**GCN - это усреднение с нормировкой**. A_hat H берёт для каждой вершины среднее признаков соседей (с учётом степеней). Это то же, что BatchNorm в пространстве графа - каждая вершина получает контекст из локального окружения. Стекая L слоёв, получаем l-шаговое соседство.
PageRank: собственный вектор матрицы переходов
PageRank - это стационарное распределение случайного блуждания по графу гиперссылок. Матрица переходов P: P[j][i] = A[j][i] / deg(i) - столбцы стохастические. PageRank вектор pi - **левый собственный вектор P при lambda=1**: pi = P pi (или pi^T P = pi^T). Практически вычисляется через **power iteration** с телепортом: pi_{t+1} = alpha * P * pi_t + (1-alpha)/n. Телепорт (обычно alpha=0.85) гарантирует единственность стационарного распределения.
Практика: спектральная кластеризация
Граф как матрица: Лапласиан и его спектр
Граф $G = (V, E)$ задаётся матрицей смежности $A$ ($A_{ij}=1$ если $(i,j) \in E$) и матрицей степеней $D = \text{diag}(d_1, \ldots, d_n)$. Нормализованный граф-лапласиан: $L = D - A$ (или $\mathcal{L} = D^{-1/2}LD^{-1/2}$ для нормализованного). Собственные векторы $L$ кодируют структуру графа.
**Ключевые свойства спектра $L$:** - $L$ симметрична и положительно полуопределена ($x^\top Lx = \sum_{(i,j)\in E}(x_i - x_j)^2 \geq 0$) - $\lambda_1 = 0$ всегда; собственный вектор - $(1/\sqrt{n}, \ldots, 1/\sqrt{n})$ - **Связность**: $\lambda_2 > 0$ тогда и только тогда, когда граф связен - **Вектор Фидлера** $v_2$ ($\lambda_2$-вектор) - разрезает граф на два кластера
Спектральная кластеризация: два кластера одним SVD
sklearn в 3 строки
Граф похожести (gaussian kernel по расстоянию). Вычислить $L$, взять вектор Фидлера $v_2$, разрезать по знаку: $C_1 = \{i: v_2[i] > 0\}$, $C_2 = \{i: v_2[i] \leq 0\}$. Для $k$ кластеров: первые $k$ собственных векторов $L$, затем k-means в этом пространстве. Используется в обработке изображений (normalized cuts), геномике (кластеры клеток в scRNA-seq).
Второе собственное значение лапласиана $\lambda_2$ называют алгебраической связностью графа. Что означает $\lambda_2 = 0$?
Кратность собственного значения $\lambda = 0$ у $L$ равна числу компонент связности. Если $\lambda_2 = 0$, граф имеет хотя бы 2 компоненты. Если $\lambda_2 > 0$ - граф связен, и $\lambda_2$ характеризует, насколько "хорошо" он связан (bottleneck).
PageRank и Graph Neural Networks через спектр
PageRank - нахождение главного собственного вектора матрицы переходов $M$: $r = Mr$ ($\lambda = 1$). С damping factor: $r = dMr + (1-d)/n \cdot \mathbf{1}$. Степенная итерация сходится за $O(\log(1/\varepsilon) / \log(1/d))$ шагов. Спектральный зазор $1 - d\lambda_2(M)$ определяет скорость сходимости.
**Graph Convolutional Networks (GCN)**: слой GCN - это умножение признаков $H$ на нормализованный лапласиан: $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} H^{(l)} W^{(l)})$, где $\tilde{A} = A + I$. Это взвешенное усреднение признаков соседних узлов. Матрица $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ - это фильтрация в спектральном пространстве графа (низкочастотные компоненты).
Предсказание взаимодействия белков через GNN
STRING database, 2023
Граф белок-белок: 20K узлов (белки), 1M рёбер (взаимодействия). GCN агрегирует признаки соседних белков (последовательность, структура) через матрицу $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$. Задача: предсказать функцию незнакомого белка по его соседям в графе. AlphaFold2 использует родственную архитектуру для предсказания структуры белка.
В Graph Convolutional Network (GCN) слой агрегирует информацию от соседей через матрицу $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$. Что делает эта операция геометрически?
$(\hat{A}H)_i = \sum_{j \in \mathcal{N}(i) \cup \{i\}} \frac{1}{\sqrt{d_i d_j}} H_j$ - взвешенная сумма признаков соседей с нормировкой по степеням. Добавление $I$ к $A$ включает сам узел в агрегацию. Это аналог свёртки, но на графе.
x^T L x = x^T (D - A) x = x^T D x - x^T A x = sum_i d_i x_i^2 - sum_{(i,j) in E} 2 x_i x_j = sum_{(i,j) in E} (x_i - x_j)^2 Интерпретация: - x - сигнал на вершинах графа (напр., температура, мнение, активация) - x^T L x = "гладкость" сигнала: мал если соседи имеют похожие значения - L - симметричная PSD матрица: lambda_i >= 0 для всех i - lambda_0 = 0 всегда (вектор 1 в ядре L: сумма строк = 0)
- **PageRank**: Левый собственный вектор матрицы переходов
- **GCN (Kipf & Welling 2016)**: H_new = A_hat H W (сглаживание на графе)
- **Спектральная кластеризация**: k-means в пространстве Fiedler-векторов
- **Graph Fourier Transform**: Базис из собственных векторов Лапласиана
- **Community Detection**: Многосрезовая спектральная кластеризация
Упражнения
- Почему lambda_0 матрицы Лапласиана всегда равна нулю? — Каждая строка L суммируется в 0: сумма строки = deg(i) - deg(i) = 0; Значит L * 1 = 0, то есть вектор 1 = (1,1,...,1) - собственный при lambda=0; Число нулевых lambda = числу компонент связности (это теорема); Для несвязного графа из k частей первые k собственных значений равны нулю
- Чем GCN отличается от обычного MLP с точки зрения линейной алгебры? — MLP: y = W * x - матрица весов W не зависит от структуры данных; GCN: y = A_hat * H * W - добавляется умножение на A_hat (структура графа); A_hat усредняет признаки по соседям: каждая вершина видит своё окружение; Это inductive bias: похожие по связям вершины должны быть похожи по признакам
Граф как матрица, структура как спектр
- Лапласиан L = D - A; симметричный PSD; x^T L x = sum(x_i - x_j)^2 по рёбрам
- lambda_0 = 0 всегда; число нулевых lambda = число компонент; lambda_1 > 0 iff граф связен
- Вектор Фидлера v_1: знак компоненты = кластер; малое lambda_1 = узкое место в графе
- Спектральная кластеризация: k собственных векторов L_sym -> k-means в R^k
- GCN: H_new = ReLU(A_hat H W); A_hat = D^(-1/2)(A+I)D^(-1/2); L слоёв = L-шаговое соседство
- PageRank: pi = alpha P pi + (1-alpha)/n; power iteration; телепорт = эргодичность цепи
- Graph Fourier Transform: собственные векторы L - ортогональный базис сигналов на графе
Связанные темы
Финальный урок раздела - продвинутые задачи интервью, которые объединяют все темы курса: SVD, собственные значения, обусловленность, численная устойчивость.
- Финальные задачи интервью — Спектральные методы часто фигурируют в вопросах про deep understanding of linear algebra
- Линейная алгебра в глубоком обучении — GNN использует нормализованный Лапласиан как оператор агрегации - прямая связь
- Собственные векторы и значения — Спектральная теория графов целиком построена на eigenvectors симметричных матриц