728x90 반응형 CS224W26 [CS224w] Label Propagation on Graphs (3) - Correct & Smooth (C&S) ReferenceCombining Label Propagation and Simple Models Out-performs Graph Neural Networks IntroductionCorrect & Smooth (C&S)는 node classification method에서 SOTA 이다.이 글을 포스팅하는 (2023.07.12) ogbn-products의 top-10 중에서 5개는 C&S 방법을 적용하였다.Label Propagation (LP)는 homophily(또는 associativity)를 이용하지만 정작 node feature vector를 이용하지 않는다. 즉 LP는 neighbor averaging이다.Graph Neural Network (GNN)은 feature vector를 이용하.. 2023. 7. 13. [CS224w] Label Propagation on Graphs (2) - Label Propagation Label Propagationlabeled node는 ground truth label $Y_v^*$로 초기화한다.unlabeled node는 $Y_v = 0.5$로 초기화한다. Update each unlabeled node\[ P^{(t+1)}(Y_v = c) = \cfrac{1}{\sum_{(v, u) \in E} A_{v,u} } \sum_{(v, u) \in E} A_{v, u} P^{(t)}(Y_v = c) \]$A_{v, u}$: edge에 가중치(strength, weight)가 있다면 $A_{v, u}$는 두 노드 $v$와 $u$ 사이의 edge weight를 나타낸다.$P(Y_v = c)$: 노드 $v$가 label이 $c$일 확률convergence할 때 까지 반복하여 update를.. 2023. 7. 13. [CS224w] Label Propagation on Graphs (1) - Outline Introduction주어진 데이터 그래프의 모든 노드에 label이 있지 않을 수 있다.이 때 network의 다른 node에 label을 어떻게 할당할 수 있을까? 기본적으로 node embedding (random walk, GNN 등)을 이용하여 해결할 수 있지만, network topology를 이용한 방법은 없을까?Observation: Correlations in Networks이웃한 노드들은 서로 correlated한 경향이 있다.이웃하는 노드가 상관성을 갖는 것은 크게 homophily와 influence로 설명할 수 있다.Homophily: 같은 interest를 갖는 사람들끼리 더 연결되는 경향이 있다.Influence: 내가 친구에게 음악을 추천새주면, 친구들 중 일부는 나랑 같은 .. 2023. 7. 12. [CS224w] General Tips for Debugging GNN 꼭 GNN에 해당하는 내용은 아니겠지만, cs224w에서 별도의 강의 슬라이드를 만들었으니 간단히 정리한다. General Tips데이터 전처리는 매우 중요하다. note attribute는 매우 많다. 따라서 정규화(normalization)을 해야한다. 확률이라면 $(0, 1)$로, 필요(데이터)에 따라 넓은 범위도 가능하다. Optimizer: Adam이면 상대적으로 robust하다.Activation function: ReLU도 충분하지만 LeakyReLU, PReLU도 좋다. 그러나 output layer에는 activation function을 적용하면 안된다. 그리고 모든 layer에 bias를 추가한다.Embedding dimension: 32, 64, 128 차원에서 시작한다. 학습결과에.. 2023. 6. 18. [CS224w] Theory of GNNs (2) - Neighbor Aggregation, GIN (Graph Isomorphism Network) 전 포스팅에서는 GNN의 node embedding이 왜 표현력이 좋은지 omputational graph의 관점에서 설명했다.이번에는 neighbor aggregation의 관점에서 더 살펴보자. Neighbor AggregationNeighbor aggregation은 multi-set function과 동일한 구조를 갖는 것에서 시작한다.aggregation function으로 GCN (ICLR 2017)에서는 mean-pool, GraphSAGE (NeurIPS)에서 max-pool을 제안하였다.GCN에서는 $\text{Mean}(\{ x_u \}_{u \in N(v)})$GraphSAGE에서는 $\text{Max}(\{ x_u \}_{u \in N(v)})$GCN (mean-pool) [ICLR.. 2023. 6. 17. [CS224w] Theory of GNNs (1) - Local Neighborhood Structures, Computational Graph Local Neighborhood Structures같은 색의 노드는 같은 feature를 갖는다고 하자. 위의 경우 5개의 노드가 동일한 feature를 가진 경우이다.1번 노드와 4번 노드는 degree가 2로 동일하지만, neighborhood structure는 다르다.1번 노드의 이웃노드들은 degree=2지만, 4번 노드의 이웃노드들은 degree가 1 또는 3으로 다르기 때문이다. 1번 노드와 2번 노드는 neighborhood structure가 동일하다.모두 이웃 노드의 degree가 2와 3으로 동일하다. Can GNN node embeddings distinguish differenct node's local neighborhood structures?Computational Grap.. 2023. 6. 14. 이전 1 2 3 4 5 다음 728x90 반응형
