16.07.2025, 11:00 Uhr
Universität Wien
Besprechungsraum 4.34
Währinger Str. 29
1090 Wien
Titel: Graph Compression Techniques for Personalized PageRank
Kurzfassung:
Die zunehmende Größe graphstrukturierter Daten macht Algorithmen mit polynomieller
Laufzeit zunehmend unpraktikabel, dennoch lassen sich viele Graphprobleme nur mit
solchen Algorithmen lösen. Ein möglicher Ansatz zur Bewältigung dieser Herausforderung
ist ein Reduktionsparadigma, das als Graph-Sparsifizierung oder Graph-Kompression
bekannt ist. Dabei handelt es sich um eine Vorverarbeitungstechnik, die die Anzahl
der Kanten oder Knoten im Graphen reduziert, während bestimmte relevante Graph-
Eigenschaften erhalten bleiben. Das Problem kann auf dem kleineren, vorverarbeiteten
Graphen (dem sogenannten Sparsifier) gelöst werden. Das Ergebnis dient dazu, eine
Lösung für den ursprünglichen Eingabegraphen abzuleiten. Die Qualität der Lösung hängt
davon ab, wie genau die Eigenschaften des Originalgraphen im Sparsifier beibehalten
werden. Welche Eigenschaften erhalten bleiben sollen, variiert je nach spezifischem
Anwendungsbereich.
In dieser Arbeit untersuchen wir Vertex-Sparsifier, die personalisierte PageRank-Werte
bewahren und knüpfen dabei an frühere Arbeiten in diesem Bereich an. Wir zeigen, dass
sich die Konstruktion solcher Sparsifier auf Operationen an der Laplace-Matrix eines
Graphen reduzieren lässt. Durch die Nutzung dieser Verbindung zwischen Graphen und
Matrizen entwerfen wir einen neuen Algorithmus, der dieselben (exakten) Sparsifier wie in
bestehenden Ansätzen konstruiert, dessen Korrektheit jedoch auf linearer Algebra basiert
und das Schur-Komplement als zentrales Werkzeug nutzt.
Diese neue Verbindung vereinfacht nicht nur die theoretische Analyse, sondern führt
auch zu praktischen Verbesserungen. Wir entwickeln effiziente Implementierungen zur
Konstruktion exakter personalisierter PageRank-Sparsifier, die auf ungerichteten Graphen
bessere Ergebnisse liefern als der bestehende Ansatz. In der Praxis können wir oft eine
mindestens doppelt so schnelle Ausführungszeit beobachten und eine Skalierung auf große
Graphen (mit mehreren Millionen Kanten) ermöglichen. Darüber hinaus stellen wir
ein Approximationsverfahren vor, das auf der Approximation des Schur-Komplements
basiert. Dieses Verfahren erlaubt eine nahezu lineare Laufzeit für die Konstruktion von
Sparsifiern und erzielt über alle getesteten Datensätze hinweg eine konkurrenzfähige
oder überlegene Ausführungszeit. Bezüglich der Qualität der approximativen Sparsifier
zeigen unsere Experimente, dass sie einen geringen durchschnittlichen Fehler für die
personalisierten PageRank-Werte aufweisen. Zudem verbessern sie die Erhaltung der
Community-Struktur im Vergleich zu einfachen induzierten Teilgraphen, auch wenn die
Gesamtqualität zwischen den Datensätzen variiert und moderat bleibt. Wir können
keine formalen Qualitätsgarantien für die von uns verwendeten Approximation geben,
zeigen dafür aber eine theoretische Limitierung für die Approximation von PageRank mit
dünnbesetzten Graphen in einem leicht abgewandelten Rahmen auf.