GraphMining

GCN, GraphSAGE, GAT 설명

Graph Convolutional Network(GCN) 가장 기초적인 GNN 이후 발전 모델 중 하나로 GNN과 비교해서 공식을 살펴보면 그 차이를 명확하게 알 수 있다. GCN의 달라진 점은 Aggregation에 있는데 기본 GNN에서는 단순히 neighbor의 평균을 내었다면 GCN에서는 자신 Node와 Neighbor들의 합을 자신 Node의 Neighbor 개수와 Neighbor Node의 Neighor 개수로 곱한 것의 Root 값으로 나눈다. 이건 단순한 GCN에 대한 설명이고, GCN도 Spectral Graph Convolution인지 Spatial Convolution인지 부터 다양한 접근이 가능하다. 참조: https://arxiv.org/abs/1609.02907 Semi-Sup..

Basic GNN 설명

GNN의 핵심은 Neighborhood Aggregation으로 이야기할 수 있다. 즉, Node의 neighborhood를 Neural Network를 이용하여 Aggregation함으로 Neural Network를 학습하는 것이다. 아래 왼쪽 Graph에서는 A부터 F까지 6개의 Node가 있다. 이를 Node A와 Node A의 neighborhood 관계로 표현하면 아래 오른쪽과 같이 표현할 수 있다. Node들은 각 Layer에서 Embedding을 갖게되고 가장 아래 Layer인 Layer0에서는 input feature를 사용하게된다. GNN의 특징 중의 하나는 각 Layer 마다 input의 개수가 다르다는 것이다. 위의 그림은 Node의 A를 기준으로하여 그렸지만 Node B가된다면 In..

K-Core & Katz index

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다. K-Core Idea : nodes with degree less than k are removed until all remaining nodes in the network have at least k degree (k보다 작은 차수를 가진 노드는 네트워크의 모든 나머지 노드가 최소한 k 차수를 가질 때까지 제거) k-core : subgraph where all nodes have 2 degree of at leat k (모든 노드가 최소 k의 2차수를 갖는 부분 그래프) node coreness : a measure that quantifies the participation of a node to t..

Kronecker Graph Model

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다. Kronecker Graph Model Self-similarity를 통한 recursive model => Power law, real-world graph structure hyperparameter에 민감하지 않고 stably Graph를 생성 Recursive graph Adjacency matrix간의 Kronecker Product을 통해 Graph 생성 \(G_k\)가 \(G_1\)의 k times의 Kronecker product라고 할 때 \(G_k\)는 \(N_1^k\) node와 \(E_1^k\) edges를 갖게 된다. 즉, Constant diameter가 되게 된다. 이를 해결하기..

Community Guided Attachment & Forest Fire Model

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다. Community Guided Attachment Model 마지막 leaf node들이 어느 Community에 속해있는지를 토대로 link probability로 edge를 생성 Assume Community structure : Group 안에는 friendship이 높고, Group 밖에는 friendship이 낮음 Self Similarity : Perfect balanced Tree Structure Linking probability(Difficulty Function) $$ f(h) = c^{-h} $$ \(h\) : tree distance of two nodes \(c\) : Diffic..

Basic Models

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다. We have now seen that densification power laws and shrinking effective diameters are properties that hold across a range of diverse networks. "How do we build models of network generations of evolution?" Lattice Networks Lattice networks have High clustering coefficients, Large diameter Small-world Models Small-world Model have High cluster..

Structural properties

KAIST AI 대학원 신기정 교수님의 수업인 데이터마이닝 및 소셜 네트워크 분석 수업 필기입니다. Three parts/goals Statistical properties of large networks Models that help understand these properties Predict behavior of networked systems based on measured srtructural properties and local rules governing individual nodes Random Graph: Null Model What is the simplest way to generate a graph? Random graph model \(G(n,p)\) (= Erdos-Renyi ..

Random Networks

Network science는 실제 네트워크 속성을 재현하는 모델을 구축하는 것을 목표로 합니다. 우리가 접하는 대부분의 네트워크들은 규칙성이나 예측 가능한 구조가 아닙니다. 처음에는 무작위로 회전된 것처럼 보입니다. Random network theory는 truly random 한 특성을 보이는 네트워크를 구성하고 특성화함으로써 명백한 무작위성을 수용하는 것입니다. Random network theory embraces this apparent randomness by constructing and characterizing networks that are truly random. 실제 시스템의 복잡성을 재현할 수 있도록 하기 위해서는 노드 사이에 링크를 배치할 위치를 결정해야합니다. 이와 관련하여 ..