Графовые сети — это способ применения классических моделей нейронных сетей к графовым данным. Графы, не обладая регулярной структурой как изображения (каждый пиксель имеет 8 соседей) или тексты (последовательность слов), долгое время оставались вне поля зрения классических нейронных моделей, которые получили широкое распространение в области машинного обучения и искусственного интеллекта. Большинство моделей векторизации графов (построения векторного представления вершин в графе) были достаточно медленными и использовали алгоритмы на основе матричной факторизации или спектральной декомпозиции графа. В 2015-16 годах появились более эффективные модели (DeepWalk, Line, Node2vec, Hope) на основе случайных блужданий. Однако и они имели ограничения, потому что никак не затрагивали при построении векторной модели графа дополнительных признаков, которые могут храниться в вершинах или на ребрах. Появление графовых нейронных сетей стало логичным продолжением исследований в области графовых эмбеддингов и позволило унифицировать под единым фреймворком предыдущие подходы.

Для чего они нужны и как устроены

Один слой графовой нейросети — это обычный полносвязный слой (fully-connected layer) нейронной сети, но веса в нeм применяются не ко всем входным данным, а только к тем, которые являются соседями конкретной вершины в графе, в дополнение к ее собственному представлению с предыдущего слоя. Веса для соседей и самой вершины могут задаваться общей матрицей весов или двумя отдельными. Могут добавляться нормализации для ускорения сходимости; могут меняться нелинейные функции активаций, но общая конструкция остается похожей. При этом графовые сверточные сети получили свое название благодаря агрегации информации от своих соседей, хотя гораздо ближе к этому определению стоят графовые механизмы внимания (GAT) или индуктивная модель обучения (GraphSAGE).

Применение

Рекомендательные системы

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

Хотя в случае с рекомендациями продуктов питания графы получаются относительно небольшими из-за географических ограничений, однако в некоторых компаниях применяются нейросети с миллиардами связей. Например, китайский гигант Alibaba запустил в эксплуатацию графовые эмбеддинги и графовые нейросети применительно к миллиардам пользователей и товаров. Одно только создание таких графов — кошмар для разработчиков. Но благодаря конвейеру Aligraph можно всего за пять минут построить граф на 400 млн узлов. Впечатляет. Aligraph поддерживает эффективное, распределённое графовое хранилище, оптимизированные операторы выборок и кучу собственных графовых нейросетей. Сейчас этот конвейер используется для рекомендаций и персонализированного поиска по многочисленным продуктам компании.

Pinterest предложила модель PinSage, которая эффективно подбирает соседние узлы с помощью персонализированного PageRank и обновляет эмбеддинги вершин с помощью агрегирования информации от соседей. Следующая модель PinnerSage уже может работать с мультиэмбеддингами, чтобы учитывать разные вкусы пользователей. Это лишь пара примечательных примеров в сфере рекомендательных систем. Можете ещё почитать об исследовании Amazon графов знаний и графовых нейросетей, или об использовании компанией Fabula AI графовых нейросетей для определения фальшивых новостей. Но и без этого очевидно, что графовые нейросети демонстрируют многообещающие результаты при значительном сигнале от пользовательских взаимодействий.

Комбинаторная оптимизация

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

Команда Google Brain использовала графовые нейросети для оптимизации энергопотребления, площади и производительности чипов для нового оборудования вроде Google TPU. Компьютерный процессор можно представить в виде графа памяти и компонентов логики, каждый со своими координатами и типом. Определение местоположения для каждого компонента с учётом ограничений по плотности размещения и маршрутизации нагрузки до сих пор является трудоёмким процессом, произведением искусства инженеров-электронщиков. Сочетание графовой модели с политикой и обучением с подкреплением позволяет находить оптимальное размещение микросхем и создавать более производительные чипы по сравнению с разработанными людьми.

Другой подход подразумевает интеграцию модели машинного обучения в уже существующие инструменты решения. Например, коллектив под руководством М. Гасса предложил графовую сеть, которая обучается политикам выбора переменных по методу ветвей и границ: это критически важная операция в инструментах решения на основе частично-целочисленных линейных программ (mixed-integer linear program, MILP). В результате выученные представления пытаются минимизировать длительность работы инструментов решения и демонстрируют хороший компромисс между скоростью вывода и качеством решений.

В более свежей совместной работе DeepMind и Google графовые сети использованы в двух ключевых подзадачах, решаемых MILP-инструментами: совместном присвоении переменных и ограничении целевых значений. Предложенный подход на основе нейросетей оказался в 2-10 раз быстрее по сравнению с существующими инструментами решения при использовании огромных наборов данных, в том числе применяемых в Google систем упаковки продукции и планирования. Если вас интересует это направление, то можно порекомендовать пару недавних исследований (1, 2), в которых гораздо глубже обсуждается сочетание графовых нейросетей, машинного обучения и комбинаторной оптимизации.

Компьютерное зрение

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

В одной из работ Facebook описано, что можно поместить в кадр объекты из популярного набора данных COCO, задать их позиции и размеры, и на основе этой информации будет создан граф сцены. С его помощью графовая нейросеть определяет эмбеддинги объектов, из которых, в свою очередь, свёрточная нейросеть создаёт маски объектов, рамки и контуры. Конечные пользователи могут просто добавлять в граф новые узлы (определяя относительное положение и размеры узлов), чтобы нейросети могли генерировать изображения с этими объектами.

Другой источник графов в компьютерном зрении — сопоставление двух взаимосвязанных изображений. Это классическая задача, для решения которой раньше вручную создавали дескрипторы. Специализирующаяся на трёхмерной графике компания Magic Leap создала архитектуру на основе графовых нейросетей под названием SuperGlue. Эта архитектура позволяет в реальном времени сопоставлять видеозаписи для трёхмерного воспроизведения сцен, распознавания мест, одновременной локализации и построения карты (SLAM). SuperGlue состоит из графовой нейросети на основе механизма внимания. Она учит находить ключевые точки изображения, которые затем передаются на оптимальный транспортный слой для сопоставления. На современных видеокартах модель способна работать в реальном времени и может быть интегрирована в SLAM-системы. Подробнее о сочетании графов и компьютерного зрения рассказано в этих исследованиях: 1, 2.

Физика и химия

Представление взаимодействий между частицами или молекулами в виде графов и прогнозированием свойств новых материалов и веществ с помощью графовых нейросетей позволяет решать различные естественнонаучные задачи. Например, в рамках проекта Open Catalyst Facebook и CMU ищут новые способы хранения возобновляемой энергии солнца и ветра. Одно из возможных решений заключается в преобразовании этой энергии с помощью химических реакций в иные виды топлива, скажем, в водород. Но для этого нужно создать новые катализаторы высокоинтенсивных химических реакций, а известные сегодня методы вроде DFT очень до?роги. Авторы проекта выложили крупнейшую подборку катализаторов, DFT-затуханий и базовых уровней для графовых нейросетей. Разработчики надеются найти новые дешёвые симуляции молекул, которые дополнят текущие дорогие симуляции, выполняющиеся в течение дней, эффективными оценками энергии и межмолекулярных сил, которые вычисляются в течение миллисекунд.

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

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

Разработка лекарств

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

Вероятно, самым многообещающим результатом использования графовых нейросетей в этой сфере стала работа исследователей из MIT, опубликованная в Cell в 2020-м. Они применили модель глубокого обучения под названием Chemprop, которая прогнозировала антибиотические свойства молекул: подавление размножения кишечной палочки. После обучения всего лишь на 2500 молекул из библиотеки, одобренной Управлением по контролю за продуктами и лекарствами, Chemprop применили к более крупному набору данных, в том числе к Drug Repurposing Hub, содержащему молекулу Halicin, переименованную в честь ИИ HAL 9000 из фильма «Космическая одиссея 2001 года». Примечательно, что до этого Halicin изучали только применительно к лечению диабета, потому что её структура сильно отличается от известных антибиотиков. Но клинические эксперименты in vitro и in vivo показали, что Halicin является антибиотиком широкого спектра. Обширное сопоставление с сильными нейросетевыми моделями подчеркнуло важность обнаруженных с помощью графовых нейросетей свойств Halicin. Помимо практической роли этой работы архитектура Chemprop интересна и другим: в отличие от многих графовых нейросетей она содержит 5 слоев и 1600 скрытых измерений, что намного больше типичных параметров графовых нейросетей для таких задач. Надеюсь, что это было лишь одно из немногих ИИ-открытий в будущей новой медицине. Подробнее об этом направлении читайте здесь и здесь.

Когда графовые нейросети стали трендом

Пик популярности графовых эмбеддингов пришелся на 2018 год, когда предложенные в 2016 году модели структурных эмбеддингов и графовых нейронных сетей были проверены во многих практических приложениях и показали высокую эффективность, включая наиболее известный пример модели PinSAGE, используемой в рекомендациях социальной сети Pinterest. С тех пор рост исследований по этой тематике стал экспоненциальным, находится всe больше применений в областях, где раньше методы были не способны эффективно учитывать в моделях связи между объектами. Примечательно, что автоматизация машинного обучения и поиск новых эффективных архитектур нейронных сетей также получили новый толчок к развитию благодаря графовым нейронным сетям.

Являются ли они трендом и в России тоже

К сожалению, Россия в большинстве случаев отстает от современных исследований в области искусственного интеллекта. Количество статей на международных конференциях и в ведущих журналах на порядок меньше статей ученых из США, Европы и Китая, а финансовая поддержка исследований в новых областях встречает сопротивление в закостенелой среде академиков, застрявших в подходах из прошлого века и выдающих гранты скорее по принципу геронтократического кумовства, чем по реальным достижениям. В результате на ведущих конференциях, таких как TheWebConf, ICDM, WSDM, KDD, NIPS фамилии российских ученых в основном аффилированы с западными университетами, что отражает тенденцию на утечку мозгов, а также серьезную конкуренцию со стороны передовых стран в области разработки ИИ, в особенности Китая.

Если посмотреть на конференции в области компьютерных наук с наивысшим рейтингом A* по версии Core, например, конференции по высокопроизводительным вычислениям, то средний размер гранта у принятых в основной трек статей составляет $1 млн., что проигрывает максимальным программам от российского научного фонда в 15-30 раз. В таких условиях исследования, проводимые в крупных компаниях с организацией R&D, по сути являются единственными драйверами в поиске новых подходов на основе графовых нейронных сетей.

В России теорией графовых нейронных сетей занимаются в НИУ ВШЭ под моим руководством, также есть группы в Сколтехе и МФТИ, прикладные исследования ведутся в ИТМО, КФУ, а также в Лаборатории ИИ Сбера, в R&D-проектах JetBrains, Mail.ru Group, Yandex.

На мировой сцене драйверами являются компании Twitter, Google, Amazon, Facebook, Pinterest.

Мимолетная или долгосрочная тенденция?

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

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