Accurate Node Feature Estimation with Structured Variational Graph Autoencoder

Posted by 날짜:

  본 문서에서는 2022년 KDD 학회에서 발표된 "Accurate Node Feature Estimation with Structured Variational Graph Autoencoder" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.

  • Title: Accurate Node Feature Estimation with Structured Variational Graph Autoencoder
  • Authors: Jaemin Yoo, Hyunsik Jeon, Jinhong Jung, and U Kang
  • Conference: ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2022

Missing Feature Estimation in Graphs

그래프 (graph)는 객체간의 관계를 표현하는 방식이며, 실세계의 많은 데이터가 그래프로 표현됩니다. 예를 들어 소셜 네트워크에서 사용자간의 관계, 전자상거래 사이트에서 상품과 판매자간의 관계, 영화 스트리밍 사이트에서 사용자와 영화간의 관계, 논문 인용 정보 사이트에서 논문간의 관계 등이 그래프로 표현될 수 있습니다. 그래프는 일반적으로 각 정점의 특징 정보 (node feature)를 포함합니다. 소셜 네트워크에서 사용자의 프로필이나 논문 인용 정보 사이트에서 논문의 요약본 등을 정점의 특징 정보로 여길 수 있습니다. 실세계 그래프에서 정점 분류 (node classification) 작업, 간선 예측 (link prediction) 작업 등과 같은 일반적인 그래프 기반의 작업에서 각 정점의 특징 정보 (node feature)는 매우 중요한 정보입니다.

그러나 실세계 그래프에서는 많은 경우에 정점의 특징 정보를 관측할 수 없습니다. 예를 들어 소셜 네트워크에서 사용자들이 본인의 프로필을 비공개로 설정하거나 전자상거래 사이트에서 판매자가 상품의 설명을 생략하는 경우가 흔히 있습니다. 대부분의 그래프 기반 알고리즘들은 정점의 특징 정보를 모두 알고 있다는 가정 하에 동작하기 때문에 이러한 경우에는 제대로 동작하지 않습니다. 따라서 결여된 특징 예측 (missing feature estimation)은 그림 1과 같이 정점 분류나 간선 예측 등 그래프에서의 필수적인 작업의 성능을 향상시킬 수 있습니다. 이 뿐만 아니라, 정점의 정보를 직접적으로 제공하여 다양하게 활용할 수 있는 효과가 있습니다.
그림 1. 그래프에서의 결여된 특징 정보 예측 (missing feature estimation) 예시.

본 논문에서는 이처럼 그래프에서 일부 정점들의 특징 정보를 관측할 수 없을 때, 이를 정확히 예측하는 결여된 특징 예측 (missing feature estimation) 문제를 다룹니다. 구체적인 문제 정의는 다음과 같습니다.
  • 주어진 정보
    • 무방향 그래프 (undirected graph): 정점과 간선의 집합
    • 일부 정점들의 특징 정보
    • 선택사항: 일부 정점들의 라벨 (label)
      • 일반적으로 정점의 라벨 정보는 특징 정보보다 얻기 쉬움
  • 목표
    • 관측되지 않은 정점들의 특징 정보를 정확히 예측

그래프에서 결여된 특징 정보를 예측하는 데에는 두 가지 난문 (challenge)이 있습니다. 첫 번째로, 예측 대상 정점에 대한 정보는 오직 그래프 구조만 있으며, 이는 주변 정점에 대한 정보만 제공하므로 매우 제한적입니다. 두 번째로, 대상 정점의 정보를 나타내는 특징 벡터 (feature vector)는 매우 고차원이며 크게는 수 천 차원입니다. 따라서 정확한 예측을 위해서는 모델의 큰 표현력을 필요로하는데 이는 모델을 쉽게 과적합 (overfitting)시킬 수 있습니다.

Proposed Method

본 논문에서는 그래프의 결여된 특징 정보를 정확히 예측하는 모델인 SVGA (Structured Variational Graph Autoencoder)를 제안합니다. SVGA의 핵심 아이디어는 다음과 같이 요약될 수 있습니다.
  • SVGA 모델은 정점들의 잠재 변수 (latent variables)를 효과적으로 표현하기 위해 그래프의 구조로부터 정점들의 상관 관계를 모델링합니다. 구체적으로, SVGA 모델은 정점들의 잠재 변수의 사전 확률 (prior)을 Gaussian Markov Random Filed (GMRF)로 모델링합니다. GMRF는 그래프 구조에서 인접한 정점들 간의 잠재 변수의 상관 관계를 효과적으로 모델링할 수 있습니다.
  • SVGA 모델은 잠재 변수를 확률적 (stochastic)으로 샘플링하는 것이 아니라, 추론의 안정성을 위해 결정적 (deterministic)인 모델을 사용합니다. 이는 정점들의 고차원 특징 벡터를 예측하는 모델의 학습이 과적합되지 않게 하여 높은 예측 정확도를 달성할 수 있게 합니다.
SVGA는 정점의 정보를 예측하는 문제를 변분 추론 (variational inference)으로 정의하며, 전반적인 모델 구조는 그림 2와 같습니다.

그림 2. SVGA (Structured Variational Graph Autoencoder)의 모델 구조.

SVGA는 그래프의 인접 행렬 (adjacency matrix)를 입력받아 정점들의 특징 매트릭스 X와 라벨 벡터 y를 예측합니다. 먼저, 인코더 (encoder)는 인접 행렬과 정점들의 원핫 (one-hot)벡터를 입력받아 정점들의 잠재 변수 Z를 예측합니다. 이때, 인코더의 네트워크로는 그래프를 잘 모델링하는 것으로 알려진 Graph Convolutional Network (GCN)을 사용합니다. 이후 디코더 (decoder)는 정점들의 잠재 변수 Z를 입력받아 각 정점의 특징 벡터와 라벨을 각각 예측합니다. 이때, 특징 벡터와 라벨을 예측하는 디코더는 별개이며, 잠재 변수 Z가 충분한 정보를 갖는다는 가정 하에 간단한 선형 변환 모델을 사용합니다. 관측된 정점의 특징 벡터와 라벨에 대한 예측 값과 실제 값의 차이를 손실 (loss)로 설정하고, 이를 줄이도록 모델의 파라미터를 업데이트합니다. 모델을 학습할 때, SVGA는 정점들의 잠재 변수 Z가 인접 정점들의 상관 관계를 효과적으로 반영하도록 사전 분포 (prior)를 GMRF로 모델링합니다. 또한, 변분 추론에서 잠재 변수 Z를 얻는 가장 기본적인 방식은 각 정점의 잠재 변수를 독립적으로 샘플링하는 것입니다. 하지만 이는 학습을 불안정하게 하고, 그래프와 같이 잠재 변수간의 상관 관계가 중요한 문제에서는 적합하지 않습니다. 따라서 SVGA는 확률적 샘플링이 아닌, 인코더의 변환 결과를 직접 사용하는 결정적인 방식을 사용합니다. SVGA의 구체적인 모델링 방식과 목적 함수는 논문을 참고하기 바랍니다.

Experiments

본 논문은 제안하는 모델의 우수한 성능을 입증하기 위해 두 가지 실험 결과를 제시합니다. 첫번째 실험은 결여된 정점의 특징 벡터를 정확히 예측하는지 확인하는 것입니다. 그림 3은 SVGA와 경쟁 방법들의 결여된 특징 예측 (missing feature estimation) 성능을 비교합니다. 이진 특징 (binary feature) 예측과 연속적 특징 (continuous feature) 예측에 대해 모두 실험하였고, 모든 경우에 SVGA가 경쟁 방법들보다 좋은 결과를 보였습니다. 이는 SVGA가 경쟁 방법들보다 결여된 정점 특징들의 원본 값을 정확히 예측한다는 것을 의미합니다.

그림 3. SVGA와 경쟁 방법들의 결여된 특징 예측 (missing feature estimation) 성능 비교.
두번째 실험은 특징 벡터를 생성하고 정점 분류 (node classification) 모델을 학습시켰을 때, 모델이 정점을 정확히 분류하는지 확인하는 것입니다. 그림 4는 SVGA와 경쟁 방법들의 특징 생성에 대한 정점 분류 (node classifcation) 성능을 비교합니다. 정점 분류 모델로는 Multi-Layered Perceptron (MLP)와 Graph Convolutional Network (GCN) 두 가지를 사용하였고, 모든 경우에 SVGA가 경쟁 방법들보다 좋은 결과를 보였습니다. 이는 SVGA가 생성한 정점의 특징 정보들이 정점 분류와 같은 일반적인 그래프 기반의 작업에 효과적이라는 것을 의미합니다.
그림 4. SVGA와 경쟁 방법들의 특징 생성에 대한 정점 분류 (node classification) 성능 비교.

Conclusion

본 문서에서는 KDD 22에서 발표된 Accurate Node Feature Estimation with Structured Variational Graph Autoencoder 논문을 소개하였습니다. 해당 논문은 그래프에서 결여된 특징을 정확히 예측하는 SVGA (Structured Variational Graph Autoencoder) 모델을 제안하였습니다.  SVGA는 실세계 데이터에서 경쟁 방법들보다 더 정확하게 결여된 특징을 예측하였습니다. 본 논문은 실세계 다양한 그래프 구조의 데이터에서 유용하게 활용될 수 있습니다. 예를 들어, 아마존과 같은 전자상거래 사이트에서 고객의 특징을 예측하여 더 정확한 상품 추천을 제공할 수 있습니다. 또한, 소셜 네트워크에서 사용자의 특징을 예측하여 이형 (anomaly) 사용자를 미리 찾아내는데 활용할 수 있습니다. 이처럼 본 논문은 실세계 그래프 기반의 데이터에서 다양한 작업을 더 정확하게 수행하는데 활용될 수 있을 것으로 기대됩니다. 본 논문에 대해 더 자세한 정보는 다음 링크에서 확인할 수 있습니다 (링크).