Temporale графовый бенчмарк

Temporal графовый бенчмарк

Испытательные наборы данных для обучения временным графам

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

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

• Веб-сайт: https://tgb.complexdatalab.com/
• Статья: https://arxiv.org/abs/2307.01026
• Github: https://github.com/shenyangHuang/TGB

Этот пост основан на нашей статье Временный Графический Бенчмарк для машинного обучения на временных графах (NeurIPS 2023 Tracks Datasets and Benchmarks) и был соавторством с Эмануэле Росси. Найдите больше работ по временным графам на моем веб-сайте. Хотите узнать больше о временных графах? Присоединяйтесь к Группе Чтения Временных Графов и Мастер-классу по Обучению Временным Графам @ NeurIPS 2023, чтобы узнать больше о передовых методах исследований временных графов.

Содержание:

1. Мотивация
2. Постановка Задачи
3. Детали Набора Данных
4. Прогнозирование Свойства Динамической Связи
5. Прогнозирование Свойства Динамического Узла
6. Начало работы с TGB
7. Заключение и Перспективная Работа

Мотивация

В последние годы область машинного обучения статическим графам испытала значительный подъем, в основном благодаря появлению общедоступных наборов данных и установленных эталонов, таких как Open Graph Benchmark (OGB), Long Range Graph Benchmark и TDC Benchmark. Однако многие системы реального мира, такие как социальные сети, транспортные сети и финансовые сети транзакций, являются временными: они развиваются со временем. До недавнего времени развитие временных графов значительно затруднялось отсутствием больших, высококачественных наборов данных и всесторонних систем оценки. Этот дефицит, в сочетании с ограничениями оценки, привел к практически идеальным показателям AP или AUROC для моделей на популярных наборах данных, таких как Википедия и Реддит, что привело к чрезмерно оптимистичной оценке производительности модели и сложности различения конкурирующих моделей.

• 8 Альтернатив GitHub для проектов по наукам о данных
• Создание отношений Many-To-One между столбцами в синтетической таблице с использованием пользовательских функций PySpark
• К несубъективной оценке больших языковых моделей

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

Упрощенная оценка. Динамическое предсказание связи обычно формулируется как задача бинарной классификации: положительным (истинным) ребрам присваивается метка 1, тогда как отрицательным (не существующим) ребрам присваивается метка 0. При оценке одно отрицательное ребро на каждое положительное выбирается путем фиксации начального узла и случайного выбора конечного узла. При такой оценке учитывается только небольшое количество легко предсказуемых отрицательных ребер, что приводит к завышению производительности модели, при которой многие модели получают >95% AP на Википедии и Реддите (Poursafaei et al. 2022, Rossi et al. 2020, Wang et al. 2021, Souza et al. 2022). В ТГБ мы рассматриваем задачу предсказания связи как задачу ранжирования и делаем оценку более надежной. Мы показываем, что улучшенная оценка приводит к более реалистичной производительности и выявляет явные различия между различными моделями.

Постановка проблемы

В ТГБ мы сосредоточены на непрерывных временных графах, как определено в работе Kazemi et al. 2020. В этой постановке мы обозначаем временные графы как ряды ребер с отметками времени, состоящие из троек (начальный узел, конечный узел, временная метка). Обратите внимание, что временные ребра могут иметь вес, быть направленными, а узлы и ребра могут дополнительно иметь признаки.

Кроме того, мы рассматриваем потоковую постановку, в которой модель может включать новую информацию во время вывода. В частности, при предсказании тестового ребра в момент времени t, модель может обращаться [1] ко всем ребрам, произошедшим до времени t, включая тестовые ребра. Однако обратное распространение и обновление весов с использованием информации из теста не допускаются.

Детали набора данных

Набор данных ТГБ содержит девять наборов данных, семь из которых подобраны для данной работы, а два из предыдущих изданий. Наборы данных разделены по временным периодам на тренировочные, проверочные и тестовые наборы в соотношении 70/15/15. Наборы данных категоризированы на основе количества ребер: маленькие (<5 миллионов), VoAGI (5-25 миллионов) и большие (> 25 миллионов).

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

Наборы данных TGB также связаны с реальными задачами. Например, набор данных tgbl-flight представляет собой сеть международных авиаперевозок, собранную от 2019 по 2022 год, где аэропорты моделируются как вершины, а рейсы между аэропортами – как ребра для заданной даты. Задача заключается в прогнозировании, состоится ли полет между двумя конкретными аэропортами в будущем. Это полезно для прогнозирования потенциальных нарушений авиаперевозок, таких как отмены и задержки. Например, во время пандемии COVID-19 многие авиарейсы были отменены для борьбы с распространением COVID-19. Прогнозирование глобальной сети авиаперевозок также важно для изучения и прогнозирования распространения таких болезней, как COVID-19, в новые регионы, как показано в работе Ding и др., 2021. Подробное описание наборов данных и задач представлено в разделе 4 статьи.

Прогнозирование свойств динамической связи

Целью прогнозирования свойств динамической связи является предсказание свойства (часто существования) связи между парой вершин в будущий момент времени.

Отрицательная выборка ребер. В реальных приложениях истинные ребра заранее неизвестны. Поэтому запрашивается большое количество пар вершин, и только пары с наивысшими оценками рассматриваются как ребра. Мотивируясь этим, мы формулируем задачу прогнозирования связи как задачу ранжирования и выбираем несколько отрицательных ребер для каждого положительного ребра. В частности, для заданного положительного ребра (s,d,t) мы фиксируем исходную вершину s и метку времени t и выбираем q разных целевых вершин d. Для каждого набора данных q выбирается на основе компромисса между полнотой оценки и временем вывода в тестовом наборе данных. Из q отрицательных выборок половина выбирается равномерно случайным образом, а другая половина – исторические отрицательные ребра (ребра, которые были наблюдены в обучающем наборе данных, но отсутствуют в момент времени t).

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

Результаты на небольших наборах данных. На небольших наборах данных tgbl-wiki и tgbl-review мы наблюдаем, что лучшие модели имеют существенные отличия. Кроме того, лучшие модели на tgbl-wiki, такие как CAWN и NAT, существенно снижают свою производительность на tgbl-review. Одно из возможных объяснений заключается в том, что набор данных tgbl-review имеет намного более высокий индекс неожиданности по сравнению с набором данных tgbl-wiki. Высокий индекс неожиданности показывает, что высокий процент тестовых ребер никогда не наблюдался в обучающем наборе данных, и, следовательно, для tgbl-review требуется более индуктивное рассуждение. В tgbl-review лучшими моделями являются GraphMixer и TGAT. Из-за их меньшего размера мы можем выбрать все возможные отрицательные ребра для tgbl-wiki и сто отрицательных ребер для каждого положительного ребра для tgbl-review.

Большинство методов исчерпывает память GPU для этих наборов данных, поэтому мы сравниваем TGN, DyRep и Edgebank на этих наборах данных из-за их меньших требований к памяти GPU. Обратите внимание, что некоторые наборы данных, такие как tgbl-comment или tgbl-flight, охватывают несколько лет, что потенциально может привести к изменению распределения в течение длительного времени.

Выводы. Как видно выше на примере tgbl-wiki, количество отрицательных примеров, используемых для оценки, значительно влияет на производительность модели: мы видим значительное снижение производительности почти всех методов, когда количество отрицательных примеров увеличивается с 20 до всех возможных пунктов назначения. Это подтверждает, что для надежной оценки действительно требуется больше отрицательных примеров. Интересно отметить, что методы, такие как CAWN и Edgebank, имеют относительно незначительное снижение производительности, и это остается предметом будущей работы для изучения причин, почему некоторые методы менее подвержены влиянию.

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

Динамическое предсказание свойств узлов

Целью динамического предсказания свойств узлов является предсказание свойства узла на любом заданном моменте времени t. Поскольку отсутствуют большие общедоступные наборы данных TG с динамическими метками узлов, мы предлагаем задачу предсказания сродства узлов для исследования задач на уровне узлов во временных графиках. Если вы хотите внести свой вклад в новый набор данных с метками узлов, пожалуйста, свяжитесь с нами.

Предсказание сродства узлов. В этой задаче рассматривается сродство подмножества узлов (например, пользователей) к другим узлам (например, товарам) в качестве свойства и то, как это сродство естественным образом изменяется со временем. Эта задача актуальна, например, в системах рекомендаций, где важно предоставлять персонализированные рекомендации пользователю, моделируя его предпочтения к разным товарам во времени. Здесь мы используем Нормализованную накопительную пользу топ-10 товаров (NDCG@10), чтобы сравнивать относительный порядок предсказанных товаров с их настоящим порядком. Метка генерируется путем подсчета частоты взаимодействия пользователя с разными товарами в будущем периоде.

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

Начало работы с TGB

Как использовать TGB? На рисунке выше показан ML-пайплайн в TGB. Вы можете автоматически загружать наборы данных и обрабатывать их в форматы данных, совместимые с numpy, PyTorchи PyG. Пользователям нужно только разработать свои собственные модели TG, которые легко можно протестировать с помощью TGB-эвалуаторов для стандартизации оценки. Наконец, публичные и онлайн-таблицы лидеров TGB помогают исследователям отслеживать последние достижения в области временных графиков. Установить пакет можно легко:

pip install py-tgb

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

Заключение и дальнейшая работа

Для обеспечения реалистичной, воспроизводимой и надежной оценки машинного обучения на временных графах, мы представляем Temporal Graph Benchmark – коллекцию сложных и разнообразных наборов данных. Используя наборы данных и оценку TGB, мы обнаружили, что производительность модели существенно различается в разных наборах данных, что демонстрирует необходимость оценки на разнообразных временных графах. Кроме того, в задаче предсказания связности узлов, простые эвристики превосходят TG-методы, что мотивирует разработку более узловых TG-моделей в будущем.

Интеграция в PyG. Маттиас Фей (Kumo.AI), Главный разработчик PyG, объявил на Семинаре по графовому обучению в Стэнфорде 2023, что TGB будет интегрирован в будущих версиях PyG. Следите за обновлениями!

Библиотека TGX. В настоящее время мы разрабатываем утилиту и библиотеку визуализации на языке Python для работы с временными графами, названную TGX. TGX поддерживает 20 встроенных наборов данных временных графов из TGB и Poursafaei et al. 2022.

Обратная связь от сообщества и вклад в наборы данных. TGB – это проект, развиваемый сообществом, и мы хотели бы поблагодарить всех членов сообщества, которые предоставили нам свои предложения по электронной почте или через проблемы на GitHub. Если у вас есть предложения или вы хотите внести новые наборы данных в TGB, пожалуйста, свяжитесь с нами по электронной почте или создайте проблему на GitHub. Мы ищем масштабные наборы данных, особенно для задач динамической классификации узлов или графов.