Графовое разложение

Материал из MachineLearning.

Статья написана с использованием LLM Gemini 3.5 Pro и проверена участником Vsevolod Peretiatko 00:45, 20 июня 2026 (MSD)

Графовое разложение (англ. Graph Decomposition) — фундаментальный класс методов в дискретной математике, линейной алгебре и машинном обучении, направленный на представление исходной графовой структуры в виде совокупности более простых или канонических подструктур (топологическая декомпозиция), либо на факторизацию операторных матричных проекций графа (алгебраическое и спектральное разложение).

В контексте интеллектуального анализа данных и геометрического глубокого обучения графовое разложение выступает ключевым инструментом преодоления «проклятия неевклидовости». Сырые представления графов (такие как списки смежности или топологические разреженные матрицы) характеризуются переменной размерностью, комбинаторной сложностью и инвариантны относительно перестановок вершин. Это исключает возможность их прямой обработки классическими дискриминантными или генеративными алгоритмами. Разложение графа позволяет либо декомпозировать сложную сеть вероятностных зависимостей на сепарабельные компоненты (что критически важно для эффективного вывода в вероятностных графических моделях), либо отобразить топологические свойства нерегулярных доменов в непрерывные низкоразмерные векторные пространства. Последнее обеспечивает математический фундамент для алгоритмов спектральной кластеризации, снижения размерности и проектирования графовых нейронных сетей.

Содержание

1 Математическая постановка и основные представления
- 1.1 Дифференциально-геометрическая интерпретация
2 Спектральное разложение графа
- 2.1 Свойства спектра и топологические инварианты
- 2.2 Алгебраическая связность и число Фидлера
3 Топологические и иерархические разложения
- 3.1 Древесная декомпозиция (Tree Decomposition)
- 3.2 k-core разложение (k-core decomposition)
4 Классические алгебраические методы обучения на графах
5 Графовое разложение в вероятностных графических моделях
6 Спектральное геометрическое глубокое обучение (Спектральные GNN)
7 Иерархическое разложение и пулинг в нейронных сетях
- 7.1 Задача укрупнения графа (Graph Coarsening)
- 7.2 Дифференциальный пулинг (DiffPool)
8 Вычислительные аспекты, ограничения и критика
9 См. также
10 Примечания
11 Литература

Математическая постановка и основные представления

Пусть задан взвешенный неориентированный граф $G = (V, E, W)$ , где:

$V = \{v_1, v_2, \dots, v_n\}$ — конечное множество вершин, причем его мощность $|V| = n$ ;
$E \subseteq V \times V$ — множество ребер, связывающих пары вершин, причем $|E| = m$ ;
$W$ — функция весов ребер, сопоставляющая каждой паре $(v_i, v_j) \in E$ вещественное число $w_{ij} > 0$ , характеризующее интенсивность или близость связи. Для невзвешенных графов принимают $w_{ij} = 1$ при наличии ребра.

Для аналитического описания и последующей декомпозиции структуры графа $G$ вводятся следующие фундаментальные матричные операторы:

Матрица смежности $A \in \mathbb{R}^{n \times n}$ определяет попарные связи между вершинами: $A_{ij} = \begin{cases} w_{ij}, & (v_i, v_j) \in E, \\ 0 \end{cases}$ В силу неориентированности графа матрица $A$ является строго симметричной: $A = A^T$ .

Матрица степеней вершин $D \in \mathbb{R}^{n \times n}$ представляет собой диагональную матрицу, элементы которой отражают суммарную топологическую значимость (локальный объем) каждой вершины: $D_{ii} = d(v_i) = \sum_{j=1}^n A_{ij},$ при этом $D_{ij} = 0$ для всех $i \neq j$ .

Матрица Лапласа (Лапласиан графа) — центральный линейный оператор спектральной теории, инкапсулирующий как геометрию графа, так и характер диффузионных процессов на нем. В алгебраических методах машинного обучения применяются три канонические формы Лапласиана:

Ненормализованный Лапласиан: $L = D - A$
Симметрично нормализованный Лапласиан: $L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}$
Нормализованный Лапласиан случайного блуждания (стохастический Лапласиан): $L_{\text{rw}} = D^{-1} L = I - D^{-1} A$

Здесь $I$ обозначает единичную матрицу размерности $n \times n$ , а под $D^{-1/2}$ понимается диагональная матрица с элементами $(D^{-1/2})_{ii} = 1 / \sqrt{d(v_i)}$ при $d(v_i) > 0$ и $0$ при $d(v_i) = 0$ .

Дифференциально-геометрическая интерпретация

Для строгого обоснования декомпозиционных подходов Лапласиан графа интерпретируют как дискретный аналог непрерывного дифференциального оператора Лапласа — Бельтрами $\Delta$ , заданного на Римановом многообразии (в рамках гипотезы о многообразиях — manifold assumption).

Пусть на вершинах графа определена вещественная функция (сигнал) $f: V \to \mathbb{R}$ , представимая в виде вектора $f = [f(v_1), f(v_2), \dots, f(v_n)]^T$ . Тогда действие ненормализованного Лапласиана на сигнал $f$ в точке $v_i$ эквивалентно вычислению локальной разностной кривизны: $(Lf)_i = \sum_{j=1}^n A_{ij} (f(v_i) - f(v_j))$ Данное выражение показывает, что оператор измеряет отклонение значения функции в конкретной вершине относительно её взвешенного окружения.

Свойством, определяющим применимость графового разложения в задачах полуавтоматического обучения (semi-supervised learning) и регуляризации, является квадратичная форма Лапласиана, определяемая как графовый функционал Дирихле: $f^T L f = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n A_{ij} (f(v_i) - f(v_j))^2$

Из структуры квадратичной формы напрямую следуют два фундаментальных математических факта:

Матрица $L$ является полуположительно определенной ( $f^T L f \ge 0$ для любого вещественного вектора $f$ ), что гарантирует вещественность и неотрицательность её спектра.
Квадратичная форма $f^T L f$ служит строгой мерой гладкости функции на топологии графа. Её минимизация минимизирует «энергию» сигнала, накладывая жесткий штраф за резкие перепады значений $f(v_i)$ и $f(v_j)$ между теми вершинами, которые характеризуются высоким весом связи $A_{ij} \gg 0$ .^[1]

Спектральное разложение графа

Спектральное разложение (векторно-матричная факторизация) операторов графа переводит топологические свойства дискретной структуры на язык линейной алгебры. В основе данного подхода лежит спектральная теорема для действительных симметричных матриц. Поскольку ненормализованный Лапласиан $L$ и симметрично нормализованный Лапласиан $L_{\text{sym}}$ являются самосопряженными (симметричными) операторами в пространстве $\mathbb{R}^{n \times n}$ , они допускают полное ортогональное разложение.

Формально теорема о спектральном разложении для матрицы $L$ утверждается как: $L = U \Lambda U^T = \sum_{i=1}^n \lambda_i u_i u_i^T$ где:

$U = [u_1, u_2, \dots, u_n] \in \mathbb{R}^{n \times n}$ — ортогональная матрица, столбцами которой являются собственные векторы оператора Лапласа ( $U^T U = I$ );
$\Lambda = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_n)$ — диагональная матрица вещественных собственных значений (спектра графа), упорядоченных по невозрастанию интенсивности гладкости: $0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ .

Каждая пара $(\lambda_i, u_i)$ удовлетворяет фундаментальному уравнению на собственные значения: $L u_i = \lambda_i u_i$

Свойства спектра и топологические инварианты

Спектральный состав Лапласиана несет в себе исчерпывающую информацию о макроструктуре графа. Выделяют следующие ключевые свойства:

Полуположительная определенность: Для любого графа минимальное собственное значение $\lambda_1 = 0$ . Ему соотносится тривиальный собственный вектор $u_1 = \frac{1}{\sqrt{n}} \mathbf{1}$ , где $\mathbf{1} = [1, 1, \dots, 1]^T$ . Это напрямую следует из равенства $L \mathbf{1} = (D - A)\mathbf{1} = 0$ , поскольку сумма элементов $i$ -й строки матрицы смежности в точности равна степени вершины $D_{ii}$ .
Кратность нулевого собственного значения: Кратность собственного значения $\lambda = 0$ (число собственных значений, равных нулю) в точности равна количеству компонент связности графа. Если граф состоит из $k$ изолированных подграфов $\{G_1, G_2, \dots, G_k\}$ , то матрица $L$ принимает блочно-диагональный вид, а подпространство решений уравнения $L u = 0$ натягивается на индикаторные векторы этих компонент:

$u_j(v_i) = \begin{cases} \frac{1}{\sqrt{|V_j|}}, & v_i \in V_j, \\ 0 \end{cases}$

Алгебраическая связность и число Фидлера

Второе наименьшее собственное значение Лапласиана $\lambda_2$ называется алгебраической связностью графа (числом Фидлера), а соответствующий ему собственный вектор $u_2$ — вектором Фидлера^[1].

Число Фидлера служит непрерывным индикатором структурной прочности графа: $\lambda_2 > 0$ тогда и только тогда, когда граф является связным. Значение $\lambda_2$ близко к нулю, если граф содержит «узкие горлышки» (bottlenecks) — минимальное число ребер, удаление которых разделяет граф на изолированные подмножества.

Математический смысл вектора Фидлера раскрывается через вариационный принцип Рэлея — Ритца. Релаксированная задача оптимального бинарного разреза графа на два подмножества $V_1$ и $V_2$ сводится к поиску вектора признаков $f \in \mathbb{R}^n$ , минимизирующего квадратичную форму Дирихле при условиях центрированности и нормировки: $\min_{f \neq 0} \frac{f^T L f}{f^T f}$ при $f^T \mathbf{1} = 0$

В силу ортогональности спектрального базиса решением данной непрерывной задачи оптимизации является вектор Фидлера $u_2$ , а минимальное значение функционала равно $\lambda_2$ . Анализ знаков компонент вектора Фидлера ( $u_2(v_i) > 0$ против $u_2(v_i) < 0$ ) лежит в основе классических декомпозиционных алгоритмов кластеризации.

Топологические и иерархические разложения

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

Древесная декомпозиция (Tree Decomposition)

Древесная декомпозиция — это отображение произвольного циклического графа в дерево мета-вершин (кластеров), сохраняющее исходные отношения смежности. Этот тип разложения незаменим при работе с разреженными структурами, обладающими скрытой иерархией.

Формально древесной декомпозицией графа $G = (V, E)$ называется пара $(T, \mathcal{X})$ , где $T = (I, F)$ — дерево, а $\mathcal{X} = \{X_i \mid i \in I\}$ — семейство подмножеств вершин (называемых «сумками», англ. bags), удовлетворяющее трем аксиомам:

Покрытие вершин: В совокупности все сумки содержат все вершины исходного графа: $\bigcup_{i \in I} X_i = V$ .
Покрытие ребер: Для каждого ребра $(u, v) \in E$ существует хотя бы одна сумка $X_i$ , содержащая обе вершины одновременно ( $\{u, v\} \subseteq X_i$ ).
Связность (интерполяция): Если одна и та же вершина $v \in V$ входит в две разные сумки $X_i$ и $X_j$ , то она обязана входить во все сумки $X_k$ , лежащие на единственном простом пути между узлами $i$ и $j$ в дереве $T$ .

Важнейшей числовой характеристикой данного разложения является древесная ширина (англ. treewidth) графа, обозначаемая как $\text{tw}(G)$ . Она определяется как минимизированный по всем возможным декомпозициям максимальный размер сумки, уменьшенный на единицу: $\text{tw}(G) = \min_{(T, \mathcal{X})} \max_{i \in I} (|X_i| - 1)$

Для деревьев $\text{tw}(G) = 1$ , для циклов — $2$ , а для полных графов $K_n$ ширина максимальна и равна $n - 1$ . В вероятностных графических моделях древесная декомпозиция позволяет оценить вычислительную емкость графа: алгоритмы точного вывода (например, Junction Tree) масштабируются экспоненциально относительно $\text{tw}(G)$ , что делает выявление минимальной древесной ширины NP-трудной, но критически приоритетной задачей.

k-core разложение (k-core decomposition)

$k$ -core разложение (слоевая декомпозиция) представляет собой иерархическое разделение графа на вложенные подграфы с гарантированным уровнем топологической плотности (внутренней степени связности).

Пусть $H \subseteq G$ — индуцированный подграф. Подграф $H$ называется $k$ -ядром (англ. $k$ -core), если он является максимальным подграфом, в котором минимальная степень любой вершины относительно $H$ не меньше $k$ : $\forall v \in V(H) \quad d_H(v) \ge k$

Процесс декомпозиции носит итерационный деструктивный характер и описывается следующим предикатом:

Задается начальный уровень $k = 1$ .
Из графа рекурсивно удаляются все вершины, чья текущая степень $d(v) < k$ , вместе с инцидентными им ребрами. Удаление одних вершин снижает степени соседних, что запускает каскадную фильтрацию.
Процесс повторяется до тех пор, пока в графе не останутся только вершины со степенью $\ge k$ . Оставшийся связный остаток формирует $k$ -ядро.
Значение $k$ инкрементируется, и процедура повторяется на усеченной топологии.

Результатом разложения является сопоставление каждой вершине инвариантного показателя — корового числа (англ. core number) $c(v)$ , равного максимальному индексу $k$ , при котором вершина $v$ еще удерживается в составе $k$ -ядра.

Слоевая топологическая декомпозиция обладает вычислительной сложностью $O(m)$ и активно применяется для:

Масштабирования визуализации сверхбольших графов посредством отсечения периферийного шума (вершин с низким $c(v)$ );
Идентификации «информационных проводников» и хабов в социальных и биологических сетях, так как вершины с максимальным коровым числом топологически центрированы и устойчивы к случайным сбоям инфраструктуры.

Классические алгебраические методы обучения на графах

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

Спектральная кластеризация

Спектральная кластеризация (англ. Spectral Clustering) решает задачу разбиения множества вершин графа на $k$ непересекающихся подмножеств $V_1, V_2, \dots, V_k$ ( $\bigcup V_p = V$ , $V_p \cap V_q = \emptyset$ ) таким образом, чтобы минимизировать суммарный вес ребер между кластерами при условии их внутренней плотности.

Прямая комбинаторная постановка задачи через критерий нормализованного разреза^[1] (англ. Normalized Cut, $\text{NCut}$ ) имеет вид: $\min_{V_1, \dots, V_k} \text{NCut}(V_1, \dots, V_k) = \min_{V_1, \dots, V_k} \sum_{p=1}^k \frac{\text{cut}(V_p, \bar{V}_p)}{\text{vol}(V_p)}$ где $\text{cut}(V_p, \bar{V}_p) = \sum_{i \in V_p, j \in \bar{V}_p} A_{ij}$ — суммарный вес ребер, связывающих кластер $V_p$ с его дополнением, а $\text{vol}(V_p) = \sum_{i \in V_p} D_{ii}$ — полный объем (суммарная степень вершин) кластера.

Минимизация функционала $\text{NCut}$ является NP-трудной задачей. Спектральное разложение позволяет выполнить непрерывную релаксацию данной задачи. Определим матрицу индикаторов кластеров $H \in \mathbb{R}^{n \times k}$ , элементы которой задаются как: $H_{ip} = \begin{cases} \frac{1}{\sqrt{\text{vol}(V_p)}}, & v_i \in V_p, \\ 0 \end{cases}$

При такой нормировке матрица $H$ удовлетворяет условию $H^T D H = I$ , а исходный функционал строго переписывается через след матрицы: $\text{NCut} = \text{Tr}(H^T L H)$ . Отбрасывание дискретного требования на элементы матрицы $H$ приводит к непрерывной задаче оптимизации: $\min_{Z \in \mathbb{R}^{n \times k}} \text{Tr}(Z^T L_{\text{sym}} Z)$ при условии $Z^T Z = I$ где $Z = D^{1/2} H$ . Согласно теореме Куранта — Фишера, глобальным минимумом данной задачи является матрица $Z$ , составленная из $k$ собственных векторов матрицы $L_{\text{sym}}$ , соответствующих её $k$ наименьшим собственным значениям.

В классическом алгоритме Нжи — Джордана — Вайса (NJW) строки полученной матрицы $Z$ нормируются на единичную длину в метрике $L_2$ для устранения координатных искажений, после чего скрытые векторные представления вершин кластеризуются стандартным методом $k$ -средних ( $k$ -means)^[1].

Снижение размерности и Manifold Learning

Алгоритм Laplacian Eigenmaps^[1] использует спектральное разложение графа для построения низкоразмерного нелинейного встраивания данных, локально распределенных на скрытом Римановом многообразии.

Пусть задана выборка высокоразмерных векторов $x_1, x_2, \dots, x_n \in \mathbb{R}^D$ . На основе метрических расстояний строится граф ближайших соседей, матрица смежности которого $A$ отражает локальную близость объектов. Задача состоит в нахождении низкоразмерных проекций $y_1, y_2, \dots, y_n \in \mathbb{R}^d$ ( $d \ll D$ ), минимизирующих взвешенное расстояние между близкими точками: $\min_{Y} \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n A_{ij} \|y_i - y_j\|^2 = \min_{Y} \text{Tr}(Y^T L Y)$ где $Y = [y_1, y_2, \dots, y_n]^T \in \mathbb{R}^{n \times d}$ — матрица координат встраивания. Чтобы избежать тривиального решения $Y = 0$ и коллапса всех проекций в одну точку, накладывается ограничение вариации $Y^T D Y = I$ и условие центрирования $Y^T D \mathbf{1} = 0$ , исключающее первый (тривиальный) собственный вектор Лапласа.

Оптимальное решение находится из обобщенной проблемы на собственные значения: $L u = \lambda D u$ Координаты нового пространства формируются столбцами матрицы $Y$ , в качестве которых берутся собственные векторы $u_2, u_3, \dots, u_{d+1}$ , соответствующие наименьшим ненулевым собственным значениям. Графовое разложение в данном аспекте гарантирует, что топологически близкие объекты в исходном пространстве останутся геометрически близкими в редуцированном пространстве.

Выделение сообществ и модулярность

В задачах анализа сложных сетей (Network Science) разложение графа применяется для обнаружения структурных общностей без априорного знания числа кластеров. Ведущим подходом здесь является максимизация модулярности Ньюмана — Гирвана (англ. Modularity)^[1].

Модулярность $Q$ измеряет отклонение плотности ребер внутри выделенных групп относительно математического ожидания их плотности в случайном графе с фиксированным распределением степеней вершин (модель Конфигурации): $Q = \frac{1}{2m} \sum_{i=1}^n \sum_{j=1}^n \left( A_{ij} - \frac{d_i d_j}{2m} \right) \delta(c_i, c_j)$ где $d_i, d_j$ — степени вершин, $m$ — полное число ребер графа, а $\delta(c_i, c_j) = 1$ при совпадении классов вершин и $0$ в противном случае.

Вводя матрицу модулярности $B \in \mathbb{R}^{n \times n}$ с элементами $B_{ij} = A_{ij} - \frac{d_i d_j}{2m}$ , для бинарного разделения графа функционал можно переписать как $Q = \frac{1}{4m} s^T B s$ , где $s \in \{-1, 1\}^n$ — вектор принадлежности. Спектральная релаксация этой задачи приводит к анализу собственных векторов матрицы $B$ . Поскольку матрица $B$ не является полуположительно определенной, разложение знаков координат её максимального положительного собственного вектора указывает на оптимальное топологическое разбиение графа.

Графовое разложение в вероятностных графических моделях

В области вероятностного моделирования (байесовские сети, марковские случайные поля) графовая структура задает условные вероятностные зависимости между случайными величинами. Ключевая проблема здесь — точный логический вывод (англ. Exact Inference), то есть вычисление маргинальных или условных распределений $P(X_i \mid E)$ , где $E$ — подмножество известных признаков (свидетельств). Если граф содержит циклы, прямое применение алгоритма исключения переменных становится неэффективным. Решением является декомпозиция циклического графа зависимостей в ациклическое дерево мета-вершин.

Алгоритм сочлененного дерева (Junction Tree Algorithm)

Алгоритм сочлененного дерева (также известный как дерево клик) представляет собой каноническую процедуру структурного разложения произвольного ненаправленного или направленного графа^[1]. Процесс включает три строгие топологические стадии:

Морализация (Moralization): Применяется к направленным ациклическим графам (байесовским сетям). Для устранения направленности и сохранения зависимостей типа V-структур (общие потомки несамостоятельных предков) все «родительские» вершины каждого узла попарно соединяются ненаправленными ребрами («сочетаются браком»), после чего стрелки ребер отбрасываются. Полученный граф обозначается как $G_M$ .
Триангуляция (Triangulation): Процесс добавления хорд во все циклы графа $G_M$ длины более 3. Граф называется триангулированным (или хордальным), если любой его простой цикл длины $\ge 4$ имеет хорду — ребро, соединяющее две вершины цикла, не смежные в самом цикле. Триангуляция гарантирует существование совершенного порядка исключения вершин, что эквивалентно возможности разложения графа на иерархию вложенных клик.
Построение дерева клик: Из триангулированного графа выделяется множество всех максимальных клик (полных подграфов) $\mathcal{C} = \{C_1, C_2, \dots, C_k\}$ . Строится мета-граф, узлами которого являются данные клики. Ребро между двумя кликами $C_a$ и $C_b$ взвешивается размером их пересечения: $w_{ab} = |C_a \cap C_b|$ . Итоговое сочлененное дерево $T$ извлекается как максимальное остовное дерево (англ. Maximum Spanning Tree) данного мета-графа.

Свойство бегущего пересечения и передача сообщений

Чтобы разложение было корректным для вероятностного вывода, сочлененное дерево обязано удовлетворять свойству бегущего пересечения (англ. Running Intersection Property): если вершина исходного графа $x \in V$ принадлежит двум кликам $C_i$ и $C_j$ , она обязана принадлежать всем кликам, находящимся на уникальном пути между $C_i$ и $C_j$ внутри дерева $T$ . Пересечения между смежными кликами в дереве образуют сепараторы: $S_{ab} = C_a \cap C_b$ .

После проведения разложения совместное распределение исходной модели факторизуется по структуре дерева: $P(X) = \frac{\prod_{C_i \in \mathcal{C}} \psi_i(C_i)}{\prod_{S_{jk} \in \mathcal{S}} \phi_{jk}(S_{jk})}$ где $\psi_i$ и $\phi_{jk}$ — потенциалы клик и сепараторов соответственно.

Логический вывод на декомпозированной структуре реализуется через алгоритм передачи сообщений (Message Passing / Сумма-Произведение) между кликами через разделяющие их сепараторы. Сообщение от клики $C_a$ к клике $C_b$ вычисляется посредством маргинализации потенциалов по переменным, не входящим в сепаратор: ${M}_{a \to b}(S_{ab}) = \sum_{C_a \backslash S_{ab}} \psi_a(C_a) \prod_{n \in \text{nb}(a) \backslash \{b\}} M_{n \to a}(S_{na})$

Влияние древесной ширины на вычислительную сложность

Структурное разложение графа позволяет строго лимитировать сложность вероятностного вывода. Если исходные случайные величины являются дискретными и принимают $r$ значений, то вычислительная сложность алгоритма передачи сообщений на сочлененном дереве составляет: $O(n \cdot r^{\text{tw}(G) + 1})$ где $\text{tw}(G)$ — древесная ширина графа, полученная в ходе триангуляции^[1].

Таким образом, графовое разложение переводит экспоненциальную зависимость сложности от полного числа переменных модели $O(r^n)$ в экспоненциальную зависимость исключительно от топологического инварианта — древесной ширины. Если граф разрежен и обладает малой древесной шириной ( $\text{tw}(G) \ll n$ ), то декомпозиция делает точный вывод в модели вычислительно разрешимым.

Спектральное геометрическое глубокое обучение (Спектральные GNN)

Спектральное геометрическое глубокое обучение (англ. Spectral Geometric Deep Learning) обобщает классические архитектуры сверточных нейронных сетей (CNN) на неевклидовы области. В евклидовых пространствах (например, в анализе изображений) операция свертки строго определена через сдвиг ядра по регулярной сетке пикселей. На графах нерегулярность топологии и отсутствие локальной системы координат делают прямой пространственный сдвиг невозможным. Спектральные графовые нейронные сети (GNN) решают эту проблему, определяя операцию свертки в спектральном домене через преобразование Фурье, базис которого извлекается из спектрального разложения Лапласиана графа.

Преобразование Фурье на графе (Graph Fourier Transform)

Пусть задан вещественный сигнал на вершинах графа, представимый вектором $x \in \mathbb{R}^n$ . Преобразование Фурье на графе (GFT) использует ортонормированные собственные векторы Лапласиана $L = U \Lambda U^T$ в качестве базисных функций. Собственные векторы $u_i$ интерпретируются как графовые аналоги гармонических экспонент $e^{-i\omega t}$ , а соответствующие им собственные значения $\lambda_i$ выступают в роли частот.

Прямое преобразование Фурье отображает пространственный сигнал $x$ в спектральный домен: $\hat{x} = \mathcal{GF}\{x\} = U^T x$ Элемент спектра $\hat{x}_i$ характеризует амплитуду (интенсивность) частотной компоненты $\lambda_i$ в исходном сигнале. Низкие значения $\lambda_i$ соответствуют гладким, медленно меняющимся по топологии графа компонентам сигнала, в то время как высокие частоты фиксируют резкие локальные перепады.

Обратное преобразование Фурье реконструирует сигнал из частотного представления: $x = \mathcal{GF}^{-1}\{\hat{x}\} = U \hat{x}$

Теория спектральной свертки

Согласно классической теореме о свертке, свертка двух сигналов в пространственном представлении эквивалентна поточечному умножению их образов в частотном домене. Для графового сигнала $x$ и параметризованного фильтра $g_\theta$ операция спектральной свертки $\star_G$ строго формулируется как: $g_\theta \star_G x = \mathcal{GF}^{-1}\{\mathcal{GF}\{g_\theta\} \odot \mathcal{GF}\{x\}\} = U ( (U^T g_\theta) \odot (U^T x) ),$ где $\odot$ обозначает элементное произведение (произведение Адамара).

Если определить фильтр непосредственно в спектральном домене через диагональную матрицу потенциалов $g_\theta(\Lambda) = \text{diag}(U^T g_\theta) = \text{diag}(\hat{g}_{\theta, 1}, \dots, \hat{g}_{\theta, n})$ , выражение принимает канонический матричный вид: $g_\theta \star_G x = U g_\theta(\Lambda) U^T x$

Эволюция спектральных архитектур

Модель Бруны (2014)

В пионерской работе Бруны и др.^[1] фильтр $g_\theta(\Lambda)$ задавался набором свободных обучаемых параметров для каждой частоты: $g_\theta(\Lambda) = \text{diag}(\theta_1, \theta_2, \dots, \theta_n)$ . Данный подход обладал тремя критическими недостатками:

Высокая вычислительная сложность: процедура требует явного нахождения матрицы собственных векторов $U$ , что сопряжено со сложностью $O(n^3)$ и исключает масштабирование на большие графы.
Отсутствие пространственной локализации: изменение значения признака в одной вершине потенциально влияет на весь граф, так как базисные векторы $u_i$ имеют глобальный носитель.
Проблема непереносимости: число параметров фильтра жестко привязано к числу вершин $n$ . Обученный фильтр невозможно применить к графу другой размерности или топологии, поскольку спектральный базис $U$ уникален для каждого графа.

Сеть ChebNet (2016)

Для преодоления указанных ограничений Дефферрар и др.^[1] предложили аппроксимировать спектральный фильтр $g_\theta(\Lambda)$ усеченным рядом по полиномам Чебышева. Полином Чебышева $T_k(z)$ порядка $k$ определяется рекуррентным соотношением: $T_0(z) = 1, \quad T_1(z) = z, \quad T_k(z) = 2z T_{k-1}(z) - T_{k-2}(z)$

Аппроксимируемая функция от диагональной матрицы нормализованных частот $\tilde{\Lambda}$ записывается как: $g_\theta(\Lambda) \approx \sum_{k=0}^K \theta_k T_k(\tilde{\Lambda}), \quad \tilde{\Lambda} = \frac{2}{\lambda_{\text{max}}} \Lambda - I$ где $\theta \in \mathbb{R}^{K+1}$ — вектор подлежащих обучению чебышевских коэффициентов, а $\lambda_{\text{max}}$ — максимальное собственное значение Лапласиана.

Подстановка данной аппроксимации в операцию свертки приводит к математическому исключению спектрального базиса $U$ за счет свойства $U T_k(\tilde{\Lambda}) U^T = T_k(U \tilde{\Lambda} U^T) = T_k(\tilde{L})$ : $g_\theta \star_G x \approx U \left( \sum_{k=0}^K \theta_k T_k(\tilde{\Lambda}) \right) U^T x = \sum_{k=0}^K \theta_k T_k(\tilde{L}) x$ где $\tilde{L} = \frac{2}{\lambda_{\text{max}}} L - I$ — масштабированная матрица Лапласиана графа, спектр которой сдвинут в диапазон $[-1, 1]$ .

Вычислительная сложность ChebNet составляет $O(K \cdot m)$ , где $m$ — число ребер. Более того, поскольку операция включает умножение на степени матрицы Лапласиана $\tilde{L}^k$ , полученный фильтр является строго $K$ -локализованным: сигнал в каждой вершине обновляется на основе информации исключительно из её $K$ -шаговой топологической окрестности. При этом число параметров $K+1$ инвариантно к размеру графа.

Классическая графовая сверточная сеть GCN (2017)

Кипф и Веллинг упростили аппарат ChebNet, предложив первый порядок локализованной аппроксимации^[1]. В модели GCN накладываются ограничения $\lambda_{\text{max}} \approx 2$ и $K = 1$ . В этом случае выражение свертки редуцируется до: $g_\theta \star_G x \approx \theta_0 x + \theta_1 \left( L - I \right) x = \theta_0 x - \theta_1 D^{-1/2} A D^{-1/2} x$

Для предотвращения переобучения и сокращения числа параметров вводится регуляризационное предположение $\theta = \theta_0 = -\theta_1$ , что преобразует оператор к виду: $g_\theta \star_G x \approx \theta \left( I + D^{-1/2} A D^{-1/2} \right) x$

Собственные значения оператора $I + D^{-1/2} A D^{-1/2}$ лежат в диапазоне $[0, 2]$ . Многократное применение этого оператора в глубоких многослойных сетях приводит к взрыву или затуханию градиентов. Для стабилизации авторами был предложен трюк ренормализации (англ. renormalization trick): к исходной матрице смежности добавляются петли самосвязи (самопетли): $\tilde{A} = A + I$ , а новая диагональная матрица степеней вычисляется как $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$ .

Финальное матричное уравнение слоя классической сети GCN для матрицы признаков $H^{(l)} \in \mathbb{R}^{n \times d_l}$ имеет вид: $H^{(l+1)} = \sigma \left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)} \right)$ где $W^{(l)} \in \mathbb{R}^{d_l \times d_{l+1}}$ — матрица обучаемых весов линейного преобразования, а $\sigma$ — нелинейная функция активации (например, ReLU). Спектральное разложение здесь скрыто внутри симметричного сглаживающего оператора Лапласа.

Иерархическое разложение и пулинг в нейронных сетях

Стандартные графовые сверточные слои агрегируют информацию локально, сохраняя исходную размерность графа $n$ . Это эффективно для задач классификации отдельных вершин или ребер. Однако для задач классификации графа целиком (например, предсказание свойств молекул или функциональных сетей головного мозга) требуется получить единый фиксированный вектор макро-представления. Процесс поэтапного снижения пространственного разрешения графа с сохранением его глобальных свойств называется графовым пулингом (англ. Graph Pooling) или иерархическим укрупнением (англ. Graph Coarsening).

Задача укрупнения графа (Graph Coarsening)

Математическая цель укрупнения состоит в отображении исходного графа $G = (V, E)$ со сложной микроструктурой в последовательность меньших графов $G_1, G_2, \dots, G_L$ , макроструктура которых аппроксимирует фундаментальные геометрические и спектральные свойства оригинала. Физически это означает, что спектр Лапласиана укрупненного графа $\Lambda_{\text{coarse}}$ должен с минимальной погрешностью аппроксимировать область нижних (главных частотных) собственных значений исходного Лапласиана $\Lambda_{\text{fine}}$ , так как именно они кодируют макро-геометрию и глобальные сообщества сети.

Дифференциальный пулинг (DiffPool)

В отличие от детерминированных топологических методов сжатия (таких как алгоритм Graclus или алгебраическое многосеточное сжатие), алгоритм дифференциального пулинга (DiffPool^[1]) реализует сквозное дифференцируемое иерархическое разложение графа, оптимизируемое непосредственно градиентными методами в процессе обучения.

На каждом слое $l$ модель DiffPool параллельно решает две задачи: извлекает новые признаки вершин с помощью фильтров свертки и вычисляет матрицу мягкого (вероятностного) назначения вершин в кластеры следующего иерархического уровня.

Пусть на слое $l$ заданы текущая матрица смежности $A^{(l)} \in \mathbb{R}^{n_l \times n_l}$ и матрица эмбеддингов $H^{(l)} \in \mathbb{R}^{n_l \times d}$ . Архитектура использует две независимые GNN-архитектуры:

Эмбеддинг-сеть генерирует новые векторные представления вершин: ${Z}^{(l)} = \text{GNN}_{l, \text{embed}}(A^{(l)}, H^{(l)}) \in \mathbb{R}^{n_l \times d}$
Пулинг-сеть вычисляет матрицу распределения (назначения) вершин по мета-узлам следующего уровня $S^{(l)} \in \mathbb{R}^{n_l \times n_{l+1}}$ ( $n_{l+1} < n_l$ ): ${S}^{(l)} = \text{softmax}\left( \text{GNN}_{l, \text{pool}}(A^{(l)}, H^{(l)}) \right)$

Операция $\text{softmax}$ применяется построчно, гарантируя, что элемент $S_{ij}^{(l)} \in [0, 1]$ строго интерпретируется как степень принадлежности (вероятность отнесения) вершины $i$ к макро-кластеру $j$ .

Математическая декомпозиция и переход к укрупненной структуре слоя $l+1$ реализуются через операторы матричного проецирования:

Укрупнение признаков: строки матрицы представлений трансформируются под воздействием весов принадлежности:

$H^{(l+1)} = (S^{(l)})^T Z^{(l)} \in \mathbb{R}^{n_{l+1} \times d}$

Разложение и сжатие топологии: новая взвешенная матрица смежности мета-кластеров вычисляется как квадратичная форма:

$A^{(l+1)} = (S^{(l)})^T A^{(l)} S^{(l)} \in \mathbb{R}^{n_{l+1} \times n_{l+1}}$

Матрица $A^{(l+1)}$ является плотной, а её элементы отражают силу связей между выделенными макро-сообществами. Финальный вектор графа извлекается после полной декомпозиции структуры до $n_L = 1$ . Для предотвращения формирования тривиальных или несвязных кластеров в целевую функцию DiffPool внедряют регуляризацию через взаимную информацию (энтропийный штраф на разреженность матрицы $S^{(l)}$ ) и минимизацию нормы Лапласиана укрупненного графа.

Вычислительные аспекты, ограничения и критика

Вычислительная сложность и алгоритмы разреженных матриц

Полное спектральное разложение матрицы Лапласиана или матрицы смежности произвольного графа требует применения классических детерминированных методов (например, $QR$ -алгоритма или алгоритма закручивания) и характеризуется вычислительной сложностью $O(n^3)$ по времени и $O(n^2)$ по памяти, где $n$ — число вершин. Это делает прямое точное разложение неприменимым для крупномасштабных графов (миллионы и миллиарды узлов), оперирующих в реальных рекомендательных системах, поисковых индексах и социальных сетях.

В практических задачах машинного обучения эту проблему преодолевают за счет двух факторов. Во-первых, реальные пространственные графы в подавляющем большинстве являются разреженными, то есть число ребер $m \ll n^2$ , а матрицы Лапласа содержат преимущественно нулевые элементы. Во-вторых, для таких алгоритмов, как спектральная кластеризация, Laplacian Eigenmaps или ChebNet, нет необходимости извлекать весь спектр матриц — достаточно вычислить подпространство из $k$ наименьших (или наибольших) собственных векторов, где $k \ll n$ .

Использование итерационных методов Крылова, в частности алгоритма Ланцоша (англ. Lanczos algorithm) для симметричных матриц или метода Арнольди для асимметричных операторов, позволяет свести задачу декомпозиции к последовательности матрично-векторных умножений. Для разреженных структур сложность вычисления $k$ пар собственных значений снижается до $O(k \cdot m + k^2 n)$ по времени и $O(k \cdot n + m)$ по памяти. Тем не менее, при наличии кратных собственных значений или высокой плотности спектра (спектрального сгущения) сходимость итерационных методов Крылова резко замедляется, требуя внедрения сложных процедур спектрального сдвига и предобусловливания (англ. preconditioning).

Проблема пересглаживания (Oversmoothing)

Фундаментальным ограничением глубоких спектральных архитектур является эффект пересглаживания (англ. Oversmoothing). Оператор нормализованного Лапласа графа по своей математической сути представляет собой дискретный фильтр нижних частот (англ. low-pass filter). Применение одного слоя классической графовой свертки эквивалентно локальной диффузии — усреднению векторов признаков вершин по их непосредственной топологической окрестности.

Если нейросетевая архитектура наращивает количество слоев ( $l \to \infty$ ), многократное последовательное применение Лапласиана полностью подавляет высокочастотные компоненты графового сигнала. Математически доказано, что в процессе такого иерархического разложения векторы скрытых представлений всех вершин графа необратимо сходятся к единому стационарному подпространству. Для симметрично нормализованного оператора эмбеддинг $h_i$ каждой вершины становится прямо пропорционален квадратному корню из её топологической степени: $\lim_{l \to \infty} h_i^{(l)} \propto \sqrt{d(v_i)}$

В результате вершины полностью теряют свою индивидуальную информативность (уникальность признаков), их векторные представления коллапсируют в узкий конус вещественного пространства, а точность работы модели на тестовой выборке падает до уровня случайного угадывания^[1]. Скорость наступления пересглаживания жестко детерминирована величиной спектральной щели (англ. spectral gap) Лапласиана, определяемой как второе наименьшее собственное значение $\lambda_2$ (число Фидлера). Чем сильнее топологическая связность графа, тем меньше спектральная щель и тем быстрее наступает коллапс признаков, что исторически ограничивало глубину эффективных спектральных GNN всего 2–4 слоями.

Проблема пережатия информации (Oversquashing)

В то время как пересглаживание вызвано фильтрацией верхних частот, проблема пережатия информации (англ. Oversquashing) порождается сугубо топологическими свойствами разложения неевклидовых пространств. В большинстве реальных графов (граф типа «тесный мир», соцсети, молекулярные структуры) количество вершин в $r$ -шаговой окрестности растет экспоненциально относительно радиуса $r$ .

При этом пространственные или локально-спектральные фильтры нейросети вынуждены агрегировать информацию из этой экспоненциально расширяющейся окрестности в фиксированный по размеру вектор эмбеддинга $d$ центральной вершины. Возникает информационное «бутылочное горлышко» (англ. information bottleneck). При попытке модели зафиксировать дальнодействующие структурные зависимости (англ. long-range dependencies) через цепочки подграфов, емкости фиксированного вектора не хватает для кодирования комбинаторного объема топологических связей.

Интенсивность пережатия информации математически связана с локальным геометрическим инвариантом — кривизной Риччи на графах (в частности, дискретной кривизной Олливье — Риччи)^[1]. Ребра графа, обладающие сильно отрицательной кривизной Риччи, действуют как топологические мосты («узкие горлышка» между плотными кластерами). Они вызывают экстремальное пережатие информационных потоков при декомпозиции, что приводит к затуханию пространственных градиентов и потере далёких контекстных связей в процессе обучения.

См. также

Матрица Кирхгофа — фундаментальный линейный оператор дискретного анализа (Лапласиан графа), спектральное разложение которого служит основой для частотной фильтрации графовых сигналов и построения базиса Фурье.
Спектральная кластеризация — классический алгоритм нелинейного разбиения данных, основанный на непрерывной релаксации NP-трудной дискретной задачи нормализованного разреза через анализ младших собственных векторов Лапласиана.
Графовые нейронные сети — современный класс моделей глубокого обучения, развивающий концепцию алгебраического разложения графов до дифференцируемых пространственно-локализованных операторов свертки.
Вероятностные графические модели — декларативная парадигма описания совместных распределений, в которой топологическое разложение циклического графа зависимостей (триангуляция и построение дерева клик) преобразует экспоненциальную сложность логического вывода в линейную.
Сингулярное разложение — общая линейно-алгебраическая теорема о факторизации произвольных матриц, частным случаем которой для вещественных симметричных матриц смежности или модулярности графа является каноническое спектральное разложение.

Примечания

Литература

Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. — San Francisco: Morgan Kaufmann Publishers, 1988. — ISBN 978-1558604797
Godsil C., Royle G. Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — ISBN 978-0-387-95220-8
Hamilton W. L. Graph Representation Learning. — San Rafael: Morgan & Claypool Publishers, 2020. — ISBN 978-1681739625
Wainwright M. J., Jordan M. I. Graphical Models, Exponential Families and Variational Inference // Foundations and Trends in Machine Learning. — 2008. — Т. 1. — № 1–2. — С. 1–305.
Wu Z., Pan S., Chen F., Long G., Zhang C., Yu P. S. A comprehensive survey on graph neural networks // IEEE Transactions on Neural Networks and Learning Systems. — 2020. — Т. 32. — № 1. — С. 4–24.
Bronstein M. M., Bruna J., Cohen T., Veličković P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges // arXiv preprint arXiv:2104.13478. — 2021.

Источник — «http://www.recognition.su/wiki/index.php?title=%D0%93%D1%80%D0%B0%D1%84%D0%BE%D0%B2%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5»

Категории: Машинное обучение | Интеллектуальный анализ данных