Skip to content
Назад к результатам поиска

Встраивание сетей — Node2Vec, DeepWalk, LINE

Год
2014 (DeepWalk); 2016 (Node2Vec)
Тип
Representation learning / unsupervised network method

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Этот подход был формализован для данных социальных сетей Пероцци, Аль-Рафу и Скиеной с помощью DeepWalk (2014), который адаптировал модель skip-gram Word2Vec к случайным блужданиям по графам, и расширен Гровером и Лесковецем с помощью Node2Vec (2016), который ввел смещенное случайное блуждание, балансирующее исследование вширь и вглубь. Эти встраивания превращают реляционные данные в векторы признаков, которые стандартные классификаторы машинного обучения и алгоритмы кластеризации могут использовать напрямую.

Интуиция метода

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

История

Идея применения Word2Vec к данным графовой структуры была предложена Пероцци, Аль-Рафу и Скиеной в DeepWalk (KDD 2014), которая показала, что случайные блуждания по социальному графу могут заменить вручную созданные признаки для классификации узлов. Гровер и Лесковец расширили это в Node2Vec (KDD 2016), введя второпорядковое смещенное случайное блуждание, параметризованное p и q, обеспечивающее явный контроль над компромиссом между исследованием соседства на основе гомофилии и на основе структурной эквивалентности. Примерно в то же время Тан и др. предложили LINE (WWW 2015), который изучает встраивания, оптимизируя объекты близости первого и второго порядка напрямую, а не через случайные блуждания, что делает его подходящим для очень больших графов. Вместе эти три метода заложили основу области обучения представлений графов и вдохновили последующие архитектуры графовых нейронных сетей.

Когда применять

Встраивание сетей подходит, когда у вас есть граф с как минимум 50 узлами, и вам нужны непрерывные векторные признаки для последующих задач, таких как классификация узлов, предсказание связей или кластеризация узлов. Метод подходит как для невзвешенных, так и для взвешенных графов и обрабатывает направленные или ненаправленные структуры. Выбирайте DeepWalk, когда достаточно простой, равномерной базовой линии случайных блужданий. Выбирайте Node2Vec, когда вы хотите настроить баланс между гомофилией и структурной эквивалентностью с помощью параметров p и q. Если вам нужно встроить новые, ранее невиданные узлы во время вывода без переобучения, предпочтите индуктивный метод, такой как GraphSAGE; встраивание сетей в стандартной форме является трансдуктивным. Метод не требует нормально распределенных атрибутов узлов.

Ограничения и замечания

  • Трансдуктивное: модель не может встраивать узлы, которые не присутствовали во время обучения, без полного переобучения.
  • Чувствительность к гиперпараметрам: размерность встраивания, длина блуждания, количество блужданий, размер окна, p и q — все это влияет на качество встраивания и требует настройки.
  • Случайные блуждания не захватывают структуру графа высшего порядка (например, гиперребра или многореляционные ребра) без расширения.
  • Производительность снижается на очень малых графах (менее 50 узлов), где корпус блужданий слишком разрежен для изучения надежной статистики.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Преобразует реляционные графовые данные в векторы фиксированной длины, совместимые с любым стандартным конвейером машинного обучения.
  • Параметры p и q Node2Vec позволяют аналитику настраивать баланс между встраиваниями, чувствительными к сообществам, и встраиваниями, чувствительными к ролям.
  • Веса ребер могут быть включены в вероятности обхода, захватывая силу отношений без дополнительных шагов моделирования.
  • Масштабируется до больших графов благодаря эффективной выборке случайных блужданий и процедуре обучения skip-gram.

Применение

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

Как это работает

Как это работает

1

Процесс начинается с графа G, в котором узлы — это сущности, а ребра представляют отношения. Ребра могут быть направленными или ненаправленными и могут нести веса, которые впоследствии будут влиять на вероятность обхода. Если веса ребер присутствуют, они включаются в вероятности обхода; если отсутствуют, все ребра получают равный вес. На этом этапе аналитик также выбирает вариант алгоритма — DeepWalk для равномерных случайных блужданий, Node2Vec для смещенных блужданий, управляемых параметрами p (возврат) и q (внутрь-наружу), или LINE, когда необходимо отдельно изучать близость первого и второго порядка. Выбор между режимами параметров Node2Vec руководствуется ожидаемым свойством сети: гомофилией (сходные узлы соединяются, поэтому предпочтительно исследование вширь, q < 1) или структурной эквивалентностью (узлы с одинаковыми ролями могут быть далеко друг от друга, поэтому предпочтительно исследование вглубь, p < 1).

2

Начиная с каждого узла, алгоритм моделирует серию случайных блужданий фиксированной длины (обычно 30 шагов) и повторяет их много раз (обычно 200 блужданий на узел). Каждое блуждание порождает последовательность идентификаторов узлов, аналогичную предложению из слов. В DeepWalk следующий узел выбирается равномерно из соседей. В Node2Vec следующий узел выбирается в соответствии с переходными вероятностями, смещенными параметрами p и q: возвращение к предыдущему узлу штрафуется множителем 1/p, сохранение на том же расстоянии остается равным 1, а движение дальше контролируется множителем 1/q. Совокупность всех блужданий формирует корпус последовательностей узлов, который кодирует топологию графа.

3

Корпус последовательностей узлов подается в модель skip-gram (та же архитектура, что и у Word2Vec). Для каждого узла в блуждании модель предсказывает окружающие контекстные узлы в пределах окна (обычно 10 шагов). С помощью стохастического градиентного спуска модель изучает плотное векторное представление фиксированной размерности — обычно 64 или 128 — для каждого узла таким образом, чтобы узлы, совместно встречающиеся в блужданиях, имели схожие векторы. Размерность является гиперпараметром: большая размерность захватывает больше структуры, но увеличивает вычислительные затраты и риск переобучения на малых графах.

4

После обучения модель предоставляет один вектор встраивания на узел. Эти векторы используются как признаки для классификации узлов (подаются в логистическую регрессию или нейронный классификатор), предсказания связей (сравнение векторов пар кандидатов узлов) или обнаружения сообществ (кластеризация векторов). Встраивания являются трансдуктивными: они фиксированы для узлов, увиденных во время обучения. Если новые узлы должны быть встроены после обучения, следует использовать индуктивный метод, такой как GraphSAGE, поскольку стандартная модель Node2Vec или DeepWalk не может обобщаться на невиданные узлы без переобучения.

Частые ошибки

  • Применение модели Node2Vec к новым узлам, которых не было в обучающем графе — у модели не будет для них вектора; используйте индуктивный метод (например, GraphSAGE), когда трансдуктивное встраивание неприемлемо.
  • Использование значений p=1, q=1 по умолчанию (эквивалентно DeepWalk) без проверки, следует ли сеть закономерности гомофилии или структурной эквивалентности — настройка p и q в соответствии с ожидаемой закономерностью может существенно улучшить производительность последующих задач.
  • Рассмотрение размерности встраивания как фиксированной константы: на малых графах размерность 64 или 128 может привести к переобучению; начните с меньшего значения и проверяйте на последующей задаче.
  • Игнорирование минимального требования к выборке: графы с менее чем 50 узлами порождают корпуса блужданий, слишком тонкие для обучения надежных встраиваний.

Часто задаваемые вопросы

Какова разница между DeepWalk, Node2Vec и LINE?

DeepWalk использует равномерные случайные блуждания и модель Word2Vec skip-gram — это самая простая базовая линия. Node2Vec добавляет смещенные случайные блуждания, управляемые параметрами p и q, позволяя аналитику настраивать, исследует ли блуждание в режиме поиска вширь (гомофилия) или в режиме поиска вглубь (структурная эквивалентность). LINE вообще не использует случайные блуждания; он оптимизирует объекты близости первого и второго порядка напрямую по списку ребер, что более масштабируемо для очень больших графов, но жертвует сигналом соседства на основе блужданий.

Как выбрать параметры p и q в Node2Vec?

p контролирует вероятность возвращения к предыдущему узлу (низкий p = меньше возвратов), а q контролирует радиус исследования (q < 1 способствует исследованию наружу, q > 1 удерживает блуждание близко к источнику). Если вы ожидаете, что узлы в одном сообществе будут похожи (гомофилия), установите q < 1, чтобы позволить блужданию распространяться наружу. Если вы ожидаете, что узлы с одинаковой структурной ролью будут похожи, даже если они находятся далеко друг от друга, установите p < 1, чтобы стимулировать исследование вглубь. Проверьте оба режима на последующей задаче.

Могу ли я встроить новые узлы после обучения без переобучения всей модели?

Стандартные Node2Vec и DeepWalk являются трансдуктивными: матрица встраивания охватывает только узлы, увиденные во время обучения. Для индуктивного обобщения на новые, ранее невиданные узлы используйте индуктивный метод графовых нейронных сетей, такой как GraphSAGE, который изучает функцию агрегации по соседствам узлов, которую можно применить к любому узлу во время вывода.

Сколько измерений следует использовать для встраивания?

Наиболее распространенные варианты — 64 и 128, и они хорошо работают для графов среднего и большого размера. Для малых графов (50–200 узлов) начните с меньшей размерности (16 или 32), чтобы избежать переобучения, и оценивайте качество встраивания, измеряя производительность последующей задачи (например, точность классификации узлов), а не только ошибку реконструкции.

Похожие методы

Источники

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    Открыть ссылку DOI
    Скопировано.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    Открыть ссылку DOI
    Скопировано.