La complexité de la présentation des données pour le deep learning augmente chaque jour. Les réseaux de neurones graphiques ( GNN ) sont devenus l'une des percées de ces dernières années. Mais pourquoi les graphiques gagnent-ils de plus en plus en popularité dans l'apprentissage automatique?

Le but ultime de mon récit est la présentation générale des graphiques dans les techniques d'apprentissage automatique. L'article ne prétend pas être un travail scientifique qui décrit pleinement la pleine puissance des graphiques, mais ne fait qu'introduire le lecteur dans ce monde étonnant et complexe. La publication est parfaite, à la fois pour les professionnels endurcis au combat qui ne sont pas encore familiarisés avec la présentation de graphiques en apprentissage profond, et pour les débutants dans ce domaine.

introduction

La mise en évidence automatique des fonctionnalités importantes nécessaires pour résoudre un problème est l'une des principales raisons du succès de l'apprentissage automatique. Mais traditionnellement, lorsque vous travaillez avec des graphiques, les approches d'apprentissage automatique reposent sur des heuristiques définies par l'utilisateur pour extraire les fonctionnalités de codage des informations structurelles des graphiques. Néanmoins, la tendance des dernières années a changé: des approches émergent de plus en plus dans lesquelles ils apprennent automatiquement à coder la structure du graphique dans des investissements de faible dimension en utilisant des méthodes d'apprentissage en profondeur et de réduction de dimension non linéaire.

Dans l'apprentissage automatique sur les graphiques, deux problèmes centraux peuvent être distingués: l'inclusion d'informations sur la structure du graphique dans le modèle (c'est-à-dire un moyen simple de coder ces informations dans le vecteur d'entités) et la réduction de la dimension du vecteur d'entités.

( ), . , , .

?

, , : ?

— . , , ( ) [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 février 2018.

Références

Graph Neural Networks: A Review of Methods and Applications
Representation Learning on Graphs: Methods and Applications