Решение задач на графах
Для решения прикладных задач на графах необходимо построить эмбеддинги для каждой вершины графа. Эмбеддинги представляют собой вещественные вектора фиксированного размера и описывают признаки соответствующих вершин. Опционально информацию о графе можно дополнить эмбеддингами рёбер и эмбеддингом всего графа целиком.
Построение эмбеддингов вершин
Начальные эмбеддинги
Эмбеддинг вершины графа (node embedding) - это вектор вещественных чисел, характеризующий признаки вершин:
Этим вектором данных могут выступать начальные характеристики вершины. Например, если рассматривается граф социальной сети, в которой вершинами выступают пользователи, то может описывать пол, возраст и интересы, указанные в анкете. Если информации об узлах не предоставлено, можно задать её самостоятельно, передавая:
-
one-hot закодированный номер вершины (для небольших графов);
-
геометрические характеристики вершины (такие как число соседей первого, второго порядка, минимальные длины путей до выбранных опорных узлов графа).
Контекстное уточнение эмбеддингов
Используя геометрию графа, можно уточнять эмбеддинги вершин, учитывая контекстную информацию о соседних вершинах для каждого узла графа (neighborhood aggregation), аналогично тому, как уточнялись эмбеддинги слов в архитектуре т рансформера по контексту соседних слов. Для этого применяется итеративный алгоритм свёрточных графовых сетей (graph convolutional networks), описанный в следующей главе.
На выходе алгоритма мы получаем эмбеддинги каждой вершины с учётом контекста её соседей 1-го порядка (соединённых ребром напрямую), эмбеддинги с учётом контекста соседей 2-го порядка (соседей от соседей) и т.д. После итераций алгоритма получаем окончательные контекстные эмбеддинги (graph-based contextual embeddings), которые совместно будут храниться в матрице .
Задачи на графе целиком
Рассмотрим задачи, в которых известно некоторое свойство для графов и требуется предсказывать свойство для нового графа , содержащего вершин. Поскольку обучающие и тестовые данные разделены, то это классическая задача обучения с учителем (supervised learning) или индуктивного обучения (inductive learning).
Корректно специфицированная модель должна быть инвариантной к перенумерации вершин (invariance to permutation), то есть результат не должен зависеть от того, как именно мы пронумеруем вершины графа. Формально это записывается как
для любой матрицы перестановки вершин .
Регрессия
Для решения задачи регрессии на графе (например, определения температуры плавления химического соединения) можно усреднить все контекстные эмбеддинги, а затем линейно преобразовать, чтобы предсказать целевую величину:
где
-
- вектор из единиц;
-
- настраиваемые параметры.
Домножение на вектор из единиц и деление на число узлов означает усреднение эмбеддингов всех вершин.
В конце можно использовать перемасштабированную активацию гиперболического тангенса, чтобы поместить предсказываемую величину в разумный диапазон значений.
Бинарная классификация
Бинарную классификацию графа (например, классификацию веществ, описанных графом, на токсичные и безопасные для человека) можно производить по формуле:
где - сигмоидная функция активации (сигмоида).
Поскольку сигмоида принимает значения в интервале , то выход интерпретируется как вероятность положительного класса (вероятность токсичности вещества).