2020년이 이제 막 시작되었지만 최신 연구 논문에서 이미 GML(Graph Machine Learning)의 추세를 볼 수 있습니다. 아래는 2020년에 GML과 이 논문에 대한 논의에서 무엇이 중요할 것인지에 대한 나의 견해입니다.
소개
이 글의 목적은 GNN(Graph Neural Networks)과 같은 GML의 기본 개념을 소개하는 것이 아니라 최고의 과학 회의에서 볼 수 있는 최첨단 연구를 폭로하는 것입니다. 처음에는 GML로 작업을 제출하기 위해 가장 권위 있는 컨퍼런스 중 하나인 ICLR 2020에 제출했습니다. 이전 게시물 에서 이미 이 도메인에 대한 몇 가지 빠른 통계를 설명했지만 여기에 짧은 버전이 있습니다.
GML에는 150개의 제출물이 있으며 세 번째 논문이 모두 승인됩니다. 이는 전체 승인된 논문의 약 10%에 해당합니다.
저는 대부분의 GML 논문을 읽었으며 2020년 트렌드 목록은 다음과 같습니다.
1.
GNN에 대한 보다 확실한 이론적 이해;
2.
GNN의 새롭고 멋진 애플리케이션;
3.
지식 그래프의 인기가 높아지고 있습니다.
4.
그래프 임베딩을 위한 새로운 프레임워크.
각각의 트렌드에 대해 알아보겠습니다.
1. GNN에 대한 보다 확실한 이론적 이해
특히 GML 영역이 성숙해지고 이전의 경험적 접근 방식이 새로운 이론적 솔루션으로 대체되고 있음을 보여주는 이러한 추세를 보게 되어 기쁩니다. 그래프 신경망에 대해 여전히 이해해야 할 것이 많지만 GNN의 작동 방식에 대한 몇 가지 중요한 결과가 있습니다.
제가 가장 좋아하는 것부터 시작하겠습니다: Andreas Loukas의 신경망이 학습할 수 없는 그래프: 깊이 대 너비 . 이 논문은 기술적인 단순성, 높은 실제적 영향력, 광범위한 이론적 통찰 사이에서 놀라운 균형을 이루고 있습니다.
이것은 노드 임베딩의 차원(네트워크 폭 w)에 레이어 수(네트워크 깊이)를 곱한 값이 그래프 크기 에 d비례해야 함을 보여줍니다. 인기 있는 그래프 문제(주기 감지, 지름 추정, 정점 커버 등)에 대한 솔루션입니다.ndw = O(n)
결과적으로 GNN의 많은 현재 구현은 레이어 수(많은 구현에서 ~2–5)와 임베딩 차원(~100–1000)이 그래프 크기에 비해 충분히 크지 않기 때문에 이 조건을 달성하지 못합니다. . 반면에 더 큰 네트워크는 현재 설정에서 너무 금지되어 있어 효율적인 GNN 을 설계하는 방법에 대한 질문을 제기합니다. 이는 미래에 해결해야 할 문제입니다. 이 논문은 또한 80년대의 분산 컴퓨팅 모델에서 영감을 얻어 GNN이 본질적으로 동일한 작업을 수행함을 보여줍니다. 내부에 더 많은 결과가 있으므로 살펴 보는 것이 좋습니다.
비슷한 맥락에서 Oono & Suzuki와 Barceló et al.이라는 두 개의 다른 논문은 GNN의 힘을 연구합니다. 첫 번째 항목인 Graph Neural Networks Exponentially Lose Expressive Power for Node Classification 은 다음을 보여줍니다.
가중치에 대한 특정 조건에서 GCN은 레이어 수가 증가할 때 노드 각도와 연결된 구성 요소(라플라시안의 스펙트럼에 의해 결정됨) 외에는 아무것도 학습할 수 없습니다.
이 결과는 Markov 프로세스가 고유한 평형 상태로 수렴한다는 잘 알려진 속성을 일반화한 것입니다. 여기서 수렴 속도는 전이 행렬의 고유값에 의해 결정됩니다.
두 번째 논문 The Logical Expressiveness of Graph Neural Networks 에서, 작성자는 GNN과 GNN이 캡처할 수 있는 노드 분류기 유형 간의 연결을 보여줍니다. 우리는 일부 GNN이 WL 동형사상 테스트만큼 강력하다는 것을 이미 알고 있습니다. 그러나 다른 분류 기능을 GNN에서 캡처할 수 있습니까? 예를 들어 그래프에 고립된 정점이 있는 경우에만 모든 노드에 true를 할당하는 부울 함수를 상상해 보십시오. GNN이 이 논리를 포착할 수 있습니까? GNN은 메시지 전달 메커니즘이고 그래프의 한 부분과 다른 부분(두 개의 연결된 구성 요소) 사이에 링크가 없으면 둘 사이에 메시지가 전달되지 않습니다.
이론에 대한 다른 작업에는 Hou et al.의 GNN에 대한 그래프 정보 사용 측정이 포함됩니다 . Srinivasan & Ribeiro 의 역할 기반 및 거리 기반 노드 임베딩의 동등성 .
2. GNN의 새롭고 멋진 애플리케이션
GNN이 실제 작업에 어떻게 적용될 수 있는지 보는 것도 좋습니다. 올해에는 Javascript의 버그 수정, 게임 플레이, IQ 유사 테스트 응답, TensorFlow 계산 그래프 최적화, 대화 시스템의 분자 생성 및 질문 생성에 대한 응용 프로그램이 있습니다.
In HOPPITY: 프로그램에서 버그를 감지하고 수정하기 위한 학습 그래프 변환 Dinella et al. Javascript 코드에서 동시에 버그를 감지하고 수정하는 방법 제시 . 코드는 추상 구문 트리로 변환된 다음 코드 임베딩을 얻기 위해 GNN에 의해 사전 처리됩니다. 아이디어는 그래프 편집 연산자(노드 추가 또는 삭제, 노드 값 또는 유형 대체)의 여러 라운드를 통해 수정하기 위해 초기 상태의 그래프에 제공됩니다. 그래프의 어떤 노드를 수정해야 하는지 이해하기 위해 그들은 그래프 임베딩과 지금까지의 편집 기록을 가져와 노드를 선택하는 포인터 네트워크를 사용합니다. 그런 다음 그래프 임베딩 및 편집 컨텍스트를 취하는 LSTM 네트워크를 사용하여 수정이 수행됩니다. 저자는 GitHub의 커밋에 대한 접근 방식을 확인했으며 덜 일반적인 다른 기준선에 상당한 향상을 보였습니다. Wei et al.의 작업과 정신이 비슷합니다. LambdaNet: 그래프 신경망 연구를 사용한 확률적 유형 추론Python 또는 TypeScript와 같은 언어에 대한 변수 유형을 유추하는 방법. 작성자는 프로그램의 변수를 노드로 포함하고 논리적(예: 부울 유형) 또는 컨텍스트(예: 유사한 변수 이름) 제약 조건과 같은 이들 사이의 관계를 포함하는 유형 종속성 하이퍼그래프를 제공합니다. 그런 다음 GNN 모델은 먼저 그래프의 변수와 가능한 유형에 대한 임베딩을 생성하도록 훈련된 다음 가장 가능성이 높은 유형을 예측하는 데 사용됩니다. 실험에서 LambdaNet은 표준 변수 유형(예: 부울)과 사용자 정의 유형 모두에서 더 높은 성능을 보였습니다.
Wang 등의 논문. Multiplex Graph Networks를 사용한 Abstract Diagrammatic Reasoning은 GNN을 사용하여 IQ와 유사한 테스트(Raven Progressive Matrix(RPM) 및 Diagram Syllogism(DS))에서 추론하는 방법을 보여줍니다 . RPM 작업에서는 행렬의 각 행에 대해 그래프를 구성하고 피드포워드 모델을 통해 에지 임베딩을 구한 후 그래프 요약을 수행합니다. 마지막 행에 대해 8개의 가능한 답변이 있으므로 8개의 서로 다른 그래프가 생성되고 각각은 ResNet 모델에 의한 IQ 점수 예측을 얻기 위해 처음 두 행과 연결됩니다.
Wang et al. 의 "다중 그래프 네트워크를 사용한 추상 다이어그램 추론"
DeepMind의 논문 Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs는 TensorFlow 계산 그래프의 비용을 최적화하는 RL 알고리즘을 제안합니다 . 그래프는 표준 메시지 전달 GNN을 통해 처리되며 그래프에서 각 노드의 스케줄링 우선 순위에 해당하는 불연속 임베딩을 생성합니다. 이러한 임베딩은 장치 배치 및 각 노드의 일정을 결정하는 유전자 알고리즘 BRKGA에 입력됩니다. 이 모델은 획득한 TensorFlow 그래프의 실제 계산 비용을 최적화하도록 훈련됩니다.
3. 지식 그래프의 대중화
올해 지식 그래프의 추론에 관한 논문이 꽤 많이 있습니다. 기본적으로 지식 그래프는 사실을 표현하는 구조화된 방법입니다. 일반 그래프와 달리 지식 그래프에서는 노드와 에지가 실제로 배우의 이름이나 영화에서 연기하는 행위와 같은 어떤 의미를 가집니다(아래 이미지 참조). Win(Oscar, V)지식 그래프에 대한 일반적인 문제는 논리적 쿼리 ∨ { ∧ Directed(Spielberg, V)∧ ProducedBefore(2000, V)} 로 변환될 수 있는 "스티븐 스필버그가 2000년 이전에 오스카상을 수상한 영화는 무엇입니까?"와 같은 복잡한 쿼리에 응답하는 것입니다.
논문 Query2box에서: Box Embeddings Ren et al을 사용하여 벡터 공간에서 지식 그래프에 대한 추론. 쿼리를 단일 지점이 아닌 직사각형 상자로 잠재 공간에 포함할 것을 제안합니다.이 접근법은 자연스러운 교차 연산, 즉 접속사 ∧를 수행할 수 있게 해줍니다. 그 결과 새로운 직사각형 상자가 생성되기 때문입니다. 그러나 합집합, 즉 분리 ∨를 모델링하는 것은 겹치지 않는 영역이 생길 수 있으므로 그렇게 간단하지 않습니다. 또한 임베딩이 있는 모든 쿼리를 정확하게 모델링하려면 VC 차원으로 측정된 임베딩 간 거리 함수의 복잡성이 그래프의 엔터티 수에 비례해야 합니다. 대신, 결합이 계산 그래프의 끝에서만 발생하는 DNF 형식으로 이접 쿼리를 대체하는 멋진 트릭이 있으며, 이는 각 하위 쿼리에 대한 단순한 거리 계산으로 효과적으로 줄어듭니다.
"Query2box: Box Embeddings를 사용하여 벡터 공간에서 지식 그래프에 대한 추론" Ren et al.
유사한 주제에서 Wang et al. "Differentiable Learning of Numerical Rules in Knowledge Graphs"라는 제목의 논문에서 수치 엔티티 및 규칙으로 작업하는 방법을 제안합니다 . 예를 들어, 인용 지식 그래프의 경우 규칙 ← ∧ ∧ 을 가질 수 있습니다 . 이 규칙은 일반적으로 학생들이 인용 횟수가 더 많은 감독자의 동료에 의해 영향을 받는다는 것을 나타 냅니다 . 이 규칙의 오른쪽에 있는 모든 관계는 행렬로 표현될 수 있으며 누락된 링크를 찾는 프로세스는 엔티티 벡터에 의한 관계의 연속적인 행렬 곱으로 공식화될 수 있습니다. 즉, 규칙 학습이라고 하는 프로세스입니다. 신경 접근 방식은 다음과 같은 범주 규칙에서만 작동할 수 있습니다.influences(Y,X)colleagueOf(Z,Y)supervisorOf(Z,X)hasCitation>(Y,Z)XYZcolleagueOf(Z,Y)행렬이 구성되는 방식 때문입니다. 저자의 공헌은 hasCitation>(Y,Z)실제로 이러한 행렬을 명시적으로 구체화할 필요가 없다는 것을 보여줌으로써 부정 연산자와 같은 수치 규칙을 효율적으로 사용하여 실행 시간을 크게 줄이는 새로운 방법에 대한 것입니다.
일반적으로 기계 학습과 올해 GML에서 더 자주 나타나는 또 다른 주제는 기존 모델의 재평가와 공정한 환경에서 어떻게 수행되는지입니다. 그런 논문으로 당신은 늙은 개에게 새로운 재주를 가르칠 수 있습니다! Ruffinelli et al.의 학습 지식 그래프 임베딩에 대해 . 는 새 모델의 성능이 종종 손실 함수, 정규화 및 샘플링 체계의 형식과 같은 실험 훈련의 "사소한" 세부 사항에 따라 달라진다는 것을 보여줍니다. 대규모 제거 연구에서 저자는 RESCAL 모델과 같은 이전 방법이 하이퍼파라미터를 적절하게 조정하는 것만으로 SOTA 성능을 달성할 수 있음을 관찰했습니다.
이 영역에는 다른 많은 흥미로운 작업이 있습니다. Allenet al. 관계 및 엔터티의 학습된 표현의 잠재 공간에 대해 더 많이 이해하기 위해 단어 임베딩의 최근 통찰력을 기반으로 합니다. Asaiet al. 모델이 주어진 쿼리에 응답하는 Wikipedia 그래프에 대한 추론 경로를 검색할 수 있는 방법을 보여줍니다. 타바코프 & 코스타벨로그래프 임베딩 모델의 확률 보정에 대한 중요한 주제를 다룹니다. 그들은 시그모이드 함수로 로짓을 변환하여 확률을 얻는 인기 있는 임베딩 모델 TransE 및 ComplEx가 제대로 보정되지 않았음을 보여줍니다. 즉, 사실의 존재를 과소 예측하거나 과대 예측합니다. 그들의 방법은 확률을 보정하기 위해 Platt 스케일링 및 등장성 회귀와 같은 알려진 접근 방식에서 사용되는 네거티브로 손상된 트리플을 생성하는 데 의존합니다.
4. 그래프 임베딩을 위한 새로운 프레임워크
그래프 임베딩은 그래프 기계 학습에 대한 오랜 주제였으며 올해 그래프 표현 학습에 접근하는 방법에 대한 새로운 관점이 있습니다.
등. 작업 GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding 에서 감독되지 않은 임베딩 방법에 대한 노드 분류 문제의 실행 시간과 정확도를 개선하는 방법을 제시합니다.. 전반적인 아이디어는 먼저 원본 그래프를 훨씬 더 작은 그래프로 축소하여 노드 임베딩을 빠르게 계산한 다음 원본 그래프의 임베딩을 복구하는 것입니다. 처음에는 속성 유사성을 기반으로 노드의 k-최근접 이웃 간의 링크에 해당하는 추가 에지로 원본 그래프가 보강됩니다. 그런 다음 그래프가 거칠어집니다. 각 노드는 로컬 스펙트럼 방법을 통해 저차원 공간으로 투영되고 클러스터로 집계됩니다. DeepWalk 또는 Deep Graph Infomax와 같은 비지도 그래프 임베딩 방법을 사용하여 작은 그래프에서 노드 임베딩을 얻을 수 있습니다. 마지막 단계에서, 본질적으로 클러스터의 임베딩을 나타내는 획득된 노드 임베딩은 동일한 임베딩을 갖는 다른 노드를 방지하기 위해 스무딩 연산자로 반복적으로 다시 브로드캐스팅됩니다.
Deng et al. 의 "GraphZoom: 정확하고 확장 가능한 그래프 포함을 위한 다단계 스펙트럼 접근 방식"
여러 논문에서 그래프 분류 문제의 이전 결과를 면밀히 조사했습니다. 그래프 분류를 위한 그래프 신경망의 공정한 비교 by Errica et al. 이 문제에 대한 GNN 모델의 공정한 재평가에 기여하여 그래프의 토폴로지를 활용하지 않는(즉, 집계된 노드 기능에서 작동하는) 간단한 기준선이 SOTA GNN과 동등하게 수행됨을 보여줍니다. 이 놀라운 현상은 분명히 이전에 Orlova et al 에 의해 발표되었습니다 . 2015년에는 많은 청중에게 도달하지 못했습니다. 이 작업의 좋은 결과는 인기 있는 데이터 세트에 대한 공정한 SOTA 결과와 PyTorch-Geometric의 편리한 코드 기반으로 향후 논문을 위한 모델 비교를 실행하는 것입니다. 우리 작업에서 그래프 데이터 세트의 동형 편향 이해, 우리는 또한 MUTAG 또는 IMDB와 같이 일반적으로 사용되는 데이터 세트에서 노드 속성을 고려하더라도 많은 그래프에 동형 사본이 있음을 발견했습니다. 더욱이, 이러한 동형 그래프 중에서 많은 것들은 서로 다른 대상 레이블을 가지고 있어 분류기에 대한 레이블 노이즈를 자연스럽게 도입합니다. 이것은 모델의 더 나은 성능을 위해 노드 또는 에지 속성과 같은 네트워크의 모든 사용 가능한 메타 정보 사용의 중요성을 나타냅니다. 또 다른 작업 강력한 그래프 신경망이 필요합니까? 그래프 분류 분석 첸 외. 비선형 이웃 집계 함수를 이웃의 차수와 전파된 그래프 속성을 포함하는 선형 대응 함수로 대체하면 모델의 성능이 감소하지 않는다는 것을 보여줍니다. 세트는 분류에 사소한 것이며 이 작업에 대한 적절한 검증 프레임워크에 대한 질문을 제기합니다.
결론
상위 컨퍼런스의 제출률이 증가함에 따라 2020년 GML 분야에서 많은 흥미로운 결과를 기대할 수 있습니다. 그래프에 대한 딥 러닝의 휴리스틱 응용 프로그램에서 보다 건전한 접근 방식과 그래프 모델의 범위. GNN은 그래프로 공식화할 수 있는 많은 실제 문제에 대한 효과적인 솔루션으로서의 위치를 찾았지만 일반적으로 GML은 그래프 이론과 기계 학습의 교차점에서 우리가 달성할 수 있는 것의 표면을 긁었을 뿐이며 우리는 계속 머물러야 합니다. 다가오는 결과에 맞춰져 있습니다.
