Inductive Representation Learning on Large Graphs, Neurips 2017

yenguage·2022년 1월 11일
0

Papers

목록 보기
8/9
post-thumbnail

Inductive Representation Learning on Large Graphs, Neurips 2017

GraphSAGE

Goal

improving node embedding via inductive graph neural network

Challenge

  • GCN-based inductive node embedding problem
    • transductive models cannot generalize to unseen nodes. & real world evolving graph
    • unseen node에 대해 generalize가 잘 된다는 것은, 임베딩을 만들 때 모델이 새로운 subgraphs에 대해서도 잘 align 할 수 있어야 한다는 말.
    • inductive 모델은 structure 관점에서 각 노드의 local role과 global position 둘 다를 잘 학습할 수 있어야 함.

Solution

  • node feature (ex. text attributes, node profile, node degrees) 및 structural feature 를 학습에 활용
  • a set of aggregator functions가 node의 local neighborhood를 aggregate하는 법을 학습하도록 해서, test 때 unseen node에 대해서도 embedding을 잘 뽑을 수 있도록 함.

Method

  • 각 iteration 마다 각 노드는 local neighborhood information을 aggregate 한다.
    • mini-batch training
      1) 각 노드는 1-hop 이웃 표현을 agg해서 하나의 벡터로 표현
      • GraphSAGE에서 이웃이란?
        : fixed-size의 이웃 노드를 uniform sampling. 각 iteration마다 이웃이 달라질 수 있음.
        2) central node와 1)의 agg된 이웃들 표현(single vector)을 concat
        3) concat 된 표현은 fc layer를 거침
  • A set of aggregators : Mean AGG, LSTM AGG, Pooling AGG
    • Mean AGG : 이웃 노드들 벡터 표현에 대해서 elementwise mean. Symmetric (O) / Trainable (X)
    • LSTM AGG : LSTM은 permutation invariant 하지 않기 때문에 (sequential한 순서가 존재함), 이웃노드들을 랜덤하게 셔플링한 다음에 LSTM에 넣어줌. Symmetric (X) / Trainable (O)
    • Pooling AGG : 각각의 이웃노드 벡터가 FC layer를 거친 다음에 elementwise max-pooling을 한다. Symmetric (O) / Trainable (O)
unsupervised Loss for GraphSAGE

  • vv : central node uu 근처에서에서 fixed-length random walk를 했을 때 co-occur하는 이웃노드
  • 즉, 랜덤워크 상의 이웃 노드들과 중심노드의 표현이 유사해지도록 학습. cluster assumption을 따라가도록.
  • 논문에선 기본적으로는 unsupervised loss를 소개해주는데, fully supervised도 당연히 가능하다.

  • K는 depth를 의미하는데, GraphSAGE는 forward 과정에선 immediate node만을 neighbor로 여기고, depth를 늘려가면서 더 멀리 있는 (higher connectivity) 노드들의 information 을 함께 반영할 수 있게 된다.

Evaluation

  • node classification for testing the ability to generate useful embeddings on unseen data
  • test on evolving document graphs (Citation, Reddit)
  • test on multi-graph generalization experiment (Protein-Protein graph)

ETC.

  • forward 할 때는 1-hop neighbors를 대상으로 하고, unsupervised loss 계산할 때는 fixed-length random walk 로 이웃을 정한다. 헷갈릴 수도 있을 듯.
  • 레스코백 교수님 논문!
  • PinSAGE 논문이 GraphSAGE를 토대로 recommendation에 초점을 맞춰서 이어서 하신 연구인가봄. 모델이 거의 비슷하다.
  • 벨로그에선 접기/펼치기 기능이 안 돼서 속상하다. 벨로그의 깔끔함과 포인트 초록색이 너무너무 마음에 들지만 접기가 안 돼서 글이 너무 지저분해보인다. 이제 슬슬 정들어가는데 속상해서 눈물이 날 것 같다. 깃허브로 이사갈까 고민 중...ㅠ_ㅠ

Source

Inductive Representation Learning on Large Graphs, Neurips 2017
https://arxiv.org/pdf/1706.02216.pdf

profile
신비한 AI 나라의 소시민

0개의 댓글