Chapter1. Machine Learning with Graphs
12기 배유나
Why Networks?
네트워크는 상호작용하는 엔티티의 복잡한 시스템을 설명하기위한 일반적 언어다.
Two Types of Networks/Graphs
Networks(Natural Graphs) -> interaction?
사회는 70억 이상의 개개인들의 집합이다.
전자 장치를 연결하는 통신망
Information Graphs -> relationship?
정보, 지식이 구성되고 연결된다
유사성 네트워크 : 데이터 수집, 유사 데이터(포인트) 연결
하지만, 둘이 모호할 때가 있다고 합니다. (구분)
Many Types of Data are Networks
이 시스템은 어떻게 구성되는가?
이 시스템을 구성하는 요소는 무엇인가?
-> 많은 시스템 뒤에는 구성 요소간의 상호 작용을 정의하는 다이어그램, 네트워크가 있다.
-> 네트워크를 이해하지 않으면 이런 시스템을 모델링하고 예측할 수 없다!
더 나은 예측을 위해 Relational Structure을 어떻게 이용할까?
Graphs : Machine Learning
복잡한 도메인(지식, 텍스트, 이미지 등)은 관계형 그래프로 표현할 수 있는 구조를 가지고 있다.
-> 관계를 명시적으로 모델링해 더 나은 성능을 달
Why should I care about networks ?
복잡한 데이터를 설명하기 위한 범용 언어
과학, 자연, 기술의 네트워크는 생각보다 비슷하다.
분야간 단어 공유
컴퓨터 과학, 사회 과학, 물리학, 경제학, 통계학, 생물학 -> 분야간 공유 가능
데이터 가용성, 계산 이슈
웹/ 모바일, 바이오, 건강, 의료
Impact
소셜 네트워크, 약물 설계, AI 추론
-> 디지털 회사에 새로운 파장 일으켰다.
구글 : web이 그래프라고 처음 인지하였다고 함. 그전 web 여러셋의 document로 구성
Networks and Applications
Node classification
주어진 노드의 type, color 예측
Link classification
두 노드가 연결되어 있는지 예측
Community classification
밀도있게 연결된 노드 클러스터 구분
Network similarity
두 노드, 네트워크의 유사도 측정
application 예
social circle Detection
네트워크가 주어졌을때 소셜 서클 발견 가능하다.
Embedding Nodes
노드를 d차원 임베딩에 매핑해서 유사한 네트워크 환경을 가진 노드가 서로 가까이에 되도록 설정
-> 이걸 활용해서 추천이 가능하다.
Structure of Grphs
structure of Networks
네트워크는 object 쌍이 링크로 연결된 object 모음
-> 네트워크 구조는 무엇일까?
Components of a Network
Networks or Graphs?
Network 는 실제 시스템을 의미
web, Social network
(Network, node, link)
Graph는 network의 수학적 표현
web graph, social graph
(Graph, vertex, edge)
필요할 땐 구별하겠지만, 대부분 두 용어를 번갈아 사용
Networks : Common Language
Choosing Proper Representations
협력하는 개인을 연결하면 professional network
sexual 관계를 연결하면 sexual network
인용하는 과학 논문을 연결하면 citation network
How do you define a network
Graph 작성
노드란? 엣지란?
주어진 도메인, 문제에서 네트워크를 성공적으로 사용하기 위해 적절한 네트워크 representation 선택은 중요한 결정이다.
어떤 경우에 독특하고 명확한 표현이 있다.
다른 경우에 표현이 unique하지 않음
링크를 할당하는 방법에 따라 공부할 내용이 다양
Choice of Network Representation
Node degree K_i : 노드 i에 인접한 edge 수
undirected Avg.degree는 노드수가 양방이다 보니 2배 -> 2E/N
in-degree : 해당 노드로 향하는
out-degree : 해당 노드가 향하는
Complete Graph
서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프
Bipartite Graph
모든 링크가 U의 노드를 V의 노드에 연결하도록 노드를 U,V로 나눌 수 있는 그래프
U와 V는 독립
Folded Networks -> 다 : 1
Representing Graphs : 인접행렬
node i와 j로 가는 링크가 있다면 1, 아니면 0
인접행렬 : 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 행렬
undirected graph는 대칭행렬이지만, directed graph은 대칭행렬이 아님
Representing Graphs : Edge List
엣지 리스트 : 연결된 엣지들의 집합
Representing Graphs : Adjacency list 인접리스트
그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현
인접 행렬에 비해 edge가 희소한 그래프에서 효과적
Networks are Sparse Graphs
현실 네트워크는 sparse -> 인접행렬은 0으로 채워짐
Edge Attributes
More Types of Graphs
Connectivity of Undirected Graphs
두 정점은 경로로 연결 가능
연결이 끊어진 그래프는 둘 이상의 연결된 구성 요소로 구성됨
여러 components로 된 네트워크 인접행렬은 block-diagonal형태로 작성할 수 있어서 0이 아닌 요소는 사각형으로 제한되고 아니면 모두 0이다.
Connectivity of Directed Graphs
strongly connected directed graph
각 노드에서 다른 모든 노드로 경로가 있고, 반대로도 모든 노드로 경로가 있다.
weakly connected directed graph
Strongly connected components (SCCs)
SCC를 식별할 수 있지만 모든 노드가 SCC는 아니다.
Last updated
