Nedávno jsem narazil na vkládání grafů, například DeepWalk a LINE. Stále však nemám jasnou představu, co se rozumí vložením grafu a kdy jej použít (aplikace)? Jakékoli návrhy jsou vítány!
Komentáře
- Vložení grafu je vložení pro grafy! Trvá tedy graf a vrátí vložení pro graf, hrany nebo vrcholy. Vkládání umožňuje hledání podobnosti a obecně usnadňuje strojové učení poskytováním reprezentací .
- @Emre, co to znamená vložením? 🙂
- Jak význam vložení jde, opravování věcí na něco. Vkládání grafů je něco jako fixování vrcholů na povrch a kreslení hran, které představují řekněme síť. Příklad je jako rovinný graf, který lze vložit na povrch $ 2D $ bez přechodu hrany. Hmotnosti lze přiřadit hranám a příslušným délkám hran viz. pomáhá nám porozumět / odhadnout, jak @Emre zmínil hledání podobnosti atd.
- @KiriteeGak Díky 🙂 Jaké jsou jejich aplikace v reálném světě? Říká se, že je lze použít pro doporučení a tak? ale jak?
- Doporučení videa z YouTube lze zobrazit jako model, kde video, které právě sledujete, je uzel, ve kterém se nacházíte, a další videa, která jsou ve vašem doporučení, jsou ta, která se vám nejvíce podobají o tom, co obdobní uživatelé sledovali dále, a samozřejmě o mnoha dalších faktorech, což je obrovská síť, kterou je třeba procházet. Tento dokument je dobrým přečtením o porozumění aplikaci.
Odpověď
Vkládání grafů se učí mapování ze sítě do vektorového prostoru při zachování příslušných síťových vlastností.
Vektorové prostory jsou přístupnější vědě o datech než grafy. Grafy obsahují hrany a uzly, tyto síťové vztahy mohou používat pouze konkrétní podmnožinu matematiky, statistik a strojového učení. Vektorové prostory mají z těchto domén bohatší sadu nástrojů. Vektorové operace jsou navíc často jednodušší a rychlejší než ekvivalentní operace s grafy.
Jedním příkladem je hledání nejbližších sousedů. „Chmel“ z uzlu do jiného uzlu můžete provádět v grafu. V mnoha grafech reálného světa po několika chmelech je málo smysluplných informací (např. Doporučení přátel přátel přátel). Ve vektorových prostorech však můžete použít metriky vzdálenosti k získání kvantitativních výsledků (např. Euklidovská vzdálenost nebo kosinová podobnost). Pokud máte metriky kvantitativní vzdálenosti ve smysluplném vektorovém prostoru, hledání nejbližších sousedů je jednoduché.
„ Techniky, aplikace a výkon při vkládání grafů: průzkum „je souhrnný článek, který jde do větších podrobností.
Odpověď
Co jsou vkládání grafů? „Vkládání grafů“ je dnes v oblasti strojového učení aktuální oblastí. V podstatě to znamená najít „latentní vektorovou reprezentaci“ grafů, která zachycuje topologii (v základním smyslu) grafu. Tuto „vektorovou reprezentaci“ můžeme obohatit také tím, že vezmeme v úvahu vztahy vrchol-vrchol, informace o hraně atd. V grafu jsou zhruba dvě úrovně vložení (samozřejmě můžeme kdykoli definovat více úrovní logickým rozdělením celého grafu na podgrafy různých velikostí):
- Vertex Embeddings – zde najdete latentní vektorovou reprezentaci každý vrchol v daném grafu. Poté můžete porovnat různé vrcholy vynesením těchto vektorů do prostoru a zajímavě „podobné“ vrcholy se vykreslí blíže k sobě než ty, které jsou odlišné nebo méně příbuzné. Jedná se o stejnou práci, jakou provádí Perozzi v „DeepWalk“.
- Vkládání grafů – zde najdete latentní vektorovou reprezentaci celého grafu samotného. Například máte skupinu chemických sloučenin, u kterých chcete zkontrolovat, které sloučeniny jsou si navzájem podobné, kolik typů sloučenin ve skupině je (shluky) atd. Tyto vektory můžete použít a vykreslit je do prostoru a najděte všechny výše uvedené informace. Toto je práce, kterou provádí Yanardag v „Deep Graph Kernels“.
Aplikace – Při pečlivém pohledu jsou vložení „latentní“ reprezentace, což znamená, že pokud má graf | V | * | V | matice sousedství kde | V | = 1M, je těžké použít nebo zpracovat čísla 1M * 1M v algoritmu. Takže latentní vložení dimenze „d“, kde d < < | V |, by vytvořilo matici sousedství | V | * d a relativně snadnější k použití. Další aplikací by mohlo být – Zvažte jednoduchý scénář, kdy chceme doporučit produkty lidem, kteří mají podobné zájmy v sociální síti.Získáním vložení vrcholů (zde to znamená vektorové znázornění každé osoby) můžeme najít podobné vynesením těchto vektorů, což usnadňuje doporučení. Jedná se o některé aplikace a existují i jiné. Můžete se podívat na pěkný průzkum – Techniky vkládání grafů, průzkum .
Odkud to všechno přišlo? V této oblasti bylo provedeno mnoho prací a téměř vše pochází z průkopnického výzkumu v oblasti zpracování přirozeného jazyka – „Word2Vec“ od Mikolova. Pokud chcete začít s výzkumem vkládání grafů, doporučil bych nejprve pochopit, jak Word2Vec funguje. Můžete najít pěkná vysvětlení – vysvětleno učení parametru Word2Vec a Stanfordská přednáška . Poté můžete přejít na papíry, které jste uvedli. Tyto práce lze kategorizovat jako:
-
Práce založené na „Vertex Embeddings“: – DeepWalk , Node2Vec , LINE .
-
Funguje na základě „Graph Embeddings“: – Deep Graph Kernels , Subgraph2Vec .
Komentáře
- Wowww !! To je naprosto dokonalá odpověď. Díky moc 🙂 Velmi dobře 🙂
- Ahoj Mausam Jain. Můžete mi prosím dát vědět, jestli mohu pomocí vložení grafů identifikovat důležité uzly v síti?
- Ahoj, Volko. K zodpovězení této otázky potřebuji vědět, na jakém typu grafu pracujete; je to twitter, facebook, reddit nebo něco jiného?
- Děkuji za odpověď. Vlastně pracuji v sociální síti, kde chci identifikovat ty nejvíce sociální lidi 🙂
- Zde ' je propracovanější verze této odpovědi. towardsdatascience.com/…
odpověď
V příspěvku Centrální limitní věta pro souhrnné vložení náhodných bodových grafů produktů od Levina et.al. papír, specifický typ vkládání grafů (vkládání Omnibus) definuje vkládání grafů jako metodiku „ve které jsou vrcholy grafu mapovány na vektory v nízkodimenzionálním euklidovském prostoru.“ Další informace najdete v odkazu.
Komentáře
- vítejte ve fóru. Pokud se chcete zmínit o příspěvku, zapište si také jeho název jako součást textu (protože odkazy mohou být nefunkční).