La complejidad de presentar datos para el aprendizaje profundo está creciendo cada día. Las redes neuronales gráficas ( GNN ) se han convertido en uno de los avances de los últimos años. Pero, ¿por qué exactamente los gráficos están ganando cada vez más popularidad en el aprendizaje automático?

El objetivo final de mi narrativa es una presentación general de gráficos en técnicas de aprendizaje automático. El artículo no pretende ser un trabajo científico que describa completamente el poder de los gráficos, sino que solo presente al lector a este mundo asombroso y complejo. La publicación es perfecta, tanto para profesionales endurecidos por la batalla que aún no están familiarizados con la presentación de gráficos en el aprendizaje profundo, como para principiantes en este campo.

Introducción

Destacar automáticamente las características importantes necesarias para resolver un problema es una de las principales razones para el uso exitoso del aprendizaje automático. Pero tradicionalmente, cuando se trabaja con gráficos, los enfoques de aprendizaje automático se han basado en heurísticas definidas por el usuario para extraer las características de codificación de la información de gráficos estructurales. Sin embargo, la tendencia de los últimos años ha cambiado: los enfoques están surgiendo cada vez más en los que aprenden automáticamente a codificar la estructura gráfica en inversiones de baja dimensión utilizando métodos de aprendizaje profundo y reducción de dimensiones no lineal.

En el aprendizaje automático en gráficos, se pueden distinguir dos problemas centrales: la inclusión de información sobre la estructura del gráfico en el modelo (es decir, una forma simple de codificar esta información en el vector de características) y la reducción en la dimensión del vector de características.

( ), . , , .

?

, , : ?

— . , , ( ) [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 de febrero de 2018.

Referencias

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