Обобщённый автокодировщик на графах GraphEDM

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

Версия от 17:16, 30 июня 2026; Dan-Кhaiaa Lakpazhap (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM Claude Opus 4.7 и проверена участником Участник:Dan-Кhaiaa Lakpazhap 18:29, 30 июня 2026 (MSD).

Промпт приводится полностью в Обсуждение:Обобщённый автокодировщик на графах GraphEDM.

Обобщённый автокодировщик на графах (англ. Graph Encoder-Decoder Model, GraphEDM) — унифицированная теоретическая схема, описывающая широкий класс методов глубокого обучения на графах через парадигму «кодировщик — декодировщик» (автокодировщик). Схема была предложена в 2020 году в обзорной работе Инеса Чами, Сами Абу-Эль-Хайджи, Брайана Перроцци, Кристофера Ре и Кевина Мёрфи^[1] и обобщает более 30 ранее опубликованных моделей: от классических методов обучения представлений узлов (DeepWalk, node2vec) до современных графовых нейронных сетей и их вариаций — графовых свёрточных сетей (GCN, англ. Graph Convolutional Network), GraphSAGE, сетей внимания на графах (GAT, англ. Graph Attention Network) и графовых автокодировщиков (GAE и VGAE, англ. (Variational) Graph AutoEncoder).

Идея GraphEDM проста: почти любой метод машинного обучения на графах можно разложить на три «кубика». Первый — кодировщик (ENC), превращающий граф (например, социальную сеть или молекулу) в набор компактных числовых векторов — эмбеддингов — по одному на каждую вершину. Второй — декодировщик (DEC), который из этих векторов восстанавливает то, что нас интересует: связи между вершинами, метки классов, свойства всего графа. Третий — функция потерь, указывающая, насколько хорошо модель справилась, и позволяющая обучать её методом градиентного спуска. Такая «общая сборка» помогает сравнивать разные модели на равных, видеть их общие свойства и проектировать новые архитектуры по аналогии.

Мотивация

К 2020 году в литературе накопилось несколько десятков методов обучения на графах, развивавшихся параллельно и пользовавшихся разной терминологией. Спектральные подходы выросли из спектральной теории графов, методы случайных блужданий (DeepWalk, node2vec) — из идей, близких к Word2vec, графовые нейронные сети — из аналогии со свёрточными сетями для изображений. Внешне эти подходы выглядели несовместимо, хотя решали одну задачу: получить полезные числовые представления вершин графа.

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

выбором кодировщика (от простой матричной факторизации до глубокой нейронной сети);
тем, что именно восстанавливает декодировщик (структуру графа, метки или и то, и другое);
балансом между обучением с учителем и без учителя в функции потерь.

Постановка задачи

Пусть задан граф $G = (V, E)$ , где $V$ — множество из $n$ вершин (узлов), а $E \subseteq V \times V$ — множество рёбер (связей). Например, в социальной сети вершины — это пользователи, а рёбра — их дружбы; в молекуле — атомы и химические связи между ними; в графе цитирований — статьи и ссылки между ними.

Граф представляют двумя матрицами:

матрица смежности $W \in \mathbb{R}^{n \times n}$ (англ. adjacency matrix) — «карта связей»: элемент $W_{ij}$ равен весу ребра между вершинами $i$ и $j$ (или нулю, если связи нет);
матрица признаков узлов $X \in \mathbb{R}^{n \times d_0}$ (англ. node features) — таблица атрибутов: каждой вершине сопоставлен вектор из $d_0$ чисел (например, для пользователя соцсети — возраст, город, интересы).

Цель — построить матрицу эмбеддингов $Z \in \mathbb{R}^{n \times d}$ , где $d \ll n$ . Каждая строка $z_i$ — это короткий вектор, «сжатое описание» $i$ -й вершины, в котором сохранено самое важное: и её положение в структуре графа, и её признаки. На таких векторах удобно решать прикладные задачи: классифицировать вершины (например, определять тематику научной статьи в графе цитирований), предсказывать новые связи (англ. link prediction — например, рекомендовать дружбу), классифицировать графы целиком (определять токсичность молекулы) или искать сообщества^[1].

Различают два режима обучения: трансдуктивный (англ. transductive), когда модель видит весь граф сразу и предсказывает метки только для его части (полу-обучение с учителем), и индуктивный (англ. inductive), когда обученная модель должна обобщаться на новые, ранее не виденные вершины или целые графы.

Общая архитектура

В рамках GraphEDM любая модель машинного обучения на графах представляется как композиция трёх отображений^[1].

Графовый кодировщик

Кодировщик (англ. graph encoder) «читает» граф и выдаёт эмбеддинги:

$Z = \mathrm{ENC}(W, X; \Theta^E),$

где $\Theta^E$ — обучаемые параметры (веса). Можно представлять его как функцию, которая для каждой вершины смотрит на её собственные признаки и на признаки соседей и сжимает всю эту информацию в один короткий вектор.

По устройству кодировщики делят на:

поверхностные (англ. shallow) — фактически просто таблица «вершина → вектор», в которой векторы обучаются как обычные параметры (по одному набору на каждую конкретную вершину). Так устроены DeepWalk и node2vec. Минус: модель привязана к конкретному графу и не умеет обобщаться на новые вершины;
линейные — например, спектральное разложение лапласиана графа;
глубокие — многослойная графовая нейронная сеть, каждый слой которой агрегирует информацию от соседей. Такие кодировщики работают как функция от признаков, поэтому могут обобщаться на новые вершины и графы.

Графовый декодировщик

Декодировщик (англ. graph decoder) решает обратную задачу: из векторов $Z$ пытается восстановить либо структуру графа, либо нужные метки. В общем виде он распадается на два под-декодировщика:

Структурный декодировщик $\widehat{W} = \mathrm{DEC}_G(Z; \Theta^S)$ восстанавливает матрицу смежности или её часть. Типичный пример — оценка вероятности существования ребра между вершинами $i$ и $j$ :

$\hat{W}_{ij} = \sigma(z_i^\top z_j),$

где $\sigma$ — сигмоида, а $z_i^\top z_j$ — скалярное произведение эмбеддингов. Идея интуитивна: если две вершины «похожи» (их векторы сонаправлены), они с большей вероятностью связаны.

Декодировщик меток $\widehat{y} = \mathrm{DEC}_Y(Z; \Theta^Y)$ — обычная нейронная сеть-классификатор или регрессор поверх эмбеддингов, выдающая прогноз для задачи с учителем.

Функция потерь

Полная функция потерь GraphEDM — взвешенная сумма трёх компонент:

$\mathcal{L} = \alpha \, \mathcal{L}_{\mathrm{sup}}(y, \widehat{y}; \Theta) + \beta \, \mathcal{L}_{G,\mathrm{recon}}(W, \widehat{W}; \Theta) + \gamma \, \mathcal{L}_{\mathrm{reg}}(\Theta),$

где:

$\mathcal{L}_{\mathrm{sup}}$ — контролируемая потеря (англ. supervised loss), штраф за неверный прогноз меток (например, перекрёстная энтропия в классификации);
$\mathcal{L}_{G,\mathrm{recon}}$ — потеря реконструкции графа (англ. graph reconstruction loss), штраф за то, что декодировщик плохо восстановил структуру связей;
$\mathcal{L}_{\mathrm{reg}}$ — регуляризатор (например, $L_2$ -норма параметров), не дающий модели «переобучиться»;
$\alpha, \beta, \gamma \geq 0$ — гиперпараметры, балансирующие три цели.

Ключевое свойство схемы состоит в том, что выбор коэффициентов $\alpha, \beta, \gamma$ и конкретного вида ENC и DEC однозначно определяет, к какому семейству относится модель. Например, при $\alpha = 0$ мы получаем «чистое» обучение без учителя, при $\beta = 0$ — обычную графовую классификацию.

Таксономия моделей

GraphEDM систематизирует методы по двум осям: (а) есть ли в данных метки (с учителем / без учителя) и (б) каков тип кодировщика (поверхностный или глубокий)^[1].

Методы без учителя

При $\alpha = 0$ модель учится самостоятельно — её задача восстанавливать структуру графа из эмбеддингов.

Методы матричной факторизации: Laplacian Eigenmaps^[1], Graph Factorization, GraRep, HOPE. Кодировщик линейный, декодировщик восстанавливает функцию от $W$ (например, саму матрицу смежности или матрицу совстречаемостей).
Методы случайных блужданий: DeepWalk^[1], node2vec^[1], LINE. Идея: запустить из каждой вершины «прогулку» по графу, а затем выучить эмбеддинги так, чтобы часто встречающиеся вместе вершины имели похожие векторы — почти как Word2vec для слов, только вместо предложений используются траектории случайных блужданий.
Графовые автокодировщики (GAE и VGAE)^[1]. Кодировщик — графовая нейронная сеть, декодировщик восстанавливает $W$ через скалярное произведение эмбеддингов. VGAE — вероятностная (вариационная) версия, ближайший «графовый родственник» вариационных автокодировщиков.

Методы с учителем

При $\alpha > 0$ модель явно оптимизирует контролируемую цель (например, классификацию вершин), при необходимости дополнительно регуляризуясь графом.

Графовые свёрточные сети (GCN)^[1]. Кодировщик послойно обновляет представления:

$H^{(l+1)} = \sigma\!\left( \tilde{D}^{-1/2} \tilde{W} \tilde{D}^{-1/2} H^{(l)} \Theta^{(l)} \right),$

где $\tilde{W} = W + I$ — матрица смежности с добавленными «петлями» (чтобы вершина учитывала и саму себя), $\tilde{D}$ — соответствующая диагональная матрица степеней, $H^{(0)} = X$ , а $\sigma$ — нелинейность (обычно ReLU). Грубо говоря, на каждом слое каждая вершина «усредняет» признаки своих соседей и пропускает результат через нелинейность; нормировка $\tilde{D}^{-1/2} \cdot \tilde{D}^{-1/2}$ нужна для того, чтобы вершины с большим числом соседей не «доминировали» в обновлениях.

GraphSAGE^[1] — индуктивное расширение GCN: агрегирует не всех соседей, а случайную выборку, что позволяет работать с очень большими графами и обобщать на новые, не виденные при обучении вершины.
Graph Attention Networks (GAT)^[1] — соседи агрегируются с разными весами, которые модель учит сама через механизм внимания: «более важным» соседям достаётся больше веса.
Сети передачи сообщений (англ. Message Passing Neural Networks, MPNN)^[1] — обобщающий взгляд: вершины обмениваются «сообщениями» по рёбрам и обновляют состояния. Большинство современных архитектур, включая GCN, GraphSAGE и GAT, укладываются в эту схему.

Современные расширения

После публикации GraphEDM появились новые семейства моделей, также описываемые этой схемой, но с более сложными кодировщиками:

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

Связь с другими подходами

Обучение представлений — эмбеддинги, получаемые ENC, и есть результат такого обучения; GraphEDM описывает, как извлекать представления из нерегулярных структур.
Классические автокодировщики — GraphEDM можно рассматривать как обобщение вариационных автокодировщиков на графы^[1].
Геометрическое глубокое обучение (англ. geometric deep learning)^[1] — общая программа обучения на нерегулярных областях (графы, многообразия, группы), в которую GraphEDM встраивается как частный случай для графов.
Спектральная теория графов — многие кодировщики опираются на собственные функции лапласиана.

Применения

Биоинформатика и хемоинформатика: предсказание свойств молекул, поиск лекарств^[1], моделирование белок-белковых взаимодействий и сворачивания белков (в частности, в AlphaFold идеи передачи сообщений используются для уточнения структуры).
Рекомендательные системы: граф «пользователь — товар»; модель PinSage, разработанная в Pinterest на основе GraphSAGE^[1], работает на графе из миллиардов рёбер.
Обработка естественного языка: графы знаний, синтаксические деревья.
Социальные сети: детектирование сообществ, предсказание связей, моделирование распространения влияния.
Компьютерное зрение: сцены как графы объектов, точечные облака в трёхмерной графике.
Физика и моделирование: симуляция систем N тел, предсказание динамики частиц и жидкостей^[1].

Для практической работы со схемой GraphEDM существуют специализированные библиотеки на основе PyTorch и TensorFlow — PyTorch Geometric (PyG), Deep Graph Library (DGL) и Spektral, реализующие большинство упомянутых архитектур в виде готовых модулей.

Ограничения и открытые проблемы

Переглаживание (англ. over-smoothing) — если сделать сеть слишком глубокой, эмбеддинги всех вершин «расплываются» и становятся почти одинаковыми, теряя способность их различать^[1].
Бутылочное горлышко (англ. over-squashing) — экспоненциальное «сжатие» информации, идущей от дальних вершин: длинные зависимости передать тяжело, поскольку информация от $k$ -удалённой вершины «протискивается» через сужающиеся участки графа^[1].
Ограниченная выразительная сила — большинство MPNN-моделей по способности различать графы не превосходят теста Вейсфейлера — Лемана первого порядка (1-WL), то есть существуют структурно разные графы, которые такая сеть в принципе не отличит^[1].
Масштабируемость к графам с миллиардами рёбер требует специальных приёмов (выборка соседей, кластеризация подграфов, разреженные представления).
Динамические и гетерогенные графы — графы, меняющиеся во времени или содержащие вершины и рёбра разных типов, остаются областью активных исследований.

См. также

Примечания

Литература

Chami I., Abu-El-Haija S., Perozzi B., Ré C., Murphy K. Machine Learning on Graphs: A Model and Comprehensive Taxonomy // Journal of Machine Learning Research. — 2022. — Т. 23. — № 89. — С. 1–64.
Hamilton W. L. Graph Representation Learning // Synthesis Lectures on Artificial Intelligence and Machine Learning. — 2020. — Т. 14. — № 3. — С. 1–159.
Ma Y., Tang J. Deep Learning on Graphs. — Cambridge University Press, 2021. — ISBN 978-1108831741
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. — 2021. — Т. 32. — № 1. — С. 4–24.
Bronstein M. M., Bruna J., Cohen T., Veličković P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. — 2021.
Kipf T. N., Welling M. Semi-Supervised Classification with Graph Convolutional Networks // ICLR. — 2017.
Veličković P., Cucurull G., Casanova A., Romero A., Liò P., Bengio Y. Graph Attention Networks // ICLR. — 2018.
Hamilton W. L., Ying R., Leskovec J. Inductive Representation Learning on Large Graphs // NeurIPS. — 2017.
Ying C., Cai T., Luo S., Zheng S., Ke G., He D., Shen Y., Liu T.-Y. Do Transformers Really Perform Bad for Graph Representation? // NeurIPS. — 2021.
Topping J., Di Giovanni F., Chamberlain B. P., Dong X., Bronstein M. M. Understanding over-squashing and bottlenecks on graphs via curvature // ICLR. — 2022.
Sanchez-Lengeling B., Reif E., Pearce A., Wiltschko A. B. A Gentle Introduction to Graph Neural Networks2021.
Fey M., Lenssen J. E. PyTorch Geometric Documentation2024.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D0%BE%D0%B1%D1%89%D1%91%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D1%89%D0%B8%D0%BA_%D0%BD%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%85_GraphEDM»

Категории: Машинное обучение | Глубокое обучение | Теория графов | Искусственные нейронные сети