Ускоренные эволюционирующие процессы множеств для локального вычисления PageRank

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

• ID статьи: 2510.08010
• Название: Accelerated Evolving Set Processes for Local PageRank Computation
• Авторы: Binbin Huang, Baojian Zhou, Luo Luo, Deqing Yang, Yanghua Xiao (Фуданьский университет)
• Классификация: cs.LG
• Конференция: 39-я конференция по нейронным системам обработки информации (NeurIPS 2025)
• Ссылка на статью: https://arxiv.org/abs/2510.08010v2

Аннотация

В данной работе предложена новая структура, основанная на вложенных эволюционирующих процессах множеств (nested evolving set processes), для ускорения вычисления персонализованного PageRank (PPR). На каждом этапе используется локализованная неточная итерация проксимального оператора для решения упрощённой линейной системы. Исследование показывает, что верхняя граница временной сложности таких локализованных методов составляет $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$ для получения ε-приближения вектора PPR, где m обозначает количество рёбер в графе, а R — константа, определённая через вложенные эволюционирующие процессы множеств. Алгоритм, индуцированный данной структурой, требует решения только $\tilde{\mathcal{O}}(1/\sqrt{α})$ таких линейных систем, где α — коэффициент затухания. Когда $1/ε^2 \ll m$, это означает существование алгоритма, вычисляющего ε-приближение вектора PPR с общей временной сложностью $\tilde{\mathcal{O}}(R^2/(\sqrt{α}ε^2))$, независимой от размера базового графа.

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

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

Вектор персонализованного PageRank π ∈ ℝⁿ определяется как:

(I - (1-α)(I + AD⁻¹)/2)π = αeₛ

где eₛ — стандартный базисный вектор, соответствующий исходному узлу s, α ∈ (0,1) — коэффициент затухания, A и D — матрица смежности и матрица степеней неориентированного графа G(V,E) соответственно.

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

1. Значимость: PPR является основным инструментом анализа графов, широко применяется в локальной кластеризации, моделировании процессов диффузии, графовых нейронных сетях и других областях
2. Существующие ограничения:
   • Стандартные методы, такие как APPR, имеют временную сложность O(1/(αε))
   • Ускоренные методы сталкиваются с проблемой нарушения монотонности остатка членами импульса
   • Существующие ускоренные методы могут обращаться ко всему графу, что приводит к временной сложности O(m/√α)
3. Открытый вопрос: Существует ли локальный ускоренный метод с временной сложностью, зависящей от 1/√α вместо 1/α?

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

1. Структура AESP: Предложена структура ускоренных эволюционирующих процессов множеств (AESP), использующая $\tilde{O}(1/\sqrt{α})$ коротких эволюционирующих процессов вместо одного длинного процесса
2. Теоретические гарантии: Установлена временная сложность $\tilde{O}(\text{vol}(S_t)/(\sqrt{α}γ_t))$, соответствующая гипотезе об ускоренных границах в существующей литературе
3. Гарантии локальности: Доказана верхняя граница $\text{vol}(S_t)/γ_t$ равная $\min\{O(R^2/ε^2), 2m\}$, достигающая сложности, независимой от размера графа, когда $1/ε^2 \ll m$
4. Экспериментальная проверка: Метод верифицирован на крупномасштабных реальных графах, демонстрирующий значительное ускорение на ранних этапах

Описание методики

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

Для заданного параметра точности ε разработать локальный алгоритм, вычисляющий ε-приближение π̂, удовлетворяющее $\|D^{-1}(π̂ - π)\|_∞ ≤ ε$, избегая при этом обращения ко всему графу.

Основная идея: вложенные эволюционирующие процессы множеств

1. Переформулировка задачи

Переформулировка линейной системы в задачу сильно выпуклой оптимизации:

min f(x) = (1/2)x⊤Qx - αx⊤D^(-1/2)b

где Q = ((1+α)/2)I - ((1-α)/2)D^(-1/2)AD^(-1/2), собственные значения λ(Q) ∈ α,1.

2. Определение вложенного ESP

На внешней итерации цикла t локальный решатель M поддерживает последовательность активных множеств {S_t^(k)}_{k≥0} на внутренних итерациях цикла k, обновления ограничены узлами в активном множестве.

3. Правило обновления AESP

x^(t) = M(φ_t, y^(t-1), η, α, b, G)
y^(t) = x^(t) + β_t(x^(t) - x^(t-1))

где β_t — вес импульса, M — локальный оператор.

Локализованный неточный проксимальный оператор

LOCGD (локальный градиентный спуск)

z_t^(k+1) = z_t^(k) - (2∇h_t(z_t^(k)) ∘ 1_{S_t^k})/(1 + α + 2η)

множество активных узлов: $S_t^k = \{u : |∇_u h_t^{-1/2}(z_t^{(k)})| ≥ ε_t\}$

LOCAPPR (локальный APPR)

координатное обновление для $u_i ∈ S_t^k$:

z_t^(k_{i+1}) = z_t^(k_i) - (2∇h_t(z_t^{(k_i)}) ∘ 1_{u_i})/(1 + α + 2η)

Технические инновации

1. Сохранение монотонности: Путём решения регуляризованной линейной системы PPR с числом обусловленности, равным константе, обеспечивается монотонное убывание ℓ₁-нормы D^{1/2}-масштабированного градиента
2. Контроль локальности: Введена константа R для ограничения отношения градиентов в процессе вложенного ESP
3. Баланс ускорения и локальности: Достигнут компромисс между зависимостью от числа обусловленности 1/α и временной сложностью каждого раунда O(R²/ε²)

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

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

Эксперименты проведены на 19 реальных графах различных масштабов:

• Средний масштаб: com-dblp (317K узлов, 1M рёбер)
• Крупный масштаб: ogb-mag240m (244M узлов, 1.7B рёбер), ogbn-papers100M (111M узлов, 1.6B рёбер)
• Другие: com-friendster, wiki-en21 и т.д.

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

• Мера ошибки: $\log \|D^{-1}(π̂-π)\|_∞$
• Мера эффективности: количество операций, время выполнения
• Коэффициент ускорения: улучшение производительности относительно базовых методов

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

• APPR: стандартный алгоритм приближённого персонализованного PageRank
• APPR-opt: APPR с оптимальным размером шага
• LOCGD: локальный градиентный спуск
• ASPR: ускоренный разреженный персонализованный PageRank
• FISTA: быстрый алгоритм итеративного сжатия-пороговой обработки

Детали реализации

• Коэффициент затухания: α = 0.01, 0.1
• Порог точности: ε = 10⁻⁶
• Случайный выбор 5 исходных узлов для тестирования
• Реализация на Python с ускорением numba

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

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

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

На четырёх крупномасштабных графах (ogb-mag240m, ogbn-papers100M, com-friendster, wiki-en21):

• AESP-LOCAPPR показывает лучшие результаты благодаря онлайн-обновлению координат
• Раннее ускорение: методы AESP достигают более быстрой сходимости на ранних этапах по сравнению с базовыми методами
• Сокращение операций: сокращение на 2-10 раз операций по сравнению с APPR

Анализ зависимости от α

При малых значениях α AESP значительно ускоряет стандартные локальные методы:

• Тестирование в диапазоне α ∈ 10⁻³, 10⁻¹
• Коэффициент ускорения увеличивается с уменьшением α, подтверждая зависимость от √α
• Значительное снижение времени выполнения и количества операций

Сравнение стратегий инициализации

Сравнение трёх стратегий инициализации z_t^(0):

1. Холодный старт: z_t^(0) = 0
2. Предыдущая оценка: z_t^(0) = x^(t-1)
3. Инициализация с импульсом: z_t^(0) = y^(t-1) (рекомендуется)

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

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

Анализ константы R

• На 19 графах R остаётся малой константой (1.0-1.4)
• R нечувствительна к размеру графа и числу обусловленности
• Подтверждает обоснованность предположения об ограниченности R в теоретическом анализе

Анализ отношения vol(S_t)/γ_t

Эксперименты подтверждают теоретическую границу $\text{vol}(S_t)/γ_t ≤ \min\{C_t^0/ε_t, 2m\}$.

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

Методы вычисления PPR

• Итеративные методы: метод сопряжённых градиентов, метод Чебышёва, сложность O(m/√α)
• Локальные методы: APPR (O(1/(αε))), вариационные методы (O(1/((α+μ²)ε)))
• Попытки ускорения: FISTA, линейная связь нарушают монотонность, не гарантируют локальность

Эволюционирующие процессы множеств

• Концепция, предложенная Morris и Peres, используется для анализа времени смешивания
• Локализованный метод Chebyshev Zhou и др., но без гарантий сходимости

Ускоренная оптимизация

• Структура Catalyst: неточный ускоренный метод проксимального оператора
• Данная работа адаптирует её к локальным методам, сохраняя монотонность

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

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

1. Теоретический прорыв: впервые достигнуто доказуемое локальное ускорение вычисления PPR, улучшение временной сложности с O(1/α) до O(1/√α)
2. Практичность: когда ε ≥ 1/√m, сложность алгоритма независима от размера графа
3. Универсальность: структура может быть расширена на вариационные формы и другие связанные задачи

Ограничения

1. Ограничение константы R: невозможно универсально ограничить R размером графа или входными параметрами
2. Зависимость от ε²: когда ε < 1/√m, локальная граница деградирует до O(m/√α)
3. Разрыв между теорией и практикой: консервативная оценка ε_t может привести к субоптимальным границам

Направления будущих исследований

1. Улучшение границ: исследование возможности достижения предполагаемой сложности O(1/(√αε))
2. Исключение зависимости от R: исключение константы R через ограничения или адаптивные перезапуски
3. Расширение приложений: применение техники к двусторонним PPR, оценкам PPR одного источника и другим задачам

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

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

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

Недостатки

1. Ограничения практичности: преимущества не очевидны при очень малых ε, проблема ограничения R влияет на практическое применение
2. Сложность реализации: вложенная структура и настройка параметров усложняют реализацию
3. Неполное сравнение: недостаточно детального сравнения с новейшими ускоренными методами

Влияние

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

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

1. Анализ крупномасштабных графов: особенно когда требования к точности не экстремальны (ε ≥ 1/√m)
2. Системы рекомендаций в реальном времени: требующие быстрого вычисления локальных оценок важности
3. Графовые нейронные сети: использование в качестве этапа предварительной обработки для вычисления важности узлов

Библиография

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

Общая оценка: Это высококачественная работа, сочетающая теорию и практику, достигающая значительного прогресса в важной задаче ускорения вычисления PPR. Несмотря на некоторые теоретические ограничения, её инновационность и практичность делают её значительным вкладом в данную область.