Neue Lanczos-Algorithmen beschleunigen Widerstandsdistanzen in großen Graphen

Ein neues arXiv-Preprint (2601.11159v1) präsentiert zwei innovative Verfahren zur Berechnung von Widerstandsdistanzen in großen Graphen. Diese Distanzmessung ist ein zentrales Werkzeug in vielen Graph-Analyse-Anwendungen wie Clustering, Link‑Prediction und Graph‑Neural‑Networks.

Die Autoren stellen die Lanczos‑Iteration vor, ein globaler Algorithmus, der in nahezu linearer Zeit arbeitet. Seine Laufzeit beträgt \(\tilde{O}(\sqrt{\kappa}\,m)\), wobei \(m\) die Anzahl der Kanten und \(\kappa\) die Bedingungszahl der Laplace‑Matrix ist. Im Vergleich zu bisherigen Power‑Iteration‑Methoden bietet dies eine Geschwindigkeitssteigerung um den Faktor \(\sqrt{\kappa}\).

Zusätzlich wird die Lanczos‑Push‑Methode vorgestellt, ein lokaler Algorithmus, dessen Laufzeit \(\tilde{O}(\kappa^{2.75})\) beträgt – völlig unabhängig von der Graphgröße. Unter üblichen, milden Annahmen verbessert sich die Leistung gegenüber den besten Random‑Walk‑basierten lokalen Verfahren um \(\kappa^{0.25}\). Die Autoren untermauern ihre Ansätze mit umfangreichen Experimenten, die die theoretischen Vorteile praktisch bestätigen.