Как использовать графическую информацию в ваших моделях машинного обучения

Введение

Многие наборы данных из реального мира естественным образом могут быть оформлены в виде графиков. Например, на онлайн-платформах, таких как социальные сети, пользователи могут быть представлены в виде узлов, а подписчики или лайки могут быть представлены в виде ребер.

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

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

Что такое графики?

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

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

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

На этом графике социальных сетей мы наблюдаем многие явления, известные нам в социальных сетях, например:

  • У некоторых пользователей, таких как знаменитости, было бы гораздо больше преимуществ, поскольку знаменитости имеют миллионы поклонников, но редко следуют за всеми в ответ.
  • У некоторых пользователей, таких как боты, было бы наоборот, и, вероятно, у них было бы гораздо больше исходящих преимуществ, чем входных, поскольку боты, как правило, следуют за случайными людьми, а реальные пользователи не будут следовать за ботом.
  • Пользователи обычно образуют кластеры плотно связанных групп, состоящих из пользователей, которые, как правило, знают друг друга. Группы друзей или люди из одной группы интересов, как правило, следуют за одними и теми же людьми.

Методы машинного обучения

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

График статистики

Самый простой способ использовать графическую информацию — рассчитать основные числа и отношения и использовать их в качестве числовых характеристик.

Некоторые графические статистические данные включают:

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

Эти графические статистические данные — отличное место для начала, и они имеют легко усваиваемые стандартизированные значения.

Однако они относительно ограничены в том, какую информацию они могут передавать:

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

Вложения узлов

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

Самый распространенный способ изучить эти вложения (из статей DeepWalk и Node2vec) — заставить узлы, расположенные близко друг к другу, иметь одинаковое представление. Они используют концепцию случайного блуждания, которая включает в себя начало в заданном узле и случайное пересечение ребер, чтобы создать пары узлов, которые находятся рядом друг с другом. Вложения обучаются путем максимизации косинусного сходства между узлами, которые одновременно встречаются в случайных блужданиях. Эта цель обучения использует допущение гомофилии, в котором говорится, что узлы, которые связаны друг с другом, имеют тенденцию быть похожими друг на друга.

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

Однако, несмотря на то, что это шаг в правильном направлении, у этих методов все же есть недостатки:

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

Граф сверточных сетей

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

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

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

GCN можно обучать как с учителем, так и без учителя. Для обучения с учителем мы просто тренируемся в соответствии с ярлыком, который у нас есть для нашей последующей задачи. Для неконтролируемого обучения существует несколько вариантов, но наиболее распространенный способ похож на метод Node2vec/DeepWalk, в котором мы обеспечиваем, чтобы близлежащие узлы имели аналогичные представления.

GCN преодолевают многие проблемы предыдущих методов, так как 1) их можно обучать от начала до конца, 2) они полностью используют функции узла и 3) они не полагаются на фиксированное сопоставление от узла к встраиванию.

Из-за этих сильных сторон этот стиль графовой нейронной сети использовался во многих реальных отраслевых системах, таких как рекомендательные системы (например, PinSage) и системы обнаружения мошенничества.

Заключение

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

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