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

A Degeneracy Framework for Graph Similarity: グラ...

OpenJNY
November 04, 2018

A Degeneracy Framework for Graph Similarity: グラフ類似度のための縮退フレームワーク

OpenJNY

November 04, 2018
Tweet

More Decks by OpenJNY

Other Decks in Technology

Transcript

  1. Χʔωϧͱ͸ͳΜͧ΍ ‣ Χʔωϧؔ਺ʢLFSOFMGVODUJPOʣ͸σʔλ఺ಉ࢜ͷྨࣅ౓ΛଌΔؔ਺ w ڭࢣ͋ΓֶशͷҝͷػցֶशΞϧΰϦζϜʹ͸ɺڭࢣσʔλͱͷۙ͞ͷ৘ใ͚ͩΛཔΓ ʹֶशɾ༧ଌΛߦ͏΋ͷ΋ʢFHαϙʔτϕΫτϧϚγϯʣ w ਓؒ΋ಉ༷ɿະ஌ͳ΋ͷʹରͯ͠ɺྨࣅ౓͕ߴ͍ط஌৘ใͰਪ࿦ ‣ ਖ਼֬ʹ͸ɺΧʔωϧؔ਺ɹɹɹɹɹɹɹɹɹ͸ɺ࣍ͷ৚݅Λຬͨؔ͢਺

    w ରশੑɿ w ਖ਼ఆ஋ੑɿ k : × → ℝ+ ∀x, y ∈ : k(x, y) = k(y, x) ∀n ∈ ℕ, x1 , …, xn ∈ : (Gij ) ≜ (k(xi , xj )) ∈ ℝn×n (͸άϥϜߦྻʢ(SBNNBUSJY (SBNJBOʣͱݺ͹ΕΔ ͕൒ਖ਼ఆ஋ߦྻ ͞Βʹݫີʹ͸ɺ͜Ε͸ʮਖ਼ఆ஋Χʔωϧʯ΍ʮϚʔαʔΧʔ ωϧʯͱݺ͹ΕΔಛघͳΧʔωϧؔ਺Ͱ͋Δ͕ɺඇৗʹศརͳ ͷͰҰൠతͳఆٛͱͳ͍ͬͯΔ
  2. άϥϑΧʔωϧ͕΍͍ͬͯΔ͜ͱ k( , ) = ⟨ϕ( ), ϕ( )⟩ℋ =

    100 ࠶ੜ֩ώϧϕϧτۭؒ 3,)4 σʔλۭؒʢू߹ʣ ℋ = (ℝd, ⟨ ⋅ , ⋅ ⟩ℋ ) ϕ : → ℋ ϕ( ) ϕ( ) ໌ࣔతʹಛ௃ྔΛੜ੒ʢJFࣸ૾ПΛఆٛʣͯ͠΋ྑ͍͕ɺΧʔωϧؔ਺Λఆٛ͢Δ͜ͱͰɺରԠ͢Δ 3,)4ٴͼП͕ʢඇ໌ࣔతʹʣҰҙʹܾఆ͞ΕΔ͜ͱ͕஌ΒΕ͍ͯΔʢΧʔωϧτϦοΫʣɻ ಛ௃ϕΫτϧ΁ͷม׵ʢҰൠʹ͸ඇઢܗࣸ૾ʣ Ұൠʹ͸࣍ݩ਺E͸ແݶେ ಺ ੵ ػցֶशք۾Ͱ͸ಛ௃ۭؒʢGFBUVSFTQBDFʣͱݺ͹ΕΔ΍ͭ
  3. Χʔωϧؔ਺ͷ࢖ΘΕ͔ͨ ‣ Χʔωϧؔ਺͕ྗΛൃش͢Δͷ͸ɿ w ಛ௃ϕΫτϧʢ΁ࣹӨ͢Δؔ਺ʣͷઃܭ͕೉͍͠ͱ͖ w ֶशΞϧΰϦζϜͰඞཁͳܭࢉ͕ɺಛ௃ۭؒ಺Ͱͷσʔλಉ࢜ͷ಺ੵʢJFΧʔωϧؔ਺ͷग़ྗ஋ʣ ͷΈʹґଘ͢Δͱ͖ ‣ ·ͨɺΧʔωϧؔ਺Λ࢖͏ͱઢܗͳֶशΞϧΰϦζϜΛඇઢܗԽͰ͖Δʂ

    w ໨తؔ਺Λࣜมܗͨ͠Γ࠷దԽ໰୊ͷ૒ର໰୊Λղ͘͜ͱͰɺಛ௃ϕΫτϧ͕಺ੵͷܗͰ͔͠ݱΕ ͳ͍ࣜͷΈͷΞϧΰϦζϜΛߏ੒͢Δ w ʲྫʳΧʔωϧԽLNFEPJET๏ɺΧʔωϧओ੒෼෼ੳʢ,FSOFM1$"ʣɺαϙʔτϕΫτϧϚγϯ ʢ47.ʣɺΧʔωϧԽϦοδճؼɺಈܘجఈؔ਺ωοτϫʔΫʢ3#'/FUXPSLʣɺFUD ̂ f(x) = ̂ w⊤ϕ(x) = ( N ∑ i=1 ̂ αi ϕ(xi ) ) ⊤ ϕ(x) = N ∑ i=1 ̂ αi k (x, xi) ಛʹάϥϑΧʔωϧ͸͜͜Ͱॏཁ
  4. άϥϑͷॖୀʢEFHFOFSBDZʣ ‣ ॖୀʢEFHFOFSBDZʣ͸άϥϑʹର͢Δੑ࣭ w ແ޲άϥϑ͕Lॖୀ LEFHFOFSBUF Ͱ͋Δͱ͸ɺ೚ҙͷ ෦෼άϥϑ͕ߴʑLͷ࣍਺ͷ௖఺ΛؚΉͱ͖Λ͍͏ ‣ LDPSF<4FJENBO>

    w άϥϑ( 7 & ͷLDPSFͱ͸ɺશͯͷ௖఺ͷ࣍਺͕L Ҏ্Ͱ͋Δ(ͷ࠷େ༠ಋ෦෼άϥϑCk = (S, E(S)) ∀v ∈ S : degree(v) ≥ k ∀(u, v) ∈ E : u, v ∈ S ⟹ (u, v) ∈ E(S) ˢʮ4 㱪7 ʹΑΔ༠ಋ෦෼άϥϑ 4 & 4 ʯͷఆٛ ˢ஫ҙ༠ಋ෦෼άϥϑʹ͓͚Δ࣍਺ ؆୯ʹݴͬͯ͠·͏ͱɺ4ʹؔ܎ͳ͍ʢ4ʹͳ͍ϊʔυΛ࢖ͬͯΔʣΤοδΛ࡟আͯ͠ಘΒΕΔ෦෼άϥϑ
  5. LDPSF෼ղΞϧΰϦζϜ ‣ ࣍਺ͷখ͍͞ॱʹɺશͯͷϊʔυʹ ͍ͭͯௐ΂͍ͯ͘ w ࠓߏங͍ͯ͠ΔLDPSFΑΓ΋࣍਺͕খ͚͞ Ε͹ͦΕΛLDPSF͔Β࡟আ w ͢΂ͯͷ࣍਺͕LҎ্ʹͳͬͨͷΛ֬ೝ͠ ͨΒLDPSFΛొ࿥

    ‣ ܭࢉͷΦʔμʔ͸0 / .  w /ϊʔυ਺ w .Τοδ਺ ઢܗ࣌ؒͰܭࢉՄೳͳͷͰɺޙड़ͷఏҊ ख๏Ͱ΋͜ͷܭࢉ͕ൺֱతϘτϧωοΫ ʹͳΓʹ͍͘
  6. ʲఏҊख๏ʳ$PSF7BSJBOUPG#BTF,FSOFM ‣ ϕʔεͱͳΔάϥϑΧʔωϧΛ༻ҙ͢Δ w ྫʣLϫΠεϑΝΠϥʔɾϦʔϚϯʢ8FJTGFJMFS-FINBOʣΧʔωϧ ‣ ༩͑ΒΕͨͭͷάϥϑʹରͯ͠ɺͦΕͧΕͷશLDPSFΛܭࢉ͢Δ w ྫʣ(ͷLDPSFT\$ $

    $ $^ (`ͷLDPSFT\$` $` $`^ ‣ ಉ͡ϨϕϧͷLDPSFΛೖྗͱͨ͠άϥϑΧʔωϧͷग़ྗ஋Λ଍͠߹ΘͤΔ w ྫʣL@D ( (` L $ $`  L $ $`  L $ $` L ɾ ɾ ͕άϥϑΧʔωϧ͡Όͳͯ͘΋ɺάϥϑͷϖΞ Λೖྗͱ͢Δ೚ҙͷؔ਺ʹར༻Ͱ͖Δ LDPSFϑϨʔϜϫʔΫ
  7. $PNQVUBUJPOBM$PNQMFYJUZ ‣ LDPSFϑϨʔϜϫʔΫͷܭࢉෳࡶ͞͸ w ɹɹɿάϥϑͷϖΞΛೖྗͱ͢Δؔ਺ʢFHάϥϑΧʔωϧʣͷܭࢉෳࡶ͞ w ɹɹɿೖྗάϥϑͷॖୀ਺ʢJFLDPSF͕ଘࡏ͢Δ࠷େͷLʣͷখ͍͞ํ ‣ Ұൠʹɺάϥϑͷॖୀ਺ͷ্ք͸࣍ͷͲͪΒ͔Ͱ༩͑ΒΕΔ w

    άϥϑͷ࠷େ࣍਺ w ྡ઀ߦྻͷ࠷େݻ༗஋ ‣ ɹɹ͸ϊʔυ਺ΑΓे෼ʹখ͍͞ʢɹɹɹɹʣ͜ͱ͕ଟ͍ͷͰɺLDPSF ϑϨʔϜϫʔΫʹཁ͢Δ௥Ճܭࢉ͸ൺֱత୹ͯ͘ࡁΉ c = A × δ* min A δ* min λmax λmax λmax ≪ n
  8. ࣮ݧͷηοςΟϯά ‣ σʔληοτɿ w όΠΦΠϯϑΥϚςΟΫεͱιʔγϟϧ ωοτϫʔΫ༝དྷͷσʔληοτΛར༻ ‣ ෼ྨ໰୊ɿ w 47.Λར༻ͯ͠෼ྨλεΫΛղ͘

    w ௒ύϥϝʔλ͸GPME$7Ͱܾఆ ‣ ൺֱ͢ΔάϥϑΧʔωϧɿ w ϕʔεάϥϑΧʔωϧछʷఏҊϑϨʔ ϜϫʔΫͷ༗ແछྨ όΠΦΠϯϑΥ ιʔγϟϧωοτ https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets
  9. ୯ҰLDPSFΛ࢖ͬͨBDDVSBDZ ‣ ೖྗΛɺΦϦδφϧͷάϥϑͰ͸ͳ͘ɺ LDPSFͱஔ͖׵͑ͨ৔߹ͷBDDVSBDZ w LͷLDPSF͸άϥϑͦͷ΋ͷͳͷͰஔ͖׵ ͑͸͠ͳ͍ ‣ ؍ଌɿ w

    ʲ$PSF(3ʳ୯ௐతʹখ͍͞LͰੑೳ޲্ w ʲ(3ʳL ͰɺΦϦδφϧͷάϥϑΛೖྗ ͤͨ͞৔߹ΑΓ΋ੑೳ͕ྑ͘ͳ͍ͬͯΔ  ʢײ૝ʣඞཁ࠷௿ݶͷ৘ใ͕٧·͍ͬͯΔ࠷খͷ෦ ෼άϥϑ͕͜ͷ͋ͨΓͳͷͰ͸ʁ IMDB-BINARYͰͷGRͱCore GR
  10. ·ͱΊ LDPSF෼ղʹجͮ͘ϑϨʔϜϫʔΫ ‣ LDPSF࠷খ࣍਺͕LͰ͋Δ࠷େ༠ಋ෦෼άϥϑ ‣ LDPSF㱬 L  DPSFͰ͋Δ͜ͱΛར༻ͯ͠ɺάϥϑͷ֊૚ߏ଄͝ͱʹൺֱΛߦ͏ϑϨʔϜϫʔΫΛఏҊ ‣

    ຊ࿦จͰ͸άϥϑΧʔωϧʹద༻͕ͨ͠ɺ೚ҙͷάϥϑϚονϯάΞϧΰϦζϜʹద༻Ͱ͖Δ ͜ͷϑϨʔϜϫʔΫʹΑͬͯɺάϥϑ෼ྨλεΫʹ͓͍ͯطଘͷά ϥϑΧʔωϧͷੑೳΛ޲্ͤͨ͞ ‣ ιʔγϟϧωοτϫʔΫͳͲͷɺεέʔϧϑϦʔωοτϫʔΫͰ༗ޮ ‣ LDPSFʹࣅͨ֓೦ͷطଘάϥϑΧʔωϧʹରͯ͠͸ޮՌ͸͍·͍ͪ