Analysis of Distance Functions in Graphs

Abstract

Many machine learning algorithms use graphs to model relations between data points. One of the main objects of interest for such algorithms is the distance between vertices. There are several distance functions defined between graph vertices, each reflecting different properties of the underlying graph. The first part of this thesis characterizes properties of global distance functions in graphs: • Shortest path distance: The behavior of the shortest path distance depends on how we construct our graph from the data points. I show that in unweighted k-nearest neighbor graphs, the shortest path distance converges to an unpleasant distance function whose properties are detrimental to some machine learning problems. • p-resistance distance: The p-resistance distance is a generalization of the resistance distance and contains several other distances as its special cases. I study the convergence of the p-resistance distance in large geometric graphs and show that an interesting phase transition takes place. There exist two critical thresholds p* and p** such that if p < p*, then the p-resistance depends on meaningful global properties of the graph, whereas if p > p**, it only depends on trivial local quantities and does not convey any useful information. The second part of this thesis deals with local distances in graphs. Local clustering and friend recommendation are the topics covered in this part. • Local clustering is the task of finding a highly connected cluster around a vertex of interest. I propose a new random walk model for local clustering, consisting of several \"agents\" connected by ropes. All agents move independently but their distances are constrained by the ropes between them. The main insight is that for several agents it is harder to simultaneously travel over the bottleneck of a graph than for just one agent. • Local distances are used for recommending new friends in social networks. Here, I propose a new distance between members of the network that exploits the temporal data in the friendship network to recommend new friends. The third part of my thesis is devoted to the problem of downsampling massive graphs. The goal of downsampling is to produce a smaller \"version\" of a given graph, which would be easier to process and visualize. Here, a new method is proposed and followed by its thorough statistical analysis. The output of this method is a downsampled graph that provably inherits many properties of the original graph.

Viele Algorithmen des maschinellen Lernens verwenden Graphen, um die Beziehungen zwischen den Datenpunkten zu modellieren. Einer der interessantesten Aspekte für solche Algorithmen ist der des Abstands zwischen den Knoten. Es gibt verschiedene Abstandsfunktionen auf der Menge der Knoten eines Graphen, die jeweils unterschiedliche Eigenschaften des zugrunde liegenden Graphen reflektieren. Der erste Teil dieser Dissertation charakterisiert Eigenschaften zweier solcher globalen Abstandsfunktionen in Graphen: • Kürzeste Pfad-Distanz: Das Verhalten der kürzesten Pfad-Distanz hängt davon ab, wie wir unseren Graphen aus den Datenpunkten konstruieren. Ich zeige, dass in ungewichteten k-Nächster-Nachbar-Graphen die kürzeste Pfad-Distanz gegen eine \"unangenehme\" Abstandsfunktion konvergiert, deren Eigenschaften sich nachteilig auf einige Ziele des maschinellen Lernens auswirken können. • p-resistance-Distanz: Die p-resistance-Distanz ist eine Verallgemeinerung der resistance-Distanz und enthält auch noch weitere Abstandsfunktionen als Sonderfälle. Ich behandle die Konvergenz der p-resistance-Distanz in großen geometrischen Graphen und zeige, dass ein interessanter Phasenübergang stattfindet: Es gibt zwei kritische Schwellenwerte p* und p**, sodass für p < p* die p-resistance von bedeutenden globalen Eigenschaften des Graphen bestimmt wird, während sie für p > p** nur von trivialen lokalen Größen abhängt und keinerlei nützliche Information enthält. Der zweite Teil dieser Dissertation befasst sich mit lokalen Abständen in Graphen. Lokales Clustering und Friend-Recommendation werden hier abgedeckt. • Lokales Clustering ist die Aufgabe, einen “stark” verbundenen Cluster um einen Punkt hohen Interesses zu finden. Ich schlage ein neues Random-Walk-Modell für lokales Clustering vor, bestehend aus mehreren “Agenten”, welche durch Seile miteindander verbunden sind. Alle Agenten können sich unabhängig voneinander bewegen, ihre Abstände zueinander werden aber durch die Seile zwischen ihnen begrenzt. Die entscheidende Einsicht dabei ist, dass es für mehrere Agenten schwieriger ist, gleichzeitig über den “Bottleneck” eines Graphen zu wandern, als dies für nur einen Agenten der Fall ist. • Lokale Abstände werden für das Empfehlen von neuen Freunden in sozialen Netzwerken verwendet. Ich schlage dabei eine neue Distanzfunktion zwischen den Mitgliedern des Netzwerks vor, sodass zeitbezogene Daten des Netzwerks für die Empfehlung genützt werden. Der dritte Teil meiner Dissertation ist dem Problem des “Downsamplings” großer Graphen gewidmet. Ziel dabei ist es, eine kleinere “Version” eines Graphen zu erzeugen, die leichter zu verarbeiten und zu visualisieren ist. Ich stelle in diesem Teil ein neues Verfahren und seine gründliche statistische Analyse vor. Resultat dieses Verfahrens ist ein verkleinerter Graph, der nachweislich viele Eigenschaften des ursprünglichen Graphen erbt.