1강은 들으면서 너무 재밌어서 놀랐습니다. Intro 라 강의의 흥미를 돋구기 위해 유독 재미있었던 것 같습니다. 1강 스터티 진행은 갓갓 윤종님께서 하셨습니다.
목차
Networks/Graphs
- Type
- Ways to Analyze Networks
- Application
Structure of Graphs
- Component of a Network
- Representing Graphs
- More Types of Graphs
Networks/Graphs
Networkssms 개체(entity) 간의 상호작용이 복잡한 시스템을 나타낼 수 있는 general language 입니다.
Type
네트워크를 두 가지로 나눈다면 소셜네트워크가 속하는, Natural Graph로 알려진 Networks 와 정보가 연결되어 있는 것을 나타내는 Information Graphs로 나뉩니다.
물론 이 두 가지는 때때로 섞여서 사용됩니다.
굉장히 다양한 도메인에서 사용될 수 있습니다.
- Event Graphs
- Knowledge Graphs
- Disease pathways
- Molecules
- Scene Graphs
- Cell-cell similarity networks
모델링을 하기 위해서 network를 이해해보겠습니다.
핵심은 더 예측을 잘 하기 위해서 실제 연결 구조를 이해해서 이점을 취하는 것입니다.
(모든 복잡한 domain들이 relational graph로 연결할 수 있는 연결 구조를 가지기 때문입니다.)
Ways to Analyze Networks
Networks 분석은 크게 4가지로 나뉘어집니다.
- Node classification -> 주어진 노드 종류 분류
- Link Prediction -> 노드간의 연결 여부 예측
- Community detection -> 군집 감지
- Network Similarity -> (네트워크나 노드간의) 유사도 축정
Application
Network 분석이 사용되는 예시로는 Social Circle Detection, Infrastructure, Knowledge, Link Prediction(reccomendation system), Embedding Nodes, Online Media, Polarization on Twitter, Misinformation, Predicting Virality, Product Adoption, Biomedicine, Side Effect 등이 있었습니다.
참 많았지만, 그 중에서 제가 특히 재밌었던 적용 두 가지를 예시로 언급하겠습니다.
예시들이 재밌어서 1강이 특히 재밌었던 것 같습니다.
Recommendation
추천시스템에서 콘텐츠 추천에 link prediction 이 사용된다고 합니다.
이렇게 쿼리가 주어졌을 때 Graph-based algorithm 이 비슷한 이미지를 찾아내는 예시도 보여줍니다.
Side Effect
부작용 탐색에 네트워크가 사용된다고 합니다. 많은 약을 한꺼번에 섭취했을 때 나타나는 부작용에 대한 예측은 실제로 많은 실험을 해보는 것이 불가능하기 때문에 서로다른 graph를 만들고 link를 예측하는 방법으로 side effect를 탐색합니다.
Structure of Graphs
Component of a Network
그래프의 요소로는 객체를 나타내는 node, vertices가 있습니다.
연결은 links, edges 로 표현하고 전체 시스템은 network, graph 입니다.
그래프를 만드는 것은 node / edge를 정하는 것부터 시작합니다.
보통 Network 는 진짜 System 을 의미하고, Graph는 네트워크의 수학적 표현입니다. 하지만 혼용해서 사용합니다.
Choice of Network Representation
Direction
방향성에 따라 두 가지 종류가 있습니다.
Node Degrees
Degree(차수) : node에 연결된 edge의 갯수입니다.
-
Undirected graph의 평균차수
모든 차수 값을 더해서 node의 갯수로 나눠서 쉽게 구할 수 있습니다. -
Directed graph의 차수
in-degree 와 out-degree를 따로 구해서 더해줘야합니다.
edge 연결 여부에 따라 Source 노드와 Sink 노드의 개념이 있습니다.
Complete Graph
undirected graph 에서 n 개의 node 들이 maximum 의 edge 로 연결 되어 있을 때의 graph 입니다.
Bipartite Graph
Bipartite Graph(이분 그래프) : 서로 다른 종류의 독립된 노드들로 구성된 그래프
- 두 가지 노드 타입 U,V 로 나눌 수 있음
- U에 속하는 노드는 V에 속한 노드에게만 연결되고 V끼리는 독립임
- V에 속하는 노드는 U에 속한 노드에게만 연결되고 U끼리는 독립임
특히 추천시스템에서 많이 사용됩니다. (유저 - 구매기록 - 아이템)
Folede/Projected Biopartite Graph 이미지를 보면 이해가 쉽습니다.
Representing Graphs
Adjacency Matrix
그래프는 Adjacency Matrix(인접행렬)로 표현될 수 있습니다.
- Undirected의 경우 대칭으로 나타나며 Undirected는 단방향일 수 있기 때문에 대칭이 아닐 수도 있음
- 노드가 많아질 수록 즉, 행렬의 차원이 커질 수록 Sparse해진다는 단점이 있음
Edge list
Edge를 연결된 노드 쌍으로 표현한 형태입니다. 실제로 이 형태의 자료구조로 구현되는 라이브러리가 있습니다.
Adjacency list
- 출발방향의 노드를 Key값으로, 도착 노드를 Value값으로 가지는 Dictioanry형태
- 네트워크가 sparse하거나 거대할 때 효율이 좋음
- 주어진 node 의 인접(이웃)에 빨리 닿게 해줌
자료구조에서 그래프를 나타낼 때 많이 써서 그런지 가장 익숙하다고 느꼈습니다.
Edge Attributes
Sparse 함을 고려하기 위해서는 다음과 같은 옵션들이 많이 사용됩니다.
- Weight : edge에 weight 주기 (ex. 가장 편한 길에 높은 점수를 준다.)
- Ranking : 순위를 매긴다. (절친, 지인, ...)
- Type : 친구, 친척, 직장동료
- Sign : 친구 vs 적, 진실 vs 거짓
More Types of Graphs
Self-edges(self-loops)
Self-edges 는 특히 GCN에서 1로 채우는 이유와 연관되어 있습니다. (GCN에 쓰는 타입)
[1] 이라는 노드를 Convolution 연산을 통해서 [2],[3] 노드로 표현한다면 (New representation) 자기 자신에 대한 정보는 잃게 됩니다.
따라서 자기 정보의 보전을 위해서 자신의 데이터도 더해줍니다.graph sage, PinSage, ... 에서 사용됩니다.
Connectivity of Undirected Graphs
- Connected graph(undirected): 어떤 노드에서 출발하든지 다른 모든 노드로 도착할 수 있음
- Disconnected graph: 최소 2개 이상의 connected graph로 구성됨
- Bridge edge: 삭제되면 connected에서 disconnected로 바꿀 수 있는 edge
- Articulation node: 삭제되면 connected에서 disconnected로 바꿀 수 있는 node
Bridge edge와 Articulation node가 중요한 정보를 주는 경우가 있습니다.
- Disconnected 의 경우 인접행렬은 block-diagonal 형태가 됩니다.
Connectivity of Directed Graphs
Directed Graph의 연결성에 대해서는 두 가지 graph 가 있습니다.
- Strongly connected directed graph: 어떤 노드에서 출발하든지 edge방향을 지키면서 다른 모든 노드로 도착할 수 있음
- Wealky connected directed graph: 어떤 노드에서 출발하든지 edge방향을 무시한다면 다른 모든 노드로 도착할 수 있음
이 그래프는 E -> G 로 방향을 무시한다면 갈 수 있고, 지킨다면 갈 수 없는 Wealky connected directed graph 입니다.
Strongly connected components(SCCs)
SCCs는 그래프에서 부분적으로 나타나는 connected subgraph 입니다.
- In-component : SCC 포함
- Out-component : SCC 미포함
Reference
Stanford CS224W 2019
스터디 1강 리뷰 자료 https://velog.io/@tobigs-gnn1213/1.-Introduction-Structure-of-graph
'🗂 REVIEW > Graph Study' 카테고리의 다른 글
| [CS224W] 5. Spectral Clustering (0) | 2021.03.08 |
|---|---|
| [CS224W] 4. Community Structure in Networks (0) | 2021.03.07 |
| [CS224W] 3. Motifs and Structural Roles in Networks (0) | 2021.02.21 |
| [CS224W] 2. Properties of Networks and Random Graph Models (0) | 2021.02.12 |
| ```시작하며``` (0) | 2021.02.12 |
