Back to : cs-adventure
Contents

Kim, H., Choi, Y., Park, K., Lin, X., Hong, S. H., & Han, W. S. (2021). Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching. Proceedings of the ACM SIGMOD International Conference on Management of Data, 925โ€“937. https://doi.org/10.1145/3448016.3457265

๊ด€๋ จ ํฌ์ŠคํŒ… : Subgraph Isomorphism : Introduction ์„ ๋จผ์ € ์ฝ์–ด์ฃผ์„ธ์š”!

Introduction

์ด๋ฒˆ์— ์ •๋ฆฌํ•  ๋…ผ๋ฌธ์€ ์ œ๊ฐ€ 2020๋…„ 2ํ•™๊ธฐ์— ์—ฐ๊ตฌ์‹ค ํ•™๋ถ€์ƒ ์ธํ„ด์œผ๋กœ ์ง€๋„ ๋ฐ›์•˜๋˜ ์„œ์šธ๋Œ€ํ•™๊ต ์ปดํ“จํ„ฐ์ด๋ก  ๋ฐ ์‘์šฉ ์—ฐ๊ตฌ์‹ค (๋ฐ•๊ทผ์ˆ˜ ๊ต์ˆ˜๋‹˜ ์—ฐ๊ตฌํŒ€) ์—์„œ ์ด๋ฒˆ 2021๋…„ SIGMOD์— ๋ฐœํ‘œํ•œ ๋…ผ๋ฌธ์ด์ž, ์ œ ์ด๋ฒˆ ์ฐฝ์˜ํ†ตํ•ฉ์„ค๊ณ„์™€ ๋ฐ€์ ‘ํ•œ ๊ด€๋ จ์ด ์žˆ๋Š” ๋…ผ๋ฌธ์ž…๋‹ˆ๋‹ค. (๊ทธ๋ž˜์„œ ๋‹ค๋ฅธ ๋…ผ๋ฌธ์— ๋น„ํ•ด ํ›จ์”ฌ ์ž์„ธํžˆ ์ฝ์—ˆ์Šต๋‹ˆ๋‹ค. ์ด ๋…ผ๋ฌธ์„ ๋˜‘๊ฐ™์ด ๊ตฌํ˜„ํ•  ๊ฐ์˜ค(?) ๋ฅผ ํ•˜๊ณ  ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์—โ€ฆ)

Subgraph isomorphism์— ๊ด€ํ•œ ๋…ผ๋ฌธ ์ •๋ฆฌํ• ๊ฒŒ 2ํŽธ ๋” ๋‚จ์•˜๋Š”๋ฐ, introduction์— ๋งค์šฐ ํฐ ๊ณตํ†ต์ ์ด ์žˆ์œผ๋ฏ€๋กœ, Subgraph Isomorphism : Introduction ๋ผ๋Š” ํฌ์ŠคํŒ…์„ ๋ณ„๋„๋กœ ์ž‘์„ฑํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ํฌ์ŠคํŒ…์œผ๋กœ Intro ๋‚ด์šฉ ๋Œ€๋ถ€๋ถ„์„ ๋•Œ์šฐ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ํฌ๊ฒŒ๋Š” ์œ„ ํฌ์ŠคํŒ…์—์„œ ๋‹ค๋ฃฌ, Filtering - Matching order - Backtracking ์˜ ํ‹€ ์œ„์—์„œ ์„ค๋ช…๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Key Ideas

Filtering : DAG Graph DP

๋” ๊ฐ•ํ•œ ํ•„ํ„ฐ๋ง์„ ์œ„ํ•ด, ์šฐ๋ฆฌ๋Š” ์–ด๋–ค ์ ๋‹นํ•œ ์ˆœ์„œ๋กœ DP๋ฅผ ๋Œ๋ ค์„œ Candidate Set (CS) ๋ผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๊ตฌ์ถ•ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„์—์„œ DP๋ฅผ ๋Œ๋ฆฌ๊ธฐ ์œ„ํ•ด์„œ๋Š” DPํ•  ์ˆœ์„œ๊ฐ€ ํ•„์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, Query Graph๋กœ๋ถ€ํ„ฐ DAG๋ฅผ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์ด๋•Œ DAG๋Š” label์ด ์ข€ uniqueํ•˜๋ฉด์„œ degree๊ฐ€ ํฐ ์ •์ ์„ ํ•˜๋‚˜ ์žก์•„์„œ, ๊ทธ ์ •์ ์—์„œ BFS๋ฅผ ๋Œ๋ ค์„œ ์–ป์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ $q_D$๋ผ๊ณ  ํ•˜๊ณ , ๋‚˜์ค‘์— ์—ญ๋ฐฉํ–ฅ์œผ๋กœ ๋Œ๋ฆฌ๊ธฐ ์œ„ํ•ด $q_D$์˜ inverse DAG $q_D^{-1}$ ๋กœ ๋งŒ๋“ญ๋‹ˆ๋‹ค.

CS๋Š” ๊ฐ $u \in V_q$์— ๋Œ€ํ•ด, ์ง‘ํ•ฉ $C(u)$ ์™€ ๊ทธ ์ง‘ํ•ฉ์˜ $v_{ip} \in C(u_i)$, $v_{jq} \in C(u_j)$ ์‚ฌ์ด์— ์ด์–ด์ง„ ๊ฐ„์„ ์„ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. ์ด ์ž๋ฃŒ๊ตฌ์กฐ๋Š” DAF[^ref-daf] ์—์„œ ์ œ์‹œ๋œ ์ž๋ฃŒ๊ตฌ์กฐ์ด์ง€๋งŒ, VEQ์—์„œ๋Š” ๋” ๊ฐœ์„ ๋œ ๋ฒ„์ „์œผ๋กœ ์ ์šฉ๋ฉ๋‹ˆ๋‹ค. ์ตœ์ดˆ์˜ CS๋Š” label๊ณผ $G$์—์„œ์˜ ์—ฐ๊ฒฐ๊ด€๊ณ„๋งŒ ๊ฐ€์ง€๊ณ  ๋Œ€์ถฉ ๋งŒ๋“ค์–ด ๋†“๊ณ  (label์ด ๊ฐ™์€ ์ •์ ๋“ค์„ ์ง‘์–ด๋„ฃ๊ณ , ๊ทธ ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ •์ ์„ BFS ์ˆœ์„œ๋กœ ๋Œ๋ฉด์„œ ๋นŒ๋“œ) ์ด๋ฅผ ์ค„์—ฌ๋‚˜๊ฐˆ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

DAG DP๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ $\abs{V_q}\abs{V_G}$ ํฌ๊ธฐ์˜ ํฐ boolean DP ํ…Œ์ด๋ธ”์„ ์ฑ„์›Œ๋‚˜๊ฐ€๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. ์ด ํ…Œ์ด๋ธ” D๋Š” $D(u_i, v_j)$ ๊ฐ€ ๊ณง $v_j \in C(u_i)$๋ฅผ ์˜๋ฏธํ•˜๋Š” DP๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. DAG์˜ ๋ฆฌํ”„๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์˜ฌ๋ผ์˜ค๋ฉด์„œ, ๋‹ค์Œ์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.

$D(u, v)$ ๊ฐ€ 1์ผ ํ•„์š”์ถฉ๋ถ„์กฐ๊ฑด : $u$์˜ ๋ชจ๋“  ์ž์‹ ๋…ธ๋“œ $u_c$์— ๋Œ€ํ•ด,

  • $^\exists v_c$ adjacent to $v$, $D(u_c, v_c) = 1$

์ด ์กฐ๊ฑด๊นŒ์ง€๋Š” DAF์—์„œ ์‚ฌ์šฉํ•œ DP์˜ ์ •์˜์ž…๋‹ˆ๋‹ค. VEQ์—์„œ๋Š” ์—ฌ๊ธฐ์„œ ๋” ๊ฐ•ํ•œ ์กฐ๊ฑด์„ ์š”๊ตฌํ•˜์—ฌ ๋” ๊ฐ•ํ•œ ํ•„ํ„ฐ๋ง์„ ๋‹ฌ์„ฑํ•ฉ๋‹ˆ๋‹ค.
$D(u, v)$ ๊ฐ€ 1์ผ ํ•„์š”์ถฉ๋ถ„์กฐ๊ฑด : $u$์˜ ๋ชจ๋“  ์ž์‹ ๋…ธ๋“œ $u_c$์— ๋Œ€ํ•ด DAF์—์„œ์˜ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋ฉฐ, $(u, v)$๊ฐ€ ๋ชจ๋“  label $l$์— ๋Œ€ํ•ด ๋‹ค์Œ์„ ๋งŒ์กฑํ•œ๋‹ค.

  • label์ด $l$์ธ $u$์˜ ์ธ์ ‘ ๋…ธ๋“œ $u_{l_i}$๋“ค์— ๋Œ€ํ•ด, $C(u_{l_i})$์— ํฌํ•จ๋˜๋Š” ์ •์ ๋“ค์„ ๋ชจ๋‘ ๋ชจ์€ ๋‹ค์Œ, ๊ทธ๋“ค ์ค‘ $v$์™€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ์ •์ ๋“ค (์ฆ‰, $v$์—์„œ extend ๊ฐ€๋Šฅํ•œ) ๋งŒ ์ฑ™๊ฒจ์„œ, ์ด๋ฅผ $N(u, v, l)$ ์ด๋ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์ด $N(u, v, l)$์˜ ํฌ๊ธฐ๊ฐ€, ์ ์–ด๋„ $u$์˜ ์ธ์ ‘ ๋…ธ๋“œ๋“ค ์ค‘ label์ด $l$์ธ ๋…ธ๋“œ๋ณด๋‹ค๋Š” ๋งŽ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค.

์ฆ‰, ์ง๊ด€์ ์œผ๋กœ, ๋งŒ์•ฝ $u_1$์„ $v_1$์— ๋งคํ•‘ํ•ด๋†“๊ณ  ๋ณด๋‹ˆ๊นŒ $u_1$์—๋Š” ๋ผ๋ฒจ์ด $l$์ธ ์ด์›ƒ์ด ์—ฌ์„ฏ๊ฐœ ์žˆ๋Š”๋ฐ $v_1$์—์„œ extend๊ฐ€๋Šฅํ•œ ๋ผ๋ฒจ $l$์ธ ์ด์›ƒ์ด ๋„ค๊ฐœ๋ฐ–์— ์—†๋Š” ์ƒํ™ฉ์„ ๋ฏธ๋ฆฌ ํŒ๋‹จํ•ด์„œ ๋ฐฉ์ง€ํ•œ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ด ์กฐ๊ฑด์„ VEQ ๋…ผ๋ฌธ์—์„œ๋Š” โ€œNeighbor-Safetyโ€๋ผ๊ณ  ์ •์˜ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ์กฐ๊ฑด์€ ๋ฏธ๋ฆฌ preprocessing์„ ๋นก์„ธ๊ฒŒ ํ•ด์„œ ์ž˜ ๊ตฌํ˜„ํ•˜๋ฉด ์›๋ž˜์˜ DP์™€ ๊ฐ™์€ ์‹œ๊ฐ„ ๋ณต์žก๋„ $O(\abs{E_q}\abs{E_G})$์— ๊ฐ€๋Šฅํ•˜๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๋˜ํ•œ, ์ด DP๋ฅผ ์ตœ๋Œ€ํ•œ ์ž˜ ์ค„์ด๊ธฐ ์œ„ํ•ด, query DAG๋ฅผ ์—ฌ๋Ÿฌ๊ฐœ ์“ฐ๋ฉด ๋” ์ข‹์€ ๊ฒฐ๊ณผ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์‹ค์ œ๋กœ๋Š” $q_D, q_D^{-1}, q_D$ ์ˆœ์„œ๋กœ ๋ฐ˜๋ณตํ•˜๋ฉด์„œ ์“ฐ๋ฉด ๋˜๋Š”๋ฐ, ๋…ผ๋ฌธ์— ์˜ํ•˜๋ฉด 3๋ฒˆ๋งŒ ํ•˜๋ฉด ๋”์ด์ƒ ํฐ ์˜๋ฏธ ์—†๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

Adaptive Matching Order : Static Equivalence

Adaptive Matching Order๋ž€, Matching order๋ฅผ ๋ฏธ๋ฆฌ ์ •ํ•˜์ง€ ์•Š๊ณ , ๋ฐฑํŠธ๋ž˜ํ‚น ํ•˜๋Š” ์ค‘์— ๋‹ค์ด๋‚˜๋ฏนํ•˜๊ฒŒ ์ •ํ•ด ๋‚˜๊ฐ€๊ฒ ๋‹ค๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค. ํ˜„์žฌ๊นŒ์ง€ ์ฐพ์€ partial embedding $M$์— ๋Œ€ํ•ด, $M$์— ์ด๋ฏธ ํฌํ•จ๋œ ์ •์ ๊ณผ ์ด์›ƒํ•œ ์ •์ ๋“ค์„ extendableํ•˜๋‹ค๊ณ  ์ •์˜ํ•˜๊ณ , ์ด๋•Œ Candidate Set $C(u)$์— ๋“ค์–ด ์žˆ๋Š” ์ •์ ๋“ค ์ค‘ partial embedding $M$์„ ๊ณ ๋ คํ•  ๋•Œ $u$์™€ ๋งค์นญ ๊ฐ€๋Šฅํ•œ ์ •์ ๋“ค์„ $C_M(u)$ ๋ผ๊ณ  ์ •์˜ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. (์ฆ‰, $C(u)$์— ์žˆ๋”๋ผ๋„, ์ด๋ฏธ $M$์—์„œ ์ด์›ƒ๋“ค์„ ๋งค์นญํ–ˆ์„ ๋•Œ $u_c$๋ฅผ $v_c$์—๋‹ค๊ฐ€ ๋Œ€๊ณ  ๋งค์น˜ํ–ˆ๋‹ค๋ฉด, $v_c$์™€ ์ด์›ƒํ•˜๋Š” ์ ๋งŒ ๋‚จ๊ธฐ๊ณ  ๋‚˜๋จธ์ง€๋Š” ๋‚ ๋ฆฌ๊ฒ ๋‹ค๋Š” ๋ง์ž…๋‹ˆ๋‹ค)

Extendable vertex์ค‘ ํ•˜๋‚˜๋ฅผ ํƒํ•ด์„œ ๋‹ค์Œ ์ •์ ์œผ๋กœ ์‚ผ๊ณ  backtrackingํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. CFL-Match์™€ DAF์˜ ๊ฒฝ์šฐ ์ด๋ถ€๋ถ„์—์„œ vertex๋ฅผ core-forest-leaf ๋˜๋Š” core-leaf๋กœ ๋‚˜๋ˆ ์„œ ๋งค์นญํ•˜๋Š” ์ „๋žต์„ ์“ฐ๋Š”๋ฐ, ์ด ๋…ผ๋ฌธ์—์„œ๋Š” ์ด์™€ ๊ฐ™์€ decomposition์ „๋žต์ด leaf๊ฐ€ ์ ์„ ๋•Œ ๋Š๋ ค์„œ ๋ณ„๋กœ ์ข‹์ง€ ์•Š๋‹ค๊ณ  ์ฃผ์žฅํ•ฉ๋‹ˆ๋‹ค.

๋Œ€์‹ ์—, ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ๋ฒ•์„ ์”๋‹ˆ๋‹ค.

  • DAG DP๋ฅผ ํ•  ๋•Œ, ๋ฏธ๋ฆฌ query์— ๋Œ€ํ•ด์„œ NEC (Neighbor Equivalence Class) ๋ผ๋Š” ๊ธฐ๋ฒ•์„ ์ด์šฉํ•ด์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๋ฅผ ํ•ฉ์น  ๊ฒƒ์ž…๋‹ˆ๋‹ค. NEC๋Š” 2013๋…„ Turbo-Iso๋ผ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Postech์˜ ํ•œ์šฑ์‹  ๊ต์ˆ˜๋‹˜ ์—ฐ๊ตฌํŒ€) ๋…ผ๋ฌธ ์ค‘์— ์ œ์‹œ๋œ ๋ฐฉ๋ฒ•์œผ๋กœ, label์ด ๊ฐ™๊ณ  ์ด์›ƒํ•˜๋Š” vertex๊ฐ€ ๊ฐ™์€ leaf๋ฅผ ํ•˜๋‚˜๋กœ ํ•ฉ์ณ๋ฒ„๋ฆฐ ๋‹ค์Œ (์ฆ‰, $u_3$์— ๋ฆฌํ”„ $u_4$ ์™€ $u_5$๊ฐ€ ๋‹ฌ๋ ค์žˆ๋Š”๋ฐ ๋‘ ๋ผ๋ฒจ์ด ๊ฐ™์œผ๋ฉด) ์ด๋ฅผ ๊ธฐ๋กํ•ด๋‘๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด๊ฒŒ ๋ง์ด ๋˜๋Š” ์ด์œ ๋Š” ์–ด์ฐจํ”ผ $u_4$๊ฐ€ ๋งค์นญ๋  ์ˆ˜ ์žˆ๋Š” ๋…ธ๋“œ๋ผ๋ฉด $u_5$๋„ ํ•ญ์ƒ ๋งค์นญ ๊ฐ€๋Šฅํ•ด์„œ, ๋‘๊ฐœ์˜ ์ž„๋ฒ ๋”ฉ์ด ๋™์‹œ์— ์ฐพ์•„์ง€๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค (๋‘˜๋‹ค ๋ฆฌํ”„์ด๋ฏ€๋กœ ๋‹ค๋ฅธ ๋…ธ๋“œ๋ฅผ ๊ณ ๋ คํ•  ํ•„์š”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค)
  • ๋งŒ์•ฝ ๋ฆฌํ”„ $u$๊ฐ€ ์กด์žฌํ•˜์—ฌ, $\abs{NEC(u)}$์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ณ ๋ คํ•  ๋•Œ ์•„์ง ๋งค์นญ๋˜์ง€ ์•Š์€ $C_M(u)$์˜ ๋…ธ๋“œ๊ฐ€ ์ถฉ๋ถ„ํžˆ ์žˆ๋‹ค๋ฉด ์ด์ชฝ์œผ๋กœ ๊ฐ€์„œ ๋งค์นญํ•ฉ๋‹ˆ๋‹ค.
  • ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด, ๋ฆฌํ”„๋ฅผ ์šฐ์„ ์ ์œผ๋กœ ๋งค์นญํ•˜๊ณ ,
  • ๋ฆฌํ”„๊ฐ€ ์—†์œผ๋ฉด, $\abs{C_M(u)}$๊ฐ€ ์ž‘์€ ๋…ธ๋“œ๋ถ€ํ„ฐ ๋งค์นญํ•ฉ๋‹ˆ๋‹ค.

์ฐธ๊ณ ๋กœ, DAF์˜ ๊ฒฝ์šฐ ๋‘๊ฐœ์˜ adaptive matching order ์ค‘ ํ•˜๋‚˜๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๋‘ ๊ฐ€์ง€ ์ค‘ ํ•˜๋‚˜๊ฐ€ $C_M(u)$์˜ ํฌ๊ธฐ๊ฐ€ ์ž‘์€ ๋…ธ๋“œ๋ถ€ํ„ฐ ๋งค์นญํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

Run time pruning : Dynamic Equivalence

๋ฐฑํŠธ๋ž˜ํ‚น์„ ํ•˜๋Š” ์ค‘์—๋„, ๊ณ„์† Search space๋ฅผ ์ค„์ด๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด์„œ, Candidate Space๋ฅผ ์ž˜ ๊ด€์ฐฐํ•˜์—ฌ Equivalence Tree์˜ ๊ฐœ๋…์„ ์ •๋ฆฝํ•ฉ๋‹ˆ๋‹ค.

$C(u)$์˜ ์›์†Œ $v_i, v_j$์— ๋Œ€ํ•ด, $v_i, v_j$์™€ ์—ฐ๊ฒฐ๋œ $C(u_c)$์˜ vertex ๊ฐ€ ๋ชจ๋“  $u$์˜ ์ด์›ƒ $u_c$ ์— ๋Œ€ํ•ด ๊ฐ™์œผ๋ฉด, ๋‘ ๋…ธ๋“œ๋ฅผ Neighbor equivalent in $C(u)$๋ผ๊ณ  ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ํ†ตํ•ด, Cell ์ด๋ผ๋Š” ๊ฐœ๋…์„ ์ •์˜ํ•˜๋Š”๋ฐ, cell $\pi(u, v)$๋Š” $C(u)$์—์„œ $v$์™€ equivalentํ•œ $v_i$๋“ค์˜ ์ง‘ํ•ฉ์œผ๋กœ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฏธ์ง€๋Š” VEQ ์›๋ณธ ๋…ผ๋ฌธ์˜ ์ด๋ฏธ์ง€์ธ๋ฐ, ๋ง๋กœ ์„ค๋ช…ํ•˜๋ฉด ์กฐ๊ธˆ ๊ท€์ฐฎ์ง€๋งŒ ๊ฐœ๋… ์ž์ฒด๋Š” ์ง๊ด€์ ์ž…๋‹ˆ๋‹ค.

figure

Partial embedding $M$๊ณผ, $C(u)$์—์„œ equivalentํ•œ ๋…ธ๋“œ $v_i, v_j$๊ฐ€ ์žˆ์„๋•Œ, $u \to v_i$๋ฅผ ๋งค์นญํ•ด ๋ณธ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, $v_j$์™€ $v_i$๋Š” ๊ทธ ํŠน์„ฑ์ด ๋งค์šฐ ๋น„์Šทํ•œ ๋…ธ๋“œ์ด๊ธฐ ๋•Œ๋ฌธ์—, $u \to v_j$๋ฅผ ์ •๋ง ๋ชจ๋‘ ํ™•์ธํ•˜๋Š” ๊ฒƒ์€ ๋ญ”๊ฐ€ ๊ธฐ๋ถ„์ด ๋งค์šฐ ๋‚˜์ฉ๋‹ˆ๋‹ค.

๋…ผ๋ฌธ์—์„œ๋Š” ์ด๋ฅผ ์œ„ํ•ด, ๋งˆ์ง€๋ง‰์œผ๋กœ subtree equivalence๋ฅผ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. Partial embedding ์„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์ฒ˜๋Ÿผ ์“ฐ๊ณ  ์žˆ๋‹ค๋Š” ์ ์— ์ฃผ์˜ํ•ด์„œ notation์„ ์ฝ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

$M \cup (u, v_i)$๋ฅผ ๋ฃจํŠธ๋กœ ํ•˜๋Š” ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ, $(uโ€™, v_i)$๋Š” ๋”์ด์ƒ ๋‚˜ํƒ€๋‚˜์„œ๋Š” ์•ˆ ๋˜๋Š” conflict๋“ค์ž…๋‹ˆ๋‹ค ($v_i$๋Š” ์ด๋ฏธ $u$์™€ ๋งค์นญ๋˜์—ˆ์œผ๋ฏ€๋กœ) ์ด๋“ค์„ $I_M(u, v_i)$๋ผ ํ•˜๊ณ , ์ด ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ $v_i \not\in \pi(uโ€™, vโ€™)$์ธ ๋ชจ๋“  ๋งคํ•‘ (์ฆ‰, $v_i$์™€ equivalence๊ด€๊ณ„๋ฅผ ๊ฐ–์ง€ ์•Š๋Š” ๋งคํ•‘) ๋“ค์˜ ์ง‘ํ•ฉ์„ $O_M(u, v_i)$ ๋ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, Negative cell $\pi^{-}(u, v_i)$๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.

  • ๋งŒ์•ฝ $v_i$์— ๋Œ€ํ•œ conflict๊ฐ€ ํ•œ๋ฒˆ์ด๋ผ๋„ ์žˆ์—ˆ๋‹ค๋ฉด, $\pi(u, v_i)$์™€ $\cap_{(uโ€™, v_i) \in I_M(u, v_i)} \pi(uโ€™, v_i)$์˜ intersection. ์ฆ‰, $v_i$์™€ ๋งค์นญ๋˜๊ณ  ์‹ถ์–ดํ•œ๋‹ค๋Š” ์ด์œ ๋กœ conflict๋ฅผ ๋งŒ๋“œ๋Š” $uโ€™$๋“ค์— ๋Œ€ํ•ด, $v_i$๋ฅผ ๋”ฐ๋ผ๋‹ค๋‹ˆ๋ฉด์„œ ๋ชจ๋“  ๊ณณ์—์„œ $v_i$์™€ equivalentํ•œ ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ.
  • Conflict๊ฐ€ ์—†์—ˆ๋‹ค๋ฉด $\pi(u, v_i)$๋กœ ๊ทธ๋Œ€๋กœ ๊ฐ€์ ธ๊ฐ‘๋‹ˆ๋‹ค.

๋˜ํ•œ, $\delta_{M}(u, v_i)$๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜ํ•ฉ๋‹ˆ๋‹ค. \(\bigcup_{(u', v') \in O_M(u, v_i)} \pi(u', v')\) ์ง๊ด€์ ์œผ๋กœ ์ด๋Š”, $v_i$์™€ equivalentํ•˜์ง€ ์•Š์€ ๋ชจ๋“  ๋งคํ•‘๋“ค์— ๋Œ€ํ•ด์„œ, ๊ทธ equivalence class๋“ค์„ ๋ชจ์€ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์ด๋ฅผ ์ด์šฉํ•˜์—ฌ, Equivalence Set $\pi_M(u, v_i)$๋ฅผ ์ •์˜ํ•ฉ๋‹ˆ๋‹ค.

  • ํ•œ๋ฒˆ์ด๋ผ๋„ ์ด ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ์„ฑ๊ณตํ•œ ์‚ฌ๋ก€๊ฐ€ ์žˆ๋Š” ๊ฒฝ์šฐ, $\pi^{-}(u, v_i) - \delta_M(u, v_i)$๋ฅผ ์”๋‹ˆ๋‹ค.
  • ๋ชจ๋‘ ์‹คํŒจํ•œ ๊ฒฝ์šฐ, $\pi^{-}(u, v_i)$๋ฅผ ์”๋‹ˆ๋‹ค.

์ด equivalence class๋Š”, ์ง„์ •ํ•œ subtree equivalence์ด๊ธฐ ๋•Œ๋ฌธ์—, $v_j \in \pi_M(u, v_i)$ ์ธ ๊ฒฝ์šฐ, $v_j$๋ฅผ $v_i$๋Œ€์‹  ์ด์šฉํ•˜๋Š” ๋ชจ๋“  ์ž„๋ฒ ๋”ฉ์ด ๋Œ€์นญ์ ์œผ๋กœ ์กด์žฌํ•ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, $u \to v_j$ ๋งค์นญ์„ ์•„์˜ˆ ์‹œ๋„ํ•˜์ง€ ์•Š๊ณ  ๋ฒ„๋ฆด ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Dynamic Equivalence ์˜ˆ์‹œ

์•„๋ž˜ ๊ทธ๋ฆผ๋„ VEQ ๋…ผ๋ฌธ์˜ ๊ทธ๋ฆผ์ธ๋ฐ, ์ผ๋ถ€๋งŒ ํ•ด์„ํ•ด ๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

figure

$\pi_M(u_2, v_3)$ ์„ ์ƒ๊ฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. (์ด equivalence Set์„ ์™„์ „ํžˆ ์•„๋Š” ๊ฒƒ์€ $u_2 \to v_3$ ์ชฝ์˜ ์„œ๋ธŒํŠธ๋ฆฌ๋ฅผ ๋ชจ๋‘ ๋Œ๊ณ  ๋‚œ ๋’ค์ž…๋‹ˆ๋‹ค) ํŠธ๋ฆฌ๋ฅผ ๊ด€์ฐฐํ•ด ๋ณด๋ฉด, $v_3$ ์™€ ๋งค์นญ๋˜๊ณ  ์‹ถ์–ดํ•ด์„œ conflict๋ฅผ ๋‚ด๋Š” ๋…ธ๋“œ $u_5$ ๊ฐ€ ๋ณด์ž…๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, $I_M(u_2, v_3) = \Set{(u_5, v_3)}$ ์ž…๋‹ˆ๋‹ค. Conflict๊ฐ€ ๋ฐœ์ƒํ•œ ์ ์ด ์žˆ์œผ๋ฏ€๋กœ, $\pi^{-}(u_2, v_3)$ ์„ ๊ณ„์‚ฐํ•  ๋•Œ $\pi(u_2, v_3)$ ์™€ $\pi(u_5, v_3)$์˜ intersection์„ ๊ตฌํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” figure 5๋ฅผ ๋ณด๊ณ  ๊ตฌํ•˜๋ฉด $\Set{v_4}$๊ณ , ์„œ๋ธŒํŠธ๋ฆฌ์—์„œ ์„ฑ๊ณตํ•ด๋ณธ ์ ์ด ์—†์œผ๋ฏ€๋กœ $\pi_M(u_2, v_3) = \pi^{-}(u_2, v_3) = \Set{v_4}$ ์ž…๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ $v_3 \equiv v_4$ ์ด๊ณ , $u_2 \to v_3$์—์„œ ์„ฑ๊ณตํ•ด ๋ณธ ์ ์ด ์—†์œผ๋ฏ€๋กœ $u_2 \to v_4$๋„ ์„ฑ๊ณตํ•˜๋Š” ์ž„๋ฒ ๋”ฉ์ด ์—†์Œ์„ ์•Œ๊ฒŒ ๋˜์–ด ํƒ์ƒ‰ํ•˜์ง€ ์•Š๊ณ  pruneํ• ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด $\pi_M(u, v)$๊ฐ€ subtree equivalence์˜ ํ•„์š”์ถฉ๋ถ„์ด๋ผ๋Š” ์ฆ๋ช…์€ proceeding์— ๋ฐœํ‘œ๋œ ๋ฒ„์ „์—์„œ๋Š” ๋น ์ ธ ์žˆ๋Š”๋ฐ, ์ดํ›„์— ์ฆ๋ช…ํ•˜๊ฒŒ ๋œ๋‹ค๋ฉด ์ฑ„์›Œ ๋„ฃ๊ฒ ์Šต๋‹ˆ๋‹ค. ์ง๊ด€์ ์œผ๋กœ๋Š”, ์ดํ›„์˜ ์„œ๋ธŒํŠธ๋ฆฌ ๋งค์นญ ์‹œ๋„์—์„œ ์ƒ๊ธฐ๋Š” ๋ชจ๋“  conflict์™€ equivalence๋ฅผ ๊ธฐ์–ตํ•ด์„œ ๋ฐ˜์˜ํ•˜๊ณ  ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์ฆ๋ช…์€ technicalํ•˜๊ฒ ์ง€๋งŒ ๊ทธ๋ ‡๊ฒŒ ์ด์ƒํ•˜์ง€๋Š” ์•Š์€๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์‹คํ—˜ (Performance Analysis)

์ด ๋…ผ๋ฌธ์˜ ์ €์ž๋“ค์€ VEQ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ธฐ์กด์˜ SOTA ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค๊ณผ ๋น„๊ตํ•˜์—ฌ ์„ฑ๋Šฅ์„ ์ธก์ •ํ•˜๋Š” ์‹คํ—˜์„ ์‹คํ–‰ํ–ˆ๊ณ , ์ ˆ๋Œ€์ ์ธ ์†Œ์š” ์‹œ๊ฐ„์„ ๋งŽ์ด ์ค„์ผ ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ํŠนํžˆ, ์žฌ๋ฏธ์žˆ๋Š” ๊ฒฐ๊ณผ ๋ช‡๊ฐ€์ง€๋งŒ ์†Œ๊ฐœํ•ฉ๋‹ˆ๋‹ค. ๋น„๊ต ๋Œ€์ƒ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์€ ๊ฐ™์€ ํฐ ํ‹€์„ ๊ณต์œ ํ•˜๋Š” CFL-Match, DAF, GQL, RI์™€ Constraint programming ๊ธฐ๋ฐ˜์˜ Glasgow (์‹œ๊ฐ„๋งŒ ๋น„๊ต) ์ž…๋‹ˆ๋‹ค.

  • Matching order๋Š” ์ฐจ์น˜ํ•˜๊ณ , ๊ฒฐ๊ตญ์€ ํ•„ํ„ฐ๋ง์„ ๋นก์„ธ๊ฒŒ ๊ฑธ๊ณ  ๋ฐฑํŠธ๋ž˜ํ‚นํ•˜๋Š”๊ฒŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์˜ ํ‹€์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ, ํ•„ํ„ฐ๋ง์„ ์—ด์‹ฌํžˆ ํ• ์ˆ˜๋ก ๋ฐฑํŠธ๋ž˜ํ‚นํ• ๊ฒŒ ์ ์€๋ฐ, ๋ฐฑํŠธ๋ž˜ํ‚น์€ ์ตœ์•…์˜ ๊ฒฝ์šฐ ์ง€์ˆ˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ์ง€๋งŒ ํ•„ํ„ฐ๋ง์€ ์–ด์จŒ๋“  ๋‹คํ•ญ์‹œ๊ฐ„์— ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ํ•„ํ„ฐ๋ง ์‹œ๊ฐ„์ด ํฌ๊ณ  ๋ฐฑํŠธ๋ž˜ํ‚น ์‹œ๊ฐ„์ด ์ž‘๋‹ค๋ฉด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์ด ๋ฐ์ดํ„ฐ์…‹์— ๋Œ€ํ•ด ์ข€๋” stableํ•ฉ๋‹ˆ๋‹ค. ์ด ์ ์—์„œ VEQ๋Š” ํ•„ํ„ฐ๋ง์„ extended DP๋กœ ๊ฐ•ํ•˜๊ฒŒ ํ•˜๊ณ , Dynamic pruning์œผ๋กœ ๋ฐฑํŠธ๋ž˜ํ‚น ์‹œ๊ฐ„์„ ๋งŽ์ด ์ค„์ด๊ธฐ ๋•Œ๋ฌธ์— ์ตœ์†Œ 50%์—์„œ ์ตœ๋Œ€ 95% ์ •๋„์˜ ์‹œ๊ฐ„์„ ํ•„ํ„ฐ๋ง์— ์“ฐ๊ณ , ๋ฐฑํŠธ๋ž˜ํ‚น์€ ์ •๋ง ์ตœ์†Œํ™”ํ•ฉ๋‹ˆ๋‹ค.
  • ์ด๊ฒƒ์€, Extended DP๋ฅผ ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์ด๊ธฐ๋„ ํ•˜์ง€๋งŒ, ํ•„ํ„ฐ๋ง ๊ฒฐ๊ณผ ์ž์ฒด์˜ ์ฐจ์ด๋ณด๋‹ค๋„ ์˜คํžˆ๋ ค ํ•„ํ„ฐ๋ง ๊ณผ์ •์—์„œ ์–ป๋Š” Cell์ด๋ผ๋Š” ์—„์ฒญ๋‚˜๊ฒŒ ๊ฐ•ํ•œ ์ •๋ณด๋ฅผ ์ดํ›„์— ์ด์šฉํ•  ์ˆ˜ ์žˆ์—ˆ๋˜ ์ ์ด ๊ฐ€์žฅ ์ค‘์š”ํ•ด ๋ณด์ž…๋‹ˆ๋‹ค. ์ฆ‰, ๋‹คํ•ญ์‹œ๊ฐ„์— ํ• ์ˆ˜์žˆ๋Š” ์ผ๋“ค์„ ์ตœ๋Œ€ํ•œ ์ฒ˜๋ฆฌํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ€๋Šฅํ–ˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ์‹ค์ œ๋กœ, Dynamic Equivalence๋ฅผ ์ˆ˜ํ–‰ํ•˜์—ฌ ๋‚ ๋ฆด ์ˆ˜ ์žˆ์—ˆ๋˜ search space๊ฐ€ ๋งŽ์€ ์ผ€์ด์Šค์—์„œ 99% ๊ฐ€๊นŒ์ด ๋‚˜์˜ค๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.

Thoughts

  • Neighbor safety์—์„œ, ์ด ๋…ผ๋ฌธ์—์„œ๋Š” 1-neighbor๋งŒ์„ ๊ณ ๋ คํ•˜์—ฌ safety๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ๋” ๋งŽ์€, ์˜ˆ๋ฅผ๋“ค์–ด 2-neighbor (๊ฑฐ๋ฆฌ๊ฐ€ 2์ธ ๋…ธ๋“œ๋“ค๊นŒ์ง€) ๊นŒ์ง€ ๊ณ ๋ คํ•˜๋ฉด ๋” ๊ฐ•ํ•œ ํ•„ํ„ฐ๋ง์ด ๊ฐ€๋Šฅํ• ํ…๋ฐ, ๊ทธ๋Ÿฌ์ง€ ์•Š์€ ์ด์œ ๋Š” ์•„๋งˆ๋„ ํ•„ํ„ฐ๋ง์— ์†Œ์š”ํ•˜๋Š” ์‹œ๊ฐ„์— ๋น„ํ•ด ํ•„ํ„ฐ๋ง์˜ ํšจ์šฉ์ด ํฌ์ง€ ์•Š๋‹ค๊ณ  ๋ณด์•˜๊ธฐ ๋•Œ๋ฌธ์ผ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด, label์˜ frequency๊ฐ€ ๋†’์„ ๋•Œ (์ฆ‰ label frequency๊ฐ€ ์ƒ๊ฐ๋ณด๋‹ค ๋” ์ค‘์š”ํ•  ๋•Œ) ๋Š” ๊ณ ๋ คํ•˜๋Š” neighbor์˜ ์ˆ˜๋ฅผ ๋” ๋Š˜๋ฆฌ๋Š” ๋ฐฉ์‹์ฒ˜๋Ÿผ ๋ญ”๊ฐ€ ๋‹ค์ด๋‚˜๋ฏนํ•˜๊ฒŒ ๊ณ„์‚ฐ๊ฐ€๋Šฅํ•œ ํŒŒ๋ผ๋ฏธํ„ฐ๋ฅผ ์žก์„์ˆ˜๋Š” ์—†์„๊นŒ์š”?
  • Equivalence๋ฅผ Hashing ๋“ฑ์„ ํ†ตํ•ด ์ž˜ ๊ด€๋ฆฌํ•˜๋ฉด ๋” ๋น ๋ฅด๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”?