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

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

Используя приведенную выше сеть голосования в канадском парламенте в качестве примера, каждый узел представляет члена парламента (MP) в канадском парламенте, а каждое ребро означает, что два депутата оба проголосовали за по законопроекту в этом году. Как показано, моментальный снимок динамического графа значительно меняется с 2012 по 2014 год, и, естественно, узлы и ребра могут добавляться или удаляться с течением времени. Кроме того, цвет каждого узла отражает, к какой партии принадлежит депутат, и партийная принадлежность данного узла также может меняться со временем. Для тех, кто заинтересован, приведенный выше набор данных является общедоступным, а также включен в наш предлагаемый тест.

📚 Прогнозирование динамических ссылок

Фундаментальной задачей динамического графа является прогнозирование будущих взаимодействий между узлами, называемое прогнозированием динамических связей. В частности, цель состоит в том, чтобы ответить на этот вопрос: в момент времени t в будущем, какова вероятность p наблюдения ребра между узлом i > и узел j? Понимание того, как формируются ссылки, важно в социальных сетях, прогнозировании трафика, политологии, системах рекомендаций и многом другом.

В последнее время предложено много методов динамического прогнозирования ссылок, и достигнут значительный прогресс. Некоторые примеры методов включают JODIE [1], TGN [2] и CAWN [3]. Основываясь на существующей настройке оценки, для большинства методов наблюдается близкая к идеальной производительность, что затрудняет их различие. Это заставляет нас внимательно изучить параметры оценки в прогнозировании динамических ссылок и переосмыслить, как разработать более строгие и надежные процедуры оценки.

💪 На пути к лучшей оценке

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

  • 1️⃣ Ограниченное разнообразие доменов. Существующие наборы контрольных данных в основном представляют собой социальные или взаимодействующие сети, поэтому разнообразие доменов ограничено. Мы представляем 6 новых наборов динамических сетевых данных из политики, экономики и транспорта и близости домен. Мы также представляем новые методы визуализации, чтобы лучше понять различия между динамическими сетями. Эти визуализации показывают, что значительная часть ребер повторяется с течением времении характер повторения сильно различается в разных доменах.
  • 2️⃣ Легкие отрицательные края для оценки: в стандартных настройках оценки отрицательные края (края, которые должны быть предсказаны как несуществующие) выбираются равномерно случайным образом. Учтите редкость ребер в реальных сетях: среди всех |N²| наблюдается лишь небольшое количество ребер. возможные пары узлов. Следовательно, края, которые ранее никогда не наблюдались, можно рассматривать как легкие негативы. В этой работе мы разрабатываем новые стратегии отрицательной выборки (NS), включающие более жесткие отрицательные границы, в том числе исторические и индуктивные стратегии NS.
  • 3️⃣ Хорошо работает запоминание: мы предлагаем простую базовую линию запоминания, которая сохраняет ранее наблюдаемые ребра, а затем предсказывает существование ребер на основе сохраненной памяти. Мы назовем эту простую схему EdgeBank и покажем, что, хотя она не требует ни обучения, ни настройки гиперпараметров, она может обеспечить высокую производительность и является необходимой базой для будущих методов для сравнения.

⏳ Понимание наборов данных динамических графиков

Формально мы рассматриваем динамический граф (непрерывного времени) как краевой поток с отметкой времени, включающий триплеты источника, получателяиотметки времени.

𝒢 = {(s₁, d₁, t₁), (s₂, d₂, t₂), … } и (0 ≤ t₁ ≤ t₂ ≤ … ≤ tₛₚₗᵢₜ ≤ ≤ T)

В целях оценки мы разделили временную шкалу в точке tₛₚₗᵢₜ на все ребра, появляющиеся до или после этой точки. Таким образом, у нас есть ребра обучающего и тестового наборов (Eₜᵣₐᵢₙ и Eₜₑₛₜ). В связи с этим ребра динамического графа можно разделить на следующие категории:

  1. Eₜᵣₐᵢₙ \ Eₜₑₛₜ : Края, которые видны только во время тренировки.
  2. Eₜᵣₐᵢₙ ∩ Eₜₑₛₜ : ребра, которые видны во время обучения и вновь появляются на этапе тестирования (можно считать трансдуктивными ребрами).
  3. Eₜₑₛₜ \ Eₜᵣₐᵢₙ :Ребра, которые видны только на этапе тестирования (можно считать индуктивными ребрами).

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

👉 График появления временного края (TEA)

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

Чтобы количественно измерить количество новых ребер в наборе данных, мы предлагаем следующий индекс новизна:

новинка= (1/ T) ∑ₜ (|Eₜ \ Eᵗₛₑₑₙ|) / |Eₜ |,

где Eₜ = {(s, d, tₑ) | tₑ = t} и Eᵗₛₑₑₙ = {(s, d, tₑ) | тₑ ‹ т}. Мы видим, что индекс новизны значительно варьируется в зависимости от наборов данных и доменов (дополнительные графики TEA см. в нашей статье). Следовательно, графики TEA подразумевают важность относительного распределения повторяющихся и новых ребер при разработке методов обучения временных графов.

👉 График временного пограничного трафика (TET)

График TET визуализирует повторяемость ребер в различных динамических сетях с течением времени. Ребра сортируются в зависимости от того, когда они впервые появились. Чтобы количественно оценить закономерности на графиках TET, мы определяем следующие показатели:

повторение = |Eₜᵣₐᵢₙ ∩ Eₜₑₛₜ| / |Eₜᵣₐᵢₙ|, сюрприз= |Eₜₑₛₜ \ Eₜᵣₐᵢₙ| / |Eₜₑₛₜ|

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

🏦 EdgeBank: основа для запоминания

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

EdgeBank состоит из компонента памяти (легко реализованного в виде хэш-таблицы), в котором хранятся ребра, наблюдаемые в прошлом. Во время вывода EdgeBank проверяет, находится ли пара узлов запроса (s, d) в памяти, и возвращает True, если да, и False в противном случае. Мы наблюдаем, что, хотя EdgeBank не имеет обучаемого параметра или вообще не обучается, он достигает удивительно высокой производительности в стандартных настройках оценки.

🔍 Пересмотр отрицательной выборки

Руководствуясь моделями граничного трафика в динамических графах, мы предлагаем новые, более сложные отрицательные кромки для оценки, что приводит к трем категориям отрицательных кромок, как показано ниже:

  • 1️⃣Случайная Отрицательная выборка: стандартная процедура выборки в современной литературе, случайная выборка пары узлов (s, d).
  • 2️⃣История Отрицательная выборка: выборка из набора ребер, которые наблюдались во время предыдущих временных меток, но отсутствуют на текущем шаге. Цель состоит в том, чтобы оценить, способен ли данный метод предсказать, в какие временные метки повторится ребро. Следовательно, в момент времени t мы делаем выборку из ребер e ∈ (Eₜᵣₐᵢₙ ∩ Eₜ).
  • 3️⃣Индуктивная Отрицательная выборка: основное внимание здесь уделяется оценке того, может ли данный метод моделировать шаблон повторения ребер, видимых только во время тестирования. Следовательно, в момент времени t мы выбираем из ребер
    e ∈ Eₜₑₛₜ и e ∉ (Eₜᵣₐᵢₙ ∪ Eₜ)

На приведенном выше рисунке показана производительность каждого метода для случайной выборки (стандартная, слева), предлагаемой нами исторической выборки (в центре) и индуктивной выборки. (справа) оценка. Наш простой базовый показатель Edgebank обеспечивает высокую производительность в стандартных настройках. Также обратите внимание, что как в историческом, так и в индуктивном параметрах все методы имеют снижение производительности, что подчеркивает важность отрицательной выборки во время оценки. Кроме того, меняется и порядок методов.

📎 OpenReview: https://openreview.net/forum?id=1GVpwr2Tfdg

📎 ArXiv: https://arxiv.org/abs/2207.10128

🔗 репозиторий github: https://github.com/fpour/dgb

🔗 ссылка на набор данных: https://zenodo.org/record/7008204

Хотите узнать больше?

Узнайте больше на семинаре Temporal Graph Learning Workshop на NeurIPS 2022

Я также являюсь соорганизатором семинара Temporal Graph Learning Workshop на NeurIPS 2022. У нас большой список спикеров, и мы рады видеть вас лично (или виртуально).

  1. ссылка на сайт: https://sites.google.com/view/tglworkshop2022/home
  2. мастерская твиттер: https://twitter.com/tgl_workshop

Ссылки:
[1] Э. Росси, Б. Чемберлен, Ф. Фраска, Д. Эйнар, Ф. Монти и М. Бронштейн. Сети временных графов для глубокого обучения на динамических графах. Препринт arXiv arXiv:2006.10637, 2020.
[2] С. Кумар, X. Чжан и Дж. Лесковец. Прогнозирование траектории динамического встраивания в сетях временного взаимодействия. В материалах 25-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных, 2019 г.
[3] Y. Wang, Y. Chang, Y. , Лю, Дж. Лесковец и П. Ли. Индуктивное репрезентативное обучение во временных сетях с помощью каузальных анонимных блужданий. Международная конференция по образовательным представительствам (ICLR), 2021 г.