Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products

Das große Ganze: Dreiecke in einem riesigen Netz zählen

Stellen Sie sich vor, Sie haben ein massives soziales Netzwerk, wie ein riesiges Geflecht von Freunden, in dem jeder mit vielen anderen verbunden ist. In diesem Netz ist ein „Dreieck“ ein ganz spezifisches Muster: Person A kennt Person B, Person B kennt Person C und Person C kennt Person A.

Das Zählen dieser Dreiecke ist für Datenwissenschaftler super wichtig. Es hilft ihnen zu verstehen, wie eng vernetzt eine Gemeinschaft ist, wer als Nächstes Freunde werden könnte oder um seltsames Verhalten (wie etwa Betrugsringe) aufzuspüren.

Das Problem:
Wenn das Netzwerk klein ist, kann man einfach jedes Dreieck einzeln zählen. Aber wenn das Netzwerk Millionen von Menschen umfasst, ist das Zählen all dieser Dreiecke so, als würde man versuchen, jedes einzelne Sandkorn an einem Strand von Hand zu zählen. Das braucht zu viel Zeit und Rechenleistung.

Der Standard-Mathematiktrick zum Zählen dieser Dreiecke beinhaltet ein riesiges Gitter (eine sogenannte Matrix), das das gesamte Netzwerk darstellt. Um das Ergebnis zu erhalten, muss man dieses Gitter normalerweise dreimal mit sich selbst multiplizieren. Aber für riesige Netzwerke ist das Erstellen dieses „multiplizierten Gitters“ unmöglich, da es mehr Speicherplatz benötigen würde, als alle Computer auf der Erde zusammen haben.

Die alte Lösung: Das „Ratespiel“

Um dies zu lösen, nutzen Mathematiker eine Methode namens Hutchinson-Schätzer. Denken Sie an dies wie an ein Spiel namens „Schätze den Durchschnitt“.

Anstatt die exakte Zahl zu berechnen, werfen Sie eine Reihe von zufälligen Dartpfeilen auf das Gitter. Sie fragen den Computer: „Was passiert, wenn ich dieses Gitter mit diesem zufälligen Dartpfeil multipliziere?“ Sie machen das viele Male, nehmen den Durchschnitt der Ergebnisse und – magisch – ergibt dieser Durchschnitt eine sehr gute Schätzung der Gesamtzahl der Dreiecke.

Das geht schnell, weil Sie das riesige multiplizierte Gitter nicht bauen müssen; Sie müssen lediglich einfache Multiplikationen mit dem ursprünglichen Gitter durchführen.

Das neue Problem: Der „Nachzügler“ und der „Lärmige Raum“

Die Arbeit befasst sich mit einem spezifischen Problem, das auftritt, wenn man dies auf einem massiven Computersystem mit vielen Prozessoren versucht, die zusammenarbeiten (wie ein Team von Menschen, die ein Puzzle lösen).

Stellen Sie sich vor, Sie haben ein Team von 100 Personen, die versuchen, das Ergebnis eines dieser „Dartpfeil-Würfe“ zu berechnen.

1. Die Kosten des Redens: Um das Endergebnis zu erhalten, muss jeder Mensch seinen Teil der Berechnung mit allen anderen teilen. In einem riesigen Netzwerk dauert dieses „Reden“ (die Kommunikation) sehr lange und bremst alles aus.
2. Der Nachzügler: Manchmal ist eine oder zwei Personen im Team langsamer als der Rest (vielleicht ist ihr Computer gerade mit etwas anderem beschäftigt). In einem traditionellen Setup muss das gesamte Team auf den langsamsten Teilnehmer warten, bevor es zum nächsten Schritt übergehen kann. Dies wird als „Synchronisationswartezeit“ bezeichnet.

Die Autoren erkannten, dass das Warten darauf, dass jeder fertig wird und jede einzelne Zahl teilt, eine Verschwendung von Zeit ist.

Die neue Lösung: Der „Teilweise Blick“

Die Autoren schlagen eine clevere neue Art vor, das Ratespiel zu spielen. Anstatt darauf zu warten, dass das ganze Team fertig ist und jede einzelne Zahl teilt, erlauben sie dem Team, nur auf einen zufälligen, teilweisen Satz von Zahlen zu blicken und sofort weiterzumachen.

Die Analogie:
Stellen Sie sich vor, Sie versuchen, die durchschnittliche Größe einer Menge zu schätzen.

• Der alte Weg: Sie warten, bis jede einzelne Person auf einer Waage steht, ihre Größe aufschreibt und sie an einen zentralen Computer sendet. Sie warten auf die langsamste Person, bevor Sie den Durchschnitt berechnen.
• Der neue Weg: Sie sagen der Menge: „Ruft einfach eure Größe, wenn ihr Lust dazu habt, und nur wenn ihr an einer zufälligen Stelle steht.“ Sie warten nicht auf alle. Sie schnappen sich einfach die Stimmen, die Sie hören, machen eine schnelle Berechnung und gehen zur nächsten Runde über.

In der wissenschaftlichen Arbeit nennen sie dies „partielle Beobachtung“ (partial observation). Sie entscheiden zufällig, welche Teile der Berechnung sie betrachten und welche sie ignorieren. Zudem erlauben sie den „langsamen“ Prozessoren, ihre Daten später beizusteuern, ohne das gesamte Team aufzuhalten.

Was sie bewiesen haben (Der „Wissenschaftsteil“)

Sie könnten denken: „Wenn ich Daten ignoriere, wird meine Antwort dann nicht falsch sein?“ Die Autoren nutzten schwere Mathematik, um drei Dinge zu beweisen:

1. Es ist immer noch fair (Unbiased): Selbst wenn sie nur auf zufällige, teilweise Teile des Puzzles schauen, ist der Durchschnitt ihrer Vermutungen immer noch vollkommen genau. Sie schummeln nicht; sie sind nur effizienter.
2. Es ist zuverlässig (Variance): Sie haben genau berechnet, wie sehr das Ergebnis schwanken könnte. Sie haben bewiesen, dass die Antwort selbst mit fehlenden Daten nah an der Wahrheit bleibt, besonders wenn man das Experiment oft genug wiederholt.
3. Es ist schnell: Sie zeigten, dass das System viel schneller läuft, indem sie den Schritt des „Wartens auf alle“ übersprangen, insbesondere wenn die Computer an verschiedenen Orten stehen oder unterschiedliche Geschwindigkeiten haben.

Die Ergebnisse: Funktioniert es?

Sie haben ihre neue Methode an drei verschiedenen Arten von Netzwerken getestet:

1. Ein echtes Netzwerk von Wissenschaftlern, die gemeinsam wissenschaftliche Arbeiten verfasst haben.
2. Ein künstlich erzeugtes Zufallsnetzwerk.
3. Ein Netzwerk von Webseiten der Harvard University.

Sie verglichen ihre „Teilweise Blick“-Methode mit der „Vollständiges Warten“-Methode.

• Das Ergebnis: Die „Teilweise Blick“-Methode lieferte fast die gleiche genaue Antwort wie die vollständige Methode.
• Der Kompromiss: Wenn sie weniger Zahlen betrachteten (um Zeit zu sparen), war die Antwort ein wenig „rauschiger“ (das Konfidenzintervall war breiter), aber sie war immer noch sehr gut.
• Der Gewinn: Sie sparten eine massive Menge an Zeit und Computerressourcen, indem sie nicht darauf warteten, dass die langsamsten Teile des Systems aufholen.

Zusammenfassung

Diese Arbeit führt eine intelligentere Art und Weise ein, Dreiecke in riesigen Netzwerken zu zählen. Anstatt ein massives Computerteam zu zwingen, auf jeden zu warten, der jedes einzelne Detail teilt, erlauben die Autoren den Computern, asynchron zu arbeiten und nur zufällige, teilweise Informationen zu teilen.

Sie haben mathematisch bewiesen, dass dieser „träge“ Ansatz im Durchschnitt immer noch das richtige Ergebnis liefert, und ihre Experimente zeigten, dass es in der realen Welt hervorragend funktioniert, was die Analyse riesiger Netzwerke viel schneller macht als bisher.