Wat is het insluiten van grafieken?

Het insluiten van grafieken leert een mapping van een netwerk naar een vectorruimte, terwijl de relevante netwerkeigenschappen behouden blijven.

Vectorruimten zijn meer geschikt voor datawetenschap dan grafieken. Grafieken bevatten randen en knooppunten, die netwerkrelaties kunnen alleen een specifieke subset van wiskunde, statistiek en machine learning gebruiken. Vectorruimten hebben een rijkere toolset van die domeinen. Bovendien zijn vectorbewerkingen vaak eenvoudiger en sneller dan de equivalente grafiekbewerkingen.

Een voorbeeld is het vinden van naaste buren. U kunt “hops” uitvoeren van knooppunt naar een ander knooppunt in een grafiek. In veel real-world grafieken is er na een paar keer springen weinig zinvolle informatie (bijv. Aanbevelingen van vrienden van vrienden van vrienden). In vectorruimten kunt u echter afstandsmetrieken gebruiken om kwantitatieve resultaten te krijgen (bijv.Euclidische afstand of Cosinus gelijkenis). Als u beschikt over kwantitatieve afstandsstatistieken in een zinvolle vectorruimte, is het eenvoudig om de dichtstbijzijnde buren te vinden.

“ Technieken, toepassingen en prestaties voor het inbedden van grafieken: een onderzoek “is een overzichtsartikel dat meer in detail gaat.

Wat zijn Graph Embeddings? “Graph Embeddings” is tegenwoordig een hot topic in machine learning. Het betekent in feite het vinden van “latente vectorrepresentatie” van grafieken die de topologie (in zeer basale zin) van de grafiek vastleggen. We kunnen deze “vectorrepresentatie” rijk maken door ook rekening te houden met de vertex-vertex-relaties, randinformatie enz. Er zijn grofweg twee niveaus van inbedding in de grafiek (we kunnen natuurlijk altijd meer niveaus definiëren door de hele grafiek logisch in te delen in subgraphs van verschillende groottes):

• Vertex Embeddings – Hier vind je een latente vectorweergave van elk hoekpunt in de gegeven grafiek. Je kunt dan de verschillende hoekpunten vergelijken door deze vectoren in de ruimte uit te zetten en interessant genoeg worden “gelijkaardige” hoekpunten dichter bij elkaar geplot dan degene die ongelijk of minder gerelateerd zijn. Dit is hetzelfde werk dat wordt gedaan in “DeepWalk” door Perozzi.
• Graph Embeddings – Hier je vindt de latente vectorweergave van de hele grafiek zelf. U heeft bijvoorbeeld een groep chemische verbindingen waarvan u wilt controleren welke verbindingen op elkaar lijken, hoeveel soorten verbindingen er in de groep zitten (clusters) etc. U kunt deze vectoren gebruiken en deze in de ruimte en vind alle bovenstaande informatie. Dit is het werk dat wordt gedaan in “Deep Graph Kernels” door Yanardag.

Toepassingen – Door goed te kijken, zijn embeddings “latente” representaties, wat betekent dat als een graaf een | V | heeft * | V | aangrenzende matrix waar | V | = 1M, het is moeilijk om 1M * 1M-getallen in een algoritme te gebruiken of te verwerken. Dus latente insluiting van dimensie “d”, waarbij d < < | V |, de aangrenzende matrix | V | * d en relatief gemakkelijker te gebruiken. Een andere toepassing zou kunnen zijn: Beschouw een eenvoudig scenario waarin we producten willen aanbevelen aan mensen met dezelfde interesses in een sociaal netwerk.Door vertex-inbeddingen te krijgen (hier betekent het vectorweergave van elke persoon), kunnen we de vergelijkbare vinden door deze vectoren uit te zetten en dit maakt aanbeveling eenvoudig. Dit zijn enkele toepassingen en er zijn andere. U kunt verwijzen naar een mooi onderzoeksartikel – Graph Embedding Techniques, a Survey .

Waar kwam het allemaal vandaan? Er is veel werk op dit gebied gedaan en bijna alles komt van het baanbrekende onderzoek op het gebied van natuurlijke taalverwerking – “Word2Vec” door Mikolov. Als je aan de slag wilt met het onderzoek naar het inbedden van grafieken, zou ik aanraden om eerst te begrijpen hoe Word2Vec werkt. Je kunt leuke uitleg vinden – Woord2Vec parameter leren uitgelegd en Stanford Lecture . Vervolgens kunt u naar de papieren gaan die u hebt vermeld. Die werken kunnen worden gecategoriseerd als:

• Werken gebaseerd op “Vertex Embeddings”: – DeepWalk , Node2Vec , LINE .

• Werkt op basis van “Graph Embeddings”: – Deep Graph Kernels , Subgraph2Vec .

Reacties

• Wowww !! Dit is absoluut een perfect antwoord. Heel erg bedankt 🙂 Heel goed gedaan 🙂
• Hoi Mausam Jain. Kun je me alsjeblieft laten weten of ik graafinbeddingen kan gebruiken om belangrijke knooppunten in het netwerk te identificeren?
• Hallo, Volka. Om deze vraag te beantwoorden, moet ik weten aan wat voor soort grafiek u werkt; is het twitter, facebook, reddit of iets anders?
• Bedankt voor je antwoord. Ik werk eigenlijk in een sociaal netwerk waar ik de meest sociale mensen wil identificeren 🙂
• Hier ‘ is een meer uitgebreide versie van dit antwoord. directiondatascience.com/…

In de paper Een centrale limietstelling voor een omnibus-inbedding van willekeurige puntproductgrafieken door Levin et.al. paper, definieert een specifiek type inbedding van een grafiek (de omnibus-inbedding) het inbedden van grafieken als een methodologie “waarin de hoekpunten van een grafiek worden toegewezen aan vectoren in een laagdimensionale Euclidische ruimte.” Controleer de link voor meer informatie.

Reacties

• welkom op het forum. Als je een paper wilt vermelden, schrijf dan ook de naam ervan als onderdeel van de tekst (omdat links kunnen worden verbroken).