기술 요약: SLeDGe – 그래프 구조 학습을 이용한 데이터 스트림 상의 준지도 학습 (Semi-Supervised Learning on Data Streams with Graph Structure Learning)

1. 문제 정의

본 논문은 데이터 스트림 상의 준지도 학습(Semi-Supervised Learning, SSL) 문제를 다룹니다. 이 환경에서 데이터는 고용량으로 순차적으로($D = \{x_t\}_{t=1}^T$) 도착하며, 학습자는 다음과 같은 두 가지 엄격한 제약 조건 하에서 작동해야 합니다:

1. 메모리 제약: 시스템은 고정된 제한된 메모리 용량($M$)을 가지며, 스트림의 전체 이력을 저장할 수 없습니다.
2. 레이블 희소성: 유입되는 샘플 중 극히 일부만이 관측된 레이블($y_t$)을 가지고 있어, 전통적인 지도 학습 방식으로는 수행이 불가능합니다.

기존의 스트림 기반 SSL 방법들은 샘플을 독립적으로 취급하거나, 고정된 유사도 휴리스틱(진화하는 관계를 포착하지 못함)에 의존하거나, 정적인 오프라인 데이터셋을 가정한다는 점에서 한계를 보입니다. 핵심 문제는 제한된 레이블 감독(supervision)을 어떻게 효과적으로 미레이블 샘플로 전파하면서, 시간 경과에 따른 데이터 분포 및 관계의 지속적인 진화에 적응할 것인가 하는 점입니다.

2. 방법론: SLeDGe

저자들은 예측 모델과 적응형 그래프 구조를 공동으로 학습하는 프레임워크인 SLeDGe(Semi-supervised Learning on Data Stream with Graph structure learning)를 제안합니다. 이 방법은 매 유입되는 샘플 $x_t$에 대해 세 가지 연속적인 단계로 작동합니다.

A. 이중 메모리 업데이트 메커니즘 (Dual-Memory Update Mechanism)

신속한 적응(가소성, plasticity)과 역사적 일관성 유지(안정성, stability) 사이의 균형을 맞추기 위해, SLeDGe는 두 개의 서로 다른 압축된 메모리 버퍼를 유지합니다:

• 레이블된 메모리 ($M_L$): 가소성에 최적화되었습니다. 각 클래스의 프로토타입을 저장합니다. 새로운 레이블 샘플이 도착하면, 빈 슬롯을 채우거나 가중 결합을 통해 가장 유사한 기존 프로토타입을 업데이트합니다. 업데이트 가중치 $\alpha$는 동적이며, 새로운 특징을 빠르게 통합하기 위해 새로운 입력을 선호하도록 설정됩니다.
• 레이블되지 않은 메모리 ($M_U$): 안정성에 최적화되었습니다. 대표적인 미레이블 프로토타입을 저장합니다. 이곳의 업데이트는 기존 프로토타입을 선호하는 가중치 $\beta$를 사용하며, 이는 미레이블 데이터의 불확실성을 반영하고 점진적인 정보 축적을 보장합니다.

B. 동적 그래프 구조 학습 (Dynamic Graph Structure Learning, GSL)

SLeDGe는 고정된 그래프나 정적 유사도 지표를 사용하는 대신, 매 타임스텝마다 결합된 메모리($M_L \cup M_U$)와 현재 샘플 $x_t$에 대해 동적으로 그래프를 구축합니다.

1. 임베딩 ($f_E$): 다층 퍼셉트론(MLP)이 입력 특징을 잠재 공간(latent space)으로 매핑합니다.
2. 스코어링 ($f_S$): 스코어링 함수(코사인 유사도)가 메모리의 모든 노드와 현재 샘플 간의 쌍별 관계 가중치를 계산하여 조밀한 인접 행렬(dense adjacency matrix)을 생성합니다.
3. 프루닝 ($f_P$): 효율성을 보장하기 위해, 조밀한 행렬을 프루닝하여 노드당 상위-$k$개의 연결만을 유지함으로써 희소 인접 행렬 $A_t$를 생성합니다.
4. 분류 ($f_B$): 그래프 합성곱 네트워크(GCN) 스타일의 백본이 학습된 그래프 구조 $A_t$를 통해 감독 정보를 전파하여 예측을 생성합니다.

C. 모델 최적화

모델은 다음과 같은 복합 손실 함수를 사용하여 업데이트됩니다:

• 지도 학습 손실 ($L_L$): 최근 샘플에 우선순위를 두기 위해 시간적 감쇠 요인(temporal decay factor)에 의해 가중치가 부여된 레이블된 메모리에 대한 교차 엔트로피 손실입니다.
• 구조적 정규화 ($L_{reg}$): 입력 공간에서의 쌍별 유사도와 잠재 공간에서의 유사도 간의 일관성을 장려하는 항입니다. 이는 동적 그래프 추론을 안정화하여 그래프 구조가 불규칙해지는 것을 방지합니다.

D. 경량화 변형: SLeDGe-L

메모리 크이 $M$이 클 때 발생하는 그래프 구축의 이차 시간 복잡도($O(M^2)$) 문제를 해결하기 위해, 저자들은 SLeDGe-L을 제안합니다. 이 변형은 그래프 스코어링을 클래스 중심 접근 방식으로 제한하여, 레이블된 프로토타입과 모든 메모리 샘플 사이의 유사도만을 계산합니다. 이를 통해 복잡도를 $M$에 대한 선형 시간($O(c \cdot M)$, 여기서 $c$는 클래스 수)으로 줄입니다.

3. 주요 기여

1. 적응형 그래프 구조: 고정된 그래프에 의존하는 기존의 스트림 SSL 방법들과 달리, SLeDGe는 데이터 스트림과 함께 진화하며 시간 가변적인 샘플 간 의존성을 포착하는 동적 그래프 토폴로지를 학습합니다.
2. 이중 전략 메모리 관리: 레이블된 메모리(가소성 중심)와 레이벨되지 않은 메모리(안정성 중심)에 대한 별도의 업데이트 전략 도입을 통해, 새로운 특징에 대한 적응과 역사적 지식의 보존 사이의 균형을 맞출 수 있습니다.
3. 제약 조건 하의 효율성: 본 프레임워크는 희소 그래프 프루닝과 경량화 변형(SLeDGe-L)을 통해 계산 효율성을 유지하면서, 엄격한 메모리 예산과 극도로 낮은 레이블 희소성(최저 0.1% 레이블) 하에서도 작동하도록 설계되었습니다.
4. 구조적 정규화: 일관성 정규화 항의 포함은 학습된 그래프 구조가 스트리밍 과정 동안 안정적이고 의미 있게 유지되도록 보장합니다.

4. 실험 결과

저자들은 웹, 이미지, 테이블 데이터 도메인을 아우르는 12개의 데이터셋에서 SLeDGe를 평가했습니다.

• 성능: SLeDGe는 모든 데이터셋에서 최신 경쟁 모델들(TLP, ReSSL, HDSSL)을 능가했습니다.
  • 0.1% 레이블 상황에서, 가장 강력한 베이스라인 대비 평균 **31.7%**의 상대적 정확도 향상을 달면했습니다.
  • 1.0% 레이블 상황에서, 평균 **14.8%**의 상대적 정확도 향상을 달성했습니다.
• 절제 연구 (Ablation Studies): 실험을 통해 메모리 모듈과 동적 그래프 구조 모두가 매우 중요하다는 것이 확인되었습니다. 동적 그래프를 제거하고 정적 k-NN 그래프로 되돌렸을 때 성능이 현저히 낮아졌으며, 이는 진화하는 관계를 학습하는 것의 필요성을 입증합니다.
• 확장성: 이 방법은 데이터 스트림 크기에 대해 선형적으로 확장되는 특성을 보여줍니다 (샘플당 상수 시간 소요). SLeDGe-L은 전체 버전과 비교하여 메모리 버퍼 크기에 대해 우수한 확장성을 보여주었으며, 이는 이론적 복잡도 분석을 뒷받침합니다.
• 속도: 딥러닝 모델임에도 불구하고, 특히 고차원 데이터에서 임베딩 수준의 계산을 활용함으로써 클러스터 기반 방법들과 경쟁할 만한 실행 시간을 보여주었습니다.

5. 의의 및 주장

본 논문은 메모리와 레이블이 극도로 제한된 환경에서 그래프 구조 학습(GSL)을 스트리밍 환경에 적용함으로써 기존 문헌의 중요한 공백을 메운다고 주장합니다. 저자들은 기존 방법들이 샘플 간의 관계가 시간에 따라 어떻게 진화하는지를 모델링하지 못하기 때문에 실패한다고 설명합니다. 예측 모델과 그래프 구조를 공동으로 학습함으로써, SLeDGe는 데이터 이력 전체를 저장할 필요 없이 제한된 감독 정보를 미레이블 데이터로 효과적으로 전파하여 상당한 정확도 향상을 달{%}성합니다. 이 연구는 비정상적(non-stationary) 데이터 스트림 환경에서 동적 그래프 추론이 정적 유사도 측정보다 우월함을 강조합니다.