Graph: A Survey of Graph Neural Networks, Embedding, Tasks and Applications

(SBQI "4VSWFZPG(SBQI/FVSBM/FUXPSLT &NCFEEJOH 5BTLTBOE"QQMJDBUJPOT

Kenshi Uchihashi uchi_k @wednesdaymuse About me nlpaper.challenge ӡӦ Freelance Machine
Learning ɹɹɹɹɹEngineer / Researcher former ະ౿16, ژେ৘ใӃ, FreakOut Machine Learning Engineer

αʔϕΠํ๏ • ؔ࿈Ωʔϫʔυ ݚڀऀͷચ͍ग़͠ ◦ (PPHMF4DIPMBS΁ • ॏཁ࿦จͷબఆ ◦ ͢ͰʹධՁ͕ఆ·ͬͨ΋ͷʹ͍ͭͯ͸Ҿ༻਺
◦ ೥ʹग़൛͞Εͨ΋ͷʹ͍ͭͯ͸಺༰ͰධՁ༗໊ݚڀऀ΍ϥϘ ◦ ༗ࣝऀʹฉ͘ • $POGFSFODF ◦ /FVS*14 *$-3 *$.- """* ʜ ◦ ,%% 888 ʜ ◦ BSYJW ʜ • ࿦จͷ෼໺͸࠷΋ߩݙ͕େ͖͍ͱࢥͬͨ෼໺ʹׂΓৼΓ • ྫ͑͹$7΁ͷΞϓϦέʔγϣϯ࿦จͰ΋৽ͯ͘͠༗༻ͳ($/ͷϑϨʔϜ ϫʔΫΛఏҊ͍ͯ͠Ε͹෼໺͸($/ΛׂΓ౰ͯΔɺͳͲ

஫ҙ • ਤ΍਺ࣜ͸࿦จ͔ΒҾ༻͍ͯ͠·͢ ◦ Ҿ༻ݩͷ࿦จ͸λΠτϧͷ࿦จͰ͢ • ҎԼͷ஌ࣝΛલఏͱ͠·͢ ◦ χϡʔϥϧωοτϫʔΫͷجૅ஌ࣝ ◦
.-1 DPOWPMVUJPO QPPMJOH $// 3// -45. ʜ ◦ άϥϑʹؔ͢Δجૅ༻ޠ ◦ ϊʔυ Τοδ ༗޲ແ޲ ॏΈ෇͖ͳ͠ ྡ઀ߦྻ άϥϑϥϓϥγΞϯ ◦ ͦͷଞ ◦ BEWFSTBSJBMBUUBDL TVCUSFF ʜ • ಛʹஅΓ͕ͳ͚Ε͹͍͍ͩͨϧʔϓ΍ଟॏΤοδΛ࣋ͨͳ͍άϥϑΛѻ͍ͬͯ·͢ • ਺ࣜ͸௥Θͣɺ࿦จ಺Ͱॏཁͳ΋ͷʹߜͬͯղઆ͢ΔελΠϧͰ͢ • ࿦จͷࡉ͔͍ͱ͜Ζ͸঺հͰ͖ͳ͍ͷͰɺݚڀͷେ͖ͳྲྀΕॏࢹͰ͢

஫ҙ • ॏཁ࿦จຊɺؔ࿈࿦จຊʹ·ͱΊ·ͨ͠ʢൃද൛Ͱ͸൒෼͘Β͍ʹݮΒͯ͠ ͍·͢ʣ • ൃදͰ͸جૅతͳ಺༰ʹ͠΅Γ·ͨ͠ ◦ (// ◦ ($/
◦ PUIFS(//T ◦ (SBQI3FQSFTFOUBUJPO&NCFEEJOH ◦ /PEFGPDVTFE5BTL ◦ (SBQIGPDVTFE5BTL ◦ 5BTLT ◦ $PNCJOBUPSJBM-PHJDBM "EWFSTBSJBM"UUBDL .BUDIJOH FUD ◦ "QQMJDBUJPOT ◦ $7 /-1 3FMBUJPO&YUSBDUJPO 3FDPNNFOEBUJPO .PMFDVMBS (SBQI(FOFSBUJPO 1IZTJDT • ൣғΛ޿͗ͨ͘͢͠ײ͋ΔΜͰ͕͢ɺޙ೔VQ͢ΔࢿྉͰิ׬͍ͩ͘͞

/FVSBM/FUXPSLTPO(SBQI

5IF(SBQI/FVSBM/FUXPSL.PEFM #Graph Neural Network *&&&5// 4DBSTFMMJ 'SBODP 6OJWFSTJUZPG4JFOB BOE(PSJ .BSDPBOE5TPJ
"I$BOE)BHFOCVDIOFS .BOE.POGBSEJOJ ( DJUBUJPOT ྡ઀Τοδϥϕϧ ϊʔυঢ়ଶ ྡ઀ϊʔυϥϕϧ ϊʔυϥϕϧ • ࠷ۙ๣ϊʔυͷ৘ใΛ࠶ؼతʹ BHHSFHBUF͢Δ • LճͷBHHSFHBUJPOʹΑͬͯɺLIPQ ͷ৘ใ͕औಘͰ͖Δ • ༧ΊܾΊΒΕͨλΠϜεςοϓͰֶश͕ ऴྃ͢ΔͷͰԕ͘ͷϊʔυͷ৘ใ͕औΕ ͳ͍͜ͱ͕͋Δ ϊʔυ͕ϝοηʔδΛ఻೻͍ͯ͘͠࢓૊ΈͰ(//Λಋग़ͨ͠ άϥϑߏ଄Λͦͷ··χϡʔϥϧωοτʹམͱ͠ࠐΊΔΑ͏ʹ

w ೖྗϊʔυू߹ΛΫϥελϦϯά͍ͯ͘͠ w ΛݸͷΫϥελʹ෼͚ͨ݁Ռ͕ w ͸ྡ઀ؔ܎͕͋Δͱ͜ΖͷΈ஋Λ࣋ͭε ύʔεͳϑΟϧλʔ 4QFDUSBM/FUXPSLTBOE-PDBMMZ$POOFDUFE/FUXPSLTPO(SBQIT #GCN #SpatialGCN
#SpectralGCN #Spectral Clustering *$-3 +PBO#SVOB /FX:PSL6OJWFSTJUZ 8PKDJFDI;BSFNCB "SUIVS4[MBN :BOO-F$VO DJUBUJPO άϥϑʹ͓͚Δہॴੑͱղ૾౓Λఆٛ͠ɺ$//Λάϥϑʹ֦ு͢Δํ๏Λ 4QBUJBMͱ4QFDUSBMͷछྨఏҊ ྡ઀ߦྻΛ༻͍ͨہॴੑ NVMUJTDBMFDMVTUFSJOHʹΑΔղ૾౓ ϊʔυू߹ ྡ઀ߦྻ ᮢ஋Λద౰ʹઃఆ͢Δ͜ͱͰہॴੑΛදݱ Ϋϥελʹؚ·ΕΔશϊʔυͷಛ௃ྔΛೖ ྗͱ͠ɺ୅ද஋ͱͯ͠Ұͭͷಛ௃ྔΛग़ྗ ϓʔϦϯά 4QBUJBM$POTUSVDUJPO ϑΟϧλʔ

4QFDUSBM/FUXPSLTBOE-PDBMMZ$POOFDUFE/FUXPSLTPO(SBQIT #Graph Neural Network #Spectral Clustering #Fourier Transform *$-3 +PBO#SVOB
/FX:PSL6OJWFSTJUZ 8PKDJFDI;BSFNCB "SUIVS4[MBN :BOO-F$VO DJUBUJPO ϑʔϦΤม׵͸೾ܗΛप೾਺੒෼ʹ෼ղ͢Δ͕ɺάϥϑϑʔϦΤม׵͸άϥϑ্Ͱఆٛ͞Εͨ৴ ߸ʹରͯ͠৴߸ͷٸफ़͞Λఆٛ͠ɺٸफ़͞͝ͱʹ੒෼෼ղ άϥϑϥϓϥγΞϯͷݻ༗஋ܭࢉͰٸफ़͞੒෼΁ͷ෼ղ͕Մೳ DPOWPMVUJPO͸'PVSJFSEPNBJOʹ͓͚Δཁૉੵʹ૬౰͢Δͱ͍͏ఆཧΛ༻͍ͯɺཁૉੵͰ DPOWPMVUJPO͢Δ͜ͱ͕Ͱ͖ΔΑ͏ʹͳΔ ཁૉੵʹରͯ͠ٯϑʔϦΤม׵ΛͱΔ ݻ༗஋ܭࢉͱݻ༗ϕΫτϧͷੵͷܭࢉίετ͕େ͖͍ 4QFDUSBM$POTUSVDUJPO ϑʔϦΤجఈʹରԠͨ͠άϥϑϥϓϥγΞϯͷݻ༗ϕΫτϧͷ݁߹܎਺ΛมԽ͞ ͤΔ͜ͱͰάϥϑ্ͷಛ௃ྔม׵͕ఆٛͰ͖Δ ݻ༗ϕΫτϧ

$POWPMVUJPOBM/FVSBM/FUXPSLTPO(SBQIT XJUI'BTU-PDBMJ[FE4QFDUSBM'JMUFSJOH #GCN #Spectral Filtering #Chebyshev Polynomials /FVS*14 .JDIBËM%F⒎FSSBSE &1'-
9BWJFS#SFTTPO 1JFSSF7BOEFSHIFZOTU DJUBUJPOT ݻ༗஋ߦྻ νΣϏγΣϑଟ߲ࣜۙࣅʹΑͬͯݻ༗஋෼ղΛճආ͠ɺ($/ͷܭࢉྔΛԼ͛Δ νΣϏγΣϑଟ߲ࣜۙࣅ ݻ༗஋ܭࢉͱݻ༗ϕΫτϧͷੵͷܭࢉίετ͕ େ͖͍໰୊Λ͔ͳΓղܾ 'PVSJFSEPNBJOͰఆٛ͞ΕͨϑΟϧλ Λ༻͍ͨ৞ΈࠐΈ͸ɺ ݻ༗஋ͷεέʔϦϯά ଟ߲ࣜۙࣅͨ͠ํ͕ਫ਼౓΋্͕ͬͨ νΣϏγΣϑଟ߲ࣜͷ࣍਺,͕ϑΟϧλαΠζ ͱରԠ͍ͯ͠Δ

4FNJ4VQFSWJTFE$MBTTJpDBUJPOXJUI(SBQI$POWPMVUJPOBM/FUXPSLT #GCN #Semi-Supervised Learning *$-3 5IPNBT/,JQG .BY8FMMJOH DJUBUJPOT ྡ઀ϊʔυͷ৞ΈࠐΈͷΈͰ4QFDUSBM($/ͷۙࣅ͕Ͱ͖Δ͜ͱΛࣔͨ͠ w
νΣϏγΣϑଟ߲ࣜۙࣅͷϞσϧͷ,ͷ৔ ߹ʢ࠷ۙ๣ͷΈࢀর͢Δʣ w Ϟσϧͷදݱೳྗ͸Լ͕Δ w %//ͷΑ͏ʹɺޯ഑ফࣦʹରԠ͢ΔςΫ χοΫΛಋೖʢSFOPSNBMJ[BUJPOUSJDLʣ աֶशͷ཈੍ޮՌʹΑͬͯɺۙࣅͨ͠΄͏͕ਫ਼౓͕ྑ͘ͳ͍ͬͯΔ ଟ߲ࣜۙࣅͨ͠ํ͕ਫ਼౓΋্͕ͬͨ ϥϕϧ͕෇͍͍ͯΔσʔλʹ͍ͭͯɺTPGUNBYDSPTTFOUSPQZʹΑֶͬͯश͢Δ ඪ४తͳ($/ͱͯ͠ҎԼͷఆࣜԽΛͨ͠

(BUFE(SBQI4FRVFODF/FVSBM/FUXPSLT #GNN #LSTM #Sequence *$-3 :VKJB-J %FQBSUNFOUPG$PNQVUFS4DJFODF 6OJWFSTJUZPG5PSPOUP %BOJFM5BSMPX .BSD#SPDLTDINJEU
BOE3JDIBSE;FNFM DJUBUJPOT w (//ͷঢ়ଶߋ৽͸࣮࣭3//͕ͩͬͨɺ͜͜Λ-45.΍(36ʹมߋ͢Δ w ޯ഑ܭࢉʹʢ"MNFJEB1JOFEBΞϧΰϦζϜͰ͸ͳ͘ʣ#155Λ࢖༻ w 4FRVFODFͳग़ྗΛֶशՄೳʹͳΓɺେ͖͘Ԡ༻෯͕૿͑ͨ -45.΍(36Ͱঢ়ଶߋ৽Λߦ͏(//Λಋग़ ίʔυͷ৴པੑධՁͳͲͷଟ༷ͳλεΫ΁ͷԠ༻Մೳੑ͕ੜ·Εͨ (36΍-45.ʹସ͑Δ ΑΓεϚʔτͳɺ࣌୅ʹԊͬͨఆࣜԽΛͨ͠

)PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT #GNN #WL test #Graph Isomorphism Network *$-3 ,FZVMV9V .*5
8FJIVB)V +VSF-FTLPWFD 4UFGBOJF+FHFMLB DJUBUJPOT (//TΛఆࣜԽ͠ɺ8-UFTUͱಉ౳ͷੑೳΛಘΔͨΊʹඞཁͳ੍໿Λಋग़ͨ͠ (//TͷఆࣜԽ ϊʔυWͷಛ௃ϕΫτϧ • "((3&("5&ͱ$0.#*/&ͷTUFQʹ෼͚Δ • (SBQIGPDVTFE5BTLͰ͸3&"%065Ͱશϊʔυ৘ใΛू໿ FY (SBQI4"(& FY ($/ "((3&("5&ͱ$0.#*/&ʹԿΛબͿ͔Ͱطଘͷ(//T͸هड़Ͱ͖Δ • $0.#*/&ͳ͠

8FJIVB)V +VSF-FTLPWFD 4UFGBOJF+FHFMLB DJUBUJPOT "((3&("5&ͱ$0.#*/&Ͱهड़Ͱ͖Δ(//T͸άϥϑ෦෼ߏ଄ͷࣝผ ೳྗ͕8-TVCUSFFLFSOFMͱ౳ՁͰ͋Δ (//Tͷදݱೳྗͷߴ͞Λ෼ੳ͍ͨ͠ ཧ૝తʹ͸ɺҟͳΔάϥϑΛ׬શʹࣝผͰ͖Δ͔Ͳ͏͔͕άϥϑͷදݱೳྗͷߴ͞ Λද͕͢ɺ͜Ε͸ಉܕੑࣝผ໰୊ʢ/1ʣΛղܾͨ͜͠ͱʹͳΔʢʂʣ ݁࿦ 8-UFTUͰͷϊʔυͷಛ௃ϕΫτϧ͸POFIPUϕΫτϧͰTVCUSFFؒ ͷྨࣅੑͳͲΛಘΔ͜ͱ͸Ͱ͖ͳ͍ͷʹର͠ɺ(//TͰ͸Մೳ (//T͕8-UFTUΛֶशϕʔεͰ࿈ଓۭؒʹ֦ுͨ͠΋ͷʹͳ͍ͬͯΔ ͳͷͰɺFNCFEEJOH΍άϥϑߏ଄ؒͷEFQFOEFODZ΋औಘՄೳ

8FJIVB)V +VSF-FTLPWFD 4UFGBOJF+FHFMLB DJUBUJPOT "((3&("5&ʹ.&"/΍."9Λ࢖͏ͱ8-UFTUʹྼΔͷͰɺ46.Λ࢖͍·͠ΐ͏ ʢͨͩ͠ɺλεΫʹΑͬͯ͸͍͍ͱ͜Ζ΋͋Δʣ 8-UFTUอূͷ͋Δ(*/ʢ(SBQI*TPNPSQIJTN/FUXPSLʣΛఏҊ ࣗ෼ࣗ਎ʹద౰ͳ܎਺Λ͔͚ͯɺશͯͷྡ઀ϊʔυͱͷ࿨Λͱͬͯ.-1ʹೖྗ͢ Δͱ͍͏γϯϓϧͳߏ੒ʢ"((3&("5&ͷΈʣͰ΋ɺ ଞͷෳࡶͳϞσϧͱཧ࿦্ಉఔ౓ͷੑೳ͕ظ଴Ͱ͖Δɻ

(SBQI/FVSBM/FUXPSL • "OFXNPEFMGPSMFBSOJOHJOHSBQIEPNBJOT ◦ *+$// .BSDP(PSJ 6OJWFSTJUZPG4JFOB FUBM DJUBUJPOT ◦
(SBQI/FVSBM/FUXPSLΛఏҊ • (SBQI8BSQ.PEVMFBO"VYJMJBSZ.PEVMFGPS#PPTUJOHUIF1PXFSPG (SBQI/FVSBM/FUXPSLT ◦ BS9JW ,BUTVIJLP*TIJHVSP 1SFGFSSFE/FUXPSLT FUBM DJUBUJPOT ◦ (//ͷදݱೳྗͷ௿͞Λ໰୊ࢹ͠ɺදݱೳྗΛ্͛Δ(SBQI8BSQ.PEVMF ʢ(81ʣΛఏҊɺখ͞ΊͷάϥϑͰ͋Δඞཁ͕͋Δ͕ɺಛʹ૑ༀͰ݁ՌΛग़͢ • 8FJTGFJMFSBOEMFNBOHPOFVSBM)JHIFSPSEFSHSBQIOFVSBMOFUXPSLT ◦ """* $ISJTUPQIFS.PSSJT FUBM DJUBUJPOT ◦ )PX1PXFSGVM"SFʙͷ݁ՌΛड͚ͯɺߴ࣍ͷ8-TVCUSFFLFSOFMʹର͢Δ (//Λߏங

(SBQI/FVSBM/FUXPSL • -FBSOJOH$POWPMVUJPOBM/FVSBM/FUXPSLTGPS(SBQIT ◦ *$.- .BUIJBT/JFQFSU /&$-BCT&VSPQF FUBM DJUBUJPOT ◦
8-HSBQILFSOFMͰάϥϑΛલॲཧͯ͠$//ʹೖΕΔ1BUDIZTBOΛఏҊ • 8BWFMFUTPO(SBQITWJB4QFDUSBM(SBQI5IFPSZ ◦ "QQMJFEBOE$PNQVUBUJPOBM)BSNPOJD"OBMZTJT %BWJE, )BNNPOE FUBM DJUBUJPOT ◦ άϥϑ৴߸ॲཧͷจ຺ͰΑ͘Ҿ༻͞ΕΔ࿦จ • 5IF&NFSHJOH'JFMEPG4JHOBM1SPDFTTJOHPO(SBQIT&YUFOEJOH)JHI %JNFOTJPOBM%BUB"OBMZTJTUP/FUXPSLTBOE0UIFS*SSFHVMBS%PNBJOT ◦ "*&&&4JHOBM1SPDFTTJOH.BHB[JOF %*4IVNBO &1'- FUBM DJUBUJPOT ◦ άϥϑ৴߸ॲཧͷจ຺ͰΑ͘Ҿ༻͞ΕΔ࿦จ

(SBQI/FVSBM/FUXPSL • )JHIFSPSEFS(SBQI$POWPMVUJPOBM/FUXPSLT ◦ *$.- 4BNJ"CV&M)BJKB 6OJWFSTJUZPG4PVUIFSO$BMJGPSOJB FUBM DJUBUJPOT
◦ POFIPQͳྡ઀ߦྻ͔ΒNVMUJIPQͳྡ઀ߦྻ΁֦ுͨ͠($/ΛఏҊ • %ZOBNJD(SBQI$POWPMVUJPOBM/FUXPSLT ◦ BS9JW 'SBODP.BOFTTJ 8BZOBVU FUBM DJUBUJPOT ◦ ಈతʹมԽ͢Δάϥϑͷղੳ͕Մೳʹͳͬͨ • (SBQI6/FUT ◦ *$.- )POHZBOH(BP 5FYBT".6OJWFSTJUZ 4IVJXBOH+J DJUBUJPOT ◦ 6/FUTΛάϥϑͰ΋Ͱ͖ΔΑ͏ʹ͢ΔͨΊʹɺHSBQIQPPMJOHͱHSBQI VOQPPMJOHΛఆٛ

(SBQI3FQSFTFOUBUJPO

%FFQXBML0OMJOFMFBSOJOHPGTPDJBMSFQSFTFOUBUJPOT #Representation #Online Learning #Graph Embedding ,%% #SZBO1FSP[[J 3BNJ"M3GPV 4UFWFO4LJFOB
DJUBUJPOT άϥϑ্ͰϥϯμϜ΢ΥʔΫΛߦ͍ɺಘΒΕͨܥྻΛ4LJQHSBNʹೖྗ͢Δ͜ͱͰ ϊʔυͷ෼ࢄදݱΛಘΔ જࡏදݱΛॳظԽ ͋Δϊʔυ͔Βग़ൃͯ͠ϥϯμϜ ΢ΥʔΫΛߦ͏ ಘΒΕͨܥྻΛ4LJQHSBN΁ ೖྗ ؔ܎ੑͷ͍ۙϊʔυΛ༧ଌ͠ɺ άϥϑͷϕΫτϧදݱΛಘΔ ڞىͷ֬཰͚ͩͰ͸ͳ͘ɺજࡏදݱ΋Ұॹʹֶश͍ͨ͠ͷͰɺ જࡏදݱͷܭࢉίετΛԼ͛Δ޻෉͕͞Ε͍ͯΔ άϥϑͷಛ௃Λଊ͑ɺؔ܎ੑͷ͍ۙϊʔυΛۙ͘ʹ഑ஔͰ͖Δ

-*/&-BSHFTDBMF*OGPSNBUJPO/FUXPSL&NCFEEJOH #Graph Embedding #Edge Sampling 888 +JBO5BOH .JDSPTPGU3FTFBSDI"TJB FUBM DJUBUJPOT
௚઀ϦϯΫΛ࣋ͨͳ͍ϊʔυͰ΋͍ۙ͠ಛ௃Λ༗͍ͯ͠ΔͳΒߟྀͯ͠ &NCFEEJOH͢Δख๏ΛఏҊ ϩʔΧϧͳߏ଄ʢpSTUPSEFSQSPYJNJUZʣͱ άϩʔόϧͳߏ଄ʢTFDPOEPSEFSQSPYJNJUZ ڞ௨͍ͯ͠Δଞͷ௖఺͕ࣅ͍ͯΔ͔Ͳ͏͔Λධ Ձʣͷ྆ํΛߟྀͯ͠FNCFEEJOHΛߦ͏ pSTUPSEFSQSPYJNJUZ ɹɹ௚઀؍ଌ͞ΕΔϊʔυಉ࢜ͷۙ઀ؔ܎ second-order proximity: ɹɹಉ͡Α͏ͳྡ઀ؔ܎Λ࣋ͭۙ઀ϊʔυ ΤοδͷॏΈͷ෼ࢄ͕େ͖͘ͳΔͱֶश཰ͷௐ੔͕೉͘͠ͳΔͷͰΤοδαϯϓ ϦϯάΛ޻෉͍ͯ͠Δ 888 ,%%͔ΒEBUBNJOJOH ੺ /*14 *$.-͔ΒNBDIJOFMFBSOJOH ੨ $713 *$$7͔ΒDPNQVUFSWJTJPO ྘ ͰBVUIPSTOFUXPSLΛՄࢹԽ

OPEFWFD4DBMBCMF'FBUVSF-FBSOJOHGPS/FUXPSLT #Graph Embedding #DFS #DeepWalk ,%% "EJUZB(SPWFS 4UBOGPSE6OJWFSTJUZ +VSF-FTLPWFD DJUBUJPOT
%FFQ8BMLͷܥྻऔಘ͕3BOEPN8BMLͰ͋Δͱ͜ΖΛվળ͠ɺ άϥϑΒ͍͠ํ๏ΛఏҊ ෯༏ઌ୳ࡧͬΆ͍#SFBEUIpSTU 4BNQMJOHʢ#'4ʣͱਂ͞༏ઌ୳ࡧͬΆ͍ %FQUIpSTU4BNQMJOHʢ%'4ʣΛఆٛ #'4͹͔Γॏࢹɾɾɾۙྡͷؔ܎͔͠ݟΕͳ͍ɻ͜Ε·Ͱ͸͜Εͩͬͨɻ ɹɹɹɹɹɹɹɹɹɹಉ͡ϊʔυ͹͔Γࢀরͯ͠͠·͏ %'4͹͔Γॏࢹɾɾɾۙ๣ΛΑΓԕ͘ͷϊʔυ͔Βߏ੒͢Δɻ ɹɹɹɹɹɹɹɹɹɹͨͩ͠෼ࢄ͕େ͖͘ͳΔ αϯϓϦϯάઓུΛ࣋ͭ%FFQ8BMLΛఆࣜԽ

(SBQI("/(SBQI3FQSFTFOUBUJPO-FBSOJOH XJUI(FOFSBUJWF"EWFSTBSJBM/FUT #GAN #Graph Softmax """* )POHXFJ8BOH 4IBOHIBJ+JBP5POH6OJWFSTJUZ +JB8 +JBMJO8
.JBP; 8FJOBO; 'V[IFOH; 9JOH9JF .JOZJ(VP DJUBUJPOT w (ͱQ@USVF͕͍͍ۙͮͯ͘͜ͱΛظ଴ w ੜ੒ϞσϧͷMPTTܭࢉͰɺάϥϑߏ଄ ʹదͨ͠෯༏ઌ୳ࡧʹجͮ͘(SBQI 4PGUNBYΛಋೖ w ܭࢉޮ཰΋্͕Δ ੜ੒͞ΕͨϊʔυΛࠞͥࠐΉੜ੒Ϟσϧͱɺάϥϑશମͷଥ౰ੑΛ൑ఆ͢ΔࣝผϞσϧ Λ༻͍ͯɺάϥϑͰ("/Λ΍Δ (SBQI4PGUNBYΛ৽ͨʹಋೖ ҟͳΔจ຺Ͱൃల͖ͯͨ͠ੜ੒ϞσϧͱࣝผϞσϧͷ༥߹

8FJTGFJMFS-FINBO(SBQI,FSOFMT #WL test #Graph Kernel #Graph Classification #Similarity +.-3 /JOP4IFSWBTIJE[F
.BY1MBODL*OTUJUVUFT5VCJOHFO FUBM DJUBUJPOT (ͱ(`ͷશͯͷϊʔυʹ͍ͭͯɺࣗ ਎ͱۙ๣ϊʔυͷϥϕϧΛूΊΔ ूΊͨϥϕϧΛࣙॻॱͰιʔτ ϥϕϧू߹ʹϢχʔΫϥϕϧΛ෇༩ ͢Δ ϥϕϧ਺Λͱͯ͠ɺ܁Γฦ͠ճ਺ O͕Λຬͨ͢·Ͱଓ͚Δ ৽͘͠࡞ΒΕΔϥϕϧू߹͕Ұக͠ ͍ͯΕ͹ಉܕ άϥϑͷಉܕੑΛ൑ఆ͢Δ8FJTGFJMFS-FINBO5FTUΛಋग़ ಉܕੑ൑ఆͰ͓ͦΒ͘Ұ൪Ҿ༻͞Ε͍ͯΔ 8-TVCUSFFLFSOFMʹΑΔಛ௃ྔԽ΋

(SBQI3FQSFTFOUBUJPO • 1Z5PSDI#JH(SBQI"-BSHFTDBMF(SBQI&NCFEEJOH4ZTUFN ◦ 4ZT.- "EBN-FSFS 'BDFCPPL"*3FTFBSDI FUBM DJUBUJPOT ◦
5SJMMJPOαΠζͷΤοδΛ࣋ͭάϥϑΛFNCFEEJOHͰ͖Δ044 • *OEVDUJWF3FQSFTFOUBUJPO-FBSOJOHPO-BSHF(SBQIT ◦ /FVS*14 8JMMJBN-)BNJMUPO 4UBOGPSE6OJWFSTJUZ 3FY:JOH +VSF -FTLPWFD DJUBUJPOT ◦ ۙ๣৘ใ͔ΒFNCFEEJOHΛٻΊΔͨΊͷBHHSFHBUFؔ਺Λֶश͢Δ͜ͱͰ ະ஌ϊʔυͷFNCFEEJOHΛֶशͰ͖Δɻ(SBQI4"(& • 3FQSFTFOUBUJPOMFBSOJOHPGLOPXMFEHFHSBQITXJUIFOUJUZ EFTDSJQUJPOT ◦ """* DJUBUJPOT ◦ &OUJUZؚ͕·Ε͍ͯͳͯ͘΋આ໌จΛ࢖ͬͯਪ࿦͢Δ[FSPTIPUʹऔΓ૊ΜͰ ͍Δ

(SBQI3FQSFTFOUBUJPO • 3FQSFTFOUBUJPO-FBSOJOHPO(SBQITXJUI+VNQJOH,OPXMFEHF /FUXPSLT ◦ *$.- ,FZVMV9V FUBM DJUBUJPOT •
-FBSOJOH-BQMBDJBO.BUSJYJO4NPPUI(SBQI4JHOBM3FQSFTFOUBUJPOT ◦ BS9JW 9JBPXFO%POH &1'- %PSJOB5IBOPV 1BTDBM'SPTTBSE BOE1JFSSF7BOEFSHIFZOTU DJUBUJPOT ◦ σʔλ͔Βάϥϑߏ଄Λֶश͍ͨ͠ɻJMMQPTFEQSPCMFN͕ͩάϥϑͷ׈Β͔͞ Λ͍͍ײ͡ʹ࢖͏ • 'BTU(SBQI3FQSFTFOUBUJPO-FBSOJOHXJUI1Z5PSDI(FPNFUSJD ◦ *$-3 .BUUIJBT'FZ+BO&-FOTTFO 56%PSUNVOE6OJWFSTJUZ DJUBUJPOT ◦ άϥϑ΍%఺܈ͱ͍ͬͨඇϢʔΫϦουߏ଄σʔλ޲͚ͷ%-ϥΠϒϥϦ 1ZUPSDI(FPNFUSJDͷ঺հ

/PEF(SBQIGPDVTFE

.PEFMJOH3FMBUJPOBM%BUBXJUI(SBQI$POWPMVUJPOBM/FUXPSLT #RGCN #entity prediction #link prediction #relational data &48$ .JDIBFM44DIMJDIULSVMM
6OJWFSTJUZPG"NTUFSEBN 5IPNBT/,JQG 1FUFS#MPFN 3JBOOFWBOEFO#FSH *WBO5JUPW .BY8FMMJOH DJUBUJPOT άϥϑߏ଄ͷ෼ੳʹओ؟Λஔ͍ͨ3($/ΛఏҊ͠ɺ FOUJUZMJOLQSFEJDUJPOͷ༷ʑͳσʔλͰ4P5" w ੺͍ϊʔυ͕ิ׬͞ΕΔ΂͖ϊʔυɺΤοδͰ͋Ε ͹ิ׬͞ΕΔ΂͖ؔ܎ੑ w ؔ܎ੑʹԠͯۙ͡๣͕มΘΔͱߟ͑ͯɺ৽͍͠৞ࠐ ΈΛఆٛ͢Δ w ߋ৽͞Εͨ৴߸͔Βϊʔυͷଐੑ༧ଌʢFOUJUZ QSFEJDUJPOʣ΍ BDUJWBUJPOGVODUJPO ਖ਼نԽ܎਺ ຒΊࠐΈϕΫτϧ SFMBUJPOSΛ৞ΈࠐΉॏΈߦྻ ؔ܎ੑΛߟྀͨ͠($/ΛఆࣜԽ

άϥϑ্ͷQPPMJOHΛιϑτΫϥελϦϯάͱͯ͠ఆࣜԽͯ͠HSBQIDMBTTJpDBUJPO ֤ϊʔυ͕࣍ͷϨΠϠʔͰͲͷΫϥελʹଐ͢Δ͔Λผͷ//Ͱ༧ଌ ྡ઀͢Δϊʔυ͕ಉ͡Ϋϥελʹଐ͢ΔΑ͏ͳਖ਼ଇԽΛ͔͚Δ Τϯτϩϐʔਖ਼ଇԽʹΑͬͯͲΕ͔ҰͭͷΫϥελʹଐ͢Δ֬཰Λ্͛Δ #graph classification #graph pooling )JFSBSDIJDBM(SBQI3FQSFTFOUBUJPO-FBSOJOHXJUI%J⒎FSFOUJBCMF1PPMJOH /FVS*14
3FY:JOH 4UBOGPSE6OJWFSTJUZ +JBYVBO:PV $ISJTUPQIFS.PSSJT 9JBOH3FO 8JMMJBN-)BNJMUPO +VSF-FTLPWFD DJUBUJPO

طଘͷώϡʔϦεςΟΫεΛಋग़Ͱ͖Δ(//Λ༻͍ͨTVCHSBQIʹΑΔϦϯΫ༧ଌ ର৅ϊʔυपลͷ৘ใͷΈΛ࢖ͬͯ΋ޡࠩΛগͳ͘Ͱ͖ΔͷͰ͸ɺͱ͍͏ΞΠσΟΞ &ODMPTJOHTVCHSBQIΛ࢖ͬͨ༧ଌ͕ྑ͍ۙࣅʹͳ͍ͬͯͨ -JOL1SFEJDUJPO#BTFEPO(SBQI/FVSBM/FUXPSLT #link prediction #enclosed subgraph /FVS*14 .VIBO;IBOH
8BTIJOHUPO6OJWFSTJUZ :JYJO$IFO DJUBUJPOT

"QQMJDBUJPOT

άϥϑͷ௿࣍ݩຒΊࠐΈΛֶश͠ɺάϥϑ΁ͷ࿦ཧԋࢉΛຒΊࠐΈۭؒͰͷ زԿૢ࡞ʹஔ͖׵͑Δ͜ͱͰઢܗ࣌ؒͰͷ୳ࡧΛߦ͏ ɾ࿦ཧૢ࡞ͱزԿֶૢ࡞͕׬શͳରԠΛ͍ͯ͠ͳ͍ʢ࿦ཧ൱ఆͳͲ͸ѻ͑ͳ͍ʣ ɾΤοδͷಛ௃Λ࢖༻͢Δ͜ͱ͕Ͱ͖ͳ͍ ͱ͍͏໰୊͸͋Δ͕ɺෆ׬શͳLOPXMFEHFCBTFʹର͢ΔޮՌతͳΤοδ༧ଌख๏ɻ DPOKVODUJWFRVFSZΛ%"(ʹม׵ BODIPSOPEFΛ௿࣍ݩ΁ຒΊࠐΈ
FEHFΛͨͲΔ࿦ཧૢ࡞ΛຒΊࠐΈۭؒͰͷ زԿૢ࡞Ͱ͋ΔQSPKFDUJPOͱͯ͠ߦ͏ ಘΒΕͨϕΫτϧͷJOUFSTFDUJPOʢ࿦ཧ ੵʣΛܭࢉ͢Δ 1SPKFDUJPOΛߦ͏ ࠷ۙ๣๏ͰRVFSZΛຬͨ͢OPEFΛ୳͢ #Graph Querying #Embedding &NCFEEJOH-PHJDBM2VFSJFTPO,OPXMFEHF(SBQIT /FVS*14 8JMMJBN-)BNJMUPO 4UBOGPSE6OJWFSTJUZ %FQBSUNFOUPG$PNQVUFS4DJFODF FUBM DJUBUJPOT άϥϑΛܦ༝ͨ͠FNCFEEJOHΛߦ͏͜ͱͰɺ࿦ཧԋࢉՄೳͳੑ࣭͕࢒Δ

*OUFSBDUJPO/FUXPSLTGPS-FBSOJOHBCPVU0CKFDUT 3FMBUJPOTBOE1IZTJDT #Physics /FVS*14 1FUFS8#BUUBHMJB %FFQ.JOE 3B[WBO1BTDBOV .BUUIFX-BJ %BOJMP3F[FOEF ,PSBZ,BWVLDVPHMV
DJUBUJPOT 5SVF .PEFM ෺ཧ๏ଇΛɺ෺ମͱͦͷؔ܎ੑʹ෼ղ͢Δ͜ͱͰਪଌͰ͖ΔΑ͏ʹͨ͠ w ෺ମͷ૬ޓ࡞༻ΛϞσϧԽ͢ΔͨΊʹɺ෺ମ ʢϊʔυʣͱ෺ମؒͷؔ܎ʢΤοδʣͷάϥϑ Λར༻ w ෺ମʹର͢ΔޮՌྔΛܭࢉ͢ΔϞσϧͱɺ֎ྗ ͳͲͷ૬ޓ࡞༻Λߟྀͨ͠ঢ়ଶਪఆΛߦ͏Ϟσ ϧΛ࡞Δ ܭࢉྔ͕͔ͳΓେ͖͘ɺେن໛ͳ෺ཧ γϛϡϨʔγϣϯ͸Ͱ͖ͳ͍ ൚༻ੑ͕ߴ͘ɺҰൠతͳ෺ཧ๏ଇʹద ༻Մೳ

ݚڀऀ঺հ • 5IPNBT/,JQG ◦ ($/ • .BY8FMMJOH ◦ 4FNJTVQFSWJTFEDMBTTJpDBUJPOXJUIHSBQIDPOWPMVUJPOBMOFUXPSLT Ͱ($/ͷσϑΝΫτʹ
◦ 7"& • :VKJB-J ◦ (BUFE(// ◦ (SBQI.BUDIJOH// • 1FUFS#BUUBHMJB ◦ 3FMBUJPOBMJOEVDUJWFCJBTFT EFFQMFBSOJOH BOEHSBQIOFUXPSLT • 4UFQIBO(ÛOOFNBOO ◦ BEWFSTBSJBMBUUBDL

ݚڀऀ঺հ • ,FZVMV9V ◦ ·ֶͩੜͱࢥΘΕΔ͕ࠓޙ͍͢͝࿦จΛॻ͖ͦ͏ ◦ Տݪྛڊେάϥϑ1+ͰབྷΈ͕͋Δʁ ◦ )PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT
• /JOP4IFSWBTIJE[F SJTJLPOEPS ◦ HSBQILFSOFM • 8JMMJBN-)BNJMUPO ◦ *OEVDUJWF3FQSFTFOUBUJPO-FBSOJOHPO-BSHF(SBQIT ◦ ໰୊ఏىͳͲಠಛͷ੾Γޱ • FUDʜ

8FMDPNF άϥϑ࿦จͷαʔϕΠ΍ݚڀΛ͍ͨ͠ਓɺ σʔληοτΛ࡞Γ͍ͨਓɺڞಉݚڀߟ͑ͯΈ͍ͨਓɺ ·ͣ͸࿈བྷ͍ͩ͘͞ʂ

Graph: A Survey of Graph Neural Networks, Embed...

Graph: A Survey of Graph Neural Networks, Embedding, Tasks and Applications

uchi_k

More Decks by uchi_k

Other Decks in Technology

Featured

Transcript

(SBQI "4VSWFZPG(SBQI/FVSBM/FUXPSLT &NCFEEJOH 5BTLTBOE"QQMJDBUJPOT

Kenshi Uchihashi uchi_k @wednesdaymuse About me nlpaper.challenge ӡӦ Freelance Machine

αʔϕΠํ๏ • ؔ࿈Ωʔϫʔυ ݚڀऀͷચ͍ग़͠ ◦ (PPHMF4DIPMBS΁ • ॏཁ࿦จͷબఆ ◦ ͢ͰʹධՁ͕ఆ·ͬͨ΋ͷʹ͍ͭͯ͸Ҿ༻਺

஫ҙ • ਤ΍਺ࣜ͸࿦จ͔ΒҾ༻͍ͯ͠·͢ ◦ Ҿ༻ݩͷ࿦จ͸λΠτϧͷ࿦จͰ͢ • ҎԼͷ஌ࣝΛલఏͱ͠·͢ ◦ χϡʔϥϧωοτϫʔΫͷجૅ஌ࣝ ◦

஫ҙ • ॏཁ࿦จຊɺؔ࿈࿦จຊʹ·ͱΊ·ͨ͠ʢൃද൛Ͱ͸൒෼͘Β͍ʹݮΒͯ͠ ͍·͢ʣ • ൃදͰ͸جૅతͳ಺༰ʹ͠΅Γ·ͨ͠ ◦ (// ◦ ($/

/FVSBM/FUXPSLTPO(SBQI

5IF(SBQI/FVSBM/FUXPSL.PEFM #Graph Neural Network *&&&5// 4DBSTFMMJ 'SBODP 6OJWFSTJUZPG4JFOB BOE(PSJ .BSDPBOE5TPJ

w ೖྗϊʔυू߹ΛΫϥελϦϯά͍ͯ͘͠ w ΛݸͷΫϥελʹ෼͚ͨ݁Ռ͕ w ͸ྡ઀ؔ܎͕͋Δͱ͜ΖͷΈ஋Λ࣋ͭε ύʔεͳϑΟϧλʔ 4QFDUSBM/FUXPSLTBOE-PDBMMZ$POOFDUFE/FUXPSLTPO(SBQIT #GCN #SpatialGCN

4QFDUSBM/FUXPSLTBOE-PDBMMZ$POOFDUFE/FUXPSLTPO(SBQIT #Graph Neural Network #Spectral Clustering #Fourier Transform *$-3 +PBO#SVOB

$POWPMVUJPOBM/FVSBM/FUXPSLTPO(SBQIT XJUI'BTU-PDBMJ[FE4QFDUSBM'JMUFSJOH #GCN #Spectral Filtering #Chebyshev Polynomials /FVS*14 .JDIBËM%F⒎FSSBSE &1'-

4FNJ4VQFSWJTFE$MBTTJpDBUJPOXJUI(SBQI$POWPMVUJPOBM/FUXPSLT #GCN #Semi-Supervised Learning *$-3 5IPNBT/,JQG .BY8FMMJOH DJUBUJPOT ྡ઀ϊʔυͷ৞ΈࠐΈͷΈͰ4QFDUSBM($/ͷۙࣅ͕Ͱ͖Δ͜ͱΛࣔͨ͠ w

(BUFE(SBQI4FRVFODF/FVSBM/FUXPSLT #GNN #LSTM #Sequence *$-3 :VKJB-J %FQBSUNFOUPG$PNQVUFS4DJFODF 6OJWFSTJUZPG5PSPOUP %BOJFM5BSMPX .BSD#SPDLTDINJEU

)PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT #GNN #WL test #Graph Isomorphism Network $-3 ,FZVMV9V .5

)PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT #GNN #WL test #Graph Isomorphism Network $-3 ,FZVMV9V .5

)PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT #GNN #WL test #Graph Isomorphism Network $-3 ,FZVMV9V .5

(SBQI/FVSBM/FUXPSL • "OFXNPEFMGPSMFBSOJOHJOHSBQIEPNBJOT ◦ *+$// .BSDP(PSJ 6OJWFSTJUZPG4JFOB FUBM DJUBUJPOT ◦

(SBQI/FVSBM/FUXPSL • -FBSOJOH$POWPMVUJPOBM/FVSBM/FUXPSLTGPS(SBQIT ◦ *$.- .BUIJBT/JFQFSU /&$-BCT&VSPQF FUBM DJUBUJPOT ◦

(SBQI/FVSBM/FUXPSL • )JHIFSPSEFS(SBQI$POWPMVUJPOBM/FUXPSLT ◦ *$.- 4BNJ"CV&M)BJKB 6OJWFSTJUZPG4PVUIFSO$BMJGPSOJB FUBM DJUBUJPOT

(SBQI3FQSFTFOUBUJPO

%FFQXBML0OMJOFMFBSOJOHPGTPDJBMSFQSFTFOUBUJPOT #Representation #Online Learning #Graph Embedding ,%% #SZBO1FSP[[J 3BNJ"M3GPV 4UFWFO4LJFOB

-/&-BSHFTDBMFOGPSNBUJPO/FUXPSL&NCFEEJOH #Graph Embedding #Edge Sampling 888 +JBO5BOH .JDSPTPGU3FTFBSDI"TJB FUBM DJUBUJPOT

OPEFWFD4DBMBCMF'FBUVSF-FBSOJOHGPS/FUXPSLT #Graph Embedding #DFS #DeepWalk ,%% "EJUZB(SPWFS 4UBOGPSE6OJWFSTJUZ +VSF-FTLPWFD DJUBUJPOT

(SBQI("/(SBQI3FQSFTFOUBUJPO-FBSOJOH XJUI(FOFSBUJWF"EWFSTBSJBM/FUT #GAN #Graph Softmax """* )POHXFJ8BOH 4IBOHIBJ+JBP5POH6OJWFSTJUZ +JB8 +JBMJO8

8FJTGFJMFS-FINBO(SBQI,FSOFMT #WL test #Graph Kernel #Graph Classification #Similarity +.-3 /JOP4IFSWBTIJE[F

(SBQI3FQSFTFOUBUJPO • 1Z5PSDI#JH(SBQI"-BSHFTDBMF(SBQI&NCFEEJOH4ZTUFN ◦ 4ZT.- "EBN-FSFS 'BDFCPPL"*3FTFBSDI FUBM DJUBUJPOT ◦

(SBQI3FQSFTFOUBUJPO • 3FQSFTFOUBUJPO-FBSOJOHPO(SBQITXJUI+VNQJOH,OPXMFEHF /FUXPSLT ◦ *$.- ,FZVMV9V FUBM DJUBUJPOT •

/PEF(SBQIGPDVTFE

.PEFMJOH3FMBUJPOBM%BUBXJUI(SBQI$POWPMVUJPOBM/FUXPSLT #RGCN #entity prediction #link prediction #relational data &48$ .JDIBFM44DIMJDIULSVMM

"QQMJDBUJPOT

OUFSBDUJPO/FUXPSLTGPS-FBSOJOHBCPVU0CKFDUT 3FMBUJPOTBOE1IZTJDT #Physics /FVS14 1FUFS8#BUUBHMJB %FFQ.JOE 3B[WBO1BTDBOV .BUUIFX-BJ %BOJMP3F[FOEF ,PSBZ,BWVLDVPHMV

ݚڀऀ঺հ • 5IPNBT/,JQG ◦ ($/ • .BY8FMMJOH ◦ 4FNJTVQFSWJTFEDMBTTJpDBUJPOXJUIHSBQIDPOWPMVUJPOBMOFUXPSLT Ͱ($/ͷσϑΝΫτʹ

ݚڀऀ঺հ • ,FZVMV9V ◦ ·ֶͩੜͱࢥΘΕΔ͕ࠓޙ͍͢͝࿦จΛॻ͖ͦ͏ ◦ Տݪྛڊେάϥϑ1+ͰབྷΈ͕͋Δʁ ◦ )PX1PXFSGVMBSF(SBQI/FVSBM/FUXPSLT

8FMDPNF άϥϑ࿦จͷαʔϕΠ΍ݚڀΛ͍ͨ͠ਓɺ σʔληοτΛ࡞Γ͍ͨਓɺڞಉݚڀߟ͑ͯΈ͍ͨਓɺ ·ͣ͸࿈བྷ͍ͩ͘͞ʂ