GNN32 CS224w - 14. Community Detection in Networks Part 2 Louvain Algorithm Louvain algorithm은 community detection에 활용되는 알고리즘입니다. 현재 그래프에서 neighborhood node를 추가하는데, 주위에서 Q maximal하게 늘릴 수 있는 node를 greedy하게 search합니다. 해당 node를 찾으면 community에 aggregate합니다. Community에 node를 추가하는 과정에서, 기존의 다른 community에 있던 node를 제외시킬수도 있습니다. 따라서 이 과정에서는 D에서 i가 빠져나가는 것과 새로 C로 편입되는 과정의 $\Delta Q$를 계산해야 합니다. Modularity Q는 식 정리를 통해서 비교적 간단하게 구할 수 있습니다. Community 내부 edge수와 총 edg.. 2022. 11. 21. CS224w - 14. Community Detection in Networks Part 1 Community Detection in Networks Granovetter’s Research의 연구에서는 close-friend 보다 지인의 중요성을 설명합니다. 강의 전반과 강하게 연결되는 내용은 아니지만, 우리 삶에서는 자주 느낄 수 있는 포인트입니다. 그 이유는 강한 친밀도의 친구끼리는 이미 많은 정보가 공유되고 있기 때문입니다. 이미 그들 사이의 정보는 redundant information일 확률이 높습니다. 어떤 식으로 community를 정할지에 대한 고민을 하는 과정에서, triadic closure를 이야기할 수 있습니다. A와 B가 연결되어있고, A와 C가 연결되어 있다면 B와 C도 연결될 가능성이 높다고 보는 것이 triadic closure입니다. 또한 edge overlap을.. 2022. 11. 21. CS224w - 13. GNNs for Recommender Systems Part 2 LightGCN NGCF에서 학습하는 파라미터는 두 가지로, Shallow user/item embeddings, GNN parameter입니다. 하지만 굳이 GNN이 끼지 않아도 shallow learnable embedding은 노드 단위로 이루어지기 때문에 충분히 expressive하다고 볼 수 있습니다. LightGCN은 NGCF를 세 가지 방법으로 simplify합니다. Adjacency matrix 개선, GCN 개선, 그리고 non-linearity 제거로 오히려 recommendation performance가 더 향상되는 결과를 보였습니다. 먼저 user와 item에 대해서 위와 같은 새로운 형태의 adjacency matrix를 제시할 수 있습니다. User와 item이 개별 축에 존재.. 2022. 11. 21. CS224w - 13. GNNs for Recommender Systems Part 1 Recommender Systems Tasks and Evaluation Recommender system의 graph는 user와 item, 두 가지 노드로 이루어진 bipartite graph입니다. Recommendation task를 정의하자면 과거의 user-item interaction을 통해 새로운 user-item interaction을 예측하는 link prediction으로 볼 수 있습니다. 유저에게 K개의 item을 추천해주고, 그 K개의 item 중에 가장 많은 수의 높은 interaction 가능성이 있는 item을 추천해주는 것이 목표입니다. 주로 Recall @K를 evaluation metric으로 사용합니다. Recommender Systems: Embedding-Based.. 2022. 11. 21. CS224w - 12. Identifying and Counting Motifs in Networks Part 2 Neural Subgraph Representations (Subgraph Matching) 지금까지는 motif counting해서 중요한 motif를 확인하는 방법을 알아봤습니다. 하지만 그 matching이 어렵다는 단점이 있습니다. Matching problem은 query graph가 target graph의 subgraph인지 확인하는 binary prediction task와 일치합니다. 이때 query graph의 embedding과 target graph에서 sampling한 node의 neighborhood embedding을 구하여 비교한다. Query subgraph에서 anchor를 잡고, target graph에서도 anchor를 잡습니다. 그 이후에 해당 anchor의 k-ho.. 2022. 11. 18. CS224w - 12. Identifying and Counting Motifs in Networks Part 1 이번 강의의 내용은 크게 세 가지로 나누어집니다. Subgraphs and Motifs Neural Subgraph Representations Mining Frequent Motifs Subgraph와 motif를 어떻게 neural network를 이용하여 표현하고, counting할지에 대한 내용을 담고 있다고 보시면 됩니다. Subgraphs and Motifs 강의 가장 처음에 나오는 내용은 node-induced subgraph와 edge-induced subgraph에 대한 내용입니다. 각각 target graph의 비교 기준이 node와 edge인데, 크게 중요하지 않은 내용이므로 넘어가겠습니다. 우리는 node label이 다 달라도 어떻게 특정 graph가 target graph의 su.. 2022. 11. 18. 이전 1 2 3 4 5 6 다음
