Abstract

최근 그래프 신경망은 큰 관심을 끌며 다양한 연구 분야에서 두드러진 성과를 거두고 있다. 이러한 알고리즘의 대부분은 관심 있는 객체의 쌍 관계를 가정했다. 그러나 많은 실제 응용 프로그램에서 객체 간의 관계는 쌍으로 공식화하는 것을 넘어 더 높은 차수에 있다. 고차 그래프 구조 데이터에 대한 심층 임베딩을 효율적으로 학습하기 위해 그래프 신경망 계열에 두 개의 종단 간 훈련 가능한 연산자, 즉 하이퍼 그래프 컨볼루션 및 하이퍼 그래프 주의를 도입한다. 하이퍼그래프 컨볼루션(hypergraph convolution)은 하이퍼그래프에서 컨볼루션(convolution)을 수행하는 기본 공식을 정의하지만, 하이퍼그래프 어텐션은 어텐션 모듈을 활용하여 표현 학습 능력을 더욱 향상시킨다. 두 연산자를 사용하면 그래프 신경망이 보다 유연한 모델로 쉽게 확장되어 비쌍 관계가 관찰되는 다양한 애플리케이션에 적용된다. 준지도 노드 분류에 대한 광범위한 실험 결과는 하이퍼그래프 컨볼루션과 하이퍼그래프 주의의 효과를 보여준다.

1. Introduction

지난 10년 동안, CNN(Convolution Neural Networks) [1]은 시각적 인식 [2], 음성 인식 [3], 기계 번역 [4] 등과 같은 다양한 연구 영역에서 광범위한 돌파구를 열었다. 선천적인 특성으로 인해 CNN은 입력 데이터가 규칙적이고 그리드 같은 구조를 가져야 한다는 매우 엄격한 가정을 가지고 있다. 이러한 한계는 불규칙한 구조의 데이터가 널리 존재하는 많은 작업에 대한 CNN의 홍보와 적용을 방해한다. 유비쿼터스 불규칙 데이터 구조를 처리하기 위해 그래프 데이터로 심층 모델을 학습하는 방법론인 그래프 신경망(GNN)[5]에 대한 관심이 높아지고 있다. GNN은 사회과학[6], 지식 그래프[7], 추천 시스템[8], 기하학적 계산[9] 등에 광범위하게 적용된다. 그리고 대부분의 기존 방법은 관심 대상 간의 관계가 쌍별 공식에 있다고 가정한다. 구체적으로, 그래프 모델에서, 각 모서리는 두 개의 꼭짓점만을 연결한다는 것을 의미한다(그림 1(a) 참조). 그러나 많은 실제 응용 프로그램에서 개체 관계는 쌍보다 훨씬 더 복잡합니다. 예를 들어, 추천 시스템에서 한 항목은 여러 사용자에 의해 코멘트될 수 있다. 항목들을 꼭짓점으로 삼고 사용자들의 등급을 그래프의 가장자리로 삼음으로써, 각 가장자리는 두 개 이상의 꼭짓점을 연결할 수 있다. 이 경우, 친화 관계는 더 이상 쌍대 관계가 아니라 삼원 관계, 사원 관계 또는 고차 관계이다. 이것은 하이퍼 엣지를 활용하여 여러 정점을 동시에 연결하는 특수 그래프 모델인 하이퍼그래프[10, 11, 12, 13]의 개념을 가져온다(그림 1(b) 참조). 불행하게도, 그래프 신경망의 대부분의 기존 변형[14, 15]은 하이퍼에지로 인코딩된 고차 구조에 적용되지 않는다. 기계 학습과 패턴 인식 커뮤니티는 간단한 그래프에서 학습 패턴에서 그래프 신경망이 두드러지는 것을 목격했지만, 하이퍼그래프에 대한 딥 러닝 조사는 여전히 초기 단계에 있다. 그 중요성을 고려하여 본 연구에서 하이퍼그래프 컨볼루션과 하이퍼그래프 주의를 그래프 신경망에 대한 강력한 보조 연산자로 제안한다. 우리 일의 장점과 기여는 다음과 같다.

1) 하이퍼그래프 컨볼루션(Hypergraph Convolution)은 하이퍼그래프에서 기본 컨볼루션 연산자를 정의한다. 고차 관계와 로컬 클러스터링 구조를 완전히 활용하여 정점 간의 효율적인 정보 전파를 가능하게 한다. 우리는 그래프 컨볼루션(convolution)이 비쌍 관계에서 쌍 관계로 변질될 때 하이퍼그래프 컨볼루션(hypergraph convolution)의 특별한 경우라는 것을 수학적으로 증명한다.
2) 전파에 사용되는 기본 구조가 미리 정의된 하이퍼그래프 컨볼루션 외에도 하이퍼그래프 어텐션은 하이퍼에지의 동적 연결을 학습하기 위해 주의 메커니즘을 추가로 발휘한다. 그런 다음 그래프의 작업 관련 부분에서 정보 전파 및 수집이 수행되어 더 차별적인 노드 임베딩을 생성한다.
3) 하이퍼 그래프 컨볼루션과 하이퍼 그래프 주의는 모두 종단 간 훈련이 가능하며, 비쌍 관계가 관찰되는 한 대부분의 그래프 신경망 변형에 삽입될 수 있다. 벤치마크 데이터 세트에 대한 광범위한 실험 결과는 준감독 노드 분류를 위해 제안된 방법의 효과를 보여준다.

2. Related Work

그래프는 고전적인 종류의 데이터 구조[16, 17, 18]로, 정점은 객체를 나타내고 두 인접 정점을 연결하는 가장자리는 해당 객체 간의 관계를 설명한다. 그래프 신경망(GNN)은 [5]에 의해 처음 제안된 그래프 구조 데이터의 심층 모델 또는 임베딩을 학습하는 방법론이다. GNN의 핵심 측면 중 하나는 그래프 영역에서 컨볼루션 연산자를 정의하는 것이다. [19] 먼저 그래프 라플라시안 행렬을 사용하여 푸리에 영역에서 컨볼루션(convolution)을 정의하고 잠재적으로 강도 높은 계산을 통해 공간적으로 국한되지 않은 필터를 생성한다. [20] 매끄러운 계수를 가진 매개 변수화를 사용하여 공간적으로 국지화된 스펙트럼 필터를 사용할 수 있다. [21] 효율성 문제에 초점을 맞추고 그래프 푸리에 기반의 명시적 사용을 피하기 위해 그래프 라플라시안의 체비셰프 확장을 사용한다. [22] 1차 이웃만 사용하여 필터링을 더욱 단순화하고 준지도 분류 작업으로 효율성과 효과 모두에서 인상적인 성능을 입증한 GCN(Graph Convolutional Network)을 제안한다. 한편, 일부 공간 알고리듬은 그래프에서 직접 컨볼루션을 수행한다. 예를 들어, [23]은 정도가 다른 노드에 대해 다른 매개 변수를 학습한 다음 이웃 구조에 걸쳐 중간 임베딩을 평균한다. [24] PATCHY-SAN 아키텍처를 제안하는데, 이는 고정 길이의 노드 시퀀스를 수신 필드로 선택하고 시퀀스의 각 노드에 대해 로컬 정규화된 이웃 표현을 생성한다. [25] 확산 기반 표현이 노드 분류의 효과적인 기초가 될 수 있음을 보여준다. [26] 이중 그래프 컨볼루션 네트워크에서 확산 및 인접 기반의 공동 사용을 추가로 탐구한다. [27]은 메시지 전달 함수를 통해 통합 프레임워크를 정의하며, 여기서 각 꼭짓점은 상태를 기반으로 메시지를 보내고 인접 이웃의 메시지를 기반으로 상태를 업데이트합니다. [6] 귀납적 설정의 임베딩을 학습하기 위해 요소별 평균, 장기 단기 메모리 및 풀링 등 세 가지 집계 기능을 사용자 지정하는 GraphSAGE를 제안한다. 일부 다른 작업은 게이트 메커니즘 [28], 스킵 연결 [29], 점프 연결 [30], 주의 메커니즘 [31], 샘플링 전략 [32, 33], 계층 표현 [34], 생성 모델 [35, 36], 적대적 공격 [37] 등에 초점을 맞추고 있다. 공간 제한으로 인해 철저한 검토가 불가능하기 때문에, 우리는 더 대표적인 방법에 대한 설문 조사에 관심 있는 독자들을 추천한다. 예를 들어, [14]와 [15]는 일련의 그래프 신경망 변형에 대한 두 가지 체계적이고 포괄적인 조사를 제시한다. [9] 기하학적 딥 러닝에 대한 리뷰를 제공합니다. [38] 다양한 접근 방식을 일반화하고 확장하며 그래프 신경망이 관계 추론 및 조합 일반화를 어떻게 지원할 수 있는지 보여준다. [39] 특히 그래프에 대한 주의 모델에 초점을 맞추고 세 가지 직관적인 분류법을 소개한다. [40]은 Geodesic CNN [41], Anisotropic CNN [42], GCN [22] 및 확산 CNN [25]을 특별한 경우로 요약하는 MoNet이라는 통합 프레임워크를 제안한다. 위에서 분석했듯이, GNN의 대부분의 기존 변형은 객체 간 쌍 관계를 가정하는 반면, 우리의 작업은 객체 간 관계가 쌍을 넘어선 고차 하이퍼 그래프[43, 44]에서 작동한다. 하이퍼그래프 학습 방법은 하이퍼그래프의 구조(예: 패거리 확장 및 별 확장 [45])와 하이퍼그래프 라플라시안[46, 47, 48]의 정의에 차이가 있다. [21]에 이어 [49]는 그래프 라플라시안의 체비셰프 확장을 이용한 하이퍼그래프 신경망을 제안한다. 하이퍼그래프의 사건 구조를 분석함으로써, 우리의 작업은 두 가지 차별화 가능한 연산자, 즉 하이퍼그래프 컨볼루션과 하이퍼그래프 어텐션(hypergraph convolution)을 직접 정의하며, 이는 보다 차별적인 딥 임베딩을 학습하는 데 직관적이고 유연하다.

3. Proposed Approach

3.1. Hypergraph Revisited

3.2. Hypergraph Convolution

하이퍼그래프에서 컨볼루션 연산자를 정의하는 데 있어 주요 장애물은 두 꼭짓점 사이의 전이 확률을 측정하는 것이며, 각 꼭짓점의 임베딩(또는 특징)은 그래프 신경망에서 전파될 수 있다. 이를 달성하기 위해, 우리는 두 가지 가정을 가지고 있다. 1) 공통 하이퍼에지에 의해 연결된 정점 사이에서 더 많은 전파가 이루어져야 하며, 2) 가중치가 더 큰 하이퍼에지는 그러한 전파에 더 많은 신뢰를 받을 자격이 있다. 하이퍼그래프 컨볼루션의 한 단계는 다음과 같이 정의된다.

3.3. Hypergraph Attention

하이퍼그래프 컨볼루션에는 일종의 선천적인 주의 메커니즘이 있다[39, 31]. 등식 (5)과 등식 (6)에서 찾을 수 있듯이, 꼭짓점 사이의 전이 확률은 비이진적이며, 이는 주어진 꼭짓점에 대해, 관심있고 정밀한 정보 흐름이 다양한 중요도의 크기를 명시적으로 할당한다는 것을 의미한다. 그러나 이러한 주의 메커니즘은 그래프 구조(발생 행렬 H)가 주어진 후에는 학습할 수 없고 훈련할 수 없다. 하이퍼그래프 주의의 목표는 동적 입사 행렬을 학습하여 정점 간의 고유한 관계를 더 잘 드러낼 수 있는 동적 전이 행렬을 학습하는 것이다. 한 가지 자연스러운 해결책은 H에 주의 학습 모듈을 적용하는 것이다. 이러한 상황에서, 주의 모듈은 각 정점을 특정 하이퍼에지에 의해 연결되거나 연결되지 않은 것으로 취급하는 대신 연결 정도를 측정하기 위해 비이진 및 실제 값을 할당하는 확률 모델을 제시한다. 우리는 확률론적 모델이 더 많은 범주 차별적 임베딩을 학습할 수 있고 꼭짓점 사이의 관계가 더 정확하게 설명될 수 있을 것으로 기대한다. 그럼에도 불구하고, 하이퍼그래프 주의는 꼭짓점 집합과 하이퍼엣지 집합이 동일한 균질 도메인에서 온(또는 투영될 수 있는) 경우에만 실현 가능하다. 이 경우에만 꼭짓점과 하이퍼엣지 사이의 유사성이 직접적으로 비교 가능하기 때문이다. 실제로, 그것은 하이퍼그래프 G가 어떻게 구성되느냐에 달려 있다. 예를 들어, [52]는 각 꼭짓점이 k개의 가장 가까운 이웃을 수집하여 하이퍼 에지를 형성하는 이미지 검색에 하이퍼 그래프 학습을 적용하며, 이는 우리의 실험에서 하이퍼 그래프를 구성하는 방법이기도 하다. 꼭짓점 집합과 에지 집합이 유사할 때, 우리는 [31]에서 영감을 얻은 하이퍼그래프 주의 절차를 정의한다.