[Paper Review] Graph Contrastive Learning with Adaptive Augmentation (WWW 2021)

Graph Contrastive Learning with Adaptive Augmentation (WWW 2021)

Abstract

• 기존 그래프 CL 방법들의 한계
  
  • 그래프 CL 방법들의 발전에도 불구하고, 데이터 증강 방식 설계는 여전히 미흡한 실정입니다. 데이터 증강은 CL에서 매우 중요한 요소임에도 불구하고 간과되고 있습니다.
  • 데이터 증강 방식은 그래프의 고유한 구조와 속성을 보존해야 합니다. 이는 모델이 중요하지 않은 노드나 엣지에 대한 perturbation에 덜 민감한 표현을 학습하도록 유도합니다.
  • 하지만 기존 방법들은 엣지를 균등하게 제거하거나, 특징을 균등하게 섞는 등 획일적인 데이터 증강 방식을 채택하고 있어 최적의 성능을 내지 못합니다.
• 본 논문에서 제안하는 방법
  
  • 본 논문에서는 그래프의 위상적(topological) 및 의미적(semantic) 측면을 고려한 적응적 증강(adaptive augmentation)을 사용하는 새로운 그래프 Contrastive 표현 학습 방법을 제안합니다.
  • 구체적으로, 위상 수준에서는 노드 중심성(node centrality) 측정에 기반한 증강 방식을 설계하여 중요한 연결 구조를 강조합니다.
  • 노드 속성 수준에서는 중요하지 않은 노드 특징에 더 많은 노이즈를 추가하여 모델이 underlying semantic 정보를 인식하도록 합니다.

Introduction

• 기존의 CL 방법의 문제점
  
  • 획일적인 데이터 증강: 기존의 그래프 CL 방법들은 획일적인 데이터 증강 방식을 사용합니다. 예를 들어, 모든 엣지를 동일한 확률로 제거하거나, 노드 특징을 무작위로 섞는 방식입니다.
  • 다양성 부족: 이러한 단순한 방식은 노드의 다양한 이웃 정보 (contexts)를 생성하는 데 충분하지 않습니다. 특히 노드 특징이 희소할 경우 contrastive objective를 최적화하기 어렵습니다.
  • 노드/엣지 중요도 무시: 기존 연구들은 데이터 증강을 수행할 때 노드와 엣지의 중요도 차이를 고려하지 않습니다. 예를 들어, 중요한 엣지를 무작위로 제거하면 임베딩 품질이 저하될 수 있습니다.
• GCA 프레임워크 개요
  
  • 적응적 데이터 증강(Adaptive Data Augmentation): GCA의 핵심은 그래프의 위상(topology) 및 노드 속성(node attribute) 수준 모두에서 수행되는 joint adaptive data augmentation scheme입니다.
  • GCA는 입력 그래프에 확률적 손상(stochastic corruption)을 가하여 두 개의 연관된 그래프 뷰를 생성합니다.
  • 위상 수준(Topology Level): 노드 중심성(node centrality) 측정에 기반한 증강 기법을 설계하여 중요한 연결 구조를 강조합니다. 즉, 중요도가 낮은 엣지(edge)를 제거할 확률을 높여 중요한 연결 구조를 보존합니다.
  • 노드 속성 수준(Node Attribute Level): 중요하지 않은 노드 특징에 더 많은 노이즈를 추가하여 노드 속성을 손상시켜 모델이 기본적인 의미 정보를 인식하도록 합니다.
  • 대조 손실(Contrastive Loss): GCA는 두 뷰에서 동일한 노드의 임베딩이 서로 일치하도록 장려하고 다른 노드의 임베딩과 구별되도록 하는 대조 손실 함수를 사용합니다. 이를 통해 모델은 뷰 간의 일관성을 학습하고 노드의 중요한 특징을 추출할 수 있습니다.
• GCA의 작동 방식
  
  • 그래프 뷰 생성: 먼저, 입력 그래프에 대해 확률적 데이터 증강을 수행하여 두 개의 그래프 뷰를 생성합니다. 이때, 엣지 제거와 특징 마스킹(feature masking)을 통해 다양한 뷰를 생성합니다.
  • 노드 임베딩 학습: 공유된 GNN(Graph Neural Network) 인코더를 사용하여 각 뷰의 노드 임베딩을 학습합니다.
    대조 학습: 대조 손실 함수를 사용하여 두 뷰 간의 노드 임베딩 일치를 최대화합니다. 이를 통해 모델은 중요한 그래프 구조와 속성을 보존하는 강력한 노드 표현을 학습합니다.

The Proposed Method

The Contrastive Learning Framework

• GCA 개요
  
  • 목표: 그래프 데이터의 비지도 학습을 위해 그래프의 서로 다른 뷰 간의 노드 임베딩 일관성을 최대화하는 것 입니다.
    접근 방식:
  • Graph Augmentation: 입력 그래프에 stochastic augmentation을 적용하여 두 개의 그래프 뷰를 생성합니다.
  • Contrastive Objective: 두 뷰에서 동일 노드의 임베딩은 유사하게, 다른 노드의 임베딩은 다르게 학습하도록 contrastive objective를 사용합니다.
• Multi-view graph CL setting

 

• 데이터 증강 함수 샘플링
  • 가능한 모든 augmentation 함수의 집합 T 에서 두 개의 stochastic augmentation 함수 t 와 t' 를 샘플링
  • 대조학습시, 매 에폭마다 새롭게 augmentation 함수를 샘플링하여 매 에폭마다 다른 augmentation 함수를 사용함
  • GNN 인코더 f 를 사용하여 각 2개 서로다른 뷰의 노드 임베딩 U 와 V 를 얻습니다.
  • 두 뷰에 있는 다른 모든 노드를 negative sample로 간주합니다.
  • Inter-view negative sample과 intra-view negative sample로 구성됩니다.

• Overall training objective
  • 전체 objective는 모든 positive pair에 대한 pairwise objective의 평균입니다.
  • 두 뷰가 대칭적이므로, 각 뷰에 대한 손실을 계산하고 평균을 취합니다.

• GCA 학습 과정
  
  • 데이터 증강 함수 샘플링: 각 학습 epoch에서 데이터 증강 함수 t 와 t' 를 샘플링합니다.
  • 그래프 뷰 생성: 샘플링된 함수를 사용하여 그래프 G 의 두 뷰 G_1 와 G_2 를 생성합니다.
  • 노드 표현 획득: GNN 인코더 f 를 사용하여 G_1 와 G_2 의 노드 표현 U 와 V 를 얻습니다.
  • 파라미터 업데이트: objective 함수 J 를 최대화하여 모델 파라미터를 업데이트합니다.

Adaptive Graph Augmentation

Topology-level augmentation

 

그래프 증강을 위해 그래프의 edge 을 제거하는 방법에 대해 설명하고 있습니다. 중요한 edge은 보존하고 덜 중요한 edge을 제거할 확률을 높여 그래프의 핵심 구조를 유지하는 adaptive augmentation 방법을 제안합니다.

edge 를 제거할 확률은 식 (3) 과 같이 정의됩니다. 이 확률은 해당 edge 의 중요도를 계산하여, 중요도 값에 따라 확률이 달라지게 됩니다. 

edge 를 제거할 확률은 식(4) 와 같이 계산되며, 이 확률을 계산하는데에 3가지의 노드 중심성 함수로 degree centrality, eigenvector centrality, PageRank centrality 가 사용됩니다. 본 연구에서는 중요하지 않은 edge 을 더 높은 확률로 제거하면서 그래프의 중요한 연결 구조를 보존하는 adaptive augmentation 방법을 수행합니다. 이러한 Adaptive augmentation은 모델이 불필요한 노이즈에 덜 민감하게 만들고, 그래프의 중요한 패턴을 학습하도록 유도합니다.

• 그래프의 노드 중심성을 측정하는 3 가지 방법 (노드 중심성 함수)
  • Degree Centrality (연결 중심성)
    
    1. 노드의 연결된 정도를 측정하는 가장 기본적인 중심성 척도입니다 
    2. 방향성이 있는 그래프에서는 in-degree(들어오는 연결 수)를 사용합니다. 이는 방향 그래프에서 노드로 향하는 연결이 노드의 영향력을 나타내기 때문입니다.
    3. 인용 네트워크(citation networks)에서 degree centrality가 높은 노드는 다른 논문으로부터 인용을 많이 받은 영향력 있는 논문일 가능성이 큽니다.
  • Eigenvector Centrality (고유 벡터 중심성)
    
    1. 노드의 연결된 정도뿐만 아니라, 연결된 이웃 노드의 중요성 또한 고려하는 척도입니다 
    2. 각 노드의 고유 벡터 중심성은 이웃 노드들의 중심성 합에 비례합니다. 즉, 많은 이웃에 연결되거나, 영향력 있는 노드에 연결된 노드가 높은 고유 벡터 중심성을 갖습니다.
    3. 방향성이 있는 그래프에서는 들어오는 엣지에 해당하는 오른쪽 고유 벡터(right eigenvector)를 사용하여 중심성을 계산합니다.
       주요 고유 벡터(leading eigenvector)만 필요하므로 계산 부담이 적습니다.
  • PageRank Centrality (페이지랭크 중심성)
    
    1. PageRank 알고리즘에 의해 계산된 PageRank 가중치로 정의됩니다.
    2. 방향성이 있는 엣지를 따라 영향력을 전파하며, 가장 많은 영향력을 받는 노드를 중요한 노드로 간주합니다.

• 적응적 구조 증강 방식에 대한 직관을 얻기 위해 Karate club 데이터셋에 대한 시각화 결과
  
  • Karate Club 데이터셋: 이 데이터셋은 두 코치가 이끄는 두 그룹의 학생들로 구성되어 있으며, edge centrality 점수를 계산하여 시각화했습니다
  • Edge Centrality 시각화: 엣지의 두께로 centrality 값을 표현했으며, 노드 색상은 네트워크 내의 두 클래스(코치는 주황색)를 나타냅니다.
  • 결과 분석
    
    1. 세 가지 방식(degree, eigenvector, PageRank)이 약간의 차이는 있지만, 모두 그룹 내에서 두 코치를 연결하는 엣지를 강조하는 경향을 보입니다.
    2. 그룹 간 주변 노드 연결에는 덜 집중합니다.
    3. 이는 제안된 노드 centrality 기반 적응적 topology 증강 방식이 그래프의 기본적인 구조를 인식할 수 있음을 보여줍니다.

Node-attribute-level augmentation

Salt-and-pepper noise와의 유사성: 디지털 이미지 처리에서 사용되는 Salt-and-pepper noise와 유사하게, 노드 속성에 노이즈를 추가합니다. 구체적으로, 노드 특징의 일부 차원을 0으로 마스킹합니다.

확률 p 의 중요성: topology-level augmentation과 유사하게, 확률 p 는 노드 특징의 i 번째 차원의 중요도를 반영해야 합니다. 저자들은 영향력 있는 노드에서 자주 나타나는 특징 차원이 중요하다고 가정합니다. 마스킹될 확률 p 가 각 특징 차원의 중요도를 반영하도록 설계됩니다. 즉, 덜 중요한 특징은 더 높은 확률로 마스킹되고, 더 중요한 특징은 낮은 확률로 마스킹됩니다.

 

• Sparse one-hot node features: 노드 u 에서 특징 i 가 나타나는지 (1) 또는 나타나지 않는지 (0)를 고려합니다. (식 7)

• Continuous node features: 특징 값의 절대적인 크기와 해당 노드의 중요도를 결합합니다. (식 8)

• 확률 계산: 계산된 중요도 w_i 를 바탕으로 각 특징이 마스킹될 확률 p 를 계산합니다. 이는 중요도가 낮은 특징일수록 더 높은 확률로 마스킹되도록 하기 위함입니다. (식 9)

• Adaptive augmentation: 위상 수준 및 노드 속성 수준 Augmentation을 결합하여 두 개의 손상된 그래프 뷰 G_1, G_2 를 생성합니다. GCA에서는 대조 학습을 위해 다양한 컨텍스트를 제공하기 위해 두 뷰를 생성하는 확률 p^e 와 p^f 가 서로 다릅니다. 
• 모델 변형: GCA-DE, GCA-EV 및 GCA-PR의 세 가지 모델 변형을 제안하고 평가합니다. 세 가지 변형은 각각 degree, eigenvector 및 PageRank 중심성 측정값을 사용합니다. 모든 노드 중심성 및 가중치 측정값은 원래 그래프의 위상 및 노드 속성에만 의존합니다. 따라서 한 번만 계산하면 되므로 계산 부담이 크지 않습니다.

4 Experiments

• RQ1: Does our proposed GCA outperform existing baseline methods on node classification?
• RQ2
  • Do all proposed adaptive graph augmentation schemes benefit the learning of the proposed model?
  • How does each graph augmentation scheme affect model performance?
• RQ3
  • Is the proposed model sensitive to hyperparameters?
  • How do key hyperparameters impact the model performance?

Datasets

Baselines

• (1) Traditional methods
  
  • DeepWalk 
  • node2vec
• (2) Deep learning methods
  • Graph Autoencoders (GAE, VGAE)
  • DGI: Deep Graph Infomax
  • GMI: Graphical Mutual Information Maximization 
  • MVGRL: Multi-View Graph Representation Learning

Performance on Node Classification (RQ1)

 

• 전반적인 성능
  
  • GCA는 transductive task에서 기존의 비지도 학습(unsupervised learning) 모델들보다 일관적으로 더 나은 성능을 보였습니다. 
  • Coauthor 데이터셋에서 기존 baseline 모델들도 이미 높은 성능을 보였지만, GCA는 그 경계를 더욱 확장했습니다.
  • 특히 GCA는 label 정보를 사용하여 학습된 모델들과 비교해도 경쟁력 있는 성능을 보였습니다.
• DeepWalk와 GCN 기반 방법 비교
  
  • DeepWalk와 같은 전통적인 contrastive learning 방법은 일부 데이터셋(Coauthor-CS, Coauthor-Physics)에서 raw feature만 사용하는 logistic regression classifier보다 성능이 낮았습니다. 이는 이러한 방법들이 node feature를 효과적으로 활용하지 못할 수 있음을 시사합니다.
  • GCN 기반 방법(예: GAE)은 node embedding을 학습할 때 node feature를 통합할 수 있었습니다.
  • 그러나 특정 데이터셋(Wiki-CS)에서는 GAE의 성능이 DeepWalk + feature보다 여전히 좋지 않았는데, 이는 GAE가 edge를 기반으로 contrastive pair를 선택하는 단순한 negative sample 선택 방법 때문일 수 있습니다.
• Adaptive Data Augmentation의 중요성
  
  • DGI, GMI, MVGRL과 같은 기존 baseline 모델과 비교했을 때, GCA는 negative sample을 구성할 때 강력하고 adaptive한 data augmentation을 수행하여 더 나은 성능을 얻었습니다.
  • MVGRL이 diffusion을 사용하여 global 정보를 augmented view에 통합하지만, 입력 그래프에서 edge의 중요도를 adaptive하게 고려하지 못한다는 점을 지적합니다.
  • GCA의 뛰어난 성능은 제안된 adaptive data augmentation 방식이 섭동(perturbation) 중 중요한 패턴을 보존하여 embedding 품질을 향상시키는 데 도움이 된다는 것을 입증합니다.
• GCA 변형 모델들의 성능
  
  • 다양한 node centrality 측정 방법을 사용한 GCA의 세 가지 변형 모델이 모든 데이터셋에서 기존의 contrastive baseline 모델보다 뛰어난 성능을 보였습니다.
  • degree centrality와 PageRank centrality를 사용한 GCA-DE 및 GCA-PR이 모든 데이터셋에서 가장 좋거나 경쟁력 있는 성능을 달성했습니다. 이는 제안된 모델이 특정 centrality 측정 방법에만 국한되지 않으며, 제안된 프레임워크의 효과와 일반성을 입증합니다.

Ablation Studies (RQ2)

• GCA-T-A
  • topology와 attribute 모두 uniform augmentation을 적용한 모델입니다. 즉, 모든 노드와 엣지에 대해 동일한 확률로 augmentation을 수행합니다. 
  • 여기서 topology는 그래프의 구조(노드와 엣지의 연결 관계)를 의미하고, attribute는 노드의 특징(feature)을 의미합니다.
• GCA-T: GCA-T-A 모델에서 attribute augmentation만 adaptive augmentation으로 변경한 모델입니다.
• GCA-A: GCA-T-A 모델에서 topology augmentation만 adaptive augmentation으로 변경한 모델입니다.
• GCA
  • topology와 attribute 모두 adaptive augmentation을 적용한 모델입니다. 
  • Adaptive augmentation은 본 연구에서 제안한 노드의 중요도에 따라 augmentation 확률을 다르게 적용하는 방식입니다.
• 실험결과: Table 4 (ablation study) 의 결과를 통해 topology-level과 node-attribute-level 모두 adaptive augmentation을 적용했을 때 모델 성능이 가장 좋다는 것을 알 수 있습니다. 이는 adaptive augmentation이 그래프의 중요한 구조와 속성을 보존하면서 불필요한 노이즈를 제거하는 데 효과적이기 때문입니다.

Sensitivity Analysis (RQ3)

• Sensitivity analysis: GCA 모델의 핵심 하이퍼파라미터인 네 가지 확률 변수가 모델 성능에 미치는 영향을 분석합니다. 이러한 확률 변수들은 그래프 뷰(graph view) 생성 방식을 결정합니다.
• 파라미터 설정: 분석의 간결성을 위해, 토폴로지 수준 증강(topology level augmentation)의 크기를 조절하는 확률와 노드 속성 수준 증강(node attribute level augmentation)의 크기를 조절하는 확률을 0.1 에서 0.9 까지 값에 대해 transductive node classification 을 Amazon-Photo 데이터셋을 사용하여 실험합니다.
• 실험결과 분석
  
  • 안정성: 정확도 측면에서 노드 분류 성능은 파라미터 값이 너무 크지 않을 때 비교적 안정적인 plateau 형태를 보입니다. 즉, 모델은 이러한 확률 변수에 크게 민감하지 않으며, 하이퍼파라미터 변화에 강건(robust)함을 보여줍니다.
  • 성능 저하: 확률 값이 너무 커지면(예: > 0.5) 원본 그래프가 심각하게 손상됩니다. 예를 들어, \(p_e = 0.9\)일 경우, 기존의 거의 모든 엣지가 제거되어 생성된 그래프 뷰에서 고립된 노드가 발생합니다. 이러한 상황에서는 GNN이 노드 주변(neighborhood)으로부터 유용한 정보를 학습하기 어렵습니다. 결과적으로, 학습된 두 그래프 뷰의 노드 임베딩(node embedding)이 충분히 구별되지 않아 contrastive objective를 최적화하기 어렵게 됩니다.
• 결론: GCA 모델은 적절한 범위 내의 하이퍼파라미터 설정에서 안정적인 성능을 보이지만, 과도한 데이터 증강은 오히려 성능 저하를 초래할 수 있습니다.

5 Conclusion

• 주요 내용: 본 논문에서는 적응적 증강을 활용한 새로운 그래프 대조 학습 프레임워크를 제안합니다. 제안하는 모델은 그래프 구조와 속성에 적응적인 방식으로 데이터를 증강하여 생성된 뷰(view) 간의 노드 임베딩 일치를 최대화함으로써 표현(representation)을 학습합니다.
• 핵심 아이디어: 네트워크 중심성 측정을 통해 중요한 에지와 특징 차원을 식별하고, 중요하지 않은 에지에 높은 제거 확률을 할당하여 모델이 네트워크 연결 패턴을 인식하도록 합니다. 또한 중요하지 않은 특징 차원에 더 많은 노이즈를 추가하여 속성을 손상시켜 모델이 기본적인 의미 정보를 강조하도록 합니다.
• 실험 결과: 다양한 실제 데이터 세트에 대한 실험 결과, 제안된 GCA 방법이 기존의 최첨단 방법보다 성능이 뛰어나고 일부 지도 학습 모델보다도 우수한 결과를 보였습니다. 이는 제안된 적응적 증강 방식이 효과적임을 입증합니다.