그래프 커널

Graph kernel
이 기사는 기계 학습에 관한 것이다.그래프 이론 개념은 그래프 이론 용어집을 참조하십시오.

구조 마이닝에서 그래프 커널은 그래프에서 내부 제품을 계산하는 커널 함수다.[1]그래프 커널은 그래프 쌍의 유사성을 측정하는 함수로 직관적으로 이해할 수 있다.그들은 지원 벡터 기계와 같은 커널화된 학습 알고리즘이 고정 길이의 실제 가치 피쳐 벡터로 변환하기 위해 피쳐 추출 작업을 할 필요 없이 그래프에서 직접 작동할 수 있도록 한다.그들은 생물정보학, 화학정보학, 그리고 소셜 네트워크 분석에서[2] 응용 프로그램을 찾는다.[1]

그래프 커널의 개념은 D가 된 1999년부터 있어왔다.Haussler는[3] 분리된 구조물에 대한 경련성 커널을 도입했다.그래프 커널이라는 용어는 R에 의해 2002년에 더 공식적으로 만들어졌다.I. Kondor와 J. Lafferty는[4] 그래프의 커널로서, 즉 단일 그래프의 노드들 사이의 유사성 함수로서 월드 와이드 웹 하이퍼링크 그래프를 제안 응용 프로그램으로 한다.2003년에 가르트너 외와 가시마 외는 그래프 사이에 커널을 정의했다.[5][6]2010년에 비슈와나단 외는 그들의 통일된 틀을 제공했다.[1]2018년, Ghosh 등은 그래프 커널의 역사와 20년에 걸친 그들의 진화를 묘사했다.

적용들

한계화된 그래프 커널은 작은 유기 분자의 분자화 에너지를 정확하게 예측할 수 있는 것으로 나타났다.[8]

커널 예제

그래프 사이의 커널의 예로는 랜덤 워크 커널이 있는데, 이 [5][6]커널은 개념적으로 두 그래프에서 랜덤 워크를 동시에 수행한 다음, 두 워크로 인해 생성된 경로 수를 계산한다.이는 그래프 쌍의 직접 산물에 대해 무작위 산책을 하는 것과 맞먹으며, 이를 통해 효율적으로 계산할 수 있는 커널을 도출할 수 있다.[1]

또 다른 예는 Weisfeiler-Lehman 알고리즘의 여러 라운드를 계산한 다음 두 그래프의 유사성을 두 그래프의 히스토그램 벡터의 내적 산물로 계산하는 Weisfeiler-Lehman 그래프 커널이다[9].이러한 히스토그램 벡터에서 커널은 모든 반복에서 그래프에서 색상이 발생하는 횟수를 수집한다.두 개의 이형성 그래프의 경우, 두 형상 벡터가 동일하기 때문에 커널은 최대 유사성을 반환한다.Weisfeiler-Lehman 이론상 커널은 Weisfeiler-Lehman 알고리즘이 할당한 가능한 색의 수가 무한하기 때문에 무한한 차원을 가지고 있다는 점에 유의한다.두 그래프에서 발생하는 색상으로 제한함으로써 연산은 여전히 가능하다.

참고 항목

참조

  1. ^ a b c d S.V. N. Vishwanathan; Nicol N. Schraudolph; Risi Kondor; Karsten M. Borgwardt (2010). "Graph kernels" (PDF). Journal of Machine Learning Research. 11: 1201–1242.
  2. ^ L. Ralaivola; S. J. Swamidass; H. Saigo; P. Baldi (2005). "Graph kernels for chemical informatics". Neural Networks. 18 (8): 1093–1110. doi:10.1016/j.neunet.2005.07.009. PMID 16157471.
  3. ^ Haussler, David (1999). Convolution Kernels on Discrete Structures. CiteSeerX 10.1.1.110.638.
  4. ^ Risi Imre Kondor; John Lafferty (2002). Diffusion Kernels on Graphs and Other Discrete Input Spaces (PDF). Proc. Int'l Conf. on Machine Learning (ICML).
  5. ^ a b Thomas Gaertner; Peter Flach; Stefan Wrobel (2003). On graph kernels: Hardness results and efficient alternatives. Proc. the 16th Annual Conference on Computational Learning Theory (COLT) and the 7th Kernel Workshop. doi:10.1007/978-3-540-45167-9_11.
  6. ^ a b Hisashi Kashima; Koji Tsuda; Akihiro Inokuchi (2003). Marginalized kernels between labeled graphs (PDF). Proc. the 20th International Conference on Machine Learning (ICML).
  7. ^ Ghosh, Swarnendu; Das, Nibaran; Gonçalves, Teresa; Quaresma, Paulo; Kundu, Mahantapas (2018). "The journey of graph kernels through two decades". Computer Science Review. 27: 88–111. doi:10.1016/j.cosrev.2017.11.002.
  8. ^ Yu-Hang Tang; Wibe A. de Jong (2019). "Prediction of atomization energy using graph kernel and active learning". The Journal of Chemical Physics. 150 (4): 044107. arXiv:1810.07310. Bibcode:2019JChPh.150d4107T. doi:10.1063/1.5078640. PMID 30709286.
  9. ^ 셰르바시체, 니노 등"Weisfeiler-lehman 그래프 커널들." 머신러닝 연구 저널 12.9(2011년).
Stub icon

이 컴퓨터 과학 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.