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

Introduction

이번에 정리할 논문은 제가 2020년 2학기에 연구실 학부생 인턴으로 지도 받았던 서울대학교 컴퓨터이론 및 응용 연구실 (박근수 교수님 연구팀) 에서 이번 2021년 SIGMOD에 발표한 논문이자, 제 이번 창의통합설계와 밀접한 관련이 있는 논문입니다. (그래서 다른 논문에 비해 훨씬 자세히 읽었습니다. 이 논문을 똑같이 구현할 각오(?) 를 하고 있었기 때문에…)

이 알고리즘도 크게는, 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 원본 논문의 이미지인데, 말로 설명하면 조금 귀찮지만 개념 자체는 직관적입니다.

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 논문의 그림인데, 일부만 해석해 보도록 하겠습니다.

$\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 등을 통해 잘 관리하면 더 빠르게 처리할 수 있을까요?