Die Komplexität der Präsentation von Daten für tiefes Lernen wächst von Tag zu Tag. Graph Neural Networks ( GNNs ) sind zu einem der Durchbrüche der letzten Jahre geworden. Aber warum genau werden Grafiken beim maschinellen Lernen immer beliebter?

Das ultimative Ziel meiner Erzählung ist eine allgemeine Darstellung von Graphen in maschinellen Lerntechniken. Der Artikel gibt nicht vor, eine wissenschaftliche Arbeit zu sein, die die volle Kraft von Graphen vollständig beschreibt, sondern führt den Leser nur in diese erstaunliche und komplexe Welt ein. Die Veröffentlichung ist perfekt, sowohl für kampferprobte Profis, die noch nicht mit der Darstellung von Grafiken im Deep Learning vertraut sind, als auch für Anfänger auf diesem Gebiet.

Einführung

Das automatische Hervorheben wichtiger Funktionen zur Lösung eines Problems ist einer der Hauptgründe für den erfolgreichen Einsatz von maschinellem Lernen. Bei der Arbeit mit Diagrammen stützten sich Ansätze des maschinellen Lernens traditionell auf benutzerdefinierte Heuristiken, um die Codierungsmerkmale von Strukturdiagramminformationen zu extrahieren. Trotzdem hat sich der Trend der letzten Jahre geändert: Es entstehen zunehmend Ansätze, bei denen sie automatisch lernen, die Graphstruktur in niedrigdimensionalen Investitionen mithilfe von Methoden des tiefen Lernens und der nichtlinearen Dimensionsreduktion zu codieren.

Beim maschinellen Lernen in Graphen können zwei zentrale Probleme unterschieden werden: die Einbeziehung von Informationen über die Struktur des Graphen in das Modell (d. H. Eine einfache Methode zum Codieren dieser Informationen in den Merkmalsvektor) und die Verringerung der Dimension des Merkmalsvektors.

( ), . , , .

?

, , : ?

— . , , ( ) [1], [2], ( [3], [4] [5]), [6] [7].

CV/ML , , . , , [8].

, . . , , , .

, (embeddings), . , , , , (), $$$R^d$. , , . , .

, . , , . , , , .

, (direct encoding), . . , , -. , , , .

DeepWalk node2vec . , . , .

( ). (DNGR SDNE), , [9].

$$$G = (V, E)$, $$$V$, , $$$E$— ( ) , .

(.1). : $$$V = \\{1,2,3,4,5,6\\}$$$$E = \\{\\{1, 2\\},\\{1, 5\\},\\{2, 3\\},\\{2, 5\\},\\{3, 4\\},\\{4, 5\\},\\{4, 6\\}\\}$

, , , ( , ). .

, $$$G = (V, E)$$$$A$. , $$$X ∈ R^{m*|V|}$( , ). , , $$$A$$$$X$, $$$z ∈ R^d$, $$$d << |V|$.

, $$$A$$$$X$, . , , . (, )

- , $$$v_i$$$$z_i$, / . ; $$$v_i$( ) , $$$v_i$( ). , .

, , , . , (, ) . 2 , , .

, — , , $$$z_i ∈ R^d$( $$$z_i$$$$v_i ∈ V$):

$$

$$\textbf{ENC: } V → R^d$$

— , :

$$

$$\textbf{DEC: } R^d * R^d → R^+$$

. , , . , $$$(z_i, z_j)$, $$$v_i$$$$v_j$. , :

$$

$$DEC(ENC(v_i), ENC(v_j)) = DEC(z_i, z_j ) ≈ sG(v_i, v_j) \textbf{ (1)}$$

$$$sG$— , $$$G$. , $$$sG(z_i, z_i) ≜ A_i,_j$, 1, 0. $$$sG$$$$v_i$$$$v_j$$$$G$. ( 1) $$$L$$$$D$:

$$

$$L = \sum_{(v_i, v_j) ∈ D} ℓ (DEC(z_i, z_j), sG(v_i, v_j))$$

$$$ℓ = R * R → R$— , (.. ) $$$DEC(z_i, z_j)$$$$sG(v_i, v_j)$.

, -, , . , , , , , .

seq2seq , , . , seq2seq, GNN [10].

, :

1. $$$sG$: $$$V * V → R^+$, $$$G$.
2. ENC, . , .
3. DEC, .
4. $$$ℓ$, , .

. , . $$$pG(v_j|v_i)$$$$v_j$, $$$v_i$.

, , . , , (.3). , , , .

DeepWalk node2vec, , , . , , . , , :

$$

$$DEC(z\_i, z\_j) ≜ \dfrac{e^{z\_i^Tz\_j}}{\sum_{v_k∈V}e^{z_i^Tz_k}} ≈ pG,T(v\_j|v\_i) \textbf{ (2)}$$

$$$pG,T (v_j|v_i)$— $$$v_j$$$$T$, $$$v_i$, $$$T$$$$T ∈ \\{2, ..., 10\\}$. , $$$pG,T (v_j|v_i)$. , :

$$

$$ℓ=\sum_{(v_i,v_j)∈D}−log(DEC(z_i, z_j)) \textbf{ (3)}$$

$$$D$, (.. $$$N$$$$v_i$$$$(v_i, v_j) \sim pG,T(v_j|v_j)$. — $$$O(|D||V|)$( (2) $$$O(|V|)$). , DeepWalk node2vec (3). DeepWalk softmax , . , node2vec (3), : , , " ".

, node2vec DeepWalk , , . , node2vec : $$$p$$$$q$, (.4). $$$p$, $$$q$. , node2vec , .

A: , node2vec , p q. , $$$v\_s$$$$v\_∗$, (α) , .

B: , (BFS) (DFS). , BFS, , , . , , DFS, .

, . , :

1. (.. ). , , .
2. . (, ), .
3. . , , ( , ). , , , , .

/ . -, , , .

(DNGR) (SDNE) , : , . , — , (.5). DNGR SDNE , .

$$$v_i$$$$s_i ∈ R^{|V|}$, $$$v_i$$$$S$( $$$S$— $$$S_i,_j = sG (v_i , v_j)$). $$$s_i$$$$v_i$$$$v_i$. DNGR SDNE , $$$s_i$, $$$s_i$:

$$

$$DEC(ENC(s_i)) = DEC(z_i) ≈ s_i$$

, :

$$

$$ℓ=\sum_{v_i∈V} ||DEC(z_i) − s_i||^2_2$$

, $$$z_i$, $$$|V|$( ), , . SDNE, DNGR, : , (.5).

SDNE DNGR , $$$s_i$, , . DNGR $$$s_i$, , DeepWalk node2vec. SDNE $$$s_i ≜ Ai$, $$$v_i$.

, SDNE DNGR , ( ), - . $$$|V|$, .

, . . , , , [9], . , .

. , , , , , , .

, , , .

. (. $$$O(|E|)$), ( ). . , , , , , , — , , , . , , , .

. , , - , , . , , , , .

. , , , . , , , . , .

. , , . , , . , , , . , , , , .

, — . , , .

[1] — W. L. Hamilton, Z. Ying, and J. Leskovec, "Inductive representation learning on large graphs," NIPS 2017, pp. 1024–1034, 2017.
[2] — T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," ICLR 2017, 2017.
[3] — A. Sanchez-Gonzalez, N. Heess, J. T. Springenberg, J. Merel, M. Riedmiller, R. Hadsell, and P. Battaglia, "Graph networks as learnable physics engines for inference and control," arXiv
preprint arXiv:1806.01242, 2018.
[4] — P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende et al., "Interaction networks for learning about objects, relations and physics," in NIPS 2016, 2016, pp. 4502–4510.
[5] — A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, "Protein interface prediction using graph convolutional networks," in NIPS 2017, 2017, pp. 6530–6539.
[6] — T. Hamaguchi, H. Oiwa, M. Shimbo, and Y. Matsumoto, "Knowledge transfer for out-of-knowledge-base entities: A graph neural network approach," in IJCAI 2017, 2017, pp. 1802–1808.
[7] — H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, "Learning combinatorial optimization algorithms over graphs," arXiv preprint arXiv:1704.01665, 2017.
[8] — X. Liang, X. Shen, J. Feng, F. Lin, S. Yan, "Semantic Object Parsing with Graph LSTM", arXiv:1603.07063v1 [cs.CV] 23 Mar 2016.
[9] — Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, "A Comprehensive Survey on Graph Neural Networks", arXiv:1901.00596v4 [cs.LG] 4 Dec 2019.
[10] - P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, Y. Bengio, "Graph Attention Networks", arXiv: 1710.10903v3 [stat.ML] 4. Februar 2018.

Verweise

Graph Neuronale Netze: Ein Überblick über Methoden und Anwendungen
Repräsentationslernen in Graphen: Methoden und Anwendungen