Koutra, D., Vogelstein, J. T., & Faloutsos, C. (2013). DeltaCon : A Principled Massive-Graph Similarity Function. Proceedings of the 2013 SIAM International Conference on Data Mining, 10(3), 162โ€“170.



์ด๋ฒˆ์— ์ •๋ฆฌํ•  ๋…ผ๋ฌธ์€ DELTACON ์ด๋ผ๋Š” Graph similarity metric์„ ์ œ์‹œํ•œ, DELTACON: A Principled Massive-Graph Similarity Function์œผ๋กœ, 2013๋…„ SIAM International Conference on Data Mining์— ๋ฐœํ‘œ๋œ ๋…ผ๋ฌธ์ž…๋‹ˆ๋‹ค. (SIAM๊ณผ IEEE์—์„œ ์ง„ํ–‰ํ•˜๋Š” ๋˜‘๊ฐ™์€ ์ด๋ฆ„์˜ Conference๊ฐ€ ์žˆ์–ด์„œ, ์ด์ชฝ์„ ๋ณดํ†ต SDM์œผ๋กœ ์•ฝ์นญํ•ฉ๋‹ˆ๋‹ค). ์ด ๋…ผ๋ฌธ์—์„œ๋Š” ๊ทธ๋ž˜ํ”„ ์œ ์‚ฌ๋„๊ฐ€ ๋งŒ์กฑํ•ด์•ผ ํ•  ๊ธฐ๋ณธ์ ์ธ ๊ธฐ์ค€๋“ค์„ ์ œ์‹œํ•˜๊ณ , ๊ทธ ๊ธฐ์ค€์— ๋งž๋Š” ์‹ค์ œ ์œ ์‚ฌ๋„ ๋ฉ”ํŠธ๋ฆญ์„ ์ œ์‹œํ•˜์˜€์Šต๋‹ˆ๋‹ค.

๋‘ ๊ทธ๋ž˜ํ”„ $G_1 = (V_1, E_1), G_2 = (V_2, E_2)$ ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์šฐ๋ฆฌ๋Š” ๋‘ ๊ทธ๋ž˜ํ”„์˜ ์œ ์‚ฌ๋„ ๋ฅผ ์ธก์ •ํ•˜๋Š” ์–ด๋–ค ์ข‹์€ ๋ฉ”ํŠธ๋ฆญ์„ ๊ฐ–๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํฐ ๊ทธ๋ž˜ํ”„ $G$๊ฐ€ ์‹œ๊ฐ„์˜ ํ๋ฆ„์— ๋”ฐ๋ผ ๋ณ€ํ™”ํ•œ๋‹ค๋ฉด - ์ฆ‰, $G_1, \dots G_n$ ์— ๋Œ€ํ•ด์„œ, $d(G_i, G_{i-1})$ ์ด ์ตœ๋Œ€์ธ ์‹œ์  $i$๋ฅผ ํ™•์ธํ•˜๋ฉด anomally๋ฅผ ์•Œ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ๋…ผ๋ฌธ์—์„œ๋Š” Node correspondence๊นŒ์ง€ ์ฃผ์–ด์ง„ ์ƒํ™ฉ์—์„œ์˜ ๊ทธ๋ž˜ํ”„ ์œ ์‚ฌ๋„์— ๋Œ€ํ•ด์„œ๋งŒ ๋‹ค๋ฃน๋‹ˆ๋‹ค.

Key Ideas


๋ญ”๊ฐ€ ๋…ธ๋“œ ๊ฐ„์˜ ์—ฐ๊ฒฐ๊ด€๊ณ„๋ฅผ ์ˆ˜์น˜ํ™”ํ•ด์„œ ์•Œ๊ณ  ์žˆ๋‹ค๋ฉด, ์ด๋ฅผ ๋น„๊ตํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, Random walk with Restart ๊ฐ™์€ ๋ฐฉ๋ฒ•์„ ์ด์šฉ (์ด ๋ฐฉ๋ฒ•์— ๋Œ€ํ•œ ์„ค๋ช…์€ Advanced-algorithm ์ชฝ์œผ๋กœ ์ œ๊ฐ€ ํฌ์ŠคํŒ…ํ•œ ์ ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋งํฌ) ํ•˜์—ฌ, ๋…ธ๋“œ๊ฐ„์˜ ์—ฐ๊ฒฐ์ •๋„๋ฅผ ํ–‰๋ ฌ๋กœ ๋งŒ๋“ค์–ด ๋†จ๋‹ค๋ฉด ์ด ํ–‰๋ ฌ์ด ๊ทธ๋ž˜ํ”„์˜ ์–ด๋–ค ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋…ผ๋ฌธ์—์„œ๋Š”, RwR์€ ์•„๋‹ˆ๊ณ  ์ด๋ณด๋‹ค ์ข€๋” ์ตœ์‹ ์ด๋ฉฐ ์—ฌ๋Ÿฌ ์ข‹์€ ์„ฑ์งˆ์„ ๊ฐ–๋Š” Fast Belief Propagation์ด๋ผ๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•  ๋•Œ, ๋…ธ๋“œ ๊ฐ„์˜ ์—ฐ๊ฒฐ์„ฑ์„ ํฌํ•จํ•˜๋Š” $n \times n$ ํ–‰๋ ฌ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค. \(S = [s_{ij}] = \left(I + \epsilon^2 D - \epsilon A\right)^{-1}\) ์—ฌ๊ธฐ์„œ, $A$๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ธ์ ‘ํ–‰๋ ฌ์„, $D$๋Š” ๋…ธ๋“œ $i$์˜ degree๋ฅผ $d_{ii}$๋กœ ํ•˜๋Š” ๋Œ€๊ฐํ–‰๋ ฌ์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

Similarity measure properties

์ด ๋…ผ๋ฌธ์—์„œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ช‡๊ฐ€์ง€ ์„ฑ์งˆ๋“ค์„ Graph Similarity Measure๊ฐ€ ๊ฐ€์ ธ์•ผ ํ•  ์„ฑ์งˆ๋“ค์ด๋ผ๊ณ  ์ฃผ์žฅํ•ฉ๋‹ˆ๋‹ค. ์ƒ๋‹น์ˆ˜๊ฐ€ ์šฐ๋ฆฌ์˜ ์ง๊ด€์— ๊ธฐ๋ฐ˜ํ•˜์˜€๊ธฐ ๋•Œ๋ฌธ์— ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ์ดํ•ดํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • Identity : $sim(G, G) = 1$. ๋งค์šฐ ์ž์—ฐ์Šค๋Ÿฝ์Šต๋‹ˆ๋‹ค.
  • Symmetry : $sim(G_1, G_2) = sim(G_2, G_1)$. ์—ญ์‹œ ๋งค์šฐ ์ž์—ฐ์Šค๋Ÿฝ์Šต๋‹ˆ๋‹ค.
  • Zero Property : Complete graph $K_n$ ๊ณผ Vertex $n$๊ฐœ์— edge๋Š” ํ•˜๋‚˜๋„ ์—†๋Š” zero graph $Z_n$์„ ์ƒ๊ฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ, $d(K_n, Z_n) \to 0$ as $n \to \infty$ ๋ฅผ ์›ํ•ฉ๋‹ˆ๋‹ค.
  • Edge Importance : Edge๊ฐ€ ๋‹ฌ๋ผ์ง€๋Š” ๋ณ€ํ™”๋“ค ์ค‘, connected component์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋ฐ”๋€Œ๋ฉด ํŠนํžˆ ๋” ํฐ ์ฐจ์ด๋กœ ๊ฐ„์ฃผํ•ฉ๋‹ˆ๋‹ค. ์ฆ‰, $K_n$ ๊ณผ $K_n$์„ edge ํ•˜๋‚˜๋กœ ์ด์–ด๋†“์€ ๊ทธ๋ž˜ํ”„์—์„œ bridge๋Š” ๋‹ค๋ฅธ edge๋“ค๋ณด๋‹ค ๋” ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.
  • Weight Awareness : Weighted graph์—์„œ, weight์ด ํฐ edge์—์„œ ์ผ์–ด๋‚˜๋Š” ๋ณ€ํ™”๋Š” ๋” ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.
  • Submodularity : ๊ฐ™์€ ํฌ๊ธฐ์˜ ๊ทธ๋ž˜ํ”„์—์„œ, edge ํ•˜๋‚˜์˜ ์ค‘์š”๋„๋Š” dense graph์—์„œ๊ฐ€ sparse graph์—์„œ๋ณด๋‹ค ๋œ ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.
  • Focus Awareness : ๊ทธ๋ž˜ํ”„์—์„œ edge๋“ค์— ๋ณ€ํ™” (์ถ”๊ฐ€ ๋˜๋Š” ์ œ๊ฑฐ) ๊ฐ€ ์ด๋ฃจ์–ด์งˆ ๋•Œ, ํ•œ ์ ์„ ๋…ธ๋ฆฌ๊ณ  ํ•œ์ชฝ์— ์ง‘์ค‘๋œ ๋ณ€ํ™”๋Š” ๋žœ๋คํ•œ ๋ณ€ํ™”๋ณด๋‹ค ๋” ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.

DELTACON Algorithm

DELTACON์€ ์•ž์„œ ์ œ์‹œํ•œ ํ–‰๋ ฌ $S$๋ฅผ ์ด์šฉ, ๋‹ค์Œ๊ณผ ๊ฐ™์€ distance๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. \(d(G_1, G_2) = \sqrt{\sum_{i = 1}^{n} \sum_{j = 1}^{n} \left(\sqrt{S_1(i, j)} - \sqrt{S_2(i, j)}\right)^2}\) ํ–‰๋ ฌ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๊ฐ€ ๊ต‰์žฅํžˆ ํŠน์ดํ•˜๊ฒŒ ์ •์˜๋˜๋Š”๋ฐ, ์ด๋ฅผ Jefries-Matusita distance ๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฃจํŠธ์˜ ์ฐจ๋ฅผ ์ œ๊ณฑํ•˜๋Š” ์‹ ๊ธฐํ•œ ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘ํ•˜๋Š”๋ฐ, ์ผ๋ฐ˜์ ์ธ Euclidean distance์™€๋Š” ๋‹ฌ๋ฆฌ ์ด distance๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ ์œ„ ์„ฑ์งˆ๋“ค ์„ ์ž˜ ๋งŒ์กฑํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ถ€๋ถ„์€ ์ด ๋…ผ๋ฌธ์—์„œ ์ˆ˜ํ•™์ ์œผ๋กœ ์—„๋ฐ€ํ•˜๊ฒŒ ๋…ผ์ฆ๋˜์ง€๋Š” ์•Š์•˜๊ณ , ๋ฐ์ดํ„ฐ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด ์‹คํ—˜์ ์œผ๋กœ ๊ฒ€์ฆ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

์šฐ๋ฆฌ๋Š” ๊ทธ๋ž˜ํ”„ ์œ ์‚ฌ๋„๋ฅผ $[0, 1]$ ์— ์ง‘์–ด๋„ฃ๊ณ  ์‹ถ๊ธฐ ๋•Œ๋ฌธ์—, $sim(G_1, G_2) = \frac{1}{1 + d(G_1, G_2)}$ ๋ฅผ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

์ด sim ํ•จ์ˆ˜๋ฅผ DELTACON์ด๋ผ๊ณ  ๋ถ€๋ฆ…๋‹ˆ๋‹ค.


Anomally detection ๋“ฑ์— ์“ฐ์ธ๋‹ค๋Š” ๊ฒƒ์„ ํ†ตํ•ด ์•Œ ์ˆ˜ ์žˆ๋“ฏ์ด, ๊ทธ๋ž˜ํ”„ ์œ ์‚ฌ๋„๋Š” ๋งŽ์€ ์ˆ˜์˜ ๊ทธ๋ž˜ํ”„๋ฅผ ๋Œ€์ƒ์œผ๋กœ ํ•ด์•ผ ํ•  ์ˆ˜๋„ ์žˆ๊ธฐ ๋•Œ๋ฌธ์—, ๊ฐ€๋Šฅํ•œ ๋นจ๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค.

Deltacon ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ๊ฐ€์žฅ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š” ๋ถ€๋ถ„์€ $S$ํ–‰๋ ฌ์˜ ๊ณ„์‚ฐ์ž…๋‹ˆ๋‹ค. $S$ํ–‰๋ ฌ์€ $S = [s_{ij}] = \left(I + \epsilon^2 D - \epsilon A\right)^{-1}$ ์™€ ๊ฐ™์ด ์—ญํ–‰๋ ฌ๋กœ ์ •์˜๋˜๋Š”๋ฐ, ์ผ๋ฐ˜์ ์ธ matrix๊ฐ€ ์•„๋‹ˆ๋ผ ํŠน์ˆ˜ํ•œ graph structure๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— FaBP ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜์—ฌ $O(n^2)$ ์‹œ๊ฐ„์— ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ดํ›„์˜ Matusita distance๋Š” ๋‹น์—ฐํžˆ $O(n^2)$์— ๊ณ„์‚ฐ ๊ฐ€๋Šฅํ•˜๋ฏ€๋กœ, ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ $O(n^2)$ ์ž…๋‹ˆ๋‹ค.

์ด ๋…ผ๋ฌธ์—์„œ๋Š” DELTACON์˜ ์ข€๋” ๋น ๋ฅด๊ฒŒ ์ž‘๋™ํ•˜๋Š” approximation ๋ฒ„์ „์„ ์ œ์‹œํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. $n^2$๋ณด๋‹ค ๋น ๋ฅด๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š”, Matusita distance ๊ณ„์‚ฐ์ด ์ผ๋‹จ $O(n^2)$ ์‹œ๊ฐ„์€ ๋ฌด์กฐ๊ฑด ๊ฑธ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ํ–‰๋ ฌ ์ž์ฒด๋ฅผ ์ค„์—ฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด, affinity๋ฅผ ๊ณ„์‚ฐํ•˜๊ธฐ๋Š” ํ•˜๋Š”๋ฐ ๋…ธ๋“œ $i$์— ๋Œ€ํ•ด ๋ชจ๋“  ๋…ธ๋“œ $j$์˜ affinity๊ฐ€ ์•„๋‹Œ, ๋…ธ๋“œ๋ฅผ ์ ๋‹นํžˆ ๋ฌถ์–ด $g$๊ฐœ์˜ ๊ทธ๋ฃน์œผ๋กœ ๋งŒ๋“ค์–ด์„œ $i$์—์„œ $j$๋ฒˆ ๊ทธ๋ฃน์œผ๋กœ์˜ affinity๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ์ด๋Š” ์ฆ‰, $S$ํ–‰๋ ฌ์—์„œ ์ž„์˜๋กœ ์—ด๋“ค์„ $g$๊ฐœ์˜ group์œผ๋กœ ๋ฌถ์–ด์„œ ๋”ํ•จ์œผ๋กœ์จ $n \times g$ํ–‰๋ ฌ์„ ๋ฌถ๋Š”๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. $g$๋ฅผ ์ถฉ๋ถ„ํžˆ ์ž‘๊ฒŒ ํ•˜๊ณ , ๊ตฌํ˜„์„ ์ž˜ ํ•˜๋ฉด ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ edge ๊ฐœ์ˆ˜์— ๋Œ€ํ•ด linearํ•˜๊ฒŒ ๋Œ๊ฒŒ ํ•  ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์ด๋•Œ, ์ด๋ ‡๊ฒŒ approximateํ•œ similarity๋Š” ํ•ญ์ƒ ์‹ค์ œ similarity๋ณด๋‹ค ํฐ ๊ฐ’์„ ๊ฐ–์Šต๋‹ˆ๋‹ค. (์ฆ๋ช…์€ ๋ถ€๋ก์— ์žˆ๊ณ , ๊ทธ๋ ‡๊ฒŒ ์–ด๋ ต์ง€๋Š” ์•Š์Šต๋‹ˆ๋‹ค. ๋งํฌ)


DELTACON์€ ๋ฌด์—‡๋ณด๋‹ค Graph Similarity Measure๊ฐ€ ๊ฐ€์ ธ์•ผ ํ•  ์ข‹์€ ์„ฑ์งˆ๋“ค์„ (์ •์„ฑ์ ์œผ๋กœ๋‚˜๋งˆ) ์ œ์‹œํ•˜์˜€๊ณ , ์ด ์„ฑ์งˆ๋“ค์„ ๋งŒ์กฑํ•˜๋Š” ์‹ค์ œ similarity measure๋ฅผ ์ฐพ์•„๋ƒˆ์œผ๋ฉฐ, ์‹คํ—˜์ ์œผ๋กœ ์ด๋ฅผ ๊ฒ€์ฆํ•˜์˜€๋‹ค๋Š” ์˜์˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ํŠนํžˆ ๋‹ค๋ฅธ Similarity measure (Graph edit distance, spectral methods ๋“ฑ) ๋“ค์€ ์ด๋Ÿฌํ•œ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•œ ์ง๊ด€์ ์ธ ์„ฑ์งˆ๋“ค์ด ์ „ํ˜€ ๊ณ ๋ ค๋˜์ง€ ์•Š์•˜๋Š”๋ฐ, ์ด๋Ÿฐ ์œ ์‚ฌ๋„๋“ค์— ๋น„ํ•ด DELTACON์ด ์–ผ๋งˆ๋‚˜ ์ œ์‹œํ•œ ์กฐ๊ฑด๋“ค์„ ์ž˜ ๋งž์ถ”๋Š”์ง€๋ฅผ ์ƒ๋‹นํžˆ extensiveํ•œ ์‹คํ—˜์„ ํ†ตํ•ด ๊ฒ€์ฆํ•˜์˜€์Šต๋‹ˆ๋‹ค. ํŠนํžˆ Graph edit distance ๋“ฑ ๊ณ„์‚ฐ ์‹œ๊ฐ„์ด ๊ต‰์žฅํžˆ ์˜ค๋ž˜ ๊ฑธ๋ฆฌ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์— ๋น„ํ•ด, exact๋„ quadratic์ด๊ณ  ์ด๋ฅผ edge ๊ฐœ์ˆ˜์— ์„ ํ˜•์ด ๋˜๊ฒŒ ๋” ๊ฐœ์„ ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค์–‘ํ•œ ํ™œ์šฉ์ด ๊ฐ€๋Šฅํ•  ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.


  • Graph์˜ ๋…ธ๋“œ ๋Œ€์‹  edge์— label์ด ์ฃผ์–ด์ง„๋‹ค๋ฉด, ์ด๋ฅผ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ํ™•์žฅํ•  ์ˆ˜ ์žˆ์„๊นŒ์š”?

  • ์‹คํ—˜์  ๊ฒ€์ฆ์„ ๋„˜์–ด์„œ์„œ, ์„ฑ์งˆ๋“ค์„ ์ˆ˜์‹์œผ๋กœ ํ‘œํ˜„ํ•˜๊ณ  ๋…ผ์ฆํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์—†์„๊นŒ์š”?
    • ๋ถ€๋ก์—๋Š” Edge importance ์„ฑ์งˆ๊ณผ zero property์— ๋Œ€ํ•ด์„œ๋Š” ์ฆ๋ช…ํ•˜๊ณ  ์žˆ์œผ๋ฉฐ, ๋‚˜๋จธ์ง€ ์„ฑ์งˆ๋“ค์— ๋Œ€ํ•ด์„œ๋Š” interesting future work ๋ผ๊ณ  ๋‚จ๊ฒจ๋‘์—ˆ์Šต๋‹ˆ๋‹ค.
    • Focus Awareness์™€ ๊ฐ™์€ ์„ฑ์งˆ๋“ค์ด ๋ฌธ์ œ์ธ๋ฐ.. ์ž ๊น ์ƒ๊ฐํ•ด๋ณด๋ฉด, edge ํ•˜๋‚˜๊ฐ€ ๋ณ€ํ™”ํ•  ๋•Œ, ๊ฐ ์  $i$์— ๋Œ€ํ•ด ์ƒˆ๋กœ ์ƒ๊ธด/์ œ๊ฑฐ๋œ edge๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์žด ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ฑฐ๋ฆฌ๋ฅผ $x_i$๋ผ๊ณ  ํ•˜๋ฉด, ๋ณ€ํ™” $m$๋ฒˆ์— ๋Œ€ํ•ด ํ–‰๋ ฌ $x_{m, i}$๋ฅผ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๊ฒ ์Šต๋‹ˆ๋‹ค. Edge๊ฐ€ ํ•œ์ชฝ์„ ํƒ€๊ฒŸํŒ…ํ•œ๋‹ค๋Š” ๊ฒƒ์€, $x_{m, i}$์˜ ๊ฐ ์—ด - ์ฆ‰, $m$๋ฒˆ์˜ ๋ณ€ํ™”๊ฐ€ ์ด vertex๋กœ๋ถ€ํ„ฐ ์–ผ๋งˆ์˜ ๊ฑฐ๋ฆฌ์—์„œ ์ผ์–ด๋‚˜๋Š”์ง€๋ฅผ ๋ชจ์€ ๋ฒกํ„ฐ - ์˜ ํ‘œ์ค€ํŽธ์ฐจ ๊ฐ™์€ ํ†ต๊ณ„์ ์ธ ์„ฑ์งˆ๋“ค์„ ์ด์šฉํ•˜์—ฌ ์ธก์ •ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.
  • Edge ํ•˜๋‚˜๊ฐ€ ๋ณ€ํ™”ํ•˜๋ฉด์„œ, ๋ณ€ํ™” ์ „ ๊ทธ๋ž˜ํ”„ $G$์™€ ๋ณ€ํ™” ํ›„ ๊ทธ๋ž˜ํ”„ $Gโ€™$๊ฐ„์˜ deltacon similarity ๋˜๋Š” ๊ทธ ๊ทผ์‚ฌ๊ฐ’์„ ์ธก์ •ํ•˜๋Š” ๋” ๋น ๋ฅธ ๋ฐฉ๋ฒ•์€ ์—†์„๊นŒ์š”? ๋ฐ”๋€Œ๋Š” edge๊ฐ€ 1๊ฐœ์ธ๋ฐ $n^2$ ์ด๋‚˜ $n$ ์‹œ๊ฐ„์„ ์ง€๋ถˆํ•˜๊ธฐ๋Š” ์ข€ ์•„๊น์Šต๋‹ˆ๋‹ค.

  • Zero Property์—์„œ, $d(K_n, G_n)$ ์ด ํ•ญ์ƒ 0์ด ์•„๋‹ˆ๋ผ 0์œผ๋กœ ์ˆ˜๋ ดํ•œ๋‹ค๋Š” ๊ฒƒ์ด ์•ฝ๊ฐ„ ์˜ค๋ฌ˜ํ•ฉ๋‹ˆ๋‹ค. ์ „์ฒด์ ์œผ๋กœ ๊ทธ๋ž˜ํ”„ ์œ ์‚ฌ๋„๊ฐ€ ํฌ๊ธฐ์— ๋งŽ์€ ์˜ํ–ฅ์„ ๋ฐ›๋Š” ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

  • FaBP๊ฐ€ ์™œ $O(n^2)$ ์— ์ž‘๋™ํ•˜๋Š”์ง€๋Š” ์•„์ง ๊ณต๋ถ€ํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ์ „๋ฐ˜์ ์œผ๋กœ ํ›„๋ฐ˜๋ถ€์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ฆ๋ช…์ด ์•ฝ๊ฐ„ ์ž˜ ๊ตฌํ˜„ํ•˜๋ฉด ๋œ๋‹ค ๋Š” ์‹์œผ๋กœ ์“ฐ์—ฌ ์žˆ๊ณ , ์—„๋ฐ€ํ•˜๊ฒŒ ์ฆ๋ช…๋˜์–ด ์žˆ์ง€ ์•Š๋‹ค๋Š” ์ ์€ ์กฐ๊ธˆ ์•„์‰ฌ์› ๋Š”๋ฐ, Github Repo ์— ๊ฝค ์ฝ๊ธฐ ์‰ฌ์šด ์ฝ”๋“œ๊ฐ€ ์žˆ์–ด์„œ ๊ทธ๋Ÿญ์ €๋Ÿญ ๋‚ฉ๋“ํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. Sparse matrix์˜ ์„ฑ์งˆ์„ ์ž˜ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.