CS224W - 03.Motifs and Structural Roles in Networks

in Data on Graph


Motifs and Structural Roles in Networks

부분그래프 (Subgraph = Subnetworks)

  • Network의 Building block
    GNN03-1
  • 부분그래프의 역할
    1. Characterize the network
    2. Discriminate the (types of) network
    Subnetworks have the power to characerize and discriminate networks.

  • 예를 들어, 3개의 노드를 가진 Non-isomorphic한 모든 방향 그래프를 생각해보자.
    -> 13개를 생각해볼 수 있음
    GNN03-2

    • 이 때, 각 subgraph들에 대해, 이들의 Significance를 분류해볼 수 있는 metric은 없을까?
      (Negative value를 지닌다면, under-representation으로 평가하고
      positive value를 지닌다면, over-representation으로 평가하는)
      ↓

      Network Significance Profile

      : 모든 Subgraph 타입들에 대한 값들(values)을 갖고 있는 feature vector
      각 Subgraph들이 over-represented 되었는지, under-represented 되었는지를 보여줄 숫자.
      • 단, domain이 다르면 network도 다르다.

      GNN03-3

        1. 네 가지 plot들은 모두 다른 종류의 네트워크를 표현  
  2. 1번 Subgraph를 예로 들어 생각해보면,  
    Language netowrk에서는 over-represented 되어있으나  
    Web & Socail network에서는 under-represented 되어 있음.  
  3. 각 network 마다의 그래프는 모두 다르지만, 서로 행동 양태가 상당히 비슷함.  
  4. y-axis가 바로 significance profile
      • 4번에서, ‘significance profile을 어떻게 generate 하는가?’에 대한 답은 아래의

        Network Significance Profile (SP)

        를 참조.

Subgraphs, Motifs, and Graphlets

Network motifs

:= “Recurring, Significant Patterns of interconnections”. (하나의 정의로 생각하면 됨)

  • Pattern: 작은 Induced subgraph
  • ‘Recurring’: 고빈도로, 자주 발견됨.
  • Significant: 생각했던 것보다 더 Frequent
    └-> 역시 그 비교기준이 필요하고 -> 그 기준으로 ‘Erdos-Renyi random graphs, scale-free networks’등을 사용

Motifs

  • 네트워크가 어떻게 작동하는지를 이해하는 데에 도움을 줌

  • 주어진 상황에서 연산(operation)과 반응(reaction)을 예측하는 데에 도움을 줌

  • 예시
    GNN03-4
    • cf. Feed-forward loops: 딥러닝에서의 Skip connection

위 Network Motifs에 대한 구체화

  • Induced Subgraph in Pattern
    GNN03-5
  • Recurrence
    GNN03-6
  • Significance
    • 아이디어: Random Network를 generate했을 때, 특정 Subgraph가 Real Network에서 훨씬 많이 나타난다면, 그 Subgraph는 functional significance를 갖고 있을 것!
      GNN03-7
    • 통계학의 Z-score 개념을 차용

      이 가 motif i의 Statistical Significance를 포착함.
      GNN03-9

Network Significance Profile (SP)

GNN03-8

  • 이제 이까지, Network Motif의 정의에 대해 알아보면서, Induced Subgraph란 무엇인지, Recurrence란 무엇인지, Significance란 무엇인지에 대해 알아봄
    Subgraph 파트에서, Network Significance Profile(SP)라는 개념을 통해, Significance를 어떻게 계산하는지를 알아보았는데,
    다른 하나의 궁금증은 -> Random graph들은 어떻게 generate 해야 하는가? 좋은 Null model이란 무엇인가?

Configuration Model

  • Degree Sequence k_1, k_2, …, k_N이 주어졌을 때, random graph generate해내는 방법 개념 이해
  • 네트워크의 Null Model로서 유용

  • Configuration Model을 통해 만들어낸 Random Graph는,

    • 노드(Nodes)의 개수
    • 간선(Edges)의 개수
    • Degree Distribution

    세 가지 모두 Real Graph와 같아진다.

  • Configuration Model을 generation 하는 방법?

    1. Spoke!  
2. Switching!

    1.Spoke

    GNN03-10

    • 4개의 노드가 있다고 가정했을 때, Real 그래프에서의 각 노드들은 각자의 Spoke들을 지니고 있음
    • 먼저 노드 A에서부터 시작해, spoke의 수를 유지하면서 확장해나감.
    • Node B가 이상함을 느낄 수 있는데 (분명 Real 그래프에서의 spoke수는 4였는데, random graph에서는 3개가 나옴) 이런 bad event는 ‘Exponentially rare’
    • 초록색 글자로 언급되었듯, Spoke를 이용한 Configuration Model generation은 ‘Double Edges’나 ‘Self-loops’는 고려하지 못한다는 단점이 있음.

    2.Switching

    • Spoke에 비해서 훨씬 expensive한 방법이지만, 원 그래프에서의 Degree Sequence를 완벽하게 유지함.
    • Real Graph에서 시작해서, Edge들을 충분히 Cross시켜준다.
    • 그럼 결과는 ‘Randomly rewired graph (with same node degrees)’
      GNN03-11
      • 여기서 Q: Repeat times.
      • converge: converge to a uniform sample

  • Spoke나 Switching을 통해서 random graph를 generate하면, (위에서 본 적 있던 그래프가 다시 등장) 비로소 Network Significance Profile을 얻어낼 수 있게 됨
    GNN03-12

    GNN03-13

    • 물론, Motif에도 다양한 변형(Variation)들이 있음.
      GNN03-14

Graphlets: Node feature vectors

  • Graphlet: Network Motif의 Extension으로 이해하면 편함
    • Network Motif: ‘전체’ 네트워크를 characterize하는 데에 사용
    • Graphlets: 주어진 ‘노드‘를 characterize하는 데에 사용
  • Graphlets
    GNN03-15
    • 그래프의 크기↑ → graphlet의 갯수↑

    • 가령, G1과 G2는 노드의 개수는 같지만, non-isomorphic position에 있음.

    • 일반적으로 그래프에서 써왔던 ‘Degree’라는 개념
      -> Graphlets에서도 물론 적용 가능.
      -> Graphlets에서는 Graphlet Degree Vector라는 개념을 도입

    • Automorphism orbit: 부분그래프의 대칭성을 고려 (즉, Isomorphism between the same object)
    • Graphlet Degree Vector: 각 orbit position에서 노드의 빈도를 기록한 벡터
      GNN03-16
      • Graphlet Degree Vector를 통해 노드의 국소적인 네트워크의 위상(local network topology)에 대한 measure를 제공

Finding Motifs and Graphlets

  • 그렇다면, Motif와 Graphlet을 어떻게 찾는가?
    • Size가 k인 motifs / graphlets 를 찾는 게 목표라고 하자

    • 두 가지 문제를 해결해야 함

      1. Enumerating  
2. Counting
      • 1, 2를 위한 연구가 굉장히 활발.
    1. Enumerating
      Size-k 짜리의 모든 instance를 찾는다.
    2. Counting
      모든 Instance들에 대해 Isomorphic instance들의 개수를 센다.
  • 특정 Subgraph가 그래프 내에 존재하는지 찾는 것은 Hard computational problem!
    Motif size가 3~8일 때가 그나마 Feasible한 허용 범위.

Enumerating & Counting을 위한 방법론

  • Exact subgraph enumeration (ESU) [Wernicke 2006] <- 오늘 다룰 알고리즘
  • Kavosh [Kashani et al. 2009]
  • Subgraph sampling [Kashtan et al. 2004]
Exact Subgraph Enumeration (ESU)
  • 두 가지 집합
    GNN03-17
    • V_subgraph: 특정 시점까지 만들어놓은 부분그래프
    • V_extension: 그 Subgraph를 확장하는 데에 사용할 노드 후보군들의 집합

  • Idea
    GNN03-18

  • Recursive Implementation!
    • Depth k의 트리 구조와 유사하다. (ESU-Tree라고도 불림)
    • Pseudo-code
      GNN03-19
  • 예시

    • 다음과 같은 Real Graph가 있다고 가정하자.
      GNN03-20
      이 Graph에 대해 ESU-Tree 알고리즘을 적용

      k=3인 경우를 가정

      1. Enumerate
        GNN03-21
      2. Count
        GNN03-22
      • 두 개의 non-isomorphic한 size-3의 Subgraph들 탄생
      • 첫 네 개의 subgraph들은 topologically equivalent (Isomorphic) -> Isomorphic한 Subgraph들은 묶는다(group).
      Isomorphic?
      • 다음을 만족하는 Bijection f:V(G) → V(H)가 존재하면 그래프 G와 H는 Isomorphic하다.
        그래프 G 임의의 두 노드 u와 v가 adjacent <=> 그래프 H에서 f(u)와 f(v)가 인접
        GNN03-23
        -> G and H are Topologically Equivalent!
        • Cf. 위 그림에서 9! 만큼의 모든 bijection의 경우의 수를 확인하는 것은 Computationally Really Hard
          -> 사람들은 Brute-force Search와 같은 알고리즘 등을 사용해서 이를 해결

Structural Roles in Networks

  • Role?
    네트워크 상에서 노드들의 “Function”
    GNN03-24
    GNN03-25
  • Role과 Group은 다른 개념이다.
    • Role: 유사한 구조적 특성을 지닌 노드들의 그룹
      • 노드들이 꼭 연결되어 있을 필요는 없다.
    • Group: 노드들 간에 잘 연결되어 있는 노드들의 그룹
      • 노드들은 서로 연결되어 있어야 한다.

    GNN03-26

  • Structural Equivalence
    노드 u와 v가 다른 모든 노드들에 대해서 동일한 Relationships를 갖고 있다면 Structurally Equivalent
    GNN03-27
    • 다음과 같은 예에서는 노드1과 2가, 노드 3과 4가 서로 Structurally Equivalent
      GNN03-28
      (다만, 이처럼 완벽히 Equivalent한 게 아니라, 어느 정도의 Noise를 ‘Clustering’을 통해 허락할 것)

Discovering Structural Roles in Networks

  • RolX: 네트워크에서 노드들의 Structural Roles를 발견하는 automatic한 방법
    • 비지도 학습 방법
    • Prior Knowledge 없음
    • 각 노드에 role들의 mixed-membership 할당

    GNN03-29

  • RolX Overview
    GNN03-31

    • 결국, Node by Node의 인접행렬에서, 재귀적으로 Feature를 추출하여, Node by Feature 행렬을 만들어주고,
      이로부터 Role을 추출하여 두 가지 Matrix(Node by Role 행렬, Role by Feature 행렬)를 결과물로 도출

    • ‘Recursive Feature Extraction’
    • ‘Role Extraction’

Recursive Feature Extraction

  • 네트워크 연결성(Network Connectivity)를 Structural Feature로 바꾼다.
    GNN03-32
    • Neighborhood Features: ‘노드들의 연결성 패턴은 무엇인가.’

    • Recursive Features: ‘한 노드가 어떤 종류의 노드들에 연결되어있는가.’

    • Idea: ‘노드의 Feature들을 모아서, 이를 새로운 Recursive Features를 generate하는 데에 사용하자.’
  • Neighbor Features의 구성 요소
    • Local Features
      노드 차수(degree)에 대한 모든 측정
      • 방향 그래프라면, 전입, 전출 차수, 총 차수 등의 정보를 포함
      • 가중치 그래프라면, Weighted Feature versions를 포함
    • Egonet Features
      Node의 Egonet 상에서 계산
      • Egonet: 노드, 그 이웃노드, 이 노드들의 Induced Subgraph 내 Edge들 로 구성
      • 두 가지 새로운 Feature에 대해 계산할 수 있음

        • of within-egonet edges (Friends들 사이에서의 Edge의 개수)

        • of edges entering/leaving egonet

    • 이 두 Feature들로부터 추가적인 피쳐(Additional Feature)를 Generate
      • 두 가지 Aggregate Function을 사용 (Mean & Sum)
        (인접 행렬 차수의 평균은? 인접 행렬 차수의 합은?)
    • 가능한 Recursive Features의 수는 recursive iteration을 돌 때마다 Exponential하게 증가하는데,
      Pruning Technique를 사용해서 Feature들의 수를 줄일 수 있다. (다양한 Pruning Technique들이 사용 됨)
      ex) Highly correlated된 Feature Pairs를 찾아서, user-defined threshold를 상회하는 correlation을 보이면, Feature Pair 중 하나는 제거
      GNN03-33

Role Extraction

GNN03-34

  • Setup
    • RolX를 사용해서 Recursive Feature Extraction & Clustering을 한 후, 각 노드에 발견된 structural roles에 대한 분포를 할당

    • 노드들의 Role 분포를 비교함으로써 유사성(Similarity)을 결정

    • 예시
      GNN03-35

References

CS224W: Motifs and Structural Roles in Networks