Detailansicht

Graph compression techniques for personalized PageRank

Ole Yannick Schlüter

Art der Arbeit

Masterarbeit

Universität

Universität Wien

Fakultät

Fakultät für Informatik

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Masterstudium Informatik

Betreuer*in

Gramoz Goranci

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.78677

URN

urn:nbn:at:at-ubw:1-30011.02894.941747-9

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

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.

Abstract

(Englisch)

The growing size of graph-structured data has made polynomial-time algorithms increasingly impractical; yet many graph problems admit only such algorithms. One approach addressing this challenge is a reduction paradigm known as graph sparsification or graph compression, a preprocessing technique that reduces the number of edges or nodes in the graph while preserving some graph property of interest. The problem can then be solved on the smaller, preprocessed graph (the sparsifier), and the result is used to infer a solution for the original input graph. The quality of the solution depends on how well the sparsifier preserves the properties of the original graph, and the properties to preserve depend on the specific problem domain. In this work, we investigate vertex sparsifiers that preserve personalized PageRank values, building on earlier work in this area. We show that constructing such sparsifiers can be reduced to operations on the Laplacian matrix of a graph. Leveraging this connection between graphs and matrices, we propose a new algorithm that constructs the same (exact) sparsifiers as existing approaches, but provides a correctness proof based on linear algebra, using the Schur complement as the central tool. This new connection not only simplifies the theoretical analysis but also leads to practical improvements. We develop efficient implementations for constructing exact personalized PageRank sparsifiers that outperform the existing approach on undirected graphs, often achieving at least 2× speedups in practice, and that scale well to large sparse graphs with millions of edges. Furthermore, we introduce an approximation scheme based on approximating the Schur complement, which yields a near-linear running time for constructing sparsifiers and delivers competitive or superior run times across all tested datasets. Regarding the quality of the approximate sparsifiers, our experiments show that they achieve low average error in personalized PageRank values. We further demonstrate that they improve community structure preservation compared to simple induced subgraphs, although the overall quality varies across datasets and remains moderate. While we do not provide formal quality guarantees for the approximation, we also establish a related theoretical limitation for approximating PageRank using sparse graphs.

Autor*innen

Ole Yannick Schlüter

Haupttitel (Englisch)

Graph compression techniques for personalized PageRank

Publikationsjahr

2025

Umfangsangabe

xiii, 80 Seiten : Illustrationen

Sprache

Englisch

Beurteiler*in

Gramoz Goranci

Klassifikation

54 Informatik > 54.10 Theoretische Informatik

AC Nummer

AC17569087

Utheses ID

76116

Studienkennzahl

UA | 066 | 921 | |

Detailansicht

Abstracts

Schlagwörter