2025-11-17T05:52:13.175509

Accelerated Evolving Set Processes for Local PageRank Computation

Huang, Luo, Xiao et al.
This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank (PPR) computation. At each stage of the process, we employ a localized inexact proximal point iteration to solve a simplified linear system. We show that the time complexity of such localized methods is upper bounded by $\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\}$ to obtain an $ε$-approximation of the PPR vector, where $m$ denotes the number of edges in the graph and $R$ is a constant defined via nested evolving set processes. Furthermore, the algorithms induced by our framework require solving only $\tilde{\mathcal{O}}(1/\sqrtα)$ such linear systems, where $α$ is the damping factor. When $1/ε^2\ll m$, this implies the existence of an algorithm that computes an $\ epsilon $-approximation of the PPR vector with an overall time complexity of $\tilde{\mathcal{O}}\left(R^2 / (\sqrtαε^2)\right)$, independent of the underlying graph size. Our result resolves an open conjecture from existing literature. Experimental results on real-world graphs validate the efficiency of our methods, demonstrating significant convergence in the early stages.
academic

Beschleunigte evolvierende Mengenprozesse zur lokalen PageRank-Berechnung

Grundinformationen

  • Paper-ID: 2510.08010
  • Titel: Accelerated Evolving Set Processes for Local PageRank Computation
  • Autoren: Binbin Huang, Baojian Zhou, Luo Luo, Deqing Yang, Yanghua Xiao (Fudan-Universität)
  • Klassifizierung: cs.LG
  • Veröffentlichungskonferenz: 39. Konferenz über neuronale Informationsverarbeitungssysteme (NeurIPS 2025)
  • Paper-Link: https://arxiv.org/abs/2510.08010v2

Zusammenfassung

Dieses Paper präsentiert einen neuen Rahmen basierend auf verschachtelten evolvierenden Mengenprozessen (nested evolving set processes) zur Beschleunigung der Berechnung von personalisiertem PageRank (PPR). In jeder Phase wird eine lokalisierte inexakte proximale Punkt-Iteration zur Lösung vereinfachter linearer Systeme eingesetzt. Die Forschung zeigt, dass die Zeitkomplexität solcher lokalisierter Methoden durch min⁡{O~(R2/ε2),O~(m)}\min\{\tilde{\mathcal{O}}(R^2/ε^2), \tilde{\mathcal{O}}(m)\} begrenzt ist, um eine ε-Approximation des PPR-Vektors zu erhalten, wobei m die Anzahl der Kanten im Graphen darstellt und R eine durch verschachtelte evolvierende Mengenprozesse definierte Konstante ist. Der durch den Rahmen induzierte Algorithmus erfordert nur die Lösung von O~(1/α)\tilde{\mathcal{O}}(1/\sqrt{α}) solcher linearen Systeme, wobei α der Dämpfungsfaktor ist. Wenn 1/ε2≪m1/ε^2 \ll m, bedeutet dies, dass ein Algorithmus existiert, der eine ε-Approximation des PPR-Vektors mit einer Gesamtzeitkomplexität von O~(R2/(αε2))\tilde{\mathcal{O}}(R^2/(\sqrt{α}ε^2)) berechnet, unabhängig von der Größe des zugrunde liegenden Graphen.

Forschungshintergrund und Motivation

Problemdefinition

Der personalisierte PageRank-Vektor (PPR) π ∈ ℝⁿ ist definiert als:

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

wobei eₛ der Standardbasisvektor des Quellknotens s ist, α ∈ (0,1) der Dämpfungsfaktor ist, und A und D jeweils die Adjazenzmatrix und Gradmatrix des ungerichteten Graphen G(V,E) sind.

Forschungsmotivation

  1. Bedeutung: PPR ist ein Kernwerkzeug der Graphenanalyse mit breiter Anwendung in lokaler Clusterung, Diffusionsprozessmodellierung und Graphenneuralen Netzen
  2. Bestehende Einschränkungen:
    • Standardmethoden wie APPR haben Zeitkomplexität O(1/(αε))
    • Beschleunigte Methoden sehen sich der Herausforderung gegenüber, dass Momentumterme die Residuenmonotonie zerstören
    • Bestehende beschleunigte Methoden können den gesamten Graphen durchsuchen, was zu O(m/√α) Zeitkomplexität führt
  3. Offene Fragen: Existiert eine lokale beschleunigte Methode mit Zeitkomplexität abhängig von 1/√α statt 1/α?

Kernbeiträge

  1. AESP-Rahmen: Präsentation des Rahmens für beschleunigte evolvierende Mengenprozesse (AESP), der O~(1/α)\tilde{O}(1/\sqrt{α}) kurze evolvierende Mengenprozesse statt eines einzelnen langen Prozesses verwendet
  2. Theoretische Garantien: Etablierung der Zeitkomplexität O~(vol(St)/(αγt))\tilde{O}(\text{vol}(S_t)/(\sqrt{α}γ_t)), die die Vermutung über beschleunigte Grenzen in der bestehenden Literatur erfüllt
  3. Lokalisierungsgarantien: Beweis, dass die Obergrenze von vol(St)/γt\text{vol}(S_t)/γ_t gleich min⁡{O(R2/ε2),2m}\min\{O(R^2/ε^2), 2m\} ist, was bei 1/ε2≪m1/ε^2 \ll m eine von der Graphengröße unabhängige Komplexität erreicht
  4. Experimentelle Validierung: Verifikation der Methodeneffektivität auf großen realen Graphen mit signifikanter Beschleunigung in frühen Phasen

Methodische Details

Aufgabendefinition

Gegeben ein Genauigkeitsparameter ε, entwerfen Sie einen lokalen Algorithmus zur Berechnung einer ε-Approximation π̂, die ∥D−1(π^−π)∥∞≤ε\|D^{-1}(π̂ - π)\|_∞ ≤ ε erfüllt, während der Zugriff auf den gesamten Graphen vermieden wird.

Kernidee: Verschachtelte evolvierende Mengenprozesse

1. Problemumformulierung

Umformulierung des linearen Systems als stark konvexes Optimierungsproblem:

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

wobei Q = ((1+α)/2)I - ((1-α)/2)D^(-1/2)AD^(-1/2), mit Eigenwerten λ(Q) ∈ α,1.

2. Definition verschachtelter ESP

In der äußeren Schleifenwiederholung t verwaltet der lokale Solver M eine Sequenz aktiver Mengen {S_t^(k)}_{k≥0} über innere Schleifenwiederholungen k, wobei Aktualisierungen auf Knoten in der aktiven Menge beschränkt sind.

3. AESP-Aktualisierungsregel

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

wobei β_t das Momentumgewicht ist und M ein lokaler Operator ist.

Lokalisierte inexakte proximale Operatoren

LOCGD (Lokaler Gradientenabstieg)

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

Aktive Knotenmenge: Stk={u:∣∇uht−1/2(zt(k))∣≥εt}S_t^k = \{u : |∇_u h_t^{-1/2}(z_t^{(k)})| ≥ ε_t\}

LOCAPPR (Lokales APPR)

Koordinaten-weise Aktualisierung für ui∈Stku_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η)

Technische Innovationen

  1. Monotonie-Erhaltung: Durch Lösung von regularisierten PPR-Linearsystemen mit konstanter Konditionszahl wird die Monotonie der ℓ₁-Norm des D^{1/2}-skalierten Gradienten gewährleistet
  2. Lokalisierungskontrolle: Einführung einer Konstanten R zur Begrenzung der Gradienten-Verhältnisse in verschachtelten ESP-Prozessen
  3. Ausgleich zwischen Beschleunigung und Lokalisierung: Erreichung eines Kompromisses zwischen der Abhängigkeit von der Konditionszahl 1/α und der Zeitkomplexität pro Runde O(R²/ε²)

Experimentelle Einrichtung

Datensätze

Experimente verwenden 19 reale Graphen mit Größen von klein bis übergroß:

  • Mittlere Größe: com-dblp (317K Knoten, 1M Kanten)
  • Große Größe: ogb-mag240m (244M Knoten, 1,7B Kanten), ogbn-papers100M (111M Knoten, 1,6B Kanten)
  • Weitere: com-friendster, wiki-en21 usw.

Evaluierungsmetriken

  • Fehlermaß: log⁡∥D−1(π^−π)∥∞\log \|D^{-1}(π̂-π)\|_∞
  • Effizienzmaß: Operationszahl, Laufzeit
  • Beschleunigungsverhältnis: Leistungsverbesserung relativ zu Baseline-Methoden

Vergleichsmethoden

  • APPR: Standard-Algorithmus für approximiertes personalisiertes PageRank
  • APPR-opt: APPR mit optimaler Schrittweite
  • LOCGD: Lokaler Gradientenabstieg
  • ASPR: Beschleunigte spärliche personalisierte PageRank
  • FISTA: Schneller iterativer Schwellenwert-Algorithmus

Implementierungsdetails

  • Dämpfungsfaktor: α = 0,01, 0,1
  • Genauigkeitsschwelle: ε = 10⁻⁶
  • Zufällige Auswahl von 5 Quellknoten für Tests
  • Python-Implementierung mit Numba-Beschleunigung

Experimentelle Ergebnisse

Hauptergebnisse

Leistung bei großen Graphen

Auf vier großen Graphen (ogb-mag240m, ogbn-papers100M, com-friendster, wiki-en21):

  • AESP-LOCAPPR zeigt beste Leistung dank Online-Koordinaten-Aktualisierung
  • Frühe Beschleunigung: AESP-Methoden erreichen schnellere Konvergenz als Baseline-Methoden in frühen Phasen
  • Reduzierte Operationen: 2-10fache Reduktion der Operationen im Vergleich zu APPR

α-Abhängigkeitsanalyse

Bei kleinerem α zeigt AESP signifikante Beschleunigung lokaler Methoden:

  • Tests im Bereich α ∈ 10⁻³, 10⁻¹
  • Beschleunigungsverhältnis wächst mit sinkendem α und validiert √α-Abhängigkeit
  • Laufzeit und Operationszahl sinken signifikant

Vergleich von Initialisierungsstrategien

Vergleich von drei Initialisierungsstrategien z_t^(0):

  1. Kalter Start: z_t^(0) = 0
  2. Vorherige Schätzung: z_t^(0) = x^(t-1)
  3. Momentum-Initialisierung: z_t^(0) = y^(t-1) (empfohlen)

Momentum-Initialisierungsstrategie zeigt beste Leistung mit minimaler Anzahl äußerer Schleifenwiederholungen.

Ablationsstudien

Analyse der Konstanten R

  • R bleibt auf 19 Graphen eine kleine Konstante (1,0-1,4)
  • R ist unempfindlich gegenüber Graphengröße und Konditionszahl
  • Validiert die Angemessenheit der Annahme der R-Begrenztheit in der theoretischen Analyse

Analyse des vol(S_t)/γ_t-Verhältnisses

Experimentelle Validierung der theoretischen Grenze vol(St)/γt≤min⁡{Ct0/εt,2m}\text{vol}(S_t)/γ_t ≤ \min\{C_t^0/ε_t, 2m\}.

Verwandte Arbeiten

PPR-Berechnungsmethoden

  • Iterative Methoden: Konjugierte Gradienten, Chebyshev-Methoden mit Komplexität O(m/√α)
  • Lokale Methoden: APPR (O(1/(αε))), Variationsmethoden (O(1/((α+μ²)ε)))
  • Beschleunigungsversuche: FISTA, lineare Kopplung zerstören Monotonie, können Lokalisierung nicht garantieren

Evolvierende Mengenprozesse

  • Von Morris und Peres eingeführtes Konzept zur Analyse von Mischzeiten
  • Lokalisierte Chebyshev-Methode von Zhou et al., aber ohne Konvergenzgarantien

Beschleunigte Optimierung

  • Catalyst-Rahmen: Inexakte beschleunigte proximale Punkt-Methoden
  • Dieses Paper adaptiert diese auf lokale Methoden unter Beibehaltung der Monotonie

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Theoretischer Durchbruch: Erste nachweisbare lokale Beschleunigung der PPR-Berechnung mit Zeitkomplexität-Verbesserung von O(1/α) auf O(1/√α)
  2. Praktikabilität: Wenn ε ≥ 1/√m, ist die Algorithmen-Komplexität unabhängig von der Graphengröße
  3. Universalität: Der Rahmen ist auf Variationsformen und andere verwandte Probleme erweiterbar

Einschränkungen

  1. Konstanten-R-Grenze: R kann nicht universell durch Graphengröße oder Eingabeparameter begrenzt werden
  2. ε²-Abhängigkeit: Wenn ε < 1/√m, degeneriert die lokale Grenze zu O(m/√α)
  3. Theorie-Praxis-Lücke: Konservative Schätzung von ε_t kann zu suboptimalen Grenzen führen

Zukünftige Richtungen

  1. Verbesserte Grenzen: Erkundung, ob die vermutete O(1/(√αε))-Komplexität erreichbar ist
  2. Beseitigung der R-Abhängigkeit: Beseitigung der Konstanten R durch Einschränkungen oder adaptive Neustarts
  3. Erweiterte Anwendungen: Anwendung der Techniken auf bidirektionales PPR, Single-Source-PPR-Schätzung usw.

Tiefgreifende Bewertung

Stärken

  1. Signifikanter theoretischer Beitrag: Löst offene Vermutungen in der Literatur mit strengen theoretischen Garantien
  2. Starke Methodische Innovation: Geschickte Kombination des Catalyst-Rahmens mit lokalen evolvierenden Mengenprozessen
  3. Umfassende Experimente: Validierung auf 19 Graphen unterschiedlicher Größe von klein bis übergroß
  4. Klare Präsentation: Rigorose mathematische Ableitungen und detaillierte Algorithmusbeschreibungen

Schwächen

  1. Praktische Einschränkungen: Vorteil nicht offensichtlich bei sehr kleinem ε, R-Begrenzungsproblem beeinflusst praktische Anwendung
  2. Implementierungskomplexität: Verschachtelte Struktur und Parametereinstellung erhöhen Implementierungsschwierigkeit
  3. Unvollständige Vergleiche: Mangel an detaillierten Vergleichen mit neuesten Beschleunigungsmethoden

Auswirkungen

  1. Akademischer Wert: Bietet neue Perspektiven für Graphen-Algorithmen-Beschleunigung mit großer theoretischer Bedeutung
  2. Praktischer Wert: Potenzielle Anwendungen in großflächiger Graphenanalyse, Empfehlungssystemen usw.
  3. Reproduzierbarkeit: Öffentlich verfügbarer Code mit detaillierten Experimenteinstellungen

Anwendungsszenarien

  1. Großflächige Graphenanalyse: Besonders wenn Genauigkeitsanforderungen nicht extrem hoch sind (ε ≥ 1/√m)
  2. Echtzeit-Empfehlungssysteme: Schnelle Berechnung lokaler Wichtigkeitswerte erforderlich
  3. Graphenneurale Netze: Als Vorverarbeitungsschritt zur Berechnung von Knotenwichtigkeit

Literaturverzeichnis

Dieses Paper zitiert 52 relevante Arbeiten, die wichtige Arbeiten in mehreren Bereichen wie PPR-Berechnung, beschleunigte Optimierung und lokale Algorithmen abdecken und eine solide theoretische Grundlage für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives Paper mit Schwerpunkt auf Theorie und Praxis, das signifikante Fortschritte beim wichtigen Problem der PPR-Berechnungsbeschleunigung erzielt. Obwohl einige theoretische Einschränkungen bestehen, machen seine Innovativität und Praktikabilität es zu einem wichtigen Beitrag auf diesem Gebiet.