Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
A Degeneracy Framework for Graph Similarity: グラ...
Search
OpenJNY
November 04, 2018
Technology
0
340
A Degeneracy Framework for Graph Similarity: グラフ類似度のための縮退フレームワーク
OpenJNY
November 04, 2018
Tweet
Share
More Decks by OpenJNY
See All by OpenJNY
Linux Networking Tools: 101
openjny
63
18k
BERT の解剖学: interpret-text による自然言語処理 (NLP) モデル解釈
openjny
11
3.2k
NSG フローログを支える技術 - NVF Advanced Flow Logging
openjny
1
870
グラフ分析ナイト - グラフデータ分析 入門編
openjny
2
1k
Sports Analyst Meetup #5 LT - 目指せPGAツアー賞金王
openjny
1
1.2k
Representation Learning for Scale-free Networks: スケールフリーネットワークに対する表現学習
openjny
0
80
Handbook of Knowledge Representation - Chapter 2: Satisfiability Solvers
openjny
0
160
Other Decks in Technology
See All in Technology
Yahoo!ニュースにおけるソフトウェア開発
lycorptech_jp
PRO
0
330
kintone開発チームの紹介
cybozuinsideout
PRO
0
73k
モダンな現場と従来型の組織——そこに生じる "不整合" を解消してこそチームがパフォーマンスを発揮できる / Team-oriented Organization Design 20250825
mtx2s
5
520
Goでマークダウンの独自記法を実装する
lag129
0
210
Figma + Storybook + PlaywrightのMCPを使ったフロントエンド開発
yug1224
2
110
イオン店舗一覧ページのパフォーマンスチューニング事例 / Performance tuning example for AEON store list page
aeonpeople
2
260
攻撃と防御で実践するプロダクトセキュリティ演習~導入パート~
recruitengineers
PRO
1
140
AIとTDDによるNext.js「隙間ツール」開発の実践
makotot
5
650
Go で言うところのアレは TypeScript で言うとコレ / Kyoto.なんか #7
susisu
5
1.4k
人を動かすことについて考える
ichimichi
2
320
MySQL HeatWave:サービス概要のご紹介
oracle4engineer
PRO
4
1.7k
Claude Code x Androidアプリ 開発
kgmyshin
1
570
Featured
See All Featured
jQuery: Nuts, Bolts and Bling
dougneiner
64
7.9k
Designing Experiences People Love
moore
142
24k
Intergalactic Javascript Robots from Outer Space
tanoku
272
27k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3k
Site-Speed That Sticks
csswizardry
10
780
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
Facilitating Awesome Meetings
lara
55
6.5k
Rails Girls Zürich Keynote
gr2m
95
14k
How to Ace a Technical Interview
jacobian
279
23k
A better future with KSS
kneath
239
17k
Making the Leap to Tech Lead
cromwellryan
134
9.5k
Chrome DevTools: State of the Union 2024 - Debugging React & Beyond
addyosmani
7
820
Transcript
"%FHFOFSBDZ'SBNFXPSLGPS (SBQI4JNJMBSJUZ ౦ژۀେֶҪ্ݚ. ࢁޱॱ . άϥϑྨࣅͷͨΊͷॖୀϑϨʔϜϫʔΫ
จʹ͍ͭͯ
"CPVU1BQFS ‣ ஶऀใ w ΤίʔϧɾϙϦςΫχʔΫʢ¬DPMFQPMZUFDIOJRVFʣͱ Ξςωେֶͷڞಉݚڀ ‣ *+*$"*Ͱ࠾ ‣ બΜͩཧ༝
w άϥϑΧʔωϧʹ ڵຯ͕͋ͬͨ
ΧʔωϧͱͳΜͧ ‣ Χʔωϧؔʢ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ʣͱݺΕΔ ͕ਖ਼ఆߦྻ ͞Βʹݫີʹɺ͜Εʮਖ਼ఆΧʔωϧʯʮϚʔαʔΧʔ ωϧʯͱݺΕΔಛघͳΧʔωϧؔͰ͋Δ͕ɺඇৗʹศརͳ ͷͰҰൠతͳఆٛͱͳ͍ͬͯΔ
‣ άϥϑΧʔωϧάϥϑͷϖΞΛೖྗͱ͢ΔΧʔωϧؔ w ͭ·ΓɺάϥϑΧʔωϧͰάϥϑಉ࢜ͷྨࣅΛܭࢉ͢Δ͜ͱ͕Ͱ͖Δ ‣ ͳͥάϥϑΧʔωϧ͕ॏཁͳͷ͔ʁ w ੈͷதͷσʔλͷଟ͘ɺہॴతʹେҬతʹԿΒ͔ͷߏΛ͍࣋ͬͯΔ͜ͱ͕ଟ͘ɺ άϥϑϩεϨεͳσʔλදݱͷྑ͍ۙࣅ w
w w w w άϥϑΧʔωϧάϥϑΛೖྗͱͯ͠ѻ͑ΔΞϧΰϦζϜͷઃܭʹཱͭ άϥϑΧʔωϧͱʁ k( , ) = 100
άϥϑΧʔωϧͷԠ༻ྫ https://art.ist.hokudai.ac.jp/~takigawa/data/fpai94_takigawa.pdf
άϥϑΧʔωϧ͕͍ͬͯΔ͜ͱ k( , ) = ⟨ϕ( ), ϕ( )⟩ℋ =
100 ࠶ੜ֩ώϧϕϧτۭؒ 3,)4 σʔλۭؒʢू߹ʣ ℋ = (ℝd, ⟨ ⋅ , ⋅ ⟩ℋ ) ϕ : → ℋ ϕ( ) ϕ( ) ໌ࣔతʹಛྔΛੜʢJFࣸ૾ПΛఆٛʣͯ͠ྑ͍͕ɺΧʔωϧؔΛఆٛ͢Δ͜ͱͰɺରԠ͢Δ 3,)4ٴͼП͕ʢඇ໌ࣔతʹʣҰҙʹܾఆ͞ΕΔ͜ͱ͕ΒΕ͍ͯΔʢΧʔωϧτϦοΫʣɻ ಛϕΫτϧͷมʢҰൠʹඇઢܗࣸ૾ʣ Ұൠʹ࣍ݩEແݶେ ੵ ػցֶशք۾ͰಛۭؒʢGFBUVSFTQBDFʣͱݺΕΔͭ
ΧʔωϧؔͷΘΕ͔ͨ ‣ Χʔωϧ͕ؔྗΛൃش͢Δͷɿ 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) ಛʹάϥϑΧʔωϧ͜͜Ͱॏཁ
ຊʹΔ
͜ͷจͰఏҊ͢Δͷ ‣ άϥϑͷ֊ߏΛ໌ࣔతʹར༻͢Δ৽ͨͳάϥϑΧʔωϧΛఏҊ w ֊ߏΛௐΔͷʹL$PSFͱݺΕΔ֓೦Λ׆༻ w ఏҊ͢Δख๏ʢJFL$PSFϑϨʔϜϫʔΫʣɺطଘͷάϥϑΧʔωϧʹదԠՄೳͰ͋ Γɺ͞ΒʹҰൠͷάϥϑϚονϯάख๏ʹదԠͰ͖Δ w ͭ·Γɺ
ఏҊάϥϑΧʔωϧ طଘάϥϑΧʔωϧ ʷ L$PSFϑϨʔϜϫʔΫ ‣ ఏҊख๏Λ༻͍Δͱɺ47.Λ༻͍ͨάϥϑྨλεΫʹ͓͍ͯɺطଘ ͷάϥϑΧʔωϧΑΓฏۉBDDVSBDZ্͕ͨ͠
άϥϑͷॖୀʢ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ʹͳ͍ϊʔυΛͬͯΔʣΤοδΛআͯ͠ಘΒΕΔ෦άϥϑ
LDPSFͷྫ ͱͷάϥϑͰ࣍ͷϊʔυʢC D V ʜʣ͋Δ͕ɺ ༠ಋ෦άϥϑ͚ͩͰ࣍Λୡ͢Δͷ͕ෆՄೳ DPSFଘࡏ͠ͳ͍
LDPSFղΞϧΰϦζϜ ‣ ࣍ͷখ͍͞ॱʹɺશͯͷϊʔυʹ ͍ͭͯௐ͍ͯ͘ w ࠓߏங͍ͯ͠ΔLDPSFΑΓ͕࣍খ͚͞ ΕͦΕΛLDPSF͔Βআ w ͯ͢ͷ͕࣍LҎ্ʹͳͬͨͷΛ֬ೝ͠ ͨΒLDPSFΛొ
‣ ܭࢉͷΦʔμʔ0 / . w /ϊʔυ w .Τοδ ઢܗ࣌ؒͰܭࢉՄೳͳͷͰɺޙड़ͷఏҊ ख๏Ͱ͜ͷܭࢉ͕ൺֱతϘτϧωοΫ ʹͳΓʹ͍͘
LDPSFͷಛ ‣ LDPSFͷಛɿ෦ू߹ੑ ‣ L͕େ͖͘ͳΔʹͭΕɺΑΓॏཁͳ ใΛؚΜͰ͍Δͱߟ͑ΒΕΔ w ྫ͑ιʔγϟϧωοτϫʔΫͰɺத৺త ਓͰߏ͞ΕΔίϛϡχςΟʔ͕֘ Cδ*(G)
⊆ … ⊆ C1 ⊆ C0 = G LDPSF͕ߏஙͰ͖Δ࠷େͷLάϥϑͷॖୀ άϥϑͷྨࣅLDPSF͝ͱͷྨࣅͰଌΔͷ͕ྑ͍ͷͰʁ
ఏҊख๏
ʲఏҊख๏ʳ$PSF7BSJBOUPG#BTF,FSOFM ‣ ϕʔεͱͳΔάϥϑΧʔωϧΛ༻ҙ͢Δ w ྫʣLϫΠεϑΝΠϥʔɾϦʔϚϯʢ8FJTGFJMFS-FINBOʣΧʔωϧ ‣ ༩͑ΒΕͨͭͷάϥϑʹରͯ͠ɺͦΕͧΕͷશLDPSFΛܭࢉ͢Δ w ྫʣ(ͷLDPSFT\$ $
$ $^ (`ͷLDPSFT\$` $` $`^ ‣ ಉ͡ϨϕϧͷLDPSFΛೖྗͱͨ͠άϥϑΧʔωϧͷग़ྗΛ͠߹ΘͤΔ w ྫʣL@D ( (` L $ $` L $ $` L $ $` L ɾ ɾ ͕άϥϑΧʔωϧ͡Όͳͯ͘ɺάϥϑͷϖΞ Λೖྗͱ͢Δҙͷؔʹར༻Ͱ͖Δ LDPSFϑϨʔϜϫʔΫ
$PNQVUBUJPOBM$PNQMFYJUZ ‣ LDPSFϑϨʔϜϫʔΫͷܭࢉෳࡶ͞ w ɹɹɿάϥϑͷϖΞΛೖྗͱ͢ΔؔʢFHάϥϑΧʔωϧʣͷܭࢉෳࡶ͞ w ɹɹɿೖྗάϥϑͷॖୀʢJFLDPSF͕ଘࡏ͢Δ࠷େͷLʣͷখ͍͞ํ ‣ Ұൠʹɺάϥϑͷॖୀͷ্ք࣍ͷͲͪΒ͔Ͱ༩͑ΒΕΔ w
άϥϑͷ࠷େ࣍ w ྡߦྻͷ࠷େݻ༗ ‣ ɹɹϊʔυΑΓेʹখ͍͞ʢɹɹɹɹʣ͜ͱ͕ଟ͍ͷͰɺLDPSF ϑϨʔϜϫʔΫʹཁ͢ΔՃܭࢉൺֱతͯ͘ࡁΉ c = A × δ* min A δ* min λmax λmax λmax ≪ n
࣮ݧ
࣮ݧͷηοςΟϯά ‣ σʔληοτɿ w όΠΦΠϯϑΥϚςΟΫεͱιʔγϟϧ ωοτϫʔΫ༝དྷͷσʔληοτΛར༻ ‣ ྨɿ w 47.Λར༻ͯ͠ྨλεΫΛղ͘
w ύϥϝʔλGPME$7Ͱܾఆ ‣ ൺֱ͢ΔάϥϑΧʔωϧɿ w ϕʔεάϥϑΧʔωϧछʷఏҊϑϨʔ ϜϫʔΫͷ༗ແछྨ όΠΦΠϯϑΥ ιʔγϟϧωοτ https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets
݁ՌʢฏۉBDDVSBDZͱͦͷࢄʣ ଠࣈͷࣈɺUݕఆʢ༗ҙਫ ४ʣʹΑͬͯɺ$03&ϑϨʔ ϜϫʔΫͷੑೳ্͕༗ҙʹ ೝΊΒΕͨέʔεΛද͢ɻ
݁ՌʢฏۉBDDVSBDZͱͦͷࢄʣ ଠࣈͷࣈɺUݕఆʢ༗ҙਫ ४ʣʹΑͬͯɺ$03&ϑϨʔ ϜϫʔΫͷੑೳ্͕༗ҙʹ ೝΊΒΕͨέʔεΛද͢ɻ όΠΦܥͷσʔλΑΓιʔγϟϧ ωοτܥͷσʔλͷํ͕ੑೳ্͕ ΈΒΕͨ ԾઆʮίΞ͕େ͖͍LDPSFͷ ΄͏͕ॏཁʯΛࢧ࣋͢Δ݁Ռ
݁ՌʢฏۉBDDVSBDZͱͦͷࢄʣ ଠࣈͷࣈɺUݕఆʢ༗ҙਫ ४ʣʹΑͬͯɺ$03&ϑϨʔ ϜϫʔΫͷੑೳ্͕༗ҙʹ ೝΊΒΕͨέʔεΛද͢ɻ (3Ͱݦஶʹੑೳ্͕ΈΒΕ ΔҰํ 8-Ͱ͍·͍ͪޮՌͳ͠ 8-֤ϊʔυͷۙΛཁ ͢ΔΑ͏ͳΧʔωϧͳͷ
ͰɺײతʹLDPSFͷ ֓೦ͱ͋·Γ૬ҧແ͠
None
࣮ߦ࣌ؒͷ૿େʹؔ͢Δߟ ‣ ϕʔεΧʔωϧͷ࣮ߦ࣌ؒʹର͢ΔɺLDPSF֦ு ͷ૬ର࣮ߦ࣌ؒΛࣔͨ͠ද ‣ *.%##*/"3:ͱ*.%#.6-5*Ͱඇৗʹ࣮ߦ ͕࣌ؒ͘ͳ͍ͬͯΔ͕ɺੑೳ্Λߟྀ͢Δͱ ܾͯ͠๏֎ͳͷͰͳ͍ʢͱओுʣ
ιʔγϟϧωοτϫʔΫͰੑೳ্͕ݦஶͳཧ༝ ‣ ωοτϫʔΫͷ͕࣍ҟͳΔ ‣ ͖ଇʹै͏ωοτϫʔΫɺΑΓத৺ͷLDPSFʹ༗ӹͳใ͕٧ ·͍ͬͯΔͱߟ͑ΕΔ
୯ҰLDPSFΛͬͨBDDVSBDZ ‣ ೖྗΛɺΦϦδφϧͷάϥϑͰͳ͘ɺ LDPSFͱஔ͖͑ͨ߹ͷBDDVSBDZ w LͷLDPSFάϥϑͦͷͷͳͷͰஔ͖ ͑͠ͳ͍ ‣ ؍ଌɿ w
ʲ$PSF(3ʳ୯ௐతʹখ͍͞LͰੑೳ্ w ʲ(3ʳL ͰɺΦϦδφϧͷάϥϑΛೖྗ ͤͨ͞߹ΑΓੑೳ͕ྑ͘ͳ͍ͬͯΔ ʢײʣඞཁ࠷ݶͷใ͕٧·͍ͬͯΔ࠷খͷ෦ άϥϑ͕͜ͷ͋ͨΓͳͷͰʁ IMDB-BINARYͰͷGRͱCore GR
·ͱΊ
·ͱΊ LDPSFղʹجͮ͘ϑϨʔϜϫʔΫ ‣ LDPSF࠷খ͕࣍LͰ͋Δ࠷େ༠ಋ෦άϥϑ ‣ LDPSF㱬 L DPSFͰ͋Δ͜ͱΛར༻ͯ͠ɺάϥϑͷ֊ߏ͝ͱʹൺֱΛߦ͏ϑϨʔϜϫʔΫΛఏҊ ‣
ຊจͰάϥϑΧʔωϧʹద༻͕ͨ͠ɺҙͷάϥϑϚονϯάΞϧΰϦζϜʹద༻Ͱ͖Δ ͜ͷϑϨʔϜϫʔΫʹΑͬͯɺάϥϑྨλεΫʹ͓͍ͯطଘͷά ϥϑΧʔωϧͷੑೳΛ্ͤͨ͞ ‣ ιʔγϟϧωοτϫʔΫͳͲͷɺεέʔϧϑϦʔωοτϫʔΫͰ༗ޮ ‣ LDPSFʹࣅͨ֓೦ͷطଘάϥϑΧʔωϧʹରͯ͠ޮՌ͍·͍ͪ