이번 글에서는 IGMC란 알고리즘에 대해 다뤄보겠다. 상세한 내용을 원하면 논문 원본을 참고하길 바라며, 본 글에서는 핵심적인 부분에 대해 요약 정리하도록 할 것이다.

Github에 관련 코드 또한 정리해서 업데이트할 예정이다.

Inductive Matrix Completion based on Graph Neural Networks 설명

1. Background

행렬 분해 알고리즘의 기본에 대해 알고 싶다면 이 글을 참조하길 바란다. Graph Neural Networks을 이용하여 Matrix Completion 알고리즘을 구축한 대표적인 예는 GC-MC가 될 것이다. 이에 대해 알고 싶다면 이 글을 참고하면 좋다. GC-MC는 Bipartite Graph에 직접적으로 GNN을 적용하여 user와 item의 잠재 벡터를 추출하였다. 이전의 대부분의 연구와 마찬가지로 GC-MC 또한 Transductive한 모델로, 학습 셋에서 사용하지 않은 unseen nodes에 대한 대응이 불가능하다는 단점을 지니고 있었다. GraphSAGE, PinSAGE 등 여러 알고리즘에서 Inductive한 방법론을 제시하기는 했지만 이들 방법론을 적용하기 위해서는 node의 feature가 풍부해야 한다.

node feature에 크게 의존하지 않으면서도 Inductive한 학습/예측 환경으로 앞서 기술한 문제점들을 상당 부분 해결한 모델이 IGMC: Inductive Graph-based Matrix Completion이다.

2. IGMC 알고리즘 설명

일반적으로 통용되는 방식으로 기호를 정의하고 시작하겠다.

IGMC의 핵심 아이디어는 user $u$ 와 item $i$ 에 관련이 있는 local subgraph를 추출하여 이를 학습에 활용한다는 점이다.

위 그림을 보면 이해가 될 것이다. 진한 초록색 5점의 예시를 보면, $u_2$ 가 $i_7$ 에게 5점을 부여한 것을 알 수 있다. 그렇다면 이 두 node에 대한 1-hop enclosing subgraph는 $u_2$ 의 1-hop neighbor인 [ $i_5, i_7, i_8$ ], 그리고 $i_7$ 의 1-hop neighbor인 [ $u_2, u_3, u_4$ ]로 구성되는 것이다. 물론 최종적으로 학습/예측을 할 때는 Target Rating인 5점은 masking될 것이다.

subgraph를 추출하는 BFS 과정은 아래 표에 나와있다.

다음으로는 node labeling 과정이 필요하다. 여기에서의 label은 y값이 아니고, 각 node의 임시 ID를 의미한다. subgraph를 추출하였으면 이 node를 구분할 id가 필요한데, IGMC의 경우 global graph를 참조하는 경우는 없고 오직 subgraph만을 이용하여 학습/예측을 수행하기 때문에 기존의 id 방식을 그대로 따를 필요가 없다. IGMC의 구조에 맞게 바꿔보자.

위와 같이 subgraph 내에서의 node id를 다시 붙여주면 (node labeling) 각각의 node들은 역할에 맞게 구분된다. 위 label을 통해 0과 1을 추출하여 target node를 구분할 수 있고, 홀수/짝수 구분을 통해 user/item을 구분할 수 있으며, $h$ 의 값을 통해 어떤 계층(h-hop)에 속하는지도 파악할 수 있다. 이러한 node label을 One-hot 인코딩하여 초기 node feature로 활용할 수 있다.

다음 단계는 GNN을 통해 학습을 수행하는 것이다. IGMC의 특징이라면 GC-MC를 비롯한 여러 알고리즘과 달리 node-level GNN이 아니라 graph-level GNN을 사용한다는 것인데, 논문에서는 이 부분에 대해 장점을 크게 어필하고 단점을 끝에 살짝 언급한 수준에 그쳤는데 상황에 따라 단점이 더 클 수도 있다는 개인적인 의견을 덧붙인다.

GNN의 기본 구조를 message passing과 pooling(or aggregation)이라고 정의할 때, message passing은 Relational Graph Convolution Operator: R-GCN 포맷을 사용하였다.

[x^{l+1} = W_0^l x_i^l + \Sigma_{r \in \mathcal{R}} \Sigma_{j \in \mathcal{N}_r(i)} \frac{1}{\vert \mathcal{N}_r (i) \vert} W_r^l x_j^l]

활성화 함수로는 tanh를 사용하게 된다. 1번째 $\Sigma$ 는 각 Rating 별로 따로 파라미터를 둔다는 것을 의미하며, 그 내부에서는 일반적인 GCN이 적용된다. 다만 이 때 이웃 집합의 크기를 나타내는 $\mathcal{N}_r^i$ 가 global graph가 아닌 local subgraph에서 계산된 것이기 때문에 효율적으로 연산이 가능하다는 점은 기억해둘 필요가 있다. 이렇게 쭉 진행해서 $L$ 번째 Layer까지 값을 얻었으면 아래와 같이 최종 hideen representation을 얻는다.

[\mathbf{h}_i = concat(x_i^1, x_i^2, …, x_i^L)]

위와 같은 방식을 적용하면, jumping network의 효과도 있을 것으로 보인다. 이렇게 user, item에 대해 각각의 hidden 벡터를 구한 뒤 이를 다시 하나의 벡터로 결합하면 (sub) graph representation을 얻을 수 있다. 이렇게 graph 표현 벡터를 얻는 것을 graph-level GNN이라고 한다.

[\mathbf{g} = concat(\mathbf{h}_u, \mathbf{h}_v)]

위와 같은 pooling 과정은 간단하지만 실제로 적용하였을 때 우수한 성과를 내는 것이 실험으로 증명되었다고 한다. MLP를 적용해서 최종적으로 rating 예측 값을 얻을 수 있다.

[\hat{r} = \mathbf{w}^T \sigma (\mathbf{W} \mathbf{g})]

활성화 함수는 ReLU를 사용하였다.

3. Model Training

Mean Squared Error를 Loss Function으로 사용하였다.

[\mathcal{L} = \frac{1}{\vert { (u, v) \vert \Omega_{u, v} = 1 } \vert} \Sigma_{(u, v): \Omega_{u, v} = 1} (R_{u, v} - \hat{R}_{u, v})^2]

$\Omega$ 부분은 관측된 edge에 대해서만 Loss를 계산하겠다는 뜻을 담고 있다.

R-GCN layer에 AAR: Adjacent Ratin Regularization이라는 기법이 적용되었다. 이 부분은 사실 GC-MC에서도 간과하고 있었던 부분으로, 평점의 정도(magnitude)를 고려하기 위해서 도입되었다. R-GCN layer를 보면 사실 평점 4점이 평점 1점에 비해 5점에 더 가깝다를 나타내는 그 어떠한 장치도 마련되어 있지 않다. 이를 위해서 아래와 같은 ARR Regulaizer가 적용되었다.

[\mathcal{L}{ARR} = \Sigma{i=1,2,…, \vert \mathcal{R} \vert -1} \Vert \mathbf{W}{r_i + 1} - \mathbf{W}{r_i} \Vert^2_F]

이 때 $\Vert \Vert_F$ 는 행렬의 frobenius norm을 의미한다. 이 부분에 대해서는 이 글의 가장 마지막 슬라이드를 참고해도 좋다. 결과적으로 이 규제항을 적용하면 $\mathbf{W}_5$ 는 $\mathbf{W}_4$ 와 비슷해지는 효과가 나타날 것이다.

최종 Loss 함수는 아래와 같다.

[\mathcal{L}{final} = \mathcal{L}{MSE} + \lambda \mathcal{L}_{ARR}]

모델 구현은 pytorch_geometric에 기반하여 이루어졌고, 저자의 코드는 이 곳에서 참고할 수 있다. 상세한 세팅은 논문을 직접 참고하길 바란다.

여러 데이터셋에 대한 실험 결과는 아래와 같다. IGMC가 대체적으로 좋은 성과를 보이는 것을 확인할 수 있다. 하나 기억해야 할 부분은 F-EAE 알고리즘을 제외하면 다른 비교 모델들은 각 데이터의 node feature를 활용한 반면, IGMC는 앞서 기술한 것처럼, node의 feature에 의존하지 않았다는 점이 흥미롭다. 즉 그러한 feature 없이도 설정에 따라 충분한 성능을 확보할 수 있다는 의미이다.

4. 인사이트 종합

IGMC의 핵심 인사이트는 아래와 같이 정리할 수 있겠다.

1) node feature와 같은 side information 없이도 충분한 성능을 확보할 수 있음
2) local graph pattern은 user-item 관계를 파악하기에 충분함
3) long-range dependency는 추천 시스템을 구상할 때 크게 중요하지 않은 경우가 많음
4) sparse한 데이터에서도 충분히 성능을 발휘할 수 있음
5) node feature에 의존하지 않기 때문에 transfer learning에도 효과적으로 활용할 수 있음
6) graph-level prediction을 통해 더욱 효과적인 학습/예측을 수행할 수 있음
7) 1-hop neighbors 까지만 추출해도 충분한 성능을 확보할 수 있음

4번에 대해서는 논문의 5.3 section에 설명이 되어있다.

위 그림과 같이 GC-MC에 비해 sparsity가 강화되는 환경에서 RMSE의 증가폭이 완만한 것을 확인할 수 있다. 이는 Transductive한 Matrix Completion 방법론은 밀집도가 높은 user-item interaction에 더욱 의존한다는 것을 의미한다.

5번의 경우 논문의 5.4 section에 설명되어 있다. IGMC는 node feature가 부재한 상황에서도 Inductive한 학습 환경을 구축할 수 있다는 특징을 가지는데, 이를 이용하여 실제로 실험을 수행해본 결과 transfer learning에도 효과적임이 입증되었다.

6번의 경우 아래 그림을 바탕으로 설명하겠다.

좌측이 IGMC의 예시인데, $\mathbf{g}$ 라는 (sub) graph representation을 생성한 뒤 한 번 더 MLP를 거쳐 최종 예측 값을 반환하기 때문에 graph-level prediction의 형태를 띠고 있다. 반면 우측의 경우 user, item 각각의 representation을 형성 한 후 내적 기반의 연산을 통해 예측 값을 반환하게 된다.

논문에서는 이렇게 각 node의 subtree embedding을 독립적으로 구하는 것이 각 tree의 상호작용과 상관성을 포착하기 어렵다는 문제점을 지닌다고 지적한다. 즉, convolution range를 늘린다 하더라도 (h-hop 에서 h를 늘린다 하더라도) target node와 별 상관 없는, 먼 거리에 있는 node들이 subgraph에 포함되어 over-smoothing 문제를 야기할 수 있다는 것이다. 이 부분은 합당한 지적이며 IGMC는 이러한 단점을 보완하여 더욱 높은 성능의 결과를 보여줌으로써 해결 방안을 제시했다고 볼 수 있다.

다만 논문에서도 언급하였듯이 IGMC의 graph-level 학습 세팅은 시간이 더욱 오래 걸린다는 단점을 지닌다. 비록 추출된 subgraph의 최대 edge 수를 특정 값 = $K$ 로 제한하는 방법을 통해 이를 어느 정도 보완할 수는 있겠지만 구조적으로 node-level prediction이 갖는 시간적 이점을 압도하기는 어려운 것이 사실이다.

이 부분에 있어서는 본인이 마주한 task에 따라 장단점을 따져야 할 것으로 보이며, 성능과 속도 사이의 적절한 완급 조절이 필요할 것으로 보인다. 만약 IGMC와 같은 graph-level prediction으로는 충분한 속도를 확보하기 어렵다면 user, item 각각의 representation을 구한 뒤 scoring을 수행하는 node-level prediction의 구조를 일부 차용하여 IGMC를 변형하는 방법 또한 실질적으로 고려해볼 수 있을 것이다.

7번의 경우 필자도 실제 여러 GNN 모델을 적용해보면서 느낀 바인데, 1-hop neighbors로도 괜찮은 성과를 보이는 경우가 많았다.

추가적으로 IGMC의 한계를 짚고 넘어가자면, IGMC는 Inductive한 방법론이기에 unseen nodes에 대해 대응이 가능하지만 다른 수 많은 GNN 모델과 마찬가지로 아예 아무 interaction이 없으면 접근에 있어 어려움이 있다.

Appendix: high-score & low-score subgraph의 다른 패턴

이번 글에서는 APPNP란 알고리즘에 대해 다뤄보겠다. 상세한 내용을 원하면 논문 원본을 참고하길 바라며, 본 글에서는 핵심적인 부분에 대해 요약 정리하도록 할 것이다.

torch_geomectric을 이용하여 APPNP를 사용하는 방법에 대해서 간단하게 Github에 올려두었으니 참고해도 좋을 것이다.

PREDICT THEN PROPAGATE: GRAPH NEURAL NETWORKS MEET PERSONALIZED PAGERANK 설명

1. Background

일반적인 GNN에서의 문제점 중 하나는 node에 대해 오직 몇 번의 propagation만 고려되고, 이렇게 커버되는 이웃의 범위를 늘리기가 쉽지 않다는 것이다. 본 논문에서는 GCN과 PageRank의 관계를 이용하여 Personalized PageRank(PPR)에 기반한 개선된 propagation scheme을 구축한다. 결과로 PPNP (Personalized Propagation of Neural Predictions)라는 간단한 모델을 제시하며, 빠르게 근사하는 버전으로 APPNP (Approximate PPNP)를 제시한다.

참고로 PageRank와 본 APPNP 논문과도 관련이 깊은 GDC 논문에 대해서 참고하고자 한다면, 이 글을 확인하길 바란다.

Original PageRank를 변형하여 정의한 Personalized PageRank의 식은 아래와 같은 재귀식으로 표현할 수 있다.

[\mathbf{\pi}{ppr}(i_x) = (1-\alpha) \hat{\tilde{\mathbf{A}}} \mathbf{\pi}{ppr}(i_x) + \alpha i_x]

이 때 Teleport 확률 $\alpha$ 는 0~1 사이로 설정된다. 참고로 위 식은 GDC 글에서 기술된 아래 식과 같은 식이다.

[\mathbf{r} = \beta \mathbf{r} + (1-\beta) a]

위 식을 풀어내면 아래 식을 얻을 수 있다.

[\mathbf{\pi}_{ppr}(i_x) = \alpha( \mathbf{I}_n - (1-\alpha) \hat{\tilde{\mathbf{A}}} )^{-1} i_x]

indicator 벡터 $i_x$ 는 limit 분포에서도 node의 지역 이웃 정보를 보존하는 역할을 수행한다. 이 벡터를 unit 행렬 $\mathbf{I}_n$ 로 대체하면 최종적으로 fully Personalized PageRank 행렬을 얻을 수 있다.

[\mathbf{\Pi}_{ppr} = \alpha(\mathbf{I}_n - (1-\alpha)\hat{\tilde{\mathbf{A}}})^{-1}]

2. PPNP 및 APPNP 도출

최종 예측값을 도출하기 위해서는 각 node의 feature에 기반하여 예측 값을 생성한뒤 이를 앞서 기술한 fully Personalized PageRank scheme을 통해 전파를 시킨다. 모델 식은 아래와 같다.

[\mathbf{Z}_{PPNP} = activation( \alpha(\mathbf{I}_n - (1-\alpha) \hat{\tilde{\mathbf{A}}})^{-1} \mathbf{H} )]

[\mathbf{H}{i, :} = Net(\mathbf{X}{i, :})]

이 때, $\mathbf{H}$ 는 Neural Network를 통과한 예측값으로 형상은 (node의 수, class의 수)이다. 물론 softmax를 통해 여러 class에 대한 예측을 수행하는 것이 아니라면 class의 수는 1이 될 것이다.

그런데 위 식을 직접적으로 계산하면 계산 비효율이 발생한다. 이를 해결하기 위해 위해 위 식을 fully PPR 행렬과 Prediction 행렬의 조합으로 보기 보다는, 각 class가 하나의 topic을 구성하는 topic-sensitive PageRank의 변형으로 바라볼 것이다. 이 관점에서 $\mathbf{H}$ 의 모든 칼럼은 teleport set의 역할을 수행하여 nodes에 대한 정규화되지 않은 분포를 정의하게 된다.

PPNP 식을 Power Iteration을 통해 근사하면 APPNP 식을 얻을 수 있다.

[\mathbf{Z}^0 = \mathbf{H} = Net(\mathbf{X})]

[\mathbf{Z}^{k+1} = (1-\alpha) \hat{\tilde{\mathbf{A}}} \mathbf{Z}^k + \alpha \mathbf{H}]

위 재귀식을 일정 수준 반복하면 수렴된 값을 얻을 수 있을 것이고, 그 값이 APPNP의 최종 예측값이 된다. 위 재귀식의 수렴성의 증명에 관해서는 본 논문의 Appendix B를 참조하면 된다.

3. APPNP의 의미

지금까지 살펴본 내용에 기반하여 정리한 APPNP의 의미와 특징은 아래와 같다.

• Propgation 부분과 예측값을 생성하는 부분이 분리가 되어있다. 따라서 GNN의 Layer의 수를 늘린다 하더라도 Over-smoothing을 포함한 여러 문제가 나타날 가능성이 낮아진다. 또한 예측값을 생성하는 Neural Network의 구조의 자유도가 높아져 여러 다른 선택지를 고려할 수 있다.
• 모델은 반드시 end-to-end 구조로 학습되어야 한다. 역전파 과정 속에서 Gradient는 Propagation Scheme을 통과하게 되고, 이를 통해 암시적으로 여러 이웃 통합 과정을 고려하게 되는 것이다. 이를 통해 모델의 정확도를 상당 수준 향상시킬 수 있다.
• Propagation에 있어 추가적인 파라미터를 활용하지 않는다.
• Teleport 확률 $\alpha$ 를 통해 이웃 node 끼리 영향을 주는 정도와 범위를 조절하게 된다.

4. 실험 결과와 생각할 부분

본 논문의 실험 결과에는 꽤 흥미로운 부분이 많다. 간단하게만 정리하겠다.

실험에서는 4가지의 text-classification 데이터셋이 사용되었다. (CITESEER, CORA-ML, PUBMED, Microsoft Academic) PPNP 및 APPNP에서 사용되는 Neural Network는 GCN의 구조와 거의 유사하게 설계되었다. (2개의 Layer와 64 hidden size) 첫 번째 Layer에서 $\lambda=0.005$ 의 L2 규제를 적용하였고, Dropout Rate은 0.5를 적용하였다. APPNP의 경우 $\alpha=0.1$, 그리고 Power Iteration의 횟수는 $K=10$ 으로 설정하였다. 자세한 사항은 논문을 참조하길 바란다.

모든 데이터셋에서 PPNP와 APPNP는 대조 모델들을 압도하는 모습을 보였다. 다만 추가적인 행렬 계산의 존재 때문에 속도는 조금 느려졌다는 점은 고려할 필요가 있다. Sparse Label 환경에서 PPNP와 APPNP의 개선 효과는 더욱 돋보였다.

추가적인 실햄에서 APPNP의 경우 아래와 같이 Power Iteration이 늘어날 수록 일반적으로 결과는 향상되는 모습을 보였다.

Teleport 확률의 경우 대체적으로 0.05 ~ 0.2 사이에서 좋은 모습을 보였고, 이 값이 증가할수록 수렴 속도는 빨라졌다.

또 하나 재미있는 사실은, 아래 그림에서 확인할 수 있듯이 Training 당시에 Propagation을 생략하고 Inference 과정에서만 Propagation을 진행해도 크게 성능이 떨어지지 않았다는 것이다. 적용되는 데이터에 따라 차이가 있겠지만 이를 통해 APPNP가 Pre-trained된 모델과도 꽤 잘 결합할 수 있을 것이라는 가능성을 엿볼 수 있다.

논문에서는 또한 Training 과정에서만 Propagation을 진행했을 때 Propagation을 아예 수행하지 않았을 때에 비해 성능 향상이 크게 이루어졌기 때문에, feature는 존재하나 이웃 정보가 없는 Inductive Learning 상황에서 유용하게 사용할 수 있을 것이라고 언급하고 있는데 이 부분에 대해서는 그 이유가 정확히 파악되지 않는다는 점을 메모로 남긴다.

마무리하자면, APPNP는 기존의 이웃 통합 (Aggregation) 과정에 대해 또 하나의 유용한 선택지를 제공해주었다고 볼 수 있다. 또한 다른 GNN과 결합하여서 사용할 수 있기 때문에 설계 상의 이점이 있고, Power Iteration을 많이 하더라도 파라미터가 증가하지 않고 Gradient가 소실되거나 Over-smoothing 문제가 발생할 가능성이 낮기 때문에 실제 적용하는 데 있어서도 고려해야 할 조건이 적다는 장점을 지닌다.

이 글에서는 2019년 ICCV에 발표된 HowTo100M - Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips 논문을 살펴보고자 한다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.

HowTo100M - Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips

논문 링크: HowTo100M - Learning a Text-Video Embedding by Watching Hundred Million Narrated Video Clips

데이터셋, 코드 및 모델: Project webpage

초록(Abstract)

Text-video 임베딩을 학습하는 것은 대개 video clip과 수동으로 만든 caption을 필요로 한다. 그러나 이러한 데이터셋은 만드는 것이 매우 비싸며 오래 걸리고 따라서 큰 규모의 데이터셋을 얻기 힘들다. 본 연구에서, 이러한 임베딩을 video에서 학습하는 대신 쉽게 얻을 수 있는 자동생성된 narration을 annotation으로 사용한다. 이 논문이 기여한 바는,

1. HowTo100M 데이터셋 제안: 23k개의 다른 visual task를 묘사하는 절차적 web video에서 얻은 136M개의 video clip을 포함
2. 위 데이터로 학습한 Text-video 임베딩이 text-to-video retrieval과 action localization에서 SOTA로 이끔을 보임
3. 이 임베딩이 Youtube video나 movie 등 다른 domain에서 잘 transfer되는 것을 보임

1. 서론(Introduction)

실세계를 이해하고 상호작용하는 것은 시각적(영상) 정보와 언어(텍스트) 정보를 이해하고 상호작용하는 것과 매우 유사성이 높다. 그러나 text-to-video retrieval, video captioning, VQA 등의 task는 여전히 AI 시스템에게 있어 상당히 어려운 과제이다.

언어를 묘사하는 visual concept을 다루는 일반적인 방법은 text와 video를 공통 임베딩 공간으로 mapping하여 관련된 text와 video clip들이 비슷한 곳에 모여 있게 하는 것이다. 그러나 이러한 방법은 매우x2 큰 데이터셋을 필요로 하지만, 현존하는 데이터셋(MSR-VTT, DiDeMo, EPIC-KITCHENS) 등은 수동 생성한 annotation이 수천~수만 정도의 규모밖에 되지 않으며 그 품질 또한 낮은 경우도 있다.

본 연구에서는 video와 language의 결합표현을 학습할 수 있는 video clip과 text caption 쌍을 얻는 방법을 탐색하였다. YouTube에서 narrated instructional video는 규모가 크고 대량의 visual/language 데이터를 얻을 수 있다. Instructional video는 대개 narration을 포함하며 명시적으로 영상의 내용을 설명하기에 학습용으로 적합하다.
따라서 YouTube에서 23k 종류 이상의 서로 다른 task를 수행하는 것을 묘사하는 1.22M개의 narrated instructional video를 수집하였다. 각 clip은 자동 생성된 narration 형식으로 text annotation와 연결되어 있다.

기여한 바가 적혀 있는데, 이는 초록의 내용과 같다.

2. 관련 연구(Related Work)

Visual/textual cue의 이해에 기반한 여러 CV task가 제안되어 왔다.

Vision, language and speech

Visual/Textual cue가 서로 비슷한 경우에만 공통 공간 내에서 인접하게 하는 방식이 일반적이다. 이들은 대부분 잘 annotated된 데이터셋을 필요로 하기에 상당히 비용이 비싸다.

본 논문에서는 수동으로 annotation을 일절 하지 않고 자동 생성된 narration만을 사용한다. Spoken text를 사용하는 모델이 있었지만 음성 녹음이 안 되어 있거나 그 규모가 매우 작은 편이었다.

Learning from instructional videos

복잡한 과제를 해결하는 학습 과정으로써 최근 주목받고 있다. Visual-linguistic reference resolution, action segmentation 등의 task에서 여러 모델이 제안되었으나 역시 적은 수의 미리 지정된 label에서 추출한 trasncription만이 존재했다.

이후 WikiHow, COIN, CrossTask 등의 데이터셋이 만들어졌고 이들은 대개 YouTube에서 대량의 영상 정보를 획득하였다. HowTo100M도 비슷하게 YouTube에서 영상을 얻었으나 그 양이 전례없이 매우 방대하다.

Large scale data for model pretraining

Noisy할 수도 있는 web data로부터 얻은 대규모 데이터셋은 language 및 vision 모델에서 유망한 부분이다. BERT, GPT-2 등은 대규모 데이터를 사용하여 많은 task에서 SOTA를 달성하였다. GPT-2와 WebText는 Reddit에서 얻은 40GB의 text를 사용하여 좋은 결과를 얻었다.

이에 영감을 받아 video와 language의 공통 임베딩을 학습하고자 하였다. YouTube에서 얻은 1M 이상의 영상을 사용하여, 미세조정 없이도 instructional video에서 이전 결과를 넘을 뿐 아니라 non-instructinoal video에 대해서도 잘 작동한다.

3. The HowTo100M dataset

요리, 수공예, 개인 생활/관리, 원예 등의 활동에 대한 내용을 포함하는 1.22M개의 영상을 포함한다. 각 영상은 (올린 사람이 만들었을) 자막 혹은 ASR로 자동 생성된 narration을 가진다.

3.1 Data collection

Visual tasks

• Instructional video는 어떻게 특정 활동을 수행하는지를 묘사하기 때문에 어떤 활동이 있는지를 먼저 WikiHow(“어떻게 무엇을 하는가”라는 12만 개의 article 포함)에서 가져왔다.
• 많은 영상들 중 추상적인 것(“선물 선택하기”)보다는 “시각적인” 활동(“땅콩버터 만들기”)에 초점을 맞추었다. Task는 12종류로 한정하였고 관계/경제/사업 등 추상적인 task는 제외하였다.
• “물리적인” 활동이 포함되는 것(make, build, change)을 남기고 그렇지 않은 것(be, accept, feel)은 반자동으로 제거하였다.
• 최종적으로 23,611개의 visual task가 생성되었다.

Instructional videos

How to <task name> 형태의 제목을 가지며 영어 자막(사람이 올렸거나 혹은 YouTube API인 ASR로 얻은 것)을 가지는 영상을 찾았다. 이후 다음 과정을 통해 품질과 일관성을 높였다.

• 검색 결과의 상위 200까지만 사용하고 나머지는 관련성이 별로 없을 가정하에 제외함
• 조회수 100 미만의 영상은 제외
• 100 단어 이하의 영상은 배울 것이 별로 없으므로 제외
• 2,000초 이하의 영상만 사용
• 중복 영상(동일 ID) 제거

3.2 Paired video clips and captions

자막은 text의 뭉치들로 이루어져 있으며 때때로 완전한 문장의 형태가 아닌 경우도 있다. 각 줄은 영상의 특정 구간과 연관된다(특히 그 자막이 읽히는 부분). 각 자막을 caption으로 사용하여 video clip의 연관된 구간과 쌍을 만든다(그림 2).

MSR-VTT와 같은 clip-caption 쌍으로 구성된 다른 데이터셋과 달리 HowTo100M은 자동으로 만든 narration을 사용한다. 그래서 (아마도) 약하게 짝을 이룬(weakly paired) 것으로 생각된다. 영상에서는 구독자와 소통하는 등 주제와 상관 없는 내용이 있을 수도 있고 문장도 완전하지 않거나 문법적으로 틀릴 수도 있다. 임의로 400개의 clip-caption 쌍을 선택해서 확인한 결과 자막에 포함된 물체나 행동 등이 적어도 한 번 나올 확률은 51%였다.

Statistics

12개의 분류로 나누어져 있으며 예시는 그림 2에서 볼 수 있다. 자세한 내용은 부록 A에 있다.
각 데이터셋의 clip-caption의 개수는 표 1에서 볼 수 있다.

HowTo100M은,

• 다른 데이터셋에 비해 훨씬 크다.
• 자동 생성된 annotation을 사용하여 자막의 품질이 깨끗하지 않다.
• 평균적으로 하나의 영상은 110개의 clip-caption 쌍을 만들며 clip당 4초, 4단어 정도이다.
• 100개를 임의로 확인한 결과 71%는 instructional한 영상, 12%는 vlog, 7%는 리뷰나 광고였다.
  • vlog나 리뷰, 광고는 시각적인 내용과 narration 사이의 관련성이 있을 수 있다.
• non-instructional video를 특별히 제거하지는 않았는데, 공통 임베딩을 학습하는 데 도움을 줄 수 있어서다.

4. Text-video joint embedding model

$n$개의 video clip과 연관된 caption $\lbrace (V_i, C_i) \rbrace^n_{i=1}$이 주어진다.

[\mathbf{v} \in \mathbb{R}^{d_v}, \mathbf{c} \in \mathbb{R}^{d_c}]

목적은 video와 caption feature를 $d$차원의 공통 공간으로 mapping하는 함수를 만드는 것이다.

[f : \mathbb{R}^{d_v} \rightarrow \mathbb{R}^{d}, \quad g : \mathbb{R}^{d_c} \rightarrow \mathbb{R}^{d}]

cosine 유사도는 caption $C$가 video clip $V$를 묘사하면 큰 값을 갖는다.

비선형 embedding 함수를 사용한다. $W$는 학습가능한 parameter이고 $\circ$는 내적을 의미한다.

[W_1^v \in \mathbb{R}^{d \times d_v}, W_1^c \in \mathbb{R}^{d \times d_c}, W_2^v, W_2^c \in \mathbb{R}^{d \times d}, b \in \mathbb{R}^d]

실험에서는 $d$는 모두 4096을 사용하였고 총 parameter 개수는 67M개이다.

위 식의 오른쪽 부분은 선형 FC layer로 거기에 gating function을 더해 출력 범위는 $0\sim1$이 된다. 결과적으로 embedding function은 입력 벡터간 비선형 곱연산 상호작용을 모델링한다.

Loss

max-margin ranking loss를 사용한다. 각 반복 동안 mini-batch $\mathcal{B}$의 caption-clip 쌍 $(V_i, C_i)_{i \in \mathcal{B}}$에 대해서 손실함수는

이다.

[\mathcal{B}=\lbracei_1, …, i_b \rbrace \subset \lbrace1, …, n \rbrace]

• $s_{i,j}$는 video clip과 caption 간 유사도 점수이다.
• $\mathcal{N}_i$는 caption-clip $i$에 대한 negative pair이다.
• $\delta$는 margin이다. 실험에서는 $\delta=0.1$이다.

Sampling strategy

Negative pair $ \lbrace(V_i, C_i) : i \ne j \rbrace$ 의 절반은 같은 원본 YouTube 영상에서 만들어졌고, 나머지 절반은 서로 다른 영상에서 가져온 것이다. 본 논문에서 intra-negative sampling을 적용하여 학습된 embedding이 주제와 관련 없는 배경보다는 상관이 있는 부분에 중점을 두도록 하였다. 부록 C에서 positive에 대한 설명을 볼 수 있다.
또한 학습 데이터 자체가 일부 noisy하기 때문에 더 이상의 sampling 방식은 성능 개선으로 이어지지 않았다.

Clip and caption representation

clip feature $\mathbf{v}$는 temporally max-pooled pre-extracted CNN feature로 구성된다. caption feature $\mathbf{c}$는 미리 계산된 단어 임베딩 위에 있는 얕은 1D-CNN의 출력값이다. 자세한 내용은 5.1절을 참조한다.

5. 실험(Experiments)

어떻게 강력한 video-text 표현을 학습할 수 있는지 설명한다. CrossTask, YouCook2, MSR-VTT, LSMDC 등에서 실험한 결과를 보고한다.

실험 결과는,

• CrossTask, YouCook2 등 instructional 영상 데이터셋에서는 HowTo100M에서 학습된 off-the-shelf 임베딩이 매우 작고 수동으로 만든 데이터셋에 비해 훨씬 좋다.
• 일반적인 YouTube 영상을 모아놓은 MSR-VTT 같은 데이터셋에서, HowTo100M 임베딩은 MSR-VTT에서 학습된 모델과 비등한 성능을 보여준다.
• MSR-VTT의 일부만 갖고 미세조정한 HowTo100M 모델이 SOTA를 능가한다.
• LSMDC에서 미세조정한 임베딩은 domain의 큰 차이에도 불구하고 video, script에 대한 일반화 성능이 뛰어나다.
• HowTo100M의 규모의 중요성을 증명한다.

5.1. Implementation details

Video features

사전학습한 2D/3D CNN에서 frame/video 수준 feature를 추출한다.

• 2D는 1초당 1 frame 비율로 ImageNet으로 사전학습한 Resnet-152를 사용한다.
• 3D는 1초당 1.5 feature 비율로 Kinetics로 사전학습한 ResNeXt-101 16frames 모델을 사용한다.

Temporal max-pooling으로 더 긴 video clip에 대한 feature를 aggregate하고 2D와 3D feature를 이어 붙여서 각 clip당 4096차원의 벡터를 최종 생성한다.

Text pre-processing

• 일반적인 영어 stop-word를 제거한다.
• GoogleNews의 사전학습된 word2vec을 사용한다.

Training time

• feature 추출 이후 전체 데이터셋에 대해 임베딩 모델을 학습하는 것은 상대적으로 시간이 적게 걸리며 하나의 Tesla P100 GPU에서 3일이 걸리지 않았다.

5.2. Datasets and evaluation setups

Action step localization

CrossTask는 18개의 task, 수동 생성한 action segment annotation이 있는 2.7k개의 instructional video를 포함한다. 또한 각 task당 짧은 자연어 설명으로 된 action step 순서를 제공한다. HowTo100M에서 학습한 모델을 CrossTask의 video의 모든 frame과 action label의 유사도를 계산하여 step localization을 수행한다.
Cross-task weakly supervised learning from instructional videos에서와 같은 평가 방식을 사용한다.

Text-based video retrieval

자연어 query를 사용하여 video clip retrieval task에서도 실험하였다. Textual description이 주어지면, 수많은 video 중에서 이를 표현하는 video clip을 찾는 문제이다. R@1, R@5, R@10 과 median rank(MR)로 평가기준을 사용하였다.

• YouCook2: YouTube에서 모은 요리 영상 데이터셋으로 89개의 recipe, 14k개의 clip을 포함하며 모두 수동 생성한 annotation을 포함한다. text set clip이 주어지지 않으므로 3.5k개를 validation set으로 사용한다. HowTo100M에 있는 일부 annotation은 제거하였다.
• MSR-VTT: 음악, 영화, 스포츠 등 20가지 분류를 묘사하는 257개의 video query에서 모든 일반 영상들로 200k개의 clip 및 수동 생성된 annotation을 포함한다.
• LSMDC: 101k개의 영화 clip-caption으로 이루어진 데이터셋으로 자막 또는 audio description이 연결되어 있다. 1000개의 쌍을 test set으로 사용했다.

5.3. Study of negative pair sampling strategy

임베딩을 학습할 시 negative caption-video 쌍을 샘플링하는 전략을 실험해 보았다.

같은 영상에서 negative를 찾는 intra-negative 방식이 좋다는 것을 알 수 있다. 이는 MSR-VTT이나 LSMDC보다 더 fine-grained한 데이터셋인 YouCook2와 CrossTask에서 더 두드러진다.

5.4. Scale matters

실제로 HowTo100M과 같은 대규모 데이터셋이 필요한지를 알아본다. 그래서 데이터셋 중 일부분만 사용하여 사전학습을 시킨 다음 다른 데이터셋에 대해 실험한 결과는 다음과 같다.

학습에 사용한 영상의 수가 많을수록 성능이 좋기 때문에, 대규모 데이터셋의 필요성이 입증되었다. 그리고 수렴하는 것도 관찰되지 않았기 때문에 더 많은 데이터를 모아 성능을 더욱 향상시킬 가능성도 있다.

5.5. Comparison with state-of-the-art

CrossTask

현재 SOTA인 약한 지도학습 방식의 모델과 비교하여 HowTo100M에서 학습한 off-the-shelf 임베딩을 비교한다. 기존 모델은 step localization에 최적화되었던 것임에도 본 논문의 모델이 한 task를 제외하고 모든 task에서 성능이 더 좋다.

따라서 대용량의 narrated video로 학습하는 방식이 annotation이 있더라도 소규모의 데이터셋으로 학습하는 것보다 더 낫다고 결론내릴 수 있다.

YouCook2

이후 실험에서는

1. HowTo100M로만 학습한 모델
2. MSR-VTT로만 학습한 모델
3. HowTo100M에서 사전학습하고 MSR-VTT에서 미세조정한 모델

위 3가지를 실험에 사용하였다.

공식 benchmark가 없어서 HGLMN FV CCA embedding 모델을 사용하였다.
결과는 YouCook2에서 직접 학습한 모델보다 더 좋으며 R@10에서 13.7%의 향상이 있기도 했다.

결론은 CrossTask와 비슷하게 HowTo100M 모델이 specific 모델보다 더 성능이 좋다.

MSR-VTT

• instructional 영상 데이터셋과는 달리 MSR-VTT에서 직접 학습한 것이 HowTo100M에서 학습한 모델보다 더 좋다. 이는 일반적인 Youtube 영상이 instructional / VLOG 형식의 영상과는 상당히 다르기 때문으로 추측된다.
• 사전학습한 데이터의 양에 따른 성능 변화도 측정한 결과는 아래와 같다.
  • SOTA 결과는 MST-VTT의 단 20%만 사용한 것과 비등한 수준이다. 이는 훨씬 더 적은 annotation을 사용해도 괜찮다는 뜻이기도 하다.

LSMDC

HowTo100M과는 상당히 다른 데이터셋이라 어려운 부분이다. 그렇지만 (논문에 실을 정도니) HowTo100M에서 사전학습 후 LSMDC에서 미세조정하는 모델은 역시 LSMDC에서 직접 학습하는 것보다 더 좋은 결과를 가져다준다.

5.6. Cross-dataset fine-tuning evaluation

HowTo100M에서 사전학습하는 것과 다른 데이터셋에서 사전학습하는 경우와 비교했다.

모든 경우 중 HowTo100M에서 사전학습 후 목표 데이터셋에서 미세조정하는 것이 가장 좋다.

5.7. Qualitative results

Video Retrieval의 일부 결과 예시를 가져왔다.

설명에 부합하는 영상을 잘 찾았음을 확인할 수 있다. 데모는 공식 홈페이지에서 볼 수 있다.

6. 결론(Conclusion)

1.2M개 이상의 narrated video에서 얻은 130M개 이상의 clip을 포함하는 HowTo100M 데이터셋을 제시하였다. 데이터 수집 과정은 자동화된 ASR을 사용하여 빠르고 규모를 키우기 쉬우며 수동으로 만들 필요가 없다. 이를 통해 학습한 모델은 다양한 video 관련 task에서 좋은 결과를 얻었으며 데이터, 모델 및 코드를 공개하였다.

참고문헌(References)

논문 참조!

이 글에서는 2020년 EMNLP에 게재된 HERO: Hierarchical Encoder for Video+Language Omni-representation Pre-training 논문을 살펴보고자 한다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.

HERO: Hierarchical Encoder for Video+Language Omni-representation Pre-training

논문 링크: HERO: Hierarchical Encoder for Video+Language Omni-representation Pre-training

초록(Abstract)

대규모 Video + Language omni-representation(전체표현) 학습을 위한 새로운 framework, HERO를 제시한다. HERO는 계층적 구조에서 multimodal 입력을 인코딩한다. Video frame의 local 문맥은 multimodal fusion에 의해 Cross-modal Transformer로 잡아내고, global video 문맥은 Temporal Transformer에 의해 추출된다. Masked Language Modeling(MLM)과 Masked Frame Modeling(MFM)에 더해 새로운 사전학습 task를 제시한다.

1. Video-Subtitle Matching(VSM): 모델이 global/local temporal alignment를 예측함.
2. Frame Order Modeling(FOM): 모델이 순서를 섞인 video frame의 올바른 순서를 예측함.

HERO는 HowTo100M과 대규모 TV 데이터셋으로 학습하여 multi-character 상호작용과 복잡한 사회적 dynamics에 대한 깊은 이해를 얻을 수 있게 한다. 종합적인 실험은 HERO가 Video Retreival, VQA, Video Captioning 등의 task에서 새로운 SOTA를 달성하였음을 보인다. 또한 How2QA와 How2R이라는 Video QA and Retrieval benchmark를 제안한다.

1. 서론(Introduction)

시각+언어 multimodal 연구에서 BERT, ViLBERT, LXMERT, UNITER, VL-BERT, Unicoder-VL 등 대규모 사전학습 방식 모델이 여럿 발표되었다. 그러나 이러한 모델은 정적인 이미지에 맞춰져 있을 뿐 동적인 영상에는 적합하지 않다. VideoBERT가 영상-텍스트 쌍에 대한 결합표현을 학습하는 첫 시도이기는 했으나 이산적인 token만 사용되었으며 전체 frame feature가 사용되지 않았다. 이후 CBT, UniViML 등이 이를 해결하기 위한 시도를 하였다.

여러 시도가 있었으나 한계가 있었는데,

1. BERT 기반으로 구성되었다. 이는 텍스트와 영상 정보를 단순히 이어붙인 형태로 사용하여 두 modality가 같은 시간에 있었다는 정보를 사용하지 않는다.
2. 사전학습 task는 이미지+텍스트 task에서 가져온 것으로 영상의 특성을 활용하지 못한다.
3. 영상 데이터셋은 요리나 일부 형식의 영상만 존재하여 한계가 있다.

이를 해결하기 위해 HERO: Hierarchical Encoder for Video+Language Omni-representation Pre-training를 제안한다.

그림 1에서와 같이, video clip frame과 대응되는 자막 문장을 입력으로 받는다. BERT의 encoder와 같은 것이 아닌, HERO는 multimodal 입력을 구조적인 형태로 받는데,

1. Cross-modal Transformer는 자막 문장과 해당하는 local video frame을 결합하고,
2. 그 다음에 Temporal Transformer가 각 frame마다 주변의 frame을 전역 문맥으로 사용하여 연속적으로 contextualized embedding을 얻는다.

제안하는 계층적 모델은 frame 수준에서 먼저 visual/textual 지역 문맥을 얻어 전역 영상수준 시간적 문맥으로 변환한다.
실험은 이러한 구조가 BERT와 같은 구조의 모델보다 성능이 좋음을 보여준다.

사전학습 task는 다음 4가지이다.

1. Masked Language Modeling(MLM)
2. Masked Frame Modeling(MFM)
3. Video-Subtitle Matching(VSM)
4. Frame Order Modeling(FOM)

VSM과 FOM은 연속적 영상입력 전체에서 modality 간 시간적 일치 정보를 활용하는 것이 핵심이다.

YouCook2나 MSR-VTT와 같은 교육용(instructional) 영상만을 쓰는 한계를 벗어나기 위해 데이터셋은 HowTo100M과 대규모 TV 데이터셋을 사용하였다. 또한 요리에만 국한되거나(YouCook2) 매우 간단한(MSR-VTT) 데이터셋의 문제를 해결하기 위해서 새로운 task인 How2R과 How2QA를 제안한다.

그래서 본 논문의 기여한 바는,

1. 시각+언어 표현 학습을 위한 Transformer 기반 계층적 모델 HERO를 제안한다.
2. Modality 간 alignemnts를 더 잘 학습할 수 있도록 하는 사전학습 task VSM과 FOM을 제시한다.
3. 단순한 데이터셋을 넘어 HowTo100M과 대규모 TV 데이터셋을 사용하여 모델이 더욱 풍부한 표현을 학습할 수 있게 하였다.
4. HowTo100M, video-moment retrieval/QA에서 데이터셋을 모아 새로운 benchmark로 How2R과 How2QA를 제안한다.

2. 관련 연구(Related Work)

• BERT이후 BERT-like한 많은 모델이 발표되었다. 이후 모델 압축이나 생성 task로 발전이 있었다.
• 텍스트만 다루는 것을 넘어 시각적 정보까지 사용하는 모델이 등장하였다(ViLBERT, LXMERT, VL-BERT, Unicoder-VL 등).
• 대개 텍스트에 이미지를 사용하는 것이 많았는데, 이후 영상을 다루는 모델(VideoBERT, CBT, MIL-NCE, Act-BERT, UniViLM)이 제안되었다.

본 논문에서는 시각+언어 전체표현(omni-representation)을 4가지 차원에서 학습하는 모델을 개발하는 것을 목표로 하였다.

1. 더 나은 모델구조
2. 더 나은 사전학습 task 설계
3. 학습 말뭉치의 다양화
4. 후속 평가를 위한 새로운 고품질의 benchmark

3. 계층적 시각+언어 인코더(Hierarchical Video+Language Encoder)

3.1 Model Architecture

그림 1에서 전체 구조를 볼 수 있다.

• 입력은 video clip과 자막(일련의 token으로 된 문장)이다.
• 이들 입력은 Video Embedder과 Text Embedder를 통과하여 초기 표현을 뽑는다.
• HERO는 계층적 과정으로 영상표현을 추출하는데,
  • 각 video frame의 local textual context는 Cross-modal Transformer에 의해 만들어진다. 자막 문장과 연관된 video frame의 contextualized multi-modal 임베딩을 계산하여 얻는다.
  • 전체 영상의 frame 임베딩은 이후 Temporal Transformer에 집어넣어 global video context와 최종 contextualized video 임베딩을 얻는다.

Input Embedder

Notation:

[\text{video clip} \ v=\lbrace v_i\rbrace^{N_v}{i=1}, \quad \text{subtitle} \ s=\lbrace s_i\rbrace^{N_s}{i=1}]

Text Embedder에서, WordPieces를 사용하여 자막 문장 $s_i$를 토큰화하고 각 sub-word token에 대한 최종표현은 token/position embedding을 합한 후 layer normalization(LN)을 통과시켜 얻는다.
Video Embedder에서, ImageNet에서 사전학습한 ResNet과 Kinetics에서 사전학습한 Slow-Fast를 사용, 각 video frame에 대한 2D/3D visual feature를 얻는다. 이들을 이어붙인 뒤 FC layer에 통과시켜 낮은 차원의 공간으로 전사, token embedding으로 사용한다.
Video frame은 연속적이기 때문에 position embedding은 Text Embedder에서와 같은 방법으로 계산된다. Frame에 대한 최종 표현은 FC 출력과 position embedding을 합하여 LN layer를 통과시켜 얻는다.
Input Embedder 이후 $w_{s_i}, v_{s_i}$에 대한 token과 frame embedding은 각각 다음과 같이 표시된다. $d$는 hidden size이다.

[W_{s_i}^{emb} \in \mathbb{R}^{L \times d}, V_{s_i}^{emb} \in \mathbb{R}^{K \times d}]

Cross-modal Transformer

자막과 video frame 간 alignments를 활용하기 위해 각 자막 문장 $s_i$에 대해 대응되는 token $w_{s_i}$와 연관된 visual frames $v_{s_i}$ 사이의 contextualized embedding을 cross-modal attention을 통해 학습한다. 이를 위해 multi-layer Transformer를 사용한다.
Cross-modal Transformer의 출력은 각 자막과 frame에 대한 일련의 contextualized embedding이며 다음과 같이 표시한다.

[\mathbf{V}{s_i}^{cross}, \mathbf{W}{s_i}^{cross} = f_{cross}(\mathbf{V}{s_i}^{emb}, \mathbf{W}{s_i}^{emb}), \quad \mathbf{V}{s_i}^{cross} \in \mathbb{R}^{L \times d}, \mathbf{W}{s_i}^{cross} \in \mathbb{R}^{K \times d}]

$f_{cross}$는 Cross-modal Transformer이다.

Temporal Transformer

Cross-modal Transformer의 출력으로부터 모든 visual frame embedding을 모은 후 video clip의 global context를 학습하기 위해 다른 Transformer를 temporal attention으로 사용한다.

[\mathbf{V}^{cross} = \lbrace \textbf{V}{s_i}^{cross}\rbrace^{N_s}{i=1} \in \mathbb{R}^{N_v \times d}]

위치정보의 손실을 막기 위해 residual connection을 $\textbf{V}^{emb} \in \mathbb{R}^{N_v \times d}$의 뒤에 추가한다. 최종 contextualized video embedding은

[\mathbf{V}^{temp} = f_{temp}(\mathbf{V}^{emb} + \mathbf{V}^{cross}), \quad \mathbf{V}^{temp} \in \mathbb{R}^{N_v \times d}]

$f_{temp}$는 Temporal Transformer이다.

모든 textual/visual feature를 그냥 이어 붙이는(concat) BERT류와 달리 본 논문의 모델은 좀 더 세밀하게 시간적 일치정보를 활용한다. 실험에서 이 방식이 더 나음을 증명한다.

3.2 Pre-training Tasks

MFM과 MLM은 BERT의 것과 비슷하다. VSM은 local & global alignment를 학습하기 위한 것이며, FOM은 영상의 연속적 특성을 모델링하기 위한 task이다.

3.2.1 Masked Language Modeling

입력은 다음과 같다.

• $i$번째 자막 문장 $\mathbf{w}_{s_i}$
• 이와 연관된 visual frames $\mathbf{v}_{s_i}$
• mask index $\mathbf{m} \in \mathbb{N}^M$

15%의 확률로 임의의 word를 [MASK]로 치환하고 이를 맞추는 task이다. 다음 음의 우도를 최소화한다.

$\theta$는 학습 가능한 parameter이며 각 $\mathbf{w}, \mathbf{v}$는 $D$로부터 샘플링된다.

3.2.2 Masked Frame Modeling

MLM과 비슷하지만, MLM은 local context에서 진행되는 데 비해 MFM은 global context에서 수행된다. 목적은 word 대신 masking된 frame $\mathbf{v}_{\mathbf{m}}$을 복구하는 것이다.

Masked frame의 visual feature는 0으로 대체된 상태에서 나머지 frame $\mathbf{v}_{\backslash \mathbf{m}}$과 자막 문장 $\mathbf{s}$을 갖고 복원을 하게 된다. 이산값인 텍스트와는 달리 visual feature는 class 우도로 학습할 수 없고 따라서 다른 목적함수를 도입한다.

Masked Frame Feature Regression (MFFR)

MFFR은 각 masked frame $\mathbf{v}_{\mathbf{m}}^{(i)}$를 visual feature로 회귀시키는 task이다.

출력 frame 표현을 FC layer에 통과시켜 입력 visual feature와 같은 차원인 벡터 $h_{\theta}(\mathbf{v}_{\mathbf{m}}^{(i)})$로 변환한다.

참고로 visual feature는 $r(\mathbf{v}_{\mathbf{m}}^{(i)})$이며, 변환 이후 L2 regression을 적용한다.

Masked Frame Modeling with Noise Contrastive Estimation (MNCE)

Masked visual feature로 바로 회귀시키는 대신 자기지도 표현학습에서 널리 쓰이는 Noise Contrastive Estimation(NCE) loss를 사용한다. NCE loss는 모델이 올바른 frame을 판별할 수 있게 한다.

MFFR과 비슷하게 masked frame $\mathbf{v}_{\mathbf{m}}^{(i)}$을 FC layer에 통과시켜 다음 벡터로 전사한다.

[g_{\theta}(\mathbf{v}_{\mathbf{m}}^{(i)})]

이후 부정 선택지에도 같은 과정을 적용한다.

최종 목적함수는 다음과 같다.

3.2.3 Video-Subtitle Matching

VSM의 입력은 아래와 같다.

• 모든 자막 문장에서 얻은 query $s_q$
• 전체 video clip $\mathbf{v}$
• video clip에 대한 나머지 자막 문장 $\mathbf{s}_{\backslash q}$

모델은 두 가지를 학습해야 한다.

1. local alignment - query와 연관된 frame의 시작과 끝 = $y_{st}, y_{ed} \in \lbrace 1, …, N_v \rbrace $
2. global alignment - query와 match되는 video

학습 방식은 XML 모델을 따라간다. Temporal Transformer의 출력을 최종 frame 표현 $\mathbf{V}^{temp} \in \mathbb{R}^{N_v \times d}$으로 추출한다.
Query는 Cross-modal Transformer에 넣어 다음 textual 표현을 얻는다.

[\mathbf{W}{s_q}^{cross} = f{cross}(\mathbf{0}, \mathbf{W}_{s_q}^{embed})]

이에 기반하여 self-attention layer로 구성된 query encoder, 2개의 선형 layer, LN layer을 사용하여 $ \mathbf{W}_{s_q}^{cross}$로부터 최종 query 벡터 $\mathbf{q} \in \mathbb{R}^d$를 얻는다.

Local Alignment

Local query-video matching 점수는 내적을 사용한다.

[S_{local}(s_q, \mathbf{v}) = \mathbf{V}^{temp} \mathbf{q} \in \mathbb{R}^{N_v}]

2개의 학습가능한 1D convolution filter가 이 점수에 적용되고 softmax를 통과하면 다음 확률벡터를 얻는다. 이는 ground-truth span의 시작과 끝을 나타낸다.

[\mathbf{p}{st}, \mathbf{p}{ed} \in \mathbb{R}^{N_v}]

학습 동안 15%의 자막을 선택하여 cross-entropy loss를 사용한다.

[\mathcal{L}{local} = -\mathbb{E}_D \log (\mathbf{p}{st}[y_{st}]) + \log (\mathbf{p}{ed}[y{ed}])]

$\mathbf{p}[y]$는 벡터 $\mathbf{p}$의 $y$번째 원소이다.

XML에서는 각 modality에 대해 독립적으로 점수를 계산하며 최종점수는 2개의 점수를 합친 것이다.
HERO에서는 multimodal fusion이 그 이전에 행해진다.

Global Alignment

Frame과 query 간 cosine 유사도를 계산하여 matching score를 얻는다.

Positive/Negative query-video 쌍에 대해 결합 hinge loss $\mathcal{L}_h$를 사용한다. Positive 쌍에 대해서 각 원소를 같은 mini-batch 안에 있는 다른 sample로 대체하여 총 2개의 negative sample을 만든다.
목적함수는 다음과 같다.

$\delta$는 margin hyper-parameter이다. 최종 손실함수는 다음과 같다.

[\mathcal{L}{VSM} = \lambda_1 \mathcal{L}{local} + \lambda_2 \mathcal{L}_{global}]

3.2.4 Frame Order Modeling

입력은 다음과 같다.

1. 모든 자막 문장 $\mathbf{s}$
2. visual frames $\mathbf{v}$
3. 재배치 순서 $\mathbf{r} = \lbrace r_i \rbrace^R_{i=1} \in \mathbb{N}^R$

15%의 frame을 순서를 섞으면 모델은 원래 시간순서(timestamp) $ \mathbf{t} = \lbrace t_i \rbrace^R_{i=1}, \ t_i \in \lbrace 1, …, N_v \rbrace$ 를 알아내야 한다.

본 논문에서, FOM은 분류 문제로 형식화하고, $\mathbf{t}$는 재배치 순서의 ground-truth label이다.

재배치는 자막과 frame의 fusion 이후 행해진다. 재배치된 feature는 Temporal Transformer에 넣어 재배치된 visual frame embedding $\mathbf{V}_r^{temp}$를 얻는다.
이 embedding은 FC layer, softmax layer를 통과하여 확률행렬 $\mathbf{P} \in \mathbb{R}^{N_v \times N_v}$를 얻는다. 여기서 각 열 $\mathbf{p}_i \in \mathbb{R}^{N_v}$는 $i$번째 timestamp가 속할 $N_v$개의 timestamp class의 점수를 나타낸다.

FOM에서, 다음 손실함수를 최소화해야 한다.

[\mathcal{L}{FOM} = -\mathbb{E}_D \sum^R{i=1} \log \mathbf{P}[r_i, t_i]]

4. 실험(Experiments)

Text-based Video, Video-moment Retreival, VQA, Video-and-Language Inference, Video Captioning 분야에서 평가한다.
6개의 benchmark(TVR, TVQA, VIOLIN, TVC, DiDeMo, MSR-VTT)을 사용하였다.

4.1 Pre-training Datasets

7.6M개의 video clip을 포함하며 downstream task에 등장하는 모든 영상은 사전학습 데이터셋에서 제거하였다.

TV Dataset

의학 드라마, 시트콤, crime show의 세 장르에서 6개의 TV show를 포함한다. 총 21,793개의 video clip이며 각 clip은 대략 60-90초 사이이다. 인물 간 상호작용과 사회적/전문적 활동 등을 포함하며 대화 목록이 제공된다.

HowTo100M Dataset

YouTube에서 모은 대부분 교육용(instructional) video인 12개의 분류, 1.22M개의 영상을 포함한다. (Food & Entertaining, Home & Garden, 등)
각 영상은 설명(narration)을 자막으로 포함하며 이는 수동으로 혹은 ASR로 얻어졌다. 평균 길이는 6.5분이지만 TV dataset과 비슷하게 맞추기 위해 1분 단위로 잘라 총 7.56M개의 clip을 만들었다.

4.2 New Benchmarks

다양한 내용을 학습하기 위해 text based video-moment retrieval를 위한 How2R, VQA를 위한 How2QA를 제안한다.

How2R

HowTo100M 영상에 대한 annotation을 얻기 위해 AMT를 이용하였다. 영상 자체에 집중하기 위해 narration은 미제공 상태로 이루어졌다.

• 하나의 self-contained scene을 포함하는 영상의 일부분을 구분하는 것
• 분절된 각 영상에 대해 설명을 쓰는 것

최종 분절영상은 10-20초 정도이며 query의 길이는 8-20단어이다.

51390개의 Query, 9371개의 영상을 얻고 각 clip당 2-3개의 query를 포함한다. 데이터셋은 train/val/test가 각 80/10/10%으로 구분된다.

How2QA

역시 AMT를 이용, 분절영상에 대해 1개의 질문과 4개의 선택지를 만들게 하였다.

만들어진 QA 중 매우 편향되게 작성된 것이 많은 관계로(모델이 영상이나 자막으로부터 어떤 정보도 얻지 않고도 답을 맞힐 수 있음) 이를 완화하기 위해 adversarial matching(3개의 오답을 다른 질문의 정답으로 대체)을 사용하였다.

TVQA와 비슷하게 각 질문과 연관된 영상의 시작/끝 부분을 제공하였다. 저품질 annotation을 제거하고 22k개의 60초 clip, 44007개의 QA 쌍을 얻었다. 비슷하게 80/10/10 비율로 나눈다.

4.3 Ablation Study

Optimal Setting of Pre-training Tasks

각 데이터셋별로 다른 사전학습 세팅을 적용하여 실험하였다.

• TV dataset에서 학습된 모델만이 계산량에서 이점을 가진다.
• MLM과 비교하여 MNCE를 추가하는 것은 모든 데이터셋에서 효과가 있다.
• 제일 좋은 조합은 MLM + MNCE + FOM + VSM이다.

Effect of FOM and VSM

• MLM, MNCE, FOM이 같이 학습되면 TVQA에서 큰 향상이 있고, How2R과 How2QA에서도 마찬가지이다.
  • 이는 FOM이 QA task와 같이 temporal reasoning에 의존하는 downstream task에 효과적임을 뜻한다.
• VSM에서 상당한 성과가 있었는데 특히 local/global alignments를 학습함으로써 TVR과 How2R에서 특히 효과적이다.
• 추가적인 MFFR을 더하는 것은 좋지 않았다.
• MFFR은 사전학습 동안 MNCE와 비등하지만 나머지의 경우는 무시할 만한 수준이다.

Effect of Pre-training Datasets

• HowTo100M에서만 사전학습한 모델은 TV dataset에서만 사전학습한 모델보다 TVR에서는 성능이 낮고, 나머지 TVQA, How2R, How2QA에서는 더 좋은 결과를 얻었다.
  • 하나의 가정은 text-based video-moment retreival이 video domain에 더 민감하다는 것이다.
• HowTo100M이 더 많은 수의 영상을 포함하지만 TV 영상에 대해서는 TV로 학습한 것이 더 낫다.

Hierarchical Design vs. Flat Architecture

HERO의 계층적 구조가 좋은 것인지 확인하기 위해 다른 기준모델 2개와 비교하였다.

1. Hierarchical Transformer(H-TRM). Cross-modal Transformer을 RoBERTa 모델로 대체한 것
2. Flat BERT-like encoder(F-TRM)

1. 사전학습 없이 실험한 경우, F-TRM은 HERO에 비해 좋지 않다. 이는 HERO의 영상의 두 modality 간 temporal alignment의 탐색 효과 때문으로 보인다.
2. 사전학습한 경우 차이는 더 큰데, 이는 cross-modal 상호작용과 temporal alignments가 downstream task에 대해 더 나은 표현을 제공함을 뜻한다.

HERO vs. SOTA with and w/o Pre-training

표 2에서 보듯이 사전학습이 있든 없든 HERO가 더 좋은 성능을 보인다.

Key Conclusions

• 최적의 사전학습 세팅은 MLM + MNCE + FOM + VSM이며 HowTo100M과 TV dataset을 모두 사용한다.
• FOM은 특히 시간적 추론을 요하는 task에서 효과적이다.
• VSM은 frame-subtitle 일치정보를 학습하게 하여 특히 video-moment retreival task에서 효과적이다.
• HERO의 계층적 구조는 명시적으로 subtitle과 frame 간 일치 정보를 학습하기 한다.
• HERO는 사전학습이 있든 없든 SOTA를 일관되게 앞선다.

4.4 Results on Downstream Tasks

HERO는 위에서 언급한 최적의 사전학습 세팅을 사용하였다. XML, STAGE, Multi-stream, MMT 등을 능가하는 결과를 볼 수 있다.

Results on Multi-channel Tasks

표 3a에서 다채널 영상에 대한 결과를 볼 수 있다. TVR R@1에서는 XML의 거의 두 배를 기록하는 등 꽤 좋은 성능을 보인다.

Results on Single-channel Tasks

표 3b는 단채널 영상에 대한 결과이다. 역시 DiDeMo, MSR-VTT에 비해 일관되게 좋은 성능이다. 더 자세한 내용은 부록 A.1에 있다.

5. 결론(Conclusion)

Video+Language omni-representation 사전학습을 위한 계층적 encoder를 제안하였다. HERO 모델은 Cross-modal & Temporal Transformer를 사용한 계층적 구조로 새로운 사전학습 task들이 지역적으로 그리고 전역적으로 temporal alignment 정보를 학습하기 위해 제안되었다. HERO는 다수의 vision-language task에서 SOTA를 달성하였고 downstream task에 대한 추가적인 평가방법으로 2개의 새로운 데이터셋(task) How2R과 How2QA를 제시하였다. 추후 연구로는 모델의 확장 버전을 검토하고 더 나은 사전학습 task를 고안할 예정이다.

참고문헌(References)

논문 참조!

이번 글에서는 ClusterGCN이란 알고리즘에 대해 다뤄보겠다. 상세한 내용을 원하면 논문 원본을 참고하길 바라며, 본 글에서는 핵심적인 부분에 대해 요약 정리하도록 할 것이다.

torch_geomectric을 이용하여 ClusterGCN를 사용하는 방법에 대해서 간단하게 Github에 올려두었으니 참고해도 좋을 것이다.

Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks 설명

1. Background

Classic Graph Convolutional Layer의 경우 Full-batch 학습이 필연적이었기 때문에 Graph의 크기가 커질수록 메모리 부담이 굉장히 커진다는 단점을 갖는다. Mini-batch SGD를 적용한 알고리즘 또한 Layer가 증가함에 따라 필요한 이웃 node와 임베딩의 수가 급속도로 증가하는 Neighborhood Expansion Problem에서 자유로울 수 없었다. 결국 GCN의 깊이가 깊어질 수록 연산량이 지수함수적으로 증가하는 것이다.

이를 위해 이웃 sample의 수를 고정하는 GraphSAGE, Importance Sampling을 도입한 FastGCN 등이 제안되었지만, 여전히 완전히 문제를 해결할 수는 없었다. VR-GCN 또한 분산 감소 기술을 통해 이웃 Sampling node의 수를 줄였지만, 여전히 메모리 문제에서 자유로울 수 없었다.

본 논문에서는 위와 같은 문제를 해결하기 위해 ClusterGCN이란 알고리즘을 제안한다. ClusterGCN은 METIS라는 Graph Clustering 알고리즘을 통해 Batch Data를 구성하고 이후 이에 적합한 GCN Layer 구조를 취함으로써 효과적으로 Graph 데이터에 대해 학습하게 된다.

ClusterGCN의 경우 오직 현재 Batch에 존재하는 node에 대해서만 임베딩 벡터를 저장하면 되기 때문에 메모리 사용량을 줄일 수 있다. 그리고 복잡한 이웃 Sampling 과정을 필요로 하지 않고 단지 행렬 곱 연산만 수행하면 되기 때문에 구현에 있어서도 편리한 장점을 지닌다.

추가적으로 본 논문에서는 GCN Layer를 더욱 깊게 쌓는 방법에 대해서도 인사이트를 공유한다. (GNN의 경우 Layer를 깊게 쌓는 것이 꼭 긍정적인 결과를 낳지 않으며, 오히려 정교한 설계 없이 Layer를 쌓으면 역효과가 나는 경우가 많다.)

Graph $G = (\mathcal{V}, \mathcal{E}, \mathcal{A})$ 가 존재하고 이 때 node의 수는 $N$ 이며, node feature matrix의 형상은 $(N, F)$ 이다.

다음이 2017년에 발표된 GCN의 기본 update 식임을 기억하자.

[H^{(l+1)} = \sigma(D^{-1} A H^l W^l)]

[A^{\prime} = D^{-1}A, H^0 = X]

원 논문에서는 이 식에 대하여 Full Gradient Descent를 이용하게 되는데, 앞서 언급하였듯이 이러한 세팅은 대용량의 현실 데이터에 적합하지 않다. mini-batch SGD를 적용한다면 각 SGD 단계는 아래 Gradient Estimation을 계산하게 될 것이다.

[\frac{1}{\vert \mathcal{B} \vert} \Sigma_{i \in \mathcal{B}} \triangledown loss (y_i, z_i^{(L)})]

다만 이렇게 진행할 경우 상대적으로 속도가 크게 느려지는 단점이 있다.

2. Vanilla Cluster-GCN

Cluster-GCN의 Batch를 구성하는 아이디어는 어떤 subgraph를 추출하고 이 subgraph에 포함된 node 집합이 $\mathcal{B}$ 이라고 할 때 각 layer의 계산에 필요한 Adjacency Matrix는 $A_{\mathcal{B}, \mathcal{B}}$ 라는 사실에서 출발한다.

그리고 이 때 생성되는 Embedding 벡터들은 위 subgraph 내에서의 관계에 기초하여 구성될 것이다. 그렇다면 Embedding Utilization을 더욱 향상시키기 위해서는 within-batch edges를 최대로 하는 Batch $\mathcal{B}$ 를 만들어 내야 할 것이다.

Graph $G$ 에 존재하는 Node들을 총 $c$ 개로 나눠보자. 이 때 $\mathcal{V}_t$ 는 t번째 파티션에 속해있는 nodes를 의미한다.

[\mathcal{V} = [\mathcal{V}_1, …, \mathcal{V}_c]]

이제 우리는 아래와 같이 $c$ 개의 subgraph를 갖게 되었다.

[\bar{G} = [\mathcal{G}_1, …, \mathcal{G}_c] = [{ \mathcal{V}_1, \mathcal{E}_1}, …]]

위 규칙에 맞추어 Adjacency Matrix도 나누어보면 아래와 같은 구조를 생각할 수 있다.

[A = \bar{A} + \Delta = \left[ \begin{matrix} A_{11} & … & A_{1c}
\vdots & \ddots & \vdots
A_{c1} & … & A_{cc}
\end{matrix} \right]]

[\bar{A} = \left[ \begin{matrix} A_{11} & … & 0
\vdots & \ddots & \vdots
0 & … & A_{cc}
\end{matrix} \right],

\Delta = \left[ \begin{matrix} 0 & … & A_{1c}
\vdots & \ddots & \vdots
A_{c1} & … & 0
\end{matrix} \right]]

그러니까 $A_{1c}$ 는 파티션1에 속한 node와 파티션c에 속한 node 사이의 link를 담은 Adjacency Matrix인 것이다.

$\bar{A}$ 와 $\Delta$ 의 가치는 명확히 다르다. 앞서 기술하였듯이 within-link edges를 많이 갖고 있는 Batch를 구성하기 위해서는 $\bar{A}$ 를 잘 구성하는 것이 중요하다고 볼 수 있다.

$\bar{A}$ 를 정규화하면 $A^{\prime} = D^{-1} A$ 가 된다.

최종 Embedding Matrix는 아래와 같이 구성된다.

Loss 함수는 아래와 같이 작성할 수 있다.

[\mathcal{L}{\bar{A}^{\prime}} = \Sigma_t \frac{\vert \mathcal{V}_t \vert}{N} \mathcal{L}{\bar{A}^{\prime}{tt}}, \mathcal{L}{\bar{A}^{\prime}{tt}} = \frac{1}{\vert \mathcal{V}_t \vert} \Sigma{i \in \mathcal{V}_t} loss(y_i, z_i^{L})]

그렇다면 $c$ 개의 그룹으로 나누는 기준은 무엇일까? 본 논문에서는 within-clusters links가 between-cluster links 보다 더 많도록 클러스터를 나누기 위해 METIS라는 Graph 군집화 방법론을 적용했다고 밝히고 있다. 원문은 이 곳에서 확인할 수 있다.

위 그림을 보면 더 깊은 Layer로 진행하면서도 설정한 Cluster의 범위를 벗어나지 않는 ClusterGCN의 특성을 확인할 수 있다.

ClusterGCN의 경우 각 Batch 마다 $\bar{A}^{\prime}_{tt} X_t^{(l)} W^{(l)}$ 와 몇몇 부가적인 계산 만 수행하면 되기 때문에 수행 시간 상의 큰 이점을 누린다. 또한 오직 subraph에 해당하는 부분만 GPU 메모리에 올리면 되기 때문에 메모리 Overhead가 발생할 가능성도 줄어든다.

3. Stochastic Multiple Partitions

이전 Chapter까지의 내용만 보고 ClusterGCN을 적용하려고 하면, 아래와 같이 2개의 문제가 발생한다.

먼저, Graph를 여러 조각으로 쪼개면서 $\Delta$ 에 대한 손실이 발생한다. 이는 데이터 손실이므로 성능에 있어 이슈가 발생할 수 있다.

다음으로 Graph 군집화 알고리즘이 유사한 Node를 모아주므로 Cluster의 분포는 원본 데이터의 분포와는 분명 다를 것이기 때문에, 최종적으로 Full Gradient를 계산하여 반환한 결과물의 경우 bias가 발생할 수 있다.

이를 해결하기 위해 Stochastic Multiple Partitions라는 방법론을 도입한다. Graph를 $p$ 개로 나눈다고 하면, 여기서 1개를 선택해서 Batch로 돌리는 것이 아니라 이 중 $q$ 개를 다시 선택해서 이들을 통합한 뒤 하나의 Batch로 취급한다. 즉, 원래 1개만 쓸 것을 여러 개를 합쳐서 쓴다는 의미이다. 이를 통해 Batch 사이의 분산은 줄이면서 between-cluster links는 통합하는 효과를 거둘 수 있다. 실제로 아래 그림을 보면 이와 같은 방법이 효과적이라는 것을 알 수 있다.

4. Issues of training deeper GCNs

본 논문에서는 더욱 깊은 GCN을 학습시키기 위한 간단한 방법을 제시한다. 직관적으로 생각했을 때, 인접한 위치에 있는 node는 멀리 떨어진 node보다 더 큰 영향력을 행사해야 하므로, 각 GCN Layer에서 사용되는 Adjacency Matrix의 대각 원소의 영향력을 더 확대하는 방안이 도입될 수 있다. 즉, 각 GCN Layer의 통합 과정에서 이전 layer에서 넘어온 representation에 더욱 큰 가중치를 부여하는 것이다. 그런데 이 때 그냥 Identity Matrix를 더하면 layer가 증가함에 따라 numerical instability가 지수 함수적으로 커질 수 있기 때문에 이를 고려햐여 아래와 같은 방법이 제안된다.

[\tilde{A} = (D + I)^{-1} (A + I)]

[X^{(l+1)} = \sigma ( (\tilde{A} + \lambda diag (\tilde{A})) X^l W^l )]

최종적으로 ClusterGCN 알고리즘을 정리해보면 아래와 같다.

학습 과정과 실험 과정의 경우 논문 원본을 직접 참고하길 바란다. 특징적인 부분은, 실험 데이터셋으로 새롭게 Amazon2M이라는 데이터가 추가적으로 사용되었다는 것이다. 이 데이터 속에서 node는 상품이고, 같은 장바구니에서 구매되었으면 상품 끼리의 link가 존재한다는 설정이 도입되었다.

0.01의 Learning Rate을 가진 Adam Optimizer와 0.2의 Drop Rate, 그리고 512의 Batch Size를 사용했다는 점은 기억해둘 필요가 있으며, 모든 실험은 NVIDIA Tesla V100 GPU (16GB Memory), 20-core Intel Xeon CPU와 192GB의 RAM 환경에서 이루어졌다. Memory 사용량을 확인하기 위해서 Tensorflow의 경우 tf.contrib.memory_stats.BytesInUse(), Pytorch의 경우 torch.cuda.memory_allocated() 함수를 사용하였다고 밝히고 있다.

마지막으로 언급할 부분은 구현할 때 고려해야할 부분이다. ClusterGCN이 기반으로 하고 있는 Layer의 경우 $D^{-1}AX$ 를 첫 번째 Layer에서 미리 계산해두면 이후에 재사용함으로써 시간을 크게 절약할 수 있기에 이 부분은 반드시 구현하는 것이 필요하다. 그리고 학습 시에는 테스트용 node의 경우 Adjacency Matrix 및 subgraph에서 아예 제거하고, 최종적으로 Test Performance를 확인할 때 다시 삽입하는 방식으로 진행되었다.

그리고 ClusterGCN은 그 구조적 특징 때문에 새로운 node가 들어오는 Inductive한 예측 환경에서는 유연하게 대처할 수 없다는 한계는 지니고 있다.