(이 포스팅에서는 논문 전체를 다루지 않고 Graph-based SSL의 기초적인 부분(Chapter4.A까지)만 다룹니다.)
- paper
https://arxiv.org/pdf/2102.13303.pdf - reference
https://www.youtube.com/watch?v=HM5z8bH29Ag&list=PLetSlH8YjIfWMdw9AuLR5ybkVvGcoG2EW&index=34
https://junhyungbyun.github.io/Graph-based-Semi-Supervised-Learning/
Abstract
Semi-supervised learning (SSL)은 labeld data와 unlabeled data 모두를 통합하는 기능이 있기 때문에 상당한 가치가 있다. Graph-based semi-supervised learning (GSSL)은 다양한 도메인에서 장점이 있다는 것이 입증되었다. 논문의 주요한 기여는 graph regularization과 graph embedding methods를 포함한 GSSL의 새로운 일반화 분류법에 있다.
1. Introduction
Graph-based SSL (GSSL)은 graph 구조상 중요한 manifold를 압축하여 반영하여 자연스럽게 사용될 수 있기때문에 특히 유망하다. graph는 구조적으로 nodes는 모든 samples를 표현할 수 있고 weighted edges는 nodes의 쌍 사이의 유사성을 반영한다.
[GSSL의 주요 과정]
Step 1. Graph construction.
A similarity graph는 labeled, unlabeled samples를 포함한 데이터로 구성되어있다.
original samples사이의 관계를 잘 표현하는 것이 중요한 과제이다.
Step 2. Label inference.
이전 step에서 만들어진 graph 구조 정보를 통합하여 labeled samples로 부터 unlabeled samples로 label 정보를 전파하는 것을 수행한다.
(this paper) Label inference methods are then categorized into two main groups: graph regularization methods and graph embedding methods. [논문참고]
2. Background and Definition
A Comprehensive Survey on Graph Neural Networks
[논문참고]
3. Graph construction
- Goal: $G = (V,E,W)$, V: nodes set, E : edges, W: associate weights(=인접행렬)
- Assumption
- undirected graph임 → W: symmetric
- edge weights는 non-negative → $W_{ij} \ge 0, \forall i \ne j$
- no self-loop
- Edges: similarity weights computed from featureshttps://junhyungbyun.github.io/Graph-based-Semi-Supervised-Learning/
- : x3는 similarity weights(=edge)가 강한 x1과 같은 label을 가질 가능성이 높다
A. Unsupervised methods
기존의 보편적인 전략, graph 구성시 label 정보 무시
- k-nearest-neighbor graph→ 밀도는 고려하지 않음
- $W_{ij} = \begin{cases} sim({\bf x}_i, {\bf x}_j) & i\in \mathcal{N}(j) \\ 0 & otherwise \end{cases}$
- b-Matching:
- (a) graph sparsification (edge selection)$P\in {0,1}^{n\times n}$, 1: egde 존재$\Delta \in \mathcal{R}_{+}^{n\times n}$ : symmetric distance matirx
- $\Sigma_j P_{ij} = b, P_{ii}=0, P_{ij}=P_{ji}, \forall 1 \le i, i \le n$
- $min_{P\in{0,1}^{n\times n}} \Sigma_{i,j} P_{ij} \Delta_{ij}$
- (b) edge re-weighting ($W$구하기)
- Binary kernel, Gaussian kernel(=RBF Kernel), Locally linear reconstruction
- → similarity graph construction시 제한을 줌 ⇒ label inference시 더 균형잡힌 전파 가능
B. Supervised methods
lable 정보를 prior knowledge로서 graph 생성시 사용할 수 있다. ⇒ supervised information를 추가하면 inference 과정을 촉진할 수 있다.
C. ETC(논문에는 언급되지 않음)
fully connected graph: weight decays with distance $w_{ij} = exp(\frac{-||x_i - x_j||^2}{\sigma^2})$
$\epsilon$-radius graph (k-nn과 유사하지만 개수를 제한하지 않음, 단 주변 노드가 없을 수 있음)
4. Graph regularization
- general regularization framework
- $\mathcal{L}(f) = \Sigma_{(x_i,y_i)\in\mathcal{D}}\underbrace{\mathcal{L}_s(f(x_i),y_i)}{supervised\ loss} + \mu \ \Sigma_{x\in\mathcal{D}l+\mathcal{D}_u}\underbrace{\mathcal{L}_r(f(x_i))}{regularization\ loss}$
A. label propagation
주어진 label은 fix해야함. labeled nodes의 정보가 edges를 통해 unlabeled nodes로 label을 예측할 때 가이드하는 역할을 한다.
[basic label propagation 알고리즘]
Step 1. All nodes propagate labels for one step $Y\leftarrow TY$
Step 2. Row-normalize Y to maintain the class probability interpretation.
Step 3. Clamp the labeled data. Repeat from step 2 until Y converges.
1) Gaussian random fields
이차 손실함수의 경우 infinity weight를 가짐 → closed-form으로 만드는 harmonic function을 사용
** Harmonic function: unlabeled data의 경우 descrete labels({0,1})를 continuous values로 표현할 수 있다.
$E(f) = \mathcal{L}_r = \frac{1}{2}\Sigma_{i,j} W_{ij}(f(x_i)-f(x_j))^2$
$f(x_i) = f_l(x_i) \equiv y_i$, $f$를 최소화
- unlabeled nodes는 제약조건 $Lf = 0$을 만족함
- unlabeled node는 neighbor nodes의 평균
- $f(x_j) = \frac{1}{d_j}\Sigma_{i\sim j} W_{ij}f(x_i)$, $j = l+1, \dots, l+u$
- 반복적인 방식으로 해석: $f^{(t+1)} \leftarrow P\cdot f^{(t)}$, $P = D^{-1}W$
$L$: Laplacian matrix
- Diagonal degree matrix$D: D_{ii} = \Sigma_{j=1}^nW_{ij}$ ** degree: node에 연결된 edges 개수
- Graph Laplacian matrix
- $\Delta = D-W$
→ 가중치 행렬을 4 blocks로 분할하면 추론가능
$W = \begin{bmatrix} W_{ll} & W_{lu} \ W_{ul} & W_{uu} \end{bmatrix}$
$f_u = (D_{uu}-W_{uu})^{-1}W_{ul}f_l = (I-P_{uu})^{-1}P_{ul}f_l$
→ 단점)
(a) label을 fix하고 진행하여 noise에 약함 (유연하지 않음)
(b) 새로운 test points에 대해서 직접적으로 적용할 수 없음 (Figure 2. Transductive)
2) Local and global consistency(LGC)
$\mathcal{L}(f) = \frac{1}{2}(\Sigma_{i,j} W_{ij}(\frac{1}{\sqrt{D_{ii}}}f(x_i)- \frac{1}{\sqrt{D_{jj}}}f(x_j))^2)+\mu\ \Sigma_{i=1}^{n_l}(f(x_i)-y_i)^2$
→ GRF와 다른점:
(a) labeled node가 seed label과 같지 않을 수 있음 (=유연함, noise가 있을 때 유리)
(b) $\frac{1}{\sqrt{D_{ii}}}$(degree)로 각 node의 label에 penalty를 줄 수 있음. 상위 nodes의 영향력을 regularization할 수 있고 불규칙한 graph에도 보장함