The Graph Mining Library – Bibliothek für Graph-Algorithmen und -Analysen

 (github.com/google)
3 Punkte von GN⁺ 2023-10-05 | 1 Kommentare | Auf WhatsApp teilen
  • Ziel des Google Graph Mining Teams ist es, eine hochskalierbare Bibliothek für Graph-Algorithmen und -Analysen aufzubauen und in Google-Produkten einzusetzen; der derzeitige Umfang umfasst eine Sammlung von Clustering-Algorithmen
  • Die entwickelten Tools zielen auf den Aufbau von Ähnlichkeitsgraphen, Clustering, Node Classification, Node Embeddings, Training von Graph Neural Networks, Graph-Visualisierung, verschiedene Sampling-Verfahren und Ähnlichkeits-Ranking
  • Der Clustering-Bereich besteht aus Shared-Memory-Parallelalgorithmen, die bis auf Graphen mit mehreren zehn Milliarden Kanten skalieren, sowie mehreren sequenziellen Algorithmen
  • Die parallelen Algorithmen sind Implementierungen auf Basis von Forschungsarbeiten zu HAC, Correlation Clustering, Affinity Clustering und Parline
  • Das Graph Neural Network Framework wird im separaten Projekt TF-GNN bereitgestellt
  • Für einen schnellen Start installiert man Bazel und führt anschließend bazel run //examples:quickstart aus
  • Dies ist kein offiziell von Google unterstütztes Produkt; Fragen und Feedback sollen über Issues in diesem Repository eingereicht werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-10-05
Hacker-News-Kommentare

  • Graph Mining war vor etwa zehn Jahren wirklich im Trend. Das erinnert an GraphX (https://spark.apache.org/graphx/) und GraphLab (https://en.wikipedia.org/wiki/GraphLab) sowie an Graphdatenbanken.
    Vermutlich fiel das zeitlich mit dem Social-Network-Phänomen zusammen; in jüngerer Zeit bekam geometrisches Lernen, also Machine Learning auf Graphen und anderen Strukturen, Aufmerksamkeit, wurde dann aber von LLMs aus dem Rampenlicht verdrängt. Trotzdem halte ich geometrisches Lernen weiterhin für sehr vielversprechend und würde mir wünschen, dass es populärer wird.

    • Bei „Graphdatenbanken“ gibt es eine Strömung, die Graphen als universellen Ansatz für Daten betrachtet, mit RDF und SPARQL sowie zahlreichen ähnlichen Versuchen. Man kann auch an C-Programme denken, bei denen die zentrale Datenstruktur ein Pointer-Graph ist.
      In solchen Graphen gibt es üblicherweise extrem viele unterschiedliche Kantentypen, etwa „ist verheiratet mit“ oder „hat eine Jahresdurchschnittstemperatur“. Dagegen haben Graphalgorithmen wie PageRank oder Graph-Zentralität oft nur einen oder wenige Kantentypen. Es gibt zwar allgemeine Algorithmen, die auch auf Graphen mit mehreren Kantentypen anwendbar sind; zum Beispiel findet das SPARQL-Muster ?s1 ?p ?o . ?s2 ?p ?o . die ?s1 und ?s2, die ein bestimmtes ?o und eine Beziehung ?p gemeinsam haben, und bildet damit die Grundlage für ein Ähnlichkeitsmaß zwischen ihnen. Graphen haben im Allgemeinen keine festgelegte Form, können also jede beliebige Struktur annehmen, und aus Sicht der Speicherlatenz kann das eine Katastrophe sein. Früher habe ich einmal mit genau diesem SPARQL-Muster ein Programm gebaut, das 100 Jahre gebraucht hätte; nachdem ich die Datenstruktur neu gepackt und eine Approximation gefunden hatte, ließ es sich in unter 20 Minuten berechnen. Deshalb stehen Praktiker universellen Graph-Processing-Bibliotheken eher skeptisch gegenüber. Häufig gibt es Probleme, bei denen man in weniger Zeit, als man mit dem Build-System ringt, spezialisierten Code schreiben kann, der 1000-mal schneller ist.
      Wenn man trotzdem dem Trend folgen will: Auf arXiv gibt es derzeit jede Menge Paper zu Graph Neural Networks, die anderswo nicht ganz so stark gehypt werden. YOShInOn hat mir eine lange Liste von GNN-Papern zum Lesen zusammengestellt, aber ich habe nur ein paar überflogen. Es gibt viele Texte, die behaupten, sie seien auf die Textanalyseprobleme anwendbar, an denen ich arbeite, aber sie wirken nicht unbedingt besser als die Systeme, die YOShInOn und ich verwenden, deshalb habe ich es damit nicht eilig.
    • Für Probleme, die sich am besten mit Graphanalyse lösen lassen, wird weiterhin viel NetworkX verwendet, und mir gefällt die Developer Experience dieses Pakets wirklich sehr.

  • Wer mit Graphen und Machine Learning experimentieren möchte: Beim Durchsehen der aktuellen ArangoDB-Dokumentation habe ich gesehen, dass sie Integrationen mit mehreren Graphbibliotheken und Machine-Learning-Frameworks enthält: https://docs.arangodb.com/3.11/data-science/adapters/
    Es gab auch einige Jupyter-Notebooks zu Machine Learning auf Graphen: https://github.com/arangodb/interactive_tutorials#machine-learning
    Zu den Integrationszielen gehören NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, und PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/.

  • Gibt es jemanden, der mit Bazel vertraut ist und Hinweise zur Build-Anleitung geben kann? bazel build macht zwar irgendetwas, aber am Ende entstehen nur bazel-build und bazel-build, und ich sehe kein auffälliges Build-Artefakt.

    • In Bazel ist //... ungefähr wie das Target all bei make.
      Man kann es z. B. als bazel build //..., bazel test //..., bazel query //... verwenden. Der letzte Befehl listet meiner Erinnerung nach alle Targets auf.
    • Ergänzend zur Antwort oben: Man kann auch nur ein einzelnes Paket bauen. Zum Beispiel lässt sich mit bazel build //in_memory/connected_components:asynchronous_union_find asynchronous_union_find bauen.
      Allerdings ist das außerhalb des Kontexts einer cc_binary-Regel möglicherweise nicht besonders nützlich. Auf diese Weise kann man, ohne das gesamte Repository zu bauen, nur die Pakete bauen und verwenden, die man in einem anderen Projekt benötigt. Wenn man etwa nur den Header asynchronous_union_find.h verwenden möchte, fügt man die graph-mining-Bibliothek irgendwo in der WORKSPACE-Datei des Projekts per git_repository-Regel hinzu (siehe Beispiel WORKSPACE.bazel) und ergänzt in der cc_library-Regel in der BUILD-Datei des Projekts @graph-mining//in_memory/connected_components:asynchronous_union_find. Dann kann der Header anderswo eingebunden werden, und beim Build des Projekts werden nur dieses Paket und seine Abhängigkeiten gebaut, nicht die gesamte graph-mining-Bibliothek.
    • Ich dachte schon lange, dass ich mir Bazel irgendwann einmal ansehen sollte, und dieses „irgendwann“ war heute. Zur Installation scheint der empfohlene Weg zu sein, zuerst Bazelisk zu installieren, es dann in bazel umzubenennen und in einen Pfad wie /usr/local/bin/bazel zu legen.
      Als ich dann aber query ausführte, kam eine JDK-Warnung, und bei build schlug es mit WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE. fehl, weil Java fehlte. Ich habe ein paar Minuten gesucht, welches JDK/JRE ich verwenden soll, obwohl ich gar kein Java benutze, und konnte dann nicht mehr. Das heutige „irgendwann“ wurde also wieder auf einen anderen Tag verschoben. Es ist fast peinlich, wie sehr ich an cargo oder npm/yarn gewöhnt bin.
      Update: Dank https://sdkman.io/ läuft es. Am Ende war es doch nicht so schlimm.

  • Anfängerfrage: Könnte man diese Bibliothek als Kandidaten sehen, um sie mit Wrappern oder Erweiterungsbibliotheken zu integrieren und graphbasierte Clustering-Algorithmen an einem Ort zu bündeln? Vorausgesetzt, das ist nicht bereits der Fall.
    Oder gibt es schon ein Framework, das dieselbe Funktionalität besser anbietet? So etwas wie NetworkX?

  • Vielleicht bin ich der Zeit weit hinterher, aber hat das etwas mit Pregel zu tun?

    • Pregel ist ein System zur verteilten Graphverarbeitung, und das hier sieht für mich wie eine Bibliothek aus, die Graphen im Speicher eines einzelnen Rechners verarbeitet.

  • Beispiele wären wirklich hilfreich.

    • Dokumentation in irgendeiner Form wäre wirklich hilfreich.
    • Kommt bald. Wenn man in 12 Stunden noch einmal nachschaut, ist vermutlich etwas da.

  • Kann jemand erklären, wofür diese Bibliothek nützlich ist?

    • Man kann sie für Clustering verwenden. Ich habe den Korrelations-Clusterer daraus schon für Probleme eingesetzt, die sich als Graph aus Knoten mit einem Ähnlichkeitsmaß (diese Daten sind jenen Daten ähnlich) und starken Abstoßungsmerkmalen (diese Daten sind bekanntlich anders als jene Daten und dürfen daher niemals zusammengeführt werden) darstellen lassen.

  • Auf GitHub steht C, C++, Starland. Was ist Starland?

    • Starlark. Das ist die Sprache zur Konfiguration des Bazel-Build-Systems, und Bazel ist der Open-Source-Port von Googles internem Build-System Blaze. Starlark ist eine Teilmenge von Python.
    • Ich vermute, das ist ein Tippfehler und sollte Starlark heißen. Das ist die Sprache, die in Bazel-Build-Dateien verwendet wird.
      Bazel ist das hier verwendete Build-System.

  • Bei Graphalgorithmen wäre ein gewisses Maß an Standardisierung dringend nötig. Man denke an BLAS und LAPACK.

  • Ich hatte erwartet, dass es im wörtlichen Sinn ein Tool zum Mining statistischer Graphen für Anomalieerkennung ist.