История до сих пор
Сети реального мира, такие как социальные сети, сети трафика и цитирования, часто развиваются с течением времени, и область обучения временных графов (TGL) направлена на извлечение, изучение и прогнозирование этих развивающихся сетей. В последнее время TGL привлекает все большее внимание сообщества машинного обучения благодаря резкому увеличению количества статей и первому семинару в этой области, проведенному в прошлом году на NeurIPS 2022!
Это сообщение было создано в соавторстве с Эмануэле Росси, Майкл Галкин и Келлин Пелрин. Спасибо Farimah Poursafaei за полезный отзыв.
В этом сообщении блога мы представляем основные достижения TGL до 2022 года и обсуждаем перспективные направления в будущем. Обратите внимание, что мы используем термины «динамический график» и «временной график» как синонимы. Если вы хотите изучить или начать проект в TGL, эта статья будет хорошим справочным материалом и отправной точкой.
Пожалуйста, поделитесь с нами в разделе комментариев любыми другими достижениями, которые вас интересуют.
Оглавление:
- Введение в изучение временного графа
- Выразительность сетей временных графов
- Переосмысление оценки во временных графах
- График временных знаний
- Библиотеки и наборы данных
- Моделирование заболеваний с помощью временных графиков
- Обнаружение аномалий во временных графиках
- Обнаружение дезинформации на временных графиках
- Присоединение к сообществу изучения временных графов
Введение в изучение временного графа
В этом разделе мы приводим краткий обзор некоторых хорошо известных в литературе методов TGL. Существует два основных широких класса методов обучения динамическим графам с непрерывным временем (CTDG): сети временных графов и методы агрегирования обхода. Для получения более подробной информации о формулировке CTDG см. этот обзор Kazemi et al.
Сети временных графов (TGN) обобщают нейронные сети передачи сообщений (MPNN) на временные графы. Они делают это, вводя память узла, которая представляет состояние узла в данный момент времени, действуя как сжатое представление прошлых взаимодействий узла. Каждый раз, когда два узла участвуют во взаимодействии, они отправляют друг другу сообщения, которые затем используются для обновления их памяти. При вычислении встраивания узла выполняется дополнительная агрегация графа по временным соседям узла с использованием как исходных признаков узла, так и памяти в этот момент времени. Ниже мы приводим схему расчета ТГН.
TGN — это общая структура, которая обобщает предыдущие модели, такие как объединенные динамические вложения пользовательских элементов (JODIE) и внимание временного графика (TGAT), в качестве конкретных случаев. Более подробное введение в TGN можно найти в приведенном ниже сообщении в блоге одного из авторов.
Агрегирующие методы обхода, такие как причинно-следственные анонимные обходы (CAW), вместо этого полагаются на (временные) случайные обходы. В частности, чтобы предсказать существование связи (u, v) в момент времени t, CAW сначала извлекает несколько случайных блужданий, начиная с u и v таким образом, что временные метки ребер в обходе могут только монотонно уменьшаться. Обходы сначала анонимизируются путем замены каждого идентификатора узла вектором счета, указывающим, сколько раз этот узел появляется в каждой из возможных позиций в обходах. Затем каждая прогулка кодируется с использованием RNN, а затем кодировки объединяются с использованием самоконтроля или простого среднего значения.
Выразительность сетей временных графов
Существует большое количество работ по изучению выразительной силы GNN, работающих на статических графах. Сюй и др. 2019 впервые охарактеризовали дискриминационную способность графовых нейронных сетей (GNN), связав их с тестом изоморфизма графов Weisfeiler-Lehman (WL) и показав, что многие GNN не более эффективны, чем тест 1-WL. Последующие более выразительные модели, такие как подграфовые GNN, графовые преобразователи и GNN более высокого порядка, разработаны так, чтобы быть более выразительными, чем тест 1-WL (ниже есть ссылка на отличный пост в блоге Майкла Бронштейна о том, как перейти вне теста WL).
До этого года было мало работы по пониманию выразительной силы методов TGL. Первая попытка восполнить этот пробел была предпринята Ribeiro et al. где ключевая идея состоит в том, чтобы разделить существующие методы TGL на фреймворки время-и-график и время-график.
1️). В time-and-graph GNN используются для создания вложений узлов на графе моментальных снимков в каждый момент времени, таким образом формируя последовательность вложений узлов.
2️). В время-затем-граф каждое ребро в TG преобразуется во временной ряд, который указывает, в какое время существовало ребро, поэтому временные ребра объединяются в функции ребер на статическом графике.
Было показано, что представление время-и-график может быть построено из любого заданного представления время-и-график, тем самым доказывая время-и-графикпо крайней мере так же выразительно, как time-and-graph. Благодаря статическому представлению в время-затем-график мы можем напрямую использовать структуру выразительности WL-теста из статического графа для методов TGL. Таким образом, время-затем-график является более выразительным, чем время-и-график, если в качестве базовой модели используется 1-WL GNN.
Соуза и др. также стремится установить основу выразительности 1-WL для методов TGL. Примечательно, что они рассматривают CTDG как последовательность мультиграфиков с отметками времени, где мультиграф G(t)в данный момент времени t получается путем последовательного применения всех события до t. Мультиграф здесь означает, что между двумя узлами в графе может быть несколько ребер, а атрибут ребра представляет собой информацию о временной метке.
Теперь тест Temporal WL можно определить, применив тест WL к мультиграфам, построенным из CTDG. Следовательно, более выразительные методы TGN должны быть инъективными в его временном соседстве (т. е. хэшировать два разных узла из нескольких наборов в разные цвета), называемые инъективными MP-TGN. Соуза и др. также проанализировали TGN на основе ходьбы, такие как CAW, и показали, что MP-TGN и CAW не более выразительны, чем друг друга (как показано выше). Предлагаемый ими метод PINT сочетает в себе преимущества обеих категорий методов, что делает его наиболее выразительным. В приведенном ниже примере показаны два временных графика, которые MP-TGN не могут различить. Цвета — это метки узлов, а ребра имеют метки времени, начинающиеся с t₁.
Переосмысление оценки во временных графах
В значительной степени процедура оценки в TGL относительно мало изучена и находится под сильным влиянием обучения на статическом графе. Например, оценка задачи прогнозирования ссылок на динамических графах (или динамического прогнозирования ссылок) часто включает: 1). фиксированный поезд, тестовый поезд, 2). случайная выборка отрицательных краев и 3).небольшие наборы данных из похожих доменов. Такие протоколы оценки часто приводят к таблицам результатов, в которых заявленные показатели уже составляют около 95+%, и очень трудно отличить, приносят ли новые модели какую-либо пользу или просто снова перефразируют существующие методы.
Вы и др. обсудили ограничения текущих методов TGL при проектировании моделей, настройках оценки и стратегиях обучения для динамических графов с дискретным временем (DTDG). Они утверждают, что развивающийся характер данных и моделей не учитывается. При стандартной оценке все временные точки в хронологическом порядке делятся на обучающую выборку, оценочную выборку и тестовую выборку. Разделение фиксируется для данного набора данных.
Они указали, что такое фиксированное разделение означает, что будут оцениваться только ребра из выбранного периода тестирования, поэтому долгосрочное поведение, потенциально охватывающее период обучения, проверки и тестирования, не будет правильно оценено. Кроме того, многие методы TGL устарели во время тестирования, а это означает, что представление модели не обновляется информацией во время оценки. Рассмотрим пример графа транзакций. Если доступна информация о предыдущем дне, пользователь, вероятно, захочет обновить модель с помощью такой информации для достижения наилучшей производительности. Поэтому предлагается оценка в режиме реального времени, при которой модели настраиваются с учетом новых наблюдаемых данных, с использованием исторической информации и прогнозированием будущих связей.
Недавняя работа двух авторов исследует, какие отрицательные края следует использовать для оценки методов CTDG, и представляет больше наборов данных из разных областей. При оценке предсказания динамической ссылки отрицательные ребра часто выбираются случайным образом из любой пары узлов. Однако многие ребра во временном графе повторяются со временем (как видно на рисунке выше). Учитывая разреженность графов реального мира, большинство пар узлов вряд ли образуют ребро. Таким образом, случайные отрицательные края можно рассматривать как простые отрицательные края.
Итак, что можно считать жесткимиотрицательными краями? Во-первых, мы вводим исторические отрицательные ребра, которые появились в обучающем наборе, но отсутствуют на текущем шаге тестирования. Мы также определяем индуктивные отрицательные ребра как тестовые ребра, которые встречались ранее в тестовом наборе, но отсутствуют на текущем шаге. Наконец, мы предлагаем базовый EdgeBank, полагающийся исключительно на запоминание прошлых ребер (по сути, хеш-таблицу увиденных ребер). На приведенном выше графике мы видим, что при изменении отрицательных границ для оценки средняя производительность существующих методов TGL значительно снижается в исторических и индуктивныхнастройках по сравнению с стандартная настройка. EdgeBank также является удивительно надежной базой для стандартных настроек. Подробнее см. в блоге одного из авторов ниже.
Графики временных знаний
В области графов знаний (KG) временная настройка немного отличается от однородного мира, т. е. моментальные снимки графа с отметкой времени не так распространены. Вместо этого некоторые (или все) триплеты имеют сопровождающую (время начала, время окончания) пару атрибутов, обозначающую временные рамки, когда данный факт был истинным. Таким образом, тройки становятся пятерками или, в Викиданных, атрибуты времени становятся квалификаторами более общего утверждения(основная тройка + множественный ключ квалификаторы -value), а операторы образуют так называемые гиперреляционные KG.
Например, (Президент Французской республики, занимающий должность, Николя Саркози, 2007, 2012) — это пятерка, описывающая период времени, когда Николя Саркози был президентом Французской республики. В качестве альтернативы может быть только одна метка времени на тройку (формируя четверки). Наиболее распространенной задачей прогнозирования является оценка предсказания орел/решка с учетом атрибутов времени, например. , `(Президент Французской Республики, должностное лицо, ???, 2007, 2012)` — это можно рассматривать как частный случай предсказания гиперреляционной ссылки, где квалификаторы являются только литералами dateTime . Классическим примером временной модели заканчивания KG является TNTComplex (ICLR 2020).
Краузе и др. предпринял первую попытку преодолеть разрыв между темпоральными KG и однородными графами. В этой работе авторы предлагают основу для формализации различных временных аспектов в KG. А именно, они определяют временные KG как локальные расширения, т. е. графы с отметками времени на ребрах, и динамические KG как глобальные расширения, т. е. графы, которые меняют топологию во времени посредством добавление или удаление узлов и ребер. Более того, возможны комбинации этих основных типов, например, временной и динамический KG будут называться инкрементными. Мы надеемся, что эта работа внесет немного больше порядка и ясности в лихорадочную литературу о темпоральных KG, и сообщество будет придерживаться хорошей таксономии. Следующий шаг: доработка надлежащего протокола оценки для этих типов графиков.
Ванг и др. решена задача предсказания нескольких связей по временным + динамическим графам, где ребра имеют временные метки, и новые узлы могут появиться на более поздних временных шагах (инкрементные графики в соответствии с приведенной выше классификацией Krause et al.). Сценарий с несколькими выстрелами делает задачу еще более сложной — у нас есть доступ только к ограниченному количеству точек обучения и выводов (обычно ‹5), чтобы рассуждать о ссылке запросов. Здесь авторы предлагают MetaTKGR, основанный на метаобучении подход, который строит представления новых узлов путем агрегирования характеристик существующих узлов в пределах определенного дельта t временного соседства. Скалярная разница между метками времени векторизуется с помощью преобразования Фурье.
Библиотеки и наборы данных
Отсутствие больших наборов данных и сложных задач сдерживало исследования в области обучения временным графам в последние несколько лет. К счастью, появляются новые наборы данных из разных областей. Например, Poursafaei et al. представил шесть новых общедоступных наборов данных TG из областей транспорта, политики, экономики и близости. Тем не менее, в этой области по-прежнему отсутствуют последовательные усилия по стандартизации эталонных тестов и оценки высокого качества, что OGB сделал для статических графиков. Мы надеемся, что в 2023 году мы сможем увидеть более стандартизированные тесты TG с упором на реальные приложения.
Что касается библиотек, хорошо известна Pytorch Geometric Temporal, расширение Pytorch Geometric для темпоральных графов. Однако Pytorch-Geometric Temporal, похоже, использует только методы и наборы данных с дискретным временем. Библиотека, которая также включает в себя методы с непрерывным временем, была бы большой добавленной стоимостью для сообщества. Недавно Чжоу и др. представила TGL, унифицированную платформу для крупномасштабного автономного обучения нейронной сети Temporal Graph. В частности, на машине с 4 GPU TGL может обучить одну эпоху из более чем одного миллиарда временных ребер в течение 1–10 часов.
Ниже мы приводим ссылки на различные библиотеки и наборы данных TGL.
- 13 обработанных наборов данных TG, доступных через pip install dgb
- Питорч Геометрический Темпорал
- Библиотека ТГЛ
- Динамическая сеть транзакций на блокчейне Chartalist
- Базовый тест прогнозирования графа временных знаний
Моделирование заболеваний с помощью временных графиков
Во время недавней пандемии COVID-19 моделирование эпидемии играет важную роль для понимания распространения болезни, а также для разработки соответствующих стратегий вмешательства. Сети человеческих контактов на самом деле представляют собой временные графы. Комбинируя графы контактов с классическими моделями на основе компартментов, такими как SEIR и SIR, мы можем более точно прогнозировать кривую заражения COVID-19 и выйти за рамки предположения об однородном смешивании (все люди с равной вероятностью будут контактировать друг с другом). .
Чанг и др. создал сеть временной мобильности на основе данных сотовых телефонов и нанес на карту почасовое перемещение 98 миллионов человек из групп переписи населения (CBG) в определенные точки интереса (POI) в США. Комбинируя почасовую контактную сеть с моделями SEIR на уровне CBG, они могут точно соответствовать реальной траектории заражения. В частности, модель показывает, что на некоторые POI суперраспространителей, такие как рестораны и фитнес-центры, приходится подавляющее большинство инфекций. Кроме того, различия в мобильности между расовыми и социально-экономическими группами приводят к разным показателям заражения среди этих групп. Эта работа продемонстрировала реальный мировой потенциал использования крупномасштабных временных графиков для прогнозирования заболеваний и информирования политик о стратегиях вмешательства.
Помимо сетей контактов между людьми, динамические транспортные сети также играют важную роль в распространении COVID-19. В недавней работе одного из авторов мы включили сети ежедневных рейсов в модель SEIR для оценки завезенных случаев COVID-19. Благодаря объединению сетей полетов становится возможным раннее выявление вспышек и прогнозирование последствий ограничений на поездки. Смотрите сообщение в блоге одного из авторов для более подробной информации.
Несмотря на эмпирический успех моделей болезней на основе временных графов, также важно ответить на такие вопросы, как как структура контактной сети влияет на распространение болезни? и что такое лучший способ изменить схему контактов, чтобы можно было замедлить или предотвратить распространение COVID-19? Holme et al. сравнили разницу в характеристиках вспышек между использованием временных, статических и полностью подключенных сетей на восьми наборах сетевых данных и изучили различные сетевые структуры, влияющие на распространение болезни. Они показали, что преобразование временных сетей в статические может привести к серьезной недооценке или переоценке как размера вспышки, так и времени исчезновения болезни.
Каковы следующие шаги TGL по моделированию эпидемий?
1️). Во-первых, прогнозирование всей контактной сети или моментального снимка сети мобильности на ближайшее будущее является важнейшей задачей. С предсказанной структурой мы можем применить сетевые модели SEIR для оценки кривой заражения.
2️). Во-вторых, определение и понимание влияния паттернов взаимодействия на сеть контактов имеет решающее значение для разработки политики и ее интерпретируемости. Анализ взаимодействия между структурами графа и кривой заражения может помочь нам определить наиболее эффективные стратегии вмешательства.
Обнаружение аномалий на временных графиках
Обнаружение аномалий является фундаментальной задачей при анализе временных графиков, которая идентифицирует объекты, которые значительно отличаются от остальных. Например, обнаружение мошенничества можно смоделировать как обнаружение аномальных границ в сети транзакций, а идентификацию дорожно-транспортных происшествий можно рассматривать как обнаружение аномальных событий в сети трафика.
Растет интерес к использованию возможностей представления сетей временных графов для обнаружения аномалий. Кай и др. разработал сквозную модель структурно-временной графовой нейронной сети для обнаружения аномальных границ, названную StrGNN. Окружающий подграф, подграф k-hop с центром вокруг ребра, сначала извлекается на основе интересующего ребра, чтобы уменьшить вычислительную сложность. Затем используется сверточная нейронная сеть графа (GCN) для создания структурного встраивания из подграфа. Затем для сбора временной информации используются закрытые рекуррентные единицы (GRU). Одной из проблем обнаружения аномалий является отсутствие помеченных примеров. Таким образом, Cai et al. предложил генерировать контекстно-зависимые отрицательные края, заменив один из узлов в нормальном крае и обучив модель этим отрицательным краям.
По сравнению с неконтролируемыми методами обнаружения аномалий, не основанными на GNN, такими как SEDANSPOT и AnomRank, методы на основе GNN могут легко включать любой заданный атрибут и потенциально могут добиться более высокой производительности. Однако есть две серьезные проблемы для подходов, основанных на GNN.
1). Во-первых, как масштабировать динамические графы с миллионами ребер и узлов? Это открытый вопрос как для модуля GNN при извлечении признаков графа, так и для временного модуля, такого как GRU и преобразователи, при обработке долговременной информации.
2️). Во-вторых, как дать точное объяснение обнаруженным аномалиям? В реальных приложениях обнаруженные аномалии часто проверяются, а затем потенциально могут привести к карательным мерам для этих обнаруженных объектов. Объяснимость GNN на динамических графах остается открытой проблемой.
Задача обнаружения точки изменения направлена на обнаружение моментов времени на динамическом графике, когда структура или распределение графика значительно отклоняются от того, что наблюдалось ранее. Это изменение может быть связано с внешними событиями (такими как нарушение движения и ограничения на полеты, связанные с COVID-19) или просто естественным развитием динамического графика. Недавняя работа одного из авторов использовала собственные значения матрицы Лапласа каждого снимка графа для встраивания структуры графа, применяя скользящие окна для сравнения изменений в структуре графа в долгосрочной и краткосрочной перспективе. В приведенном выше предложенном методе обнаружения аномалий Лапласа (LAD) обнаруживается изменение в сети голосования канадских членов парламента (MP) из-за увеличения перевеса между политическими партиями. Это совпадает с избранием Джастина Трюдо лидером Либеральной партии в 2013 году.
Обнаружение дезинформации на временных графиках
Дезинформация распространяется по разным схемам и с разной скоростью по сравнению с достоверной информацией (Vosoughi et al.). Было проведено значительное исследование, изучающее эти сетевые паттерны в статическом графе, в то время как методы, основанные на динамическом графе, недостаточно изучены (Song et al.). Однако в прошлом году для обнаружения и понимания дезинформации использовалось все больше методов TGL. Например, Чжан и др. разработал метод, основанный на процессах временных точек, в то время как динамический GCN (DynGCN) и DGNF являются методами, основанными на динамическом GNN.
На иллюстрации ниже показана архитектура DynGCN. Они строят снимки графа с равномерным интервалом во времени, пропускают каждый через слои GCN, а затем комбинируют представления и изучают закономерности эволюции снимков, используя внимание. Это относительно более простой подход к использованию временной информации по сравнению с некоторыми рассмотренными выше методами, такими как TGN или CAW, но, тем не менее, он обеспечивает более высокую производительность, чем предыдущий уровень техники для обнаружения дезинформации в наборах данных, которые исследовали авторы.
Показано, что динамические паттерны взаимодействия достаточно информативны для выявления дезинформации (Plepi et al.). Благодаря значительным недавним достижениям в методах TGL, мы можем ожидать новых современных методов обнаружения дезинформации, которые включают динамические графы.
Присоединение к сообществу Temporal Graph Learning
В 2022 году сообщество ML привлекло к TGL повышенное внимание. На NeurIPS 2022 прошел первый в истории семинар TGL. Записи докладов и панели скоро будут доступны на виртуальном сайте NeurIPS. Принятые работы размещены на сайте семинара. Следите за объявлениями о новых итерациях семинара TGL и присоединяйтесь к семинару (актуальная ссылка на веб-сайте), чтобы взаимодействовать с сообществом. В этом году мы также планируем группу чтения TGL. Если вы хотите поделиться своей работой или принять участие в организации группы чтения, пожалуйста, напишите по адресу [email protected].
