초록
우리는 Transformer를 임의 차수의 순서 불변 데이터(집합, 그래프, 하이퍼그래프)에 일반화하는 방법을 제시합니다. 먼저, Transformer가 DeepSets 또는 1차원(집합 입력) 순서 불변 다층 퍼셉트론(MLP)을 일반화한다는 점을 관찰합니다. 그런 다음 최근에 특징화된 고차원 불변 MLP를 바탕으로, 자기 주의(self-attention) 개념을 고차원으로 확장하고 $k$차원 데이터($k=2$인 경우 그래프, $k>2$인 경우 하이퍼그래프)를 위한 고차원 Transformer를 제안합니다. 그러나, 고차원 Transformer는 입력 노드 수 $n$에 대해 금지적인 복잡도 $\mathcal{O}(n^{2k})$를 가진다는 문제가 있습니다. 이 문제를 해결하기 위해, 우리는 입력 하이퍼엣지 수에 대해 이차 복잡도를 가지는 희소(sparse) 고차원 Transformer를 제시하며, 이를 통해 커널 주의(kernel attention) 접근법을 채택하여 복잡도를 선형으로 줄입니다. 특히, 커널 주의를 사용한 희소 2차원 Transformer는 메시지 전달 연산보다 이론적으로 더 표현력이 뛰어나면서도 비슷한 복잡도를 가지는 것으로 나타났습니다. 우리의 모델은 대규모 그래프 회귀와 집합-그래프 예측 과제에서 불변 MLP와 메시지 전달 그래프 신경망보다 상당히 우수한 성능 개선을 보여주었습니다. 우리의 구현은 https://github.com/jw9730/hot에서 확인할 수 있습니다.