Ce sunt încorporarea graficelor?

Încorporarea graficului învață o mapare de la o rețea la un spațiu vector, păstrând în același timp proprietățile relevante ale rețelei.

Spațiile vectoriale sunt mai predispuse științei datelor decât graficele. Graficele conțin margini și noduri, acele relații de rețea pot folosi doar un subset specific de matematică, statistici și învățare automată. Spațiile vectoriale au un set de instrumente mai bogat din acele domenii. În plus, operațiile vectoriale sunt adesea mai simple și mai rapide decât operațiunile grafice echivalente.

Un exemplu este găsirea celor mai apropiați vecini. Puteți efectua „hamei” de la nod la alt nod dintr-un grafic. În multe grafice din lumea reală după câteva hamei, există puține informații semnificative (de exemplu, recomandări ale prietenilor prietenilor prietenilor). Cu toate acestea, în spațiile vectoriale, puteți utiliza metricele distanței pentru a obține rezultate cantitative (de exemplu, distanța euclidiană sau similitudinea cosinusului). Dacă aveți valori cantitative ale distanței într-un spațiu vectorial semnificativ, găsirea vecinilor mai apropiați este simplă.

„ Tehnici de încorporare a graficelor, aplicații și performanță: un sondaj „este un articol de ansamblu care intră mai în detaliu.

Ce sunt graficele încorporate? „Graficele încorporări” este o zonă fierbinte astăzi în învățarea automată. Practic înseamnă găsirea „reprezentării vectoriale latente” a graficelor care surprinde topologia (în sens foarte de bază) a graficului. Putem face această „reprezentare vectorială” bogată luând în considerare și relațiile vârf-vârf, informații despre margini etc. Există aproximativ două niveluri de încorporări în grafic (desigur, putem oricând să definim mai multe niveluri împărțind logic întregul grafic în subgrafe de diferite dimensiuni):

• Vertex Embeddings – Aici găsiți reprezentarea vectorială latentă a fiecare vârf din graficul dat. Apoi puteți compara diferiții vârfuri trasând acești vectori în spațiu și, în mod interesant, vârfurile „similare” sunt reprezentate mai aproape unul de celălalt decât cele care sunt diferite sau mai puțin legate. Aceasta este aceeași lucrare care se face în „DeepWalk” de Perozzi.
• Încorporări grafice – Aici găsiți reprezentarea vectorială latentă a întregului grafic în sine. De exemplu, aveți un grup de compuși chimici pentru care doriți să verificați ce compuși sunt similari între ei, câte tipuri de compuși există în grup (clustere) etc. Puteți utiliza acești vectori și le puteți trasa în spațiu și găsiți toate informațiile de mai sus. Aceasta este lucrarea realizată în „Deep Graph Kernels” de către Yanardag.

Aplicații – Privind cu atenție, încorporările sunt reprezentări „latente”, ceea ce înseamnă că dacă un grafic are un | V | * | V | matricea de adiacență unde | V | = 1M, este greu de utilizat sau de procesat un număr de 1M * 1M într-un algoritm. Deci, încorporarea latentă a dimensiunii „d”, unde d < < | V |, ar face matricea de adiacență | V | * d și relativ mai ușor de utilizat. O altă aplicație ar putea fi – Luați în considerare un scenariu simplu în care dorim să recomandăm produse persoanelor care au interese similare într-o rețea socială.Prin obținerea încorporărilor pe vertex (aici înseamnă reprezentarea vectorială a fiecărei persoane), putem găsi cele similare trasând acești vectori și acest lucru facilitează recomandarea. Acestea sunt unele aplicații și altele. Puteți consulta o lucrare de sondaj drăguță – Tehnici de încorporare a graficului, un sondaj .

De unde a venit totul? Au existat o mulțime de lucrări în acest domeniu și aproape toate provin din cercetările inovatoare în domeniul procesării limbajului natural – „Word2Vec” de Mikolov. Dacă doriți să începeți cu cercetarea privind încorporarea graficelor, aș recomanda să înțelegeți mai întâi cum funcționează Word2Vec. Puteți găsi explicații frumoase – Învățarea parametrilor Word2Vec explicată și Lectura Stanford . Apoi, puteți să treceți la ziarele pe care le-ați enumerat. Aceste lucrări pot fi clasificate ca:

• Lucrări bazate pe „Vertex Embeddings”: – DeepWalk , Node2Vec , LINE .

• Funcționează pe baza „Încorporări grafice”: – Kerneluri grafice profunde , Subgraph2Vec .

Comentarii

• Wowww !! Acesta este absolut un răspuns perfect. Mulțumesc mult 🙂 Foarte bine 🙂 🙂
• Salut Mausam Jain. Puteți să-mi spuneți dacă pot folosi încorporări grafice pentru a identifica noduri importante din rețea?
• Bună, Volka. Pentru a răspunde la această întrebare, trebuie să știu la ce tip de grafic lucrați; este twitter, facebook, reddit sau altceva?
• Vă mulțumim pentru răspuns. Lucrez de fapt într-o rețea socială în care vreau să identific cei mai sociali oameni 🙂
• Iată ‘ o versiune mai elaborată a acestui răspuns. spredatascience.com/…

În lucrare O teoremă a limitei centrale pentru o încorporare omnibusă a graficelor de produse cu punct aleatoriu de Levin et.al. hârtie, un tip specific de încorporare a graficului (încorporarea Omnibus) definește încorporarea graficului ca metodologie „în care vârfurile unui grafic sunt mapate la vectori într-un spațiu euclidian cu dimensiuni reduse”. Verificați linkul pentru mai multe informații.

Comentarii

• bun venit pe forum. Dacă doriți să menționați o lucrare, vă rugăm să notați numele acesteia și ca parte a textului (deoarece linkurile pot fi rupte).