이 wandb 리포트는 Stanford CS224 그래프 머신러닝 과정 강의 노트입니다.

저는 그래프 신경망(Graph Neural Networks)라는 용어를 처음 흥미로운 알게 해준 Kaggle 문제를 접하게 되었고, 어떻게 딥러닝이 그래프 구조(graph-structured) 데이터세트와 함께 작동하는지에 대해 학습하기 위해 자료를 찾고 있었습니다. 온라인에서 여러 자료를 찾았지만, 완전히 이해하기에는 너무 어려웠었고, 자료를 읽고 난 뒤에도 궁금증은 계속 남아 있었습니다. CNN 입문서들을 통해 그래프에 대한 스펙트럼법(spectral methods)을 접하게 되었습니다. 잠시 동안 포기했었지만 곧바로 PyTorch geometric의 정말 잘 쓰여진 문서에 달려들기로 결심했고 colab에서 간단한 문제(toy problems)를 활용했습니다. GNN을 이용해서 해결할 수 있는 문제에 어떤 것이 있는지 알게 되었지만 여전히 핵심적인 직관적 지식에 대해서는 제대로 파악하지 못했습니다. PyTorch 모델에서 얼마나 다양한 합성곱 레이어가 tensor demensions(차원)을 변화 시키는지 파악할 수 없었습니다. “그래, 그래서 이 사람들은 그래프에서 컨볼루션(convolution)을 한다고 하는데, 더 많은 레이어를 추가할수록 그래프가 점점 더 작아진다는 말이야? 그렇다면 어떻게 작아지는 것으로 정해진 거지?” 같은 의구심의 들었습니다.

마침내, 저는 Jure Leskovec의 이 훌륭한 강의 시리즈를 접하게 되었고, 그래프 신경망뿐만 아니라 머신러닝의 전 영역이 그래프에 어떻게 적용되는지에 대해 알려주었을 뿐만 아니라, GNN 및 기타 고급 개념을 이해하는데 필요한 직관력을 배양할 수 있도록 큰 도움을 줬습니다. 이 강의에서 그래프에 대해 매우 구체적인 새로운 개념을 접하게 되었습니다. 네트워크에 대해 독창적으로 생각해낼 수 있는 분명한 피처 공학(feature engineering) 또는 속성(properties) 외에도 motifs, graphlets, 피처 공학을 수행하는 널 그래프(null graph)의 개념 및 스펙트럼법 같은 참신한 개념이 많이 있습니다. 메인 강사인 Juve Leskovec께서는 이러한 모든 개념을 접근하기 쉽고 직관적으로 만드는 데 아주 큰 역할을 했습니다. 이러한 개념의 대부분은 어렵지 않았답니다. 어떤 경우에는 이러한 개념 뒤의 수학이 어려울 수도 있지만, 이 개념들이 설명하는 부분과 결과는 이해하기 쉬웠습니다.

저는 이 노트를 부분적으로는 포괄적인 참고 자료로 쓰기 위해 작성하고 또한 그래프 신경망을 처음 접하는 모든 분들이 이러한 개념들에 좀 더 쉽게 다가갈 수 있도록 돕고자 이 노트를 작성하고 싶었습니다. 과거에 GNN에 무지했었던 제 자신이 이 노트를 이해할 수 있고 이러한 개념에 대한 강한 직관력을 구축할 수 있도록 최선을 다해 이 노트를 만들었습니다.

노트 사용법:

그래프 신경망에만 관심 있으신 경우, 챕터 8, 9, 17, 18, 19만 읽으시면 됩니다. 이 과정에서는 GCN, GraphSAGE, GAT, GIN, PinSage, GCPN, 및 기타 신경망에 대해서 소개하고 있습니다. 챕터 9는 PyTorch 지오메트릭에 대해 소개하고 있으며 이 노트에 대한 실제 강의를 따르지는 않았습니다. 저는 GNN 몇 개를 훈련시키고 또한 colab notebook을 포함했습니다. 그래프 생성 알고리듬(Graph Generation algorithms)에 관심이 있으신 경우, GraphRNN에 대해서 작성한 챕터 10을 확인하시기 바랍니다.

하지만, 적어도 그래프의 측면에서 ml 기본사항을 소개하고 있는 처음 10개의 챕터는 훑어보시기 바랍니다. 특성 벡터(feature vector)가 일반 ML에서 2차원에 불과하고 CNN을 사용하여 직접 이미지 분류기(classifier)를 훈련시킬 때 선형 회귀(liear regression)을 훈련하는 동안 추가적인 특성을 생성하는 방법을 모른다고 상상해보세요. 그렇지 않다면, 그래프에서 가능한 두 종류의 클러스터링(clusterings)와 같은 것들도 누락될 수 있습니다. 하나는 역할 탐색용이며 다른 하나는 커뮤니티 탐색용입니다. 스펙트럼 클러스터링 노트는 수학으로 가득 차 있어 어려워 보일 수 있지만, 여러분들이 스펙트럼 클러스터링이 어떤 것을 하는지 이해하기 위해 파악해야 할 것은 단 하나의 핵심 직관뿐입니다. 챕터 11에서 16까지는 페이지랭크(PageRank), 캐스케이드(cascades), 에피데믹(epidemics), 영향(influence), 최대화(maximization)와 같은 그래프의 다른 측면에 대해서 다루고 있습니다.

그리고, 네트워크 진화(network evolution)에 대해서 다루고 있는 챕터 16에서는, 대부분의 강의를 이해할 수 없었습니다. 저는 시간 페이지랭크(Temporal Pagerank) 같은 개념들 말입니다. 그래서 이에 대한 부분은 제 노트에 제대로 담아내지 못했습니다.

이 리포트에서 고전적인 그래프 데이터세트에 대한 일부 GNN만을 훈련했지만, 앞으로 이 과정을 마치기 위해 소규모 프로젝트를 진행할 계획입니다. 그 세부사항도 이곳에 곧 게시하도록 하겠습니다.

노트에서 틀린 부분을 발견하시면 관련 섹션의 리포트나 각 리포트의 마지막 부분에 댓글로 알려주시기 바랍니다

이 곳에서 동영상 강의를 확인하실 수 있습니다.

이곳에서 실제 수업을 수강하는 학생들이 작성한 공식 강의 노트를 확인하실 수 있습니다. 실제 강의 웹사이트가 아니라 강의 슬라이드 중 하나에 링크되어 있습니다. 슬라이드를 검토하다 이 자료를 발견하게 되었는데, 제 생각에는 이 노트에서도 몇 가지 주제가 누락된 것 같습니다. 아마도 이런 이유 때문에 강의 웹사이트에 이 노트를 링크 시키지 않은 것 같습니다. 하지만 이러한 노트를 작성하는 것은 여전히 즐거웠고, 각 강의를 두 번씩 봐야 했으며, 이제 저는 훨씬 더 잘 이해하게 되었습니다. 여러분들도 이 자료를 유용하게 사용하시길 바랍니다.

단원

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks

주제

Node Degree, Complete Graph, Bipartite Graph, Adjacency Matrix, Connected Graph, Disconnected Graph, Directed Graph, Degree Distribution, Path, Diameter, Geodesic Distance, Diameter, Average Path Length, Clustering Coefficient, MSN Messenger Network, Erdos-Renyi Random Graph Model, $G_{np}$ Random Model, Small-World Model, Kronecker Graphs, Kronecker Product, Stochastic Kronecker Graphs, Subgraphs, Motifs, Graphlets, Automorphism Orbits, Exact Subgraph Enumeration, Roles, RolX, Communities, Granovetter, Zachary's Karate Club, Modularity, Louvian Algorithm, BigCLAM, Affiliation Graph Model(AGM), Spectral Clustering, Graph Partitioning Criterion, Conductance, Spectral Graph Theory, d-regular Graph, Degree Matrix, Laplacian Matrix, ${\lambda }_2$ as an Optimization problem, Optimal Cut, Rayleigh Theorem, Spectral Partitioning Algorithm, k-Way spectral clustering, Motif Based Spectral Clustering, Node Classification, Homophily, Collective Classifiers, Local Classifier, Relational Classifier, Collective Inference, Probabilistic Relational Classifier, Iterative Classifiers, REV2, Loopy Belief Propagation, Graph Representation Learning, Embedding Nodes, Shallow Encoding, Random Walk Embeddings, Node2Vec, Biased Walks, TransE, Embedding Entire Graphs, Anonymous Walk Embeddings, Graph Neural Networks, Computational Graph, Graph Convolutional Network(GCN), GraphSAGE, Graph Attention Networks(GAT), Tips to train GNN, GCN on Zachary, GNN Comparisons on Cora Citation Network, Graph Generation, GraphRNN, PageRank, Random Walk with Restarts, Personalized PageRank, Cascades, Decision Based Diffusion Models, Reproductive Number $R_0$, Epidemic Models, SIR Model, SIS Model, SEIZ Model, Independent Cascade Model, Exposure Curve, Influence Maximization, Linear Threshold Model, Independent Cascade Model, Greedy Hill Climbing, Submodular Functions, Sketch-based Algorithms, Outbreaks Detection, CELF, Lazy Hill Climbing, Data Dependent Bound, Macroscopic Evolution, Densification power law, Forest Fire Model, Temporal Networks, Microscopic Evolution, Temporal PageRank, Knowledge Graphs, Freebase Knowledge Graph, TransE in Knowledge Graphs, TransR in Knowledge Graphs, Path Queries, Conjunctive Queries, Box Embeddings, Query2Box, EPFO Queries, GNN Limitations, Graph Structure Vulnerability, Injective, Graph Isomorphism Network(GIN), Weisfeiler-Lehman Graph Isomorphism Test, Noise Vulnerability in Graphs, Nettak, PinSAGE, Decagon, Goal Directed Graph Generation(GCPN)