Message Passing — Передача сообщений

Единая схема, к которой сводятся почти все архитектуры GNN: собрать сообщения от соседей, агрегировать, обновить состояние.

h_{v}^{(k + 1)} = ϕ (h_{v}^{(k)}, u \in N (v) ⨁ ψ (h_{v}^{(k)}, h_{u}^{(k)}))

Что означает каждый компонент

$h_{v}^{(k)}$ текущее состояние вершины
$⨁$ агрегация по соседям: сумма, среднее или максимум — операция, не зависящая от порядка
$ψ (\cdot)$ сообщение от соседа: что именно передаётся по ребру

Ключевые тезисы

Агрегация должна быть инвариантна к порядку соседей: сумма, среднее, максимум.
Число слоёв равно радиусу, с которого собирается информация.
Мини-батчи строятся сэмплированием соседей — иначе один батч разрастается на весь граф.

Подробный разбор

2 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Единая схема

Три шага, к которым сводится любая GNN.

Message: для каждого ребра считаем сообщение из представлений вершин.
Aggregate: собираем сообщения соседей инвариантной к порядку операцией.
Update: обновляем состояние вершины по старому состоянию и агрегату.

h_{v}^{(k + 1)} = ϕ h_{v}^{(k)}, u \in N (v) ⨁ ψ (h_{v}^{(k)}, h_{u}^{(k)}, e_{uv})

Обозначения

$n$ число объектов в выборке
$k$ степень вершины — число её связей

Батчинг на графах

Как обучать, когда граф не помещается в память.

Neighbor sampling (GraphSAGE): для батча вершин берём случайную часть соседей на каждом слое.
Cluster-GCN: разбиваем граф на кластеры и обучаемся на подграфах.
Full-batch возможен только на графах в сотни тысяч вершин и при достаточной памяти GPU.

На практике

Сэмплирование соседей вносит шум в агрегацию — это одновременно и ограничение, и форма регуляризации.

Связанные темы

Машинное обучение на графах

Graph Basics85%

Основы графов · Графы и сети

Вершины, рёбра, веса и направления. Матрица смежности и список рёбер — два способа хранить одно и то же.

Centrality85%

Центральности · Графы и сети

Меры важности вершины: по числу связей, по посредничеству, по близости и по влиянию соседей.

PageRank85%

PageRank · Графы и сети

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

Community Detection85%

Поиск сообществ · Графы и сети

Разбиение графа на плотно связанные группы: клиенты одного круга, связанные аккаунты, тематические кластеры документов.

Graph Embeddings85%

Графовые эмбеддинги · Графы и сети

Векторные представления вершин, в которых близость отражает связанность в графе.

Graph Neural Networks85%

Графовые нейросети · Графы и сети

Нейросети, работающие прямо на структуре графа: представление вершины обновляется по представлениям соседей.

Link Prediction85%

Предсказание связей · Графы и сети

Задача «появится ли ребро между вершинами»: рекомендации друзей и товаров, достройка графов знаний.

Knowledge Graphs85%

Графы знаний · Графы и сети

Факты в виде троек «субъект — предикат — объект». Структурированная память, которую всё чаще подключают к языковым моделям.

Network Motifs85%

Мотивы и триады · Графы и сети

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

Clustering85%

Кластеризация · Обучение без учителя

Разбиение объектов на группы похожих без заранее известных меток.

Eigenvector85%

Собственный вектор · Математический справочник

Направление, сохраняющееся при линейном преобразовании с точностью до масштаба.