يزداد تعقيد تقديم البيانات للتعلم العميق كل يوم. أصبحت الشبكات العصبية الرسومية ( GNNs ) واحدة من الاختراقات في السنوات الأخيرة. ولكن لماذا تكتسب الرسوم البيانية بالضبط شعبية متزايدة في تعلم الآلة؟

الهدف النهائي لروايتي هو عرض عام للرسوم البيانية في تقنيات التعلم الآلي. لا تدعي المقالة أنها عمل علمي يصف بشكل كامل القوة الكاملة للرسوم البيانية ، ولكنه يقدم القارئ فقط إلى هذا العالم المذهل والمعقد. المنشور مثالي ، سواء بالنسبة للمهنيين المحنكين الذين لم يكونوا على دراية بعد بعرض الرسوم البيانية في التعلم العميق ، والمبتدئين في هذا المجال.

المقدمة

يُعد إبراز الميزات المهمة اللازمة لحل مشكلة تلقائيًا أحد الأسباب الرئيسية لاستخدام التعلم الآلي بنجاح. ولكن تقليديًا ، عند العمل باستخدام الرسوم البيانية ، اعتمدت مناهج التعلم الآلي على الاستدلال المعرف بواسطة المستخدم لاستخراج ميزات التشفير لمعلومات الرسم البياني الهيكلي. ومع ذلك ، فقد تغير اتجاه السنوات الأخيرة: بدأت المناهج في الظهور بشكل متزايد حيث يتعلمون تلقائيًا ترميز بنية الرسم البياني في الاستثمارات منخفضة الأبعاد باستخدام طرق التعلم العميق وتقليل الأبعاد غير الخطية.

في التعلم الآلي على الرسوم البيانية ، يمكن تمييز مشكلتين مركزيتين: تضمين معلومات حول هيكل الرسم البياني في النموذج (أي طريقة بسيطة لتشفير هذه المعلومات في ناقل الميزة) وتقليل أبعاد متجه الميزة.

لاستخراج المعلومات الهيكلية من الرسوم البيانية ، غالبًا ما تستند المناهج الآلية التقليدية إلى إحصاءات موجزة للرسوم البيانية (على سبيل المثال ، معاملات التجميع) ، أو وظائف النواة ، أو الوظائف المصممة بعناية لقياس هياكل الأحياء المحلية. ومع ذلك ، فإن هذه الأساليب محدودة ، لأن هذه الحلول الهندسية لا يمكن تكييفها في عملية التعلم ، وتطويرها عملية شاقة ومكلفة.

لماذا الرسوم البيانية؟

بالحديث عن الرسوم البيانية كوحدات هيكلية لتمثيل البيانات ، يمكنك أن تسأل نفسك سؤالًا بسيطًا: لماذا الرسوم البيانية؟

— . , , ( ) [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 فبراير 2018.

المراجع

الشبكات العصبية الرسومية: مراجعة الطرق وتمثيل التطبيقات
التعلم على الرسوم البيانية: الأساليب والتطبيقات