본문 바로가기

논문리뷰/그래프 이론

(5)
Knowledge Graph (지식 그래프) 요즘 Graph science 분야에서 지식 그래프 (Knowledge Graph)가 굉장한 이슈입니다. ​ 지식 그래프의 정의에 대해 먼저 살펴보자면, 지식 그래프는 데이터의 일종으로 지식이라는 개념을 매우 구조적으로 구성한 것입니다. ​ 예를 들어보도록 하겠습니다. ​ 코끼리라는 지식이 있을 때, 코끼리의 특징을 모두 데이터로 만들 수 있습니다. 코끼리에 대한 지식을 모아보자면, ​ 코끼리는 동물이다. 코끼리는 코가 길다. 코끼리는 초식이다. 코끼리는 굉장히 무거운 동물이다. ​ 이러한 모든 지식들을 그래프 구조하에 만드는 것이 지식 그래프입니다. ​ 한 가지 예를 더 들어보면, 위의 그래프가 지식그래프로 볼 수 있습니다. A와 B가 친구 관계에 있으며, A와 B는 모두 다양한 정보를 가지고 있습니다..
Graph convolution network (GCN) Graph convolution network (GCN) 은 graph stucture를 가진 데이터에서 예측을 하는 딥러닝 모델입니다. 예를 들어서, 가장 많이 쓰이는 예로, 화합물을 예측하는 것입니다. CH4 라는 물질이 있을 때, 원자와 결합관계를 통해 그래프로 표현할 수 있습니다. 이 연결 강도, 연결 각도, 원자 고유의 특징등의 정보를 통해, 해당 그래프가 CH4임을 예측하도록 학습할 수 있습니다. ​ 또한 다른 예시로, 각 노드별로 예측을 할 수 있습니다. 예를 들어서, 자전거 수요 예측에 있어서, 각 노드를 자전거 Station으로, 그리고 Edge를 거리로 가정할 때, 그래프 구조를 생성할 수 있고, 이를 통해, 예측하고 싶은 시간대에 자전거의 수요를 예측할 수 있습니다. ​ 가장 기본적인..
[논문 리뷰] node2vec: Scalable feature learning for networks [원문] Grover, A., & Leskovec, J. (2016, August). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864). ACM. ​ Node2vec 은 Word2vec의 아이디어를 가져왔습니다. Node2vec의 목적함수는 Word2vec 의 목적함수와 굉장히 유사합니다. u가 skip-gram 입장에서 중심 노드를 의미하며, N_s(u) 는 노드 u의 이웃 노드 집합입니다. 즉 skip-gram이 중심단어로부터 주변단어가 나올 로그 우도를 최..
[Graph] Breadth-first search vs Depth-first search 아래와 같은 그래프가 있다고 가정합시다. 1번노드를 Root node로 가정하고, Breadth-first search 를 수행해보겠습니다. 1과 이웃된 노드는 2번 노드와 5번 노드가 있습니다. 우선 첫번째로, 2번 노드를 search 하게 됩니다. 다음으로 나머지 이웃 노드인 5번 노드를 search 합니다. 이제 1 번 노드는 explored 되었다고 할 수 있고, 2, 5 번 노드는 search 된 노드입니다. 다시 2번 노드에 대해서 아직 explored 되지 않은 노드를 search 해야 합니다. 3번 노드가 search 되겠네요. 다음은 5번 노드에 대해서 같은 방식으로 4번 노드가 search 됩니다. 이제 2번 노드와 5번 노드는 explored 노드로 변경됩니다. 3번 노드의 입장에서 ..
[논문 리뷰] DeepWalk: Online Learning of Social Representations 원문 : Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM. ​ 안녕하세요. 이번에 리뷰해볼 paper는 "DeepWalk: Online Learning of Social Representations" 입니다. 이 논문은 Graph를 저차원으로 embedding 하는 아이디어를 최초로 반영한 논문입니다. ​ 위와 같은 4개의 Class (색깔)을 가지..