Переосмысление предсказания сродства узлов во временных графах

Основная информация

• ID статьи: 2510.06940
• Название: Revisiting Node Affinity Prediction in Temporal Graphs
• Авторы: Krishna Sri Ipsit Mantri, Or Feldman, Moshe Eliasof, Chaim Baskin
• Категория: cs.LG (Машинное обучение)
• Статус публикации: Препринт. На рецензии
• Ссылка на статью: https://arxiv.org/abs/2510.06940
• Ссылка на код: https://github.com/orfeld415/NAVIS

Аннотация

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

Исследовательский контекст и мотивация

Определение задачи

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

Основные проблемы

1. Парадокс производительности: сложные временные графовые нейронные сети (TGNN) показывают худшие результаты на задаче предсказания сродства узлов, чем простые эвристические методы
2. Ограничения выразительной способности: существующие TGNN не могут представлять простые операции, такие как скользящее среднее
3. Несоответствие функции потерь: потеря перекрёстной энтропии не соответствует природе упорядочивания задачи сродства
4. Недостаточное использование информации: TGNN не полностью используют глобальную временную динамику и информацию о долгосрочных зависимостях

Исследовательская мотивация

Авторы путём теоретического анализа обнаружили, что простые эвристические методы фактически являются частными случаями линейных моделей пространства состояний (SSM), что обеспечивает теоретическую основу для разработки более мощных архитектур TGNN.

Основные вклады

1. Теоретический вклад: доказано, что простые эвристические методы являются частными случаями линейных SSM, и на основе этой связи разработана архитектура TGNN, способная обобщать эвристические методы
2. Инновация архитектуры: предложена модель NAVIS, объединяющая виртуальное глобальное состояние и механизм линейного пространства состояний, эффективно решающая задачу предсказания сродства узлов
3. Улучшение функции потерь: проанализированы недостатки потери перекрёстной энтропии при предсказании сродства, предложена альтернатива на основе упорядочивания — Lambda-потеря
4. Экспериментальная верификация: метод верифицирован на эталонах TGB и множественных наборах данных, последовательно превосходя существующие методы и эвристические базовые линии

Подробное описание метода

Определение задачи

Дан непрерывный временной динамический граф (CTDG): $G_t = \{(u_j, v_j, \tau_j, w_j)\}_{j=1}^{J(t)}$

Для узла запроса $u \in V$ и будущего момента времени $t^+ > t$ целью является предсказание вектора оценок сродства: $s = F_\theta(u, G_t, t^+) \in \mathbb{R}^{|V|}$

Теоретическая основа

Теорема 1 (линейные SSM обобщают базовые эвристики): Пусть $H$ — множество базовых эвристик (PF, SMA, EMA), $F_{\text{lin-SSM}}$ — множество отображений, реализуемых линейными SSM, тогда: $H \subsetneq F_{\text{lin-SSM}}$

Теорема 2 (ограничения выразительной способности RNN/LSTM/GRU): Стандартные единицы RNN, LSTM или GRU не могут представлять наиболее базовую эвристику постоянного предсказания (PF), то есть не существует параметров, при которых $h_i = x_i$ для всех входных последовательностей.

Архитектура модели NAVIS

NAVIS использует механизм линейного пространства состояний для поддержания состояния каждого узла $h \in \mathbb{R}^d$ и виртуального глобального состояния $g \in \mathbb{R}^d$:

zh = σ(Wxh*x + Whh*hi-1 + bh)
hi = zh ⊙ hi-1 + (1-zh) ⊙ x
zs = σ(Wxs*x + Whs*hi + Wgs*g + bs)  
s = zs ⊙ hi + (1-zs) ⊙ x

где:

• $x$ — предыдущий вектор сродства
• $h_{i-1}, h_i$ — предыдущее и обновлённое состояния
• $g$ — виртуальный глобальный вектор
• $s$ — предсказанный вектор сродства
• $z_h, z_s$ — механизмы адаптивного управления

Ключевые особенности проектирования

1. Механизм линейного обновления: сохраняет концептуальное сходство с EMA, но позволяет адаптивную настройку во время выполнения
2. Виртуальное глобальное состояние: захватывает глобальные тренды путём поддержания буфера недавних векторов сродства
3. Совместимость с механизмом t-Batch: не зависит от скрытых состояний соседей, поддерживает эффективную пакетную обработку
4. Масштабируемость: адаптируется к крупномасштабным графам через разреживание конвейера предсказания сродства

Проектирование функции потерь

Анализ проблемы: Теорема 3 (субоптимальность перекрёстной энтропии для упорядочивания): существуют бесконечные тройки $(y, s_1, s_2)$, где $\text{rank}(s_1) = \text{rank}(y)$ и $\text{rank}(s_2) \neq \text{rank}(y)$, но $\ell_{CE}(s_1, y) > \ell_{CE}(s_2, y)$.

Решение: применение Lambda-потери: $\ell_{\text{Lambda}}(s,y) = \sum_{y_i > y_j} \log_2\left(\frac{1}{1 + e^{-\sigma(s_{\pi_i} - s_{\pi_j})}}\right) \delta_{ij} |A_{\pi_i} - A_{\pi_j}|$

в сочетании с парной маржинальной регуляризацией: $\ell_{\text{Reg}}(s,y) = \sum_{y_i > y_j} \max(0, -(s_{\pi_i} - s_{\pi_j}) + \Delta)$

Экспериментальная установка

Наборы данных

Наборы данных TGB:

• tgbn-trade: сеть сельскохозяйственной торговли между странами ООН 1986-2016 (255 узлов, 468 245 рёбер)
• tgbn-genre: сеть взаимодействия пользователей и музыкальных жанров (1 505 узлов, 17 858 395 рёбер)
• tgbn-reddit: сеть взаимодействия пользователей и subreddit (11 766 узлов, 27 174 118 рёбер)
• tgbn-token: сеть взаимодействия кошельков и криптовалютных токенов (61 756 узлов, 72 936 998 рёбер)

Преобразованные наборы данных предсказания связей:

• Wikipedia: сеть взаимодействия редакторов и статей
• Flights: сеть маршрутов аэропортов во время COVID-19
• USLegis: сеть сотрудничества Сената США
• UNVote: сеть голосований Генеральной Ассамблеи ООН

Метрики оценки

• Основная метрика: NDCG@10 (нормализованный дисконтированный совокупный прирост)
• Экспериментальная установка: временное разделение 70%-15%-15%, 50 эпох, размер пакета 200

Методы сравнения

• Эвристические методы: Persistent Forecast, Moving Average, Historical Average
• Методы TGNN: JODIE, TGAT, CAWN, TCL, GraphMixer, DyGFormer, DyRep, TGN, TGNv2

Результаты экспериментов

Основные результаты

Производительность на наборах данных TGB (NDCG@10):

• tgbn-trade: NAVIS 0.863 против лучшей базовой линии TGNv2 0.735 (+17.4%)
• tgbn-genre: NAVIS 0.520 против лучшей базовой линии TGNv2 0.469 (+10.9%)
• tgbn-reddit: NAVIS 0.552 против лучшей базовой линии TGNv2 0.507 (+8.9%)
• tgbn-token: NAVIS 0.444 против лучшей базовой линии TGNv2 0.294 (+51.0%)

Производительность на преобразованных наборах данных:

• Wikipedia: NAVIS 0.573 против TGNv2 0.433 (+32.3%)
• Flights: NAVIS 0.499 против TGNv2 0.299 (+66.9%)
• USLegis: NAVIS 0.347 против TGNv2 0.253 (+37.2%)
• UNVote: NAVIS 0.952 против TGNv2 0.813 (+17.1%)

Абляционные исследования

Исследования абляции верифицировали важность каждого компонента:

• Линейное обновление состояния против GRU: на tgbn-trade 0.863 против 0.850
• Включение глобального вектора: улучшение примерно на 1-2 процентных пункта
• Потеря упорядочивания против перекрёстной энтропии: значительное улучшение производительности

Ключевые находки

1. Подтверждение преимущества эвристик: простые эвристические методы действительно превосходят сложные TGNN
2. Важность глобальной информации: виртуальное глобальное состояние эффективно захватывает тренды уровня сети
3. Соответствие функции потерь: потеря, чувствительная к упорядочиванию, критична для предсказания сродства
4. Последовательное улучшение: NAVIS достигает последовательного улучшения на всех наборах данных

Связанные работы

Выразительная способность временных графов

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

Эвристические методы и модели пространства состояний

Недавние исследования показали, что простые эвристические методы превосходят сложные TGNN на нескольких эталонах; данная работа впервые явно использует формальную эквивалентность эвристик и SSM для проектирования архитектуры.

Временные графовые нейронные сети

Существующие методы включают архитектуры на основе памяти (TGN, DyRep) и без памяти (DyGFormer, GraphMixer), но ни одна не может эффективно решать специальные требования задачи предсказания сродства узлов.

Заключение и обсуждение

Основные выводы

1. Недостатки существующих TGNN при предсказании сродства узлов обусловлены ограничениями выразительной способности и несоответствием целей обучения
2. Линейные модели пространства состояний обеспечивают теоретическую основу для обобщения эвристических методов
3. NAVIS эффективно решает задачу предсказания сродства узлов путём объединения виртуального глобального состояния и потери, чувствительной к упорядочиванию

Ограничения

1. Моделирование сложных зависимостей: остаётся сложным моделирование сложных многошаговых зависимостей
2. Масштабируемость: размер параметров растёт линейно с числом узлов, требуя стратегий разреживания
3. Полнота теории: не все связанные вопросы полностью решены

Будущие направления

1. Расширение на более сложное моделирование временных зависимостей
2. Повышение масштабируемости для крупномасштабных графов
3. Исследование возможности нелинейных моделей пространства состояний

Глубокая оценка

Преимущества

1. Надёжный теоретический вклад: строгие математические доказательства устанавливают связь между эвристическими методами и SSM
2. Глубокий анализ проблемы: систематический анализ недостатков TGNN при предсказании сродства узлов
3. Разумное проектирование метода: проектирование NAVIS имеет чёткую теоретическую основу и практические соображения
4. Обширные эксперименты: экспериментальная верификация на множественных наборах данных подтверждает эффективность метода
5. Ясное изложение: структура статьи ясна, технические детали описаны точно

Недостатки

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

Влияние

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

Применимые сценарии

1. Системы рекомендаций: предсказание сродства пользователей к товарам
2. Социальные сети: предсказание интенсивности взаимодействия пользователей
3. Финансовые сети: предсказание интенсивности торговых отношений
4. Сети цепочки поставок: предсказание отношений сотрудничества

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