Contents
해당 논문은 WSDM'23에서 발표된 논문이며, 논문 제목에서도 알 수 있듯, Structural Distribution Shift (SDS) 문제를 완화한 Graph Anomaly Detection 모델을 제안한다. SDS 문제는 정상 데이터에 비해 비정상 데이터의 수가 매우 적어서 발생하는 문제를 의미한다. 본 논문에서는 특정 지점에서의 이질적인 이웃의 영향을 완화하고, Invariant하도록 만들기 위한 Graph Decomposition Network (GDN) 기법을 제안하였다.
Link: https://github.com/blacksingular/wsdm_GDN
GitHub - blacksingular/wsdm_GDN: [WSDM 2023] "Alleviating Structrual Distribution Shift in Graph Anomaly Detection" by Yuan Gao,
[WSDM 2023] "Alleviating Structrual Distribution Shift in Graph Anomaly Detection" by Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, Yongdong Zhang - GitHub - blacksingula...
github.com
Introduction
Graph Anomaly Detection (GAD)에서는 이질성(Heterophily)과 동질성(Homophily)이라는 구조적 분포를 가지고 있다. 이질성이 높을수록 그래프 내 노드의 이웃들이 다른 라벨을 가지는 노드들로 구성되어 있다는 것을 의미하고, 동질성이 높을수록 노드와 이웃 노드들이 서로 같은 라벨을 가진다는 것을 의미한다. [Figure 1 참조]
GAD에서는 Train mask, valid mask, test mask를 통해, 학습 단계에서는 학습 데이터를 제외한 나머지 정보는 마스킹 처리를 하고, 검증 단계와 테스트 단계에서는 각 단계에 속하는 노드를 제외한 나머지 노드들은 마스킹 처리를 한 후 노드에 대한 라벨을 예측하는 형태로 수행된다. 아래의 그림을 살펴보면, 이상치(Abnormal)는 상대적으로 적은 양의 데이터를 가지고 있기 때문에 이웃들이 대부분 정상 데이터로 되어 있어 이질성은 높고, 동질성은 낮은 형태로 구성되어 있다. 반면에, 정상 데이터는 주변 노드들이 대부분 정상 데이터로 구성되어 있기 때문에 동질성은 높고, 이질성은 낮은 형태를 띈다.
그래프에서는 일반적으로, 주변 노드의 정보를 취합하여 해당 노드의 정보를 업데이트하는 형태로 구성되어 있기 때문에, 주변 노드가 어떤지에 따라 노드의 표현(Representation)이 달라진다. 따라서, 이상치 주변에 정상치 데이터가 많이 존재한다면, 이상치를 제대로 감지할 수 없게 된다. 본 논문에서는 이와 같은 분포의 불균형을 완화하기 위해 Graph Decompostiion Network (GDN) 기법을 제안하였다.
Methodology
본 논문에서는 SDS Problem가 정확히 어떤 것인지에 대해서 먼저 다루고, Invariant Feature Extraction 그리고, Constraints Loss에 대해서 다룬다. 먼저, SDS Problem에 대해서 알아보자.
Structural Distribution Shift in GAD
SDS는 구조적으로 분포가 치우쳐져 있다는 것을 의미한다. SDS는 $p_{train}$과 $p_{test}$에서 마스킹하는 양이 달라지기 때문에 학습 데이터에서의 이질성, 동질성의 분포와 검증 데이터에서의 이질성, 동질성의 분포가 달라지는 현상을 의미한다.
\[ p_{train} ( [ X_{hetero} (v_1), X_{homo} (v_1)]) \neq p_{test} ([X_{hetero} (v_2), X_{homo}(v_2)]) \]
\[ p_{train} (\psi (v), x_v, o) \neq p(x_v, o) \]
\[ \mathcal{D}[p_{train} (\phi(v), x_v, o), p(x_v, o) ] \]
이때 $\mathcal{D}(p(x), g(x)) = \int_{\mathcal{X}} p(x) \psi(\frac{g(x)}{p(x)})dx $는 거리 함수로, 본 논문에서는 KL divergence를 사용하였다. $o$는 학습에서 관측된 노드를 의미한다.
GNN-based GAD 방법은 주변 노드의 패턴을 학습해, 학습 단계에서 관측하지 못한 노드에게 전달하기 때문에 SDS를 무시하고 있다. 이때 SDS로 인해, 모델의 성능을 저하시키는 원인이 된다.
\[ \mathbb{E}_{v \tilde p} [ l(g(\psi (v), x_v))] \neq \mathbb{E}_{(v,o)) \tilde p_{train}} [ l(g(\psi(v), x_v)) | o = 1 ] \]
위 수식에서, $\mathbb{E}_v \tilde p[l(g(\psi(v), x_v))]$는 GNN 기반 목적 함수의 기댓값을 의미하고, 우변은 학습 데이터에서 손실의 기댓값을 의미한다. 즉, 실제 검증 데이터의 기댓값과 학습 데이터의 기댓값이 다른 문제가 발생한다.
Invariant Feature Extraction
SDS의 부정적인 영향을 완화하기 위해, SDS에 상관없이 Invariant하다고 예상되는 특징을 추출하는 것을 목적으로 한다. 이상치에 대해서는 기존 선행 연구에서 제안된 Variable Decompostion 방식을 참고하여, Node Feature $X$를 Class Feature $C$와 Surrounding Feature $S$로 분해(Decompose)하여 사용한다.
\[ \begin{equation} \begin{split} \mathbb{E}[Y_{train} | \Phi(X_{train})] & = \mathbb{E} [Y_{train} | C_{train}, S_{train} ] \\ \\ & = \mathbb{E} [ Y_{train} | C_{train}] = \mathbb{E} [Y|C] \end{split} \end{equation} \]
$\Phi(X_{train})$는 학습 데이터의 이웃 특징 분포 (Neighbor Feature Distribution)를 의미한다.
반면에, 정상 데이터의 경우에는 아래와 같은 수식을 따른다.
\[ \alpha^{(l,c)}_k = \frac{1}{N} | \sum^N_{n=1} \frac{ \partial y^{(c)}}{\partial H^{(l)}_{k,n} } | \]
$y^{(c)}$는 Ground Truth $c$의 예측된 확률을 의미하고, $H$는 은닉층(Hidden Layer)의 특징 표현(Feature Representation)을 의미한다. 본 논문에서는 Gradient Score를 기반으로 Feature Selector를 구성하였다. 최종적으로 학습의 최적화를 위해 아래와 같은 제약 조건을 도입하였다.
Constraints
본 논문에서는 같은 클래스에 속해 있는 두 노드 간의 유사도 ($C$)를 최대화하기 위한 Class Constraints 와 두 노드가 이웃이면 최대화하고, 아니면 최소화하기 위한 즉, 연결 여부에 따라 최적화하기 위한 Connectivity Constraint를 도입하였다.
\[ \mathcal{L}_{cla}(v) = KL(C_v, proto_+) - KL(C_v, proto_-) \]
\[ \mathcal{L}_{sur}(v) = \sum_{u \in \mathcal{L}(v)} KL(S_u, S_v) - \sum_{u \notin \mathcal{N}(v)} KL(S_u, S_v) \]
\[ \mathcal{L}_{constraint} = \frac{1}{|N|} \sum_{v:y_v = 1} \mathcal{L}_{cla}(v) + \mathcal{L}_{sur} (v) \]
$proto_+$와 $proto_-$는 각각 이상치와 정상에 대한 사전 분포(Prior Distribution)를 의미한다. $L_{sur}$에서 이웃이 아닌 노드는 랜덤 샘플링을 해서 선택한다. GNN에서 널리 사용되는 방법은 Prototype vector를 통해 Global Context를 학습하는 방식이다.
\[ s^{(e)}_v = cosine(h^{(e)}_v, proto^{(e-1)}), \quad w^{(e)}_v = \frac{ \exp (s^{(e)}_v / \tau )}{\sum^N_{u=1} \exp (s^{(e)}_u / \tau )} \]
\[ proto^{(e)} = \sum^N_{v=1} w_v \cdot h^{(e)}_v \]
$w^{(e)}_v$는 각 노드의 가중치를 의미한다. 이렇게 계산된 Prototype vector가 SDS에 제약을 주어 모델을 학습한다. 최종 목적 함수는 Cross-Entropy Loss와 Constraint Loss의 조합으로 구성된다.
\[ \mathcal{L}_{GDN} = \sum_{v \in \mathcal{V}} -\log(y_v \cdot \sigma(z_v)) + \lambda \exp (\mathcal{L}_{constraint}) \]
이때 Backbone 모델은 RGCN을 사용하였다.
Experiments
본 논문은 Xiangnan He 교수님이 교신저자로 되어 있는데, 해당 교수님은 추천 시스템에서 NCF를 쓰신 분이시며, 실험 단계에서 Research Question (RQ)을 제시하고 이를 해결하는 형태로 실험을 구성한다. 본 연구에서는 총 4가지 RQ를 제시하였다.
RQ1. How does our model GDN perform compared with SOTA graph anomaly detection methods? Section 4.2
RQ2. Can GDN alleviate the SDS problem on biased dataset? Section 4.3 - 4.4
RQ3. Is the proposed model effective under different hyper-parameter settings? Section 4.5
RQ4. Is GDN framework flexible to various GNN backbones and helpful in enhancing them? Section 4.6
RQ1. 는 그래서 GDN 모델이 SOTA 모델보다 좋은 지에 대한 실험이고, RQ2. 는 실제로 데이터셋에서 SDS 문제를 완화할 수 있는가? 에 대한 실험이다. RQ3. 는 초매개변수(Hyper-parameter)를 달리 했을 때 성능 즉, 민감도 분석에 대한 실험이고, RQ4. 는 GDN의 Backbone 모델을 달리 했을 때의 성능을 비교한 실험이다.
