Есть известная цитата мотивационного оратора Джима Рона:

«Вы представляете собой среднее из пяти человек, с которыми вы проводите больше всего времени».

Вот еще один: «Покажи мне своих друзей, и я покажу тебе твое будущее». Возможно, вы встречали эти цитаты в какой-то момент времени, но задумывались ли вы когда-нибудь об их существовании вне философии? Что ж, давайте выясним это, изучив недавнюю разработку в области машинного обучения (ML) — Graph Neural Networks (GNN).

Как следует из названия, GNN представляют собой расширенное семейство нейронных сетей, специально разработанных для обучения на основе структур данных graph, таких как социальные сети друзей, молекулярные структуры и т. д. Что такое нейронные сети? Во-первых, их можно рассматривать как аппроксиматоры функций, то есть они пытаются изучить лежащую в основе скрытую функцию, просматривая ваши данные. Граф — это структура данных, представляющая объекты реального мира, известные как узлы, и их взаимодействия через ребра. Он также может содержать дополнительную информацию, такую ​​как атрибуты как узлов, так и ребер.

В этой статье мы рассмотрим популярный алгоритм GNN: GraphSAGE [1]. Цель состоит в том, чтобы вычислить краткое представление узлов, которое фиксирует не только их собственную информацию, но и информацию об их окружении. Это итеративный алгоритм, в котором соседние узлы обмениваются информацией друг с другом в каждом раунде посредством сообщений, содержащих такую ​​информацию, как атрибуты узла/ребра. Позже каждый узел объединяет сообщения от своих соседей и свою собственную информацию, чтобы получить обновленное представление.

На рисунке 1 представлен обзор GraphSAGE для визуального понимания, а на рисунке 2 показан алгоритм, входные данные которого состоят из следующего:
(1) График 𝒢 (𝒱, ℰ): это основная часть входных данных, состоящая из набор узлов (вершин) 𝒱 и ребер ℰ, который представляет реальную сеть. Рассмотрим пример социальной сети пользователей в виде узлов и ребер, символизирующих дружбу, т. е. ребро (𝓊, 𝓋) представляет, что 𝓊 и 𝓋 являются друзьями.
(2) Входные признаки (𝐱_𝓋 ∀ 𝓋 ∈ 𝒱): Это относится к атрибутам или исходной априорной информации, которую мы имеем о каждом узле в графе. Рассматривайте это представление как вектор или список пользовательских предпочтений по различным измерениям (см. «Атрибуты узла» на рисунке 1).
(3) Глубина 𝐾: представляет количество слоев блоков GNN, наложенных друг на друга или, интуитивно, как дальше вы хотите искать окрестности узла (окружение) для сбора/отправки информации.
(4) Веса 𝐖^𝑘: внутренние параметры 𝑘-го слоя модели и изучаются через другие методы оптимизации.
(5) Функция агрегатора Агрегат_𝑘: стратегия объединения собранной информации после получения сообщений на узле. Это может быть разным для каждого слоя; таким образом, индекс 𝑘. Например, сложение всей информации или получение среднего значения.
(6) Окрестность 𝒩: Эта функция определяет окружение узла при сборе/отправке информации. Для простоты это могут быть его соседние узлы.

Результатом алгоритма GNN является сжатое представление для каждого узла, которое захватывает как априорную информацию о его атрибутах, с которых мы начали, и информацию о его окружении в структуре сети. Последняя информация (также называемая локальным контекстом) — это то, что GNN стремятся зафиксировать. Где можно использовать эту информацию, спросите вы. Эти представления являются мощными индикаторами для различных задач, например, рекомендации друзей. Допустим, Боб и Алиса еще не знакомы, но у них много общих друзей. Модель рекомендаций теперь может легко идентифицировать потенциальную связь между ними, поскольку их локальное окружение (контексты) существенно перекрываются в новых представлениях, полученных с помощью GNN.

Алгоритм начинается с итераций передачи сообщений, когда каждый узел отправляет (собирает) информацию своим соседям (от них). Мы инициализируем новую переменную 𝐡_𝓋 для каждого узла исходной информацией, которая у нас есть о нем, и обновляем ее с каждой последующей итерацией. Внутри каждого слоя мы перебираем каждый узел 𝓋 и обрабатываем собранную информацию. Я считаю, что именно здесь как нельзя лучше подходит высказывание Джима Рона. Строка 4 собирает и агрегирует (усредняет) информацию от своих соседей 𝒩_𝓋 (людей, с которыми вы проводите больше всего времени или, в данном случае, друзей) на основе заданной стратегии. Строка 5 объединяет (объединение векторов) агрегированную информацию 𝐡_𝒩(𝓋) с собственной априорной информацией узла 𝐡_𝓋 с использованием матричных преобразований (умножение на 𝐖^𝑘), чтобы получить обновленную информацию вектора того же размера, который кодирует всю информацию. Строка 7 нормализует представления в единичном масштабе и передает их на следующий раунд. Наконец, представления из последнего раунда возвращаются и могут использоваться для других последующих задач, как описано выше.

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

Ссылки:

[1] Гамильтон, Уилл, Житао Ин и Юре Лесковец. «Индуктивное репрезентативное обучение на больших графах». Достижения в области нейронных систем обработки информации 30 (2017 г.).