Contents
- Networks and Applications
- Structure of Graphs
1. Networks and Applications
1. Network
Networks are a general language for describing complex systems of interacting entities!
= 상호작용하는 특성들을 설명
우리가 살고 있는 세상 속에는 생각보다 많은 도메인에서 많은 요소들이 네트워크로 구성되어 있다 ~
모든 network는 도메인마다 다르고, 각 네트워크에 존재하는 object의 의미와 관계 모두 다 다르다 ~
Network를 통해 괜찮은 Relational Structure 를 구축한다면 ~?
= By explicitly modeling relationships, we achieve better performance
= 네트워크를 이해하면, 이런 시스템을 모델링하고 예측할 수 있게 된다
그럼.. why network?
1. univeral language for describing complex data
2. shared vocab btw fields
3. data availability & computational challenges
4. impact! (Google, Facebook, Amazon, ...)
2. Applications
Ways to Analyze Network
- Node classification : 주어진 노드의 color, type 예측
- Link Prediction : 두 노드 사이가 연결 되어 있는지 예측
- Community detection : 밀도 있게 연결된 노드 클러스터 구분
- Network Similarity : 두 노드/네트워크 사이의 유사도 측정
Application Examples
- 소셜 네트워크 : Social Circle Detection
사람들 사이의 관계 그래프로 표현 ~
- Infrastructure
- Knowledge
특정 개념/특성들의 관계를 그래프로 표현
link prediction : node를 embedding 함으로써, 비슷한 네트워크를 가진 노드가 서로 가까이 있도록 설정...
-> (나의 이해) 노드 임베딩 하면 비슷한 특성을 가진 노드는 비슷한 embedding space 에 존재하게 되는데, 이 때 비슷한 임베딩 공간에 존재하고 있는 노드에 연결되어 있는 다른 이웃 노드들 추천
-> 비슷한 embedding space 에 있는 것 graph-based 로 추천!
- Online Media
- Polarization on Twitter : 양 극단에 몰려 있는지...
- Misinformation
진짜 뉴스는 이렇게 서로서로 연관성이 있는데, 가짜 뉴스는 연결이 안 되어 있다. random 으로 구분하거나(50%) human이 구분(66%)하는 것 보다 graph-based로 구분(86%)하는 것이 훨씬 성능이 좋다
- Predicting Virality : 이미지 또는 비디오가 급속하게 유포될 때, 어떻게 유명하게 되었는지 파악 가능
- Product Adoptation : 사람들이 어디서 유입되었는지.. 체크 체크 (ex. 멤버십 가입, LinkedIn 연결 등등)
- BioMedicine
- Side Effect 가 어디서 왔는지 파악 가능 (인과추론 개입효과랑 느낌이 비슷..ㅎㅎ)
- Biomedical Graph : drug 와 protein 사이에 interaction 뭐가 있고 side effect 뭐가 있는지 등등...
Why Graph?
🙋🏻 학생 질문 :
그래서 그래프 네트워크 왜 하나용? 안 와닿아요
🙆🏻♀️ 답변 :
prob : we don't have enough data
do : capturing prior knowledge network
to be efficient the amount of data you have
result : provide information
2. Structure of Graphs
Component of Graphs
Network Representations
- unidirectional : 방향성 없는 그래프
ex. collaborations, friendship (협업) - directional : 방향성 있는 그래프
ex. 인스타 following, 좋아요
unidirected 에서는 연결된 개수만 구하면 되서 degree 로 표현하지만,
directed 에서는 방향성도 고려해야 하기 때문에 in-degree, out-degree 구분
- Unidirected 에서의 A node의 degree 값 = 4
- Directed 에서의 Source Node : G
- Directed 에서의 Sink Node : 없음
Complete Graph
모든 노드에 모두 연결 ~ everyone links to everyone!
최대 edge 개수를 가진 undirected graph
Bipartite Graph
서로 다른 종류의 독립된 노드들로 구성된 그래프!
U-V 사이만 연결되어 있고, U끼리는 연결 No & V끼리도 연결 No No
대표적인 예시가 pinterest! + Authors-to-Papers, Actors-to-Movies they appeared in 등등 ...
실제 도메인에서 많이 나타나고 있는 구조라고 함 ~
(추천시스템 CF - U : user, V : item)
Folded Bipartite Graph
bipartite graph를 펼쳐서, neighbor in common이 존재하면 연결 ~
ex. Projection V
A와 B는 2 라는 공통 요소를 가지고 있어서 연결되지만,
A와 C는 공통 yellow node 가 없어서 연결이 안 됨
Adjacency Matrix
인접행렬! (+ 알고리즘에서 맨날 본 bfs dfs ㅠㅠ)
- 연결 되어 있으면 1, 연결 안 되어 있으면 0 ~
- unidirectional 한 경우 diagonal 하지만, directional의 경우 노노
- 각 노드에서의 degree는 해당 행/열을 다 더한 값
- 인접행렬은 sparse 하다...
- edge list : 연결된 노드의 집합
Edge Attributes
- Unweighted / Weighted : edge 굵기가 달라짐
- self-edges : 인접행렬 대각원소의 값 1 = 자기 자신 to 자기 자신
+ GCN에서 쓰이는 구조니깐 눈에 잘 익혀 두기로 하자 ~
(conv 연산 시 본인 노드에 대한 값인 1을 같이 더함으로써, 자기 자신의 정보를 잊지 않게끔 하는 representation 방법론)
GCN → GraphSAGE → PinSAGE 로 발전되었다고 함 ... - multigraph : 연결된 노드 사이의 엣지가 여러 개
- connected component : 건너 건너 건너면 다른 노드로 갈 수 있는지
+bridge edge,articulation node: 삭제되면 connected 에서 disconnected 로 바꿀 수 있는 edge / node
bridge 분석할 때 매우 중요하다구 함 ...
+strongly connected components (SCC): any node can visit each other, 그래프에서 부분적으로 나타나는 connected subgraph
Reference
