Укрощение графов

Банки ищут мошенников по цепочкам переводов между счетами. Маркетплейсы подбирают товары по связям между покупателями и покупками. Логистические компании строят маршруты по сети складов и дорог, а поисковики отвечают на вопросы с помощью графов знаний. Во всех этих задачах важны не только свойства отдельных объектов, но и связи между ними, и для такой работы созданы графовые нейросети. Индустриальные графы насчитывают десятки миллиардов связей, и работа с ними упирается в нехватку памяти и низкую скорость обработки постоянно меняющихся данных. Вместе с исследователями AI VK, которые представят на конференции CIKM 2026 свой подход к работе с графовыми нейросетями, рассказываем, как эти задачи решаются сегодня.

Граф вместо таблицы

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

Поэтому задача подбора возможных друзей в корне отличается от рекомендаций контента. Современные рекомендательные системы сочетают два подхода. Первый опирается на описание самого объекта: жанр, режиссер, актеры, темп музыки. Если человек любит скандинавские детективы, ему предложат еще один. Второй подход называется коллаборативной фильтрацией, и он работает без описаний вовсе. Система замечает, что люди с похожей историей любят похожие вещи, и советует то, что пришлось по нраву вашим «братьям» по вкусу. Сверху добавляются неявные сигналы: что человек досмотрел до конца, что пролистал через пять секунд, в какое время суток и с какого устройства смотрит контент. Из тысяч таких мелочей складывается довольно точная картина того, что ему нравится. С дружбой так не получается. Фильм не может отказаться от зрителя, а человек может отклонить заявку. Рекомендация срабатывает, только если интерес взаимный, то есть система должна угадать желания сразу двоих. Явных оценок вроде количества лайков здесь нет, а анкета с возрастом, полом и городом мало что говорит о совместимости людей. Зато есть то, чего нет у фильмов — окружение: кто друзья человека, насколько тесно они связаны между собой, как их круги пересекаются.

Как думает графовая нейросеть

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

Механику можно представить на примере сбора информации о знакомых. Допустим, каждый пользователь сначала собирает сведения о своих друзьях: кто они, с кем общаются, какие у них интересы. Затем он объединяет эти данные со своими. На втором этапе пользователь получает уже собранную его друзьями информацию об их знакомых и тоже добавляет её к своей. Так за два раунда обмена данными в цифровом представлении человека появляется информация не только о его друзьях, но и о друзьях его друзей. Именно так графовая модель постепенно расширяет контекст, в котором рассматривает каждого пользователя.

В итоге информация о каждом пользователе превращается в эмбеддинг — сжатое числовое описание пользователя в виде вектора из нескольких сотен чисел. Обновленное представление пользователя на каждом шаге пересчитывается из его прежнего вектора и взвешенной суммы векторов соседей. Чтобы оценить, подружатся ли два человека, модель сравнивает их числовые описания. В системе VK у каждого пользователя два таких вектора: один для роли «кому рекомендуют», другой для роли «кого рекомендуют». Это важно, потому что популярный человек и активный искатель друзей ведут себя по-разному. 

AI VK использует архитектуру GATv2 с механизмом внимания. Она помогает модели оценивать, какие связи между людьми важнее для рекомендации. Например, если у пользователя много контактов, модель может учитывать не только сам факт дружбы, но и то, насколько люди связаны между собой и есть ли у них общие знакомые. Это помогает отличать близкий круг общения от случайных контактов и точнее находить людей, с которыми пользователь, вероятно, захочет подружиться. 

Почему в теории просто, а на практике нет

На учебных датасетах в графе несколько тысяч вершин и GNN (graph neural network, графовая нейросеть) обучается за минуты. Социальный граф VK в исследовании насчитывает 194 миллиона пользователей и 28 миллиардов связей. Авторы выделяют три ограничения, которые на таком масштабе не позволяют применять стандартные алгоритмы:

• Размер. Один только граф пользователей, записанный максимально компактно, занимает около 225 гигабайт оперативной памяти. Хуже другое — из-за пользователей с десятками тысяч друзей, окружение растет взрывообразно. Уже на расстоянии двух шагов от одного человека могут оказаться десятки миллионов аккаунтов. Опросить их все ради одного прогноза невозможно.
• Слабые признаки. Анкетных данных у модели VK всего три: пол, возраст и число друзей. Этого явно мало, поэтому каждому пользователю хочется дать собственный эмбеддинг, который модель будет строить в ходе обучения. Но таблица из 200 миллионов векторов по 256 четырехбайтовых чисел занимает около 205 ГБ. Такой объем не поместить в память видеокарты, что сильно усложняет работу системы в продакшене.
• Динамика. Граф постоянно меняется, а модель учится на истории показов рекомендаций. Если при обучении она видит граф целиком, как он выглядит сегодня, то незаметно «подглядывает» в будущее. Например, модель «знает», что два человека подружились через месяц после показа, и учится на этой подсказке. В реальной работе такой подсказки не будет, и качество окажется хуже, чем предсказывалось на тестах. Это называется утечкой данных.

Как ученые умеют ужимать графы

Проблема масштаба в графовых нейросетях известна давно, и за последние десять лет появился целый набор приемов. Их общая идея — уменьшить объем данных, который проходит через модель за один шаг обучения.

Самый простой способ — не опрашивать всех соседей, а брать случайную выборку. Так устроена модель GraphSAGE, которую в 2017 году предложили Уильям Гамильтон и его коллеги из Стэнфорда. Вместо полного окружения она берет фиксированное число соседей на каждом шаге, например, 25 на первом и 10 на втором. Объем вычислений перестает зависеть от того, сколько друзей у человека на самом деле. Заодно GraphSAGE умеет строить представления для вершин, которых не было при обучении.

Следующие работы сделали выборку умнее. FastGCN отбирает вершины не случайно, а по важности, чтоб небольшая выборка лучше представляла весь граф. Cluster-GCN от исследователей из Google сначала разрезает граф на плотные кластеры и обучает модель на них по очереди: внутри кластера большинство связей остается, а памяти нужно гораздо меньше. GraphSAINT собирает куски из небольших случайных подграфов и подправляет статистическое смещение, которое возникает от того, что вершины с множеством связей попадают в такие куски чаще. Модель стала бы придавать им лишний вес, поэтому GraphSAINT оценивает частоту попадания каждой вершины и делает поправку.

До индустриальных масштабов одним из первых дошел Pinterest. Его модель PinSage работала на графе из 3 миллиардов вершин и 18 миллиардов ребер — пинов и досок, в которые пользователи их собирают. Соседей PinSage выбирала с помощью случайных блужданий: важными считались те вершины, на которые блуждание попадает чаще всего.

Отдельная линия исследований касается графов, которые меняются со временем. TGAT использует временное кодирование, в частности, кодирует временные расстояния между событиями и моментом, для которого строится представление. Temporal Graph Networks добавили каждой вершине «память», которая обновляется с каждым новым событием. Обе модели следят за тем, чтобы прошлое не смешивалось с будущим. Представление пользователя на момент времени t строится только из связей и событий с отметкой времени раньше t. TGAT, к примеру, передает модели возраст каждой связи, так что свежая и давняя дружба весят по-разному. 

Что придумали в AI VK

Исследователи взяли стандартную выборку соседей в духе GraphSAGE и PinSage: модель смотрит на два шага вокруг пользователя и на каждом шаге берет не более 30 соседей. А дальше добавили два решения, которые закрывают оставшиеся проблемы:

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

Это можно сравнить с тем, как людей различают по одежде. Курток одного цвета в городе тысячи, кроссовок одной модели тоже, так же и рюкзаков, но комбинация «эта куртка, эти кроссовки, этот рюкзак» почти уникальна. Так и здесь — отдельная строка таблицы достается многим пользователям, а вот совпадение всех трех строк у двух человек практически исключено. Обучаемая таблица при этом занимает два гигабайта, то есть меньше процента от исходного объема. 

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

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

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

В цифрах это выглядит так. Наивный перебор тратил на подготовку одной порции данных 1 473 миллисекунды, бинарный поиск — 595 миллисекунд. Выборка без учета времени заняла бы 581 мс, то есть корректность почти не стоит процессорного времени. 

Благодаря обоим приемам вся система обучается и работает на одном сервере с восемью видеокартами NVIDIA A100. Граф лежит в оперативной памяти, а все обучаемые параметры помещаются на одну видеокарту.

Зачем это всей индустрии

Графы окружают нас повсюду. Покупатели и товары на маркетплейсах образуют граф покупок. Банковские счета и переводы между ними — граф, в котором антифрод-системы ищут подозрительные цепочки. Ученые, их вузы и совместные статьи образуют графы с тысячами и миллионами вершин. Крупные платформы уже тестируют и используют графовые нейросети в рекомендациях друзей и контактов. Это GraFRank от Snapchat, SSNet для Xbox и LiGNN от LinkedIn. Amazon и Snap выпустили собственные фреймворки для обучения GNN на огромных графах.

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

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

Что показали тесты и где границы

Сначала модель проверили на исторических данных: 1,4 миллиарда показов рекомендаций для обучения и 25 миллионов для проверки. Качество измеряли метрикой ROC-AUC, которая показывает, как часто модель ставит принятого в друзья кандидата выше отвергнутого. Случайное угадывание дает 0,5, ранжирование по количеству друзей у пользователя дало 0,505, классическая матричная факторизация — 0,532, прежняя модель VK — 0,557, новая графовая — 0,628.

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

Оценку новой модели добавили как признак в действующую систему ранжирования и две недели сравнивали ее с прежней версией в А/В-тесте. Число добавлений в друзья из рекомендаций выросло на 16 процентов, а число людей, которые добавили хотя бы одного рекомендованного друга, — на 11,5 процента. Время отклика системы при этом не увеличилось.

У новой модели тем не менее есть и ограничения:

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

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