Abstract

그래프 신경망(GNN)은 그래프 구조 데이터의 강력한 표현으로 인해 다양한 분야에 널리 적용되어 왔다. GNN의 성공에도 불구하고, 대부분의 기존 GNN은 고정 및 동종 그래프에서 노드 표현을 학습하도록 설계되었다. 특히 다양한 유형의 노드와 가장자리로 구성된 잘못 지정된 그래프 또는 이기종 그래프에서 표현을 학습할 때 제한 사항이 문제가 된다. 이러한 한계를 해결하기 위해, 우리는 새로운 그래프에서 효과적인 노드 표현을 종단 간 방식으로 학습하면서 노이즈가 많은 연결을 배제하고 작업에 유용한 연결(예: 메타 경로)을 포함하는 새로운 그래프 구조를 생성할 수 있는 GTN(Graph Transformer Networks)을 제안한다. 또한 그래프 변환의 확장성을 향상시키는 향상된 버전의 GTN, Fast Graph Transformer Networks(Fast GTN)를 제안한다. GTN에 비해 FastGTN은 230배 더 빠르고 100배 더 적은 메모리를 사용하며 GTN과 동일한 그래프 변환을 허용한다. 또한 그래프 변환을 노드의 의미론적 근접성으로 확장하여 메타 경로를 넘어 로컬이 아닌 작업을 가능하게 한다. 동종 그래프와 이기종 그래프 모두에 대한 광범위한 실험은 로컬이 아닌 연산을 가진 GTN과 FastGTN이 노드 분류 작업에 대한 최첨단 성능을 달성한다는 것을 보여준다.

1 INTRODUCTION

그래프 신경망(GNN)은 그래프 구조화된 데이터의 표현을 학습하는 데 점점 더 인기 있는 도구가 되었다. 노드 분류, 링크 예측 , 그래프 분류 , 그래프 생성과 같은 다양한 작업에 널리 사용된다.그래프에서 표현을 학습하는 효과에도 불구하고, 대부분의 GNN은 주어진 그래프가 고정되고 균일하다고 가정한다. 위에서 논의된 그래프 컨볼루션은 고정된 그래프 구조에 의해 결정되기 때문에, 누락/불규칙한 연결이 있는 노이즈가 있는 그래프는 그래프에서 잘못된 이웃과 비효율적인 컨볼루션을 초래한다.또한, 일부 응용 프로그램에서 GNN을 작동하기 위해 그래프를 구성하는 것은 간단하지 않다. 예를 들어 인용 네트워크는 여러 유형의 노드(예: 저자, 논문, 컨퍼런스)와 이들의 관계(예: 저자 논문, 논문-회의)에 의해 정의된 에지를 가지고 있으며, 이를 이기종 그래프라고 한다. 이기종 그래프에서 각 노드 유형과 에지 유형의 중요성은 작업에 따라 달라질 수 있으며, 일부 노드/엣지 유형은 완전히 무용지물이 될 수도 있습니다. 이기종 그래프를 다루는 순진한 접근 방식은 노드/에지 유형을 무시하고 동종 그래프(노드와 에지가 한 유형인 표준 그래프)로 처리하는 것이다. 모델들이 유형 정보를 이용할 수 없기 때문에 이것은 분명히 차선의 것이다. 보다 최근의 해결책은 이기종 에지 유형으로 연결된 경로인 유용한 메타 경로를 수동으로 설계하고 이기종 그래프를 메타 경로에 의해 정의된 동종 그래프로 변환하는 것이다. 그런 다음 기존의 GNN은 변환된 동종 그래프에서 작동할 수 있다.이전 접근 방식보다 개선되었음에도 불구하고, 이것은 2단계 접근 방식이며 각 문제에 대해 수작업으로 만들어진 메타 경로가 필요하다. 다운스트림 분석의 정확도는 이러한 메타 경로의 선택에 의해 크게 영향을 받을 수 있다.이러한 한계를 해결하기 위해, 우리는 원래 그래프를 노이즈가 많은 연결을 배제하고 각 작업에 유용한 멀티홉 연결(예: 메타 경로)을 포함하는 새로운 그래프로 변환하는 방법을 학습하는 GTN(Graph Transformer Networks)을 개발하고, 새로운 그래프에 대한 노드 표현을 종단 간 방식으로 학습한다. 구체적으로, GTN의 핵심 계층인 Graph Transformer 계층은 에지 유형에 대한 인접 행렬의 부드러운 선택을 학습하고 선택된 두 개의 인접 행렬을 곱하여 유용한 메타 경로를 생성한다. 또한, 정체성 매트릭스를 활용함으로써 GTN은 이기종 그래프에서 부드럽게 선택된 에지 유형과 연결된 임의의 길이 합성 관계를 기반으로 새로운 그래프 구조를 생성할 수 있다.또한, 우리는 GTN의 확장성 문제를 해결한다. 그래프를 변환하기 위해 GTN은 거대한 인접 행렬의 행렬 곱셈에 의해 메타 경로의 새로운 인접 행렬을 명시적으로 계산한다. 이를 위해서는 상당한 계산 비용과 대용량 메모리가 필요하므로 큰 그래프에 GTN을 적용하는 것이 불가능하다. 이 문제를 해결하기 위해 두 인접 행렬의 곱셈 없이 그래프를 암묵적으로 변환하는 향상된 버전의 GTN인 Fast Graph Transformer Networks(FastGTN)를 제안한다. GTN에 비해 FastGTN은 230배 더 빠르고 100배 더 적은 메모리를 사용하며 GTN과 동일한 그래프 변환을 허용한다.GTN의 또 다른 문제는 에지 생성이 노드의 의미론적 근접성을 고려하지 않은 입력 그래프의 메타 경로에 의해 연결된 노드로 제한된다는 것이다. 우리는 또한 그래프 변환을 노드의 의미론적 근접성으로 확장하여 메타 경로를 넘어 로컬이 아닌 작업을 가능하게 한다.GTN과 FastGTN의 새로운 그래프 구조는 효과적인 노드 표현으로 이어져 도메인 지식에서 미리 정의된 메타 경로 없이 이기종 그래프에 대한 6가지 벤치마크 분류에서 최첨단 성능을 발휘한다.