[Reading] DeltaCon : A Principled Massive-Graph Similarity Function (Kor)

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.

Introduction

이번에 정리할 논문은 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

Concepts

뭔가 노드 간의 연결관계를 수치화해서 알고 있다면, 이를 비교할 수 있을 것 같습니다. 예를 들어, 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이라고 부릅니다.

Scalability

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보다 큰 값을 갖습니다. (증명은 부록에 있고, 그렇게 어렵지는 않습니다. 링크)

---

Conclusion

DELTACON은 무엇보다 Graph Similarity Measure가 가져야 할 좋은 성질들을 (정성적으로나마) 제시하였고, 이 성질들을 만족하는 실제 similarity measure를 찾아냈으며, 실험적으로 이를 검증하였다는 의의가 있습니다. 특히 다른 Similarity measure (Graph edit distance, spectral methods 등) 들은 이러한 그래프에 대한 직관적인 성질들이 전혀 고려되지 않았는데, 이런 유사도들에 비해 DELTACON이 얼마나 제시한 조건들을 잘 맞추는지를 상당히 extensive한 실험을 통해 검증하였습니다. 특히 Graph edit distance 등 계산 시간이 굉장히 오래 걸리는 알고리즘들에 비해, exact도 quadratic이고 이를 edge 개수에 선형이 되게 더 개선했기 때문에 다양한 활용이 가능할 것 같습니다.

---

Thoughts

• 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의 성질을 잘 사용하는 것 같습니다.