Heim > Artikel > Technologie-Peripheriegeräte > Lernen und Nachdenken über Graph Computing
Gute Software wird nicht durch Programmanalyse und Fehlerprüfung gefunden, sondern wird von den richtigen Leuten erstellt.
Grafiken sind zu einem immer wichtigeren Rechenobjekt geworden. Die Grafikstruktur ist eine Abstraktion von Gruppenbeziehungen und kann umfangreiche Objekte und Beziehungen beschreiben. Der Kern der Graphenberechnung besteht darin, wie man Daten in eine Graphenstruktur modelliert und wie man die Lösung des Problems in ein Rechenproblem auf der Graphenstruktur umwandelt. Wenn das Problem eine Korrelationsanalyse beinhaltet, kann die Graphenberechnung oft die Lösung des Problems auf natürliche Weise herstellen ausgedrückt als eine Reihe von Operationen und Berechnungen an Graphstrukturen. Beispielsweise wird der PageRank-Algorithmus verwendet, der auf der Diagrammstruktur von Webseitenlinks basiert, um das Gewicht der Webseite zu ermitteln, das als Referenz für das Suchmaschinenranking verwendet wird. Die Benutzerverhaltensdaten der Diagrammstruktur werden verwendet, um genaue Informationen zu erhalten Gruppenpräferenzanalyse und personalisierte Produktempfehlungsergebnisse.
Graph Computing ist eine Technologie, die Dinge in der menschlichen Welt und die Beziehungen zwischen Dingen untersucht und sie beschreibt, charakterisiert, analysiert und berechnet. Der Graph hier ist „Graph“, nicht der Graph „Bild“, der aus der Graphentheorie in der Mathematik stammt.
Grafiken sind die flexibelste Verbindungsmethode und ermöglichen die uneingeschränkte Verbindung von Entitäten. Graph Computing ist nicht nur eine Technologie, sondern eine Möglichkeit, die Welt zu verstehen. Diagrammdaten können die Verbindungen zwischen Dingen gut beschreiben, einschließlich der Beschreibung der Richtung und Attribute der Verbindungen. Aus Sicht der Datenstruktur sind Diagramme ein nativer Ausdruck der Beziehungen zwischen Dingen. Bis zu einem gewissen Grad sollten relationale Datenbanken als Tabellendatenbanken bezeichnet werden, während Diagrammdatenbanken als relationale Datenbanken bezeichnet werden sollten. Im weitesten Sinne bezieht sich Graph Computing auf verschiedene Verarbeitungen basierend auf Graphdaten, einschließlich Graphdatenbanken.
Die Graph-Computing-Technologie löst die Probleme der geringen Effizienz und der hohen Kosten der damit verbundenen Abfragen in herkömmlichen Computermodi. Sie stellt die Beziehungen im Problembereich vollständig dar und verfügt über umfassende, effiziente und agile Datenanalysefunktionen:
Für die Graphberechnung sind Leistungskosten, Fehlertoleranzmechanismus und Skalierbarkeit sehr wichtig.
Graphenrechnen lässt sich auf baumstrukturierte Datenbanken in den 1970er und 1980er Jahren zurückführen, wie zum Beispiel LDM ( Logisches Datenmodell) usw. . Bis 2007 wurde die erste kommerzielle Graphdatenbank Neo4j eingerichtet, was den Eintritt des Graph Computing in eine Entwicklungsphase markierte.
Der eigentliche Beginn der Graph-Computing-Forschung ist, dass Google 2004 MapReduce entwickelte, ein Computermodell für die Parallelverarbeitung von Big Data. Die Einführung dieses Modells brachte einen enormen revolutionären Einfluss auf die Parallelverarbeitung von Big Data. Anschließend führte das Apache Hadoop-Team im Jahr 2006 das Hadoop Distributed File System (HDFS) und das neue Hadoop MapReduce-Framework ein. Im Jahr 2009 entwickelte das AMP Lab der University of California in Berkeley das Spark-System.
Seit 2010 haben Forschungsrichtungen im Bereich Graph Computing wie groß angelegte verteilte Architektur, multimodale Unterstützung und Design von Graph-Abfragesprachen nach und nach Aufmerksamkeit erregt. Google schlug Pregel vor, ein verteiltes Graph-Computing-System, das für die Eigenschaften von Graph-Algorithmen entwickelt wurde und dem BSP-Computing-Modell folgt. Anschließend schlug das CMU Select Laboratory GraphLab-Projektteam das GAS-Computing-Modell vor. . Obwohl Pregel und GraphLab beide Verarbeitungsframeworks für komplexe Berechnungen des maschinellen Lernens sind und für Iterationsberechnungen verwendet werden, gehen ihre Implementierungsmethoden unterschiedliche Wege: Pregel basiert auf einem Nachrichtenübermittlungsmechanismus für große Blöcke, und GraphLab basiert auf dem Speicherfreigabemechanismus einen tiefgreifenden Einfluss auf das spätere Design anderer Graph-Computing-Systeme.
Google hat im Mai 2012 das Konzept des Wissensgraphen vorgeschlagen, das eine neue Art der Verknüpfung von Informationen darstellt. Seine Grundeinheit ist das „Entitäts-Beziehungs-Entitäts“-Triplett, und Entitäten sind durch Beziehungen miteinander verbunden und bilden ein vernetztes Wissen Struktur. Der Kern der Erstellung von Wissensgraphen ist der Wissensschlussmechanismus von Computern, und Graph Computing bietet wichtige zugrunde liegende technische Unterstützung dafür.
Im Jahr 2015 öffnete sich mit dem rasanten Wachstum des Datenvolumens der Anwendungsmarkt schrittweise und die Nachfrage nach Skalierbarkeit und Effizienz von Graph-Computing-Systemen stieg weiter an. Die akademische und industrielle Forschung auf dem Gebiet des Graph-Computing in China hat damit begonnen, nach und nach eigene Graph-Computing-Systeme und -Plattformen zu entwickeln, wie beispielsweise Gemini der Tsinghua-Universität.
Mit der Entwicklung der Technologie der künstlichen Intelligenz haben in den letzten Jahren auch graphische neuronale Netze ihr Können in der Branche unter Beweis gestellt.
Das Framework des Graph-Computing folgt grundsätzlich dem BSP-Computing-Modell (Bulk Synchronous Parallell). Das einzigartige Merkmal des Massensynchronisationsmechanismus im BSP-Modus liegt in der Einführung des Superstep-Konzepts. Ein Berechnungsprozess besteht aus einer Reihe globaler Superschritte. Jeder Superschritt umfasst drei Phasen: parallele Berechnung (lokale Berechnung), globale Kommunikation (nicht lokale Datenkommunikation) und Zaunsynchronisierung (Warten auf das Ende des Kommunikationsverhaltens).
Der BSP-Modus weist die folgenden Merkmale auf:
Unterteilt Berechnungen nacheinander in Superschritte und vermeidet so effektiv Deadlocks;
Trennt Prozessoren und Router und betont die Trennung von Rechenaufgaben und Kommunikationsaufgaben, während Router nur Punkt-zu-Punkt-Nachrichtenübermittlung durchführen und bietet keine Funktionen wie Assemblieren, Kopieren und Senden, was nicht nur die spezifische Verbindungsnetzwerktopologie maskiert, sondern auch das Kommunikationsprotokoll vereinfacht
Übernehmen Sie den Synchronmodus, um eine globale Synchronisierung und eine steuerbare grobkörnige Ebene in der Hardware zu implementieren, um eng gekoppelte synchrone parallele Algorithmen auszuführen.
Einige repräsentative Graph-Computing-Frameworks sind wie folgt:
Der Graphalgorithmus bezieht sich auf eine einfache Methode, die bestimmte Eckpunkte und Kanten verwendet, um Antworten zu finden. Viele häufig verwendete Graphalgorithmen können für ungerichtete Graphen, gerichtete Graphen und Netzwerke verwendet werden. Für Diagrammdaten bilden Traversalalgorithmen (zuerst Tiefe/Breite) die Grundlage für andere Algorithmen. Zu den typischen Diagrammalgorithmen gehören PageRank, kürzester Pfad, verbundener Zweig, maximaler unabhängiger Satz, minimaler Spannbaum und Bayesian Belief Propagation. Der minimale Spannbaum eines Diagramms stellt häufig die niedrigsten Kosten oder minimalen Lebenskosten dar, und häufig werden der Prim-Algorithmus und der Kruskal-Algorithmus verwendet. Community Discovery, kürzester Pfad, topologische Sortierung und kritischer Pfad verfügen ebenfalls über entsprechende Algorithmen.
Graph-Algorithmen umfassen verschiedene Datenanalysetechnologien wie Suche, Matching, Klassifizierung und Auswertung. Sie können grob in zwei Kategorien aus der Algorithmusstrukturdimension unterteilt werden: durchquerungszentrierte Algorithmen und berechnungszentrierte Algorithmen. Traversierungszentrierte Algorithmen müssen den Graphen von bestimmten Eckpunkten aus auf eine bestimmte Weise durchlaufen, und es gibt eine große Menge an Direktzugriffen. Berechnungszentrierte Algorithmen erfordern eine große Anzahl von Operationen in einem Iterationszyklus und weisen eine relativ gute Datenlokalität auf.
Die Belastung durch die Berechnung von Graphen ist komplex und es gibt keine repräsentativste Belastung für die Berechnung von Graphen. Die Kanten, die die Eckpunkte verbinden, stellen nur einen kleinen Teil der unzähligen möglichen Verbindungen dar und sind äußerst unregelmäßig. Beim Graphenrechnen ist die räumlich-zeitliche Lokalität des Lesens und Schreibens schwer zu erfassen und die Bandbreitenbelegung schwer vorherzusagen.
Die meisten Algorithmen belegen möglicherweise weniger als 50 % der Speicherbandbreite. Was begrenzt die Nutzung der Speicherbandbreite? Der Prozessor muss Anweisungen erhalten, zwischen den Befehlsfenstern ist Platz und die Registeroperanden müssen warten, bis die Operanden verfügbar sind, und die zugehörigen Abhängigkeiten werden nicht freigegeben. Aufgrund der hohen Befehlstrefferrate kann die Parallelität auf Speicherebene verringert sein, was es schwierig macht, die Speicherbandbreite der Plattform vollständig auszunutzen. Ein niedriges Cache-Datennutzungsverhältnis bedeutet, dass es für Anwendungen schwierig ist, von der räumlichen Lokalität zu profitieren, und die Strategie zum Vorabrufen von Daten wird ineffektiv sein. Das Vorabrufen von Daten trägt im Allgemeinen zur Verbesserung der Leistung bei, erzeugt jedoch auch eine große Anzahl nutzloser Vorabrufvorgänge. Bei Anwendungen mit begrenzter Speicherbandbreite oder Cache-Kapazität kann das Vorabrufen von Daten zu einer gewissen Ressourcenverschwendung führen. Im Fall von Multi-Thread-Computing wird das Auslösen von Remote-Speicherzugriffen mit höherer Latenz auch die Vorteile von Multi-Threading zunichte machen.
Welcher Prozessorkern wird für Graph Computing benötigt? Im Allgemeinen wird eine Architektur mit vielen kleinen Rechenkernen und einer hohen Anzahl von Threads verwendet, die sich für die Verarbeitung großer Diagrammberechnungen eignet, für die herkömmliche Mehrkernprozessoren nicht geeignet sind. Bei der gleichzeitigen Berechnung mehrerer Diagramme gibt es zwei Strategien: gemeinsame Zuweisung und exklusive Zuweisung. Die Shared Allocation-Strategie bedeutet, dass jede der m Anfragen parallel mit n logischen Kernen verarbeitet wird und das Betriebssystem die Vermittlung verschiedener Anfragen auf den logischen Kernen verwaltet. Die exklusive Zuweisungsstrategie bezieht sich auf die Zuweisung von n/m logischen Kernen zu jeder Anforderung, sodass die logischen Kerne nicht zwischen Aufgaben wechseln müssen. Die exklusive Zuordnungsstrategie eignet sich besser für gleichzeitige Diagrammberechnungen und kann normalerweise die Gesamtlaufzeit für dieselben gleichzeitigen Anforderungen verkürzen. Die geringe Konkurrenz des Neuordnungscache kann der Grund dafür sein, dass die exklusive Strategie in gleichzeitigen Graph-Computing-Szenarien besser ist als die gemeinsame Strategie.
Was den durch die Diagrammberechnung verursachten Stromverbrauch betrifft, führen Laständerungen zu Schwankungen der Systemleistung und Spitzen und Täler können schwanken. Zunehmende gleichzeitige Aufgaben verändern das Spitzen-Tief-Verhältnis und erhöhen den Stromverbrauch. Im Allgemeinen verbrauchen berechnungszentrierte Algorithmen im Durchschnitt viel Energie pro Befehl, während durchlaufzentrierte Algorithmen in Bezug auf den Speicherstromverbrauch den gegenteiligen Effekt haben und berechnungszentrierte Algorithmen weniger Speicher verbrauchen. Der durchschnittliche Energieverbrauch ist gering, und das Gegenteil gilt für durchquerungszentrierte Algorithmen.
Die meisten auf Graph-Computing basierenden Anwendungen sind speicherbegrenzt, es gibt jedoch auch eine unzureichende Speicherauslastung, die durch Einschränkungen der Kernkomponenten verursacht wird. Genügend aktive Threads sorgen für gleichzeitigen Zugriff, was die Auslastung verbessern kann. Es werden mehr Threads benötigt, aber aufgrund des Ungleichgewichts zwischen den Threads können diese möglicherweise nicht effizient genutzt werden. Es muss eine skalierbarere Parallelstrategie bereitgestellt werden, um die Speichernutzung mit hoher Bandbreite von Mehrkernprozessoren zu optimieren. Der Stromverbrauch und das Energieverbrauchsverhalten unterscheiden sich von der Anweisungsperspektive und der Scheitelpunktberechnungsperspektive, was präzise Energieverwaltungsmethoden erfordert und umfangreiche Anpassungen möglicherweise nicht effektiv sind.
Basierend auf den Nutzungsszenarien und der Computerplattformarchitektur großer Graph-Computing-Systeme können sie in Einzel-Memory-Graph-Computing-Systeme und Einzel-Maschine-External-Memory-Graph-Computing-Systeme unterteilt werden und verteilte Speicher-Graph-Computing-Systeme und verteilte Speicher-Graph-Computing-Systeme.
Das Einzelmaschinen-Speicherdiagrammverarbeitungssystem ist ein Diagrammverarbeitungssystem, das in einer Einzelmaschinenumgebung ausgeführt wird und alle Diagrammdaten im Speicher puffert. Das eigenständige externe Speicherdiagrammverarbeitungssystem ist ein effizienter Diagrammalgorithmus, bei dem das Diagrammverarbeitungssystem in einer eigenständigen Umgebung ausgeführt wird und durch die Berechnung von Diagrammdaten kontinuierlich mit dem Speicher und der Festplatte interagiert. Das verteilte Speichersystem ist ein Diagrammverarbeitungssystem, das in einer verteilten Clusterumgebung ausgeführt wird und alle Diagrammdaten in den Speicher lädt. Das verteilte externe Speicher-Graph-Computing-System erweitert Einzelmaschinen-Out-of-Core-Systeme zu Clustern und kann Graphen mit Kanten in der Größenordnung von Billionen verarbeiten.
Das durch die Fusion von KI und Graph Computing erzeugte Graph Neural Network (GNN) ist derzeit ein sich schnell entwickelndes und wichtiges Feld. Wie lassen sich die Beziehungsdaten zwischen verschiedenen Entitäten mit neuronalen Netzen kombinieren? Das neuronale Netzwerk des Graphen nutzt das Repräsentationslernen. Durch die Struktur des Graphen wird jeder Knoten oder jede Kante zunächst durch einen Vektor dargestellt und dann mithilfe eines neuronalen Netzwerks weiterverarbeitet. Dies erweitert den Anwendungsbereich neuronaler Netzwerke und führt die Beziehung zwischen Entitäten in die KI-Verarbeitung ein.
Graphisches neuronales Netzwerk kann als Lernprozess für Graphenmerkmale angesehen werden, z. B. repräsentative Merkmale von Knoten oder repräsentative Merkmale auf Diagrammebene. Es verwendet im Allgemeinen die Attribute des Diagramms und die Struktur des Diagramms als Eingabe und gibt eine Reihe von aus aktualisierte Knotendarstellungen. Im Allgemeinen wird dieser Vorgang auch als Diagrammfiltervorgang bezeichnet. Durch die Diagrammfilterung werden Knotenfunktionen aktualisiert, die Struktur des Diagramms jedoch nicht geändert. Die Entwicklung graphischer neuronaler Netze basiert beispielsweise auf einer Faltungsverallgemeinerung der nichteuklidischen Distanz, die meisten GNNs basieren jedoch auf neuronalen Nachrichtenübermittlungsmethoden Übergangsalgorithmus, vorgeschlagen durch Analogie zum probabilistischen Denken in grafischen Modellen.
Ob es sich um eine Spektralmethode oder eine weltraumbasierte Idee handelt, das graphische neuronale Netzwerk kann endlich in einem auf Nachrichtenübermittlung basierenden Framework vereinheitlicht werden. Die Grundidee des GNN-Message-Passing-Frameworks besteht darin, dass jeder Knoten bei jeder Iteration die Informationen seiner Nachbarknoten aggregiert. Mit zunehmender Anzahl der Iterationen enthält jeder Knoten einen größeren Informationsbereich im Diagramm. Beispielsweise kann der zentrale Knoten nach k Iterationen die Informationen seiner k-Hop-Nachbarn erhalten. Die Schlüsselidee besteht darin, Knotendarstellungen basierend auf der Diagrammstruktur und bekannten Merkmalsinformationen zu generieren. GNN verwendet die Struktur- und Knotenmerkmalsinformationen im Diagramm, um Darstellungen mit tiefer Einbettung zu generieren, während die herkömmliche Methode zum Einbetten von Diagrammen nur die Strukturinformationen des Diagramms verwendet, um Ebeneneinbettungen durch Tabellensuche zu generieren.
7.1 GNN VS MLP/CNN/RNN
Knotennachbarn in Diagrammdaten weisen zwei Merkmale auf: Erstens ist die Anzahl unsicher, und zweitens ist die Reihenfolge so, dass MLP/CNN/RNN solche Nicht-Nachbarn nicht direkt verarbeiten kann. Europäische Daten können nur mit GNN modelliert werden. Tatsächlich kann GNN als allgemeineres Modell betrachtet werden. Beispielsweise entspricht RNN dem GNN in einem linearen Diagramm und Transformer entspricht dem GNN in einem vollständigen Diagramm.
7.2 GNN VS Graph Embedding
Viele Graph Embedding-Methoden sind vor GNN entstanden und werden häufig in der Vektorrückrufphase von Suchdiensten verwendet. Solche Methoden sind von Word2vec inspiriert, vom ursprünglichen Item2Vec bis hin zu Node2Vec Das Ausbalancieren von Homogenität und Struktur, die Verbesserung von MetaPath2Vec basierend auf der Heterogenität des Diagramms und die Einführung von Attributdaten zur Linderung der Spärlichkeit von Verhaltensdaten folgen alle dem Skip-Gram-Paradigma.
Im Vergleich zu diesen Methoden kann GNN Ende-zu-Ende basierend auf der Zielaufgabe trainiert werden, während das Einbetten von Diagrammen eher einem Vortraining ähnelt. Das Einbetten, das es erlernt, hängt nicht unbedingt mit der Zielaufgabe zusammen, insbesondere in Geschäftsszenarien Bei großen Stichprobengrößen ist die Einbettung durch End-to-End-Training effektiver als die Einbettung durch Vortraining.
Die hierarchische Netzwerkstruktur von GNN lässt sich leicht mit anderen Deep-Learning-Technologien wie GCN+Attentinotallow=GAT kombinieren. GNN kann auf induktive Aufgaben angewendet werden, d. h. wenn sich die Struktur des Diagramms ändert und einige neue Knoten hinzugefügt werden. Wenn es sich um eine Methode zur Einbettung von Diagrammen handelt, muss das Modell neu trainiert werden, und GNN kann eine dem GraphSage Node ähnliche Methode verwenden -Wise Sampling, wobei das bereits trainierte Modell direkt neue Knoten ableitet, und im Nachrichtenübermittlungsprozess können verschiedene Funktionen verwendet werden.
7.3 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss
Feature Concat bedeutet, Features zusammenzufügen und dann Attributassoziationsinformationen erster Ordnung durch Feature-Schnittpunkt zu lernen. Collaborative Filtering kann auch Verhaltenskorrelationsinformationen erster Ordnung durch historisches Benutzerverhalten lernen. Näherungsverlust bedeutet, der Verlustfunktion reguläre Terme hinzuzufügen, um benachbarte Knoten ähnlicher zu machen. Einerseits ist dies jedoch eine implizite Methode. Wenn Sie andererseits sicherstellen möchten, dass Ähnlichkeitsbeziehungen höherer Ordnung gelernt werden, müssen Sie hinzufügen komplexer Der reguläre Term der K-Ordnung ist auch einer der Ausgangspunkte, als GCN vorgeschlagen wurde. Im Vergleich zu diesen drei Methoden kann GNN durch Stapeln mehrerer Schichten explizit Korrelationsinformationen höherer Ordnung lernen.
Beim Entwurf von graphischen neuronalen Netzen muss eine Schlüsselbedingung erfüllt sein, nämlich Permutationsinvarianz oder Permutationsäquivarianz. Das heißt, wenn die entworfene Funktion Diagrammdaten verarbeitet, wird sie nicht von der Reihenfolge der Knoten beeinflusst Die Reihenfolge der Ausgabe der sequentiellen Transformationsdomäne ist konsistent.
Graph ist die flexibelste Verbindungsmethode, mit der Entitäten ohne Einschränkungen verbunden werden können. Graph Computing ist ein Bereich, der untersucht, wie Diagrammdaten in großen Datenmengen effizient berechnet, gespeichert und verwaltet werden. Es kann auf eine Vielzahl von Geschäftsszenarien angewendet werden, wie z. B. Kapitalmarktrisikomanagement, Life-Science-Forschung, Gesundheitsversorgung und Überwachung und Reaktion auf Verkehrsunfälle, intelligentes Infrastrukturmanagement usw. Graph Computing, das große Datenmengen effizient verarbeitet, kann die Entwicklung neuer Anwendungsbereiche wie die Analyse sozialer Netzwerke, die semantische Webanalyse, die Analyse biologischer Informationsnetzwerke und die Verarbeitung natürlicher Sprache fördern.
„Graph Computing of Artificial Intelligence“, Tsinghua University Institute of Artificial Intelligence, Beijing Zhiyuan Institute of Artificial Intelligence, Tsinghua-Academy of Engineering Knowledge Intelligence Joint Research Center, 2019-2
https : //www.php.cn/link/c9e5c2b59d98488fe1070e744041ea0e
https://www.php.cn/link/d40d35b3063c11244fbf38e9b55074be
https://www.php.cn / link/315f006f691ef2e689125614ea22cc61
https://www.php.cn/link/51d1cd3a02276948f566e6ea0a7d78cb
Das obige ist der detaillierte Inhalt vonLernen und Nachdenken über Graph Computing. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!