Graph
06. Structural properties of Network
06. Structural properties of Network
2022.06.04강의의 앞 부분에서 average node degree (degree distribution), average clustering , average path length 등의 네트워크의 global perperties 에 대해 배웠고, 이어서 node centrality , pagerank 등의 vertex 에 대한 local properties 또한 공부하였다. 6강에서는 Pairwise properties 에 대해 다룬다. - node equivalence - node similarity - correlation between pairs of vertices (node values) * Structural equivalence 두 노드의 in-out neighbors가 모두 같다면 즉 ,정확히 같은 ..
05. Node centrality rating on Networks
05. Node centrality rating on Networks
2022.06.01그래프에서 어떤 노드가 가장 중요한 노드인지 에 대한 지표를 node centrality 라고 할 수 있다. 하지만 단순히 degree가 가장 높은 노드가 중요할 수도 있고, 노드를 거쳐서 최단거리가 되는 노드가 중요할 수도 있어 결국 어떤 속성의 네트워크인지와 어떤 것을 중점으로 볼 지에 따라 다르다. 대표적인 node centrality 에 대해서 알아보자. *closeness centrality how close an actor to all the other actors in network 특정 노드에서 다른 모든 노드에 도달하는데 얼마나 많은 단계를 거치는지를 나타내는 지표, closeness가 높다는 것은 네트워크의 중심성이 낮다. 노드의 접근성에 따라서 중요도 부과. * Betweeness c..
[CS224W] 7. Graph Neural Networks 2: Design Space
[CS224W] 7. Graph Neural Networks 2: Design Space
2022.02.26GNN 에서 computation graph, 신경망의 구조를 결정하는 것은 node's neighborhood 이다. 그림은 GraphSAGE 논문에서 가져온것으로 depth k 에 따라의 message passing임. 왼쪽의 그래프가 input graph 라고 해보자. A가 구하려는 타겟 노드라면 A는 그와 연결된 주변 이웃 노드의 임베딩을 aggregate 하여 결정되는데, 주변 이웃들도 그들의 이웃, A로부터 1-hop 이상인 노드로 부터 영향을 받는다. 결국 모든 노드들이 레이어마다 각자의 representation 을 가지고 있고 레이어가 깊어지면서 update된다는 컨셉이다. k=0 일 때는 node feature 를 사용한다. 결국 GCN,GraphSAGE,GAT 건 간에 Layer 1에..
Graph Convolutional Network (GCN)
Graph Convolutional Network (GCN)
2022.02.22오늘은 ICLR 2017 에서 나온 논문인 semi-supervised classification with graph convolutional networks 를 읽고 GCN 에 대해서 리뷰하려고 합니다. 그래프를 공부하면서 읽는 첫 논문이라 개인적으로 어려웠습니다. Abstract 를 읽어보면 논문에서 소개하는 convolutional 모델은 spectral graph convolution의 localized first-order approximation이라고 합니다. 그래프를 통해서 label information이 smoothed 가 된다고 하고 이는 정규화된 Laplacian 행렬을 이용하기 때문에 가능하다고 하는데 전혀 이해가 안갔습니다. 라벨이 있는 노드에 대한 loss와 라벨이 없는 노드에 ..
[CS224W] 5. Label Propagation for Node Classification
[CS224W] 5. Label Propagation for Node Classification
2022.02.08몇 개의 노드에 대한 라벨을 가진 네트워크가 있을 때, 정보가 없는 노드들을 어떻게 처리할 것인가? 위 그래프처럼 초록과 빨강이란 node label 이 그래프의 일부 노드에만 주어져 있을 때 오른쪽처럼 어떤식으로 node classification을 할 수 있을까? 일부 정보만 주어져 있기 때문에 semi-supervised node classification 문제라고 볼 수 있다. Message passing message passing이란 것을 이용해 문제를 해결하고자 하는데 노드들의 correlation을 이용하자는 게 아이디어이다. 간단히 말해 변수간의 상관관계처럼 노드 간의 similarity가 있다면 correlated라고 것이고 이는 곧 노드 간의 connection을 보자는 것이다. 앞서..
[CS224W] 3. Node embedding
[CS224W] 3. Node embedding
2022.02.021. Node embedding 기존의 머신러닝 모델에서 그래프를 이용하는 방법은 다음과 같다. input으로 그래프가 주어졌을 때, feature engineering을 통해 structured features를 만들어 ml 알고리즘으로 이를 학습한다. 하지만 Graph Representation learning 은 피쳐 엔지니어링을 자동화하기때문에 특정 task 마다 반복되는 작업을 할 필요가 없다. graph 를 잘 표현하는 것은 결국 그래프의 feature를 representation 하는 것이다. 노드 임베딩이란 그래프의 node u를 d차원의 실수 벡터로 표현하는 것이다. 노드를 벡터로 표현할 수 있게 되면, 노드 간의 similarity를 구할 수 있으며 네트워크(graph) 간의 유사성도 ..