Ein neuer Weg, KI auf Graphdaten ohne Überwachung zu trainieren

```html ``` Autoren: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ABSTRAKT Der Reichtum an Inhalten in verschiedenen Informationsnetzwerken wie sozialen Netzwerken und Kommunikationsnetzwerken bietet ein beispielloses Potenzial für das Erlernen hochwertiger, ausdrucksstarker Repräsentationen ohne externe Aufsicht. Diese Arbeit untersucht, wie die Fülle von Informationen aus graphenstrukturierten Daten in einem unbeaufsichtigten Verfahren im Einbettungsraum erhalten und extrahiert werden kann. Zu diesem Zweck schlagen wir ein neuartiges Konzept vor, die grafische gegenseitige Information (GMI), um die Korrelation zwischen Eingabegraphen und High-Level-Darstellungen zu messen. GMI verallgemeinert die Idee konventioneller Berechnungen der gegenseitigen Information vom Vektorraum auf den Graphbereich, in dem die Messung der gegenseitigen Information aus zwei Aspekten von Knotenmerkmalen und topologischer Struktur unerlässlich ist. GMI weist mehrere Vorteile auf: Erstens ist sie invariant gegenüber isomorphen Transformationen von Eingabegraphen – eine unvermeidliche Einschränkung in vielen bestehenden Algorithmen zum Erlernen von Graphrepräsentationen; außerdem kann sie effizient durch aktuelle Methoden zur Schätzung der gegenseitigen Information, wie MINE, geschätzt und maximiert werden; schließlich bestätigt unsere theoretische Analyse ihre Korrektheit und Rationalität. Mithilfe von GMI entwickeln wir ein unbeaufsichtigtes Lernmodell, das durch Maximierung von GMI zwischen der Eingabe und Ausgabe eines Graph-Neural-Encoders trainiert wird. Umfangreiche Experimente zur transdiktiven und induktiven Knotenklassifizierung und Link-Vorhersage zeigen, dass unsere Methode die State-of-the-Art-unbeaufsichtigten Gegenstücke übertrifft und manchmal sogar die Leistung von überwachten Methoden übertrifft. 1 EINFÜHRUNG Um eine zuverlässige quantitative Analyse für verschiedene Informationsnetzwerke zu erreichen, ist das Lernen hochwertiger Repräsentationen für graphenstrukturierte Daten zu einem der faszinierendsten aktuellen Themen geworden. Neuere Methoden, die auf dieses Ziel abzielen und üblicherweise als Graph Neural Networks (GNNs) kategorisiert werden, haben bemerkenswerte Fortschritte bei einer großen Anzahl von Lernaufgaben erzielt, wie z. B. Knotenklassifizierung [ , , ], Link-Vorhersage [ , , ], Graph-Alignment [ , , ], Molekulargenerierung [ , , ], um nur einige zu nennen. Trotz fruchtbarer Fortschritte erfordert das Training von GNNs in bestehenden Ansätzen normalerweise eine gewisse Form der Überwachung. Zweifellos sind die Beschriftungsinformationen teuer zu beschaffen – manuelle Annotation oder Bezahlung der Erlaubnis – und aufgrund der Datenschutzrichtlinien sogar unmöglich zu erhalten. Ganz zu schweigen davon, dass die Zuverlässigkeit der gegebenen Labels manchmal fraglich ist. Daher ist es für viele praktische Fälle unerlässlich, hochwertige Graphrepräsentationen ohne Überwachung zu erzielen, was die Studie dieser Arbeit motiviert. 35 42 50 26 27 49 12 19 43 4 5 46 Durch sorgfältige Prüfung unserer gesammelten graphenstrukturierten Daten stellen wir fest, dass sie im Allgemeinen aus verschiedenen Quellen stammen, wie z. B. sozialen Netzwerken, Zitationsnetzwerken und Kommunikationsnetzwerken, in denen eine gewaltige Menge an Inhalts- und Verknügungsinformationen vorhanden ist. Daten auf vielen sozialen Plattformen wie Twitter, Flickr und Facebook enthalten beispielsweise Merkmale von Benutzern, grundlegende persönliche Details, Texte, Bilder, IP, und ihre Beziehungen, Kauf desselben Artikels, Freundschaft. Diese reichhaltigen Inhaltsdaten reichen aus, um nachfolgende Mining-Aufgaben ohne zusätzliche Anleitung zu unterstützen: Wenn zwei Entitäten extreme Ähnlichkeiten in ihren Merkmalen aufweisen, besteht eine hohe Wahrscheinlichkeit für eine Verbindung zwischen ihnen (Link-Vorhersage), und sie gehören wahrscheinlich zur selben Kategorie (Klassifizierung); wenn zwei Entitäten beide zu derselben Entität verlinken, haben sie wahrscheinlich ähnliche Merkmale (Empfehlung). In diesem Sinne erleichtert das Bewahren und Extrahieren so vieler Informationen wie möglich aus Informationsnetzwerken in den Einbettungsraum das Erlernen hochwertiger, ausdrucksstarker Repräsentationen, die eine wünschenswerte Leistung bei Mining-Aufgaben ohne jegliche Überwachung aufweisen. Das unbeaufsichtigte Lernen von Graphrepräsentationen ist in vielen Fällen aufgrund der Freiheit von Labels eine günstigere Wahl, insbesondere wenn wir die Vorteile großer Mengen unbeschrifteter Daten in freier Wildbahn nutzen wollen. z. B. z. B. Um die reichen Informationen in Graphen vollständig zu nutzen, führen wir in dieser Arbeit Graph-Embedding basierend auf der Maximierung der gegenseitigen Information (MI) durch, inspiriert vom empirischen Erfolg der Deep-Info-Max-Methode [ ], die auf Bildern operiert. Um nützliche Repräsentationen zu entdecken, trainiert Deep InfoMax den Encoder, um die MI zwischen seinen Eingaben ( , den Bildern) und Ausgaben ( , den versteckten Vektoren) zu maximieren. Bei der Betrachtung von Deep InfoMax im Graphbereich ist der erste Schritt, wie man MI zwischen Graphen und versteckten Vektoren definiert, während die Topologie von Graphen komplizierter ist als die von Bildern (siehe Abbildung Eine der Herausforderungen besteht darin, sicherzustellen, dass die MI-Funktion zwischen den versteckten Repräsentationen jedes Knotens und seinen benachbarten Eingabemerkmalen die symmetrische Eigenschaft erfüllt oder äquivalent, invariant gegenüber Permutationen der Nachbarschaften ist. Als eine der letzten Arbeiten, die MI berücksichtigte, bettet Deep Graph Infomax (DGI) [ ] einen Eingabegraphen und einen entsprechenden korrumpierten Graphen ein, fasst dann den Eingabegraphen über eine Lesefunktion zu einem Vektor zusammen und maximiert schließlich die MI zwischen diesem zusammenfassenden Vektor und den versteckten Repräsentationen, indem der Eingabegraph (positives Beispiel) vom korrumpierten Graphen (negatives Beispiel) diskriminiert wird. Abbildung gibt einen leicht verständlichen Überblick über DGI. Die Maximierung dieser Art von MI erwies sich als äquivalent zur Maximierung der MI zwischen den eingegebenen Knoteneigenschaften und den versteckten Repräsentationen, aber diese Äquivalenz gilt unter mehreren voreingestellten Bedingungen, , die Lesefunktion sollte injektiv sein, was in realen Fällen noch zu eingeschränkt erscheint. Selbst wenn wir die Existenz einer injektiven Lesefunktion durch bestimmtes Design garantieren können, die in DeepSets [ ] verwendete, wird die Injektivitätsfähigkeit der Lesefunktion auch davon beeinflusst, wie ihre Parameter trainiert werden. Das heißt, dass eine ursprünglich-injektive Funktion das Risiko birgt, nicht-injektiv zu werden, wenn sie ohne externe Überwachung trainiert wird. Und wenn die Lesefunktion nicht injektiv ist, verringert sich die im zusammenfassenden Vektor enthaltene Eingabegraphinformation mit zunehmender Größe des Graphen. Darüber hinaus bleibt DGI bei einer grobkörnigen MI-Maximierung auf Graph-/Patch-Ebene. Daher gibt es keine Garantie dafür, dass der Encoder ausreichende Informationen aus den Eingabedaten destillieren kann, da er versteckte Repräsentationen nie elaboriert mit ihren ursprünglichen Eingaben korreliert. 20 d. h. d. h. 1). 41 1 z. B. z. B. 47 In dieser Arbeit schlagen wir einen direkteren Weg vor, MI in Bezug auf grafische Strukturen zu betrachten, ohne eine Lesefunktion und eine Korruptionsfunktion zu verwenden. Wir leiten MI direkt ab, indem wir die Eingabe ( , den Teilgraphen, der die Eingabenachbarschaft umfasst) und die Ausgabe ( , die versteckte Repräsentation jedes Knotens) des Encoders vergleichen. Und interessanterweise zeigen unsere theoretischen Ableitungen, dass die direkt formulierte MI in eine gewichtete Summe lokaler MIs zwischen jedem Nachbarschaftsmerkmal und dem versteckten Vektor zerlegt werden kann. Auf diese Weise haben wir die Eingabemerkmale zerlegt und die MI-Berechnung handhabbar gemacht. Darüber hinaus kann diese Form von MI die symmetrische Eigenschaft leicht erfüllen, wenn wir die Werte der Gewichte anpassen. Weitere Einzelheiten finden Sie in § Da die obige MI hauptsächlich auf der Ebene von Knoteneigenschaften gemessen wird, bezeichnen wir sie als Feature Mutual Information (FMI). d. h. d. h. 3.1. Zwei verbleibende Probleme bezüglich FMI: die kombinierenden Gewichte sind immer noch unbekannt und sie berücksichtigt die Topologie ( , die Kantenmerkmale) nicht. Um diese beiden Probleme weiter anzugehen, definieren wir unsere grafische gegenseitige Information (GMI)-Messung basierend auf FMI. Insbesondere weist GMI eine intuitive Wertzuweisung zu, indem die Gewichte in FMI gleich der Nähe jedes Nachbarn zum Zielknoten im Repräsentationsraum gesetzt werden. Um die Topologieinformationen zu erhalten, korreliert GMI diese Gewichte über einen zusätzlichen gegenseitigen Informationsterm weiter mit den Eingabekantenmerkmalen. Das resultierende GMI ist topologisch invariant und auch mit Mutual Information Neural Estimation (MINE) [ berechenbar. Die wichtigsten Beiträge unserer Arbeit sind: 1. 2. d. h. [2] • : Wir verallgemeinern die konventionelle MI-Schätzung auf den Graphbereich und schlagen dementsprechend ein neues Konzept der grafischen gegenseitigen Information (GMI) vor. GMI ist frei von dem Konzepte potenziellen Risiko, das durch die Lesefunktion verursacht wird, da es MI zwischen Eingabegraphen und High-Level-Embeddings in einem direkten Muster betrachtet. • : Durch unsere theoretische Analyse geben wir eine handhabbare und berechenbare Form von GMI an, die die Algorithmen gesamte GMI in eine gewichtete Summe lokaler MIs zerlegt. Mithilfe der MINE-Methode kann die GMI-Maximierung auf Knotenebene leicht erreicht werden. • : Wir überprüfen die Wirksamkeit von GMI bei mehreren gängigen Knotenklassifizierungs- und Link-Vorhersageaufgaben, einschließlich transdiktiver und induktiver Aufgaben. Die Experimente zeigen, dass unsere Methode auf einer Vielzahl von Benchmarks vielversprechende Leistungen erbringt und manchmal sogar die Leistung von überwachten Gegenstücken übertrifft. Experimentelle Ergebnisse 2 VERWANDTE ARBEITEN Im Einklang mit dem Fokus unserer Arbeit geben wir einen kurzen Überblick über frühere Arbeiten in den folgenden zwei Bereichen: Schätzung der gegenseitigen Information und neuronale Netze zum Erlernen von Repräsentationen über Graphen. 1. 2. . Da das InfoMax-Prinzip [ ] die Maximierung von MI zwischen den Ein- und Ausgaben von neuronalen Netzen befürwortet, versuchen viele Methoden wie ICA-Algorithmen [ , ], die Idee von MI beim unbeaufsichtigten Merkmalslernen anzuwenden. Dennoch können diese Methoden aufgrund der Schwierigkeit bei der Berechnung von MI zwischen hochdimensionalen kontinuierlichen Variablen nicht leicht auf tiefe neuronale Netze verallgemeinert werden. Glücklicherweise macht Mutual Information Neural Estimation (MINE) [ ] die Schätzung von MI in tiefen neuronalen Netzen möglich, indem ein Statistiknetzwerk als Klassifikator trainiert wird, um Stichproben aus der gemeinsamen Verteilung und dem Produkt der Randverteilungen zweier Zufallsvariablen zu unterscheiden. Speziell verwendet MINE die exakte KL-basierte Formulierung von MI, während eine Nicht-KL-Alternative, die Jensen-Shannon-Divergenz (JSD) [ ], ohne die Sorge um den genauen Wert von MI verwendet werden kann. Schätzung der gegenseitigen Information 3 1 21 2 30 . Mit der rasanten Entwicklung von Graph Neural Networks (GNNs) wurden in den letzten Jahren eine Vielzahl von Algorithmen zum Erlernen von Graphrepräsentationen auf Basis von GNNs vorgeschlagen, die eine stärkere Leistung als traditionelle Random-Walk-basierte und Faktorisierungs-basierte Embedding-Ansätze [ , , , , ] erzielen. Typischerweise können diese Methoden in überwachte und unbeaufsichtigte Kategorien unterteilt werden. Unter ihnen gibt es eine reiche Literatur über überwachtes Lernen von Repräsentationen über Graphen [ , , , , ]. Trotz ihrer Unterschiede in der Netzwerkarchitektur erzielen sie empirische Erfolge mit Hilfe von Labels, die in realistischen Szenarien oft nicht zugänglich sind. In diesem Fall haben unbeaufsichtigte Graphlernmethoden [ , , ] ein breiteres Anwendungspotenzial. Die bekannte Methode ist GraphSAGE [ ], ein induktiver Rahmen zum Trainieren von GNNs durch ein Random-Walk-basiertes Ziel in seinem unbeaufsichtigten Setting. Und kürzlich wendet DGI [ ] die Idee der MI-Maximierung auf den Graphbereich an und erzielt starke Leistung in einem unbeaufsichtigten Muster. DGI implementiert jedoch eine grobkörnige Maximierung ( , Maximierung von MI auf Graph-/Patch-Ebene), was es schwierig macht, die feinen Informationen im Eingabegraphen zu bewahren. Außerdem scheint die Bedingung, die der in DGI verwendeten Lesefunktion auferlegt wird, in realen Fällen übermäßig eingeschränkt zu sein. Im Gegensatz dazu konzentrieren wir uns darauf, die Einschränkung der Lesefunktion aufzuheben und die grafische gegenseitige Information auf Knotenebene zu erreichen, indem wir MI zwischen Eingaben und Ausgaben des Encoders direkt maximieren. Repräsentationen, die von unserer Methode abgeleitet werden, sind raffinierter bei der Erhaltung von Eingabegraphinformationen, was ihr Potenzial für nachfolgende Graph-Mining-Aufgaben wie Knotenklassifizierung, Link-Vorhersage und Empfehlung sicherstellt. Neuronale Netze für das Lernen von Graphrepräsentationen 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 d. h. 3 GRAFISCHE GEGENSEITIGE INFORMATION: DEFINITION UND MAXIMIERUNG Bevor wir weiter fortfahren, stellen wir zunächst die in dieser Arbeit verwendeten vorläufigen Konzepte vor. Sei G = (V, E) ein Graph mit Knoten ∈ V und Kanten = ( , ) ∈ E. Die Knoteneigenschaften, mit angenommener empirischer Wahrscheinlichkeitsverteilung P, werden durch ∈ N vi eij vi vj X R × = { 1, · · · , } gegeben, wobei ∈ R die Eigenschaft für den Knoten bezeichnet. Die Adjazenzmatrix ∈ R × stellt Kantenverbindungen dar, wobei , die mit der Kante assoziiert ist, eine reelle Zahl oder ein mehrdimensionaler Vektor1 sein kann. N D x x N xi D vi A N N Aij eij Das Ziel des Lernens von Graphrepräsentationen ist es, einen Encoder : R × × R × → R × ′ zu lernen, so dass die versteckten Vektoren = { 1, · · · , } = ( , ) hochwertige Repräsentationen für alle Knoten anzeigen. Der Kodierungsprozess kann in einer knotenweisen Form umgeschrieben werden. f N D N N N D H h hN f X A Um dies zu zeigen, definieren wir und für den Knoten als die Eigenschaften seiner Nachbarn bzw. die entsprechende Adjazenzmatrix Xi Ai i bedingt durch die Nachbarn. Insbesondere umfasst alle k-Hop-Nachbarn von mit ≤ , wenn der Encoder ein -Schicht-GNN ist, und es enthält den Knoten selbst, wenn wir Selbstschleifen in der Adjazenzmatrix weiter hinzufügen. Hier nennen wir den Teilgraphen, der von und erweitert wird, einen für den Knoten , bezeichnet als G . Mit der Definition des Support-Graphen wird die Kodierung für jeden Knoten zu = (G ) = ( , ). Xi vi k l f l i Xi Ai Support-Graphen i i hi f i f Xi Ai In Deep InfoMax [ ] ist das Trainingsziel des Encoders die Maximierung der MI zwischen seinen Eingaben und Ausgaben. Die MI wird geschätzt, indem ein Statistiknetzwerk als Diskriminator verwendet wird, um Stichproben zu klassifizieren, die aus der gemeinsamen Verteilung stammen, und die aus dem Produkt der Randverteilungen stammen. Natürlich sollten wir beim Anpassen der Idee von Deep InfoMax an Graphen die MI zwischen der Repräsentation und dem Support-Graphen G für jeden Knoten maximieren. Wir bezeichnen solche grafische MI als ( ; G ). Es ist jedoch nicht trivial, I (hi ; Gi ) zu definieren. Die Schwierigkeiten sind: Schwierigkeiten bei der Definition der grafischen gegenseitigen Information. 20 hi i I hi i • Die grafische MI sollte bezüglich des Knotenindex invariant sein. Mit anderen Worten, wir sollten haben ( ; G ) = ( ; G′ ), wenn G und G′ zueinander isomorph sind. I hi i I hi i i i • Wenn wir die MINE-Methode für die MI-Berechnung verwenden, akzeptiert der Diskriminator in MINE nur Eingaben einer festen Größe. Dies ist für G noch nicht durchführbar, da verschiedene G normalerweise unterschiedliche Anzahlen von Knoten enthalten und somit unterschiedliche Größen haben. i i Um das Problem der Definition der grafischen gegenseitigen Information zu umgehen, beginnt dieser Abschnitt mit der Einführung des Konzepts der Feature Mutual Information (FMI), das sich nur auf Knoteneigenschaften stützt. Auf der Grundlage der Inspiration aus der Zerlegung von FMI definieren wir dann die Graphical Mutual Information (GMI), die sowohl die Knoteneigenschaften als auch 3.1 Feature Mutual Information Wir bezeichnen die empirische Wahrscheinlichkeitsverteilung der Knoteneigenschaften als ( ), die Wahrscheinlichkeit von als ( ) und die gemeinsame Verteilung als ( , ). Nach der Informationstheorie ist die MI zwischen und definiert als Xi p Xi hi p hi p hi Xi hi Xi Interessanterweise haben wir den folgenden Satz zur Zerlegung der gegenseitigen Information zur Berechnung von ( ; ). I hi Xi Theorem 1 (Zerlegung der gegenseitigen Information). ( | ) ( ; ) Wenn die bedingte Wahrscheinlichkeit p hi Xi multiplikativ ist (siehe die Definition von multiplikativ in [ ]), kann die globale gegenseitige Information I 36 hi Xi definiert in Gl. (1) als gewichtete Summe lokaler MIs zerlegt werden, nämlich ≤ ≤ 1 wobei x j der j-te Nachbar des Knotens i ist, in die Anzahl aller Elemente in Xi ist und das Gewicht wij erfüllt 1 wij für jedes j. Um das obige Theorem zu beweisen, führen wir zunächst zwei Lemmata und eine Definition ein. Lemma 1. Für beliebige Zufallsvariablen X, Y und Z gilt Mit der Zerlegung in Theorem können wir die rechte Seite von Gl. über MINE berechnen, da die Eingaben für den Diskriminator jetzt die Paare ( , ) sind, deren Größe immer gleich bleibt ( , ′-mal- ). Außerdem können wir die Gewichte anpassen, um die isomorphen Transformationen von Eingabegraphen zu reflektieren. Wenn beispielsweise nur Nachbarn erster Ordnung des Knotens enthält, führt die Festlegung aller Gewichte auf identisch zu derselben MI für die Eingabeknoten in unterschiedlicher Reihenfolge. 1 (2) hi xj d. h. D D Xi i Trotz einiger Vorteile der Zerlegung ist es schwierig, die genauen Werte der Gewichte zu charakterisieren, da sie sich auf die Werte von ( ; ) und ihre zugrunde liegenden Wahrscheinlichkeitsverteilungen beziehen. I hi xj Ein trivialer Weg ist, alle Gewichte auf zu setzen, dann ist die Maximierung der rechten Seite von Gl. äquivalent zur Maximierung der unteren Schranke von ( ; ), wodurch die wahre FMI bis zu einem gewissen Grad auch maximiert wird. Zusätzlich zu dieser Methode bieten wir eine weiter verbesserte Lösung an, indem wir die Gewichte als trainierbare Aufmerksamkeiten betrachten, was das Thema im nächsten Unterabschnitt ist. 1 (2) I hi Xi Inspiriert von der Zerlegung in Theorem versuchen wir, trainierbare Gewichte aus dem anderen Aspekt von Graphen ( , 3.2 Topologie-bewusste gegenseitige Information 1, d. h. topologische Sicht) zu konstruieren, damit die Werte von flexibler sein und die inhärente Eigenschaft von Graphen erfassen können. Schließlich leiten wir die Definition der grafischen gegenseitigen Information (GMI) ab. wij Definition 2 (Grafische gegenseitige Information). G = ( , ) Die MI zwischen dem versteckten Vektor h und seinem Support-Graphen X A ist definiert als wobei die Definitionen von xj und in wie in Theorem 1 sind, aij das Kantengewicht/Merkmal in der Adjazenzmatrix A ist und σ (·) eine Sigmoidfunktion ist. Intuitiv misst das Gewicht wij im ersten Term von Gl. (10) den in Experimenten behandelten ungewichteten Graphen. Formal berechnen wir I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) Durch Maximierung von I (hi ; Gi ) mit der Summe von Gl. (11) und Gl. (12) über alle versteckten Vektoren H gelangen wir zu unserer vollständigen Zielfunktion für den Beitrag einer lokalen MI zur globalen. Wir implementieren den Beitrag von I (hi ; xj ) durch die Ähnlichkeit zwischen den Repräsentationen hi und hj (d. h. wij = σ (hThj )). Mittlerweile maximiert der Term I (wij ; aij ) MI zwischen wij und dem Kantengewicht/Merkmal des Eingabegraphen (d. h. aij ), um wij zu zwingen, topologischen Beziehungen zu entsprechen. In diesem Sinne ist der Beitragswert konsistent mit der Nähe in der topologischen Struktur, was allgemein als Tatsache akzeptiert wird, dass wij größer sein könnte, wenn Knoten j "näher" an Knoten i ist und umgekehrt. Diese Strategie kompensiert den Nachteil, dass FMI sich nur auf Knoteneigenschaften konzentriert und lokale MIs adaptiv zur globalen beiträgt. Um die Idee der Aufmerksamkeit in dieser Strategie besser zu verstehen, können Sie sich auf die auf Aufmerksamkeit basierende GCN [40] beziehen. Beachten Sie, dass die Definition von Gl. (10) für allgemeine Fälle anwendbar ist. Für bestimmte spezifische Situationen können wir Gl. (10) zur Effizienz leicht modifizieren. Beispielsweise können wir bei ungewichteten Graphen (d. h. der Kantenwert ist 1, wenn verbunden, und sonst 0) den zweiten MI-Term I (wij ; aij ) durch einen negativen Kreuzentropieverlust ersetzen. Die Minimierung der Kreuzentropie trägt ebenfalls zur MI-Maximierung bei und ermöglicht eine effizientere Berechnung. Weitere Einzelheiten finden Sie im nächsten Abschnitt. Insgesamt ergeben sich aus der Definition von Gl. (10) mehrere Vorteile. Erstens ist diese Art von MI invariant gegenüber der isomorphen Transformation von Eingabegraphen. Zweitens ist sie rechnerisch machbar, da jede Komponente auf der rechten Seite von MINE geschätzt werden kann. Wichtiger ist, dass GMI leistungsfähiger als DGI bei der Erfassung ursprünglicher Eingabeinformationen ist, da es eine explizite Korrelation zwischen versteckten Vektoren und Eingabemerkmalen von Knoten und Kanten auf feinkörniger Knotenebene gibt. 3.3 Maximierung von GMI Nun maximieren wir die rechte Seite von Gl. direkt mit Hilfe von MINE. Beachten Sie, dass MINE eine untere Schranke für MI mit der Donsker-Varadhan (DV) [ -Darstellung der KL-Divergenz zwischen der gemeinsamen Verteilung und dem Produkt der Randverteilungen schätzt. Da wir uns mehr auf die Maximierung von MI als auf die Ermittlung seines spezifischen Wertes konzentrieren, können andere Nicht-KL-Alternativen wie der Jensen-Shannon-MI-Schätzer (JSD) [ ] und der Noise-Contrastive-Schätzer (infoNCE) [ ] verwendet werden, um ihn zu ersetzen. Basierend auf den experimentellen Ergebnissen und Analysen in [ ] greifen wir aus Gründen der Effektivität und Effizienz auf den JSD-Schätzer zurück, da der infoNCE-Schätzer empfindlich auf negative Abtaststrategien (die Anzahl der negativen Stichproben) reagiert und somit für große Datensätze mit verfügbarem Festplattenspeicher zu einem Engpass werden kann. Im Gegensatz dazu ist der JSD-Schätzer unempfindlich gegenüber negativen Abtaststrategien und seine respektable Leistung bei vielen Aufgaben macht ihn für unsere Aufgabe besser geeignet. Insbesondere berechnen wir ( ; ) im ersten Term von Gl. mit (10) [10] 30 31 20 I hi xj (10) wobei D : × ′ → R ein Diskriminator ist, der durch ein neuronales Netz mit dem Parameter konstruiert wird. ist eine negative Stichprobe aus P = P, und ( ) = (1 + ) bezeichnet die Soft-Plus-Funktion. w D D w x j sp x loд ex Wie in § erwähnt, maximieren wir ( ; ) durch Berechnung seiner Kreuzentropie anstelle der Verwendung des JSD-Schätzers, da die in Experimenten behandelten Graphen unbewertet sind. Formal berechnen wir 3.2 I wij aij Durch Maximierung von I (hi ; Gi ) mit der Summe von Gl. (11) und Gl. (12) über alle versteckten Vektoren H gelangen wir zu unserer vollständigen Zielfunktion für die GMI-Optimierung. Außerdem können wir zusätzliche Gewichtungsparameter hinzufügen, um Gl. (11) und (12) für mehr Flexibilität auszugleichen. 4 EXPERIMENTE In diesem Abschnitt bewerten wir empirisch die Leistung von GMI bei zwei gängigen Aufgaben: Knotenklassifizierung (transduktiv und induktiv) und Link-Vorhersage. Ein zusätzlicher, relativ fairer Vergleich zwischen GMI und zwei anderen unbeaufsichtigten Algorithmen (EP-B und DGI) zeigt seine Wirksamkeit weiter. Außerdem liefern wir die Visualisierung von t-SNE-Plots und analysieren den Einfluss der Modelltiefe. 4.1 Datensätze Um die Qualität unseres Ansatzes bei jeder Aufgabe zu bewerten, übernehmen wir 4 oder 5 gängige Benchmark-Datensätze aus früheren Arbeiten [ , , Detaillierte Statistiken sind in Tabelle aufgeführt. 16 25 41]. 1 Bei der Klassifizierungsaufgabe sind Cora, Citeseer und PubMed [ ]2 Zitationsnetzwerke, in denen Knoten Dokumenten entsprechen und Kanten Zitationen darstellen. Jedes Dokument ist mit einem Bag-of-Words-Repräsentationsvektor verbunden und gehört zu einer der vordefinierten Klassen. Dem transdiktiven Setup in [ , ] folgend, wird das Training auf allen Knoten durchgeführt und 1000 Testknoten werden zur Auswertung verwendet. Reddit3 ist ein großes soziales Netzwerk, das aus zahlreichen miteinander verbundenen Reddit-Posts besteht, die im September 2014 erstellt wurden [ ]. Posts werden als Knoten behandelt und Kanten bedeuten, dass derselbe Benutzer kommentiert hat. 38 25 41 16 ![ Tabelle 1: Statistiken der in den Experimenten verwendeten Datensätze. ](https://cdn.hackernoon.com/images/InxBRjRIs6M1kdhuWcyNHiiUrxm1-eph3eec.jpeg) Das Klassenlabel ist die Gemeinschaft, und unser Ziel ist es, vorherzusagen, zu welcher Gemeinschaft verschiedene Posts gehören. PPI3 ist ein Protein-Protein-Interaktionsdatensatz, der mehrere Graphen enthält, die sich auf verschiedene menschliche Gewebe beziehen [ ]. Die Positionsgen-Sets, Motivgen-Sets und immunologischen Signaturen werden als Knoteneigenschaften betrachtet, und jeder Knoten hat insgesamt 121 Labels, die von Gen-Ontologie-Sets gegeben werden. Die Klassifizierung von Proteinfunktionen, die zu mehreren Genres über verschiedene PPI-Graphen gehören können, ist unser Ziel. Dem induktiven Setup in [ ] folgend, füttern wir auf Reddit Posts aus den ersten 20 Tagen in das Modell zum Trainieren, während die restlichen für das Testen verwendet werden (mit 30% zur Validierung); auf PPI gibt es 20 Graphen zum Trainieren, 2 zur Validierung und 2 zum Testen. Es sollte betont werden, dass auf Reddit und PPI das Testen auf ungesehenen (nicht trainierten) Knoten und Graphen erfolgt, während die ersten drei Datensätze für das transdiktive Lernen verwendet werden. 52 16 Für die Link-Vorhersageaufgabe werden BlogCatalog4 ist eine soziale Blogging-Website, auf der Blogger einander folgen und ihre Blogs unter vordefinierten 6 Kategorien registrieren. Die Tags der Blogs werden als Knoteneigenschaften verwendet. Flickr4 ist eine Bild-Sharing-Website, auf der Benutzer mit anderen interagieren und ein soziales Netzwerk bilden. Benutzer laden Fotos mit 9 vordefinierten Klassen hoch und wählen angehängte Tags aus, um ihre Interessen widerzuspiegeln, die Attributinformationen liefern. Die Beschreibung von Cora und PPI wird der Kürze halber weggelassen. Den experimentellen Einstellungen und Bewertungsmetriken in [15] folgend, zielen wir darauf ab, fehlende Links vorherzusagen, gegeben einen Graphen, bei dem bestimmte Teile der Kanten entfernt wurden. Für Cora, BlogCatalog und Flickr entfernen wir zufällig 20%, 50% und 70% der Kanten, stellen dabei sicher, dass das verbleibende Netzwerk nach der Kantenentfernung verbunden ist, und verwenden das beschädigte Netzwerk zum Trainieren. Bei PPI behandeln wir direkt einen Teil der während des Trainings nicht gesehenen Kanten als Vorhersageziele, anstatt kantenentfernungen manuell vorzunehmen. 4.2 Experimentelle Einstellungen Wir greifen auf ein Standard-Graph-Convolutional-Network (GCN)-Modell mit der folgenden schichtweisen Propagationsregel als Encoder für beide Aufgaben – Klassifizierung und Link-Vorhersage – zurück: Encoder-Design. Wobei Aˆ = D -1/2AD - 1/2A = A + In, Dii = Aij, H (1) und H (I + 1) die Eingabe- und Ausgabematrizen der -ten Schicht sind, ( ) ist eine schichtspezifische trainierbare Gewichtsmatrix. Hier ist die nichtlineare Transformation , die wir angewendet haben, die PReLU-Funktion (parametrisches ReLU) [ ]. Es sollte anerkannt werden, dass für Knoten die Nachbarschaft in seinem Support-Graphen Gi den Knoten selbst enthält, da Selbstschleifen durch A¯ eingefügt werden. l W l σ 17 i Xi i Genauer gesagt ist der von uns auf Citeseer und PubMed verwendete Encoder ein Ein-Schicht-GCN mit der Ausgabedimension ′ = 512. Und auf Cora, Reddit, BlogCatalog, Flickr und PPI verwenden wir einen Zwei-Schicht-GCN als unseren Encoder. Hier haben wir versteckte Dimensionen von ′ = 512 in jeder GCN-Schicht. Beachten Sie, dass die Verwendung desselben GCN-Encoders für transdiktive und induktive Klassifizierungsaufgaben unsere vorgeschlagene Methode einfacher zu befolgen und auf große Netzwerke zu skalieren macht als DGI, da DGI unterschiedliche Encoder entwerfen muss, um sich an verschiedene Lernaufgaben anzupassen, insbesondere die Encoder, die in induktiven Aufgaben verwendet werden, sind zu kompliziert und aufwendig, was für praktische Anwendungen nicht günstig ist. D D Der Diskriminator in Gl. bewertet die Eingabe-Ausgabe-Merkmals-Paare durch eine einfache bilineare Funktion, ähnlich dem Diskriminator in Diskriminator-Design. (11) [31]: wobei Θ eine trainierbare Bewertungsmatrix darstellt und die von uns verwendete Aktivierungsfunktion die Sigmoidfunktion ist, die darauf abzielt, Bewertungen in Wahrscheinlichkeiten für ( , ) als positives Beispiel umzuwandeln. σ h x Tatsächlich gibt es für das Gewicht des ersten Terms in Gl. zwei Möglichkeiten, seinen Wert in Experimenten zu erhalten. Die erste besteht darin, = ( T ) zu halten, was lokale MIs adaptiv zum globalen beitragen lässt, und wir nennen diese Variante GMI-adaptive. Implementierungsdetails. wij (10) wij σ h hj Die andere besteht darin, = , , das linke Ende des Intervalls, zu dem gehört (siehe Theorem was bedeutet, dass der Beitrag jeder lokalen MI gleich ist, und wir nennen diese Variante GMI-mean. Hier sind sowohl GMI-mean als auch GMI-adaptive im Vergleich mit Baselines enthalten. wij 1/in d. h. wi j 1), Alle Experimente werden in PyTorch [23] mit Glorot-Initialisierung [13] implementiert und auf einer einzigen Tesla P40 GPU durchgeführt. Bei der Vorverarbeitung führen wir eine Zeilennormalisierung für Cora, Citeseer, PubMed, BlogCatalog und Flickr nach [25] durch und wenden die in [16] beschriebene Verarbeitungsstrategie auf Reddit und PPI an. Während des Trainings verwenden wir den Adam Optimizer mit einem anfänglichen Training von 0,001 auf allen sieben Datensätzen. Wie in [41] vorgeschlagen, verwenden wir eine Early-Stopping-Strategie mit einem Fenster von 20 auf Cora, Citeseer und PubMed, während wir das Modell für eine feste Anzahl von Epochen auf den induktiven Datensätzen trainieren (20 auf Reddit, 50 auf PPI). Die Anzahl der negativen Stichproben wird auf 5 gesetzt. Aufgrund der Größe von Reddit und PPI müssen wir die in [ ] eingeführte Subsampling-Technik verwenden, um sie in den GPU-Speicher zu bekommen. Im Detail wird zunächst ein Minibatch von 256 Knoten ausgewählt, und dann werden für jeden ausgewählten Knoten 8 bzw. 5 Nachbarn in seiner ersten bzw. zweiten Nachbarschaftsebene gleichmäßig abgetastet. Wir verwenden die Nachbarschaft erster Ordnung, um den Support-Graphen in den Experimenten zu konstruieren, und nutzen (0) ( , eine komprimierte Eingabemerkmal) zur Berechnung von FMI, da die Verwendung des ursprünglichen Eingabemerkmals zu einem GPU-Speicherüberlauf führt. Die Gewichtungsparameter werden im Bereich [0,1] abgestimmt, um Gl. und Gl. auszugleichen. Die Batch-Normalisierungsstrategie wird verwendet, um unser Modell auf Reddit und PPI zu trainieren. 16 XW d. h. X (11) (12) [22] Für die Klassifizierungsaufgabe stellen wir die gelernten Embeddings des Trainingsdatensatzes einem Logistik-Regressionsklassifikator zur Verfügung und liefern die Ergebnisse auf den Testknoten [ , ]. Insbesondere im transdiktiven Lernen verwenden wir die durchschnittliche Klassifikationsgenauigkeit nach 50 Läufen zur Bewertung der Leistung, während der mikro-durchschnittliche F1-Score, gemittelt nach 50 Läufen, im induktiven Lernen verwendet wird. Und für PPI standardisieren wir, wie von [ ] vorgeschlagen, die gelernten Embeddings, bevor wir sie in den Logistik-Regressionsklassifikator einspeisen. Für die Link-Vorhersageaufgabe ist das von uns verwendete Kriterium AUC, die Fläche unter der ROC-Kurve. Die in die AUC-Berechnung einbezogenen negativen Stichproben werden durch zufällige Auswahl einer gleichen Anzahl von Knotenpaaren ohne Verbindungen im ursprünglichen Graphen generiert. Je näher der AUC-Wert an 1 liegt, desto besser ist die Leistung des Algorithmus. Ebenso berichten wir den AUC-Score, gemittelt nach 10 Läufen. Bewertungsmetriken. 16 25 41 4.3 Klassifizierung Tabelle zeigt die durchschnittliche Klassifikationsgenauigkeit unserer Methode und anderer Baselines bei transdiktiven Aufgaben. Hier werden die Ergebnisse für EP-B [ ], DGI [ ], Planetoid-T [ ], GAT [ ] sowie GWNN [ ] aus ihren Originalarbeiten übernommen, und die Ergebnisse für DeepWalk [ ], LP (Label Propagation) [ ] und GCN [ ] werden von Kipf & Welling [ ] kopiert. Was die rohen Merkmale betrifft, so speisen wir sie zum Trainieren in einen Logistik-Regressionsklassifikator ein und liefern die Ergebnisse auf den Testmerkmalen5. Obwohl wir experimentelle Ergebnisse für sowohl überwachbare als auch unbeaufsichtigbare Methoden liefern, konzentrieren wir uns in dieser Arbeit stärker auf den Vergleich mit unbeaufsichtigbaren Methoden, was mit unserem Setup übereinstimmt. Transduktives Lernen. 2 11 41 45 40 44 33 51 25 25 Wie zu sehen ist, erzielen unsere vorgeschlagenen GMI-mean und GMI-adaptive im Vergleich zu anderen unbeaufsichtigbaren Methoden die beste Klassifikationsgenauigkeit über alle drei Datensätze hinweg. Wir betrachten diese starke Leistung als vorteilhaft für die Idee, die grafische MI zwischen Eingabe- und Ausgabepaaren des Encoders E auf feinkörniger Knotenebene direkt zu maximieren. Daher bewahrt die kodierte Repräsentation die Informationen von Knoteneigenschaften und Topologie in G maximal, was zur Klassifizierung beiträgt. Im Gegensatz dazu ignoriert EP-B die zugrunde liegenden Informationen zwischen Eingabedaten und gelernten Repräsentationen, und DGI verbleibt bei einer MI-Maximierung auf Graph-/Patch-Ebene, was ihre Fähigkeit einschränkt, die ursprünglichen Eingabeinformationen in den Einbettungsraum zu bewahren und zu extrahieren. Daher leicht schwächere Leistung bei Klassifizierungsaufgaben. Außerdem erzielt unsere Methode ohne Anleitung durch Labels vergleichbare Ergebnisse mit einigen überwachten Modellen wie GCN und GAT und übertrifft sie sogar auf Citeseer und PubMed. Wir glauben, dass die durch GMI-Maximierung zwischen Ein- und Ausgaben gelernten Repräsentationen die reichen Informationen in G erben, was für die Klassifizierung ausreicht. Bemerkenswerter ist, dass viele verfügbare Labels auch auf der Grundlage von Informationen in G gegeben werden. Daher kann die Beibehaltung so vieler Informationen wie möglich von der Eingabe die Informationen, die durch das Label bereitgestellt werden, bis zu einem gewissen Grad kompensieren, was die Leistung von GMI bei nachfolgenden Graph-Mining-Aufgaben aufrechterhält. Man könnte argumentieren, dass das Lernen von ursprünglichen Eingaben ohne Labels das Potenzial für qualitativ hochwertigere Repräsentationen als das überwachte Muster verspricht, da die extreme Sparsamkeit der Trainingslabels unter der Bedrohung von Overfitting leiden kann oder die Korrektheit gegebener Labels möglicherweise nicht zuverlässig ist. Tabelle fasst auch die mikro-durchschnittlichen F1-Scores von GMI und anderen Baselines auf Reddit und PPI zusammen. Wir zitieren die Ergebnisse von DGI, GAT, FastGCN [ ] und GaAN [ ] in ihren Originalarbeiten, während die Ergebnisse für die restlichen sieben verglichenen Methoden von Hamilton et al. [ ] extrahiert werden (hier verwenden wir die unbeaufsichtigten GraphSAGE-Ergebnisse wieder, um unser Setup anzupassen). Ebenso ist der Vergleich mit unbeaufsichtigbaren Algorithmen der Schwerpunkt unserer Arbeit. Induktives Lernen. 2 7 48 16 GMI-mean und GMI-adaptive übertreffen erfolgreich alle anderen konkurrierenden unbeaufsichtigbaren Algorithmen auf Reddit und PPI, was die Wirksamkeit der GMI-Maximierung im Bereich der induktiven Klassifizierung (Generalisierung auf ungesehene Knoten) belegt. Interessanterweise ist das Ergebnis unserer Methode auf Reddit mit einigen fortschrittlichen überwachten Modellen konkurrenzfähig, aber die Situation auf PPI ist ganz anders. Nach weiterer Analyse stellen wir fest, dass 42% der Knoten in PPI keine Merkmalswerte haben, was bedeutet, dass die Merkmalsmatrix X sehr spärlich ist [ ]. In diesem Fall begrenzt das direkte und alleinige Verlassen auf den Eingabegraphen G = ( , ) die Leistung von unbeaufsichtigbaren Ansätzen, einschließlich DGI und unserer Methode, während das Lernen in einem überwachten Verfahren aufgrund der zusätzlichen Informationen durch zusätzliche Labels eine deutlich bessere Leistung zeigt. 16 X A Gemäß Tabelle erzielen die beiden Varianten von GMI (GMI-mean und GMI-adaptive), die unterschiedliche Strategien zur Messung des Beitrags jeder lokalen MI verwenden (Details in § wettbewerbsfähige Ergebnisse miteinander, aber GMI-adaptive zeigt eine etwas schwächere Leistung als GMI-mean. Nach weiterer Analyse vermuten wir, dass dies auf die Schwierigkeiten beim Trainieren zurückzuführen ist, die durch die Natur des adaptiven Lernens entstehen. Vielleicht könnte die Leistung von GMI-adaptive mit Hilfe einer fortschrittlichen Trainingsstrategie verbessert werden. In diesem Sinne ist GMI-mean praktischer und machbarer und kann daher als Vertreter in der Praxis angesehen werden. Bewertung von zwei Varianten von GMI. 2 4.2), 4.4 Wirksamkeit der Zielfunktion Um die Wirksamkeit der Maximierung der grafischen MI beim unbeaufsichtigten Lernen von Graphrepräsentationen weiter zu verdeutlichen und einen relativ fairen Vergleich mit DGI und EP-B (zwei unbeaufsichtigbare Algorithmen) zu ermöglichen, ersetzen wir unsere Zielfunktion durch ihre jeweiligen Verlustfunktionen, während andere experimentelle Einstellungen unverändert bleiben. Tabelle listet die Ergebnisse unter dem transdiktiven und induktiven Setup auf. Wie zu sehen ist, erzielt GMI (GMI-mean und GMI-adaptive) auf allen fünf Datensätzen eine stärkere Leistung, was zeigt, dass DGI und EP-B einige Überlegungen bei der Aufgabe des Lernens von Graphrepräsentationen vermissen lassen. Insbesondere die EP-B-Verlustfunktion legt nur Einschränkungen für jeden Knoten und seine Nachbarn auf der Ausgabenebene (Einbettungsraum) fest, sie ignoriert die Interaktion zwischen Ein- und Ausgabepaaren des Encoders, was zu ihrer schlechten Fähigkeit führt, die gültigen Informationen in G zu bewahren. Für DGI, obwohl es versteckte Repräsentationen implizit mit ihren ursprünglichen Eingabemerkmalen korreliert, diskutiert es MI auf Graph-/Patch-Ebene, was etwas grob ist. 3 Interessanterweise gewinnen wir im Vergleich zu DGI mit unserer FMI (ohne Topologieinformationen) mit zunehmender Graphgröße deutlich an Verbesserungen. Wir führen diese Entdeckung darauf zurück, dass die Leistungsverschlechterung der Lesefunktion dazu führt, dass DGI bei zunehmender Graphgröße bestimmte nützliche Informationen für die Knotenklassifizierung verliert, obwohl es auf kleinen Graphen wie Cora und Citeseer eine gute Leistung zeigt. Wenn die Topologie des Eingabegraphen reflektiert wird, übertrifft unser GMI alle anderen Verlustarten auf allen Datensätzen. Darüber hinaus ist zu beachten, dass der gesamte Trainingsprozess von GMI dem Training von Diskriminatoren in generativen Modellen [14, 30] ähnelt, und GMI zeigt empirisch eine vergleichbare Trainingsgeschwindigkeit mit EP-B und DGI auf dem größten Datensatz Reddit, was seine gute Skalierbarkeit beweist. 4.5 Link-Vorhersage Basierend auf den obigen experimentellen Ergebnissen stellen wir fest, dass DGI ein starker Konkurrent für GMI im Bereich der unbeaufsichtigbaren Algorithmen ist. Daher beabsichtigen wir in diesem Abschnitt, die Leistung von DGI und GMI bei einer weiteren Mining-Aufgabe – der Link-Vorhersage – weiter zu untersuchen. Hier wählen wir FMI und GMI-mean, um sie mit DGI zu vergleichen. Tabelle zeigt ihre AUC-Scores auf vier verschiedenen Datensätzen. Unter verschiedenen Kantenentfernungsraten übertreffen GMI und FMI DGI (außer FMI bei 70,0% BlogCatalog) bemerkenswert, was zeigt, dass die Messung grafischer MI zwischen Eingabegraph und Ausgaberepräsentationen in einem feinkörnigen Muster in der Lage ist, reiche Informationen in Eingaben zu erfassen und eine gute Generalisierungsfähigkeit zu liefern. Bei DGI schränkt seine Graph-/Patch-Level-MI-Maximierung, die relativ grob ist, seine Leistung bei einer solch feinen Link-Vorhersageaufgabe ein; zum anderen schwächt die Unangemessenheit der Korruptionsfunktion die Fähigkeit von DGI, genaue Repräsentationen zum Vorhersagen fehlender Links zu lernen. Erinnern Sie sich, dass die negative Stichprobe für den Diskriminator in DGI durch Korruption des ursprünglichen Eingabegraphen generiert wird, und eine gut gestaltete Korruptionsfunktion ist unerlässlich, die einige geschickte Strategien erfordert [ ]. Bei dieser Aufgabe übernehmen wir immer noch die Funktion des Merkmalsmischens, die die besten Ergebnisse bei der Klassifizierungsaufgabe zeigt, um negative Stichproben zu erstellen. Aber in dem Fall, dass ein Eingabegraph in Bezug auf topologische Links unvollständig ist, wird die Anleitung, die von diesem korrumpierten Graphen als negativem Label im Diskriminator gegeben wird, aufgrund der Ungenauigkeit des Eingabegraphen unzuverlässig, was zu schlechter Leistung führt. Daher ist die Notwendigkeit einer aufgabenorientierten Korruptionsfunktion eine Schwäche von DGI. Im Gegensatz dazu ist unser GMI frei von diesem Problem, indem die Korruptionsfunktion eliminiert und die grafische MI zwischen Ein- und Ausgaben des Encoders direkt maximiert wird. Darüber hinaus kann beobachtet werden, dass FMI in den meisten Fällen konkurrenzfähig zu GMI ist, sogar auf Flickr ist FMI GMI überlegen. Wir vermuten, dass dies auf die Vorteile der direkten und ausgefeilten Maximierung der gegenseitigen Merkmalinformation auf Knotenebene zurückzuführen ist. Basierend auf der Homophilie-Hypothese [ ] (d. h. Entitäten im Netzwerk mit ähnlichen Merkmalen verbinden sich wahrscheinlich), machen die in den gelernten Embeddings bewahrten Eingabemerkmalinformationen FMI zu einer guten Fähigkeit, fehlende Links zu inferieren. 4 41 29 4.6 Visualisierung Zur intuitiven Veranschaulichung zeigt Tabelle t-SNE [ ]-Plots der gelernten Embeddings auf Cora und Citeseer. Aus qualitativer Sicht scheint die Verteilung der von FMI und DGI gelernten Plots ähnlich zu sein, und die von GMI erzeugten Embeddings weisen besser unterscheidbare Cluster auf als Rohmerkmale, FMI und DGI. 5 28 Besonders auf Cora sind die Kompaktheit und Trennbarkeit der Cluster extrem offensichtlich, was die sieben Themenkategorien darstellt. Zur quantitativen Analyse versuchen wir, die Clustering-Qualität zu messen, indem wir den Silhouette-Koeffizienten-Score [ ] berechnen. Speziell verwenden wir die Funktion aus dem scikit-learn Python-Paket [ ] mit allen Standardeinstellungen und folgen dem Benutzerhandbuch zur Auswertung. Das Clustering der durch GMI gelernten Embeddings erzielt einen Silhouette-Koeffizienten-Score von 0,425 auf Cora, 0,402 auf Citeseer und 0,385 auf PubMed, während DGI 0,417, 0,391, 0,373 und EP-B 0,384, 0,385, 0,379 auf den drei Datensätzen erzielt. Sowohl qualitativ als auch quantitativ zeigt dies die großartige Leistung von GMI, was die Rationalität und Wirksamkeit der grafischen gegenseitigen Informationmaximierung beim unbeaufsichtigten Lernen von Graphrepräsentationen demonstriert. 37 silhouette_score 32 4.7 Einfluss der Modelltiefe In diesem Teil passen wir die Anzahl der Convolutional Layers im Encoder an, um den Einfluss der Modelltiefe auf die Klassifikationsgenauigkeit zu untersuchen. Angesichts der potenziellen Schwierigkeit, tiefe neuronale Netze zu trainieren, und wie von [ ] vorgeschlagen, experimentieren wir auch mit einer entsprechenden Residualversion des Standard-GMI-Modells, das Identitäts-Shortcut-Verbindungen zwischen jeder zweiten versteckten Schicht hinzufügt, um das Training tiefer Netze zu verbessern. Hier haben wir weiterhin D ′ = 512 Merkmale für jede versteckte Schicht und beginnen mit der Anwendung von Identitäts-Shortcuts ab der zweiten Schicht, da die Eingabe und Ausgabe der ersten Schicht keine identische Dimension haben. 18 Darüber hinaus betrachten wir im Vergleich zum Standard-GMI-Modell, das GMI-Maximierung zwischen der finalen Repräsentation und dem ursprünglichen Eingabegraphen erzielt, eine weitere Variante namens Dense GMI, die GMI zwischen jeder versteckten Schicht und dem Eingabegraphen maximiert. Abbildung zeigt eine detaillierte Architekturanleitung. Die beteiligten Hyperparameter bleiben unverändert, außer dass wir für feste Epochen (600 auf Cora und Citeseer) ohne Early Stopping trainieren. Die Ergebnisse sind in Abbildung dargestellt. 2 3 Einerseits vergrößert die Zunahme der Modelltiefe signifikant die Leistungslücke zwischen Modellen mit und ohne Shortcut-Verbindungen. Das beste Ergebnis für Cora wird mit einem Zwei-Schicht-GCN-Encoder erzielt, während das beste Ergebnis für Citeseer mit einem Ein-Schicht-GCN-Encoder erzielt wird. Abgesehen von der Tatsache, dass das Training ohne Shortcut-Verbindungen bei zunehmender Modelltiefe schwierig wird, vermuten wir auch, dass die durch mehrere Convolutional Layers hervorgerufenen Informationen aus weiter entfernten Nachbarschaften für das Selbstrepräsentationslernen Rauschen darstellen können. Insbesondere bedeutet die unterschiedliche Nähe zwischen Nachbarn unterschiedliche Ähnlichkeitsgrade. Wenn zwei beliebige Knoten eine gewisse Entfernung voneinander haben, sind sie wahrscheinlich völlig unterschiedlich. Daher kann die von der weiter entfernten Nachbarschaft aggregierte Information im Standard-GMI-Modell viel Rauschen enthalten, das sich von den Merkmalen des Knotens selbst unterscheidet, was die Qualität der gelernten Embeddings und die nachfolgende Klassifizierungsleistung beeinträchtigt. Im Gegensatz dazu ermöglichen zusätzliche Identitäts-Shortcuts, dass das Modell die Informationen des Eingangs der vorherigen Schicht weitergibt, was als komplementärer Prozess zu ähnlichen Nachbarschaftsinformationen von flacheren zu tieferen Schichten betrachtet werden kann, sodass die Residualversion relativ weniger anfällig für die Modelltiefe ist. Andererseits beobachten wir, dass die Dense-GMI-Variante die Leistungsverschlechterung bis zu einem gewissen Grad auch lindern kann, obwohl die MI aufgrund der Datenverarbeitungsungleichheit [ ] mit der Tiefe tendenziell abnimmt. Dies liegt daran, dass die Maximierung der grafischen MI zwischen der Ausgabe jeder Schicht und dem Eingabegraphen eine direkte Einschränkung für jede versteckte Schicht auferlegt, um die Eingabeinformationen so intakt wie möglich zu bewahren. Basierend auf dieser Beobachtung könnte die Auferlegung der Einschränkung der Maximierung von MI auf versteckte Schichten, um den Informationsverlust beim Trainieren tiefer neuronaler Netze zu reduzieren, eine gute Praxis sein. 8 5 FAZIT Um das Dilemma fehlender verfügbarer Aufsicht zu überwinden und das potenzielle Risiko unzuverlässiger Labels zu vermeiden, führen wir ein neuartiges Konzept der grafischen gegenseitigen Information (GMI) ein, um das Lernen von Graphrepräsentationen in einem unbeaufsichtigten Muster durchzuführen. Sein Kern liegt in der direkten Maximierung der gegenseitigen Information zwischen der Eingabe und Ausgabe eines Graph-Neural-Encoders in Bezug auf Knoteneigenschaften und topologische Struktur. Durch unsere theoretische Analyse geben wir eine Definition von GMI an und zerlegen sie in eine gewichtete Summe, die leicht mit der aktuellen Methode zur Schätzung der gegenseitigen Information, MINE, berechnet werden kann. Dementsprechend entwickeln wir ein unbeaufsichtigtes Modell und führen zwei gängige Graph-Mining-Aufgaben durch. Die Ergebnisse zeigen, dass GMI State-of-the-Art-unbeaufsichtigte Baselines sowohl bei Klassifizierungsaufgaben (transduktiv und induktiv) als auch bei Link-Vorhersageaufgaben übertrifft und manchmal sogar wettbewerbsfähig mit überwachten Algorithmen ist. Zukünftige Arbeiten werden sich auf aufgabenorientiertes Repräsentationslernen konzentrieren oder die Idee der GMI-Maximierung auf andere Arten von Graphen wie heterogene Graphen und Hypergraphen anwenden. DANKSAGUNG Diese Arbeit wurde unterstützt durch das National Key Research and Development Program of China (Nr. 2018AAA0101400), die National Nature Science Foundation of China (Nr. 61872287 und Nr. 61532015), die Innovative Research Group der National Natural Science Foundation of China (Nr. 61721002), das Innovation Research Team des Ministeriums für Bildung (IRT_17R86) und das Projekt des China Knowledge Center for Engineering Science and Technology. Außerdem wurde diese Forschung durch das National Science and Technology Major Project des chinesischen Ministeriums für Wissenschaft und Technologie (Nr. 2018AAA0102900) gefördert. REFERENZEN [1] Luís B Almeida. 2003. MISEP–Linear and Nonlinear ICA Based on Mutual Information. 4, Dez (2003), 1297–1318. Journal of machine learning research [2] Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville und R Devon Hjelm. 2018. Mine: mutual information neural estimation. In . ICML [3] Anthony J Bell und Terrence J Sejnowski. 1995. An information-maximization approach to blind separation and blind deconvolution. 7, 6 (1995), 1129–1159. Neural computation [4] Esben Jannik Bjerrum und Richard Threlfall. 2017. Molecular generation with recurrent neural networks (RNNs). (2017). arXiv preprint arXiv:1705.04612 [5] Xavier Bresson und Thomas Laurent. 2019. A Two-Step Graph Convolutional Decoder for Molecule Generation. (2019). arXiv preprint arXiv:1906.03412 [6] Shaosheng Cao, Wei Lu und Qiongkai Xu. 2015. Grarep: Learning graph repre-sentations with global structural information. In . CIKM [7] Jie Chen, Tengfei Ma und Cao Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. (2018). arXiv preprint arXiv:1801.10247 [8] Thomas M Cover und Joy A Thomas. 2012. . John Wiley & Sons. Elements of information theory [9] Ming Ding, Jie Tang und Jie Zhang. 2018. Semi-supervised learning on graphs with generative adversarial nets. In . CIKM [10] Monroe D Donsker und SR Srinivasa Varadhan. 1983. Asymptotic evaluation of certain Markov process expectations for large time. IV. 36, 2 (1983), 183–212. Communications on pure and applied mathematics [11] Alberto Garcia Duran und Mathias Niepert. 2017. Learning graph representations with embedding propagation. In . NeurIPS [12] Evgeniy Faerman, Otto Voggenreiter, Felix Borutta, Tobias Emrich, Max Berrendorf und Matthias Schubert. 2019. Graph Alignment Networks with Node Matching Scores. In . NeurIPS [13] Xavier Glorot und Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In . AISTATS [14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville und Yoshua Bengio. 2014. Generative adversarial nets. In . NeurIPS [15] Aditya Grover und Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In . KDD [16] Will Hamilton, Zhitao Ying und Jure Leskovec. 2017. Inductive representation learning on large graphs. In . NeurIPS [17] Kaiming He, Xiangyu Zhang, Shaoqing Ren und Jian Sun. 2015. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In . ICCV [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren und Jian Sun. 2016. Deep residual learning for image recognition. In . CVPR [19] Mark Heimann, Haoming Shen, Tara Safavi und Danai Koutra. 2018. Regal: Representation learning-based graph alignment. In . CIKM [20] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler und Yoshua Bengio. 2018. Learning deep represen-tations by mutual information estimation and maximization. (2018). arXiv preprint arXiv:1808.06670 [21] Aapo Hyvärinen und Petteri Pajunen. 1999. Nonlinear independent component analysis: Existence and uniqueness results. 12, 3 (1999), 429–439. Neural networks [22] Sergey Ioffe und Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. (2015). arXiv preprint arXiv:1502.03167 [23] Nikhil Ketkar. 2017. Introduction to pytorch. In . 195–208. Deep learning with python [24] Diederik P Kingma und Jimmy Ba. 2014. Adam: A method for stochastic opti-mization. (2014). arXiv preprint arXiv:1412.6980 [25] Thomas N Kipf und Max Welling. 2016. Semi-supervised classification with graph convolutional networks. (2016). arXiv preprint arXiv:1609.02907 [26] Thomas N Kipf und Max Welling. 2016. Variational graph auto-encoders. (2016). arXiv preprint arXiv:1611.07308 [27] David Liben-Nowell und Jon Kleinberg. 2007. The link-prediction problem for social networks. 58, 7 (2007), 1019–1031. Journal of the American society for information science and technology [28] Laurens van der Maaten und Geoffrey Hinton. 2008. Visualizing data using t-SNE. 9, Nov (2008), 2579–2605. ournal of machine learning research [29] Miller McPherson, Lynn Smith-Lovin und James M Cook. 2001. Birds of a feather: Homophily in social networks. 27, 1 (2001), 415–444. Annual review of sociology [30] Sebastian Nowozin, Botond Cseke und Ryota Tomioka. 2016. f-gan: Training gen-erative neural samplers using variational divergence minimization. In . NeurIPS [31] Aaron van den Oord, Yazhe Li und Oriol Vinyals. 2018. Representation learning with contrastive predictive coding. (2018). arXiv preprint arXiv:1807.03748 [32] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. 2011. Scikit-learn: Machine learning in Python. 12, Okt (2011), 2825–2830. Journal of machine learning research [33] Bryan Perozzi, Rami Al-Rfou und Steven Skiena. 2014. Deepwalk: Online learning of social representations. In . KDD [34] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang und Jie Tang. 2018. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In . WSDM [35] Meng Qu, Yoshua Bengio und Jian Tang. 2019. GMNN: Graph Markov Neural Networks. In . ICML [36] Renato Renner und Ueli Maurer. 2002. About the mutual (conditional) information. In . ISIT [37] Peter J Rousseeuw. 1987. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. 20 (1987), 53–65. Journal of computational and applied mathematics [38] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher und Tina Eliassi-Rad. 2008. Collective classification in network data. 29, 3 (2008), 93–93. AI magazine [39] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan und Qiaozhu Mei. 2015. Line: Large-scale information network embedding. In . WWW [40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio und Yoshua Bengio. 2017. Graph attention networks. (2017). arXiv preprint arXiv:1710.10903 [41] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio und R Devon Hjelm. 2018. Deep graph infomax. (2018). arXiv preprint arXiv:1809.10341 [42] Jun Wu, Jingrui He und Jiejun Xu. 2019. Net: Degree-specific Graph Neural Networks for Node and Graph Classification. (2019). arXiv preprint arXiv:1906.02319 [43] Yuting Wu, Xiao Liu, Yansong Feng, Zheng Wang, Rui Yan und Dongyan Zhao. 2019. Relation-aware entity alignment for heterogeneous knowledge graphs. In . IJCAI [44] Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu und Xueqi Cheng. 2019. Graph Wavelet Neural Network. (2019). arXiv preprint arXiv:1904.07785 [45] Zhilin Yang, William W Cohen und Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. (2016). arXiv preprint arXiv:1603.08861 [46] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande und Jure Leskovec. 2018. Graph convolutional policy network for goal-directed molecular graph generation. In . NeurIPS [47] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov und Alexander J Smola. 2017. Deep sets. In . 3391–3401. NeurIPS [48] Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King und Dit-Yan Yeung. 2018. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. (2018). arXiv preprint arXiv:1803.07294 [49] Muhan Zhang und Yixin Chen. 2018. Link prediction based on graph neural networks. In . NeurIPS [50] Yingxue Zhang, Soumyasundar Pal, Mark Coates und Deniz Ustebay. 2019. Bayesian graph convolutional neural networks for semi-supervised classification. In . AAAI [51] Xiaojin Zhu, Zoubin Ghahramani und John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In . ICML [52] Marinka Zitnik und Jure Leskovec. 2017. Predicting multicellular function through multi-layer tissue networks. 33, 14 (2017), i190–i198. Bioinformatics Diese Arbeit ist unter der CC BY 4.0 Deed (Attribution 4.0 International) Lizenz verfügbar. auf ieee.org