[CS224W] Lecture 1 : Course Introduction and Structure of Graphs

Stanford의 강의 CS224W(2018 Fall)를 정리한 포스트입니다.

코스 전체에서 다루는 주제입니다.

Topic # Lectures
Course Introduction and Structure of Graphs 1
Measuring Networks, and Random Graph Model 2
Link Analysis: PageRank 3
Network Construction, Inference, and Deconvolution 4
Motifs and Graphlets 5
Community Structure in Networks 6
Community Detection: Spectral Clustering 7
Link Prediction 8
Graph Representation Learning 9
Network Effects and Cascading Behavior 10-11
Influence Maximization & Outbreak Detection 12-13
Power-laws and Network Robustness 14
Network Centrality 15
Message Passing and Node Classification 16
Network Evolution 17
Knowledge Graphs and Metapaths 18
Graph Convolutional Networks 19


Why Networks?

Networks(Graphs)는 복잡한 시스템을 표현하는 일반적인 언어다. 여러 요소들과 그 관계를 나타낼 수 있기 때문이다. 인간들의 Society, 전자기기들간 연결된 통신 시스템, knowledge graph 라고도 불리우는 정보와 지식, 생물학적인 genes/proteins과 그들의 관계 등등 다양한 형태의 데이터가 network형태로 존재한다. 따라서 네트워크 기술들을 자신의 분야가 아닌 타 분야에도 얼마든지 적용할 수 있다. (배워두면 다양한 분야를 연구할 수 있다.) CS224W-01-01

Networks and Applications

Network를 분석하여 할수있는 task는 아래와같은 큰 갈래로 구분된다.

  • Predict the type/color of a given node
    • Node classification : 각각의 노드가 어떤 타입인지 예측하는 것이다. 예를 들면 citation이 link(edge)이고 각각 논문이 node인 graph 에서 해당 node(논문) 가 어떤 종류의 논문인지 예측하는 것이 이에 해당한다.
  • Predict whether two nodes are linked
    • Link prediction : 위와는 반대로 link(edge)를 예측하는 것이다. 예를 들면, 개개인이 node이고, 친구관계가 edge(link)인 페이스북 graph 에서, 친구추천을 하는 것이 이에 해당한다.
  • Identify densely linked clusters of nodes
    • Community detection : Image로치면 segmentation에 해당하는데, 각각의 노드를 클러스터(community)로 묶는 것이다.
  • Measure similarity of two nodes/networks
    • Network similarity : 두 network가 얼마나 유사한지 측정하는 것이다. 예를 들면 두 가지 뇌의 발현상태를 비교하는 등의 task가 이에 해당한다.

아래는 Network 와 그에 따른 Applications의 예시들이다.

Social Network

CS224W-01-02

Facebook social graph(왼쪽)와 친구관계에서 그룹(social circle) detection (오른쪽).

Information, Knowledge Graph

CS224W-01-03

Graph 의 종류들(왼쪽)과 application(오른쪽). 오른쪽 상단은 Wikipedia 문서중 악의적으로 작성된 문서와 그렇지 않은 문서를 분류하는 것이다. 오른쪽 하단은 content recommendation을 link(edge) prediction 문제로 치환하여 해결하는 application이다.

Online Media

CS224W-01-04

Online media들을 network로 나타내고 분석한 application. 좌측 상단은 정치색에 따른 blog들의 연결성을 나타낸 것이다. 좌측 하단은 Twitter 계정들의 정치색에 따른 연결성을 나타낸 것인데, 정치색에 따라 강하게 분류되면 이 그림의 왼쪽처럼, 그렇지 않으면 오른쪽 처럼 나타난다. 우측 상단은 virality를 예측하는 것이다. 싸이의 강남스타일처럼 급속도로 소셜네트워크를 타고타고 퍼지는 영상매체에 대한 분석을 하는 것이다. 우측 하단도 약간 유사한데, LinkedIn 유저들이 다른 사람을 가입하도록 초대하는 양상을 분석한 것이다.

Biology

CS224W-01-05

Biology graph(왼쪽)와 protein의 역할 분류(오른쪽).

About CS224W

이 수업에서 다루고자 하는 내용이다.

  • Reasoning about Networks (network에 대한 공부를 통해 얻고자 하는 것은 무엇인가?)
    • Network 데이터의 패턴과 통계적인 특성
    • 예측 모델과 알고리즘 설계
  • Mining and Learning with Graphs (어떻게 Graph로부터 유의미한 결과를 뽑아낼 것인가?)
    • 실험적으로.
    • 수학적인 모델링으로. (그래프 이론 및 통계학적 모델링)
    • 알고리즘으로.
  • Networks: Structure & Process (networks에서 어떠한 내용을 공부할 것인가?)
    • Structure and evolution: network의 구조는 어떤 것인지.
    • Processed ans dynamics: Network는 “skeleton”을 통해 정보를 퍼뜨리는데, 이러한 정보가 어떻게 퍼지는지.

Starter Topic: Structure of Graphs

CS224W-01-06 Network는 관계성을 가진 object pair들의 모음이다. 각각의 요소로는 Object, Interaction이 있고, 이들로 이루어진 System이 있다. Network, node, link는 주로 실제 시스템 (Web, Social network, Metabolic network)을 언급할때 사용되는 용어다. Graph, vertex, edge는 수학적인 표현이다(Web graph, Social graph). 그러나 혼용해서 사용하기도 한다.

How to build a graph?

  • Node는 무엇인가?
  • Edge는 무엇인가? Graph 를 어떻게 정의하는지에 따라 그래프를 분석하는 능력이 달라진다. 각각을 정의하는 것은 domain knowledge에 따라 결정되며, 한가지 방법으로만 표현되는 경우도 있지만, domain에 따라서는 같은 대상을 여러 종류의 그래프로 표현할 수도 있다.

Choice of Network Representation

Undirected vs. Directed Graphs

CS224W-01-07 Graph는 Undirected graphDirected graph가 있다. 관계가 방향성이 없다면 (페이스북 친구) undirected link로 표현되고, 방향성이 있다면 (페이스북 팔로우) directed link로 표현된다.

Node Degrees

CS224W-01-08 Degree란, 노드에 연결되어있는 edge의 수다. Degree의 평균은 $\bar{k}, \left\langle k \right\rangle$ 로 표기한다. 예를 들어 Undirected graph에서 빨간 노드 A에 edge가 4개 달려있으므로 degree $k_A = 4$ 이며 전체 graph degree의 평균은 $\bar{k} = \left\langle k \right\rangle = \frac{1}{N} \underset{i=1}{\overset{N}{\sum}}k_i = \frac{2E}{N}$ 이다. Directed graph에서는 edge의 방향성이 있기 때문에, 방향성에 따라 들어오는 edge는 in-degree, 나가는 edge는 out-degree로 나누어 표기한다. Directed graph 에서 빨간 노드 C의 in-degree는 $k_C^{in}=2$이고, out-degree는 $k_C^{out}=1$ 이며 전체 graph degree의 평균은 $\bar{k} = \left\langle k \right\rangle = \frac{E}{N}$ 이다. (total) degree는 둘의 합하여 $k_C=3$으로 표기한다. 이때, 나가는 edge만 있는 노드$(k^{in}=0)$를 source node라고 하며, 들어오는 edge만 있는 노드$(k^{out} = 0)$를 sink node라고 한다.

Complete Graph

CS224W-01-09 가능한 모든 edge를 가진 graph를 complet graph (fully connected graph)라고 한다. 이 경우 평균 degree는 $\bar{k} = \left\langle k \right\rangle =N-1$이다.

Directedness & Avg.Degree in real networks

CS224W-01-10 실제 network들의 directedness와 평균 degree를 나타낸 도표다. 전체 graph size에 비해 평균 degree가 낮을 수록 adjacency 가 sparse하며, 높을 수록 dense하다고 한다.

Bipartite Graph

CS224W-01-11 Bipartite graph는 독특한 형태의 graph다. 마치 두 partition이 있는 것 처럼, U와 V 사이에 edge는 있지만, U끼리 또는 V끼리 edge는 없는 graph다. 만약 U를 user, V를 상품으로 표현할 때 user가 상품을 구매했을 때를 edge로 두면 bipartite graph가 된다. 공통된 V를 가진 U끼리 edge를 넣은 U의 graph를 Projection U로 표현한다 (반대의 경우는 Projection V).

CS224W-01-12 하나의 예가 식재료와 맛을 나타낸 graph다. A는 식재료와 맛끼리 연결한 bipartite graph고, B는 이를 (Projection) 이용하여 같은 맛을 공유하는 식재료끼리 연결지은 flavor graph다.

Representing Graphs: Adjacency Matrix

CS224W-01-13 Adjacency matrix는 각각 노드쌍의 edge정보를 나타낸 matrix다. undirected graph는 symmetric adjacency matrix로 표현되고, directed graph는 symmetric하지 않게 표현된다. 맨 아래는 adjacency matrix를 시각화 한 것인데, 점은 edge가 있는 것이고 빈 부분은 edge가 없는 것이다. 매우 sparse함을 알 수 있다.

CS224W-01-14 Adjacency matrix가 sparse하기 때문에 0으로 채워진 matrix대신 위와 같이 표현하는데, 왼쪽은 edge list이고, 오른쪽은 directed graph에서의 adjacency list다 (나가는 방향의 edge만 표기).

Edge Attributes

Edge의 특성으로 여러가지를 넣을 수 있다.

  • Weight (communication의 빈도 등)
  • Ranking (중요도 또는 유저의 상품 평가)
  • Type (어떤 종류의 relation인지. (친구인지, 직장동료인지 등))
  • Sign (relation이 positive 한지, negative한지. (Trust vs. Distrust))
  • Properties depending on the structure of the rest of the graph (함께 아는 친구가 몇인지 등)

아래는 edge atrributes에 따른 다양한 graph의 예시다. CS224W-01-15

Connectivity of Undirected Graphs

CS224W-01-16 Undirected graph가 분리된 component로 이루어져 있다면, disconnected graph라고 한다. 이 때 disconnected graph의 adjacency matrix는 block diagonal matrix의 형태로 나타난다. 지웠을 때 graph 를 diconnected로 만드는 edge를 Bridge edge, node는 Articulation node 라고 부른다.

Connectivity of Directed Graphs

CS224W-01-17 Directed graph는 connected graph가 두가지로 다시한번 나뉜다. 일단 edge의 방향성과 상관없이 connected graph면 Weakly connected directed graph이고, 각각의 노드가 다른 모든 노드와 path를 갖고 있으면(모든 노드에 대해 A-B path와 B-A path가 둘다 존재하면), Strongly connected directed graph이다. 보통은 모든 node가 strongly connected인 경우보다는 일부 노드들만 그러한 경우가 많은데, 이 노드들의 집합을 Strongly connected components(SCCs)라고 한다.

Network Representations

지금까지 배운 표현대로 각각의 network를 표현해보면, 아래와 같다.

  • Email network » directed multigraph with self-edges
  • Facebook friendships » undirected, unweighted
  • Citation networks » unweighted, directed, acyclic
  • Collaboration networks » undirected multigraph or weighted graph
  • Mobile phone calls » directed, (weighted?) multigraph
  • Protein Interactions » undirected, unweighted with self-interactions