[Paper Review] Bipartite Graph Embedding via Mutual Information Maximization

등긁는 고슴도치·2021년 5월 29일
1
  • Jiangxia Cao, Xixun Lin et al.
  • Institute of Information Engineering, University of Chinese Academy of Sciences
  • WSDM 2021

Abstract

  • 이전 bipartite 그래프 임베딩은 random walk-based 혹은 reconstruction-based 기반
  • 이 방법론들은 그래프의 local graph strucuture를 학습하기에 효과적이나 global property까지 보존하진 못함
    • homogenous 노드 간 community structure
    • heterogenous 노드 간 long-range dependencies
  • 본 논문은 이러한 global property까지 보존할 수 있는 local-global infomax objective를 제안함 (BiGI)
    • (1) global representation은
      • u에 대한 representaion과 v에 대한 representation을 함께 이용해 표현
    • (2) local representation
      • subgraph-level의 어텐션 메커니즘을 제안
    • (3) Infomax objective
      • 이 두 representation간 mutual information을 최대화함으로 성능을 높임
  • 3가지 종류의 데이터셋에서 top-k 추천과 link prediction에 대해 state-of-the-art 성능을 보임

Introduction

  • Bipartite graph 모델링 기법은 크게 2가지로 나눌 수 있음.
      1. Random walk-based
      • 다양한 node sequence를 생성하기 위해 random walk
      • 다음, sliding window 내 context node들을 예측하는 방향으로 학습
      1. Reconstruction-based
      • collaborative 필터링과 유사하게 adjacency matrix를 재구성하는 방향으로 학습
  • 이러한 기존 방법론들은 슬라이딩 윈도우 내 노드들 / 이웃 노드들이 밀접하게 관련이 있다는 가정하에 local graph structure를 학습하는데 초점을 둘 뿐, global property는 학습하기 어려움

위 그림에서 하늘색 화살표가 heterogenous 노드 간 long-range dependency 의미, 주황색 바탕이 homogenous 노드 간 community structure 의미합니다.

  • homogenous 노드 간 community structure
    • 영화 'Lion King'은 'Ice Age', 'Toy Story'와 비슷한 장르를 가진 비슷한 영화로 여겨질 수 있지만, 'Lion King'이 이 영화들과 연결이 되어 있지 않기에 local graph structure로는 이러한 community structure를 포착하기 어려움
  • heterogenous 노드 간 long-range dependencies
    • 사용자 'Lily'와 영화 'Ice Age'는 연결이 안되어 있기에 두 노드 간 long range dependency 또한 포착하기 어려움

Bipartite Graph Embedding

  • homogeneous 그래프 임베딩
    • DeepWalk, LINE, Node2vec, VGAE이 있음
  • heterogenous 그래프 임베딩
    • Metapath2vec, DMGI이 있음
    • 위 두 방법 다 Bipartite graph에 초점을 둔 것은 아니기에 Bipartite그래프의 구조적 특성 보존 어려움
  • Bipartite graph에 초점을 둔 기법들
    • PinSage, IGE, BiNE, FOBE
  • Matrix completion
  • Collaborative filtering
  • 그러나 이 모델들도 local graph structure 모델링에 초점을 두는 한계 존재

Background

  • G=(U,V,E)G = (U,V,E)는 bipartite 그래프
  • UUVV는 다른 종류의 node set, EE는 edge set
  • Bipartite graph embedding의 목적은 각 노드를 d차원 벡터로 맵핑하는 것

Proposed Model

1. Bipartite Graph Encoder

  • 각 노드 임베딩은 2-hop neighbor로부터 학습
    • bipartite 그래프는 u-v-u-v.. 와 같이 표현되므로 2-hop
  • 2번 평균 내는 방식으로 사용
    • k 레이어의 노드 uiu_i 임베딩을 얻기 위해서는
      • 1차 : uiu_i 이웃 노드들 각각에 대해 노드 임베딩을 평균내서 구한다 (그림 a)
        • 평균 낼 때 자기 자신은 미포함 (화살표 없음)
      • 2차 : 이렇게 구한 각 이웃 노드들의 임베딩을 평균낸다 (그림 b)
        • 평균 낼 때 자기 자신은 포함 (화살표 있음)
        • 평균 내어 구한 임베딩에 자기 자신의 이전 레이어 임베딩을 concat해 W 곱하여 구함
  • 위 수식은 노드 uiu_i에 대한 수식인데 vv에 대해서도 마찬가지 방식으로 구하면 된다 (그림 c,d)

2. Local-Glabal Infomax

(1) Global Representation

  • 모든 u 노드들의 노드 임베딩을 평균, 모든 v 노드들의 노드 임베딩을 평균해 활성화 함수 거쳐서 concat해 global representation을 구함

(2) Local Representation

  • 1. H-hop Enclosing Subgraph
  • 어떤 노드 v가 주어졌을 때 이 v에 대한 sub-graph는 v로부터 거리가 h 이내인 u들이다.
    • 이때 h는 항상 짝수이다 (u-v-u-v.. 로 표현되는 bipartite 그래프이기 때문)
    • u에 대한 subgraph도 마찬가지 방식으로 구함
  • 2. Attention weight
    • v로부터 거리가 h 이내인 u들 각각과 가중합 및 곱하여 softmax 하듯 계산해 attention weight를 구함 (attention mechanism과 유사)
    • u에 대한 Attention weight도 마찬가지 방식으로 구함
  • 최종 형태
    • 어떤 (u,v)의 edge가 주어졌을 때, 노드 v와 가까운 노드 u들 각각의 attenion weight를 곱해 연산을 취한 값과, 마찬가지로 노드 u와 가까운 노드 v들 각각의 attenion weight를 곱해 연산을 취한 값을 concat하여 최종 local representaion을 구함

(3) Infomax Objective

  • Negative samping을 이용함
  • β\beta의 확률로 negative 샘플 생성 (corruption)
  • 아래와 같이 Binary Cross-Entropy loss 이용하여 local representation과 global representaion의 MI(mutual information) 최대화

3. 모델 학습

  • local representation과 global representaion의 MI 최대화하는 LmL_m과 negative sampling된 노드 쌍을 고려한 margin-based ranking loss를 최소화하는 LrL_r의 조합
  • Negative sampling은 u-v가 있을 때 u 또는 v가 다른 u' 또는 v'로 대체됨

4. Model Analysis

  • Parameter overhead를 방지하기 위해 인코더를 공유하여 GGGG~ 학습 (아래 그림의 Encoder 블록)

Experiments

  • DBLP, MovieLens, Wikipedia 데이터셋 이용
  • user-item interation 행렬을 implicit 데이터로 변환
  • 60%의 edge로 학습, 40% edge로 테스트
  • Top-k 추천에서도, link prediction에서도 가장 좋은 성능을 보임
  • 여러 Ablation study (비교)를 통해 논문에서 제안하는 방식이 좋은 성능을 보임을 실험
  • Representation을 이용해 클러스터링 했을 때도 다른 방법론보다 좋은 성능을 보임
    • community structure를 잘 포착하는 것 알 수 있음
  • 노드 간 거리가 짧지 않더라도 (5~7만큼 떨어져 있더라도) 잘 예측함

Conclusion

  • two-hop neighbor의 노드 임베딩을 학습해 각 노드에 대한 노드 임베딩 값을 구함
  • u에 대한 representaion과 v에 대한 representation을 함께 이용해 global representation 표현
  • subgraph-level에서(가까운 노드들 이용) attention weight를 구해 local representation 표현
  • 이 두 representation간 mutual information을 최대화함으로 성능을 높임
  • 다른 임베딩 방법론의 한계인 global properties를 모두 포착할 수 있음
    • homogenous 노드 간 community structure
    • heterogenous와 노드 간 long-range dependencies
profile
천천히 다만 꾸준히

0개의 댓글