Contents

0. Intro
1. Limitations of conventional GNNs in capturing graph structure
2. Vulnerability of GNNs to noise in graph data
3. Open questions & Future directions

0. Intro

핵심 아이디어 : 로컬 네트워크 환경을 기반으로 노드 임베딩 생성 neighbor aggregation의 아이디어를 기반으로 노드는 신경망을 사용하여 neighbor로부터 정보를 수집합니다. 다양한 신경망 선택에 따라 다양한 모델 변형이 제안되며 모델에 따라 박스 안에 들어가는 내용물이 달라집니다.

각 노드는 이웃에 따라 computation graph를 정의하고 neighbor aggregation을 통해 노드 임베딩을 구합니다. node representation을 구한 후 해당 graph의 노드들을 더하거나 평균내는 방식(Pooling)으로 하나의 graph representation을 구하게 됩니다.

위의 그림과 같이 GNN을 활용하여 많은 SOTA성능을 내기도 했지만 GNN에는 한계가 존재하고 이번 강의에서 그 한계에 대해 배우게 됩니다.

GNN에는 크게 2가지 한계점이 존재합니다.

1. 기존의 GNN으로는 일부 간단한 그래프 구조를 잘 구분하지 못합니다.
2. GNN은 그래프 데이터의 노이즈(node feature의 변화, edge의 추가/삭제)에 robust하지 못합니다.

1. Limitations of conventional GNNs in capturing graph structure

Graph Isomorphism

GNN은 위 그림의 두 그래프를 잘 구분해 내지 못할 수 있습니다. 이러한 문제를 완벽하게 해결할 수 있는 다항식 알고리즘은 없기 때문에 GNN이 완벽하게 구분하지 못할 수 있으며 이를 해결하기 위해선 그래프의 설계부터 신경써야 합니다.

왼쪽의 그림을 보면 4개의 노드는 다 다른 노드지만 computation graph를 보면 모두 동일하며 각 노드가 다르다는것을 GNN에 이해시키는 것은 불가능합니다. 반면 오른쪽의 그래프를 보면 노드간의 차이가 존재합니다.

graph representation을 위해 neighbor aggregation을 통한 node representation을 하면 두 개의 다른 노드를 가진 그래프가 생깁니다. 하지만 이러한 aggregating 과정에서 mean pooling이나 max pooling을 사용하게 되면 두 그래프는 같은 결과값이 나오게 됩니다. 이를 해결하기 위해 injective function을 aggregate function로 사용합니다.

injectivity

하나의 output에 하나의 element를 mapping하는 것으로, 이를 통해 node의 subtree가 다르면 node representation 또한 달라지게 됩니다. 여기서 각 트리의 층마다 injective function을 적용해 줍니다.

Neighbor aggregation은 multi-set로 이루어지는데, 여기서 multi-set는 set에서 중복요소를 추가한 것입니다. 이를 활용함으로써 neighbor aggregation을 더욱 잘 표현할 수 있습니다.

GCN과 GraphSAGE에는 multi-set를 적용하더라도 injective하지 않습니다. GCN에서 mean pooling을 하는 경우 노란색 1개, 파란색 1개인 경우와 2개,2개인 경우 모드 mean을 한다면 0.5 * 0.5가 되어 같은 결과가 나옵니다. GraphSAGE에서는 max값만 뽑기 때문의 각 노드의 개수는 중요하지 않습니다.

injective mult-set function을 표현하면 위 그림과 같습니다.

Graph Ismorphism Network (GIN)

위의 예시를 GCN과 GraphSAGE는 구별 할 수 없지만 GIN의 Sum pooling을 사용하면 구분할 수 있습니다.

Weisfeiler-Lehman (WL) Graph Isomorphism Test와 마찬가지로 GIN은 동형 그래프를 구별하는 좋은 능력을 가지고 있는데 그 방법은 아래와 같습니다.

먼저 root로부터 subtree를 하나씩 내립니다. 이때, node간의 다름이 확인되면 거기서 멈추고 같은 개수의 subtree를 가지고 있다면 이를 계속 진행해 시작 노드의 색을 구분합니다.

이후 각 그래프에서 같은 색의 노드 개수를 세어주고 이를 바탕으로 그래프를 이루는 노드의 개수를 구분합니다. 그 결과가 동일하다면, 두 그래프는 isomorphism 하다고 할 수 있습니다.

이렇게 GIN은 좋은 성능을 보여주지만, 위 그림과 같이 모든 노드가 같은 수의 subtree를 가지는 경우에는 WL로 구분할 수 없습니다.

다른 모델들과 비교해 좋은 성능을 보여줍니다.

node feature가 존재하는 경우에는 성능의 차이가 크지 않다고 합니다.

Summary of the first part

1. 기존의 GNN은 non-injective neighbor aggregation을 사용하기 때문에 구별하는 능력이 떨어짐

2. GIN은 injective neighbor aggregation을 사용하기 때문에 성능은 WL graph isomorphism test만큼 좋음

3. GIN은 graph classification에서 SOTA의 성능을 보임

2. Vulnerability of GNNs to noise in graph data

DNN은 데이터 교란에 취약합니다. 눈에 보이지 않는 변화만 주더라도 예측 결과에 변화를 주며 이는 이미지 뿐만 아니라 검색엔진, 추천시스템, sns 등 여러 분야에서 쉽게 발생합니다.

위 그림은 GCN을 활용한 semi-supervised node classification에서 비어있는 label을 채워 넣는 문제입니다.

실생활에서 attack possibilities 하는 방법에는 두가지가 있습니다.

1. Direct attack

• target node를 직접적으로 변경하는 방법으로, target의 feature를 변경한 뒤 target에 대한 연결을 해줍니다. 이는 target으로부터의 연결을 제거함으로써 해결할 수 있습니다.

2. Indirect attack

• target을 follow한 후 attacker의 feature를 변경합니다. 이후 attacker의 연결을 늘려 spam farm을 만들어줍니다. 이는 attacker로부터의 연결을 제거함으로써 해결 가능합니다.

Mathematical Formulation of Attack

이 공식은 타겟노드에 대한 예측된 라벨의 변화를 최대화하는 수정된 그래프를 찾는것이 목적입니다.이 공식에는 두 가지 주요 공격 유형이 있는데, adjacency matrix A를 변경하는 방법과 node feature X를 변경하는 방법이 있습니다.

타겟노드 v가 c로 예측될 loglikelihood을 높이는 것과 변경되기 전의 c_old로 예측되는 대상 노드 v의 loglikelihood을 줄여줍니다. 공격 전에 노드 v는 c_old에 속합니다.공격 후에는 c_old에 속하는 노드 v의 확률이 낮아지고 동시에 c에 속하는 노드 v의 확률이 증가합니다.

즉, 공격 전후에 서로 다른 범주에 속하는 노드 v의 확률이 변경되어 공격이 성공합니다.

여기서 GCN은 수정 된 그래프에서 훈련 된 후 대상 노드의 레이블을 예측하는 데 사용됩니다.

이렇게 변경된 그래프는 원래의 그래프에 가까워야 합니다.

Tractable Optimization

최적의 해를 정확히 구하는 것은 불가능한데, 그 이유로는 두 가지가 있습니다.

1. Graph modification은 이산적이기 때문에 최적화를 위한 gradient descent를 사용할 수 없음
2. 과정의 일부인 GCN을 다시 학습시키는데 비용이 많이 듬

이를 해결하고 근사 솔루션을 얻기 위해 그래프의 수정을 단계적으로 해가는 방법과 ReLU를 제거하여 GCN을 단순화 하는 방법등 몇가지 간편 추론(heuristics)이 제안되었습니다.

Summary of the second part

GNN은 robust하지 못하고 공격에 취약합니다.

3. Open questions & Future directions

향후 화학과 생물학 등 과학 도메인에 GNN을 적용하기 위해 연구할 예정입니다.

현재 직면한 과제로는

1. 라벨링된 데이터의 부족

• 라벨링에는 비싼 실험이 필요하고 라벨링된 데이터 부족으로 인해 모델이 오버피팅 됨

2. 실제 테스트 케이스와 학습한 것이 많이 달라 분포 이탈 예측이 발생함(일반적으로 성능이 좋지 않음)

과학 분야에서의 pre-training GNN이 연구되고 있으며 공격이 있으면 방어가 있듯 GNN을 robust하게 만들기 위해 노력하고 있음

Contents

1. Reasoning over Knowledge Graphs
2. Path Queries
3. Conjunctive queries
4. Query2Box

Reasoning over Knowledge Graphs

Knowledge Graphs

• Knowledge 즉, 지식을 그래프의 형태로 구성한 것
  • node = entity (labeled with type)
  • edge = relationship

KG Representation

• KG에서의 edge는 triples(h, r, t)로 임베딩 할 수 있다

  • head(h): 출발노드(앵커 노드)
  • relation(r): edge, 관계
  • tail(t): 도착 노드

• 우리의 KG를 임의의 차원으로 임베딩 시키고 실제로 연결되어있는 true triple(h, r, t)가 주어졌다고 해보자

• Ex) h(기생충)의 r(감독) t(봉준호)

  • Q1) 기생충의 감독은 봉준호. 즉, h에서 r만큼 이동한 위치가 t의 위치와 똑같아야 겠지?
  • Q2) 그러면 (h, r)을 어떻게 임베딩 시킬까?
  • Q3) 두 노드 간의 거리는 뭘로 정의하지?
  
  

Relation Patterns

Relation의 특성 3가지를 살펴보자

TransE

앞서 Graph representation에서 배웠던 TransE를 써먹을 수 있을 것 같다.

• TransE는 h, r, t를 임의의 차원에 매핑하는 임베딩 방법이다.
• h에서 r만큼 이동한 위치가 t의 위치가 같을 수록 좋다!

TransE Training

TransE는 어떻게 학습할까?

1. True triple과 Corrputed triple(가짜) 2가지를 뽑고 2가지 값과 임의의 마진값의 합을 maximize한다
   • True tiple의 거리가 가까울 수록 좋다
   • Corrupted tirple의 거리가 멀 수록 좋다

Link Prediction using TransE

• TransE는 Link prediction에 써먹을 수 있다

Composition in TransE

• KG의 특성인 Composition을 만족한다

Limitations

• 그러나 TransE는 2가지의 KG 특성을 만족시키지 못한다.

Symmetric relations

• 만약 r이 0이라면 symmetric 특성에 따라 h와 t가 같아야하지만, 실제로 매핑된 TransE값을 보면 h와 t는 서로 다른 벡터이다

  N-ary relations

• 일대다, 다대일, 다대다 관계를 만들 수 없다
• 만약 (h, r)의 결과인 t가 많은 경우
  • t1 = h+r
  • t2 = h+r -> t1과 t2는 같아야한다
  • 그러나 t1 != t2
    

TransR

• TransE와 동일하게 entity vector를 임의의 d차원을 매핑한 후 각 relation을 vector r로써 다른 k차원에 매핑한다.
• 임베딩 매트릭스 ${M_r}$의 shpae은 (k, d)

Symmetric relation in TransR

• TransR은 symmetric 특성을 보존할 수 있다

  N-ary relation in TransR

• 일대다, 다대일, 다대다 관계도 지킬 수 있다
• d차원에서 다른 노드더라도 r을 통해 k차원으로 매핑시킨다면 같은 값으로 임베딩 될 수 있다

Limitation

• 그러나 TransE와 반대로 composition 관계를 보전할 수 없다
• 왜냐하면 TransR에서 모든 r은 각자 다른 space에 매핑하는 역할이기 때문!

Translation-Based Embedding

Path Queries

Query type on KG

• 만약 multi-hop reasoing을 진행한다면 어떻게 될까?
• 복잡한 질의를 불완전하고 거대한 KG가 다룰 수 있을까?

One-hop queries

• 간단한 one-hop 질의는 link prediction으로 생각할 수 있다

Path queries

• one-hop을 일반화하여 여러 단계로 나누어 path를 구성하여 질의를 진행할 수 있다

Traversing KG

• KG에서 multi-hop을 진행해본다고 해보자

• IDEA 1) one-hop처럼 link prediction으로 KG를 횡단할 수 있지 않을까?

  • NO! KG는 dense graph이기 때문에 매 스텝마다 모든 노드와의 link 확률을 구한다면 시간복잡도는 path의 길이가 n이라면 $O(|V|^n)$이 걸린다!

• IDEA 2) query를 임베딩하자

• TransE를 multi-hop reasoning에 사용할 수 있을 것 같다 -> Compoistion을 만족하니까!

• score function은 ||q - v||로 바로 구할 수 있으니까 훨씬 빠르다

Traversing KG in vector space

• TransE를 활용한 multi-hop 예시를 보자

Conjunctive queries

• 더 복잡한 질의는 어떻게 다룰까?
• 만약 multiple ancohor node에서 출발하면?

• 과정을 살펴보자
  1. anchor node 각각 출발하여 두 relation이 겹치는 node를 찾는다
  2. multi-hop을 진행한다

Traversing KG in vector space

• Computation grpah와 embedding space를 동시에 비교해보자

• Q) 실제 임베딩 space에서 점 하나로 딱 떨어지지 않는데 뭐가 정확한 intersection인가?

  • A) 아몰랑 Neural Net이 해결해주실거야

Neural intersection operator

• 여러 query를 받아서 intersection을 찾아야 한다
• 전지전능 neural intersection operator $J$를 모델링하자
  • Input: query embedding set $(q1, ..., q_m)$
  • Output: intersection embedding $q$

• 그러면 우린 성공적으로 intersection을 찾을 수 있다

Training

• entity embedding $v$와 query embedding $q$가 주어졌을 때

• score function = $||q - v||$

• parameters

  • entity embedding: $d|V|$
  • relation embedding: $d|R|$
  • intersection operator φ, β: 그래프 사이즈에 영향받지 않음

• TransE하고 똑같이 학습하면 됨

  1. query q, answer v, negative sample v'를 샘플링한다
  2. q를 임베딩한다
  3. v와 v' score를 구한다
  4. loss 최적화 한다

• Evaluation

  1. test query q를 임베딩한다
  2. 모든 triple v에 대하여 score를 구한다
  3. ditance rank를 구하여 prediction한다

• Limitations

  • 단순히 intersection vector 하나 구하는 것은 직관적이지 않음
  • 정답이 될 수 있는 후보군을 추릴 수 없을까?
  • 기하학적으로 더 설득력있는 답을 내놓고싶은데...

Query2Box

Box Embeddings

• query를 box로 임베딩하자
• 기존 intersection vector를 구하는 방식에 비해 더 직관적이다!

Embed with Box

• parameters
  • entity embedding: 크기가 0인 box로 초기화
  • relation embedding: $2d|R|$ center와 offset때문에 2개씩 만든다
  • intersection operator φ, β: 그래프 사이즈에 영향받지 않음
    • input으로 box를 받아서 output으로 box를 뱉을 예정

Projection operator

• path가 진행될 수록 box는 계속 커지며 간단히 생각해서 error에 해당되는 부분이라고 보면 된다

Embed with Box

• 기존 intersection vector를 구하는 방식과 달리 box를 임베딩하였다

• 모든 box의 교집합 부분을 intersection box로 본다

• center는 weighted average로 정한다
• new offset은 줄어든 것을 알 수 있다

• 이를 embedding space 관점에서 살펴보자
• intersection box를 구하고, 다음 매핑에서 새로운 box를 만들었다

Entity-to-Box distance

• query box $q$와 entity vecotr $v$가 주어졌을 때 distance를 구해보자
• $q$에서 시작해서 $v$까지의 L1 norm을 distance로 정의할 수 있고 알파를 조절하여 box $q$의 영향을 조절할 수 있다

Training

• loss를 minimize하는 방식으로 학습한다
• 좌항에서 true box score를 minimize하고, 우항에서 false box score를 maximize한다

Relation patterns

• 결론 Leskovec 교수가 갓이다

EPFO queries

• Existential Positive First-order (EPFO) : Conjunctive queries + disjunction
• 기존 embedding 방법으로 처리할 수 있다
• Process
  1. 모든 union이 걸린 노드마다 최종 목적지인 $v_{parent}$를 선택한다
  2. 모든 union edge를 제거한다
  3. 모든 union node를 순회하면서 $v$와 $v_{parent}$로 새로운 compuation graph를 조직한다
• 쉽게 생각해서 모든 경우의 수를 따로 나누어서 graph를 만든다고 보면 된다

Contents

1. Introduction of Network Evolution
2. Macroscopic Evolution of Networks
3. Temporal Networks
4. Microscopic Evolution of Networks
5. Mesoscopic Evolution of Networks

1. Introduction of Network Evolution

Today, we'll be talking about evolution of networks and dynamic networks and how do we model that.

networks that change their structure over time.

이번 16번 강의에서는 시간의 흐름에 따라 구조가 바뀌는 network의 진화(변화), 동적 네트워크 그리고 그러한 네트워크를 모델링하는 방법에 대해서 다룹니다.

네트워크가 진화하는 과정을 네트워크의 규모적인 관점에서 다르게 바라보게 되며, 해당 관점에서 자세하게 다룰 수 있는 것들에 초점을 마추게 됩니다. 또한 진화 혹은 변화는 항상 시간적인 요소와 관련이 있기 때문에 이번 강의에서는 temporal한 특징을 자주 고려하여 네트워크를 다루게 됩니다.

사실 거의 모든 real world(복잡계)의 네트워크는 시간이 지남에따라 link와 edge를 추가하고 제거함으로써 evolve(진화)합니다. 아주 간단한 예시로, 우리는 새로운 친구를 사귈 수도 있고 친구를 잃을 수도 있기 때문에 친구 관계라는 네트워크에서 사람들(노드)이 추가되기도 제거되기도 합니다.

그 다음으로는 네트워크가 진화하는 예시를 보여주고 있습니다. 좌상단 첫번째 강의노트에서는 과제를 하면서 학우들과의 관계 네트워크가 진화하고 있음을 보여주고 우상단 두번째 강의노트에서는 10개의 큰 산업별 네트워크의 진화 과정이라고 할 수 있습니다. 하단의 예시들도 마찬가지로 시간의 지남에 따라 변화하는 네트워크를 보여주고 있습니다.

정리하자면, 오늘 강의에서 중점적으로 다룰 내용은 여러 다른 level에서 진화하는 네트워크를 연구하는 방법입니다. 여러 다른 level이란 네트워크의 규모적인 관점에서의 진화를 바라보는 것으로 이해했습니다.

• macroscopic level(거시적인 규모): 네트워크의 전체적인 구조의 특징이 시간에 따라 어떻게 변화하는지
• meso level(inntermediate scale): 네트워크 motif와 같은 보다 작은 substructures가 생겨나고 나타는지
• micro level: 네트워크가 변함에 따라 노드의 중요성 또한 어떻게 변화하는지

강의는 macroscopic level을 시작으로 micro level, 마지막으로 meso level 순서로 다룰 예정입니다.

2. Macroscopic Evolution of Networks

macro level에서 네트워크는 어떻게 진화할까요? 그리고 네트워크의 성장/확장의 전반적인 현상은 무엇일까요? 강의에서는 해당 질문의 포인트에 있어 3가지 question을 던집니다.

• 시간이 지남에 따라 노드의 수와 엣지의 수 간의 관계는 어떻게 정의할 수 있는가?
• 네트워크 성장에 따라 네트워크의 diameter(지름)은 어떻게 변화하는가?
• 또한 네트워크의 차수의 분포는 어떻게 변화하는가?

이 3가지 포인트 질문은 네트워크의 진화의 보편적인 원칙(universal law)을 통해 확인할 수 있습니다.

t 시점의 시간에서 N개의 노드와 E개의 엣지가 있습니다. 이 때, t+1 시점 혹은 미래의 시점에서 노드의 개수가 2N개가 되었다고 가정할 수 있습니다. 그렇다면 이 때, 엣지의 개수는 어떻게 될지 생각해볼 수 있습니다.

다양한 관점에서 생각해볼 수 있지만, 강의자는 다음과 같이 말합니다. _ I actually argue that it's not clear why the number of connections should grow faster that the number of people(node)._

이는 노드의 증가는 명백하게 몇 개가 증가했는지 알 수 있지만 노드와 노드와의 관계는 어떻게 설정되는지에 따라 증가할수도 감소할수도 있기 때문에, 노드의 증가에 따라 엣지가 증가한다는 사실을 명백하게 밝힐 수는 없다고 이해했습니다. 여기서 노드의 증가에 따라 엣지가 증가한다는 것은 어떻게 보면 보통은 당연할 수밖에 없는 상황으로 이해할 수 있습니다.

어쨋든 노드의 개수가 2개가 되는 시점에서의 엣지의 개수에 대한 답변은 2배 이상이라고 합니다. 이에 대한 답변?이유?는 Densification Power Law라는 것을 따른다고 합니다.

첫번째 포인트 질문입니다.

시간이 지남에 따라 노드의 수와 엣지의 수 간의 관계는 무엇인가?

우측의 Internet 네트워크와 Citations(참고문헌 관계) 네트워크의 로그 스케일상 노드와 엣지의 2차원 관계를 볼 수 있습니다. 각 포인트는 t시점마다의 노드의 개수와 엣지의 개수의 위치이며 결론적으로 노드와 엣지의 관계는 로그 스케일상 선형 관계를 가지고 있음을 알 수 있습니다.

이 때, 기울기는 0과 2사이의 값으로 표현될 수 있는데, 1.2와 1.6의 의미는 노드의 증가보다 엣지의 증가가 보다 빠르며 차수의 평균도 증가한다는 것으로 해석할 수 있습니다. 이러한 과정이 네트워크 진화에서 empirical observation이라고 할 수 있는 네트워크가 보다 빽빽(dense)해지는 Densification Power Law를 의미합니다.

정리하자면, Densification Power Law는 엣지의 수는 노드의 수보다 빠르게 증가하며 평균 차수 또한 증가함을 말합니다. 이 때 수식으로는 다음과 같이 표현할 수 있습니다. 이 때, 로그 엣지의 수를 로그 노드의 수로 나누게 되면 constant이다 라고 말하는데, 엣지의 수가 로그의 수보다 로그 스케일상 항상 일정 배수를 유지한다고 이해했습니다. (그런데 모든 시점에서 노드와 엣지가 going in/going out 하는 개수가 달라질텐데 로그 스케일상 constant한 배수를 가지는 것이 가능한지 잘은 모르겠습니다.)

앞서 언급했듯이, densification exponent는 엣지의 수가 노드의 수보다 빠르게 증가하기 때문에 1 이상의 값을 가지며 제곱의 형태도 증가하지 않기 때문에 2보다 작은 값을 가집니다. 값이 1이면 기울기값으로 증가하는 1차식 형태를 의미하게 되면 값이 2이면 2차식 형태로 증가하는 형태가 될 것 같습니다.

두번째 포인트 질문입니다.

네트워크 성장에 따라 네트워크의 diameter(지름)은 어떻게 변화하는가?

먼저 그래프 상에서 지름, Diameter는 정점 간 거리의 최댓값을 의미합니다.

강의 1과 2에서 다뤘던 랜덤 그래프의 직경은 노드의 수 N에 따라 logarithmically하게 증가한다고 했습니다. 예를 들어, 노드의 수가 적으면 logarithmically하게 직경은 보다 작을 것이고 노드의 수가 많으면 보다 큰 직경을 가지게 될 것입니다. 그러나 항상 옳은 사실은 아니라고 밝혀졌습니다. 이는 매우 반직관적인데(왜냐하면 시간이 지나면 노드가 증가할 것이고 그림처럼 직경 또한 증가할 것으로 예상하기 때문입니다.), 직접 직경을 측정해서 plot으로 그려보게 된다면 시간에 흐름에 따라 직경이 줄어듦을(shrinking) 알 수 있습니다. 우측 Internet 네트워크와 Citation 네트워크를 보게 되면 시간의 흐름에 따라 직경이 감소하고 있음을 확인할 수 있습니다.

네트워크의 크기가 증가함에도 불구하고 직경이 줄어든다는 의미는 노드 간의 거리가 천천히 감소가고 밀도가 증가했다고 해석할 수 있습니다.

그렇다면 직경의 감소는 그저 밀도로 인한 결과라고 할 수 있을까요? 시뮬레이션을 통해 답을 얻을 수 있었다고 합니다. 서로 다른 크기의 랜덤 그래프를 생성한 뒤에 밀도를 측정합니다. 결과를 살펴보면 네트워크의 크기(여기서는 밀도를 의미한다고 이해했습니다, densify)에 따른 직경의 증가는, densification exponent가 1.3으로 증가한다고 이해할 수 있습니다.

if the densification would be the sole contributor to the shrinking diameter, I should see the thing going down, but don't

만약 직경의 감소에 대한 원인으로 densification이라고 한다면 오히려 densification exponent가 1보다 작고 그래프가 감소해야하지만 그렇지 않습니다. 즉, 정리하자면 밀도만이 직경의 감소의 원인이라고 할 수 없으며, 분명 다른 원인이 있을 것입니다.

실제 네트워크와 같은 차수 분포를 가지는 랜덤 네트워크를 비교해봄으로써 직경의 감소에는 밀도와 degree sequence가 영향을 미쳤다는 것을 알 수 있었다고 합니다.

여기서 세번째 포인트 질문이 등장합니다.

네트워크의 차수의 분포(degree distribution)는 어떻게 변화하는가?

degree distribution은 어떻게 densification과 함께 진화할까요? 여기에는 degree sequence가 진화하는 2가지 방법이 있다고 합니다.

Option 1 where the degree exponent $\gamma_t$ is constant over time as network evolves. In this case if $\gamma_t = \gamma \in [1,2]$, then $\alpha = 2/\gamma$. Power laws with exponents less than 2 hav e infinite expectations, so by maintaining constant degree exponent $\gamma$ the average degree grows.

첫번째 방법은 네트워크 진화에 따른 degree exponent $\gamma_t$가 상수로 존재한다고 할 때, $\gamma_t$가 [1, 2] 사이의 값이라면 densification은 $2/\gamma$가 된다고 합니다. 솔직히 무슨 말인지 잘 모르겠습니다..

Email 네트워크 예시를 통해 알아보겠습니다. 해당 plot은 Email 네트워크의 degree distribution입니다. 노드의 차수와 그에 따른 노드 개수를 표현한 것이기에 분포도라고 할 수 있습니다. 정확하게 모든 것을 이해하지는 못했지만, 해당 plot에 대한 설명을 보자면, 먼저 차수가 낮은 노드의 개수 자체가 많은 것을 알 수 있는 반면 보통 차수가 많은 노드들의 분포가 많은 것을 알 수 있습니다. 이를 heavy-tailed라고 하는 것 같습니다. 또한 좌측 plot의 기울기(slope)에 대한 값을 $\gamma$라고 표현하는 것 같습니다.

Option 2 where the degree exponent $\gamma_t$ evolves with graph size $n$, if $\gamma_t = \frac {4n^{x-1}{t} - 1}{2n^{x-1}{t} - 1}$ then $x = a$ the densifying constant. Here $\gamma_t -> \text {2 as }n_t -> \infty$. The expected degree in a power law is $E[X] = \frac {\gamma_t - 1}{\gamma_t - 2}x_m$, so $\gamma_t$ has to decay as a function of graph size $n_t$ for the average degree to go up.

결론적으로, 네트워크의 밀도가 높아지고 직경이 감소하는 현상에 대한 이유에는 degree distribution(차수의 분포도)가 시간에 따라 진화하고 either it's being basically having the distribution is constant and accoring to a given shape, that gives us densification.(뭔소리일까요..)

이러한 네트워크를 생성할 수 있는 Forest Fire Model에 대해서 소개합니다. 여기서 이러한 네트워크는 밀도가 높아지면서 직경이 감소하는 그래프를 말하는 것 같습니다.(graphs that densify and have shrinking diameters)

그래프가 진화하는 과정을 파티에서 친구를 만나 관계가 확장되는 것으로 예시를 들게 됩니다. 친구가 하나도 없던 v가 w라는 친구를 만남으로써 w의 친구들을 계속해서 소개받음으로써 친구 관계를 생성해나간다고 합니다. 여기서 w의 친구를 소개받고 w의 친구의 친구를 소개 받는 것을 fire spreads라고 표현합니다. 이 때, w의 친구를 모두 소개하는(spread) 과정을 가지는 것이 아니라 decide to spread it 과정을 가지는 것 같습니다.(어떤 기준인지에 대해서는 언급하지 않습니다.) 그리고 fire dies할 때까지 (소개할 친구가 없을 때까지) 이러한 과정이 반복됩니다.

해당 과정에서는 forward burning probability, $p$ 와 backward burning probability, $r$ 이라는 2가지 파라미터가 필요합니다. 방향성이 존재하는 graph에서 새로운 v가 추가될 때마다 무작위로 'ambassador' 노드를 선택하게 됩니다.(ambassador 노드는 불을 번지게 하는 첫번째 노드 w를 의미하는 것 같습니다.)

다음으로 파라미터 $p, r$에 기반하여 spread할 노드의 in/out을 결정하는 binary 과정을 통해 최종적으로 몇 개의 노드에 fire spread할 지 결정하게 됩니다. 새롭게 spread한 노드에 대해서 다음 과정을 반복하면서 fire dies될 때까지 진행되며 새로운 노드 v는 fire spread된 모든 노드와 연결되게 됩니다.

Forest Fire Model로 생성된 노드의 개수와 엣지의 개수를 로그 스케일상에서 살펴보면, densification exponent는 1.32가 나오게 되며 노드 개수가 증가함에 따라 직경이 감소하다는 것을 알 수 있게 됩니다.

위 그림은 Forward burning probability, $p$에 대한 computational 과정에 대한 것입니다. $p$가 작게되면 fire spread를 위한 burning이 작으며, 크게 되면 많은 노드들을 burning하는 것으로 이해할 수 있습니다. 점선은 densification에 대한 변화를 의미하며 $p$가 작을 시에는 적은 관계가 형성되기 때문에 densification 또한 거의 없다고 볼 수 있습니다.

그래프의 지름의 경우에는 처음에는 증가하는 현상을 보입니다. 이렇게 되는 이유는 노드 간의 엣지(연결)이 dense하지 않고 sparse하기 때문에 한 노드에서 노드로 갈 수 있는 거리가 굉장히 멀기 때문입니다. 하지만 어느 시점에서는 diameter가 감소하게 되는데, 노드 간의 연결이 많아졌기 때문에 이제는 노드에서 노드로 갈 수 있는 거리가 가까워졌음을 의미합니다. 그리고 diameter가 일정하게 유지되는 이유를 complete graph라고 하는데 모든 노드간의 연결이 존재하기 때문으로 이해했습니다.

3. Temporal Networks

지금까지 살펴본 macroscopic level에서의 graph evolve는 어떠한 기준의 주기의 snapshot을 통해 변화를 살펴볼 수 있었습니다.

What we will do now is how nodes and edges are coming and leaving.

이번 목차에서는 어떻게 노드와 엣지가 추가되고 삭제되는지 알아보는 것 같습니다. 이 때 temporal networks를 정의하게 되는데, temporal networks란 동일한 집합의 정적 그래프의 연속?변화?입니다. 노드와 노드의 엣지에는 timestamp가 존재한다고 합니다. 이 timestamp가 연속에 대한 order를 의미하는 것 같습니다.

해당 네트워크를 보면 모두 같은 노드의 집합임을 알 수 있습니다. 그리고 time이 지날 수록 엣지가 변화하는 것 또한 볼 수 있습니다. 시점 1,2,3에 대한 snapshop을 통해 엣지가 변화하는 것을 볼 수 있는데, 엣지 (c,d)의 경우에는 시점 1,2,3에 모두 존재하기 때문에 최종 네트워크에서 엣지 (c,d)가 가지는 timestamp는 1,2,3이 됩니다.

temporal network의 예시로는 다음과 같습니다.

• communication networks like phone calls
• proximity networks like people in the same hospital room, meeting at a conference
• Transportation networks like trains or planes fly
• Cell biology networks like protein-protein interactions, gene regulation and etc

또한 하단의 그림은 일주일간 24시간 동안의 email communication에 대한 temporal network입니다. 그리고 하단 우측의 그림은 각 요일의 그래프를 집계한 것으로 이해했으며 이메일을 주고 받은 2명 간의 엣지가 표현되었습니다.

4. Microscopic Evolution of Networks

we can now start thinking about how do networks evolve at this microscopic level. how do the nodes change over time.

이번 목차에서는 microscopic level에서 네트워크가 진화하는 과정과 어떻게 노드들이 변화하는지에 대해 다뤄보고자 합니다. micro level에서 네트워크는 어떻게 진화할까요? macro level에서도 알아봤듯이, micro level에서도 질문의 포인트에 있어 2가지 question을 던집니다.

• How do we define paths and walks in temporal networks?, 어떻게 temporal networks에서 path(경로)와 walk(보행)을 정의할 것인가?
• How can we extend network centrality measures to temporal networks?, 어떻게 network centrality measures like PageRank or node importance를 temporal networks로 확장할 수 있는가?

먼저 walk(보행), path(경로)에 대해 정의하고 그 개념들을 simple graph에서 temporal graph로 확장시킬 수 있습니다.

temporal path 또한 temporal network에서 이해했듯이, 시점마다 존재하는(sequential) 엣지들의 집합?이라고 할 수 있을 같습니다. 예시를 보자면, path (5, 1)이 만족하기 위해서는 시점 $t_1, t_3$의 temporal path이 필요하게 됩니다.

사실 이렇게 temporal path를 정의하는 이유를 정확히 이해하지는 못했지만 단순 그래프에서 경로를 계산할 때와, 시점이 존재할 때에 경로를 계산하는 것이 다른 결과를 초래하기 때문에 이처럼 시계열적인 특징을 고려하기 위해서 temporal path를 정의하는 것으로 이해했습니다.

그리고 TPSP-Djikstra algotirhm을 통해 가장 짧은 temporal path를 찾을 수 있다고 합니다.

해당 알고리즘의 예시를 한번 볼 수 있습니다. 총 5개의 시점으로 이루어진 해당 그래프는 시점 마다 엣지의 관계가 변하고 있음을 알 수 있습니다. 해당 그래프에서 각 시점마다 $path(a, f)$를 찾을 수 있습니다.

• $t_1: a-c-d-e-f$
• $t_2: a-c-d-f$
• $t_3: a-c-d-g-f$
• $t_4: a-b-g-f$
• $t_5: a-b-g-f$

이렇게 가장 짧은 경로를 구하는 알고리즘을 적용하는 이유는 closeness centrality 때문입니다. Temporal closeness는 시점마다 네트워크의 특정 노드와 모든 노드 간의 근접도 측정 방식입니다. 노드 간의 거리를 측정하게 되면 해당 노드가 네트워크의 중심부에 있는지 가장자리에 있는지 추측할 수 있습니다. 이 과정이 어떻게 보면 node importance, 노드의 중요성에 대해 판단할 수 있는 요소가 될 수 있습니다.

수식을 살펴보면, 주어진 시점에서 노트 x와 모든 노드 y들 간의 shortest path를 계산하여 합함으로써 closeness centrality를 구할 수 있습니다. 즉 closeness centrality가 1에 가까울수록 네트워크의 중심부라고 해석할 수 있을 것 같습니다.

example을 보게 되면 이해가 되지 않는 부분이 있었습니다. $c_clos(A, 2)$를 구하기 위해서 A와 C의 $t_2$의 distance가 1임을 알 수 있지만 A와 E의 $t_2$의 distnace가 왜 2가 나오는지 모르겠습니다. $t_2$에서는 path (A, E)가 성립되지 않는 것으로 이해했는데, 절대적인 path (A, E)라서 2가 더해지는 것인지 정확히 이해할 수 없었습니다. 아.. 혹시 path (A, B)와 path (A, E)가 $t_1$에 이미 만족하고 있기 때문에 성립되는 것인지 갑자기 생각이 들긴합니다. 확실하지는 않습니다.

이 전 강의에서 페이지와 페이지가 연결되어 있는 인터넷 구조에서 페이지(노드)의 중요성을 판단하기 위해서 PageRank 알고리즘을 적용할 수 있었습니다. 사실 이 알고리즘에서도 temporal(시계열적)인 특징을 적용해볼 수 있습니다. 시간의 흐름에 따라 페이지와 페이지의 연결이 생기기도하고 사라지기도 하면서 해당 페이지의 중요도가 바뀔 수 있기 때문입니다.

이번에는 temporal walk에 대한 개념을 정의해보도록 하겠습니다. 사실 해당 슬라이드의 설명으로는 temporal walk에 대한 개념을 이해하지 못했습니다.

해당 페이지랭크의 예시를 보면 time-respecting의 의미를 조금은 이해할 수 있었습니다. path (c -> b -> a -> c) 의 경우에는 엣지에 존재하는 timestamp가 시계열 특징을 만족하는 반면 path (a -> c -> b -> a)는 시점의 순서가 얽혀 time respecting 하지 못한다고 합니다.

그렇다면 temporal path의 확률에 대해 생각해볼 수 있습니다.

$$P[(u,x,t_2)|(v,u,t_1)]$$

는 $t_1$시점에서 노드 v가 노드 u와 연결되어 있을 때, $t_2$시점에 노드 u가 노드 x와 연결될 확률을 의미합니다. 지수 분포 상에서 해당 확률을 정의하게 되면 다음과 같습니다.

$$P[(u,x,t_2)|(v,u,t_1)] = \beta^{|Γ_u|}$$

이 때, $\beta$는 transition probability로 0~1 의 값을 가지게 되며, $Γ_ u$는 해당 시점에서 노드 u가 가지는 엣지의 개수라고 할 수 있습니다. 그렇기 때문에 많은 노드와 연결되어 있는 엣지의 개수가 많아지게 되면 결국 특정 노드와의 연결 확률이 낮아지는 결과를 낳게 됩니다.

그런데 t 시점에 대한 제한이 없을 경우에는 temporal PageRank는 static PageRank에 수렴하게 됩니다. 이렇게 되는 이유는 결국 $t_1 - t_\infty$에서 발생하는 네트워크의 변화에 대한 축적이 static PageRank에서 다루는 완성된 네트워크와 동일하다고 볼 수 있기 때문으로 이해했습니다.

참고문헌

• Anil, 16.Network Evolution
• Tobigs graph study, Chapter16. network evolution graph

• 이번 강의에서는 네트워크에서 특정 사건이 발생하고 이를 어떤방식으로 탐지하고 처리하는 방법에 대해서 소개합니다.

• 먼저 문제에 대해서 정의하고 이를 해결하는 알고리즘 중 그리디하게 접근하는 hill-climbing 알고리즘에 대해서 소개합니다.

• 사진의 네트워크의 노드는 가정집이고 간선은 수도로 정의합니다.
• 여기서 수질오염이 발생하여 이를 센서를 통해 탐지하고자 합니다. 센서를 모든 노드마다 배치하여 수질오염을 탐지할 수 있으면 좋겠지만 아시다시피 정해진 cost내에서 센서를 효율적으로 배치하여 수질오염을 탐지하는게 목표입니다.

• 여기서 파란 박스를 유저로 두고 박스 내에 있는 p는 post, 글입니다. 어떤 포스트를 따라가야 repost된 관계 구조를 효율적으로 파악할 수 있을까가 문제입니다. 이는 위에서 소개했던 예시와 유사합니다.

• 주어진 네트워크 내 노드를 선택하여 문제를 효율적으로 탐지하고자 합니다. 이는 전염병, 네트워크 보안등에 적용될 수 있습니다.

• 센서위치를 어디에 두는지에 따라 센서가 탐지하는 범위가 달라집니다. S1의 경우는 넓은 범위를 탐지하지만 오른쪽에 센서들은 작은 범위만을 탐지합니다.
• 여기서 trade off는 여러개 센서를 두어 효율적으로 일찍 탐지를 할것인지 아니면 늦게 탐지하더라도 넓은 범위를 탐지할 수 있도록 센서를 둘것인지를 결정해야합니다.

• 주어진 그래프에서 u 노드가 사건을 탐지하는데 걸리는 시간을 다음과 같이 정의합니다.

• 그래서 가장 큰 reward를 얻을 수 있는 노드 집합을 찾아 고르는 것이 우리의 목표입니다. 여기서 cost는 주어진 예산보다 작아야 합니다.

• 여기서 reward의 가치는 다음과 같이 둘 수 있습니다. 이전에 언급했듯이 사건 탐지를 가장 빠르게 할것인지, 느리게 탐지하더라도 넓은 범위를 커버하는지가 있습니다.
• 연결이 너무 많이된 노드에 센서를 두면 탐지하기 위해 많은 시간을 사용합니다.

• Time to detection : 오염을 탐지하는데 걸린 시간.
• Detection likelihood : 얼마나 오염을 탐지하였는지.
• Population affected : 얼마나 많은 사람들이 오염된 물을 마셨는가.
• 여기서 중요한 점은 무조건 빨리 탐지하는게 좋다고 교수님께서 말씀 하셨습니다. 이 점을 이용하여 후에 그리디한 알고리즘으로 문제를 해결한다고 저는 이해했습니다.

• 다음과 같이 목적함수를 정의합니다.
• 왼쪽에서 새로운 센서를 다음과 같이 두면 효율적으로 오염을 탐지할 수 있습니다. 하지만 오른쪽에 똑같이 적용하면 왼쪽에서만큼 효율을 발휘하지 못합니다.

• A, B는 주어진 그래프의 노드 셋입니다. 서브 그래프 개념으로 본다면 B는 A를 포함하는 더 큰 서브그래프인 셈입니다.

• 위의 식이 성립하는 이유는 앞서 센서가 겹쳐서 탐지하는 부분이 많다면 효율이 떨어지는 경우를 보았습니다. 이처럼 A가 B의 부분집합일 때 A에 센서를 추가하는것이 B에 추가하는것 보다 더 효율적일 수 있습니다.

• 탐지하는 시간의 경우를 세 가지로 나누어 봅니다.

• 첫번째 경우는 x 센서를 두어도 탐지하는데 가장많은 시간이 걸리기 때문에 필요가 없습니다.

• 두번째 경우는 A에 대해선 더 좋지만 B에는 아니라는 점입니다.

• 세번째 경우는 x가 A,B보다 빨리 탐지합니다.

• 그래서 우리가 사용하는 목적함수는 Submodular라는 것입니다.

• 매번마다 노드의 reward를 갱신하고 이를 선택하는 알고리즘입니다. 하지만 특정 문제에서만 해결 가능하며 시간복잡도가 느린 알고리즘입니다.

• Hill-climbing은 노드 자체의 cost를 무시합니다. 그리고 이 방법을 사용하면 가진 예산을 금방 낭비할 가능성이 큽니다. 고의적으로 최선을 선택하지 못하는 상황이 발생합니다.

• 여기서 n개 센서에 B 예산을 가지고 있습니다. s1은 r과 B를 가지는데 나머지 센서의 reward는 s1보다 작습니다. 따라서 Hill-climbing 알고리즘을 적용하면 s1을 선택하게 되고 주어진 예산을 전부 사용하게 됩니다. 하지만 나머지 센서들을 여러개 선택할 수 있고 더 좋은 reward를 얻을 수 있었지만 s1을 택하게 되는 현상이 발생합니다.
• 따라서 이를 조율할 수 있는(최적화 할 수 있는) benefit-cost ratio를 적용합니다. 하지만 이또한 위와 유사한 문제가 발생하게 됩니다.

• CELF 알고리즘은 그리디 알고리즘을 적용하여 두 결과중 최적의 결과를 선택합니다. 앞서 발생한 문제가 있었지만 그래도 정답과 유사한 결과를 선택할 수 있다고 합니다.

• 여기서 각 노드들의 Marginal gain을 고려하여 탐색을 진행하는데 S1이 a인 상태에서 gain을 구했고 남은 노드들에 대해서도 구하고 정렬합니다.
• a를 서브셋에 넣고 다음 노드들을 집합에 넣어 marginal gain을 다시 계산합니다. 이를 반복적으로 적용하여 셋을 구합니다.
• 무조건 marginal gain이 높은걸 선택해야 최적화된 답입니다. 이유는 이를 택하지 않는 최적의 경우의수가 있다고 생각했을 때 다른 노드를 선택하면 당연히 gain이 낮은것들만 선택함으로 greedy하게 접근하는 것이 가능합니다.

• 여기서는 Solution quality에 대해서 얘기합니다. 알고리즘을 통해서 구한 답은 정답이 아니라 정답에 가까운 답을 구해줍니다. Submodular 함수는 1-1/e의 바운드가 존재합니다.

• 여기서 델타 u는 u를 선택하였을 때 얻는 margin. 그리고 OPT는 구한 최적의 노드 셋을 의미합니다.
• 다음 식을 따라서 최적의 셋의 스코어가 다음 보다 작다고 정의하고 있습니다.

우리는 어떠한 상품을 구매할 때, 주로 낯선 사람들보다 주변 사람들에게 영향을 많이 받습니다. 통계 역시도 68%가 친구들이나 가족들에게 조언을 구한다고 제시하고 있습니다.

그렇다면, 우리는 다음과 같은 마케팅 요소를 생각해볼 수 있을 것입니다.

어떠한 사람이 가장 친구들에게 영향을 많이 끼치는가?

한 예로, Kate Middleton effect를 생각해볼 수 있습니다.

"... when she does wear something, it always seems to go on a waiting list."

그녀가 입은 옷은 모두 완판된다는 것으로 그 만큼, 상품을 구매하는데 큰 영향을 끼친다는 것을 알 수 있습니다.

그렇다면, 우리는 Kate와 같이 "Influential Person"을 어떻게 찾을 수 있을까요? Kate와 같은 사람들을 다수 찾는다면, 그만큼 광고 효과를 크게 낼 수 있을 것입니다. (Influence Maximization)

Two Classical Propagation Models

Linear Threshold Model

노드마다 임의의 threshold가 있습니다. 이것은 node v가 영향을 받는 정도의 weight를 나타내는 값으로 영향력을 나타냅니다. 예를 들어, 나를 기준으로 친한 친구한테 받은 영향력이랑 학교 선생님한테 받은 영향력이 다를겁니다. 이를 표현한 것이라고 생각하시면 됩니다.

node v부터 시작해봅시다. 각각의 노드들은 앞서 말한 threshold들을 가지고 있고, 그 값보다 크면 영향을 받게 됩니다. node w의 경우, node의 threshold보다 이웃에게 받은 영향이 더욱 크게 나타납니다. (파란색 사각형보다 빨간색 사각형의 크기가 더 큼으로부터 알 수 있습니다.) 따라서 Active Node가 됩니다. 이러한 과정들을 지속적으로 반복하면 Active Node와 Inactive Node를 구분할 수 있게 됩니다.

Independent Cascade Model

각각의 edge (v, w)는 확률들로 구성되어있으며, node v가 active 되었을 때, node w가 active될 확률들 나타냅니다. 즉, 영향받은 확률을 나타내는 것으로 볼 수 있습니다.

각각의 edge (v, w)는 probability 를 가지고 있다. 이때, 는 node v가 node w에게 영향을 줄 확률이다. 즉, node w가 node v에게 영향을 받아 상품을 살 확률이라고 생각하시면 됩니다.

그러한 작업들을 반복하였을 때, 각각의 subset을 확인할 수 있으며, 영향력이 가장 크게 나타나는 경우 역시 확인해볼 수 있습니다. 위의 그림을 보면 a와 d의 합이 가장 영향력이 크다는 것을 직관적으로 확인할 수 있습니다.

How hard is influence maximization?

정리하면, K개의 node를 찾는 것이며, K개의 node의 subset S가 maximize되어야 한다는 것입니다.

"Influence maximization NP-complete"

NP-complete문제로 해결하지가 쉽지 않습니다. 하지만, approximation algorithm을 활용하여 다음과 같은 문제를 해결할 수 있습니다. 이 algorithm을 사용한다면 최적해 결과의 63%의 효율을 끌어올 수 있습니다.

Greedy Hill Climbing Algorithm

해당 알고리즘은 매시점마다 Si가 최대가 되도록 선택하는 것입니다. 예를 들어, 처음 값을 보면 d가 높은 값을 가지고 있으므로, Si에 d를 추가합니다. 다음 step으로 Si와 합집합하였을 때, 가장 높은 값을 선택하게 됩니다. 이 경우 b이기 떄문에 Si에 b를 추가해줍니다.

이러한 과정을 계속해서 반복하여 최적값을 찾아가는 것이 해당 알고리즘이라고 생각하시면 됩니다.

해당 함수는 두가지 특성이 나타나게 됩니다.

• f is monotone
• f is submodular

Prove 1: our f(S) is submodular

T가 S를 포함하고 있다고 가정해봅시다. 그렇다면 u라는 순수영역을 더욱 보존하고 있는 경우는 당연히 S가 될 것입니다. 그림에서 녹색으로 채워진 부분이 S이며, 녹색과 파란색으로 채워진 부분이 T입니다. 해당 집합들과 u간의 차집합을 구했을 때, S인 경우가 u의 면적이 더 많이 남아있음을 알 수 있습니다.

Principle of deferred decision

f(S)를 확률적으로 접근했기 때문에 우리는 f(S)에 해당하는 parallel possible worlds를 만들 수 있고, 이걸 average함으로써 우리의 알고리즘(무작위 알고리즘)에 신뢰를 줄 수 있습니다.

Prove 2: Hill Climbing gives near-optimal solutions

해당 식의 증명과정은 이곳은 참고하면 됩니다!

Greedy algorithm is Slow

위의 모든 과정들을 생각해봤을 때, 연산속도가 매우 느리다는 것이 큰 단점인 것을 파악할 수 있습니다. 우리는 k만큼의 영향력있는 사람들을 알길 원하며, 모든 node에 대해서 iteration을 진행해야 합니다.

Sketch-based Algorithms

그리디 알고리즘을 수행할 경우, 많은 시간이 소요됨을 확인할 수 있었습니다. 따라서, 연산시간을 줄이기 위해서 Sketch-based Alogrithms을 사용하고자 합니다. 이 모델은 기존의 시간복잡도 O(M)을 O(1)로 줄일 수 있습니다. (m = number of edges)

1. Take a possible world G(i)
2. Give each node a uniform random number from 0~1
3. Compute the rank of each node v, which is the minimum number among the nodes that v can reach

여기서의 핵심 아이디어는 node v가 많은 node들과 연결되어있다면, 그 만큼 rank가 작을 것이라는 것입니다. 따라서, 해당 rank 정보를 활용하여 영향력을 추정해볼 수 있게 되는 것입니다.

하지만, 이러한 추정은 물론 불안정합니다. 하지만, 다수의 random number와 rank를 부여한다면 추정의 불안정성을 어느정도 개선할 수 있습니다.

Epidemics vs Cascade Spreading

epidemic spreading

• 의사결정이 결핍되어있음
• 감염의 과정이 매우 복잡하고 눈에 보이지 않습니다.

당연하게도 높은 감염률이면 질병이 퍼져나가게 되며, 낮은 감염률이면 질병이 소멸하게 됩니다.

Probabilistic Spreading Models

'd'를 자식노드의 수 'q'를 감영확률이라고 가정한다면, 전염벙이 지속되는 d와 q값은 무엇일까요?

임의의 노드 h에서 한 노드가 감염될 확률이 0보다 크다면 우리는 전염병이 확산된다고 말할 수 있습니다. 임의의 노드 h가 무한대로 갈 때 (시기가 계속된다면), 전염병은 지속되고 있다고 말할 수 있을 겁니다.

그렇다면, 우리는 임의의 노드 h에서 한 노드가 감염될 확률을 구한다면, 전염병의 지속여부에 대해서 파악할 수 있습니다.

임의의 노드 h에서의 확률은 다음과 같이 구할 수 있습니다. 이전 노드에서 나온 자식노드들이 모두 감염되지 않을 확률을 1에서 빼면 됩니다.

결국 root 노드 (초기감염자)의 확률 1에서 시작하여, 확률이 점차 낮아지는 형태의 함수가 만들어집니다.

여기서 중요한 것은 변화율 qd에 따라 전염병이 확신이 될지 안될지 결정할 수 있다는 점입니다. qd는 감염된 사람들의 기대평균 수를 나타내는 값으로, qd가 1보다 작다면 x=p가 0으로 수렴하게 되므로 0으로 수렴하게 됩니다.

Applicaition: Social cascades on Flickr and estimating R0 from real data

Dataset

• Users can be exposed to a photo via social influence (cascade) or -external links
• Did a particular like spread through social links
• • No, if a user likes a photo and if none of his friends have previously liked the photo
• • Yes, if a users likes a photo after at least one of her friends liked the photo-> Social cascade
• Example social cascade: A->B and A->C->E
• Flickr social network
• • Users and connected to other users via friend links
• • A user can like/favorite a photo
• Data:
• • 100 days of photo likes
• • Number of users : 2 million
• • 34,734,221 likes on 11, 267, 320 photos

R0를 추정하는 방법에는 두가지 방법이 있습니다. Estimate of R0 방법과 Empirical R0를 획득하는 방법입니다. Estimate of R0의 경우, 실제와 유사한 값을 가지기 위해서 보정상수(Correction factor)을 곱해주어 다음 값을 구해줍니다. Empirical R0의 경우, start node를 기반으로 cascade 과정을 통해 직접 감염된 노드를 세주는 것입니다.

확실하진 않지만, Estimate of R0는 전체적인 연산과정을 통해 R0를을 추정하는 것이며, Empirical R0는 단편적인 부분만 보고 R0를 유추한다는 것으로 이해됩니다.

여기서는 Empirical R0가 Estimate of R0를 얼마나 따라갈 수 있을지 확인해보는 것이 포인트 입니다. 만약 잘 따라간다면, 단편적인 부분 (부모노드)만 보고서 해당값을 유추할 수 있을 것입니다.

결과적으로 높은 상관관계가 나타나고 있습니다.

Epidemic models

Virus Propagtion에는 두 개의 파라미터가 있으며, Birth rate: probability that an infected nieghbor attacks Death rate: Probability that an infected node heals

Epidemic models에는 SEIR, SIR, SIS Model 등이 있습니다.

More Generally: S+E+I+R Models

각각 노드가 갈 수 있는 상태를 나타낸 것입니다.

SIR Model

Susceptible people changing (-BSI): 취약층에서 감염된 사람들만큼 줄기 때문에 -의 부호가 붙습니다.

SIS Model

virus "strength"을 측정은 다음과 같이 측정할 수 있습니다. $$ s = beta / delta < tau $$ SIR모형과의 차이점은 unsusceptible people changing의 값이 다르다는 점입니다. 이는 노드가 다시 susceptible 상태로 이동할 수 있음을 나타내고 있습니다.

당연하게도, 치료확률 (cured value)이 훨씬 더 커지게 되면, 전염병은 더이상 확산되지 않을 것입니다. 위의 그림은 다음과 같은 논리를 수식으로 표현하고 있습니다.

threshold 값을 넘는다면 바이러스는 지속되게 됩니다. 그렇다면 주어진 그래프에서 Epidemic threshold (tau)를 어떻게 구할 수 있을까요? (증명과정은 여기서 생략합니다.) 결론적으로, 가장 큰 고유값의 역수의 값으로 Epidemic threshold를 규정할 수 있습니다.

Application: Rumor spread modeling using SEIZ model

루머의 확산 == 질병의 확산 S: 트위터 계정 I: 루머/뉴스를 믿거나 리트윗한 경우 E: 루머/뉴스를 마주하였으나, 그것을 아직 믿지 않은 상태 S: 루머/뉴스를 믿지 아니하는 것

Susceptible의 변화율만 본다면, SI: S에서 I로의 이동과 파라미터(contact rate) B SZ: S에서 Z로의 이동과 파라미터(contact rate) b Susceptible에서는 유입되는 것은 없고, 유출되는 것만 있으므로, 둘다 -의 부호를 가지게 됩니다.

그리드 서치를 통해 실제 rumor의 tweets 수와 모델이 예측한 rumor tweets 수의 차이를 줄이면서 파라미터들을 추정하게 됩니다.

연구자들은 다음과 같은 metric에 대해서 흥미를 가지고 있다고 말합니다. 해당 RSI는 S에서 E로 이동하는 사람의 수와 E에서 I로 이동하는 사람 수의 비율입니다. 비유하자면, 환자가 일상생활에서 병에 노출(Exposed)되는 속도와 노출된 환자가 실제 감염(Infected)되는 속도에 대해서 파악하고자 한 것으로 보입니다.

한 실험에서의 결과를 바탕으로 봤을 때, Rumor의 경우 Real news보다 해당 값의 비율이 높았다고 말하고 있습니다. 그 만큼 Rumor의 경우, 빠르게 사실로 받아지는 것을 알 수 파악해볼 수 있었습니다.

Independent Cascade Model

edge (u,v) 는 확률값을 가지고 있으며, 다른 edge들과 독립적입니다. 즉, 한번의 edge마다 동전던지기를 1회 수행하는 것처럼 독립사건이라는 뜻입니다.

하지만, 실제 데이터로부터 이 weight들을 모두 추정하는 것은 굉장히 어렵습니다. 또한, 이 weight들을 모두 동일하게 취급하는 것 역시 너무 simple한 모델이 되어버립니다. 그렇다면 어떻게 이 문제를 해결할 수 있을까요?

Exposures and Adoptions

결국, 새로운 행동(전염)의 전파 여부는 이미 행동(전염)이 전파된 주변 노드의 수에 의존하는 것을 파악해볼 수 있습니다.

이외의 다양한 형태의 curves들이 존재할 수도 있습니다. 첫번째 그림같은 경우, 광고를 예시로 들을 수 있습니다. 광고의 한두번 노출됐을 때, 구매량이 높게 나타나나, 이후 지속적인 노출은 더이상의 구매량을 증가시키지 못하는 경우를 흔히 찾아볼 수 있습니다.

Twitter Example

해당 실험은 500개의 hastags에 대해 얼마나 노출되었으며, hashtags에 노출된 뒤, 해당 hastags를 얼마나 사용했느냐 측정한 것입니다. 결과적으로 그래프는 다음과 같이 나타나고 있습니다. 일정시점에서 증가하다가 peak를 찍고, 감소하는 추세를 보이고 있습니다.

우리는 여기서 persistence의 개념을 파악할 수 있습니다. 만약 가장 높은 peak 점을 찍고 난 후에도 그래프의 곡선이 낮아지지 않는다면 해당 그래프는 지속성이 크다고 말할 수 있을 것입니다. 즉, persistence가 높다고 말할 수 있습니다. 우리는 이를 그래프의 아래의 면적을 통해서 파악할 수 있습니다.

8개의 카테고리에 대해 persistence를 측정한 결과를 보면, Politics와 Sports가 높은 persistence를 가지고 있는 것으로 확인할 수 있었습니다. 8개의 카테고리에 대해 stickiness를 측정한 결과를 보면, Music의 경우, stickiness가 높게 나타나는 것으로 파악해볼 수 있습니다.

Contents

0. Intro: Spreading Through Networks
1. Decision Based Model of Diffusion
2. Application: Modeling protest recruitment on social networks
3. Extending the Model: Allow People to Adopt A and B
4. Summary & PREVIEW

Network Effects and Cascading Behavior

0. Intro: Spreading Through Networks

Keyword cascade,diffusion,game theoretic model, k-core decomposition

12강은 제목 그대로 Network Effect와 Cascading Behavior에 대해 배웁니다. Spreading Through Networks에는 다음과 같은 분야들이 있습니다. '행동' 들은 network안에서 node에서 node로 흐릅니다(cascade).

Spreading Through Networks

• Cascading behavior
• Diffusion of innovations
• Netsork effects
• Epidemics

Example

• Biological: 전염병
• Technological
  • Cascading failures
  • Spread of information
• Social
  • Rumors, news, new technology
  • Viral marketing

-> Twitter & Facebook posh sharing(repost) 와 상품 추천 등이 해당

Network Cascades(and Terminology)

• contagion
• cascade
• infection event : Adoption, infection, activation
• main players : infected/active nodes, adopters

확산(Diffusion)을 어떻게 model로 만들까?

의사결정(decision making)여부에 따라 Decision based model 과 Probabilistic model 이 있습니다. 오늘은 Decision based model에 대해서만 알아보도록 하겠습니다.

1. Decision Based Model of Diffusion

Decision Based Model은 기본적으로 게임이론을 이용합니다.

Game Theoretic Model of Cascades

• 2명의 player가 각각 선택A나 선택B를 하는 의사결정 상황
• 만약 친구들이 내가 한 선택과 같은 선택을 한다면 더 많은 이득을 얻음
• ex. BetaMax vs VHS , BlueRay vs HD DVD

The Model for Two Nodes

payoff matrix

• v와 w가 모두 행동A를 선택하면 payoff a>0 획득
• v와 w가 모두 행동B를 선택하면 payoff b>0 획득
• v와 w가 서로 반대 선택을 하면 각각 0 획득

-> payoff는 여러 게임에서 보상의 합계로 계산 -> 큰 네트워크에서 각 node v는 근처 이웃의 행동을 따라하게 된다.

Calculation of Node v

쉽게 말해서 보상 받는 pay를 고려한 다수결의 선택을 합니다. (보수는 같을 수도, 다를 수도)

Example Scenario

Scenario

• Graph 안에 모두는 B에서 시작한다.

• 작은 집단 S들만 A를 일찍 적용한다. (Small set S of early adopters of A)

  • Hard-wire S : 보상에 상관없이 꾸준히 A만 선택 (꾸준하게 애플만 선택하는 앱등이)

• 내 친구 중 50% 이상이 A를 선택하면, 나도 A를 선택한다.(보상 a와 b가 거의 같은 상황인 것)

*이게 Cascade입니다. 나(node)는 보상에 충실한 선택(친구따라) 선택했을 뿐인데, 결과적으로 다른 노드에 영향을 주었습니다**

2. Application: Modeling protest recruitment on social networks

The Dynamics of Protest Recruitment through an Online Network Bailon et al. Nature Scientific Reports, 2011

cascade 사례를 보기위해서 스페인에서 일어난 긴축방지 시위(The Spanish 'Indignados' Movement)를 예시로 보겠습니다.

Twitter를 사용해서 모이고 모바일 유저들이 참여했습니다. #indignados_movement

(1) Data collected using hashtags

sns를 사용한 운동이었기 때문에 관련 해시태그를 모두 크롤링하고 그 중에 70개의 주요해시태그를 선택했습니다.

(2) Dataset

• 1달 동안 주요 해시태그가 포함된 트윗(tweets)을 수집했습니다. 결과적으로 581,750개의 트윗을 사용했습니다.
• 관련 사용자 데이터도 수집했습니다. tweet을 언급한 사람 + 그 사람의 followers 결과적으로 87,569의 유저 데이터를 사용했습니다.
• 2개의 network를 만들었습니다.
  1. Full network : with all Twitter follow links (directed)
  2. Symmetric network : with only the reciprocal follow links (strong connections only, i<->j)(undirected)

(3) Definitions

• User activation time : Moment when user starts tweeting protest messages (첫 순간, 언제 시작했는지)
• $k_{in}$ = The total number of neighbors when a user became active
  • 유저가 active 시작할 당시 모든 이웃 수
• $k_{a}$ = Number of active neighbors when a user
  • 유저가 active 시작할 때 active 이웃 수
• Activation threshold = $k_{a}/k_{in}$
  • $0 < k_{a}/k_{in} < 1$
  • 마법의 tradeoff는 없고 상황이나 데이터에 따라 알아내야함

(4) Recruitment & Activation Threshold

• $k_{a}/k_{in}\approx 0$

  • 주변에 active 이웃 없는데 active하는 상황
  • no social pressure

• $k_{a}/k_{in}\approx 1$

  • 주변 이웃이 모두 active

  • high social pressure

    

(5) Result & significant

성공하는 cascade는 누가 시작하나?

성공하는 cascade는 소수입니다. 네트워크에서 더 중앙에 있는 starter일수록 성공할까요? 성공하는 특정 player들에 대해서 알아보겠습니다. 방법은 k-core decomposition을 사용합니다.

k-core decomposition

• k-core : 모든 노드가 적어도 차수 k개를 가진 연결성이 큰 subgraph.
• Method : k보다 작은 차수를 가진 node를 반복적으로 제거해나간다.
• Higher k-core number of a node means it is more central

Summary : Cascades on Twitter

• Uniform activation threshold for users, with two local peaks
• Most cascades are short
• Successful cascades are started by central (more core) users

3. Extending the Model: Allow People to Adopt A and B

Decision based model을 multiple contagions가 가능하도록 확장한 모델에 대해서 알아보겠습니다.

Extending the model

• extra strategy "AB"를 추가합니다.
• 한 player가 선택 A와 B를 모두 하는 것을 허용합니다.
  • AB-A : gets a
  • AB-B : gets b
  • AB-AB : gets max(a,b)
  • *cost c *: AB라는 선택을 하면 cost c만큼의 비용을 지불해야합니다. 모든 보상과 비용을 합산합니다.

Cascades & Compatibility: Model

• 모든 node들은 infinite network에 있고 B로 시작합니다.
• finite set S만 A를 선택합니다. (앱등이)
• Run the model for t=1,2,3,...
  • Each node selects behavior that will optimize payoff(t-1시점에서 이웃이 선택한 상황이 주어지고 t에서 내가 선택)

언제 선택 B에서 A나 AB로 바꿀까?

(1) B -> AB : 3+2-1=4, 전에는 2를 받았다면 이제 4를 받기 때문에 AB선택할 것이다. 하지만 A가 흐르는 모습은 볼 수 없다. (2) 보상이 바뀜 : 보상이 바뀌면서 A가 흐르게 된다. A를 선택함으로써 얻는 보상을 크게 해서 점점 A나 AB로 선택을 바꿨다.

General case

보상과 비용에 따라 선택이 달라지기 때문에 일반화 해봅시다. 어떻게 (c,a)를 설정해야 B로 시작하는 곳에서 A가 퍼질 수 있을까요?

• infinite path, start with all B
• payoffs for w : A:a, B:1, AB:a+1-c

(c,a) 에 대해서 x축 = a, y축 = b로 두고 그래프를 그리면 다음과 같습니다.

(1) 기본

(2) change payoff : b보상을 늘림

(3) 두 결과를 합침

lesson

좋은 A나 나올 때까지 디폴트가 B인 상황

• Infilteration : too compatibel

  • B가 호환가능성이 높으면 사람들은 두개 다 해보고 더 나쁜 것 (B)를 버릴것

• Direct conquest : not compatible

  • A가 호환되지 않는 경우, 경계에 있는 사용자가 선택. 더 좋은 것을 고름. 더 좋은 (A)를 선택 할 것

• Buffer zone

  • 최적인 상태를 고르는 경우, A와 B사이가 정적인 buffer 가 유지됨

이 그림을 보면 A가 B랑 호환성을 높게 만들면(즉, c가 낮아지면) B -> AB -> A 로 넘어가지만, 호환성을 낮게 만들면 direct하게 A로 바뀝니다. 애플의 이어폰단자를 생각해보면 쉽게 이해할 수 있을거라고 생각합니다. a를 쓰는 이점이 매우 크기 때문에, 호환성을 낮춰서 B를 버리고 A로 오게 하는거죠.. ㅠㅠ (갓진혁의 정리중...발췌)

4. Summary & PREVIEW

* Cascade의 기본 개념과 용어에 대해 알아보고, Diffusion(cascade)를 모델링 하는 방법 두 가지 중에 decision based model에 대해서 배웠습니다. decision based model은 게임이론이 베이스가 되고 기본형과 확장형이 있었습니다. *

Reference

Stanford CS224W 2019 https://tobigs.gitbook.io/tobigs-graph-study/chapter12.

Structure of the web

• 인터넷 웹을 그래프로 생각해보자
  • nodes = web pages
  • edges = hyperlinks
  • 웹 페이지 내부에서 외부 웹 페이지로 링크를 달면 edge가 생긴다고 볼 수 있다

• Web is a Directed Graph
  • web grpah를 보면 directed graph인 것을 알 수 있다
  • 이렇게 연결된 링크를 BFS로 크롤링을 하면 Google의 웹페이지를 몽땅 훑어볼 수 있다

What does the web look like?

• 인터넷 웹을 그래프로 만들었으면 어떻게 생겼을까?
• Web as a directed graph [Broder et al, 2000]
  • In(v): node v가 directed edge를 따라서 도달할 수 있는 다른 node의 set
  • Out(v): directed edge를 따라서 node v에 도달할 수 있는 다른 node의 set

• Two types of directed graphs

  • Strongly connected: 어느 node에서든 다른 node에 도달할 수 있음 In(A) = Out(A) = {A, B, C, D, E}

  • Directed Acyclic Graph(DAG): cycle이 없음. 노드 v에서 u에 도달할 수 있다고해도 u에서 v로 갈 수 없을 수도 있음

  • 모든 directeed graph(e.g. web)은 이 2가지 타입에 속한다!

Strongly Connected Component(SCC)

• SCC 내에서 어느 noed에서 출발하든 다른 node에 도달할 수 있음(strongly connected)

• 현재 SCC를 포함한 또 다른 SCC는 존재할 수 없음 → 모든 node는 한 SCC에만 속한다

• FACT: 모든 directed graph는 SCC의 DAG으로 표현할 수 있다

  • SCC는 전체 그래프의 partition이다. partition이라 함은 중복이 없다는 뜻
  • 전체 그래프 G를 참고하여 G의 SCC를 G'로 만들 수 있다. 이 때 edge는 G와 G' 모두 동일하게 매핑할 수 있고 G'는 DAG라고 볼 수 있다.

Graph structure of the web

• Computational issue: 현재 node가 어느 SCC에 포함되어있는지 어떻게 알 수 있을까?
• Observation: node v를 포함하는 SCC = Out(v)∩In(v) = Out(v, G)∩Out(v, G')

• Directed version of the web graph

  • 웹을 graph로 정의하고 일부 노드에서 시작해서 BFS어디까지 탐색할 수 있을까?
  • 결과를 살펴보면 출발 node 노드 비중이 어느 시점을 기준으로 대부분 탐색할 수 있거나 조금 밖에 탐색할 수 없는 경우로 나타났다

• random node v에 대하여

  • Out(v): 1억(전체 node의 50%)
  • In(v): 1억(전체 node의 50%)
  • 가장 큰 SCC: 5천 6백만(전체 node의 28%)
  • 이러한 인사이트를 바탕으로 Bowtie structure를 그릴 수 있다

PageRank

• How to organize the web
• made by Google research

Ranking nodes on the graph

• 모든 웹 페이지 각각의 중요성은 저마다 다를 것이다
  • 신윤종의 깃헙 vs HuggingFace 깃헙
• 그래서, web graph를 활용하여 rank를 매겨보자
• Link analysis approaches
  • PageRank
  • Personalized PageRank
  • Random Walk with Restarts

Link as Votes

• IDEA: link(edge)는 민주주의적으로 투표로 따집시다
• link가 많은 page는 중요도가 높을 것이다!
• In-link를 중요도의 지표로 따져보자
  • 신윤종의 깃헙(팔로워 11명) vs HuggingFace 깃헙(Transformers만 해도 star 42만개)
• 모든 in-link가 중요할까?
  • 중요한 페이지에서 보낸 link가 다른 link보다 더 중요할 것이다
• Recursive question!

PageRank: The "Flow" Model

• 중요한 페이지에서 보낸 "투표"가 더 가치 있을 것이다
  • 각 link는 source page의 중요성 비율이다
  • 만약 page i의 중요도 $r_i$가 $d_i$ out link를 가지고 있을 때, 각 link는 $\frac{r_i}{d_i}$만큼의 vote 가중치를 가진다
  • page j의 중요도 $r_j$는 j의 in-link vote의 합이다 $r_j = \displaystyle\sum_{i→j}\frac{r_i}{d_i}$

Matrix Formulation

• Stochastic adjacency matrix M

  • page j는 out link {d_j}를 가진다고 하자
  • 만약 j에서 i로 링크가 연결된다면 ${M_{ij}} = \frac{1}{d_j}$
    • $M$의 column 하나의 sum은 1이다

• Rank vector r

  • $r_i$는 page i의 중요도를 의미한다
  • $\sum_{i}{r_i} = 1$

• flow equation ${r} = {M}\cdot{r}$
  

Random walk interpretation

• random web surfer
  • 특정 time t에 page i를 서핑하고 있다고 해보자
  • 다음 t+1에 uniformly random하게 결정된 out-link를 따라 page j로 이동한다
  • 이 과정을 무한히 반복한다

• $p(t)$: 전체 페이지 개수만큼의 벡터로, i째 원소는 time t에서 i에 도달할 확률을 의미한다

• time t+1에 어디에 있을까?

  • 균등확률로 랜덤하게 움직여보자 $p(t+1) = {M}\cdot{p(t)} = p(t)$ p(t)는 aP = a를 만족하는 stationary distribution 상태이다

• 앞서 배운 rank vector는 ${r} = {M}\cdot{r}$인데?

  • 따라서 r은 random walk에서 stationary distribution 상태이다

Eigenvector formulation

• ${r} = {M}\cdot{r}$ 에 따라 rank vector r은 stochastic web matrix M의 eigenvector임을 확인하였다

  • 임의의 node u에서 출발해서 random walk를 진행한다고 해보자 수식은 $r = \lim\limits_{i \to \infty}M(M(...M(M u)))$가 된다.

  • 좀더 풀어서 써보면 $r = Mu = M(M u) = M(M(M U) = M(M(...M(M u)))$

  • 그럼 우리의 pagerank를 쉽게 뽑을 수 있을 거 같다

Power iteration

• Power iteration; simple iterative scheme
  • 초기화: $r^{(0)} = [1/N, ..., 1/N]^T$ where N= # of nodes
  • 반복: $r^{(t+1)} = {M}\cdot{r^{(t)}}$
  • 기저: $|r^{(t+1)} - r^{(t)}|_1 < ε|$ (L1 norm)

PageRank: how to solve?

• 모든 노드마다 page rank를 초기화한다
• power iteartion으로 수렴할 때까지 반복한다

3 Questions

• 그래서 실제 그래프에서는 수렴하긴 하나?
• 수렴하면 우리가 원하는 모양으로 수렴하나?
• 결과는 합리적인가?

→그러니까 일반적인 상황에서 써먹을 수 있냐구

Problems

• Problem 1) 어떤 페이지는 막다른길이다

  • out-link가 없다
  • importance의 leakage를 유발한다
  • pagerank의 수렴에는 문제가 되지 않지만 pagerank score가 맘에 들지 않을 것이다

• Problem 2) Spider traps

  • 모든 out-link가 group에 속해있을 때 모든 importance는 해당 group이 모두 흡수해버린다
  • pagerank 수렴에 문제가 생긴다

    Solutions

• Spider traps의 해결책: 각 time마다 random sufer는 2가지 선택지가 생긴다

  • 확률 β는 link를 그대로 따라갈 확률이다
  • 확률 1-β는 연결되어있지 않는 랜덤한 page로 점프할 확률이다
  • 일반적으로 β는 0.8~0.9로 설정한다

• Dead ends 해결책:

  • Teleports: 막다른 길에 다다른 node에게 다른 node로 연결될 확률은 배분한다
    • dead ends node m이 다른 node로 갈 확률의 전체 합은 1이다

Google matrix

• Spider traps를 고려한 Pagerak 수식 ${r_{j}} = \displaystyle\sum_{i→j}β\frac{r_i}{d_i} + (1-β)\frac{1}{N}$

  • 이 수식은 $M$에 균등확률을 배정하는 전처리를 진행하여 dead ends 문제를 피할 수 있다.

• Google Matrix A ${A} = β M + (1-β)[\frac{1}{N}]_{N×N}$

  • 여전히 $r = {A}\cdot{r}$의 재귀적인 문제가 있지만 power iteration을 사용해준다

How do we actually compute PageRank?

Computing PageRank

• N = 10억 page
  • 각 entry마다 4byte를 쓴다고하자
  • pagerank r이 old, new 2종류가 합해서 8GB가 필요하다
• Google matrix A는 N*N크기이다
  • 개수만 해도 ${10}^{18}이다

Sparse Matrix formulation

• 수식을 재정의해보면 ${A} = β M + (1-β)[\frac{1}{N}]_{N}$
• M은 sparse matrix로 dead ends가 없다는 가정하에 10개의 링크가 각 노드마다 달려있다고하면 10N entries가 있다고 볼 수 있다
• 매 반복마다 pagerank 공식에 (1-β)/N의 상수를 각 $r^{new}$에 더하면 된다
• 다만 dead-ends가 우려되는 상황이라면 normalize해주자

Complete algorithm

• Input: Graph G and parameter β
• Output: Pagerank vector $r^{new}$
  • Set $r^{old}_j = \frac{1}{N}$
  • 수렴할 때까지 반복: $\displaystyle\sum_{j}|r^{new}_j - r^{old}_k| < ε$
    • $r'^{new}j = \displaystyle\sum{i→j}βr'^{new}_i / d_i$
    • in-link가 없는 경우에는 0
  • leaked pagerank 정보를 더해준다
    • $r^{new}_j = r'^{new}_j + (1-S / N)$

Node Proximity Measurement

• Bipartite graph에서의 pagerank는?
• 같은 종류끼리는 독립인데?

Proximity on graphs

• personalized pagerank: random walk로 계산해보자
• query nodes가 주어지면 random walk 수행
• restart proba가 주어지면 random walk를 처음부터 수행하게 됨
• 주어진 query nodes들이 가장 많이 방분한 node가 highest proximity를 보인다

Content 0. Intro

1. The Probelm : Graph Generation
2. Machine Learning for Graph Generation
3. GraphRNN : Generating Realistic Graphs
4. Applications and Open Questions

지난 강의에서는 Graph를 vector로 encoding하는 방법을 배웠습니다. Deep Graph Encoders 이번 강의에서는 graph를 generate하는 과정을 배우보겠습니다. Deep Graph Decoders encoding된 vector으로 부터 grpah structure를 생성할 수 있습니다.

1. The Probelm : Graph Generation

graph generation의 목표는 realistic한 grpah를 생성하는 것입니다. graph generation이 갖는 의의는 다음과 같습니다.

• Generation : graph 형성 과정에 대한 insight를 얻을 수 있습니다.
• Anomaly detection - 비정상적인 부분/동작이 발생하는 이유를 발견할 수 있습니다.
• Predictions - 과거로부터 미래를 예측할 수 있습니다.
• 새로운 구조를 발견할 수도 있습니다.
• Graph completion - many graphs are partially observed
• "What if" scenarios

graph generation의 목표에 따라 모델이 달라 질 수 있습니다. Task1 : Realistic graph generation ->reference graph와 동일한(유사한) graph를 만들어야 합니다. Task2 : Goal-directed graph generation -> 주어진 조건과 제약에 맞게 graph를 만들어야 합니다. (예.Drug molecule generation/optimization)

이번 강의에서는 Task1 : Realistic graph generation에 대한 내용을 주로 다루겠습니다.

Graph Generation을 사용하는 task의 대표적인 예는 Drug Discovery입니다. 기존 분자 구조를 완성하여 desired property에 최적화된 새로운 약물을 발견할 수 있습니다. 이외에도 Discovering novel sturctures, Network Science(Null momdels for realistic networks) 같은 분야에도 사용됩니다.

하지만, 그래프를 생성하는 작업은 그리 쉽지 않습니다. Grpah Generation은 왜 어려울까요?? output space가 크고 다양하기 때문입니다. $n$개의 node를 위해 $n^2$개의 값을 생성해야합니다. (인접행렬) 또한 7강에서 언급한 바와 같이, Graph의 표현은 고정되어있지 않습니다. 또한 정해진 순서도 없습니다. 같은 그래프이지만, node의 index가 다르면 다르게 표현되고, 이는 objective function으로 최적화하는데 어려움이 있습니다.

또한 복잡한 의존성(complex dependency)문제도 있습니다.(long-range dependencies) 만약 6개의 node가 있는 링 그래프를 생성하려면, 먼저 node가 있어야하고 그 node를 연결해야합니다. 연결하는 과정에서 우리가 현재 처리하고 있는 node의 수를 기억해야합니다. 그렇지않으면 우리가 원하는 조건을 만족하지 못할 수도 있습니다. it's hard to generate a graph with respect to some specific conditions.

2. Machine Learning for Graph Generation

Graph Generative Model은 말 그대로 graph를 생성하는 모델입니다. 특정graph의 구조와 특징을 잘 닮은 현실적인 그래프를 생성하려고 합니다. reference graph들의 확률분포 $p_{data}(G)$가 있을 때, $p_{data}(G)$와 유사한 $p_{model}(G)$을 만들면됩니다. $p_{data}(G)$에서 sampling한 graph들이 주어지고, 이 그래프들로 $p_{data}(G)$를 만들면, $p_{data}(G)$에서 generated graph를 sampling합니다. 만약 "어떤 특징을 가지고 있는 분자"들의 확률 분포를 $p_{data}(G)$라고 하면, 그 확률 분포에서 sampling해온 reference graph들은 동일한 "어떤 특징"을 가지고 있을것입니다. $p_{data}$와 비슷하도록 학습된 $p_{model}$에서 sampling한 generated graph들도 "어떤 특징"을 가지고 있도록 하는것이 generation의 목표입니다. graph 도메인에서의 generative model은 graph의 node를 생성하는 것이 아닌, 전체 graph를 생성합니다.

Recap : Generative Model

Generative Model의 개념을 알아보겠습니다. 앞서 말씀드린 바와 같이 Generative Model의 목표는 기존 data의 확률분포 $P_{data}$와 유사한 $P_{model}$을 만드는 것입니다. 우리는 $P_{data}$에서 온 data $xP_{data}$만 있을 뿐, $P_{data}$가 무엇인지 모릅니다. 학습 데이터로 모델 분포에 최적으로 근사시키는 변수 $\theta$를 찾게됩니다. 이는 결합확률 함수 형태로 표현 가능하며, 수치해석이 쉽도록 log 공간으로 변형시켜 maximum likliehood문제로 풀게됩니다. 대부분의 생성모델에서는 noise distribution에서 $z$를 sampling해옵니다. $z_i$N(0,1) Deep Neural Net으로 decoding하여 원하는 data를 생성합니다. $x_i=f(z_i;\theta)$

생성모델에는 많은 종류가 있는데, 오늘 배울 Graph Generation은 Auto-regressive model을 사용합니다. Tractable Density를 추정합니다. fully visible brief network의 일종으로, density를 명시하고 시작하며 likelihood $p(x)$를 모델링합니다. chain rule을 통해 graph내의 모든 action(add node, add edge)에 대한 joint likelihood는 모든 action의 likelihood의 곱의 형태가 됩니다.

3. GraphRNN : Generating Realistic Graphs

idea : node와 edge를 sequencial하게 추가하면서 graph를 생성합니다.

• $\pi$ : node ordering(Graph의 node순서). Random으로 결정됩니다.
• $S^{\pi}$ : Graph의 node의 연결 sequence graph $G$ with node ordering $\pi$ can be uniquely mapped into a sequence of node and edge additions $S^{\pi}$ (예. 1~5까지의 숫자를 가진 5개의 node의 sequence)

graph $G$의 node ordering $\pi$가 결정되면, sequence $S$는 unique하게 결정됩니다. $S^{\pi}$의 원소 $S^{\pi}_n$은 모두 작은 graph입니다. 노드의 순서가 고정되면 전체 그래프를 생성하는 방법은 하나뿐입니다.

sequence $S^{\pi}$은 두 가지 level로 나뉩니다.

• Node-level : 새로운 node를 하나 추가합니다.
• Edge-level : 추가된 node와 기존 node를 잇는 edge(link)를 추가합니다. node-level을 한번 upedate하면, 그 node에 해당하는 edge-level을 update하고, 그 다음 node를 추가하는 node-level을 update하고 다시 edge-level을 update하는 과정을 반복합니다.

node-level squence의 요소마다 edge-level sequence가 있으므로, squence of sequence라고 합니다. graph generation문제를 sequence generation문제로 볼 수 있습니다. sequence generation은 두 단계로 나뉩니다.

• Generate a state for a new node (Node-level sequence)
• Generate edge for the new node based on its state (Edge-level sequence)

sequence 생성이기 때문에 Recurrent Neural Network로 해결할 수 있습니다.

GraphRNN

GraphRNN은 두단계로 나뉩니다.

• node-level RNN : 새로운 node를 만들고, 만들어진 node는 edge-level RNN의 initial state가 됩니다.
• edge-level RNN : 이전 방법대로 한다면 Node 5를 생성할 때, Node 1~4까지의 모든 연결을 고려해야했습니다. 하지만 이제 새로운 node의 edge를 만듭니다. 만들어진 edge는 node-level RNN의 state를 update합니다.

이제 RNN으로 sequence를 만드는 방법에 대해 자세하게 알아보겠습니다. (RNN,LSTM,GRU...)

• $s_t$ : state for RNN after time $t$
• $x_t$ : input to RNN after time $t$
• $y_t$ : output of RNN after time $t$
• $W,U,V$ : parameter matrices
• $\sigma()$ : non-linearlity Auto-regressive model이기 때문에 이전 cell의 output이 다음 cell의 input으로 들어가는 구조이므로 $x_{t+1}=y_t$입니다. 또한 처음 state와 처음 input인 $s_0,x_1$은 SOS(Start Of Sequence) start tocken으로 지정해주고, end tocken인 EOS(End Of Sequence)로 생성을 멈춰줍니다. (SOS,EOS $\rightarrow$ zero vector) 하지만, 이렇게 $x_{t+1}=y_t$이라면 모델이 deterministic하여 같은 graph만 생성될 것입니다. (diversity가 없다.) 따라서 이전 cell의 output을 다음 cell의 input으로 바로 넣어주는 것이 아닌, $y_t$로 확률을 출력하여, 그 확률 분포에 맞게 $x_{t+1}$을 sampling해줍니다. $x_{t+1}~y_t$ RNN의 각 step의 output $y$는 확률 vector입니다.

Training

edge에 대한 Ground Truth(Adjacency matrix) $y^$로 *teacher forcing**을 합니다.

teacher forcing techer forcing이란, Ground Truth를 디코더의 다음 입력으로 넣어주는 기법입니다.

Loss

$y^={1,0,1,....}$ 로 Binary Cross Entropy를 계산합니다. $L=-[y^_1log(y_1) + (1-y^_1)log(1-y_1)]$ BCE를 minimize하는 방향으로 학습합니다. 실제값 $y^$=1이면 $y^_1log(y_1)$ term을 최소화하고, 실제값 $y^$==0이면 $(1-y^*_1)log(1-y_1)$ term을 최소화합니다.

training process

이 graph가 data로 주어졌습니다. Node 1이 graph에 있다고 가정하고, Node2를 추가해보겠습니다. Edge RNN은 Node 1과 Node 2사이의 edge를 예측합니다. 첫번째 Edge RNN cell에서 0.5의 확률을 output으로 출력했고, teacher forcing하기 때문에 실제 GT인 1을 다음 Edge RNN cell의 입력으로 넣어줍니다. Edge RNN에 GT가 supervision으로 오게됩니다. Edge RNN의 최종 output sequence {1}을 Node RNN의 입력으로 주어 다음 node level(Node 3)로 update합니다. 다음으로 Edge RNN은 새로운 노드 Node 3와 기존 Node들이 연결되어있는지 확인합니다. 역시 Edge RNN에서는 teacher forcing을 해줍니다. 다음으로 GT를 supervision으로 줍니다. Edge RNN의 output인 결과를 Node RNN의 입력으로 보내줍니다. 동일하게 Edge RNN에서 edge에 대한 확률값을 예측하는데, Node 4는 아무 node와 연결되어있지 않으므로 graph 생성을 중단합니다. reference graph (GT)를 가지고 BCE loss를 사용하여 전체 RNN layer에 대해 backprob을 진행합니다.

Test

Edge RNN의 output으로 나온 확률이 threshold이상일 경우 1, 반대의 경우에는 0값을 얻을 수 있습니다. GT가 없기 때문에, 이전 Edge RNNcell의 결과인 1 또는 0값이 다음 Edge RNN cell의 input으로 들어갑니다.

GraphRNN을 정리하자면, graph 생성은 node-level sequence과 edge-level sequence 두 단계로 진행되며, RNN을 사용하여 sequnce를 생성합니다.

Issue : Tractability

어느 node든지 모든 node와 연결될 수 있습니다. edge generation을 하기에 많은 단계를 거쳐야 합니다. 우선 전체 adjacency matrix가 필요하고, edge의 종속성이 너무 길어져 복잡해집니다. 이러한 한계를 해결하기 위해 BFS를 사용합니다.

기존 Random node ordering

Node 5 may connect to any/all previous nodes

• Node 1을 놓는다.
• Node 2를 놓는다.
• Node 2와 Node 1의 edge를 확률에 따라 생성한다.
• Node 3를 놓는다
• Node 3와 Node 2, Node 1의 edge를 확률에 따라 생성한다.
• Node 4를 놓는다. ......

BFS node ordering

• Node 4와 Node 1은 연결되어있지 않기 때문에, 어쩌라고...

BFS node ordering을 적용한 결과 Node ordering과 Edge generation 모두 시간복잡도가 대폭 줄게됩니다.

Evaluating Generated Graphs

GraphRNN같은 graph generative model로 생성한 graph가 reference와 얼마나 유사한지 어떻게 측정할 수 있을까요?? 어느 그래프에나 적용할 수 있는 효율성있는 Graph Isomorphism test가 없습니다. 따라서 Visual similarity와 Graph statistics similarity로 두 그래프의 유사한 정도를 판단합니다.

4. Applications and Open Questions

GraphRNN은 앞서 한번 언급한 Drug Discovery에 사용될 수 있습니다.

• 주어진 목적에 따라 모델을 최적화 시켜야 합니다.(High score)
• 주어진 제약 조건을 지켜야합니다.(Valid)
• 실제 그래프 데이로부터 학습을 해야합니다.(Realisitc)

특정 요구 사항, 주어진 화학적 특성의 높은 점수, 화학적 valency와 realistic을 만족하도록, 세가지 다른 방향으로 접근을 했습니다.

• GCN + 강화학습
• adversarial training
• Policy Network in 강화학습

Drug Discovery에 대표적으로 사용되지만, graph generation은 아직 open problem이 많습니다.

• 3D,point cloud,scene graph같은 다른 domain에서의 graph generation
• 큰 그래프 생성
• Anomaly detection (예. real graph vs fake graph)

이번강의에서는 Graph Generation에 의의와 문제, ML으로 Graph를 생성하는 GraphRNN을 배워보았습니다.

Reference

https://zhuanlan.zhihu.com/p/147675627 https://tobigs.gitbook.io/tobigs-graph-study/chapter10.

PyTorch Geometric

torch-geometric : GNN implementation module

• Docs : https://pytorch-geometric.readthedocs.io/en/latest/modules/nn.html
• git : https://github.com/rusty1s/pytorch_geometric

• torch_geometric.nn : GNN Layer
• torch_geometric.utils : Loss / Evaluation Metrics / Utility Function
• torch_geometric.transforms : Transform Data
• networkx : Visualize Graph Structure

torch_geometric.data.Data : Graph Attributes

• data.x : node feature matrix , [num_nodes, num_node_features]
• data.edge_index : graph connectivity , [2, num_edges]
• data.edge_attr : edge attribute matrix , [num_edges, num_edge_features]
• data.y : Graph or node targets
  • graph level : [num_nodes, *]
  • node label : [1, *]

Setup

# install 

!pip install --verbose --no-cache-dir torch-scatter
!pip install --verbose --no-cache-dir torch-sparse
!pip install --verbose --no-cache-dir torch-cluster
!pip install torch-geometric 
!pip install tensorboardX
!wget https://bin.equinox.io/c/4VmDzA7iaHb/ngrok-stable-linux-amd64.zip
!unzip ngrok-stable-linux-amd64.zip

import torch
import torch.nn as nn
import torch.nn.functional as F

import torch_geometric.nn as pyg_nn        # GNN module 
import torch_geometric.utils as pyg_utils  # GNN Utility Function
import torch_geometric.transforms as T


import time
from datetime import datetime

import networkx as nx                      # visualize Graph Structure 
import numpy as np
import torch
import torch.optim as optim

# dataset 
from torch_geometric.datasets import TUDataset
from torch_geometric.datasets import Planetoid
from torch_geometric.data import DataLoader

# visualize 
from tensorboardX import SummaryWriter     
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt

Define the Model

1. torch_geometric

class GNNStack(nn.Module):      # stacking of Graph Convolutions 
    def __init__(self, input_dim, hidden_dim, output_dim, task='node'):
        super(GNNStack, self).__init__()
        self.task = task
        # nn.ModuleList() : nn.Module()을 list로 정리! 각 layer를 list로 전달하고, layer의 iterator를 만듭니다. 
        self.convs = nn.ModuleList()    
        self.convs.append(self.build_conv_model(input_dim, hidden_dim))
        self.lns = nn.ModuleList()
        self.lns.append(nn.LayerNorm(hidden_dim))
        self.lns.append(nn.LayerNorm(hidden_dim))
        for l in range(2):
            self.convs.append(self.build_conv_model(hidden_dim, hidden_dim))

        # post-message-passing
        self.post_mp = nn.Sequential(
            nn.Linear(hidden_dim, hidden_dim), nn.Dropout(0.25), 
            nn.Linear(hidden_dim, output_dim))
        if not (self.task == 'node' or self.task == 'graph'):
            raise RuntimeError('Unknown task.')

        self.dropout = 0.25
        self.num_layers = 3

    # task에 따른 convolution layer를 만들어 줍니다. 
    def build_conv_model(self, input_dim, hidden_dim):
        # refer to pytorch geometric nn module for different implementation of GNNs.
        if self.task == 'node':  # node classification 
            return pyg_nn.GCNConv(input_dim, hidden_dim)
            # return CustomConv(input_dim, hidden_dim) : run my method 
        else:
            return pyg_nn.GINConv(nn.Sequential(nn.Linear(input_dim, hidden_dim),
                                  nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)))

    def forward(self, data):
        '''
        x : feature matrix (# of nodes, # of node feature dim) 
        edge_index : sparse adj list, 연결된 edge에 대한 node 저장  
                     ex. node 1 : [1,4,6]
        batch : (array) batch마다 node 개수가 달라지므로 -> 어떤 node가 어떤 graph에 속하는지에 대한 정보 저장 
                ex. [1,1,1,1,1] : 5 nodes in graph 1 , [2,2,2] : 3 nodes in graph 2 
        '''

        x, edge_index, batch = data.x, data.edge_index, data.batch
        if data.num_node_features == 0:         # feature 없으면 -> constant 
          x = torch.ones(data.num_nodes, 1)

        # Neural Network 
        for i in range(self.num_layers):
            x = self.convs[i](x, edge_index)    # Conv Layer 
            emb = x
            x = F.relu(x)
            x = F.dropout(x, p=self.dropout, training=self.training)
            if not i == self.num_layers - 1:
                x = self.lns[i](x)

        if self.task == 'graph':                # mean pooling : average all the nodes 
            x = pyg_nn.global_mean_pool(x, batch)

        x = self.post_mp(x)

        return emb, F.log_softmax(x, dim=1)     

    def loss(self, pred, label):
        return F.nll_loss(pred, label)          # negative log-likelihood 

2. Custom Model

class CustomConv(pyg_nn.MessagePassing):    # inherenting from MessagePassing 
    def __init__(self, in_channels, out_channels):
        super(CustomConv, self).__init__(aggr='add')  # Neighborhood Aggregation : Mean, Max, Add, ... 
        self.lin = nn.Linear(in_channels, out_channels)
        self.lin_self = nn.Linear(in_channels, out_channels)

    def forward(self, x, edge_index):
        '''
        x : feature matrix 
        edge_index : connectivity, Adj list in the edge index  
        '''

        # x has shape [N, in_channels]
        # edge_index has shape [2, E]

        # original code 
        # Add self-loops to the adjacency matrix : neighbor + self 
        # pyg_utils.add_self_loops(edge_index, num_nodes = x.size(0))   # A + I 

        # 여기에서는 remove self-loops : skip layer on top of that 
        edge_index, _ = pyg_utils.remove_self_loops(edge_index)    

        # Transform node feature matrix.
        self_x = self.lin_self(x)   # B 
        # x = self.lin(x)           # W 

        return self_x + self.propagate(edge_index, size=(x.size(0), x.size(0)), x=self.lin(x))

    def message(self, x_i, x_j, edge_index, size):
        '''
        GCN : D^(-1/2)*A*D(1/2)*W*X
        x_i : self  
        x_j : neighborhood 
        '''

        # Compute messages
        # x_j has shape [E, out_channels]

        row, col = edge_index
        deg = pyg_utils.degree(row, size[0], dtype=x_j.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]

        return x_j

    def update(self, aggr_out):
        # aggr_out has shape [N, out_channels] : add additional layer after message passing 

        # GraphSAGE : L2 Normalization 
        # F.normalize(aggr_out, p=2, dim=-1) 

        return aggr_out

# Custom Model 을 사용하는 경우, GNNStack class 내의 build_conv_model return 값을 다음과 같이 수정해 주면 됩니다. 

    def build_conv_model(self, input_dim, hidden_dim):
        # refer to pytorch geometric nn module for different implementation of GNNs.
        if self.task == 'node':
            # return pyg_nn.GCNConv(input_dim, hidden_dim)
            return CustomConv(input_dim, hidden_dim) # run my method 
        else:
            return pyg_nn.GINConv(nn.Sequential(nn.Linear(input_dim, hidden_dim),
                                  nn.ReLU(), nn.Linear(hidden_dim, hidden_dim)))

Model

Training Setup

Train

def train(dataset, task, writer):
    if task == 'graph':
        data_size = len(dataset)
        loader = DataLoader(dataset[:int(data_size * 0.8)], batch_size=64, shuffle=True)
        test_loader = DataLoader(dataset[int(data_size * 0.8):], batch_size=64, shuffle=True)
    else:
        test_loader = loader = DataLoader(dataset, batch_size=64, shuffle=True)

    # build model
    model = GNNStack(max(dataset.num_node_features, 1), 32, dataset.num_classes, task=task)
    opt = optim.Adam(model.parameters(), lr=0.01)

    # train
    for epoch in range(200):
        total_loss = 0
        model.train()
        for batch in loader:
            #print(batch.train_mask, '----')
            opt.zero_grad()
            embedding, pred = model(batch)
            label = batch.y
            if task == 'node':
                pred = pred[batch.train_mask]
                label = label[batch.train_mask]
            loss = model.loss(pred, label)
            loss.backward()
            opt.step()
            total_loss += loss.item() * batch.num_graphs
        total_loss /= len(loader.dataset)
        writer.add_scalar("loss", total_loss, epoch)

        if epoch % 10 == 0:
            test_acc = test(test_loader, model)
            print("Epoch {}. Loss: {:.4f}. Test accuracy: {:.4f}".format(
                epoch, total_loss, test_acc))
            writer.add_scalar("test accuracy", test_acc, epoch)

    return model

Validation / Test

def test(loader, model, is_validation=False):
    model.eval()

    correct = 0
    for data in loader:
        with torch.no_grad():
            emb, pred = model(data)
            pred = pred.argmax(dim=1)
            label = data.y

        # mask 를 통해 validation, test 결정 
        if model.task == 'node':
            mask = data.val_mask if is_validation else data.test_mask
            # node classification: only evaluate on nodes in test set
            pred = pred[mask]
            label = data.y[mask]

        correct += pred.eq(label).sum().item()

    if model.task == 'graph':
        total = len(loader.dataset) 
    else:
        total = 0
        for data in loader.dataset:
            total += torch.sum(data.test_mask).item()
    return correct / total

Training the Model

# Setting TensorboardX in Colab 
get_ipython().system_raw(
    'tensorboard --logdir {} --host 0.0.0.0 --port 6006 &'
    .format("./log")
)
get_ipython().system_raw('./ngrok http 6006 &')
!curl -s http://localhost:4040/api/tunnels | python3 -c \
    "import sys, json; print(json.load(sys.stdin)['tunnels'][0]['public_url'])"

Visualize Node Embeddings

color_list = ["crimson", "orange", "green", "royalblue", "purple", "dimgrey", "gold"]

loader = DataLoader(dataset, batch_size=64, shuffle=True)
embs = []
colors = []
for batch in loader:
    emb, pred = model(batch)
    embs.append(emb)
    colors += [color_list[y] for y in batch.y]
embs = torch.cat(embs, dim=0)

xs, ys = zip(*TSNE().fit_transform(embs.detach().numpy()))

plt.figure(figsize=(10, 8))
plt.scatter(xs, ys, color=colors, alpha=0.5)

Learning Unsupervised Embeddings with Graph AutoEncoders

# VGAE : variational graph auto-encoder
# Knowledge Graph, Graph Reasoning 

class Encoder(torch.nn.Module):
    '''
    Encoder : Graph Conv to get embeddings 
    Decoder : inner product -> 2개 node 사이의 값이 크면, there's a likely link between them 
    '''

    def __init__(self, in_channels, out_channels):
        super(Encoder, self).__init__()
        self.conv1 = pyg_nn.GCNConv(in_channels, 2 * out_channels, cached=True)
        self.conv2 = pyg_nn.GCNConv(2 * out_channels, out_channels, cached=True)

    def forward(self, x, edge_index):
        x = F.relu(self.conv1(x, edge_index))
        return self.conv2(x, edge_index)

def train(epoch):
    model.train()
    optimizer.zero_grad()
    z = model.encode(x, train_pos_edge_index)
    loss = model.recon_loss(z, train_pos_edge_index)    # reconstruction loss 
    loss.backward()
    optimizer.step()

    writer.add_scalar("loss", loss.item(), epoch)

def test(pos_edge_index, neg_edge_index):
    model.eval()
    with torch.no_grad():
        z = model.encode(x, train_pos_edge_index)
    return model.test(z, pos_edge_index, neg_edge_index)

writer = SummaryWriter("./log/" + datetime.now().strftime("%Y%m%d-%H%M%S"))

dataset = Planetoid("/tmp/citeseer", "Citeseer", transform = T.NormalizeFeatures())
data = dataset[0]

channels = 16
dev = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
print('CUDA availability:', torch.cuda.is_available())

# encoder: written by us; decoder: default (inner product)
model = pyg_nn.GAE(Encoder(dataset.num_features, channels)).to(dev)
labels = data.y
data.train_mask = data.val_mask = data.test_mask = data.y = None

# data = model.split_edges(data) # split_edges 안 돌아가서 변경!  
data = pyg_utils.train_test_split_edges(data)   # construct positive/negative edges (for negative sampling!)
x, train_pos_edge_index = data.x.to(dev), data.train_pos_edge_index.to(dev)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)

for epoch in range(1, 201):
    train(epoch)
    auc, ap = test(data.test_pos_edge_index, data.test_neg_edge_index)
    writer.add_scalar("AUC", auc, epoch)
    writer.add_scalar("AP", ap, epoch)
    if epoch % 10 == 0:
        print('Epoch: {:03d}, AUC: {:.4f}, AP: {:.4f}'.format(epoch, auc, ap))

model.eval()
z = model.encode(x, train_pos_edge_index)
colors = [color_list[y] for y in labels]

xs, ys = zip(*TSNE().fit_transform(z.cpu().detach().numpy()))

plt.figure(figsize=(10, 8))
plt.scatter(xs, ys, color=colors, alpha=0.5)
plt.show()

Reference

1. Tobigs Graph Study : Chapter9. Graph Neural Networks:Hands-on Session
2. 예제를 통해 알아보는 PyTorch Geometric 5 Basic Concepts
3. Lecture 7. Graph Neural Networks - 2: Design Space

Contents

0. Intro

1. Deep Learning for Graphs
2. Graph Convolutional Network
3. Graph Attention Network
4. Application

Keyword : Deep Learning on Graph , Neighborhood Aggregation , GNN , GCN , GAT

0. Intro

Node Embedding

7강에서는 Node Embedding 에 대해 공부했습니다. embedding node ($z_u$, $z_v$) 사이의 관계가 original network node ($u$, $v$) 사이의 관계 (Similarity) 를 가장 잘 표현해 주는 encoder ($ENC(⋅)$) 를 찾는 방법을 배웠습니다.

From "Shallow" to "Deep"

이 때 Shallow Encoder (Lookup table) 를 공부했습니다. Shallow Encoder는 single layer ($f$) 로 구성되어 있으며, 이를 통해 node embedding 을 진행하고 ($u$ → $z_u$), similarity (${z_v}^T z_u$) 를 계산합니다.

Limitations of Shallow Embedding

1. $O(|V|)$ parameters are needed
   • parameter 개수 = # of nodes node 끼리 parameter 를 공유하지 않습니다.
   • 각 node 들은 unique embedding 값을 가지게 됩니다.
2. Inherently "transductive"
   • I have to re-embed everything
   • train 과정에서 보지 않은 node/embedding 을 generalize 할 수 없습니다.
3. Do not incorporate node features
   • node attribute feature 를 사용하지 않습니다.

Deep Graph Encoders

따라서 위의 한계를 극복하고자, multiple layer 로 구성된 Deep Encoder 를 고려하게 됩니다.

Challenges

Graph Network 를 Deep Neural Network 구조에 통과시켜서, node embedding (good prediction) 을 만들어 내고 싶지만, 이는 쉽지 않습니다.

단순하게 Deep Learning을 적용하기에는, 실제 Network가 매우 복잡하기 때문입니다.

• 현존하는 ML/DL ToolBox 는 Image (Grids = Fixed Size Graph) & Text (Sequences = Line Graph) 에 특화되어 있습니다.
• Network는 위상학적으로 매우 복잡한 구조를 가지고 있습니다.
• node들은 고정된 순서 & 기준점이 없습니다.
• dynamic 하며, Multimodal features를 갖는 경우도 있습니다.

A Naive Approach

Adjacency matrix 와 Feature vector 를 concat 해서 Deep Neural Network 의 input 으로 넣는 방법 또한 적용이 어렵습니다.

Issues

1. $O(N)$ : parameter 개수 (node + feature) 가 많아집니다.
2. different size 의 graph 에 적용할 수 없습니다.
3. node 의 순서가 바뀌면, 의미가 달라질 수 있습니다.
   • Adj node 의 ordering 이 shuffle 될 수도 있습니다.
     • 2 additional feature node 를 어디에 넣어야 할지 모호해집니다.

idea : Convolutional Networks

Convolutional 연산의 원리는 위와 같습니다. sliding window 통해 얻은 정보를 다 더하여, output 을 도출합니다.

$(f \ast g)(t) = \int_{a}^{b} f(\tau) g(t-\tau) , d\tau$

neighborhood 의 message 를 collect 하여, node 의 message 와 combine 하고, 이를 통해 new value 를 produce 하고자 합니다.

이러한 과정을 가장 잘 수행할 수 있는 연산 방법이 ConV 이기 때문에, Convolutional 을 graph 에 적용해서, information 을 aggregate 하고자 합니다.

1. Deep Learning for Graphs

Setup

graph $G$ 에 대하여,

• $V$ : vertex set = node 집합
• $A$ : Adjacency matrix = 인접행렬
• $X$ : Node Feature matrix

Graph Convolutional Networks

Learn how to propagate information across the graph to compute node features

node i 에 대한 prediction 을 하고 싶을 때,

1. node computation graph 를 결정하고,
2. neighborhood information 을 propagate 하고 aggregate 합니다.

Aggregate Neighbors

Key idea

Local Network Neighborhoods 정보를 기반으로 node embedding 을 진행합니다.

• node B 는 A, C 로 부터, node A 는 B, C, D 로 부터 정보를 얻습니다.
• Graph 에서는 4~5 level 이상의 Layer를 쌓지 않는데, (Ch2 MSN 예시에서도 path length = 6.6 이었듯이) Depth 6 정도면 graph 내의 모든 node 를 방문할 수 있기 때문입니다.

Intuition 1

Neural Network 를 통해 neighborhood information 을 aggregate 합니다.

Intuition 2

neighborhood 가 computation graph 를 결정합니다. 모든 node들은 자기 자신만의 Neural Network Architecture 를 갖고 있으며, 각자의 neighborhood에 근거하여 computation graph를 정의합니다.

Neighborhood Aggregation

Neighbors 로 부터 정보를 모아 Average 한 뒤, Neural Network 를 적용합니다.

Models

Deep Layer Model

Model의 depth는 자유롭게 설정할 수 있습니다.

• Node는 각 layer에서 embedding 값을 가지게 됩니다.
• Layer-0에서의 node A의 embedding 은 $X_A$ 가 됩니다.
• Layer-K에서의 embedding 은, Layer-0 에서 시작하여 Hidden Layer를 거쳐 K번 전달된 정보에 대한 값을 가지게 됩니다.

Deep Encoder

정보가 전달되어 embedding 값을 가지게 되는 과정을 수식적으로 표현하면 위와 같습니다.

• W : Average of neighbor's previous layer embeddings
• B : Message myself from the previous layer

Training the Model

위의 식에서, Train의 대상은 Weight Matrix 인 W 와 B 입니다. W 와 B 비율을 통해, friend / own property 중 어디에 더욱 주목할 지 결정합니다.

• W ↑ , B ↓ : Neighbor 정보 더욱 많이 고려
• W ↓ , B ↑ : 이전 레이어의 자신의 정보를 더욱 많이 고려

embedding 값은 어떠한 loss function에도 적용 가능하며, Stochastic Gradient Descent 를 통해 Weight를 update 합니다.

Loss Function은 Task에 따라 달라집니다.

1. Unsupervised Training

Task : graph structure 를 고려한 node embedding

• node u 와 node v 가 similar 할 때, $y_{u,v} = 1$ 이 됩니다.
• CE : Cross Entropy
• DEC : Decoder (ex. inner product)
• Loss Function : Random Walks, Graph Factorization, Node Proximity in the Graph

2. Supervised Training

Task : node classification

• Cross Entropy Loss
• $y_v$ : ground-truth label
• Positive node 라면 $\sigma({z_v}^T\theta)$ 값이 커지고, Negative node 라면 $1 - \sigma({z_v}^T\theta)$ 값이 커지게 됩니다.

Overview

Parameter Sharing

The same aggregation parameters are shared for all nodes new nodes & new graphs 에 대해서도, generalize 가능합니다.

Summary

Generate node embeddings by aggregating neighborhood information

Graph Neural Network

Layer에서 Neighborhood 와 자기 자신의 message 를 Aggregate 하여 embedding 을 만들고, 이를 전달하여 최종 target node의 embedding 을 만드는 것입니다.

2. Graph Convolutional Network (GCN)

Matrix Formulation

k-1 hidden layer에서 information aggregation을 통해 k hidden layer 로 전달하는 Neighborhood Aggregation 식은 위와 같습니다.

$A$ (인접행렬)은 node 연결 여부에 대한 정보(0/1)를 담고 있는 행렬입니다. 따라서 $AH^{(l)}$ 는 node i 와 relationship이 있는 state 값만 더한 값으로 update 한다는 의미입니다.
여기에 $D^{-1}$을 곱해 row normalized matrix 를 만들어 냅니다.

Neighborhood Aggregation 식을 vector form 으로 표현하면 위와 같습니다.

Graph Convolutional Networks

idea

1. neighborhood aggregate 에는 $W_k$ 를 사용하였고, previous self embedding 에는 $B_k$ 를 곱했는데 → GCN 에서는 neighbor 와 self 모두에 대해 동일한 parameter 인 $W_k$ 를 사용합니다.

2. 인접행렬($A$)을 사용하게 되면 자기 자신으로의 연결을 고려하지 않게 되므로 → self-connection을 추가한 $\hat{A} = A + I_N$ 행렬을 사용합니다.

3. 단순히 neighborhood 정보의 평균 ($D^{-1} A$)을 구하지 않고 → neighborhood aggregation 에 symmetric normalization ($D^{-1/2} A D^{1/2}$)을 적용하여 계산합니다.

$f(H^{(l)}, A) = \sigma ({\hat{D}}^{-\frac{1}{2}}\hat{A}{\hat{D}}^{\frac{1}{2}}H^{(l)}W^{(l)})$

1. graph 에서 $\hat{A}$, $\hat{D}$ 를 얻습니다.
2. 각 node에 연결된 edge 개수에 대해 normalization 을 진행합니다.
3. l번째 hidden state 인 $H^{(l)}$ 을 곱합니다.
4. 학습 가능한 parameter $W^{(l)}$ 을 곱합니다.
5. activation function $\sigma$ 를 거쳐 비선형성을 학습합니다.

Output : 인접 노드들의 가중치 $\ast$ feature vector $\ast$ W의 합 즉, GCN은 특정 node의 representation으로, 해당 node에 연결되어 있는 node들을 가중합하는 방법입니다.

GraphSAGE

idea

1. Concatenate neighbor embedding & self embedding
2. 다양한 Aggregation 방법론을 적용합니다.

• GCN : neighbor 과 self 의 message 를 더합니다. GraphSAGE : neighbor 과 self 의 message 를 concat 합니다.

• Aggregation 방법은 여러 가지가 있습니다.

3. Graph Attention Network (GAT)

각 neighborhood node들의 중요도를 같다고 보지 않고 ($\neq \frac{1}{|N(v)|}$), attention coefficients $e_{vu}$ 를 적용해 neighborhood node 마다 가중치를 다르게 적용합니다.

Attention Mechanism in NLP

출력 값을 예측할 때, encoder의 모든 입력 단어들의 정보(확률값)를 다시 한번 참고하여 손실했던 정보를 반영합니다.

1. $e^t = [{s_t}^T h_1, {s_t}^T h_2, ... , {s_t}^T h_N]$ encoder 에서 나온 hidden state 에, 현재 시점 t에서의 decoder hidden state 값을 dot product 연산을 통해 구합니다.
2. $a^t = softmax(e^t)$ attention distribution 을 구합니다.
3. $a_t = \sum\limits_{i=1}^N a_i^t h_i$ encoder의 hidden state와 Attention Weights를 곱하고, Weighted Sum 합니다.
4. $v_t$ = concat($a_t$, $s_t$) attention value 와 decoder hidden state 값을 concat 한 후, 최종 layer 를 통과하여 output 을 계산합니다.

Attention Mechanism in Graph

PROCESS

$e_{vu}$ 를 통해서 노드 $u$에서 노드 $v$로 가는 message importance 를 계산합니다.

각 node 의 hidden state 값이 concat 되고, linear 를 거쳐 attention coefficient $e_{vu}$ 가 계산됩니다.

softmax 함수 를 거치고, 이를 통해 나온 값 $\alpha_{vu}$ 을 곱해 가중합 하여 $h_v^{(l)}$ 을 계산합니다.

Multi-head attention 을 통해 값을 여러 개 도출하여, 이를 aggregate 해서 최종 output을 계산합니다. ✔︎ Multi-head attention : 서로 다른 attention mechanism을 여러 번 계산하여, input을 여러 관점(head)에서 해석

Allows for (implicitly) specifying different importance values to different neighbors

Experiments

MLP 보다는 Random Walk 가, 이보다는 GCN 과 GAT 가 훨씬 성능이 좋다고 합니다.

4. Application

Pinterest

Graph 를 이용해서 더 나은 Recommendation 결과를 도출합니다.

PinSAGE

visual 로만 구분하면, fence 와 bed 를 제대로 구분할 수 없게 됩니다. 따라서 Image 와 이를 한 곳에 모아 놓은 Pins 를 node 로 하여, bipartite graph 를 구축해 좀 더 나은 추천 결과를 도출합니다.

node v image 를 embedding 하여, similar 한 node u 를 찾고, node u의 neighbor 를 추천해 줍니다.

Graph 적용 시 훨씬 좋은 추천 결과를 보인다고 합니다.

Reference

Reviews

1. Tobigs Graph Study : Chapter8. Graph Neural Networks
2. 데이터 괴짜님 Review : CS224W - 08.Graph Neural Networks
3. snap-stanford Review : Graph Neural Networks

CS224 Winter 2021

1. Lecture 6. Graph Neural Networks - 1: GNN Model
2. Lecture 7. Graph Neural Networks - 2: Design Space

GCN

1. Paper : Semi-Supervised Classification with Graph Convolutional Networks
2. Review : Graph Convolutional Networks
3. PyTorch Code : tkipf/pygcn
4. reference links
5. GraphSAGE : Inductive Representation Learning on Large Graphs

GAT

1. Paper : Graph Attention Networks
2. PyTorch Code : Diego999/pyGAT
3. reference links

etc.

1. 컨볼루션(Convolution) 이해하기
2. jihoon님 Review : Graph Neural Network
3. Deep Learning on Graphs with Graph Convolutional Networks
4. Interpretation of Symmetric Normalised Graph Adjacency Matrix?
5. lee-ganghee님 Review : GNN, GCN 개념정리
6. wikidocs : 어텐션 메커니즘 (Attention Mechanism)
7. Yeongmin님 GCN Paper Review : Graph Convolutional Networks Review

Contents

0. Intro

1. Embedding Nodes
2. Random Walk Approaches to Node Embeddings
3. Translating Embeddings for Modeling Multi-relation Data
4. Embedding Entire Graphs

0.Intro

이번 강의는 graph domain에서의 representation learning에 대해 알아보겠습니다.

representation learning이란, 어떤 task를 수행하기에 적절하게 데이터의 representation을 변형하는 방법을 학습하는 것입니다. 즉 어떤 task를 더 쉽게 수행할 수 있는 표현을 만드는 것입니다. Raw data에 많은 feature engineering과정을 거치지 않고 데이터의 구조를 학습하는 것으로, 딥러닝 아키텍처의 핵심요소라고 할 수 있습니다. 입력 데이터의 최적의 representation을 결정해주고 이 잠재된 representation을 찾는 것을 representation learning 또는 feature learning이라고 부릅니다.

grpah에서의 representation learning 역시 같은 의미입니다. graph의 node $u$를 mapping function $f$를 통해 Latent space(=embedding space)로 embedding할 수 있습니다. graph의 feature representation(=embedding)을 통해 다양한 task를 효과적으로 수행할 수 있습니다. 이때 효과적인 representation이란, task에 specific하지 않고 다양한 task에도 적용할 수 있는 representation을 의미합니다.

그렇다면 왜 graph를 Embedding해야 할까요?? graph의 인접행렬(Adjacency Matrix)는 각 column이 node를 의미하기 때문에 sparse하고 크기 매우 큽니다. 인접행렬을 그대로 다루기에는 computation 측면에서 문제가 있습니다. 그렇기 때문에 grpah의 각 node를 low-dimension으로 mapping할 필요가 있습니다. Adjacency Matrix의 dimension보다 dimension이 낮은 Latent Dimension으로 embedding하여 computation의 효과를 얻을 수 있습니다. 각 node를 embedding하는 것이기 때문에 node별 representation이 가능합니다. 단, 각 column이 node를 나타내는 adjacency matirx와는 다르게, latent demension에서 나타낼 수 있는 embedding matrix의 column은 각 node를 나타내지는 않습니다. latent demension의 축들은 node가 아닌 node간의 상관관계와 같은 graph의 정보를 의미하는 feature가 됩니다. 즉, Adjacency matrix의 그래프 정보를 Latent Dimension으로 encoding하고, node representation을 만들어내는 것입니다. ** graph의 정보를 담았기 때문에, latent space상에서 나타내지는 node간의 similarity은 실제 graph에서의 node간의 similarty라고 볼 수 있습니다. ** 위 그림은 grpah를 2D latent space로 embedding한 예시입니다. 앞서 말씀드린것 처럼 각 node를 latent space에 mapping할 수 있고, latent space의 축은 node를 의미하는 것이 아닌 그래프의 정보를 담고있다고 이해할 수 있습니다.

*그렇다면 기존 Deep Learning에서 사용하는 network들로 embedding을 할 수 있을까요?? * 결론부터 말씀드리자면 사용할 수 없습니다. CNN은 고정된 크기의 이미지나 그리드에 적용할 수 있고, RNN이나 Word2Vec은 텍스트나 시퀀스 데이터에 적용됩니다. 하지만, graph는 이러한 데이터들보다 훨씬 복잡합니다. 이미지나 그리드처럼 특정 차원에 표현될 수 없고, 가끔 차원이 변동되고 multi-modal feature를 갖기도 합니다. 따라서 graph를 embedding하기 위해서는 graph만의 방식을 적용합니다.

2. Embedding Nodes

이제 graph의 node들을 embedding하는 방법에 대해 알아보겠습니다.

• graph $G$
• vertex set $V$
• adjacency matrix $A$ (assume binary)

node feature나 그 외 정보들은 사용되지 않습니다. (이하 Encoding은 Embedding과 같은 의미입니다.) encoding의 목적은 embedding space상에서의 similarity와 원본 graph의 similarity최대한 동일하게 만드는 것입니다. embedding space상의 두 vector의 similarity는 dot product $z_v^Tz_u$로 측정할 수 있습니다.

The dot product is proportional to both the cosine and the lengths of vectors.

과정은 다음과 같습니다. 1). Define encoder -> 각 node를 low-dimentional vecotr로 mapping(embedding)하는 방법 정의 $z_{node} = ENC(node)$ 2). Define a node similarity function -> 원본 graph의 node간 유사도를 측정하는 함수를 정의 $similarity(u,v)$ 3). Optimize the parameters of the encoder so that $similarity(u,v) \approx z_v^Tz_u$

1) Encoder

Shallow Encoding

shallow encoder :encoding is just an embedding-lookup $ENC(v)=Zv$

• $Z\in \mathbb{R}^{d\times|V|}$ : matrix. 각 column이 node embedding
• $v\in \mathbb{I}^{|V|}$ : indicator vector. node $v$를 지정하는 column과 만나는 element는 1, 그 외에는 0인 vector

$similarity(u,v) \approx z_v^Tz_u$을 optimize하며 $Z$를 학습시킵니다. shallow encoding으로 각 node를 개별적으로 representation할 수 있습니다.

shallow encoding 외에도 DeepWalk,** node2vec,TransE**등으로 Embedding할 수 있습니다.

다음 파트 _2. Random Walk Approaches to Node Embeddings_에서 상세히 다루겠습니다.

2) Similarity Function

node similarity를 어떤기준으로 정의할지 결정해야 합니다. 예시는 다음과 같습니다.

• 두 노드의 연결관계
• 공유하는 node(neighbor)
• structural role의 유사성
• 등등

이 역시 encoding방법에 따른 similarity fucntion을 _2. Random Walk Approaches to Node Embeddings_에서 자세히 설명드리겠습니다.

3) Optimization도 2. Random Walk Approaches to Node Embeddings 에서 자세히 설명드리겠습니다. 강의 순서가 뒤죽박죽하군요

2. Random Walk Approaches to Node Embeddings

_paper refenece : Perozzi et al.2014 :DeepWalk: Online Learning of Social Representations Grover et al.2016 : node2vec: Scalable Feature Learning for Networks _

paper reference에서 알 수 있듯, DeepWalk, node2vec에 관련된 node embedding방법을 상세하게 다뤄보겠습니다.

Random Walk

Random Walk란, 말 그대로 node 위를 random하게 걸어다니는 것을 말합니다. 그래프의 특정한 시작점에서 random하게 neighbor들을 선택해서 나가는데, 그 point의 sequnce를 random walk라고 합니다. 걸어간 발자취를 나열한 것이라고 생각할 수 있습니다. 예를 들어, 위의 그림에서 노란색 point가 시작점으로 주어지고 4걸음을 간다는 parameter가 주어진다면 [1,3,2,8,11]이 random walk가 될 수 있습니다. 3걸음을 간다고하면 [5,8,11,12]가 될 수 있습니다. 이러한 random walk는 parameter를 주고 sampling한다고 표현합니다.

Random-walk Embedding (Deep Walk)

$z_u^Tz_v \approx$ probability that $u$ and $v$ co-occur on a random walk over the network

$z_u^Tz_v$를 "network 전체의 random walk에서 $u$와 $v$가 함께 발생할 확률"로 근사할 수 있습니다. 왜냐하면 $z_u$와 $z_v$의 similarity가 높다면 latent space상에 가깝게 위치할 것이고, 이는 node $u$와 $v$의 similarity가 높다는 의미이므로 random walk에서 동시에 발견될 확률이 높기 때문입니다.
Random-walk Embedding의 과정은 다음과 같습니다.

• 1.어떤 random walk strategy R을 사용하여 node u에서 출발하여 node v에 방문할 확률 $P_R(v|u)$ 을 추정합니다.
• 2. 이 $P_R(v|u)$를 encoding하기 위해 embedding을 최적화시킵니다. 여기서 두 $z$의 similarity인 dot product는 $cos(\theta)$과 같고, 이는 random walk similarity로 볼 수 있습니다.
     
     
• *그렇다면 왜 Random Walks를 사용할까요??**
• Expressivity : Local과 Higher-order neighborhood 정보를 함께 고려하는 node similarity를 유동적으로 정의내릴 수 있습니다. _한국어로 풀어쓰니까 의미전달이 직관적이지 않네요... 강의자료에는 "Flexible stochastic definition of node similarity that incorporates both local and higher-order neightborhood information"라고 명시되어있습니다. _
• Efficiency : 학습할 때, 모든 node쌍을 고려할 필요 없이, 오직 random walk에 함께 발견될 쌍들만을 고려하면 됩니다. 이는 그래프의 크기가 클수록 더 두드러지는 장점입니다. (ex. real social graph)
  
  ### Random Walk Optimization 다시 graph domain에서의 **Unsupervised Feature Learning**의 의미를 생각해봅십다. 목표는 유사성을 보존하는 d-dimension의 latent space에서의 node embedding을 찾는 것이었습니다. 실제 graph에서 가깝다면 latent space상에서도 가깝도록 embedding해야 합니다. 그렇다면 **node $u$가 주어질 때, node의 주변, neighbor를 어떻게 정의**할 수 있을까요? 다음과 같이 정의됩니다.

$N_R(u)$ : random walk strategy $R$로부터 얻을 수 있는 $u$의 neighborhood

graph $G=(V,E)$가 있을 때, feature learning의 목표는 mapping function $z:u \rightarrow \mathbb{R}^d$를 학습하는 것입니다. 이때 Objective function은 다음과 같습니다.

Log-likelihood objective $max_z \sum_{u \in V}^{}{logP(N_R(u)|z_u)}$ Given node $u$, we want to learn feature representations that are predictive of the nodes in its neighborhood $N_R(u)$

node의 neighborhood를 예측하는 방향으로 feature representation을 학습합니다.

Random Walk의 Optimization 과정을 정리해보겠습니다.

Random Walk Optimization

• 1. graph의 각 node에서 정해진 짧은 길이만큼의 random walk를 수행합니다 (using some strategy $R$)
• 2. 각 node의 neighborhood $N_R(u)$를 수집합니다. ($N_R(u)$ : the multiset of nodes visited on random walks starting from $u$)
• 3. node $u$가 주어질 때, 그 node의 neighborhood $N_R(u)$를 잘 예측하는 방향으로 node를 embedding합니다. $max_z \sum_{u \in V}^{}{logP(N_R(u)|z_u)}$

loss function $L = \sum_{u \in V}\sum_{v \in N_R(u)}-log(P(v|z_u)$

intuition Random walk가 동시에 발생(co-occurrrence)할 likelihood를 maximize할 수 있도록 embedding을 최적화 이때 $p(v|z_u)$는 vector representation이 softmax를 거친 후의 값입니다. $P(v|z_u) = {{exp(z_u^Tz_v)}\over{\sum_{u \in V}exp(z_u^Tz_v)}}$ softmax를 사용하는 이유는 node $u$와 가장 유사도가 높은 node $v$를 얻기 위함입니다. $\sum_iexp(x_i) \approx max_iexp(x_i)$

Optimizing random walk embeddings = Finding embeddings $z_u$ that minimize $L$ 정리하면 위와 같습니다. grpah의 모든 node에 대해, 각 node의 neighborhood가 random walk시에 동시에 발견될 확률을 높도록 embedding을 학습합니다.

하지만, 이 naive한 과정은 compuation 측면에서 매우 expensive하다는 단점이 있습니다. softmax의 normalization term $\sum_{u \in V}exp(z_u^Tz_v)$이 원인입니다. log안에 있는 ${exp(z_u^Tz_v)}\over{\sum_{u \in V}exp(z_u^Tz_v)}$부분을 근사하여 이 문제를 해결합니다. 이때 Negative Sampling이 사용됩니다.

Negative Sampling

위에서 설명한 loss fuction의 log안의 함수를 다음과 같이 근사합니다. 모든 node를 고려하여 normalize한 기존의 loss는 expensive했기 때문에, random으로 Negative sampling한 k개의 negative samples $n_i$에 대해서만 normalize합니다. w2v에서 전체 corpus에서 빈도가 높은 단어를 negative sample로 sampling하였듯이, node의 degree가 높은 node를 negative sample로 사용합니다.

negative sample의 개수 $k$가 갖는 의미는 다음과 같습니다.

• Higher $k$ gives more robust estimates
• Higher $k$ correspond to higher bias on negative events

실제로는 $k$는 5~20으로 설정합니다.

지금까지 randome walk로 node를 embedding하는 방법에 대해 알아보았습니다. random walk는 지정한 시작점에서 고정된 길이 "fixed size"를 조건으로 시행됩니다. 하지만 이러한 조건때문에 한계가 있습니다. 만약, 두 노드의 structural role이 비슷하지만 멀리 떨어져있는 경우라면 어떨까요?? 실제로 두 node는 유사하지만, random walk는 고정된 사이즈로만 노드주변을 보기 때문에 random walk embdding방식으로는 이 유사성을 담지 못할것입니다. 이러한 경우 node의 similarity를 담도록 latent space에 embedding한다"라는 node embedding의 가장 큰 목적에 맞지 않습니다. 또한 random하게 보기 때문에, graph의 전체 structure를 고려하지 못한다는 단점도 있습니다.

이 단점을 보완한 node2vec에 대해 알아보겠습니다.

node2vec

Deep Walk의 단점을 보완한 node2vec에 대해 알아보겠습니다. 이 역시 graph의 node를 embedding하는 방식이기 때문에, node2vec의 목표는 다양한 task에 적용가능하도록 (downstream task에 상관없이) graph에서 node의 neighborhood간의 유사성을 latent space (feature space)상에서도 유지하는 것입니다. node2vec은 maximum likellihood optimization문제로 접근합니다.

Abstract 네트워크의 node와 edge에 대해서 prediction task를 수행하는 것은 feature engineering 측면에서 많은 노력이 소요된다. 최근의 연구들에서는 reprsentation learning 측면에서 feature 자체를 학습하여 이 측면에서 많은 혁신들이 있었으나, network에서 파악되는 connectivity pattern에 대해서는 제대로 학습하지 못한다는 한계를 가지고 있다. 따라서, 이를 해결하기 위해서 network의 이러한 feature를 학습할 수 있는 프레임워크인 node2vec을 제시하였다. node2vec에서는 network의 node들의 관계(neighborhood)를 우도(likelihood)를 최대화할 수 있는 low-dimensional(저차원) 피쳐 공간을 학습시켰다. 실제로 기존의 존재하는 데이터들을 대상으로 수행을 해봤는데 괜찮은 결과가 나왔다.

** Recap : word2vec** 여기에서 제가 제일 word2vec을 모르겠지만 감히 설명해볼게염...

• skipgram : 중심단어(center word)로 주변단어(context word)를 예측 가정 : 실제 문장들에서 비슷한 위치에 있는 word들은 embedding space에서도 비슷한 위치에 있을것이다. 따라서 중심단어(c)가 주어졌을 때 주변단어(o)가 나타날 확률(아래식)을 최대화 하면 됩니다. $P(o|c)= {{exp(u_o^Tv_c}\over{\sum_{w=1}{W}exp(u_w^Tv_c)}}$ graph에서는 특정 node가 주어졌을 때 그 node의 neighborhood가 나타날 확률을 최대화 하면 되겠네요!

random하게 neighbor를 보아서 graph 전체 structure를 고려하지 못한 Deep Walk의 단점을 개선하기 위해, node2vec에서는 기존의 randomwalk를 사용하지 않습니다.

node2vec key idea use flexible, biased random walk that can trade off between local and global views of the network

특정 node $u$의 neighborhood$N_R(u)$는 DFP와 BFS로 정의할 수 있습니다.

• $N_{BFS}(u)$ : local 영역으로 neighborhood 지정 (microscopic view) (위 그림 예시: if size of $N_{R}(u)$ = 3 $\rightarrow$ $N_{BFS}(u)={s_1,s_2,s_3}$)
• $N_{DFS}(u)$ : Global 영역으로 neighborhood 지정 (macroscopic view) (위 그림 예시: if size of $N_{R}(u)$ = 3 $\rightarrow$ $N_{DFS}(u)={s_4,s_5,s_6}$)

node2vec에서는 Biased 2nd-order random walk를 사용합니다.

• 1st-order random walk : node to node
• 2nd-order random walk : edge to edge

biased fixed-length random walk는 두가지 parameter를 정의해야 합니다.

• return parameter $p$ : 이전 node로 돌아갈 가능성을 계산하는 parameter. 주변을 잘 탐색하는지 $p$가 낮을수록 BFS like walk (좁은 지역 고려)
• in-out parameter $q$ : DFS와 BFS의 비율. random walk가 얼마나 새로운 곳을 잘 탐색하는지 $q$가 낮을수록 DFS like walk (넓은 지역 고려)

example $(s_1,w)$의 경로로 이동하여 지금 $w$인 상태 node $w$의 neighborhood로 $s_1,s_2,s_3$만 가능합니다. $s_2$는 $s_1$과 $w$의 공통 이웃, $s_3,s_4$는 $s_1$으로부터 멀어지는 방향입니다. $p$가 낮을 수록 좁은 지역을 보고 $q$가 낮을수록 넓은 지역을 봅니다.

node2vec algorithm

1. 예시와 같이 random walk probability를 계산합니다.
2. grpah의 각 node $u$에 대해 길이 $l$만큼의 random walk를 합니다.
3. node2vec을 SGD로 최적화합니다.

node embedding의 대표적인 두가지 방법 Deep Walk와 node2vec을 배워보았습니다. 이러한 embedding을 통해 graph의 정보를 최대한 보존하면서 computation 효과를 볼 수 있었습니다. graph의 node $u_i$들을 latent space로 임베딩한 embedding vector $z_i$들은 어디에 사용될 수 있을까요?? 기존 머신러닝에서 데이터를 임베딩(ex. 차원축소)하여 clustering, classification을 할 수 있듯 graph domain에서도 많은 task를 수행할 수 있습니다.

• Clustering / Community Detection
• Node classification
• Link prediction
• etc

3. Translating Embedding for Modeling Multi-relational Data

이제 Knowledge Graph(KG)의 node들을 embedding할 수 있는 TransE에 대해 배워보겠습니다.

Knowledge Graph

knowledge graph에서는 node를 entitie, link relation이라고 합니다. 한 KG의 relation에는 많은 종류가 있을 수 있습니다. KG에서의 link는 종류마다 갖는 의미가 다 다릅니다.

The knowledge graph represents a collection of *interlinked descriptions of entities *– objects, events or concepts. Knowledge graphs put data in context via linking and semantic metadata and this way provide a framework for data integration, unification, analytics and sharing.

KG의 이어지지 않은 entitie(node)의 relation(link)를 예측하는 KG completion (=link prediction)에 대한 연구가 활발합니다. intuition : KG의 local&global pattern을 잘 학습하는 link prediction model을 만들고자합니다. downstream task : link prediction은 학습된 패턴을 사용하여 관심 node와 그 외 모든 node간의 relationship을 일반화함으로써 수행됩니다.

TransE

Abstract 지금 우리가 해결할 문제는 구성요소와 관계들을 저차원의 벡터 공간으로 임베딩 시키는 것이고, 무엇보다 지식 그래프의 기반이 되고 학습하기 쉬운 장점을 가지는 것을 목표로 한다. 이에 TransE 라는 모델을 제시하는데 이 모델은 relationship(관계)를 저차원의 임베딩된 구성요소간 translations(전환) 으로 해석한다는 것이 핵심이다.

knowledge graph를 embedding하는 TransE에서는 KG의 두 node(entity)의 관계를 triplet으로 표현합니다. h (head entity), l (relation), t (tail entity) → (h,l,t) 먼저 Entitie(node)들을 entitiy space $R^k$에 embedding하고, 각 Entitie $e$을 mapping function $M_r$을 통해 relation space로 mapping합니다. TransE model을 통해 KG의 relation이 embedding space상에서 의미를 갖도록 합니다. 이때 핵심은 $(h,l,t)$가 성립한다면, $h + l\approx t$가 성립한다는 점입니다. 즉 embedding된 tail entity $t$는 임베딩 된 head entity $h$와 realtionship 과 관련된 벡터 $l$과의 합과 가까이 위치한다는 의미입니다.

• $h,t \in E$(set of entities), $l \in L$(set of relationships)
• 임베딩 벡터의 차원 : $\mathbb{R}^k$(k : hyperparameter)
• energy of triplet : $d(h+l,t)$ ($d$:dissimilarity measure,주로 $L_1,L_2-norm$
• marginary hyperparameter : $\gamma$ $\mathcal{L}=\sum_{(h,l,t) \in S}\sum_{(h',l,t') \in S'{(h,l,t)}} [\gamma _ d(h+l,t)-d(h'+l,t')]$ $S'{(h,l,t)}= { (h',l,t)|h'\in E } \cup { (h,l,t')|t'\in E }$

$S'{(h,l,t)}$은 corrupted triplet입니다. 이때 corrupted는 노이즈가 추가된 상태라는 의미입니다. 위 수식에서 알 수 있듯이 head entity나 tail entity에 변화가 있는 상태입니다. $S'{(h,l,t)}$는 실제 KG에는 없는 triplet입니다. loss $\mathcal{L}$를 mimimize하므로, training triplet $(h,l,t)$의 energy(dissimilariy)는 작게하고 corrupted traiplet$(h',l,t')$의 energy(dissimilarity)는 크도록 학습한다는 의미입니다.

1. 먼저 Entitie(node)들을 entitiy space $R^k$에 embedding합니다.
2. 각 Entitie $e$을 mapping function $M_r$을 통해 relation space로 mapping합니다.
3. 각 Relation(link)들은

학습 과정은 다음과 같습니다.

1) relation set의 $l$에 대해 uniform distribution을 따르게 하고 정규화를 시킵니다. 2) entitiy set의 $e$에 대해 uniform distribution을 따르게 하고 정규화를 시킵니다. 3) triaining triplet set $S$에서 batch size만큼의 triplet을 뽑아 $S_{batch}$를 구성하고, $T_{batch}$를 공집합으로 초기화합니다. 4) $S_batch$에 대한 corrupted triplet을 만들어 $T_batch$에 원소로 넣어줍니다. 5) 구성된 $S_{batch}$와 $T_{batch}$로 loss를 mimize하는 방향으로 임베딩을 업데이트합니다. 6) 2)~5)를 반복합니다.

TransE는 KG에서 entities간의 관계를 잘 반영하고 기존 SE model보다 최적화가 간단합니다. 2-way interactions를 표현하는데 있어 강점이 있지만, 3-way dependencies를 표현하는데는 약점을 가집다. 또한 1-to-1 이상의 , 1-to-N, N-to-1 관계를 포함하는데 TransE는 부적합할 수 있습니다.

4. Embedding Entire Graphs

이전까지는 node를 embedding하는 방법을 배웠습니다. 이번 파트에서는 Graph $G$를 embedding하는 방법을 배워보겠습니다. 전체 graph 뿐만 아니라 전체 graph의 sub-graph를 한 point를 embedding할 수 있습니다. (sub)graph embedding을 통해 "Toxic molecules, non-toxic molecules 분류", "anomalous graph 분류"등을 할 수 있습니다.

다음으로 (sub)grpah를 embedding하는 몇가지 approach를 알아보겠습니다.

Approach 1 (sub)graph $G$의 각 node를 embedding하고(ex.Deep Walk, node2vec...) 그 embedding값을 모두 더하거나 평균을 내어 graph embedding을 할 수 있습니다. sum : $z_g= \sum_{v \in G}z_v$ avg : $z_g= {{1}\over{# ; of; node}}\sum_{v \in G}z_v$

Approach 2 (sub)graph를 대표하는 virtual node (super-node)를 만들고, 그 node를 embedding값을 (sub)graph의 embedding으로 사용할 수 있습니다.

Approach 3 : Anonymous Walks Embeddings Anonymous Walk는 random walk를 하는데 어느 node를 지나왔느냐가 아닌, 지나온 순서를 고려하는 random walk입니다. random walk를 진행하고 그 발자취의 순서(index)를 Anonymous Walk라고 합니다. Anonymous Walk의 결과로 embedding하는 것을 Anonymous Walks Embeddings이라고 합니다.

Reference

• CS244W fall 2019 : Machine Learning with Graphs의 7강 "Graph Representation Learning"
• 데이터 괴짜님 CS224W - 07.Graph Representation Learning
• frhyme님 node2vec은 무엇인가?
• Sukwon Tun님 [지식그래프] (TransE) Translating Embeddings for Modeling Multi-relational Data

Contents

0. Intro

1. Relational Classification
2. Iterative Classification
3. Belief Propagation

Keyword : Machine Learning applied on Graph, Node Classification

0. Intro

Main Question

Network에서 몇 개의 node에만 label이 달려 있고, 몇 개는 모른다면, 모르는 node의 label을 어떻게 설정해 줄 수 있을까요?

주어진 label을 이용하여, unlabeled node를 예측합니다! 이와 같은 방법론을 semi-supervised node classification 이라고 합니다.

semi-supervised learning

• supervised learning 관측치마다 정답 label이 달려 있는 데이터셋을 이용하여 학습 ex. Regression, Classification, Neural Network, ...
• unsupervised learning 정답 label이 달려 있지 않은 데이터셋을 이용하여, 모델 스스로 학습 ex. Clustering
• semi-supervised learning
  label이 달려있는 데이터와 label이 달려있지 않은 데이터를 동시에 학습해서, 더 좋은 모델을 만드는 것 데이터가 군집의 형태를 따르고 있다면, 학습에 도움이 될 것

Network를 구성하고 있는 node 끼리는 Cluster(=Community, Correlation)를 형성하고 있을 것이므로, semi-supervised learning을 통해 unlabeled node를 분류해 보자는 것이 핵심 idea 입니다.

Collective Classification

Network 상에는 Correlation이 존재합니다. Similar node는 connected 되어 있을 것이고, 이러한 정보를 기반으로 node에 label을 assign 해 주는 것이 collective classification 개념입니다.

Collective Classification Techniques

1. Relational Classification
2. Iterative Classification 
3. Belief Propagation 

Correlations Exist in Networks

Individual behaviors are correlated in a network environment

1. Homophily

   • 유유상종
   • 비슷한 성향을 가진 사람들끼리, 비슷한 social connection을 형성
   • ex. age, gender, organization roles + AI에 관심 많은 투빅스..

2. Influence

   • 나의 취향을 추천하여, 다른 사람도 좋아하게끔 만드는 것
   • ex. 내가 좋아하는 연예인을 동료한테 매일 보여줬더니 동료도 결국 그 연예인을 좋아하게 되는 것

3. Confounding

   • 교란 변수 : individual characteristics와 social connections에 동시에 영향을 주는 environment

correlation 중, homophily에 주목해 node classification을 수행하고자 합니다.

Classification with Network Data

How do we leverage this correlation observed in networks to help predict node labels?

Guilt-by-association
If I am connected to a node with label 𝑋, then I am likely to have label 𝑋 as well. = 내가 투빅스 사람들하고 친구라면, 나도 투빅스 사람일 확률이 크다!

v node label 은 위의 세 가지 요소에 영향을 받게 됩니다.

따라서 node classification task는, positive / negative / unlabeled node 에서, unlabeled node 가 positive node가 될 확률을 예측하는 것 입니다. (cf. logistic regression에서의 p = 1이 될 확률)

Collective Classification Overview

Simultaneous classification of interlinked nodes using correlations

• Markov Property : $P(S_t|S_{t-1}, ... , S_1) = P(S_t|S_{t-1})$
• Markov Assumption : neighbor 에 모든 정보가 함축되어 있다고 생각하고, node v에 연결된 neighbor 정보를 고려합니다.

PROCESS

STEP 1. Local Classifier

• 초기 label을 부여합니다.
• node 속성만을 사용해 예측하며, network 정보를 사용하지 않습니다.

STEP 2. Relational Classifier

• correlation 을 capture 합니다.
• neighborhood node의 label, attribute 정보를 사용해 예측합니다.

STEP 3. Collective Inference

• Propagate the Correlation
• 각 node마다 Relational Classifier 를 반복적으로 적용합니다.
• 인접한 neighbor 정보만 사용하는 것이 아니라, neighbor에 전달된 correlation을 사용합니다. 이를 통해 전체 network의 정보를 사용할 수 있게 됩니다.
  (Basically, we do not want to stop at the level of only using our neighbors, but through multiple iterations we want to be able to spread the contribution of other neighbors to each other.)

Collective Classification 은 iterative 하게 진행되며, approximate inference 입니다.

• iterative : neighborhood labels 불일치가 최소화 될 때 까지 반복합니다.
• approximate inference : propagation 진행할 때 neighborhood 범위를 점점 줄입니다.

several applications

• Document classification
• Part of speech tagging
• Link prediction
• Optical character recognition
• Image/3D data segmentation
• Entity resolution in sensor networks
• Spam and fraud detection

1. Relational Classification

setting

• idea : $Y_i$의 class probability는 neighbor 노드들의 class probability의 weighted average
• labeled node : ground-truth Y label 로 initialize
• unlabeled node : uniformly 하게 설정합니다. (0.5 or 신뢰할 만한 prior)

training

• update : 수렴할 때 까지 or 최대 iteration 수에 도달하기까지 모든 노드들을 random order로 업데이트 합니다.
• repeat : 모든 node i 와 label c에 대해, 다음 과정을 반복합니다.
  

Example

1. Initialize : node label 에 맞게, 확률값을 초기화 합니다.

2. 1st Iteration : random order 순서대로 update 합니다.

... (node 3→4→5→8→9)

3. Repeat Iteration : 모든 node 가 수렴할 때 까지 or 최대 iteration 수에 도달할 때 까지 반복합니다.

• $P(Y_v) > 0.5$ 인 경우 label = 1, $P(Y_v) < 0.5$ 인 경우 label = 0 으로 분류합니다.
• cf. node 4 : +/- equally contributing → bridge 역할 가능

Challenges

1. convergence 보장되어 있지 않습니다. 위의 예시의 경우 그래프가 작아서 수렴이 잘 되었지만, 그래프 크기가 커지는 경우 취약한 방식이라고 합니다.
2. node feature information을 전혀 사용하지 않습니다.

2. Iterative Classification

idea : node i의 attribute & neighborhood 의 label 모두 고려합니다. If two objects are related, inferring something about one object can assist inferences about the other.

PROCESS

1. Bootstrap Phase

   • $a_i$ : 각각의 node i 에 대해 flat vector $a_i$ 를 생성합니다.
   • $f(a_i)$ : $a_i$를 local classifier(ex. SVM, KNN, LR) 을 통해 분류합니다.
   • aggregate neighbors : count, mode, proportion, mean, exists 등의 neighborhood information 을 취합합니다.

2. Iteration phase

   • Repeat : 각각의 node i 에 대해 다음 과정을 반복합니다.

     • node vector $a_i$ 를 update 합니다.
     • $f(a_i)$ 에 대해 label $Y_i$를 update 합니다.

   • Iterate : class label이 stabilize 되거나 최대 iteration 횟수가 만족될 때까지 반복합니다.

1. $\phi_1(f_v)$ = feature vector 만으로 node label을 예측하는 classifier
2. $\phi_2(f_v, z_v)$ = feature vector + $N_i$ 모두 이용하여 label을 예측하는 classifier

Example : Web Page Classification

0. Setting

   • $f_v$ : feature vector, node의 정보 (강의에서 소개해 준 feature vector 예시 : Bag-Of-Words)
   • $z_v$ : neighborhood label에 대한 정보 통계량 벡터
     • I : Incoming neighbor label information vector
     • O : Outgoing neighbor label information vector
     • $I_0$ = 1 : 최소 1개의 label 0 노드가 incoming (count)

1. $\phi_1$ 과 $\phi_2$ 를 학습시킵니다.

2. feature vector 만으로 classification ($\phi_1$) 을 진행합니다.

3. 예측한 label 값에 기반하여, $z_v$를 update 합니다.

4. feature vector와 $z_v$를 모두 사용하여 classification ($\phi_2$) 을 진행합니다.

5. 수렴할 때 까지 반복합니다.

REV2 : Fake Review Detection

Fake Review Spam

• Review Site에서는 spam이 공공연하게 발생합니다.
  • 평점이 하나 높아질수록, 수입이 5~9% 상승합니다.
  • Paid Spammers는 거짓으로 해당 상품들의 평가를 낮게 평가함으로써, 경쟁사를 꺾으려고 합니다.
• Behavioral analysis, Language Analysis 만으로는 Spammer를 판별하기 어려운데, Individual Behavior 이나 Content of Review 는 거짓으로 보여주기 쉽기 때문입니다.
• 따라서, 쉽게 속이기 어려운 graph structure 를 통해 Reviewers, Reviews, Stores 사이의 relationship 을 파악하고자 합니다.

REV2 Solution

1. Setting

• Input : Bipartite rating graph as a weighted signed network
  • node : Users, Products (Items)
  • Edges : [-1, +1] rating scores (Red : -1 & Green : +1)
• Output : 거짓으로 평점을 평가하는 유저 집단

2. Intrinsic Properties

   1. Users have fairness scores 사기꾼들은 좋은 상품에 낮은 평점, 나쁜 상품에 좋은 평점을 줄 것입니다.
   2. Products have goodness scores 좋은 상품의 평점은 좋을 것입니다.
   3. Ratings have reliability scores reliability $\neq$ fairness : user는 bias가 있습니다. 개인적인 의견이 다수의 의견과 일치하지 않을 수 있습니다.

3. Axiom

   1. Better Products get higher ratings.
   2. Better products get more reliable positive ratings.
   3. Reliable ratings are closer to goodness scores.
   4. Reliable ratings are given by fairer users.
   5. Fairer users give more reliable ratings.

Iterative Classification

1. Fairness of Users : goodness와 reliability를 고정시키고, fairness를 update 합니다.

2. Goodness of Products : fairness와 reliability를 고정시키고, goodness를 update 합니다.

3. Reliability of Ratings : fairness와 goodness를 고정시키고, reliability를 update 합니다.

PROCESS

1. Initialize to best scores : F, G, R 값을 모두 1로 초기화합니다.

2. Updating goodness

3. Update reliability

4. Update fairness

5. Convergence : Fairness가 낮은 user가 Fraudster 입니다.

Properties of REV2 Solution

• REV2는 수렴이 보장되어 있습니다.
• 수렴하기까지 총 Iteration 횟수의 상한선이 존재합니다.
• 시간복잡도는 그래프의 Edge의 수가 증가함에 따라 Linear하게 증가합니다.
• 위에서 다루지는 않았지만, Laplace Smoothing을 통해 cold start problem도 해결합니다.

3. Belief Propagation

idea : message passing dynamic programming 접근 방식으로, graph model에서 조건부 확률로 답을 구해내는 방식입니다.

Message Passing

• Task : graph 에서 node의 개수 세기
• Condition : 각 node들은 그들의 neighbors와만 interact 할 수 있습니다.
• Solution : 각 node들은 그들의 neighbor로 부터 message를 전달받고, 이를 update 하여, 앞으로 전달합니다.

Message Passing in Trees

노란색 node에서 전달된 정보를 토대로 개수를 파악하여, 앞으로 전달합니다.

반대 방향으로 전달할 때에는, 위와 같습니다.

따라서 전달된 (Passing a belief) 두 정보를 종합하여, 7+3+3+1=14 라는 과정을 통해 총 node의 개수는 14개가 될 것이라는 Belief Propagation 을 내리게 됩니다.

다만, graph가 cyclic 한 경우에는 Belief Propagation이 잘 작동하지 않습니다.

Loopy Belief Propagation

i는 j에게 message를 보낼 때, 주변 neighbor인 k에게 들은 내용을 전달합니다. 즉, neighbor k는 i에게 belief state를 전달합니다.

Notation

1. $\psi$ : Label-label Potential Matrix

   • node와 neighbor 사이의 dependency
   • $\psi(Y_i, Y_j)$ : 노드 j의 neighbor i가 state $Y_i$에 있을 때, 노드 j가 state $Y_j$에 속할 확률 = correlation between node i & j

2. $\phi$ : Prior Belief

   • $\phi_i(Y_i)$ : 노드 i가 state $Y_i$에 속할 확률
   • $m_{i→j}(Y_j)$ : j가 state $Y_j$에 있을 때 i의 추정치 = i's message

3. $L$ : 모든 state의 집합

PROCESS

1. 모든 message를 1로 초기화 한 후, 각 노드에 대해 다음을 반복합니다.

2. 수렴하면, 각 state에 대한 belief $b_i(Y_i)$를 계산합니다.

Loopy BF는 cyclic graph에서 사용할 수 없습니다. (no longer independent)

Summary

1. Advantages
   • 프로그래밍 및 병렬화가 쉽습니다.
   • 어떤 그래프 모델보다도 general하게 적용 가능합니다. (+ higher order than pairwise)
2. Challenges
   • 수렴이 보장되지 않습니다.
   • 특히 많은 closed loop가 있는 경우, 적용이 어렵습니다. (Clustering Coef를 확인해 보고, Belief Propagation 적용 가능성을 검토해 볼 수 있습니다.)
3. Potential Functions
   • parameter 추정을 위해 train이 필요합니다.
   • gradient-based 최적화가 진행됩니다.

NetProbe : Online Auction Fraud

Online Auction Fraud

• 경매 사이트는 사기 치기에 상당히 매력적인 장소입니다. 종종 상품 배달을 못 받았다는 사기를 치곤 하며, 이러한 사기 사건 하나 당 발생하는 평균 손실 비용이 $385 라고 합니다.
• 단순 individual feature (user attributes, geographic locations, login times, session history, etc) 만으로 사기꾼을 탐지하기는 어렵습니다.
• 따라서 graph structure 을 구성하여, user 사이의 relationship 을 캐치하여 사기꾼을 탐지하고자 합니다.

Role of Users

Main Question : How do fraudsters interact with other users and among each other?

fraudster : 사기꾼 / accomplice : 공범 / honest : 선량한 시민들

• 경매 사이트에는 Reputation System 이 존재합니다.
• 사기꾼들끼리는 서로의 Reputation Score를 올려 주지 않는데, 한 명이 걸리게 되면 다 같이 걸리게 되기 때문입니다.
• 따라서 near-bipartite graph를 형성합니다.
  • accomplice
    • perfectly 하게 정상적인 것 처럼 보이는 user를 말하며, honest와 거래하며 high feedback rating 얻습니다.
    • fraudster의 feedback rating 을 올려줍니다.
  • fraudster
    • accomplice 와 거래하며, honest 에게 사기를 칩니다.
• 사기를 치고 나면, fraudster는 사기 현장을 떠나고, accomplice는 사기 현장에 남아 다음 사기를 치는 것을 도와줍니다.

Detecting Auction Fraud

Markov Random Field & Belief Propagation

Propagation Matrix

$\psi(\sigma, \sigma')$ : the likelihood of a node being in state $\sigma'$ given that it has a neighbor in state $\sigma$

• 해당 논문에서의 $\epsilon_p$ = 0.05 입니다.
• 즉, 노란색으로 칠한 값이 heavily linked 된 관계를 나타냅니다.
• Intuition
  • fraudster 는 accomplice와 heavily link 되어 있으나, 다른 bad node와의 연결은 피하는 양상입니다.
  • accomplice 는 fraudster 와 honest 모두와 연결되어 있으며, 특히 fraudster와 더 잘 연결되어 있습니다.
  • honest 는 accomplice와 다른 honest와 연결되어 있습니다.

PROCESS

1. fraudster, accomplice, honest 확률값을 모두 같게 initialize 합니다.
2. 각각의 node는 iteratively 하게 message를 pass하며, belief를 update 합니다.
3. $\psi(\sigma, \sigma')$ 에 따르면, iteration 1 이후의 node는 accomplice 가 될 가능성이 높습니다. accomplice 로 분류된 node에 대해서, 이웃을 fraud 혹은 honest 로 두고, 값을 계속적으로 update 합니다.
4. 수렴할 때 까지 update 합니다.

분류가 잘 된 것을 볼 수 있습니다.

Reference

1. Tobigs Graph Study : Chapter 6. Message Passing and Node Classification
2. 데이터 괴짜님 Review : CS224W - 06.Message Passing and Node Classification
3. snap-stanford Review : Message Passing and Node Classification
4. CS224W Winter 2021 : 5. Label Propagation for Node Classification

5. REV2: Fraudulent User Prediction in Rating Platforms
6. NetProbe : A Fast and Scalable System for Fraud Detection in Online Auction Networks
7. Collective Classification in Network Data

8. Semi-supervised Learning(준지도학습) - Overview
9. Confounding Variable: Simple Definition and Example

작성자 : 정민준

이전 강의에서는 Network의 구조를 분석하고 Network motifs를 찾고 노드간 Community를 찾아내는 방법에 대해 소개했습니다. 이번 강의에서는 이전 내용에 이어 어떻게 그래프를 군집화 하고 더 나아가 Network motifs를 구성하는 Community를 찾아 그래프를 군집화하는 방법에 대해 소개합니다.

1. Spectral Clustering Algorithms

• Spectral Clustering을 위한 세 단계를 살펴보겠습니다. 먼저 전처리 단계를 거치고 고유값, 고유벡터를 구한다음 Grouping을 통해 네트워크를 표현합니다. 각 단계에 대해 자세히 알아봅시다.

1-1. Partitioning

• 먼저 G라는 Undirected graph가 있다고 가정하겠습니다. 여기서 의문은 우리는 어떻게 노드 1,2,3을 그룹화하고 나머지 노드 4,5,6을 그룹화 하는지입니다. 또한 이런 파티션을 어떻게 알아내는가에 대한 방법도 필요합니다.

• 좋은 파티션이라 함은 그룹내 노드간 간선이 최대며 그룹간의 간선이 최소여야 합니다. 이전 강의에서 Modularity를 배웠는데 이와 비슷한 개념이라고 이해했습니다. 결국 강한 연결을 지닌 서브 네트워크를 식별하여 분리합니다.

1-2. Edge cut

• 파티션을 표현하는 목적함수로 edge cut을 사용합니다. 이는 각 그룹에서 종점이 있는 간선 수로 나타낼 수 있습니다. 위 그림에서는 파티션 A, B에 대한 edge cut은 2입니다.

• 그래서 우리가 하려는 것은 두 파티션에 대한 최소 edge cut를 얻는 것입니다. 위 그림에서 Optimal cut을 찾는 과정이라고 할 수 있습니다. 하지만 이는 오로지 군집간의 연결만 고려하였고 군집 내부의 연결성에 대해선 전혀 고려하지 않았습니다.

1-3. Conductance

• edge cut 대신 우리는 Conductance를 사용합니다. 군집간 연결성을 비교하는데 각 군집의 밀도를 반영합니다. edge cut값이 작고 min(vol(A), vol(B))의 값이 커진다면(=두 군집의 밀도가 유사) 작은 Conductance값을 얻을 수 있습니다.
• 이전에 좋은 파티션을 어떻게 알아내야하는지에 대해 얘기했습니다. 답은 최소 Conductance값을 구하는 것입니다. 하지만 이는 NP-hard 문제로 최적의 파티셔닝을 구하기 위해 Conductance값을 계산하는것은 쉽지 않습니다.
• NP-hard: 대표적으로 TSP(Traveling Salesman Problem)문제가 있습니다. 그래프내 간선을 전부 비교하면서 문제를 해결하는 방법으론 다항시간내에 풀 수 없습니다. 이러한 NP-hard문제를 해결하기 위해서 휴리스틱한 방법이나 가지치기, 탐욕법등의 방법을 적용합니다.
• 이후 내용에서는 그래프에서 얻은 행렬, 고유값, 고유벡터를 통해 파티셔닝을 하는 방법에 대해 소개합니다.

1-4. Spectral Graph Partitioning

• Matrix A : 그래프 G에서 얻은 인접행렬. 노드 i,j가 연결되어 있다면 1, 아니면 0을 가집니다.
• y : 우리는 인접행렬에서 x 벡터를 곱하여 y 벡터를 얻었습니다. y벡터는 각 노드가 이웃한 총 노드 수를 표현합니다.

• 여기서 고유벡터와 고유값이 등장합니다.

• 그래프 G의 모든 노드들이 차수 d를 가지는 d-Regular Graph의 경우를 살펴보겠습니다.
• 여기서 가장 큰 고유값은 d입니다. CS230n Lecture7 의 내용을 빌리자면 이런 가정을 하는 이유는 원하는 결과를 보기 위함이라고 설명했습니다. Deconvolution case를 예를들어 설명하겠습니다.

• 실시간으로 이미지에서 object detection하는 모델이 있다고 가정합시다.
• 일반적인 CNN를 보면 이미지의 feature extraction을 통해 낮은 차원을 가진 정보를 반복적으로 가지고갑니다. 실제로 Convolution Layer은 이미지 전체를 보지 않습니다. 커널이 지나가는 이미지의 일부분에서 계산된 값을 다음 정보에 저장합니다.
• 위 그림과 같이 실제로 Convolution Layer을 통해서 나온 값을 확인해보면 해당 object일 확률이 높은 region을 표시하면 다음과 같은 사진이며 이 값들이 Fully Connected layer의 가중치와의 곱과 합을 통해서 Classification을 진행합니다.

• 여기서 복원 벡터가 있다고 가정하고 Deconvolution을 통해서 해당 값이 어떤 이미지의 부분을 집중적으로 보았는지 복원해봅니다. 강의에서는 이런 가정을 통해서 우리가 하려는게 정말 가능한지를 확인하기 위해서 한다고 합니다. 사실 학습을 한다면 이런 가정이 무의미하다고 설명합니다.

• 그래프 G가 위 사진처럼 C와 B 파티션을 두 가지 경우로 가진다고 가정하겠습니다.
• 왼쪽의 경우 C, B 파티션이 연결성이 없으므로 최대 고유값과 두번째로 큰 고유값은 동일합니다. 이전 페이지에서 x가 전부 1인 고유벡터와 최대 고유값을 가짐을 확인했습니다.
• 다시 돌아와서 x벡터가 C 파티션의 노드 정보만 가지는 경우와 B 파티션의 노드 정보만 가지는 경우를 생각해보면 고유값이 동일함을 알 수 있습니다. 오른쪽의 경우 C, B 파티션이 연결성을 가진다면 근사한 값을 가지지만 동일하진 않습니다.

• 여기서 오른쪽 경우가 d-regular graph라고 가정하겠습니다. 그러면 이미 아는대로 모든 값이 1인 고유벡터가 최대 고유값을 가집니다.
• 고유벡터들은 직교함으로 서로 곱하였을때 0이 나와야합니다. 그러면 다른 고유벡터의 모든 값들의 합은 0이 되어야 합니다. 그렇다면 두 그룹의 노드정보에 대해 양수, 음수의 그룹으로 나누어 표현하게 됩니다.

1-5. Matrix Representations

1-6. Laplacian Matrix

• 위에서 차례대로 인접행렬 A와 차수행렬 D를 보았습니다. 여기서 Laplacian Matrix L은 D - A로 표현할 수 있습니다.
• 여기서 모든 L의 값의 합은 0입니다. 그래서 이전과 동일하게 모든 값이 1인 고유벡터는 최대 고유값을 가지는건 자명합니다.

1-7. Rayleigh Theorem

• 여기서 우리가 구하고싶은 람다2를 통해서 그래프를 파티셔닝합니다.
• 수식을 정리하면 노드 i, j 차이의 제곱합임을 알 수 있습니다.

• 여기서 y벡터가 A, B파티션에 속하는 노드에 대한 정보를 담고있는데 A에 속하면 1, B에 속하면 -1이라고 합시다. 그러면 우리는 군집내 노드와 다른 군집의 노드만 고려하면 됩니다.
• 여기서 람다2는 최소 값의 f(y)로 표현할 수 있습니다. 그리고 고유값에 대응되는 고유벡터를 x로 두고 있습니다.
• 정리하자면 이 x 벡터가 군집을 결정하고 Conductance를 최소화 합니다.

1-8. Summary

• 그래서 우리는 지금까지 그래프의 좋은 파티션의 정의를 하였고 이를 찾는법은 cut criterion(=conductance)를 최소화하는 것이었습니다.
• 파티션을 찾는 좋은 방법은 그래프에서 얻은 행렬에서 고유값, 고유벡터를 사용하여 추정하는 것입니다.

• 우리는 지금까지 Spectral Partitioning Algorithm에 대해 살펴보았고 총 정리를 하겠습니다.
• 먼저 Pre-processing단계에서 그래프의 인접행렬과 차수행렬을 통해 Laplacian 행렬을 얻습니다.
• Decomposition을 통해 Laplacian 행렬의 고유값, 고유벡터를 구합니다. 우리가 집중해야할 값은 람다2 입니다.
• 이전 단계에서 얻은 고유벡터에 담긴 노드 정보로 Grouping을 하여 파티셔닝을 진행합니다. 여기서 나이브하게 접근하면 0 또는 중간값으로 분리하여 파티셔닝을 하고 벡터내 값을 정규화하여 노드의 파티션을 정한다고 합니다.

-이렇게 파티셔닝한 결과를 보겠습니다. 오른쪽 그래프에서 0을 지나는 구간을 자릅니다. 그리고 가장 0에 가까운 노드 4개는 왼쪽 그래프의 네트워크의 게이트웨이 위치에 있음을 확인할 수 있습니다. 오른쪽 차트가 나타내는 그래프 정보가 왼쪽 실제 그래프와 일치함을 볼 수 있습니다.

• 다음의 경우를 보겠습니다. 0을 지나는 구간은 왼쪽 그래프의 서브 그래프를 연결하는 간선을 의미합니다.

• 다른 람다값의 벡터에 대한 결과입니다. 람다1은 모두 같은 값을 가집니다.

1-9. K-Way Spectral Clustering

• 군집의 수를 정하는 이 k 변수를 어떻게 정해야하는지에 대해 방법을 제시하고 있습니다. PCA에서 고유값, 고유벡터를 사용하는것과 유사하다고 이해했습니다.

• 연속한 두 고유값의 차이가 가장큰 경우의 k를 선택합니다.

2. Motif-Based Spectral Clustering

• 파티셔닝을 하는데 Network motifs를 바탕으로 할 수 있는지가 main discussion입니다.

2-1. Modules of Motifs

• Based Motif에 따라 다르게 파티셔닝됨을 볼 수 있습니다.

2-2. Motif Conductance

• 이전까지 우리는 edge cut에서 conductance 개념을 살펴보았는데 이를 motifs 관점에서 적용시켜 다루겠습니다.

• 전체 네트워크에 6개의 motif를 볼 수 있습니다. 그리고 cut을 기준으로 4개의 간선이 존재하는데 두 간선은 motif를 이루는 간선이 아님으로 제외합니다. 그렇다면 파티셔닝된 S 네트워크의 motif volume은 2번 노드를 기준으로 4개의 motif가 존재하고 3개의 완전한 motif와 2번 노드만 남은 motif가 있음으로 10입니다. 여기서 잘린 motif는 하나 임으로 S 네트워크 Motif Conductance는 10 / 1로 정의할 수 있습니다.
• 이 과정 또한 NP-hard문제 입니다. 이전 Spectral Clustering Algorithm을 적용하겠습니다.

• Spectral Clustering Algorithm 의 단계와 동일합니다. 하나씩 살펴보도록 하겠습니다.

• 주어진 motif에 대해서 motif를 이루는 서브 그래프를 찾고 간선에 가중치를 주는 Matrix W를 둡니다.
• Matrix W는 low motif conductance를 찾도록 합니다.

• 이어서 Laplacian Matrix를 구합니다. 이전에는 인접행렬을 사용했다면 이번엔 W 행렬을 사용합니다.

• 람다값을 구하고 이에 상응하는 고유벡터를 얻습니다. 여기서 최소 Motif Conductance를 띄는 노드의 정보를 통해 Grouping 과정을 진행합니다.

2-3. Motif Cheeger Inequality

• Motif conductance가 다음과 같은 값의 범위를 가진다고 설명하고 있습니다. 이는 앞서봤던 람다2와 유사하다고 이해했습니다.

• 정리하자면 최적의 Motif conductance은 위의 정리를 따르고 값을 구하여 Motif를 기반으로한 네트워크를 표현합니다.

2-4. Example

• Network Motif의 유무에 따른 두 가지 경우를 제시합니다. 강의자료에선 Food webs에 대해 설명하고 있습니다.

• Motif Spectral Clustering을 통해 각 Motif에 따른 결과를 보여줍니다.

• 여기서 특정 Motif를 설정하였을때 파티셔닝은 다른 Motif에 대해서는 좋은 파티셔닝이 아니라고 합니다.

Contents

1. Community Structure in Networks
2. Network Communities
3. Louvain Algorithm
4. Detecting Overlapping Communities: BigCLAM

Community Structure in Networks

1. Community Structure in Networks

이번 챕터의 목적, 즉 Community Structure는 '서로간에 밀접하게(densely) 연결된 노드들의 집합을 구분하는 것'입니다.

알고리즘에 들어가기 전에, 사회과학적으로 군집이 생성되는 원리에 대해 먼저 보겠습니다.

Granovetter's Answer

Granovetter는 '사람들은 어떻게 새로운 직장을 찾는가?'에 대한 연구를 진행

-> 사람들은 자주 만나는 친한 친구가 아닌, 드물게 만나는 지인(Acquaintances)을 통해 직장에 대한 정보를 얻는다고 밝혔습니다.

이런 관계를 생각했을 때, 두 가지 관점의 frendships으로 나누어집니다.

• Structual: 링크가 네트워크의 어떤 부분을 연결하는가?
• Interpersonal: 링크가 강한 연결관계를 가지고 있는가 약한 연결관계를 가지고 있는가?

Triadic Closure

• 어떤 edge가 더 연결될 가능성이 높은가?

  답은 a-b입니다. a-c는 3칸 떨어져 있지만 a-b는 두 명의 공통된 이웃을 가지고 있기 때문에 a-b의 edge가 더 연결될 가능성이 높습니다.

Granovetter's Explanation

• First Point: Structure

  • 구조적으로 결속된(embedded) edge들은 사회적으로도 강하게 연결되어 있음.
  • 서로 다른 네트워크를 연결하고 있는(long-range) edge들은 사회적으로 약하게 연결되어 있음.

• Second point: Information

  • 구조적으로 결속된(embedded) edge들은 정보 접근의 관점에서 매우 중복(redundant)됨.
  • Long-range edge들은 지인(Acquaintances)들로부터 새로운 정보를 얻을 수 있게 됨.

• S Structure: Socially Strong Information: Redudant
• W Structure: Socially Weak Information: Useful information

Edge Overlap

위의 이론은 Onnela에 의해 2007년 증명되었는데, 사용한 데이터는 EU 소속 국가 인구의 20%의 휴대폰 네트워크 데이터이며 Edge Weight는 통화횟수로 정의하였습니다.

네트워크에서 얼마나 많은 지인(nodes)을 공유하고 있는가(overlap)에 대한 정보를 나타내는 수치를 Oij로 정의했습니다. 여기서 분자는 두 노드간의 겹치는 지인의 숫자이며, 분모는 두 노드의 모든 지인의 숫자(합집합)입니다.

즉, 지인을 공유할수록 해당 수치는 1에 가까워집니다.

2. Network Communities

Granovetter's의 이론에 따르면 네트워크는 강하게 연결된 노드의 집합(tightly connected sets of nodes)입니다.

• Network communities: 내부적으로 연결된 많은 노드와 몇몇 외부적으로 연결된 노드들로 이루어진 집합.

Modularity Q

Communities는 강하게 연결된 노드들의 집합인데, 이 Communities를 찾기 위해 Modularity를 이용하며 이것을 최대화 하는것이 Communities입니다.

• Modularity Q란? 네트워크가 communities로 얼마나 잘 나누어져(partitioning) 있는가에 대한 수치
• partitioning이란? 하나의 노드가 어떠한 그룹(community)에 속하도록 네트워크를 쪼개는 것.

Q = community s의 edge 수 - 기대되는 community s의 edge 수 이 수치가 클수록(즉, edge수 차이가 클수록) 매우 strong group이라고 할 수 있습니다.

따라서, "기대되는 community s의 edge 수"를 찾기 위해 null model이 필요합니다.

Null model : Configuration Model

Real network G는 n개의 노드와 m개의 엣지를 가지고 있으며, 이를 이용해 rewired network G'을 만들 수 있습니다.

G'은 G와 같은 차수의 분포(degree distribution)를 가지고 있지만 uniformly random하게 연결되어 있으며, multigraph로 가정합니다.

노드 i, 노드 j의 degree를 $k_i, k_j$ 라고 할 때, edge의 기대값은 ${k_i} × {k_j \over 2m}$ 입니다.

${k_j \over 2m}$는 노드 j와 연결될 확률입니다. 또한 모든 노드는 2번씩 count되기 때문에 2m이 분모가 되며, multi-graph이기 때문에 노드 i의 degree인 ${k_i}$를 곱해주는 것입니다.

Modularity

• ${A_ij}$: 두 노드 사이의 edge 개수
• ${k_ik_j \over 2m}$: expected number of edges
• ${1 \over 2m}$: Normalizing constant

m개의 엣지를 가진 그래프가 가질 수 있는 엣지의 합이 최대 2m 였으므로, 2m으로 나눠줘 normalizing 해주면 Q는 -1과 1사이의 값을 가지게 됩니다.

또한 보통 0.3과 0.7 사이 정도면 Significant Community Structure가 있음을 의미합니다.

강의 중 질문에서 Q의 값이 negative일 때의 의미는 서로간에 거의 상관이 없는, 연결되어 있지 않은 community를 정의한 경우라고 합니다.(연결 되어야 하지만 연결되지 않은 경우)

Equivalently modularity는 위와 같이 표현될 수 있으며 ${c_i}$와 ${c_j}$는 노드들의 community입니다. $\delta(c_i,c_j)$는 indicator function으로 같은 그룹일시 1, 아니면 0 입니다.

3. Louvain Algorithm

Community detection을 위한 Greedy Algorithm이며, 시간복잡도 O(nlogn)으로 매우 빠른 휴리스틱 알고리즘 입니다.

가중치 그래프도 지원하고, Hierarchical communities detection도 가능한데 이 경우 Dendrogram을 통해 네트워크의 Hierarchical한 구조를 나타낼 수 있습니다.

이 알고리즘은 빠르고, 수렴도 빠르고, High Modularity output을 도출해주기 때문에 네트워크에 널리 사용됩니다.

• Phase 1:
  • 가장 처음은 각각의 노드가 single community라고 생각
  • 노드 i를 어떤 neighbor j의 community 속에 넣으면 발생하는 modularity 값의 증가량(Modularity delta: $\Delta Q$)을 측정
  • 노드 i를, 가장 큰 $\Delta Q$를 발생시키는 community로 이동
  • $\Delta Q$의 변화가 없을 때까지 Phase1 계속 실행
• Phase 2:
  • Phase 1에서 찾은 community들을 모아 single super-node를 만들어 줌.
    • Super-node들 사이에 하나의 Edge라도 있으면 연결
    • 두 Super-node 간의 edge 가중치는 커뮤니티 간 모든 Edge 가중치들의 합
  • 다시 Phase 1으로(한 개의 Community를 찾을 때까지 계속 반복).

$\Delta Q(i→C)$ : 노드 i를 C community에 추가시켰을 때 Q의 증가량 $\Delta Q(D→i)$ : D community 에서 노드i를 제거시켰을 때 Q의 증가량 $\Delta Q$ = $\Delta Q(i→C) + \Delta Q(D→i)$

위의 그림은 $\Delta Q$식을 더 구체적으로 보여주는 내용입니다.

위의 그림은 Louvain algorithm의 전체적인 과정을 나타냅니다.

4. Detecting Overlapping Communities: BigCLAM

앞에서의 Community들은 모두 Non-Overlapping 이었지만 실제로는 고등학교 동창이면서 대학교 동창일수도 있는 것처럼 Community가 겹치기도 합니다. 여기서는 이에 해당하는 Overlapping Community를 Detect할 수 있는 방법을 알아봅니다.

이는 인접행렬(adjacency matrix)에서도 확인할 수 있는데 만약 community가 discrete하다면 위의 그림처럼 겹치는(overlap) 부분이 존재하지 않을 것이며, 반대로 한 노드가 여러 community에 속할 수 있다면 아래의 그림처럼 겹치는 부분이 존재할 것 입니다.

마찬가지로 Overlapping Communities도 2가지 step으로 진행됩니다.

• Step1
  • Node Community affiliation에 근거하여 graph generative model을 정의
  • Community Affiliation Graph Model (AGM)
• Step2
  • Graph G가 AGM을 통해 만들어졌다는 가정 하에 진행.
  • AGM의 파라미터는 Graph G를 만드는데 사용되며, AGM이 G를 generative하도록 파라미터를 학습시킴. (MLE)
  • 여기서 파라미터는 node가 community에 얼마나 속하는지 알려줌.

왼쪽 그림의 A, B는 communities이며, 밑의 점들은 네트워크 노드 입니다. community와 노드가 이어져 있다면 해당 노드는 해당 community에 속해있는 것이며, 양쪽 community에 모두 이어져 있다면 양쪽 모두에 속하는 것입니다.

이러한 Community affiliation가 모델을 거쳐 네트워크(오른쪽 그림)가 됩니다.

• Generative model issue: 어떻게 edges를 design할 것인가?

• Model Parameters: ${V, C, M, p_c}$
• $p_c$: 어떤 노드가 c community와 연결될 확률
• $M_u \cap M_v$: 노드 u, 노드 v의 공통 communities
• $p(u,v)$ : u,v가 서로 연결되어 있을 확률, 1 - 두 노드의 공통 community에 속하지 않을 확률들의 곱

• 적어도 하나의 공통 커뮤니티에 속할 확률

AGM은 Overlapping 양상에 따라서 다양한 Community Structure를 표현할 수 있음.

지금까지는 model로 네트워크를 생성했지만, 반대로 네트워크로 model(어떤 노드가 어떤 커뮤니티에 속하는지)도 만들어야 합니다.

• Maximum Likelihood Estimation 사용
• F에서 생성된 network가 G이길 바라기 때문에 G를 잘 만들어낼 수 있는 F(model/parameter)를 찾으면 됨. -> real G와 가장 비슷한 G를 만들자!

이를 위해 F(model/parameter)가 주어졌을 때 G가 나올 확률(Graph Probability)을 구하고, 이 확률을 최대화(argmax) 시키는 F를 찾아야 합니다.

이것을 위해 우리는 (1) F가 주어졌을 때 G가 나올 확률을 구해야하고, 이 확률을 (2) 최대화시키는 F를 찾아야 한다.

• Graph Likelihood $P(G|F)$ : F가 주어졌을 때 G가 나올 확률
• 오른쪽 행렬에서 $(u,v) ∈ G$ 일 때 1, $(u,v) ∉ G$ 일 때 0

"Relaxing" AGM: Towards P(u,v)

위의 모델은 0,1을 사용하여 노드들이 given community의 member인지 아닌지를 따졌지만, 여기선 모든 node community membership의 strength를 따져보기로 합니다.

• $F_u$: 노드 u가 각각의 커뮤니티에 속할 확률을 가진 벡터
• $F_uA$: 노드 u가 community A에 속할 확률

• $exp(F_u·F_v)$: 노드 u와 노드v가 각각의 커뮤니티에 동시에 속할 확률 (하나의 노드라도 어떤 커뮤니티에 할 확률이 0이라면 둘의 product는 0)

노드 u와 v가 각각의 커뮤니티에 동시에 속할 확률은, shared memberships의 strength에 비례합니다.

• $l(F)$: log-likelihood

결국 BigCLAM Model은 F가 주어졌을 때 G가 나올 확률을 구하고, 이 확률을 최대화시키는 F를 찾고자 하는 것입니다. 즉, log-likelihood를 최대화 하는 F를 찾는 것입니다.

Reference

https://tobigs.gitbook.io/tobigs-graph-study/chapter4.-community-structure-in-networks https://data-weirdo.github.io/data/2020/09/05/data-graph-04.communities

Contents

1. Motifs and Structural Roles in Networks
2. Subgraphs, Motifs, and Graphlets
3. Graphlets: Node feature vectors
4. Finding Motifs and Grphlets
5. Structural Roles in Networks
6. Discovering Structural Roles in Networks

we are going to talk about two topics about Network motifs graphlets and then the discovery of structural roles in networks

이번 3번째 강의에서는 Network motifs와 graphlets, 그리고 networks에서의 구조적 역할(discovery of structural roles)에 대해서 다루게 됩니다. 전체적인 graphs와 networks 보다는 구성 요소인 subnetworks에 대해서 보다 배우게 됩니다.

1. Motifs and Structural Roles in Networks

subgraphs는 networks의 구조를 identify하게 하고 다른 유형의 network와 구별할 수 있게 특징화하며 주어진 node를 통해 network의 구조를 describe할 수 있게 해줍니다. 예를 들어, 레고 또한 작은 레고들의 모음으로 만들어진 하나의 레고 집합이며, 작은 레고들은 서로 구별될 수 있는 모양과 역할을 가지고 있습니다.

그러므로 이번 강의의 목표는 bigger network를 구성하는 small network인 subgraphs(=sub networks)에 대해서 배우며 이러한 these building blocks에 대해 이해하는 것입니다.

위는 bigger network를 작은 구조의 network로 분해한 것을 보여줍니다. 3개 노드의 non-isomorphoic한 graphs는 총 13개의 경우의 수를 가지게 됩니다.

they have a different number of edges and in in what they differ is what are the directions of these edges and how many edges there are

이 모든 graphs들은 모두 non-isomorphic인 distinct한 특징을 가지고 있습니다.

isomorphic는 graph가 같은 edges와 같은 방향을 가지고 있으므로 다른 방법으로 그려짐에도 본질적으로 같은 grpah임을 의미합니다.

즉 non-isomorphic graph는 edges에 대한 다른 방향을 가지고 있으므로 본질적으로 동일하지 않은, 다른 graph임을 의미합니다.

그렇다면 이렇게 bigger network를 구성하는 subgraphs들의 frequency와 occurrence에 따라 정해지는 significant(중요성)에 대한 metric에 대해 생각해볼 수 있습니다.

the significance value가 negative 혹은 positive 하다면 network 내에서 under-represented 되거나 over-represented 라고 해석할 수 있습니다.

그렇게 되면 우리는 주어진 network에서 가능한 graph에 대한 significance profile을 작성할 수 있습니다.

위는 다른 유형의 network를 보여줍니다. 앞서 언급한 3개의 노드에서 발생하는 유니크한 13개의 subgraphs가 있을 때, 다른 유형의 network에서 어떻게 significance가 달라지는지 확인해볼 수 있습니다.

각 network는 Gene regulation networks, Neurons networks, Web and social betworks, Language networks 입니다. 각 그림의 y축은 significance profile이며 network의 유형에 따라 subgraph의 significance가 달라짐을 볼 수 있습니다.

첫번째 subgraph의 significance는 Language networks에서는 over-represented이지만 Web and social networks에서는 under-represented 되었음을 알 수 있습니다.

그렇다면 어떻게 subgraph의 significance가 정의되고 계산되는지에 대해 학습할 수 있습니다.

이 강의에서는 3개의 주제에 대해 다루게 됩니다

• 먼저 subgraph에 대해서 다루게 되고 network motif와 graphlets의 개념에 대해 정의 후 motif와 graphlets을 찾는 알고리즘에 대해 배우게 됩니다.

• 이러한 개념에 기반하여, network에서 노드의 구조적 역활을 찾는 방법에 대해 배우게 됩니다.

• 마지막으로 활용 사례에 대해 다루게 됩니다.

• first we kind of we will talk about sub graphs and we will define a notion of network motif and we will define a notion of graphlets and then I will talk about algorithms to find motifs and graphlets

• using these types of concepts we will talk about how do we discover structural roles of nodes in the network

• I'll show you some applications of these things

2. Subgraphs, Motifs, and Graphlets

Network motifs의 정의는 significant recurring pattern of interconnections in the network 입니다. network motifs를 정의하기 위해서는 pattern, recurring, significant의 대한 개념을 정의해야 합니다.

• Pattern: Small induced subgraph, subgraph가 유도가 될 수 있는 패턴을 의미하는 것 같습니다.

induced: if you have a set of nodes then, you take all the edges between that set of nodes

• Recurring: it occurs muiltiple times with high frequency, 발생 빈도를 의미하는 것 같습니다.

• Significant: more frequent than expected, significant 혹은 more frequent라고 하기 위해서는 비교를 할 수 있는 baseline이 필요하다고 말합니다.

그렇다면 왜 sub structures, motifs가 필요할까요? 위에는 다른 유형의 motifs에 대한 예시가 있습니다. Motif는 어떻게 network가 작동하는지에 대해 이해할 수 있도록 해주며 주어진 상황에서 network의 operation과 reaction을 예측할 수 있도록 도와줍니다.

subgraph를 induced하는 과정에 대해 알아보겠습니다. motif of interest가 주어졌을 때, network에서 해당 subgraph가 나타나는지 찾아볼 수 있습니다. 주어진 motif는 3개의 node와 2개의 edges로 이루어져있는데, 빨간선의 subgraph에서는 3개의 edges로 이루어져있기 때문에 해당 motif라고 할 수 없으며 파란선의 subgrpah가 주어진 motif와 pattern이 동일하다고 할 수 있습니다.

즉, 빨간선의 subgraph는 내가 가지고 있는 pattern에 존재하지 않기 때문에 induced(유도)되지 못한다..라고 이해했습니다.

두번째는 recurrence의 개념을 정의하는 것입니다. recurrence의 개념은 중복을 허용하여 주어진 motif의 패턴이 몇 번 발견되는지 입니다. 위와 같이 어떠한 motif가 주어졌을 때, 다음과 같은 graph에서는 해당 motif가 4번 발견됩니다. node의 중복을 허용하기는 하지만 결과적으로 발견된 4개의 motif는 다르다고 할 수 있습니다.

다음으로는 significance를 계산하는 과정을 가집니다. significance를 계산하는 핵심 아이디어는 비교하고자 하는 network와 랜덤 생성된 network에서 주어진 motif의 발생 빈도를 비교하는 것입니다.

그림을 보면 좌측의 target network에서는 주어진 motif(feed-forward loop)가 많이 발견되었고 우측의 랜덤하게 생성된 network에서는 거의 발견되지 않습니다. 이렇게 랜덤 생성된 network와 비교했을 때, 해당 motif는 target network에서 over-represented 혹은 over-expressed 되었다고 할 수 있습니다.

significance는 본질적으로 그저 z-score의 개념을 의미합니다. 랜덤 생성된 network에서 발견된 motif의 발생 빈도의 평균과 표준편차를 사용하게 됩니다. 여기서 랜덤 생성된 network를 일반적인 모집단과 같이 생각하는 것으로 이해했습니다.

다음으로 network significance profile를 정의하는 방법이 있습니다. z-score를 z-score의 제곱근의 합으로 나눠줌으로써 해당 motif의 SP, Significance Profile을 구할 수 있습니다.

SP를 계산할 수 잇는 방법에 대해서 학습하게 되었습니다. 그러나 아직 랜덤 그래프를 생성하는 방법에 대해서는 모르며 랜덤 그래프를 생성할 어떠한 null model이 좋은지에 대해서도 생각해보아야 합니다. 만약 null model을 가지고 있다면, 우리는 다수의 랜덤 그래프를 생성할 수 있고 significance 계산을 위한 모집단의 평균과 표준편차를 구할 수 있습니다. 그러므로 다음에 다룰 내용은 어떻게 랜덤 그래프를 생성하는지에 대한 방법입니다.

우리는 랜덤 그래프를 생성하고자 합니다. 주어진 degree sequence를 사용하여 랜덤 그래프를 생성할 수 있는데, 이 degree sequence는 real graph(target?)에서 온다고 합니다.

• Spoke

nodes가 존재할 때, 각 node는 주어진 degree를 가지고 있습니다. 이 degree는 spokes라는 half edges 개수를 의미하는 것으로 이해했습니다. half edges가 존재하는 nodes를 연결함으로써 랜덤 그래프를 생성할 수 있습니다.

노드를 하나의 파티션으로 생각하게 되었을 때, 각 파티션끼리 한번 이상의 연결이 존재하게 되면 두 노드 간 edge를 형성하고 우측과 같은 랜덤 그래프가 생성될 수 있습니다.

이러한 방법은 랜덤 그래프를 생성하는 굉장히 빠르고 효율적인 방법입니다. 하지만 Spoke를 이용한 Configuration Model generation은 ‘Double Edges’나 ‘Self-loops’는 고려하지 못해 기존의 주어진 degree sequence를 유지하지 못한다는 단점이 있습니다.

• Switching

Switching은 보다 expensive한 방법이지만 주어진 degree sequence를 정확하게 유지할 수 있는 방법입니다. 아이디어는 랜덤 edge 쌍을 선택하여 cross하는 방법입니다. (A-B), (C-D)라는 edge 쌍을 선택하게 되었을 때, endpoint를 cross하게 되면 (A-D), (B-C)라는 새로운 쌍이 나타나게 됩니다.

이렇게 주어진 edge를 교체(swap)하는 느낌으로 랜덤 그래프를 생성하게 되면 주어진 degree sequence는 철저히 준수할 수 있게 됩니다. 그러나 해당 rewiring화는 과정은 spoke 방법에 비해 매우 느립니다.

일반적으로 랜덤 그래프를 생성할 때에는, 10,000개에서 100,000개 이상의 랜덤 그래프를 생성한다고 합니다. 보통 real graph의 크기에 따라 생성되는 그래프의 개수가 달라지긴 합니다.

랜덤 그래프를 생성한 이후에는 real(target) graph에 존재하는 subgraph의 significance를 모두 구할 수 있고 가장 높은 significance를 가지고 있는 subgraph를 해당 graph의 network motif라고 할 수 있습니다.

3. Graphlets: Node feature vectors

3번째 목차에서 배울 내용은 Graphlets라고 불리는 network motif의 extension입니다. graph motif의 개념을 사용하여 전체 network를 특징화할 수 있습니다. Graphlets의 개념을 사용한다면 주어진 node를 특징화할 수 있습니다. 주어진 node를 바탕으로 network 구조를 설명할 수 있게 됩니다.

전체 network에 대해서 다루기 전에, 네트워크 구성요소를 보고 node와 node 주변을 볼 수 있는데, graphlets에 의해 captured 된다고 합니다.

graphlets은 non-isomorphic한 subgraphs를 의미하며 위와 같은 subgraphs가 있습니다.

이러한 graphlets을 통해 node-level representation을 얻을 수 있습니다. motif가 전체 network에서 subgraph에 대한 metric이면, graphlets은 node에 대한 node-level subgraph metric이라고 할 수 있습니다.

여기서도 degree 개념이 차용되는데 노드의 인접한 edges의 개수라고 볼 수 있습니다. graphlet degree vector(GDV)는 주어진 노드가 연결된? 속한? graphlet의 개수

automorphism orbit은 주어진 subgraph에서 symmetries, 대칭성을 고려해줍니다. 여기서 graphlet degree vector(GDV)는 각 orbit position에서 node의 빈도에 대한 벡터를 의미합니다.

v 노드를 기준으로 GDV를 구하게 되면 c가 v 노드라고 가정했을 때 해당 graphlet이 존재할 수 없기 때문에 0번 발견됩니다.

이런식으로 GDV는 하나의 노드를 기준으로 73개의 차원으로 구성된 벡터라고 할 수 있습니다. 그렇기 때문에 이 벡터를 가지고 노드를 특징화할 수 있으며 다양한 것에 활용해볼 수 있습니다.

4. Finding Motifs and Grphlets

그렇다면 어떻게 motifs와 graphlets를 발견할 수 있을까요. 그리고 수학적으로 어떻게 motifs와 graphlets을 계산하여 식별할 수 있을까요. motifs와 graphlets을 발견하기 위해서는 2가지 challenges를 해결해야 합니다.

K-size의 motifs와 graphlets을 찾는다고 가정한다면, 2가지 단계를 거치게 됩니다.

• Enumerating: K-size의 가능한 모든 subgraphs를 찾는 과정
• Counting: 찾은 모든 subgraphs의 occurrences를 세는 과정

하지만 이 과정에서 매우 복잡한 computational problem인 np-complete 문제가 발생하게 됩니다. 보통 motifs와 graphlets가 5개에서 8개의 노드로 구성되면서 combinatorial explosion이 발생되기 때문입니다.

이번 강의에서는 Enumerating과 Counting을 위한 방법으로 2006년에 제안된 ESU 알고리즘을 다루게 됩니다.

ESU 알고리즘은 v 노드를 시작으로 새로운 노드를 추가해나가면서 subgraph를 만들어나가는 과정을 거칩니다. ESU 알고리즘은 재귀적 구조를 가지고 있으며 현재 시점의 subgraph를 저장하는 $V_{subgraph}$와 motif를 확장하기 위한 후보 노드를 보관하고 잇는 $V_{extension}$로 구성되어 있습니다. $V_{extension}$의 후보 노드가 $V_{subgraph}$로 이동하게 되면서 state가 업데이트되는 과정에서 재귀 구조가 발생한다고 볼 수 있습니다.

ESU 알고리즘의 수도코드는 위와 같습니다.

예시를 확인하게 되면 보다 쉽게 이해할 수 있습니다. 1번~5번의 노드로 구성되어 있는 그래프 G가 있을 때, k개의 depth(노드 개수)의 subgraphs를 추출할 수 있습니다. 먼저 각 노드를 시작점으로 생각하면 자연스럽게 확장 가능한 후보 노드를 $V_{extension}$에 저장할 수 있게 됩니다.

1번 노드를 시작으로 하게 된다면 1번 노드와 연결되어 있는 3번 노드가 $V_{extension}$에 추가될 것이고 아직 $V_{subgraph}$의 개수가 3이 되지 않았기 때문에 후보 노드 중 하나를 추가하는 재귀가 발생하고 $V_{subgraph} = {[1,3]}$이 되면서 3번 노드와 연결되어 있는 2,4,5번 노드가 $V_{extension}$에 추가됩니다. 그렇게 다시 한번 재귀 구조가 발생하면서 depth가 3인 subgraphs를 뽑아낼 수 있게 됩니다. 여기서 주의해야할 점은 후보 노드는 항상 시작 노드 v보다 크게 함으로써 중복을 피할 수 있게 됩니다.

이렇게 가능한 subgraph를 찾는 과정이 Enumerating 과정입니다.

다음 단계는 Counting 과정입니다. count를 하는 기준은 non-isomorphic한 graph를 토대로 subgraphs의 개수를 세주는 것입니다. 즉, 3개의 노드와 2개의 edge로 구성되어 있는 subgraph는 topologically equivalent한 isomorphic한 graph이기 때문에 해당 구조가 총 5번 나왔다고 할 수 있으며, 이 때 isomorphic을 구별하기 위해 Mckay's nauty algorithm을 사용했다고 합니다.

5. Structural Roles in Networks

Roles 은 네트워크에서 노드의 function이라고 할 수 있습니다. 일반적으로 생태계에서 종의 roles, 그리고 회사에서 개인의 roles와 같은 개념이라고 볼 수 있습니다. 회사에서 직무에 따라 부여되고 책임을 지는 roles이 달라지는 것처럼, 궁극적인 목표는 네트워크 구조에서 노드의 Roles를 식별하는 것입니다.

Role은 네트워크에 존재하는 비슷한 위치 및 기능을 가지는 nodes의 집합을 의미하는 자료구조라고 할 수 있습니다. 여기서 강조하는 부분은 Role은 Group 혹은 Community와는 다른 개념이라고 말합니다. Role은 similar position이라는 특징을 가지지만 무조건 연결되어 있을 필요는 없다고 합니다. 하지만 Group/Community는 서로가 densely하게 연결되어 있어야 합니다.

그렇다면 similar position 혹은 similar structural properties로 네트워크 내의 Role을 판단하기 위해서 Structural equivalence라는 개념이 사용됩니다. Structural equivalence는 노드 U, V가 다른 노드와의 관계가 동일하다면 구조적으로 동등한 role로 볼 수 있음을 의미합니다.

해당 예시 그래프에서 노드 3, 4가 Structural equivalence임을 알 수 있습니다. 노드 간 structural equivalence를 찾을 때에는 어느정도의 noise를 감안하기도 합니다.

6. Discovering Structural Roles in Networks

Roles은 네트워크 구조에 존재하는 노드의 서로 다른 특징을 구별해주기 때문에 매우 중요합니다. 또한 노드의 Roles를 가지고 위와 같은 여러 과제를 수행할 수 있습니다.

각 노드의 네트워크 구조 상 roles를 자동으로 찾아주는 방법으로 RolX가 있습니다. 해당 접근법은 unsupervised learning 방법에 속하며, 사전 정보를 요구하지 않습니다. 그리고 각 node에 mixture of roles를 부여하게 됩니다.

RolX에서 node의 role를 추출하는 과정은 다음과 같습니다.

• Node * Node 인접 행렬을 생성합니다.
• 모든 Node별 재귀 구조를 통해 descriptor를 생성해줍니다.
• 그 다음 Node * Feature(descriptor)이라는 새로운 행렬을 만들어줍니다.
• Role Extraction을 통해 Node별 Role에 대한 행렬과 Role을 설명해주는 Role * Feature 행렬이 output으로 나오게 됩니다.

node에서 feature를 추출해내는 재귀 구조에 대해서 한번 알아보도록 하겠습니다. 어떠한 재귀 구조가 형성되는지 언급하지는 않았지만 개인적으로는 인접 행렬의 정보를 기반으로 feature를 추출할 것이라고 이해했습니다. 결과적으로 Node * Feature 행렬이 만들어 지는데, node와 local network에 대한 정보와 neighborhood 정보, 그리고 노드와의 연결성에 대한 recursive 정보까지 포함한다고 말합니다.

이러한 feature extraction의 핵심 아이디어는 노드의 정보를 모아 새로운 recursive features를 생성하는 것이라고 할 수 있습니다.

• Local Features: 노드의 차수에 대한 모든 측정치

  • 방향 그래프라면, include in- and out-degree, total degree
  • 가중 그래프라면, include weighted feature versions

• Egonet Features: 노드의 egonet에서 계산되는 값

  • Egonet은 노드에서 유도된 subgraph의 노드와 이웃 그리고 모든 edges를 포함합니다.

base set of features 가 형성되었으면 집계를 통해 features를 더욱 확장시킬 수 있습니다. mean과 sum 이라는 2개의 집계 함수를 사용해서 이웃 노드의 평균 차수 혹은 이웃 노드 차수의 합 등과 같은 feature를 계속해서 늘려나갈 수 있게 됩니다.

그런데 재귀를 돌 때마다, 계산해야할 features의 수가 급증하기 때문에 pruning technique이라는 기법을 통해 features의 수를 줄일 수 있다고 합니다.

각 노드별로 노드를 표현할 수 있는 features가 벡터로 표현되었다면 clustering을 통해 Roles를 표현할 수 있게 됩니다. 이 때, 다양한 접근법의 clustering을 모두 적용해볼 수 있습니다. clustering 결과를 바탕으로 네트워크 상의 구조적 roles를 부여할 수 있고 role distributions을 통해 노드 간 유사도 또한 계산해볼 수 있습니다.

참고 자료

• Tobigs graph study, Chapter3. Motifs and Structural Roles in Networks
• 데이터 괴짜, CS224W - 03.Motifs and Structural Roles in Networks
• 이현준, cs224w 3강 정리( Motifs and Structural Roles in Networks)
• Wikidocs, 03-02 Finding motifs and graphlets

Contents

0. Intro
1. Network Properties: How to Measure a Network
2. Real-World Networks (MSN Messenger)
3. Erdos-Renyi Random Graph Model
4. The Small-World Model
5. Kronecker Graph Model
6. Summary

Properties of Networks and Random Graph Models

0. Intro

이 장에서는 기본적인 Network의 속성과 Random Graph Model 들에 대해서 배웁니다. 기본 속성의 개념과 용어를 숙지하는 위주로 리뷰하겠습니다.

Keyword degree distribution,path length,clustering coefficient, connected components,random graph model, small-world, kronecker graph

1. Network Properties: How to Measure a Network

Network 속성들, 즉 어떻게 Network를 정량적으로 측정하는지 알아보겠습니다. 크게 4가지 방법이 있습니다.

(1). Degree distribution : P(k)

degree distribution (차수 분포) 입니다. node에 연결 된 엣지의 갯수가 degree k 라고 할 때, 무작위로 선택한 node 가 k개의 차수를 가지고 있는 확률을 P(k) 라고 합니다. N_k 는 degree 가 k 인 노드의 수 이고, 이를 Normalize 해서 P(k)를 구합니다. histogram 으로 나타내면 다음과 같습니다.

(2). Paths in a Graph - 경로

Path : 각 노드가 다른 노드와 연결된 연속성을 경로라고 합니다. Distance(거리) : 연결된 node들의 가장 짧은 경로 입니다.
directed graphs 에서는 방향을 고려합니다. Network Diameter(직경) : 그래프에서 노드 간의 최대거리입니다. 어떤 그래프에서 Path의 최대값. 가장 먼 두 node의 거리를 나타내주는 값이라고 생각하면 됩니다. Average path length : directed graph에서 평균 경로 길이를 나타낼 수 있습니다.

(3). Clustering Coefficient - 결집계수

Clustering Coefficient 는 undirected graphs 에서 사용됩니다. 페이스북 소셜 네트워크 같은 곳에서 사용할 수 있습니다.

핵심 아이디어는 *노드 i 의 이웃들은 서로 얼마나 연결되어 있을까?* 입니다.

Clustering Coefficient 는 C 로 나타내고 0~1 사이 값을 가집니다. 노드 i 에 대한 C를 구하는 공식은 다음과 같습니다. 노드 i 의 이웃이 실제로 연결된 엣지 갯수 (e_i) 를 이웃 차수로 가질 수 있는 경우의 수 (k_i)(k_i -1)로 나눠줍니다. -> 두번째 경우, i 의 이웃은 4개의 노드가 있습니다. 이 이웃들이 실제로는 3개의 연결된 엣지를 가지고 있기 때문에 분모는 2x3 이고, 분모는 경우의 수 4x3이 됩니다.

Average clustering coefficient : 평균 결집계수는 각 노드의 C를 구한 값을 평균내서 구할 수 있습니다.

(4). Connectivity - 연결성

연결된 구성요소 중에 가장 큰 크기 입니다. BFS(너비우선탐색) 알고리즘으로 찾습니다. Lagest component = Giant component (뒤에서는 GCC라고 언급하기도 합니다.)

2. Real-World Networks (MSN Messenger)

이 네 가지 네트워크 속성이 Real-World Networks 에서는 어떻게 측정되는지 MSN Messenger 예시를 보도록 하겠습니다.

1. Degree Distribution

정의대로 분포를 시각화하면 분포가 잘 보이지 않아서 로그 스케일링한 log-log degree distribution을 보겠습니다. 대부분의 사람들이 10^3 정도에 몰려서 분포해 있고, 몇몇의 사람들이 더 높은 연결 수(degree k)를 가지고 있습니다.

2. Clustering

• 평균 결집 정도는 0.1140 입니다. 크다, 작다 판단 보다는 그냥 숫자로 이해해야합니다.
• C와 K간의 기울기를 보면 반비례함을 알 수 있습니다. degree 가 높은 node 일 수록, 이웃들 간의 연결(결집계수 C) 는 작아진다는 것을 의미합니다.

3. Connected Components

largest component(giant component)는 99.9% 의 노드들을 가진 큰 component임을 알 수 있습니다.

4. Diameter of WCC

MSN의 Network Properties

Another example: PPI Network (protein protein international Network)

(다른 도메인인데도 비슷하다!)

3. Erdos-Renyi Random Graph Model

Erdos-Renyi Random Graph Model 을 보겠습니다. 2가지 종류로 나뉩니다.

중점적으로 살펴볼 G_np 는 undirected graph에서 n개의 node들이 있을 때, 각 edge(u,v)의 확률 p가 iid 임을 가정합니다. (independent identically distributed, 상호독립 & 동일한 확률분포 가짐)

*이 그래프 모델이 어떤 network를 만드는지 살펴보겠습니다.*

Random Graph Model

Random Graph Model은 n개의 노드와 확률 p를 가지지만 그래프를 unique 하게 정의하지는 않습니다. (생성할 때 마다 다른 모양)

그럼 랜덤그래프를 앞에서 배운 4가지 속성으로 평가해보겠습니다.

1. Degree Distribution

random graph model G_np 의 degree distribution은 binomial(이항분포)을 따릅니다.

degree k의 평균과 분산도 이항분포의 공식으로 나타낼 수 있습니다.

2. Clustering Coefficient

C = 2*e_i / k_i(k_i -1) 임을 기억한다면, e_i의 기댓값과 C_i의 기댓값은 다음과 같습니다.

3. Path length

Expansion alpha : Expansion은 subset에서 edge가 퍼져나가는 정도로, 그래프에서 노드 S가 V의 부분일 때, S -> V로가는 edge의 수의 최소값을 Expansion alpha 라고 합니다.

alpha를 다음과 같이 수식화 할 수 있습니다.

처음 s개의 노드를 정하고 각각의 노드와 (α⋅S) edges로 연결된 노드들을 구한다. 그 다음, 새롭게 연결된 노드들까지 포함하여 S′ 노드들을 다시 하나의 subset으로 보고 (α⋅S') edges로 연결된 노드들을 구한다. 이렇게 모든 노드들을 방문할 때까지 반복하여 path를 구할 수 있다. path length는 O((log n)/α) 다. 우측 그림에서 노드 수가 증가할때 shortest path는 log 함수 형태로 증가함을 볼 수 있다.

즉 그래프 크기에 비해 짧은 경로들을 가지게 된다.

4. Connectivity

확률 p 에 변화에 따른 랜덤그래프의 구조는 위와 같은데, 확률이 커질 수록 (1에 가까울 수록) 모든 노드가 서로 연결되어 있는 Complete graph가 된다.

5. 비교

랜덤 그래프 모델과 실제 네트워크 (MSN) 을 비교해보면 Average Path length 와 Largest Connected Component에 대한 속성은 비슷하고 Degree distribution 과 Clustering Coefficient 은 달랐습니다.

Problems with random networks model

• Degree distribution이 실제 네트워크들과 다름
• 실제 네트워크의 Giant component는 phase transition을 통해 나타나지 않음
• local structure 가 없음. (=clustering coefficient가 너무 낮다.)

근본적으로 real world 가 random 이 아니기 때문에 완전히 fit 될리가 없습니다.

4. The Small-World Model

실제 Real world는 random graph model과 다르게 High Clustering을 유지하면서 small diameter를 유지합니다.

이러한 모델을 만들기 위해서 Small-World model 을 설명합니다.

small-world model 중에 Watts-Strogatz 를 살펴봅니다.

Low-dimensional regular lattice 에서 rewiring을 해준다면 절충되는 그래프를 만들 수 있습니다.

Low-dimensional regular lattice는 주변노드끼리만 이어져있는 네트워크를 의미한다. 즉, High clustering이고 따라서 High diameter입니다.

행운의 편지 전달에서 끼리끼리 그룹의 친구에게만 공유하는 것이 아니라 가끔은 별로 안친한 그룹의 친구에게 전달하는 것과 같습니다.

5. Kronecker Graph Model

오늘 강의의 3번째 모델로는 Kroneckr Graph Model을 살펴보겠습니다.

*핵심 아이디어는 Self-similarity (자기 복제)를 통한 재귀적 그래프 생성입니다. *

Kronecker Graph의 구조는 위와 같이 recursive model 입니다.

Kronecker Product : 인접행렬간의 행렬곱을 위와 같이 정의합니다.

Stochastic Kronecker Graphs

0,1 이 아니라 확률적으로 이루어진 Stochastic Kronecker Graphs는 아래와 같이 생겼는데, 하나의 graph를 생성하기 위해서 사건을 너무 많이 시행해봐야하는 문제점이 있습니다. (동전 던지기를 너무 많이 해봐야함)

-> 이는 노드 수가 증가하면서 run time 에 많은 영향을 주기 때문에 빠르게 생성하는 방법을 고안했습니다.

Stochastic Kronecker Graphs

Drop Edge : 빠르게 Kronecker graphs를 만드는 방법은 그래프에 edge 를 하나씩 'drop'하는 것입니다. (재귀적인 특성 이용)

재귀적으로 drop을 반복합니다. Fast Kronecker generator algorithm을 정리하면 위와 같습니다. 신기하게도 Kronecker 는 real-world 와 아주 닮아있습니다.

결론적으로 Kronecker Graph Model 은 확률적인 속성을 가지고, 적은 파라미터를 사용해서 real world에 잘 fitting 시킬 수 있다는 장점이 있습니다.

(Kronecker의 MLE와 자세한 유도는 http://www.cs.cmu.edu/~jure/pub/kronecker-cornell-Sept08.pdf 여기에 나와있습니다.)

6. Summary

*Graph Model의 4가지 속성에 대해서 배우고, 실제 예시에 대입해봤습니다. 실제 real-world를 설명할 수 있는 graph model 만들기 위해서 random graph model, small-world model, kronecker graph model에 대해서 배웠습니다. *

Reference

https://tobigs.gitbook.io/tobigs-graph-study/chapter2. https://leejunhyun.github.io/deep%20learning/graph/2019/03/05/CS224W-02/

Network: graph representation with data

• 네트워크는 서로 상호작용하는 entity 간 복잡한 시스템을 설명할 수 있는 범용 언어임
• 표현하고자 하는 object를 선으로 연결함으로써 network를 만듦
• 데이터 가용성을 고려하였을 때 다양한 도메인에서 사용될 수 있음
  • web/mobile, bio, health, medical, etc.
• Impact!
  • social network, drug design, AI reasoning

Many types of networks

• 모든 network는 저마다 object가 의미하는 바가 다르며, 그들간의 관계 또한 다름
• 주어진 network를 이해하지 못하면 모델링을 할 수 없음! (투빅스1강이 EDA인 이유)

Ways to Analyze Networks

• Node classification
• Link prediction
• Community detection
• Netwrok similarity

Structure of Graphs

Components of a Network

• Objects N: nodes, vertices
• Interactiosn E: links, edges
• System G(N, E): network, graph

Networks or Graphs?

• Network: real system

  • web, social network
  • Language: network, node, drug network

• Graph: netwowrk의 수학적 표현

  • web graph, social graph
  • Language: graph, vertex, edge

• 서로 경계가 모호하기때문에 일반적으로 혼용하는 편!

Choice of Network Representation

Direction of edges

• Undiredcted graph: 링크가 양방향인 그래프
  • EX) collaborations, friendship
• Directed graph: 링크에 특정 방향이 주어지는 그래프
  • citation/quotation, 인스타 DM, 팔로잉, 좋아요

Node Degrees

• Degree(차수): 노드에 부속되어 있는 link의 수
• Undirected graoph의 평균 차수 $\overline k = {1 \over N}\displaystyle\sum_{i=1}^{N} k_i = {2E \over N}$ ($E$=edge 개수, $N$=node 개수, $k_i$=i째 node의 차수)
• 위의 예시에서는 $k_A=4$
• Directed의 경우는 in-degree와 out-degree가 구분됨
  • 전체 차수는 두 가지 degree 총합임 $\overline k={2E \over N}$

Complete Graph

• undirected graph의 최대 edge 개수 $E_{max}={N(N-1) \over 2}$
• Complete graph: 최대 edge개수를 가진 undirected grpah

Bipartite Graph

• Bipartite graph: 서로 다른 종류의 독립된 노드들로 구성된 그래프
  • 두 가지 노드 타입 U, _V_로 나눌 수 있음
  • U에 속하는 노드는 V_에 속한 노드에게만 연결되고 **_U**끼리는 독립임
  • V_에 속하는 노드는 **_U에 속한 노드에게만 연결되고 _V**_끼리는 독립임
• Bipartite graph는 실제 도메인에서 많이 나타나는 구조이며, 특히 추천시스템에서 많이 사용되는 개념임

Representing Graphs

Adjacency Matrix

• Adjacency Matrix(인접행렬): 그래프를 연결 유무를 1과 0으로 나눠 행렬로 표현한 것
• Undirected의 경우 대칭으로 나타나며 Undirected는 단방향일 수 있기 때문에 대칭이 아닐 수도 있음
• 노드가 많아질 수록 즉, 행렬의 차원이 커질 수록 Sparse해진다는 단점이 있음

Edge list

• Edge를 연결된 노드 쌍으로 표현한 것

Adjacency list

• 출발방향의 노드를 Key값으로, 도착 노드를 Value값으로 가지는 Dictioanry형태
• 단방향이거나 거대한 그래프에서 효율이 좋음

Edge Attrbutes

• Weight: edge에 weight를 줄 수 있음 (와인 추천 시 와인에 대한 평점을 edge에 weight 주기)
• Ranking: 짱절친, 절친, 아는 사이
• Type: 친구, 친척, 직장동료

More types of Graph

Connectivity of Undirected Graphs

• Connected graph(undirected): 어떤 노드에서 출발하든지 다른 모든 노드로 도착할 수 있음
• Disconnected graph: 최소 2개 이상의 connected graph로 구성됨
• Bridge edge: 삭제되면 connected에서 disconnected로 바꿀 수 있는 edge
• Articulation node: 삭제되면 connected에서 disconnected로 바꿀 수 있는 node

• Disconnected의 경우 인접행렬은 block-diagonal 형태가 된다

Connectivity of Directed Graphs

• Strongly connected directed graph: 어떤 노드에서 출발하든지 edge방향을 지키면서 다른 모든 노드로 도착할 수 있음

• Wealky connected directed graph: 어떤 노드에서 출발하든지 edge방향을 무시한다면 다른 모든 노드로 도착할 수 있음

• Strongly connected components(SCCs): 그래프에서 부분적으로 나타나는 connected subgraph

  • SCCs 포함유무에 따라 In-component, Out-component로 분류