Subgraph Matching Problem
2025๋ ์ ๋ ๋ฐ์ดํฐ๋ฒ ์ด์ค ๋ฉ์ ์ปจํํ์ฌ ํ๋ถ ์กธ์ ์ฐ๊ตฌ ์ฃผ์ ๋ฅผ ๋ฐ์์ ์งํํ๊ณ ์์ต๋๋ค. ์ ์ ์ฃผ์ ๋ โContinuous Subgraph Matchingโ๊ณผ ๊ด๋ จํด ์ฝ๋๋ฅผ ์ต์ ํ ํ๊ณ ๊ฐ์ ํ๋ ๊ฒ์ผ๋ก ๊ทธ๋ํ ์ฟผ๋ฆฌ ๊ด๋ จ ๋ ผ๋ฌธ์ ์ฝ๊ณ , C++ ์ฝ๋๋ฅผ ํ๋ํ๊ณ ์์ต๋๋ค. ์กธ์ ๋ง์ง๋ง ํ๊ธฐ์ ๋ฃ๋ ์์ ์ธ๋ฐ ๋ง์ ๋ ธํ์ฐ์ ๊ฒฝํ์ ์๊ณ ์กธ์ ํ๊ธฐ๋ฅผ ๊ธฐ๋ํ๊ณ ์์ต๋๋ค ใ ใ
IntroductionPermalink
์ด๋ฒ ํฌ์คํธ์์๋ SymBi ๋ ผ๋ฌธ์์ ํธ๋ ค๊ณ ํ๋ ๋ฌธ์ ์ธ โCSM(Continuous Subgraph Matching)โ ๋ฌธ์ ์ ๊ด๋ จ๋ ์ฉ์ด๊ฐ ๊ฐ๋ ์ ์ ๋ฆฌํ๊ณ ์ ํฉ๋๋ค. ๋จผ์ ์กฐ๊ธ ์น์ํด์ง๊ธฐ ์ํด CSM ๋ฌธ์ ์ ๋ํด ๊ธฐ์ ํ๋ฉด,
์ฟผ๋ฆฌ์ ๋ฐ์ดํฐ ๋๋ค ๊ทธ๋ํ์ ํํ๋ก ์ฃผ์ด์ง๋๋ค. โSubgraph Matchingโ ๋ฌธ์ ๋ ์ฃผ์ด์ง ๋ฐ์ดํฐ ๊ทธ๋ํ ์์์ ์ฟผ๋ฆฌ ๊ทธ๋ํ๊ฐ ๋ถ๋ถ ๊ทธ๋ํ๋ก ์ผ๋ง๋ ์กด์ฌํ๋์ง ์ฐพ๋ ๋ฌธ์ ๊ฐ ๋ฉ๋๋ค.
โContinuousโ SM ๋ฌธ์ ๋ ๋ฐ์ดํฐ ๊ทธ๋ํ์ Graph Update Stream
์ฃ์ง ์ถ๊ฐ๋ก ์ธํด Subgraph Matching์ด ์ถ๊ฐ๋๋ค๋ฉด positive match, ์ฃ์ง ์ญ์ ๋ก ์ธํด Subgraph Matching์ด ์์ด์ง๋ค๋ฉด negative match๋ผ๊ณ ํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ ํฌ์คํธ์์ ๋ค๋ฃจ๋ ์ฉ์ด์ ๊ฐ๋ ์ โSymBiโ ๋ ผ๋ฌธ์ ๊ธฐ์ค์ผ๋ก ์์ฑ ๋์์์ ๋ฏธ๋ฆฌ ๋ฐํ๋๋ค!
TerminologiesPermalink
GraphPermalink
Undirected, Connected, and vertex-labeled graph๋ฅผ ๊ฐ์ ํฉ๋๋ค. ๊ทธ๋ํ
- set of vertices
- set of edges
- labeling function
is โset of labelsโ
๊ทธ๋ฆฌ๊ณ ๊ทธ๋ํ
RepresentationPermalink
๋ณ๋ ํฌ์คํธ?
Induced SubgraphPermalink
์ฃผ์ด์ง ๊ทธ๋ํ
Given
์ฝ๊ฒ ์ค๋ช
ํ๋ฉด, Subgraph๋ฅผ ๋ง๋ค๊ธฐ ์ํด ๋ฝ์ Vertex subset
Graph Matching ProblemPermalink
HomomorphismPermalink
์ฟผ๋ฆฌ ๊ทธ๋ํ
- Query Graph
- Data Graph
There exist a mapping
- For every
, - For every
,
EmbeddingPermalink
an injective homomorphism s.t.
Homomorphism ๋ณด๋ค ๋ ๊ฐํ ๋งค์นญ ์กฐ๊ฑด์ ๋ง์กฑ ํฉ๋๋ค. ์๋ณธ ๊ทธ๋ํ์ ๊ตฌ์กฐ์ ์ฑ์ง์ ์ต๋ํ ๋ณด์กดํ๋ ๊ทธ๋ํ ๋งคํ ๋ฐฉ๋ฒ ์ ๋๋ค.
์ ๊ทธ๋ฆผ์ Homomorphism์ ๋ง์กฑํ์ง๋ง, Embedding์ ๋ง์กฑํ์ง ์๋ ์์ ์
๋๋ค. ์ฟผ๋ฆฌ ๊ทธ๋ํ์์
Partial EmbeddingPermalink
When induced subgraph of
has embedding on data graph .
์ฟผ๋ฆฌ ๊ทธ๋ํ์ โinduced subgraphโ์ ๋ํด์ ์๋ฒ ๋ฉ์ด ์กด์ฌํ๋ ๊ฒฝ์ฐ
Subgraph-isomorphism/homomorphismPermalink
Subgraph-isomorphism์ ๋ ๊ฐํ ์กฐ๊ฑด์ผ๋ก ์ฟผ๋ฆฌ ๊ทธ๋ํ
๋ฐ๋ฉด์ โSubgraph-homomorphismโ์ ์ข๋ ๋์จํ ๋งคํ์ผ๋ก ์ฟผ๋ฆฌ ๊ทธ๋ํ
Subgraph-Homomorphism์ ์ข๋ ๋์จํ ๋งคํ์ด๊ธฐ ๋๋ฌธ์ Subgraph-Isomorphism๋ณด๋ค ๋ ๋น ๋ฅด์ง๋ง ๋ ์ ํํฉ๋๋ค.
์์ผ๋ก ์ ๊ฐ๋๋ ๋ด์ฉ์์ ๊ทธ๋ํ ์ฟผ๋ฆฌ ๋งค์นญ์ ์ฐพ๋๋ค๋ ๊ฒ์ โsubgraph isomorphismโ์ ๋ง์กฑํ๋ ๋งค์นญ์ ์ฐพ๊ฒ ๋ค๋ ๊ฒ์ ๋งํฉ๋๋ค!
How to find subgraph matching efficientlyPermalink
DAG of query graphPermalink
์ฟผ๋ฆฌ ๊ทธ๋ํ์์ ์์๋ก ๋ฃจํธ ๋
ธ๋๋ฅผ ์ก์ ํ, ์ด๋ฅผ ๋ฐํ DFS ํ์์ ํ์ฌ ์ฟผ๋ฆฌ DAG
Path Tree of query graphPermalink
์ด๋, ์ฟผ๋ฆฌ DAG
Path Tree๋ DAG ์ฟผ๋ฆฌ๋ฅผ ๋ค๋ฃฐ ๋, ๊ทธ๋ํ์ ์ ์ฒด ๊ตฌ์กฐ๋ฅผ ์ ์งํ๋ฉด์๋ ๊ฒ์์ ๋น ๋ฅด๊ฒ ํ๋๋ก ํ๋ ์ฟผ๋ฆฌ ๊ทธ๋ํ์ ๋ณํ ์ ๋๋ค.
Weak EmbeddingPermalink
For a rooted DAG
a โweak embedding
DAG ์ฟผ๋ฆฌ
Weak Embedding์ ๋งค์นญ ์ฌ๋ถ๋ฅผ ๋น ๋ฅด๊ฒ ํ์ธํ๊ธฐ ์ํด โ์ํ๋ ๋งค์นญโ์ ๋๋ค.
ExamplePermalink
์๋๋ ๋
ผ๋ฌธ์์ ์ ์ํ Weak Embedding์ ์์ ์
๋๋ค. ์ฌ๊ธฐ์์ โweak embedding of
์์ธํ ์ดํด๋ณด๋ฉด, ์์๋ ๋์ด์คํ ๋งคํ์ด๋ผ์ sub-DAG
๋จผ์ , ์์์ ๋งคํ์ Weak Embedding ์
๋๋ค. ์ด์ ๋ Path Tree์ ๋ํด โhomomorphismโ ๋งคํ์ด๊ธฐ ๋๋ฌธ์
๋๋ค.
Embedding and Weak EmbeddingPermalink
Every embedding of
but the converse is not true
์ฟผ๋ฆฌ ๊ทธ๋ํ์ ์๋ฒ ๋ฉ์ด ์กด์ฌํ๋ค๋ฉด, ์ฟผ๋ฆฌ DAG์ ๋ํด์๋ ํญ์ โWeak Embeddingโ์ด ์กด์ฌํ๋ค๋ ๋ช ์ ์ ๋๋ค. ํ์ง๋ง, SymBi ๋ ผ๋ฌธ์์๋ ์ด๊ฒ์ ๋์ฐ ๋ช ์ ๋ฅผ ํ์ฉํด ํ์ ๋ฒ์๋ฅผ ๊ฐ์ง์น๊ธฐ ํ๋๋ฐ ์ฌ์ฉํฉ๋๋ค.
IF there exist no weak embedding of
then there no embedding of
์ญ๋ช ์ ๋ ๊ฑฐ์ง์ด๋ผ๊ณ ํ๋๋ฐ, โWeak Embedding์ด ์กด์ฌํ๋ค๊ณ ํด์, Embedding์ด ์กด์ฌํ๋ ๊ฒ์ ์๋๋ค.โ ์ด๊ฒ๋ ์ฝ๊ฒ ์์๋ฅผ ๋ ์ฌ๋ ค ๋ณผ ์ ์์ต๋๋ค.
๋ฐ์ดํฐ ๊ทธ๋ํ์ Path Tree์ ํ์์ด ์์ ํ ๋๊ฐ์ ๋งคํ์ด ์กด์ฌํ๋ค๊ณ ํด๋ด
์๋ค. ์ฆ, Path Tree์ ๋ํด homomorphism์ด ์๋๋ผ embedding์ ๋ง์กฑํ๋ ๊ฒฝ์ฐ ์
๋๋ค.
๊ทธ๋ฐ๋ฐ, ์ฟผ๋ฆฌ DAG
๋จ, Embedding์ด ๋์ง ๋ชปํ๋ ์ด์ ๋ฅผ Path Tree์ ๋ํด embedding์ด ์กด์ฌํ๊ธฐ ๋๋ฌธ์ด๋ผ๊ณ ์๊ฐํ๋ฉด ์ ๋๊ณ , ์ฟผ๋ฆฌ DAG์ Path Tree์ ํ์์ด ์๋ก ๋ค๋ฅด๋ฉด ์ด๋ ๊ฒ Weak Embedding์ ๋ํ ์ญ์ด ์ฑ๋ฆฝํ์ง ์๋ ๊ฒฝ์ฐ๊ฐ ๋ฐ์ํ ์ ์๋ค๊ณ ๋ฐ์๋ค์ฌ์ผ ํฉ๋๋ค.
BacktrackingPermalink
์ฌ๊ท์ ์ผ๋ก ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ํ์ํ๋ ๊ธฐ๋ฒ ์ ๋๋ค. ์ด๋, ์ ๋งํ์ง ์์ ๊ฒฝ๋ก๋ ์กฐ๊ธฐ์ ํฌ๊ธฐ(Pruning)ํ์ฌ ํ์ ์ฑ๋ฅ์ ๋์ผ ์ ์์ต๋๋ค. ๊ทธ๋์ ์์ ํ์(Brute-force)๋ณด๋ค ํจ์จ์ ์ผ๋ก ์ํ๋ ์กฐ๊ฑด์ ํ์ํ ์ ์์ต๋๋ค.
- ๊ฐ๋ฅํ ํด(Partial Solution)์ ๊ตฌ์ฑํ๊ณ
- ์ ํจ์ฑ์ ๊ฒ์ฌํจ
- ์ด๋, ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์์ผ๋ฉด, ํฌ๊ธฐํ๊ณ ๋์๊ฐ = backtrack
- ์กฐ๊ฑด์ ๋ง์กฑํ๋ฉด, ๊ณ์ ์งํ
๋ฐฑํธ๋ํน์ ์ฃผ๋ก ์๋์ ๋ฌธ์ ๋ค์ ์ฌ์ฉ ํฉ๋๋ค.
- ์ ์ฝ ์ถฉ์กฑ ๋ฌธ์ (Constraint Satisfaction Problems)
- N-queen ๋ฌธ์
- ์ค๋์ฟ
- ๊ทธ๋ํ ์์น ๋ฌธ์ (Graph Coloring)
- ์กฐํฉ ๋ฐ ์์ด ๋ฌธ์
- ๋ถ๋ถ์งํฉ์ ํฉ ๋ฌธ์ (Subset Sum)
- ์ฌํ์ ๋ฌธ์ (TSP)
- ๊ทธ๋ํ ํ์
- ๋ฏธ๋ก ์ฐพ๊ธฐ(Maze Solver)
ํ๋ถ ์๊ณ ๋ฆฌ์ฆ ์์ ๊ณผ ์ธ๊ณต์ง๋ฅ ์์ ๋, ๋ง์ด ๋ฐฐ์ ๋ ๊ฐ๋ ์ ๋๋ค ใ ใ
Ullmannโs backtrackingPermalink
๋ถ๋ถ ๊ทธ๋ํ์ ๋ํ(subgraph isomorphism) ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด 1976 Ullmann์ด ์ ์ํ ๋ฐฑํธ๋ํน ๊ธฐ๋ฐ ์๊ณ ๋ฆฌ์ฆ ์ ๋๋ค.
๋ ๊ฐ์ ๊ทธ๋ํ
- ํ๋ณด ํ๋ ฌ ์์ฑ
๋ ธ๋์ ๋ ธ๋ ๊ฐ์ ๋งค์นญ ํ๋ณด๋ฅผ ์ฐพ์ ๊ธฐ๋กํฉ๋๋ค.- ๋ ธ๋ ๋ ์ด๋ธ์ด ๋ค๋ฅด๋ฉด ๋งคํ์ด ์ ํ ์ ๋๋ ๋ ธ๋ ์์ด๋, ์ฌํํ๊ฒ๋ ๊ฐ ๋ ธ๋์ ๋ ์ด๋ธ์ด ๊ฐ๋ค๋ฉด, ํ๋ณด๋ก ๋ถ๋ฅ ํฉ๋๋ค.
- ์ฌ๊ท์ ์ผ๋ก ํ์
- ๊ฐ ๋ ธ๋์ ๋ํด ๊ฐ๋ฅํ ๋งคํ์ ๋ฐฑํธ๋ํน ํ๋ฉฐ ํ์ ํฉ๋๋ค.
- Pruning
- ์ ํจํ์ง ์์ ๋งคํ์ ๋ฏธ๋ฆฌ ์ ๊ฑฐํ์ฌ ํ์ ์๋๋ฅผ ๋์ ๋๋ค.
- ๋งคํ ๊ฒ์ฆ
- ์์ฑ๋ ๋งคํ์ด ๊ทธ๋ํ ๊ตฌ์กฐ๋ฅผ ์ ์งํ๋์ง ํ์ธ ํฉ๋๋ค.
Related WorksPermalink
Symbi ๋ ผ๋ฌธ์์ ์ ์๋์๋ ๊ด๋ จ ๋ ผ๋ฌธ๋ค์ ๊ธฐ์ค์ผ๋ก ๋์ด ํ์์ต๋๋ค.
- TurboIso (2013) [1]
- CFL-Matching (2016)
- DAF (2019)
์ด์ค์์ TurboIso ๋ ผ๋ฌธ์ ํ์ฌ ์กธ์ ์ฐ๊ตฌ ์ค์ธ ์ฐ๊ตฌ์ค์์ ๊ฒ์ํ ๋ ผ๋ฌธ ์ ๋๋ค! ์ถํ์ ์ฝ๊ณ ๋ด์ฉ์ ์ ๋ฆฌํ๊ฒ ์ต๋๋ค.
๋งบ์๋งPermalink
์ง๊ธ๊น์ง โSubgraph Matchingโ์ ๋ํ ์ฉ์ด์ ๊ฐ๋ ๋ค์ ์ดํด๋ณด์์ต๋๋ค. ์ด์ ๋ ๋ณธ๊ฒฉ์ ์ผ๋ก ์กธ์ ์ฐ๊ตฌ์์ ๋ค๋ฃจ๋ โContinuous Subgraph Matchingโ ๋ฌธ์ ์ ๋ํด์ ์ดํด๋ณด๊ฒ ์ต๋๋ค.
โก๏ธ Continuous Subgraph Matching