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

グラフに関連する話題について幅広くサーベイを行い、30本の重要論文と70本の関連論文にまとめました。
※こちらは発表のための縮小版です
※ 発表はこちらで行いました。動画もあります（ https://nlpaper-challenge.connpass.com/event/136090/ ）
GNN, GCN, RelationalGCN and other GNNs, Link Prediction, Graph Classification, Graph Completion, Graph Representation/Embedding, Graph Kernel, Combinatorial/Logical, その他の最近の話題, CV, NLP, Molecular Graph Generation, Recommendation などの Application について、2016年以降の研究成果を中心に紹介します。

Transcript

1. (SBQI
   "
   4VSWFZ
   PG
   (SBQI
   /FVSBM
   /FUXPSLT
   &NCFEEJOH
   5BTLT
   BOE
   "QQMJDBUJPOT
2. Kenshi Uchihashi uchi_k @wednesdaymuse About me nlpaper.challenge ӡӦ Freelance Machine Learning ɹɹɹɹɹEngineer / Researcher former ະ౿16, ژେ৘ใӃ, FreakOut Machine Learning Engineer
3. αʔϕΠํ๏ • ؔ࿈Ωʔϫʔυ
   ݚڀऀͷચ͍ग़͠
   ◦ (PPHMF
   4DIPMBS
   ΁
   • ॏཁ࿦จͷબఆ
   ◦ ͢ͰʹධՁ͕ఆ·ͬͨ΋ͷʹ͍ͭͯ͸Ҿ༻਺
   ◦ ೥ʹग़൛͞Εͨ΋ͷʹ͍ͭͯ͸಺༰ͰධՁ༗໊ݚڀऀ΍ϥϘ
   ◦ ༗ࣝऀʹฉ͘
   • $POGFSFODF
   ◦ /FVS*14 
   *$-3 
   *$.- 
   """* 
   ʜ
   ◦ ,%% 
   888 
   ʜ
   ◦ BSYJW 
   ʜ
   • ࿦จͷ෼໺͸࠷΋ߩݙ͕େ͖͍ͱࢥͬͨ෼໺ʹׂΓৼΓ
   • ྫ͑͹
   $7
   ΁ͷΞϓϦέʔγϣϯ࿦จͰ΋৽ͯ͘͠༗༻ͳ
   ($/
   ͷϑϨʔϜ ϫʔΫΛఏҊ͍ͯ͠Ε͹෼໺͸
   ($/
   ΛׂΓ౰ͯΔɺͳͲ
4. ஫ҙ • ਤ΍਺ࣜ͸࿦จ͔ΒҾ༻͍ͯ͠·͢
   ◦ Ҿ༻ݩͷ࿦จ͸λΠτϧͷ࿦จͰ͢
   • ҎԼͷ஌ࣝΛલఏͱ͠·͢
   ◦ χϡʔϥϧωοτϫʔΫͷجૅ஌ࣝ
   ◦ .-1
   DPOWPMVUJPO
   QPPMJOH
   $//
   3//
   -45.
   ʜ
   ◦ άϥϑʹؔ͢Δجૅ༻ޠ
   ◦ ϊʔυ
   Τοδ
   ༗޲ແ޲
   ॏΈ෇͖ͳ͠
   ྡ઀ߦྻ
   άϥϑϥϓϥγΞϯ
   ◦ ͦͷଞ
   ◦ BEWFSTBSJBM
   BUUBDL
   TVCUSFF
   ʜ
   • ಛʹஅΓ͕ͳ͚Ε͹͍͍ͩͨϧʔϓ΍ଟॏΤοδΛ࣋ͨͳ͍άϥϑΛѻ͍ͬͯ·͢
   • ਺ࣜ͸௥Θͣɺ࿦จ಺Ͱॏཁͳ΋ͷʹߜͬͯղઆ͢ΔελΠϧͰ͢
   • ࿦จͷࡉ͔͍ͱ͜Ζ͸঺հͰ͖ͳ͍ͷͰɺݚڀͷେ͖ͳྲྀΕॏࢹͰ͢
5. ஫ҙ • ॏཁ࿦จຊɺؔ࿈࿦จຊʹ·ͱΊ·ͨ͠ʢൃද൛Ͱ͸൒෼͘Β͍ʹݮΒͯ͠ ͍·͢ʣ
   • ൃදͰ͸جૅతͳ಺༰ʹ͠΅Γ·ͨ͠
   ◦ (//
   ◦ ($/
   ◦ PUIFS
   (//T
   ◦ (SBQI
   3FQSFTFOUBUJPO&NCFEEJOH
   ◦ /PEFGPDVTFE
   5BTL
   ◦ (SBQIGPDVTFE
   5BTL
   ◦ 5BTLT
   ◦ $PNCJOBUPSJBM-PHJDBM
   "EWFSTBSJBM
   "UUBDL
   .BUDIJOH
   FUD
   ◦ "QQMJDBUJPOT
   ◦ $7
   /-1
   3FMBUJPO
   &YUSBDUJPO
   3FDPNNFOEBUJPO
   .PMFDVMBS
   (SBQI
   (FOFSBUJPO
   1IZTJDT
   • ൣғΛ޿͗ͨ͘͢͠ײ͋ΔΜͰ͕͢ɺޙ೔VQ͢ΔࢿྉͰิ׬͍ͩ͘͞
6. /FVSBM
   /FUXPSLT
   PO
   (SBQI
   
7. 5IF
   (SBQI
   /FVSBM
   /FUXPSL
   .PEFM #Graph Neural Network *&&&
   5//
   
   4DBSTFMMJ
   'SBODP 6OJWFSTJUZ
   PG
   4JFOB
   BOE
   (PSJ
   .BSDP
   BOE
   5TPJ
   "I
   $
   BOE
   )BHFOCVDIOFS
   .
   BOE
   .POGBSEJOJ
   (
   
   DJUBUJPOT ྡ઀Τοδϥϕϧ ϊʔυঢ়ଶ ྡ઀ϊʔυϥϕϧ ϊʔυϥϕϧ • ࠷ۙ๣ϊʔυͷ৘ใΛ࠶ؼతʹ
   BHHSFHBUF
   ͢Δ
   • Lճͷ
   BHHSFHBUJPO
   ʹΑͬͯɺLIPQ
   ͷ৘ใ͕औಘͰ͖Δ
   • ༧ΊܾΊΒΕͨλΠϜεςοϓͰֶश͕ ऴྃ͢ΔͷͰԕ͘ͷϊʔυͷ৘ใ͕औΕ ͳ͍͜ͱ͕͋Δ ϊʔυ͕ϝοηʔδΛ఻೻͍ͯ͘͠࢓૊ΈͰ
   (//
   Λಋग़ͨ͠ άϥϑߏ଄Λͦͷ··χϡʔϥϧωοτʹམͱ͠ࠐΊΔΑ͏ʹ
8. w ೖྗϊʔυू߹
   
   
   
   
   
   ΛΫϥελϦϯά͍ͯ͘͠
   w
   
   
   
   
   
   
   
   
   
   Λ
   
   
   
   
   ݸͷΫϥελʹ෼͚ͨ݁Ռ͕
   w
   
   
   
   
   
   
   
   
   ͸ྡ઀ؔ܎͕͋Δͱ͜ΖͷΈ஋Λ࣋ͭε ύʔεͳϑΟϧλʔ 4QFDUSBM
   /FUXPSLT
   BOE
   -PDBMMZ
   $POOFDUFE
   /FUXPSLT
   PO
   (SBQIT #GCN #SpatialGCN #SpectralGCN #Spectral Clustering *$-3
   
   +PBO
   #SVOB /FX
   :PSL
   6OJWFSTJUZ
   8PKDJFDI
   ;BSFNCB
   "SUIVS
   4[MBN
   :BOO
   -F$VO
   
   DJUBUJPO άϥϑʹ͓͚Δہॴੑͱղ૾౓Λఆٛ͠ɺ$//
   Λάϥϑʹ֦ு͢Δํ๏Λ
   4QBUJBM
   ͱ
   4QFDUSBM
   ͷछྨఏҊ ྡ઀ߦྻΛ༻͍ͨہॴੑ NVMUJTDBMF
   DMVTUFSJOH
   ʹΑΔղ૾౓ ϊʔυू߹ ྡ઀ߦྻ ᮢ஋Λద౰ʹઃఆ͢Δ͜ͱͰہॴੑΛදݱ Ϋϥελʹؚ·ΕΔશϊʔυͷಛ௃ྔΛೖ ྗͱ͠ɺ୅ද஋ͱͯ͠Ұͭͷಛ௃ྔΛग़ྗ ϓʔϦϯά 4QBUJBM
   $POTUSVDUJPO ϑΟϧλʔ
9. 4QFDUSBM
   /FUXPSLT
   BOE
   -PDBMMZ
   $POOFDUFE
   /FUXPSLT
   PO
   (SBQIT #Graph Neural Network #Spectral Clustering #Fourier Transform *$-3
   
   +PBO
   #SVOB /FX
   :PSL
   6OJWFSTJUZ
   8PKDJFDI
   ;BSFNCB
   "SUIVS
   4[MBN
   :BOO
   -F$VO
   
   DJUBUJPO  ϑʔϦΤม׵͸೾ܗΛप೾਺੒෼ʹ෼ղ͢Δ͕ɺάϥϑϑʔϦΤม׵͸άϥϑ্Ͱఆٛ͞Εͨ৴ ߸ʹରͯ͠৴߸ͷٸफ़͞Λఆٛ͠ɺٸफ़͞͝ͱʹ੒෼෼ղ
    άϥϑϥϓϥγΞϯͷݻ༗஋ܭࢉͰٸफ़͞੒෼΁ͷ෼ղ͕Մೳ
    DPOWPMVUJPO
   ͸
   'PVSJFS
   EPNBJO
   ʹ͓͚Δཁૉੵʹ૬౰͢Δͱ͍͏ఆཧΛ༻͍ͯɺཁૉੵͰ DPOWPMVUJPO
   ͢Δ͜ͱ͕Ͱ͖ΔΑ͏ʹͳΔ
    ཁૉੵʹରͯ͠ٯϑʔϦΤม׵ΛͱΔ ݻ༗஋ܭࢉͱݻ༗ϕΫτϧͷੵͷܭࢉίετ͕େ͖͍ 4QFDUSBM
   $POTUSVDUJPO ϑʔϦΤجఈʹରԠͨ͠άϥϑϥϓϥγΞϯͷݻ༗ϕΫτϧͷ݁߹܎਺ΛมԽ͞ ͤΔ͜ͱͰάϥϑ্ͷಛ௃ྔม׵͕ఆٛͰ͖Δ ݻ༗ϕΫτϧ
10. $POWPMVUJPOBM
    /FVSBM
    /FUXPSLT
    PO
    (SBQIT
    
    XJUI
    'BTU
    -PDBMJ[FE
    4QFDUSBM
    'JMUFSJOH #GCN #Spectral Filtering #Chebyshev Polynomials /FVS*14
    
    .JDIBËM
    %F⒎FSSBSE &1'-
    9BWJFS
    #SFTTPO
    1JFSSF
    7BOEFSHIFZOTU
    
    DJUBUJPOT ݻ༗஋ߦྻ νΣϏγΣϑଟ߲ࣜۙࣅʹΑͬͯݻ༗஋෼ղΛճආ͠ɺ($/ͷܭࢉྔΛԼ͛Δ νΣϏγΣϑଟ߲ࣜۙࣅ ݻ༗஋ܭࢉͱݻ༗ϕΫτϧͷੵͷܭࢉίετ͕ େ͖͍໰୊Λ͔ͳΓղܾ 'PVSJFS
    EPNBJO
    Ͱఆٛ͞ΕͨϑΟϧλ
    
    
    
    
    
    
    
    
    Λ༻͍ͨ৞ΈࠐΈ͸ɺ ݻ༗஋ͷεέʔϦϯά ଟ߲ࣜۙࣅͨ͠ํ͕ਫ਼౓΋্͕ͬͨ νΣϏγΣϑଟ߲ࣜͷ࣍਺,͕ϑΟϧλαΠζ ͱରԠ͍ͯ͠Δ
11. 4FNJ4VQFSWJTFE
    $MBTTJpDBUJPO
    XJUI
    (SBQI
    $POWPMVUJPOBM
    /FUXPSLT #GCN #Semi-Supervised Learning *$-3
    
    5IPNBT
    /
    ,JQG
    .BY
    8FMMJOH
    
    DJUBUJPOT ྡ઀ϊʔυͷ৞ΈࠐΈͷΈͰ
    4QFDUSBM($/
    ͷۙࣅ͕Ͱ͖Δ͜ͱΛࣔͨ͠ w νΣϏγΣϑଟ߲ࣜۙࣅͷϞσϧͷ,ͷ৔ ߹ʢ࠷ۙ๣ͷΈࢀর͢Δʣ
    w Ϟσϧͷදݱೳྗ͸Լ͕Δ
    w %//
    ͷΑ͏ʹɺޯ഑ফࣦʹରԠ͢ΔςΫ χοΫΛಋೖʢSFOPSNBMJ[BUJPO
    USJDLʣ աֶशͷ཈੍ޮՌʹΑͬͯɺۙࣅͨ͠΄͏͕ਫ਼౓͕ྑ͘ͳ͍ͬͯΔ ଟ߲ࣜۙࣅͨ͠ํ͕ਫ਼౓΋্͕ͬͨ ϥϕϧ͕෇͍͍ͯΔσʔλʹ͍ͭͯɺTPGUNBY
    DSPTT
    FOUSPQZ
    ʹΑֶͬͯश͢Δ ඪ४తͳ
    ($/
    ͱͯ͠ҎԼͷఆࣜԽΛͨ͠
12. (BUFE
    (SBQI
    4FRVFODF
    /FVSBM
    /FUXPSLT #GNN #LSTM #Sequence *$-3
    
    :VKJB
    -J %FQBSUNFOU
    PG
    $PNQVUFS
    4DJFODF
    6OJWFSTJUZ
    PG
    5PSPOUP
    %BOJFM
    5BSMPX
    .BSD
    #SPDLTDINJEU
    BOE
    3JDIBSE
    ;FNFM
    
    DJUBUJPOT w (//
    ͷঢ়ଶߋ৽͸࣮࣭
    3//
    ͕ͩͬͨɺ͜͜Λ
    -45.
    ΍
    (36
    ʹมߋ͢Δ
    w ޯ഑ܭࢉʹʢ"MNFJEB1JOFEB
    ΞϧΰϦζϜͰ͸ͳ͘ʣ#155
    Λ࢖༻
    w 4FRVFODF
    ͳग़ྗΛֶशՄೳʹͳΓɺେ͖͘Ԡ༻෯͕૿͑ͨ -45.
    ΍
    (36
    Ͱঢ়ଶߋ৽Λߦ͏
    (//
    Λಋग़ ίʔυͷ৴པੑධՁͳͲͷଟ༷ͳλεΫ΁ͷԠ༻Մೳੑ͕ੜ·Εͨ (36
    ΍
    -45.
    ʹସ͑Δ ΑΓεϚʔτͳɺ࣌୅ʹԊͬͨఆࣜԽΛͨ͠
13. )PX
    1PXFSGVM
    BSF
    (SBQI
    /FVSBM
    /FUXPSLT #GNN #WL test #Graph Isomorphism Network *$-3
    
    ,FZVMV
    9V .*5
    8FJIVB
    )V
    +VSF
    -FTLPWFD
    4UFGBOJF
    +FHFMLB
    
    DJUBUJPOT (//T
    ΛఆࣜԽ͠ɺ8-
    UFTU
    ͱಉ౳ͷੑೳΛಘΔͨΊʹඞཁͳ੍໿Λಋग़ͨ͠ (//T
    ͷఆࣜԽ ϊʔυWͷಛ௃ϕΫτϧ • "((3&("5&
    ͱ
    $0.#*/&
    ͷ
    TUFQ
    ʹ෼͚Δ
    • (SBQIGPDVTFE
    5BTL
    Ͱ͸
    3&"%065
    Ͱશϊʔυ৘ใΛू໿ FY
    (SBQI4"(& FY
    ($/ "((3&("5&
    ͱ
    $0.#*/&
    ʹԿΛબͿ͔Ͱطଘͷ
    (//T
    ͸هड़Ͱ͖Δ • $0.#*/&
    ͳ͠
14. )PX
    1PXFSGVM
    BSF
    (SBQI
    /FVSBM
    /FUXPSLT #GNN #WL test #Graph Isomorphism Network *$-3
    
    ,FZVMV
    9V .*5
    8FJIVB
    )V
    +VSF
    -FTLPWFD
    4UFGBOJF
    +FHFMLB
    
    DJUBUJPOT "((3&("5&
    ͱ
    $0.#*/&
    Ͱهड़Ͱ͖Δ
    (//T
    ͸άϥϑ෦෼ߏ଄ͷࣝผ ೳྗ͕
    8-
    TVCUSFF
    LFSOFM
    ͱ౳ՁͰ͋Δ (//T
    ͷදݱೳྗͷߴ͞Λ෼ੳ͍ͨ͠ ཧ૝తʹ͸ɺҟͳΔάϥϑΛ׬શʹࣝผͰ͖Δ͔Ͳ͏͔͕άϥϑͷදݱೳྗͷߴ͞ Λද͕͢ɺ͜Ε͸ಉܕੑࣝผ໰୊ʢ/1ʣΛղܾͨ͜͠ͱʹͳΔʢʂʣ ݁࿦ 8-
    UFTU
    Ͱͷϊʔυͷಛ௃ϕΫτϧ͸
    POFIPU
    ϕΫτϧͰ
    TVCUSFF
    ؒ ͷྨࣅੑͳͲΛಘΔ͜ͱ͸Ͱ͖ͳ͍ͷʹର͠ɺ(//T
    Ͱ͸Մೳ (//T
    ͕
    8-
    UFTU
    ΛֶशϕʔεͰ࿈ଓۭؒʹ֦ுͨ͠΋ͷʹͳ͍ͬͯΔ ͳͷͰɺFNCFEEJOH
    ΍άϥϑߏ଄ؒͷ
    EFQFOEFODZ
    ΋औಘՄೳ
15. )PX
    1PXFSGVM
    BSF
    (SBQI
    /FVSBM
    /FUXPSLT #GNN #WL test #Graph Isomorphism Network *$-3
    
    ,FZVMV
    9V .*5
    8FJIVB
    )V
    +VSF
    -FTLPWFD
    4UFGBOJF
    +FHFMLB
    
    DJUBUJPOT "((3&("5&
    ʹ
    .&"/
    ΍
    ."9
    Λ࢖͏ͱ
    8-
    UFTU
    ʹྼΔͷͰɺ46.
    Λ࢖͍·͠ΐ͏
    ʢͨͩ͠ɺλεΫʹΑͬͯ͸͍͍ͱ͜Ζ΋͋Δʣ 8-
    UFTU
    อূͷ͋Δ
    (*/ʢ(SBQI
    *TPNPSQIJTN
    /FUXPSLʣΛఏҊ ࣗ෼ࣗ਎ʹద౰ͳ܎਺Λ͔͚ͯɺશͯͷྡ઀ϊʔυͱͷ࿨Λͱͬͯ
    .-1
    ʹೖྗ͢ Δͱ͍͏γϯϓϧͳߏ੒ʢ"((3&("5&
    ͷΈʣͰ΋ɺ
    ଞͷෳࡶͳϞσϧͱཧ࿦্ಉఔ౓ͷੑೳ͕ظ଴Ͱ͖Δɻ
16. (SBQI
    /FVSBM
    /FUXPSL • "
    OFX
    NPEFM
    GPS
    MFBSOJOH
    JO
    HSBQI
    EPNBJOT
    ◦ *+$//
    
    .BSDP
    (PSJ 6OJWFSTJUZ
    PG
    4JFOB
    FU
    BM
    
    DJUBUJPOT
    ◦ (SBQI
    /FVSBM
    /FUXPSL
    ΛఏҊ
    • (SBQI
    8BSQ
    .PEVMF
    BO
    "VYJMJBSZ
    .PEVMF
    GPS
    #PPTUJOH
    UIF
    1PXFS
    PG
    (SBQI
    /FVSBM
    /FUXPSLT
    ◦ BS9JW
    ,BUTVIJLP
    *TIJHVSP 1SFGFSSFE
    /FUXPSLT
    FU
    BM
    
    DJUBUJPOT
    ◦ (//
    ͷදݱೳྗͷ௿͞Λ໰୊ࢹ͠ɺදݱೳྗΛ্͛Δ
    (SBQI
    8BSQ
    .PEVMF ʢ(81ʣΛఏҊɺখ͞ΊͷάϥϑͰ͋Δඞཁ͕͋Δ͕ɺಛʹ૑ༀͰ݁ՌΛग़͢
    • 8FJTGFJMFS
    BOE
    MFNBO
    HP
    OFVSBM
    )JHIFSPSEFS
    HSBQI
    OFVSBM
    OFUXPSLT
    ◦ """*
    
    $ISJTUPQIFS
    .PSSJT
    FU
    BM 
    DJUBUJPOT
    ◦ )PX
    1PXFSGVM
    "SF
    ʙ
    ͷ݁ՌΛड͚ͯɺߴ࣍ͷ
    8-
    TVCUSFF
    LFSOFM
    ʹର͢Δ
    (//
    Λߏங
17. (SBQI
    /FVSBM
    /FUXPSL • -FBSOJOH
    $POWPMVUJPOBM
    /FVSBM
    /FUXPSLT
    GPS
    (SBQIT
    ◦ *$.-
    
    .BUIJBT
    /JFQFSU /&$
    -BCT
    &VSPQF
    FU
    BM
    
    DJUBUJPOT
    ◦ 8-
    HSBQI
    LFSOFM
    ͰάϥϑΛલॲཧͯ͠
    $//
    ʹೖΕΔ
    1BUDIZTBO
    ΛఏҊ
    • 8BWFMFUT
    PO
    (SBQIT
    WJB
    4QFDUSBM
    (SBQI
    5IFPSZ
    ◦ "QQMJFE
    BOE
    $PNQVUBUJPOBM
    )BSNPOJD
    "OBMZTJT
    
    %BWJE
    ,
    )BNNPOE
    FU
    BM
    
    DJUBUJPOT
    ◦ άϥϑ৴߸ॲཧͷจ຺ͰΑ͘Ҿ༻͞ΕΔ࿦จ
    • 5IF
    &NFSHJOH
    'JFME
    PG
    4JHOBM
    1SPDFTTJOH
    PO
    (SBQIT
    &YUFOEJOH
    )JHI %JNFOTJPOBM
    %BUB
    "OBMZTJT
    UP
    /FUXPSLT
    BOE
    0UIFS
    *SSFHVMBS
    %PNBJOT
    ◦ "
    *&&&
    4JHOBM
    1SPDFTTJOH
    .BHB[JOF
    
    %
    *
    4IVNBO &1'-
    FU
    BM
    
    DJUBUJPOT
    
    ◦ άϥϑ৴߸ॲཧͷจ຺ͰΑ͘Ҿ༻͞ΕΔ࿦จ
18. (SBQI
    /FVSBM
    /FUXPSL • )JHIFSPSEFS
    (SBQI
    $POWPMVUJPOBM
    /FUXPSLT
    ◦ *$.-
    
    4BNJ
    "CV&M)BJKB 6OJWFSTJUZ
    PG
    4PVUIFSO
    $BMJGPSOJB
    FU
    BM
    
    DJUBUJPOT
    ◦ POFIPQ
    ͳྡ઀ߦྻ͔Β
    NVMUJIPQ
    ͳྡ઀ߦྻ΁֦ுͨ͠
    ($/
    ΛఏҊ
    • %ZOBNJD
    (SBQI
    $POWPMVUJPOBM
    /FUXPSLT
    ◦ BS9JW
    'SBODP
    .BOFTTJ 8BZOBVU
    FU
    BM
    
    DJUBUJPOT
    ◦ ಈతʹมԽ͢Δάϥϑͷղੳ͕Մೳʹͳͬͨ
    • (SBQI
    6/FUT
    ◦ *$.-
    
    )POHZBOH
    (BP 5FYBT
    ".
    6OJWFSTJUZ
    4IVJXBOH
    +J
    
    DJUBUJPOT
    ◦ 6/FUT
    ΛάϥϑͰ΋Ͱ͖ΔΑ͏ʹ͢ΔͨΊʹɺHSBQI
    QPPMJOH
    ͱ
    HSBQI
    VOQPPMJOH
    Λఆٛ
19. (SBQI
    3FQSFTFOUBUJPO
    
20. %FFQXBML
    0OMJOF
    MFBSOJOH
    PG
    TPDJBM
    SFQSFTFOUBUJPOT #Representation #Online Learning #Graph Embedding ,%%
    
    #SZBO
    1FSP[[J
    3BNJ
    "M3GPV
    4UFWFO
    4LJFOB
    
    DJUBUJPOT άϥϑ্ͰϥϯμϜ΢ΥʔΫΛߦ͍ɺಘΒΕͨܥྻΛ
    4LJQHSBN
    ʹೖྗ͢Δ͜ͱͰ
    ϊʔυͷ෼ࢄදݱΛಘΔ  જࡏදݱΛॳظԽ
     ͋Δϊʔυ͔Βग़ൃͯ͠ϥϯμϜ ΢ΥʔΫΛߦ͏
     ಘΒΕͨܥྻΛ
    4LJQHSBN
    ΁ ೖྗ
     ؔ܎ੑͷ͍ۙϊʔυΛ༧ଌ͠ɺ άϥϑͷϕΫτϧදݱΛಘΔ ڞىͷ֬཰͚ͩͰ͸ͳ͘ɺજࡏදݱ΋Ұॹʹֶश͍ͨ͠ͷͰɺ જࡏදݱͷܭࢉίετΛԼ͛Δ޻෉͕͞Ε͍ͯΔ άϥϑͷಛ௃Λଊ͑ɺؔ܎ੑͷ͍ۙϊʔυΛۙ͘ʹ഑ஔͰ͖Δ
21. -*/&
    -BSHFTDBMF
    *OGPSNBUJPO
    /FUXPSL
    &NCFEEJOH #Graph Embedding #Edge Sampling 888
    
    +JBO
    5BOH .JDSPTPGU
    3FTFBSDI
    "TJB
    FU
    BM
    
    DJUBUJPOT ௚઀ϦϯΫΛ࣋ͨͳ͍ϊʔυͰ΋͍ۙ͠ಛ௃Λ༗͍ͯ͠ΔͳΒߟྀͯ͠
    &NCFEEJOH
    ͢Δख๏ΛఏҊ ϩʔΧϧͳߏ଄ʢpSTUPSEFS
    QSPYJNJUZʣͱ
    άϩʔόϧͳߏ଄ʢTFDPOEPSEFS
    QSPYJNJUZ
    ڞ௨͍ͯ͠Δଞͷ௖఺͕ࣅ͍ͯΔ͔Ͳ͏͔Λධ Ձʣͷ྆ํΛߟྀͯ͠
    FNCFEEJOH
    Λߦ͏ pSTUPSEFS
    QSPYJNJUZ
    
    ɹɹ௚઀؍ଌ͞ΕΔϊʔυಉ࢜ͷۙ઀ؔ܎
    second-order proximity: ɹɹಉ͡Α͏ͳྡ઀ؔ܎Λ࣋ͭۙ઀ϊʔυ ΤοδͷॏΈͷ෼ࢄ͕େ͖͘ͳΔͱֶश཰ͷௐ੔͕೉͘͠ͳΔͷͰΤοδαϯϓ ϦϯάΛ޻෉͍ͯ͠Δ 888
    ,%%
    ͔Β
    EBUB
    NJOJOH ੺
    /*14
    *$.-
    ͔Β
    NBDIJOF
    MFBSOJOH ੨
    $713
    *$$7
    ͔Β
    DPNQVUFS
    WJTJPO ྘ Ͱ
    BVUIPST
    OFUXPSL
    ΛՄࢹԽ
22. OPEFWFD
    4DBMBCMF
    'FBUVSF
    -FBSOJOH
    GPS
    /FUXPSLT #Graph Embedding #DFS #DeepWalk ,%%
    
    "EJUZB
    (SPWFS 4UBOGPSE
    6OJWFSTJUZ
    +VSF
    -FTLPWFD
    
    DJUBUJPOT %FFQ8BML
    ͷܥྻऔಘ͕
    3BOEPN
    8BML
    Ͱ͋Δͱ͜ΖΛվળ͠ɺ
    άϥϑΒ͍͠ํ๏ΛఏҊ ෯༏ઌ୳ࡧͬΆ͍
    #SFBEUIpSTU
    4BNQMJOHʢ#'4ʣͱਂ͞༏ઌ୳ࡧͬΆ͍
    %FQUIpSTU
    4BNQMJOHʢ%'4ʣΛఆٛ #'4͹͔Γॏࢹɾɾɾۙྡͷؔ܎͔͠ݟΕͳ͍ɻ͜Ε·Ͱ͸͜Εͩͬͨɻ
    ɹɹɹɹɹɹɹɹɹɹಉ͡ϊʔυ͹͔Γࢀরͯ͠͠·͏
    %'4͹͔Γॏࢹɾɾɾۙ๣ΛΑΓԕ͘ͷϊʔυ͔Βߏ੒͢Δɻ
    ɹɹɹɹɹɹɹɹɹɹͨͩ͠෼ࢄ͕େ͖͘ͳΔ αϯϓϦϯάઓུΛ࣋ͭ
    %FFQ8BML
    ΛఆࣜԽ
23. (SBQI("/
    (SBQI
    3FQSFTFOUBUJPO
    -FBSOJOH
    
    XJUI
    (FOFSBUJWF
    "EWFSTBSJBM
    /FUT #GAN #Graph Softmax """*
    
    )POHXFJ
    8BOH 4IBOHIBJ
    +JBP
    5POH
    6OJWFSTJUZ
    +JB
    8
    +JBMJO
    8
    .JBP
    ;
    8FJOBO
    ;
    'V[IFOH
    ;
    9JOH
    9JF
    .JOZJ
    (VP
    
    DJUBUJPOT w (
    ͱ
    Q@USVF
    ͕͍͍ۙͮͯ͘͜ͱΛظ଴
    w ੜ੒Ϟσϧͷ
    MPTT
    ܭࢉͰɺάϥϑߏ଄ ʹదͨ͠෯༏ઌ୳ࡧʹجͮ͘
    (SBQI
    4PGUNBY
    Λಋೖ
    w ܭࢉޮ཰΋্͕Δ ੜ੒͞ΕͨϊʔυΛࠞͥࠐΉੜ੒Ϟσϧͱɺάϥϑશମͷଥ౰ੑΛ൑ఆ͢ΔࣝผϞσϧ
    Λ༻͍ͯɺάϥϑͰ
    ("/
    Λ΍Δ (SBQI
    4PGUNBY
    Λ৽ͨʹಋೖ ҟͳΔจ຺Ͱൃల͖ͯͨ͠ੜ੒ϞσϧͱࣝผϞσϧͷ༥߹
24. 8FJTGFJMFS-FINBO
    (SBQI
    ,FSOFMT #WL test #Graph Kernel #Graph Classification #Similarity +.-3
    
    /JOP
    4IFSWBTIJE[F .BY
    1MBODL
    *OTUJUVUFT
    5VCJOHFO
    FU
    BM
    
    DJUBUJPOT  (ͱ(`ͷશͯͷϊʔυʹ͍ͭͯɺࣗ ਎ͱۙ๣ϊʔυͷϥϕϧΛूΊΔ
     ूΊͨϥϕϧΛࣙॻॱͰιʔτ
     ϥϕϧू߹ʹϢχʔΫϥϕϧΛ෇༩ ͢Δ
     ϥϕϧ਺Λ
    
    
    
    
    ͱͯ͠ɺ܁Γฦ͠ճ਺ O͕
    
    
    
    
    
    
    
    
    
    
    
    
    Λຬͨ͢·Ͱଓ͚Δ
     ৽͘͠࡞ΒΕΔϥϕϧू߹͕Ұக͠ ͍ͯΕ͹ಉܕ άϥϑͷಉܕੑΛ൑ఆ͢Δ
    8FJTGFJMFS-FINBO
    5FTU
    Λಋग़ ಉܕੑ൑ఆͰ͓ͦΒ͘Ұ൪Ҿ༻͞Ε͍ͯΔ 8-
    TVCUSFF
    LFSOFM
    ʹΑΔಛ௃ྔԽ΋
25. (SBQI
    3FQSFTFOUBUJPO • 1Z5PSDI#JH(SBQI
    "
    -BSHFTDBMF
    (SBQI
    &NCFEEJOH
    4ZTUFN
    ◦ 4ZT.-
    
    "EBN
    -FSFS 'BDFCPPL
    "*
    3FTFBSDI
    FU
    BM
    
    DJUBUJPOT
    ◦ 5SJMMJPO
    αΠζͷΤοδΛ࣋ͭάϥϑΛ
    FNCFEEJOH
    Ͱ͖Δ
    044
    • *OEVDUJWF
    3FQSFTFOUBUJPO
    -FBSOJOH
    PO
    -BSHF
    (SBQIT
    ◦ /FVS*14
    
    8JMMJBN
    -
    )BNJMUPO 4UBOGPSE
    6OJWFSTJUZ
    3FY
    :JOH
    +VSF
    -FTLPWFD
    
    DJUBUJPOT
    ◦ ۙ๣৘ใ͔Β
    FNCFEEJOH
    ΛٻΊΔͨΊͷ
    BHHSFHBUF
    ؔ਺Λֶश͢Δ͜ͱͰ ະ஌ϊʔυͷ
    FNCFEEJOH
    ΛֶशͰ͖Δɻ(SBQI4"(&
    • 3FQSFTFOUBUJPO
    MFBSOJOH
    PG
    LOPXMFEHF
    HSBQIT
    XJUI
    FOUJUZ
    EFTDSJQUJPOT
    ◦ """*
    
    
    DJUBUJPOT
    ◦ &OUJUZ
    ؚ͕·Ε͍ͯͳͯ͘΋આ໌จΛ࢖ͬͯਪ࿦͢Δ
    [FSPTIPU
    ʹऔΓ૊ΜͰ ͍Δ
26. (SBQI
    3FQSFTFOUBUJPO • 3FQSFTFOUBUJPO
    -FBSOJOH
    PO
    (SBQIT
    XJUI
    +VNQJOH
    ,OPXMFEHF
    /FUXPSLT
    ◦ *$.-
    
    ,FZVMV
    9V
    FU
    BM
    
    DJUBUJPOT
    • -FBSOJOH
    -BQMBDJBO
    .BUSJY
    JO
    4NPPUI
    (SBQI
    4JHOBM
    3FQSFTFOUBUJPOT
    ◦ BS9JW
    9JBPXFO
    %POH &1'-
    %PSJOB
    5IBOPV
    1BTDBM
    'SPTTBSE
    BOE
    1JFSSF
    7BOEFSHIFZOTU
    
    DJUBUJPOT
    ◦ σʔλ͔Βάϥϑߏ଄Λֶश͍ͨ͠ɻJMMQPTFE
    QSPCMFN
    ͕ͩάϥϑͷ׈Β͔͞ Λ͍͍ײ͡ʹ࢖͏
    • 'BTU
    (SBQI
    3FQSFTFOUBUJPO
    -FBSOJOH
    XJUI
    1Z5PSDI
    (FPNFUSJD
    ◦ *$-3
    
    .BUUIJBT
    'FZ
    
    +BO
    &
    -FOTTFO 56
    %PSUNVOE
    6OJWFSTJUZ
    
    DJUBUJPOT
    ◦ άϥϑ΍%఺܈ͱ͍ͬͨඇϢʔΫϦουߏ଄σʔλ޲͚ͷ%-ϥΠϒϥϦ 1ZUPSDI
    (FPNFUSJD
    ͷ঺հ
27. /PEF(SBQIGPDVTFE
    
28. .PEFMJOH
    3FMBUJPOBM
    %BUB
    XJUI
    (SBQI
    $POWPMVUJPOBM
    /FUXPSLT #RGCN #entity prediction #link prediction #relational data &48$
    
    .JDIBFM
    4
    4DIMJDIULSVMM 6OJWFSTJUZ
    PG
    "NTUFSEBN
    5IPNBT
    /
    ,JQG
    1FUFS
    #MPFN
    3JBOOF
    WBO
    EFO
    #FSH
    *WBO
    5JUPW
    .BY
    8FMMJOH
    
    DJUBUJPOT άϥϑߏ଄ͷ෼ੳʹओ؟Λஔ͍ͨ
    3($/
    ΛఏҊ͠ɺ
    
    FOUJUZ
    
    MJOL
    QSFEJDUJPO
    ͷ༷ʑͳσʔλͰ4P5"
    w ੺͍ϊʔυ͕ิ׬͞ΕΔ΂͖ϊʔυɺΤοδͰ͋Ε ͹ิ׬͞ΕΔ΂͖ؔ܎ੑ
    w ؔ܎ੑʹԠͯۙ͡๣͕มΘΔͱߟ͑ͯɺ৽͍͠৞ࠐ ΈΛఆٛ͢Δ
    w ߋ৽͞Εͨ৴߸͔Βϊʔυͷଐੑ༧ଌʢFOUJUZ
    QSFEJDUJPOʣ΍ 
    BDUJWBUJPO
    GVODUJPO 
    ਖ਼نԽ܎਺ 
    ຒΊࠐΈϕΫτϧ 
    SFMBUJPO
    S
    Λ৞ΈࠐΉॏΈߦྻ ؔ܎ੑΛߟྀͨ͠
    ($/
    ΛఆࣜԽ
29. άϥϑ্ͷ
    QPPMJOH
    ΛιϑτΫϥελϦϯάͱͯ͠ఆࣜԽͯ͠
    HSBQI
    DMBTTJpDBUJPO ֤ϊʔυ͕࣍ͷϨΠϠʔͰͲͷΫϥελʹଐ͢Δ͔Λผͷ//Ͱ༧ଌ ྡ઀͢Δϊʔυ͕ಉ͡Ϋϥελʹଐ͢ΔΑ͏ͳਖ਼ଇԽΛ͔͚Δ Τϯτϩϐʔਖ਼ଇԽʹΑͬͯͲΕ͔ҰͭͷΫϥελʹଐ͢Δ֬཰Λ্͛Δ #graph classification #graph pooling )JFSBSDIJDBM
    (SBQI
    3FQSFTFOUBUJPO
    -FBSOJOH
    XJUI
    %J⒎FSFOUJBCMF
    1PPMJOH /FVS*14
    
    3FY
    :JOH 4UBOGPSE
    6OJWFSTJUZ
    +JBYVBO
    :PV
    $ISJTUPQIFS
    .PSSJT
    9JBOH
    3FO
    8JMMJBN
    -
    )BNJMUPO
    +VSF
    -FTLPWFD
    
    DJUBUJPO
30. طଘͷώϡʔϦεςΟΫεΛಋग़Ͱ͖Δ
    (//
    Λ༻͍ͨ
    TVCHSBQI
    ʹΑΔϦϯΫ༧ଌ ର৅ϊʔυपลͷ৘ใͷΈΛ࢖ͬͯ΋ޡࠩΛগͳ͘Ͱ͖ΔͷͰ͸ɺͱ͍͏ΞΠσΟΞ &ODMPTJOH
    TVCHSBQI
    Λ࢖ͬͨ༧ଌ͕ྑ͍ۙࣅʹͳ͍ͬͯͨ -JOL
    1SFEJDUJPO
    #BTFE
    PO
    (SBQI
    /FVSBM
    /FUXPSLT #link prediction #enclosed subgraph /FVS*14
    
    .VIBO
    ;IBOH 8BTIJOHUPO
    6OJWFSTJUZ
    :JYJO
    $IFO
    
    DJUBUJPOT
31. "QQMJDBUJPOT
32. άϥϑͷ௿࣍ݩຒΊࠐΈΛֶश͠ɺάϥϑ΁ͷ࿦ཧԋࢉΛຒΊࠐΈۭؒͰͷ
    زԿૢ࡞ʹஔ͖׵͑Δ͜ͱͰઢܗ࣌ؒͰͷ୳ࡧΛߦ͏ ɾ࿦ཧૢ࡞ͱزԿֶૢ࡞͕׬શͳରԠΛ͍ͯ͠ͳ͍ʢ࿦ཧ൱ఆͳͲ͸ѻ͑ͳ͍ʣ
    ɾΤοδͷಛ௃Λ࢖༻͢Δ͜ͱ͕Ͱ͖ͳ͍
    ͱ͍͏໰୊͸͋Δ͕ɺෆ׬શͳ
    LOPXMFEHF
    CBTF
    ʹର͢ΔޮՌతͳΤοδ༧ଌख๏ɻ  DPOKVODUJWF
    RVFSZ
    Λ
    %"(
    ʹม׵
     BODIPS
    OPEF
    Λ௿࣍ݩ΁ຒΊࠐΈ
     FEHF
    ΛͨͲΔ࿦ཧૢ࡞ΛຒΊࠐΈۭؒͰͷ زԿૢ࡞Ͱ͋Δ
    QSPKFDUJPO
    ͱͯ͠ߦ͏
     ಘΒΕͨϕΫτϧͷ
    JOUFSTFDUJPOʢ࿦ཧ ੵʣΛܭࢉ͢Δ
     1SPKFDUJPO
    Λߦ͏
     ࠷ۙ๣๏Ͱ
    RVFSZ
    Λຬͨ͢
    OPEF
    Λ୳͢ #Graph Querying #Embedding &NCFEEJOH
    -PHJDBM
    2VFSJFT
    PO
    ,OPXMFEHF
    (SBQIT /FVS*14
    
    8JMMJBN
    -
    )BNJMUPO
    4UBOGPSE
    6OJWFSTJUZ
    %FQBSUNFOU
    PG
    $PNQVUFS
    4DJFODF
    FU
    BM
    
    DJUBUJPOT
    άϥϑΛܦ༝ͨ͠
    FNCFEEJOH
    Λߦ͏͜ͱͰɺ࿦ཧԋࢉՄೳͳੑ࣭͕࢒Δ
33. *OUFSBDUJPO
    /FUXPSLT
    GPS
    -FBSOJOH
    BCPVU
    0CKFDUT
    3FMBUJPOT
    BOE
    1IZTJDT #Physics /FVS*14
    
    1FUFS
    8
    #BUUBHMJB %FFQ.JOE
    3B[WBO
    1BTDBOV
    .BUUIFX
    -BJ
    %BOJMP
    3F[FOEF
    ,PSBZ
    ,BWVLDVPHMV
    
    DJUBUJPOT 5SVF .PEFM ෺ཧ๏ଇΛɺ෺ମͱͦͷؔ܎ੑʹ෼ղ͢Δ͜ͱͰਪଌͰ͖ΔΑ͏ʹͨ͠ w ෺ମͷ૬ޓ࡞༻ΛϞσϧԽ͢ΔͨΊʹɺ෺ମ ʢϊʔυʣͱ෺ମؒͷؔ܎ʢΤοδʣͷάϥϑ Λར༻
    w ෺ମʹର͢ΔޮՌྔΛܭࢉ͢ΔϞσϧͱɺ֎ྗ ͳͲͷ૬ޓ࡞༻Λߟྀͨ͠ঢ়ଶਪఆΛߦ͏Ϟσ ϧΛ࡞Δ ܭࢉྔ͕͔ͳΓେ͖͘ɺେن໛ͳ෺ཧ γϛϡϨʔγϣϯ͸Ͱ͖ͳ͍ ൚༻ੑ͕ߴ͘ɺҰൠతͳ෺ཧ๏ଇʹద ༻Մೳ
34. ݚڀऀ঺հ • 5IPNBT
    /
    ,JQG
    ◦ ($/
    • .BY
    8FMMJOH
    ◦ 4FNJTVQFSWJTFE
    DMBTTJpDBUJPO
    XJUI
    HSBQI
    DPOWPMVUJPOBM
    OFUXPSLT
    Ͱ
    ($/
    ͷσϑΝΫτʹ
    ◦ 7"&
    • :VKJB
    -J
    ◦ (BUFE(//
    ◦ (SBQI.BUDIJOH//
    • 1FUFS
    #BUUBHMJB
    ◦ 3FMBUJPOBM
    JOEVDUJWF
    CJBTFT
    EFFQ
    MFBSOJOH
    BOE
    HSBQI
    OFUXPSLT
    • 4UFQIBO
    (ÛOOFNBOO
    ◦ BEWFSTBSJBM
    BUUBDL
35. ݚڀऀ঺հ • ,FZVMV
    9V
    ◦ ·ֶͩੜͱࢥΘΕΔ͕ࠓޙ͍͢͝࿦จΛॻ͖ͦ͏
    ◦ Տݪྛڊେάϥϑ1+ͰབྷΈ͕͋Δʁ
    ◦ )PX
    1PXFSGVM
    BSF
    (SBQI
    /FVSBM
    /FUXPSLT
    • /JOP
    4IFSWBTIJE[F
    SJTJ
    LPOEPS
    ◦ HSBQI
    LFSOFM
    • 8JMMJBN
    -
    )BNJMUPO
    ◦ *OEVDUJWF
    3FQSFTFOUBUJPO
    -FBSOJOH
    PO
    -BSHF
    (SBQIT
    ◦ ໰୊ఏىͳͲಠಛͷ੾Γޱ
    • FUDʜ
36. 8FMDPNF άϥϑ࿦จͷαʔϕΠ΍ݚڀΛ͍ͨ͠ਓɺ
    σʔληοτΛ࡞Γ͍ͨਓɺڞಉݚڀߟ͑ͯΈ͍ͨਓɺ
    ·ͣ͸࿈བྷ͍ͩ͘͞ʂ