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
370
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
890
グラフ分析ナイト - グラフデータ分析 入門編
openjny
2
1k
Sports Analyst Meetup #5 LT - 目指せPGAツアー賞金王
openjny
1
1.2k
Representation Learning for Scale-free Networks: スケールフリーネットワークに対する表現学習
openjny
0
88
Handbook of Knowledge Representation - Chapter 2: Satisfiability Solvers
openjny
0
180
Other Decks in Technology
See All in Technology
AI時代の発信活動 ~技術者として認知してもらうための発信法~ / 20251028 Masaki Okuda
shift_evolve
PRO
1
110
激動の時代を爆速リチーミングで乗り越えろ
sansantech
PRO
1
140
プロファイルとAIエージェントによる効率的なデバッグ / Effective debugging with profiler and AI assistant
ymotongpoo
1
340
Azure Well-Architected Framework入門
tomokusaba
1
140
ソースを読む時の思考プロセスの例-MkDocs
sat
PRO
1
290
CREが作る自己解決サイクルSlackワークフローに組み込んだAIによる社内ヘルプデスク改革 #cre_meetup
bengo4com
0
350
仕様駆動開発を実現する上流工程におけるAIエージェント活用
sergicalsix
1
410
NLPコロキウム20251022_超効率化への挑戦: LLM 1bit量子化のロードマップ
yumaichikawa
3
540
マルチエージェントのチームビルディング_2025-10-25
shinoyamada
0
200
Kubernetes self-healing of your workload
hwchiu
0
570
SCONE - 動画配信の帯域を最適化する新プロトコル
kazuho
1
400
アウトプットから始めるOSSコントリビューション 〜eslint-plugin-vueの場合〜 #vuefes
bengo4com
3
1.8k
Featured
See All Featured
Optimizing for Happiness
mojombo
379
70k
RailsConf 2023
tenderlove
30
1.3k
Visualization
eitanlees
149
16k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
21
1.2k
Thoughts on Productivity
jonyablonski
70
4.9k
Writing Fast Ruby
sferik
630
62k
Producing Creativity
orderedlist
PRO
347
40k
Done Done
chrislema
185
16k
Rebuilding a faster, lazier Slack
samanthasiow
84
9.2k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
230
22k
How to Think Like a Performance Engineer
csswizardry
27
2.1k
Leading Effective Engineering Teams in the AI Era
addyosmani
7
640
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ʹࣅͨ֓೦ͷطଘάϥϑΧʔωϧʹରͯ͠ޮՌ͍·͍ͪ