Robust Graph Neural Networks using Weighted Graph Laplacian

[2nazero]

Robust graph neural networks using weighted graph laplacian

@article{runwal2022robust,
  title={Robust graph neural networks using weighted graph laplacian},
  author={Runwal, Bharat and Kumar, Sandeep and others},
  journal={arXiv preprint arXiv:2208.01853},
  year={2022}
}

[2nazero]

https://github.com/bharat-runwal/rwl-gnn

[2nazero]

그래프 구조 공격에 대해 기존 방어기법에는 다양한 한계들이 존재했다.

그래프 정화(graph purification): GCN-Jaccard 같은 기법은 공격자가 추가한 엣지를 사전에 제거해 그래프를 정화하는 방식을 사용했지만, 이 과정에서 정상적인 엣지까지 제거될 수 있는 단점이 있었다.

저차원 근사: ProGNN 같은 기법은 그래프의 희소성(sparsity), 특징 평활성(smoothness), 저차원성(low-rank) 등의 특성을 이용해, 주어진 그래프를 저차원 근사화하여 공격을 방어했으나 이 방식은 계산 비용이 크고, 대규모 그래프에서 효율적이지 않다는 문제가 있었다.

Attention 기법: GNNGuard와 PA-GNN 같은 기법은 주어진 그래프에서 특징과 구조 간의 관계를 학습해, 공격으로 인해 이상이 생긴 엣지를 식별해 제거하려 했다. 하지만 학습을 통해 적절한 Attention Score를 찾는 것이 어렵고, 공격 강도가 강해지면 방어 성능이 떨어지는 경우가 많았다.

이에 대해 다음 논문에서는 Weighted Laplacian GNN (RWL-GNN)라는 프레임워크를 제시하였다.

이 프레임워크의 핵심은 그래프의 라플라시안 행렬이 가지는 양의 준정부성(Positive Semi-Definiteness)과 특징 평활성(Feature Smoothness)이다. 공격자의 목표가 이질적인 특징을 가진 노드들을 연결해 특성을 방해하는 것임을 이용해, 라플라시안 행렬을 통해 공격으로 인해 추가된 엣지를 자동으로 낮은 가중치로 설정하거나 제거하는 방식이다.

1. 특징 평활성 (Feature Smoothness)

• 목적: 그래프에서 서로 유사한 특징을 가진 노드가 강하게 연결되고, 서로 다른 특징을 가진 노드는 약하게 연결되도록 유도하는 것입니다.
• 작동 방식: 라플라시안 행렬 ( L )을 이용해 디리클레 에너지(Dirichlet Energy)를 최소화함으로써 평활성을 유지해요. 디리클레 에너지는 다음과 같이 정의됩니다:

$$ \text{Dirichlet Energy} = \text{Tr}(X^T L X) = \frac{1}{2} \sum{i,j} L{ij} | x_i - x_j |^2$$

여기서 $\text{Tr}(X^T L X)$는 인접한 노드들 간의 특징 차이를 줄이는 방향으로 그래프를 정렬해요. 즉, 이질적인 특징을 가진 노드 간의 연결을 자동으로 약하게 만들어 공격자가 추가한 노이즈나 엣지를 제거하는 효과를 가져옵니다.

2. 양의 준정부성 (Positive Semi-Definiteness)

• 목적: 그래프의 안정성을 보장하고, 최적화 과정을 쉽게 만들어서 공격 방어에 효율적으로 사용되도록 합니다.
• 작동 방식: 라플라시안 행렬은 항상 양의 준정부성을 가지므로, 모든 고유값이 0 이상이에요. 이 성질은 최적화 과정에서 중요한 역할을 하며, 에너지 최소화 문제를 풀기 쉽도록 만들어 그래프의 구조를 안정적으로 유지하게 합니다.
  • 또한, 양의 준정부성 덕분에 특정 노드나 엣지를 변경하더라도 그래프가 과도하게 왜곡되지 않고 원래 구조에 가깝게 복원될 수 있어요. 이를 통해 RWL-GNN은 공격으로 인해 왜곡된 그래프에서도 중요한 연결을 보호하고, 공격자의 효과를 줄일 수 있어요.