Как вы помните, я обещал еженедельно выкладывать хотя бы один | Матчасть

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

Объясняю задачу. Направленный граф - это множество объектов (вершин), некоторые из которых попарно соединены стрелочками (рёбрами), отражающими какое-то отношение между ними. Например, вершины могут быть юзерами соцсети, а рёбра - наличием подписки. Фичи в вершинах - это какой-то набор их характеристик; например, для юзера фичами может быть имя, аватарка, bio, число постов. Заэмбеддить - значит, вычислить какие-то векторные представления вершин, учитывающие структуру графа. И как же это сделать?

Подход 0, базовый. Игнорируем граф, и просто эмбеддим каждую вершину по отдельности. Имя и bio прогоняем через какие-то текстовые нейросетки, аватарку - через картиночную нейронку, на выходе получаем векторы фиксированной длины. И, допустим, конкатенируем их. Если результат получится слишком длинный, можно попробовать применить к нему алгоритм сокращения размерности. Дополнительно можно прикрепить число входящих и исходящих рёбер, т.е. число подписчиков и подписок. Это просто счётчики, не жалко. Готово, у нас есть хоть какое-то представление вершины. Пусть для вершины i такое представление равно f[i].

Подход 1, учёт непосредственных соседей. Мы можем обогатить представление вершины агрегированными представлениями её связей первого порядка. Обогащать будем, просто конкатенируя вектора. Агрегировать будем, например, усреднением. Будем отдельно агрегировать тех, кто подписан на юзера (children), и тех, на кого юзер подписан (parents). То есть представление вершины i можно теперь вычислить как f[i] & mean(f[childen(i)]) & mean(f[parents(i)]), где & - символ конкатенации. Такое представление выглядит уже весьма юзабельным.

Подход 2, чисто графовый. Забиваем на фичи, и строим эмбеддинги чисто по графу. Здесь проще всего провести аналогию с эмбеддингами слов: мы обучаем модель, чтобы по какому-то "контексту" вершины предсказывать её, подобно тому, как по тексту с пропуском алгоритмы типа word2vec и BERT предсказывают пропущенное слово. "Контекстом" будет какое-то случайное множество вершин, находящихся недалеко от данной - например, его можно насэмплить короткими случайными блужданиями из данной вершины. В случае с направленным графом контекста может быть два - для входящих и исходящих связей. Какая-нибудь небольшая нейронка в процессе предсказания вершины по контексту вполне может выучить её эмбеддинг, дающий полезную информацию о её положении в графе.