Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Representation Learning for Scale-free Networks...

OpenJNY
November 09, 2018

Representation Learning for Scale-free Networks: スケールフリーネットワークに対する表現学習

OpenJNY

November 09, 2018
Tweet

More Decks by OpenJNY

Other Decks in Science

Transcript

  1. ैདྷͷάϥϑຒΊࠐΈख๏  ࣗવݴޠॲཧͷք۾Ͱ༗໊ͳXPSEWFD<.JLPMPWFUBM>ΛɺϊʔυຒΊࠐΈʢ/PEF&NCFEEJOHʣ ʹద༻ͨ͠OPEFWFD<(SPWFSBOE-FTLPWFD>͕੒ޭΛऩΊ͍ͯΔ  ୯ޠϊʔυ  ηϯςϯεάϥϑ্ͷϥϯμϜ΢ΥʔΫྻ  ·ͨɺϊʔυຒΊࠐΈ͸ɺଟ༷ମֶशͱݺ͹ΕΔ

    ඇઢܗ࣍ݩ࡟ݮख๏ͷҰ෦ͷύʔτͱͯ͠ɺੲ͔ Β੝Μʹݚڀ͞Ε͍ͯΔλεΫͷͻͱͭ  ϥϓϥγΞϯݻ༗Ϛοϓ๏ʢ-BQMBDJBO&JHFONBQʣ <#FMLJOBOE/JZPHJ>͕༗໊  σʔλؒͷྨࣅ౓ΛΤοδͷॏΈͱͨ͠ྨࣅ౓ά ϥϑʢTJNJMBSJUZHSBQIʣΛߏஙͯ͠ɺ͜ͷྡ઀ߦ ྻͷݻ༗஋෼ղͰ௿࣍ݩຒΊࠐΈΛಘΔ https://www.cs.cmu.edu/~aarti/Class/10701/slides/Lecture21_2.pdf
  2. ैདྷख๏ͷ໰୊఺  ঺հͨ͠ैདྷख๏͸ɺ఺ؒͷؔ܎ͷΑ͏ͳɺωοτϫʔ Ϋ͕࣋ͭہॴతͳߏ଄ͷ৘ใΛอ࣋͢ΔΑ͏ͳຒࠐΛߦ͏  ͔͠͠εέʔϧϑϦʔੑ͸େҬతͳ৘ใͷͻͱͭ  ݱ࣮ͷωοτϫʔΫʹසൟʹݟΒΕΔ͜ͷ৘ใΛແࢹ͢Δͷ ͸೗Կͳ΋ͷ͔ʁ 

    ࣮ࡍɺಘΒΕͨຒΊࠐΈͰ΋ͱͷάϥϑΛ࠶ߏஙͨ͠ͱ͖ɺ ैདྷख๏͸IJHIEFHSFFͳϊʔυ਺͕ଟ͘ͳΔ܏޲ʹ͋Δ  ͭ·ΓɺຒΊࠐΈۭؒͰσʔλಉ͕࢜ͻ͖ͬͭ͗ͯ͢ɺશମ తʹ͙ͪΌͬͱͳͬͯ͠·͍ͬͯΔ ʮଟ͘ͷϊʔυͷۙ͘ʹډΕΔݖརΛɺগ਺ϊʔυʹ͚ͩ༩͑Δʯ੍໿͕ඞཁ
  3. ͦ΋ͦ΋εέʔϧϑϦʔੑ͸FNCFEͰ͖Δͷ͔໰୊  ௚ײతʹ͸ɺຒΊࠐΈۭؒʹ͓͍ͯσʔλ͕ΰνϟͬͱͯ͠͠·͏͔Βɺάϥϑ࠶ߏங࣌ʹߴ࣍਺ϊʔ w w w υ͕૿͑ͯ͠·͏ͱਪଌͰ͖Δ  ΰνϟͬͱ͍ͯ͠Δߴ࣍਺ϊʔυ͕ଟ͘ͷ௿࣍਺ϊʔυΛۙ͘ʹҾ͖دͤΔ͕ނʹɺҾ͖دͤΒΕͨ௿࣍਺ϊʔ υಉ࢜ʹ΋άϥϑ࠶ߏங࣌ʹΤοδ͕݁͹Εͯ͠·͏Α͏ͳঢ়ଶ

     Ͱ͸ԿΒ͔ͷ੍໿ΛՃ͑ͯɺΰνϟͬͱ͠ͳ͍Α͏ʹͰ͖Δͷ͔ʁ  ྫ͑͹࣍ݩϢʔΫϦουۭؒʹຒΊࠐΈΛ͢ΔͳΒɺc7cͰ͢Βແཧͦ͏  ͔ͱ͍ͬͯc7cʹରͯ͠ɺ.࣍ݩͷۭؒΛ༻ҙ͢Δͷ͸΍Γա͗ʜ  ͦ͜Ͱɺ,࣍ݩͷϢʔΫϦουۭؒʹຒΊࠐΜͩ࣌ʹɺ໰୊ͳ͘εέʔϧϑϦʔੑΛ࠶ߏஙͰ͖ΔΑ͏ ͳϊʔυ਺ͷ࠷େ஋ʢʹର͢ΔԼքʣʹ͍ͭͯɺཧ࿦తͳղੳΛߦͬͨ
  4. ݁࿦͚ͩड़΂Δͱ
 ໰୊ͳͦ͞͏ k 10 20 50 100 lower bound 57

    3325 637M 4E+17 .@LL࣍ݩϢʔΫϦουۭؒʹ͓͍ͯɺத৺Y൒ܘЏͷ௒ٿ# Y Џ ͷ தʹɺ͓ޓ͍͕ЏҎ্཭ΕͯΔ఺Λ࠷େͰԿݸ഑ஔͰ͖Δ͔ʁ ʢ࣍ݩͳΒʣ࣍਺͕& ͷεʔύʔϋϒ ͷपΓʹɺ࣍਺͕ͷ༿ϊʔυΛ& ݸຒΊ ࠐΈͰ͖Δ େମͷݱ࣮ੈքͷωοτϫʔΫ͸ɺे෼ʹεέʔ ϧϑϦʔੑΛอ࣋ͨ͠··ຒΊࠐΈՄೳ ͪͳΈʹ ఆཧ͸ɺϊʔυ͕࠷େͰԿݸ഑ஔͰ͖Δ͔ ໰୊Λɺٿॆరʢ4QIFSF1BDLJOHʣ໰୊ɺ ͋Δ͍͸ٿମͷ࠷ີॆర໰୊ͱͯ͠஌ΒΕΔ ໰୊ʹؼண͢Δ͜ͱͰূ໌͞Ε͍ͯΔɻ
  5. ϏʔόʔͱΦόϚɺ஥ྑ͠໰୊΁ͷରॲࡦ  ैདྷख๏ͷଟ͘͸TU OEPSEFSͷQSPYJNJUZΛอͭ͜ͱʹઐ೦  TUPSEFSQSPYJNJUZ˺ʮ༑ୡʯ౓߹͍  OEPSEFSQSPYJNJUZ˺ʮ༑ୡͷ༑ୡʯ౓߹͍  ͦͷ݁ՌɺεέʔϧϑϦʔωοτϫʔΫʹଘࡏ͢ΔlCJHIVCzಉ࢜͸ྨࣅ౓͕ߴ͘ͳΓ΍͍͢

     ྫʣΦόϚͷ༑ୡʹ͸ɺδϟεςΟϯɾϏʔόʔͱ༑ୡͳਓ͕ਓͰ΋ډΔ֬཰͸ߴ͍  ྨࣅ౓͕ߴ͘ͳΓ΍͍͢ͳΒɺ࣍਺͕ߴ͍ϊʔυͷQSPYJNJUZʹϖφϧςΟΛ༩͑Ε͹ྑ͍ جຊతํ਑ཧ࿦ղੳͷ݁Ռʹج͖ͮɺεέʔϧϑϦʔੑΛ୲อͰ͖ ΔຒΊࠐΈΞϧΰϦζϜͷͨΊͷ࣍਺േଇʢEFHSFFQFOBMUZʣݪଇ ΛఏҊ͢Δɻ࣍਺േଇ͸ɺ࣍ٴͼ࣍ͷQSPYJNJUZΛ୲อ্ͨ͠Ͱɺ ߴ͍࣍਺Λ΋ͭ௖఺ಉ࢜ͷQSPYJNJUZʹରͯ͠േΛՊ͢ݪଇͰ͋Δɻ
  6. ఏҊख๏%14QFDUSBM 2nd-order proximity 1st & 2nd-order proximity weighted adjacency matrix

    ྡ઀ߦྻ ࣍਺ߦྻ%EJBH E@ ʜ E@O https://www.slideshare.net/pecorarista/ss-51761860 ॏΈ෇͖ྡ઀ߦྻʢXFJHIUFEBEKBDFODZNBUSJYʣͷྫ
  7. ఏҊख๏%14QFDUSBM ͩTG 2nd-order proximity 1st & 2nd-order proximity weighted adjacency

    matrix ྡ઀ߦྻ ࣍਺ߦྻ%EJBH E@ ʜ E@O J K ؒͷQSPYJNJZ͕ߴ͍ʢ8@JK ͷ஋͕େ͖͍ʣͳΒɺຒΊࠐΈ ͷڑ཭Λ୹͍ͨ͘͠ ॏཁ౓ʢ%@JʣͰεέʔϧௐઅͨ͠ޙ ͷۭؒͰɺ௨ৗͷݻ༗ϕΫτϧͷੑ࣭ Λຬͨ͠ ͯཉ͍͠ʢҰൠԽݻ༗஋໰୊ʣ ∀i : u⊤ i Dui = 1 ∀i, j(i ≠ j) : u⊤ i Duj = 0 Wij = 1 (di dj )β C′ ij ࣍਺ͷߴ͞ʹରͯ͠ࢦ਺ తͳϖφϧςΟΛ՝͢
  8. ఏҊख๏%14QFDUSBM ͩTG 2nd-order proximity 1st & 2nd-order proximity weighted adjacency

    matrix ྡ઀ߦྻ ࣍਺ߦྻ%EJBH E@ ʜ E@O J K ؒͷQSPYJNJZ͕ߴ͍ʢ8@JK ͷ஋͕େ͖͍ʣͳΒɺຒΊࠐΈ ͷڑ཭Λ୹͍ͨ͘͠ ॏཁ౓ʢ%@JʣͰεέʔϧௐઅͨ͠ޙ ͷۭؒͰɺ௨ৗͷݻ༗ϕΫτϧͷੑ࣭ Λຬͨ͠ ͯཉ͍͠ʢҰൠԽݻ༗஋໰୊ʣ ∀i : u⊤ i Dui = 1 ∀i, j(i ≠ j) : u⊤ i Duj = 0 LͳΒ Wij = 1 (di dj )β C′ ij ࣍਺ͷߴ͞ʹରͯ͠ࢦ਺ తͳϖφϧςΟΛ՝͢ ৽نੑ͸8ͷ࡞Γํ
  9. σʔληοτ Vertex Edge |V| |E| Synthetic 10K 400K Facebook Ϣʔβ

    ༑ୡ 4K 88K Twitter Ϣʔβ ϑΥϩʔ 81K 1.76M Author ஶऀ ڞஶ 5K 29K Citation ஶऀ Ҿ༻ 48K 357K Mobile ొ࿥ऀ ௨࿩ 198K 1.15M
  10. ൺֱख๏ ུশ Ҿ༻ ৄࡉ ϥϓϥγΞϯݻ༗ Ϛοϓ๏ LE Belkin and Niyogi

    2003 εϖΫτϧϕʔεͷຒΊࠐΈख๏ɻ DP-Spectral ͱͷҧ͍͸ɺྨࣅ౓ߦྻͷߏங๏ํ๏ Deep Walk DW Perozzi, Al-Rfou, and Skiena 2014 skip-gram Ϟσϧʹجͮ͘ຒΊࠐΈɻ֤௖఺͔Β10ݸͷϥϯ μϜ΢ΥʔΫྻʢྻ௕:40ʣΛੜ੒͢Δɻ DP-Walker ͱͷҧ͍͸ɺભҠ֬཰͕Ұ༷Ͱ͋Δ͜ͱ ఏҊख๏1 DP-Spectral - LE + ྨࣅ౓ߦྻʹ࣍਺േଇΛద༻ ఏҊख๏2 DP-Walker - DW + ϥϯμϜ΢ΥʔΫͷભҠ֬཰ʹ࣍਺േଇΛద༻ શख๏ڞ௨ͯ͠ɺຒΊࠐΈ࣍ݩ͸Λ࠾༻
  11. λεΫ  ωοτϫʔΫͷ࠶ߏங  ʲ໨తʳεέʔϧϑϦʔੑΛอ࣋ͨ͠ຒΊࠐΈ  ʲํ๏ʳલड़௨Γʢলུʣ  ʲධՁʳೖྗͱ࠶ߏஙωοτϫʔΫͷͦΕͧΕͷ࣍਺෼෍ΛٻΊɺϐΞιϯͷੵ཰૬ؔ܎਺ <

    >Λܭࢉ͢Δʢߴ͍ͱྑ͍ʣ  ʲඋߟʳ֤ख๏Ͱɺ͔Β·Ͱͷൣғ ࠁΈ ͰЏΛಈ͔͠ɺ࠷ྑ࣌ͷ૬ؔ܎਺Λใࠂ  ϦϯΫ༧ଌ  ʲ໨తʳϊʔυWJ WKؒʹΤοδ͕͋Δ͔ͷ༧ଌ  ʲํ๏ʳຒΊࠐΈۭؒͰͷࠩ෼V@JV@KΛಛ௃ྔͱͯ͠ઢܗճؼϞσϧʹೖྗ͢Δ  ʲධՁʳਫ਼౓ʢQSFDJTJPOʣɺ࠶ݱ཰ʢSFDBMMʣɺ'஋ʢ'TDPSFʣ  ʲඋߟʳແ࡞ҝʹબ͹ΕͨϊʔυϖΞͷू߹Λ܇࿅ධՁσʔλʢͦΕͧΕશϊʔυϖΞͷ ʣͱ͢Δ  ϊʔυ෼ྨ  ʲ໨తʳϊʔυʹ෇༩͞Ε͍ͯΔϥϕϧͷ༧ଌ  ʲํ๏ʳ༩͑ΒΕͨW@Jʹରͯ͠ɺຒΊࠐΈV@JΛಛ௃ϕΫτϧͱͯ͠ઢܗ෼ྨػʹೖྗ  ʲධՁʳਖ਼ղ཰ʢBDDVSBDZʣ  ʲඋߟʳσʔληοτ$JUBUJPOͰͷΈλεΫΛ࣮ߦɻϥϕϧ͸ͭͷݚڀ෼໺ i P((i, j ) ∈ E ) ≜ sigmoid(w⊤(ui − ui) + b) j {Architecture Computer Network Computer Science Data Mining Theory Graphics Unknown i P(i ∈ l ) ≜ softmax(w⊤ l ui + bl )
  12. ݁ՌɿωοτϫʔΫ࠶ߏஙλεΫ ຒΊࠐΈ࣍ݩ േଇͷڧ͞ Wij = 1 (didj)β C′ ij %14QFDUSBMͷ΄͏͕ෆ҆ఆͳͷ͸ɺЌ͕௚઀໨తؔ਺ʹ૊Έࠐ·Ε͍ͯ

    Δ͔Βɻ%18BMLFS͸ϥϯμϜ΢ΥʔΫྻੜ੒ʹ͔͔͔͠ΘΒͳ͍ 4ZOUIFUJDͱ'BDFCPPLͰ࠷దͳЌ͕ҟͳΔ͕ɺ͜Ε͸േଇ͕࣍਺ͷߴ͞ ͦͷ΋ͷʹ՝ͤΒΕ͍ͯΔ͔ΒͰɺτϙϩδʔ͕มΘΕ͹Ќͷޮ͖۩߹͍ ͸มԽ͢Δɻ εέʔϧϑϦʔੑΛ୲อ͢Δͷʹे෼ͳ࣍ݩ਺͕ଘࡏ͢Δ͜ͱ͕෼͔Δɻ %14QFDUSBM͸ຒΊࠐΈ࣍ݩ͕গͳ͍ͱੑೳ͕ඇৗʹѱ͍͕ɺ%18BMLFS ͸࣍ݩ਺͕૿͑ͯ΋͋·ΓมԽͤͣɺ҆ఆͯ͠ྑ͍݁ՌɻϥϯμϜ΢Υʔ Ϋͷઓུ͕ޮ͍͍ͯΔͷ͕ཁҼͰ͋ΔͱਪଌͰ͖Δɻ
  13. ײ૝  ʮ୯ʹطଘख๏ʹߴ࣍਺ͷϊʔυʹϖφϧςΟΛ՝͚ͩ͢ʯͱ͍͏ࢸͬͯγϯϓϧͳख๏Ͱɺগ͠ݞ͔͢͠Λ৯ Βͬͨɻ  ͱ͸͍͑)JHIPSEFSQSPYJNJUZΛ֫ಘ͢ΔຒΊࠐΈख๏͸ɺաڈʹ͋·Γͳ͍ͷͰ༗ӹ  ʢϊʔυຒΊࠐΈʹର͢ΔʣεϖΫτϧ෼ղख๏͸ɺύϥϝʔλʢFHຒΊࠐΈ࣍ݩ਺ʣʹରͯ͠ඇৗʹ҆ఆ͠ ͳ͍͜ͱ͕Θ͔ͬͨͷ͸େ͖ͳऩ֭ɻ 

    ϥϯμϜ΢ΥʔΫख๏͕҆ఆ͍ͯ͠Δͷ͸ɺඇઢܗͳQSPYJNJUZΛ௿࣍ݩͳۭؒͰ্खʹଊ͑ΒΔ͔ΒʁʢXPSEWFDͷڧΈ Λ׆༻Ͱ͖͍ͯΔͷ͸ؒҧ͍ͳͦ͞͏ʣ  εέʔϧϑϦʔੑͷอ࣋ͷͨΊʹ͸ɺ࣍਺ϖφϧςΟҎ֎ʹ΋खஈ͸͋Γͦ͏ɻ  ҰൠͷϊʔυຒΊࠐΈख๏ʹద༻Ͱ͖ΔɺεέʔϧϑϦʔੑΛ֫ಘ͢Δҝͷϝλઓུख๏͕"""*Ͱൃද͞Ε͍ͯΔ  ͪ͜Β͸άϥϑΛ֊૚ߏ଄ʹ෼ׂ͠େہతߏ଄ͷຒΊࠐΈΛ֫ಘ͍ͯ͠Δ  LDPSFΛ࢖ͬͯάϥϑΧʔωϧΛվળͨ͠ϝλઓུͱࣅ͍ͯͯɺLDPSFΛ࢖ͬͨϊʔυຒΊࠐΈͰ΋εέʔϧϑϦʔੑ͕֫ ಘͰ͖ͦ͏ʢ͜ͷख๏ͷ࿦จ͕ൃද͞ΕΔͷ͸࣌ؒͷ໰୊ͳؾ΋͢Δ͕ʜʣ /JLPMFOU[PT (JBOOJT FUBM"%FHFOFSBDZ'SBNFXPSLGPS(SBQI4JNJMBSJUZ*+$"* $IFO )BPDIFO FUBM)"31IJFSBSDIJDBMSFQSFTFOUBUJPOMFBSOJOHGPSOFUXPSLT"""*