Hypergraph Neural Networks

Paper: Yifan Feng; Haoxuan You; Zizhao Zhang; Rongrong Ji; Yue Gao (2019). "Hypergraph Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence, 33(1), 3558–3565. arXiv:1809.09401. PDF · https://doi.org/10.1609/aaai.v33i01.33013558

1. 하이퍼그래프가 더하는 정보

일반 그래프의 간선은 정확히 두 노드를 잇는다. 영화·사용자·장르가 한 사건으로 묶이거나, 같은 객체를 이미지·텍스트·소셜 관계가 함께 설명할 때는 그 묶음을 여러 쌍 간선으로 쪼개야 한다. 이때 ‘이 다섯 항목이 하나의 관계에 함께 속한다’는 정보가 흐려질 수 있다.

하이퍼그래프의 하이퍼엣지는 여러 노드를 한 번에 포함할 수 있다. HGNN은 이런 소속을 결합행렬로 적고, 그래프 신경망의 전파를 하이퍼그래프 위로 옮긴 모델이다. 또한 modality마다 하이퍼엣지 묶음을 만든 뒤 열 방향으로 이어 붙일 수 있다. 그래서 하나의 객체에 시각 관계와 텍스트 관계가 있을 때, 둘을 같은 전파 연산 안에 함께 넣는 틀을 준다.

그림 1. AAAI-19 원논문 PDF p. 3559의 Figure 2를 인용한 공개 자산이다. 왼쪽은 두 노드씩 연결한 그래프와 인접행렬, 오른쪽은 여러 노드를 포함하는 하이퍼엣지와 modality별 결합행렬을 이어 붙이는 모습을 보인다. 이 도식은 임의의 고차 관계가 자동으로 더 좋은 예측을 준다는 실험 결과가 아니다.

2. 한 층의 직관: 모았다가 다시 나눈다

HGNN의 한 층은 노드→하이퍼엣지→노드 순서로 이해하면 쉽다. 먼저 각 노드의 특징을 학습 가능한 변환으로 바꾼다. 다음으로 같은 하이퍼엣지에 속한 노드 특징을 모아 하이퍼엣지 특징을 만든다. 마지막으로 각 노드는 자신이 속한 모든 하이퍼엣지의 특징을 받아 새 특징을 얻는다. 노드가 많은 관계나 많은 관계에 속한 노드가 특정 관계를 과도하게 키우지 않도록 차수 정규화가 들어간다.

그림 2. AAAI-19 원논문 PDF p. 3561의 Figure 4를 인용한 공개 자산이다. 위는 소속 구조, 아래는 node feature transform→edge feature gathering→node feature aggregating의 계산 흐름이다. 하이퍼엣지 특징은 독립적으로 예측하는 숨은 객체라기보다 노드 정보를 모으고 되돌리는 중간 표현이다.

예를 들어 제품 세 개가 ‘같은 고객군이 함께 본 상품’이라는 하나의 하이퍼엣지에 속하고, 그중 하나가 다른 상품군에도 속한다고 하자. HGNN은 첫 하이퍼엣지에서 세 특징을 함께 모으고, 두 번째 하이퍼엣지의 정보도 그 노드에 돌려준다. 단순 그래프의 pairwise message passing도 비슷한 이웃 정보를 보낼 수 있지만, 여기서는 관계 묶음이 소속 단위로 남는다.

3. GCN과 무엇이 다른가

논문은 하이퍼엣지가 노드 둘씩을 잇는 조건에서 GCN을 HGNN의 특수 경우로 설명한다. HGNN의 스펙트럴 합성곱은 완전히 별개의 연산자를 처음부터 만든 것보다, 기존 하이퍼그래프 라플라시안 위에 GCN 계열의 단순화를 적용한 것이다. 실제 기여는 ‘고차 관계를 어떤 구조로 넣을지’와 ‘여러 모달 관계를 어떻게 같이 저장할지’에 더 가깝다.

그 차이는 데이터 준비에서 결정된다. 논문의 시각 실험은 각 객체와 최근접 이웃 10개를 한 하이퍼엣지로 만든다. 즉 하이퍼엣지는 원시의 자연스러운 그룹이 아니라 특징 공간의 kNN으로 구성된다. kNN이 좋은 이웃을 만들 때에는 유용하지만, 이 구성이 정말 pairwise graph보다 더 높은 차수의 의미를 담는지는 별도 통제가 필요하다.

4. 결과: 큰 다중 모달 차이를 어떻게 읽을까

인용 네트워크 분류에서는 HGNN이 Cora 81.6, Pubmed 80.1을 보고했고 GCN은 각각 81.5, 79.0이었다. 차이는 0.1과 1.1 percentage points다. 저자들은 생성한 하이퍼그래프가 원래 그래프와 꽤 비슷해서 이득이 유의하지 않다고 직접 설명한다. HGNN은 100회 실행 평균을 보고했지만 표준편차는 없어 작은 차이의 안정성은 표만으로 판단할 수 없다.

3D 객체 인식에서는 차이가 더 크다. ModelNet40의 최고 HGNN 점수는 96.7이고, NTU에서 다중 모달 구조를 쓴 일부 셀은 GCN보다 8.1–10.4 points 높다. 이는 여러 특징 관계를 함께 보존하는 설계가 저자 데이터에서 강한 후보라는 근거다. 그러나 공정 비교의 단위는 더 좁다. 두 modality를 쓸 때 HGNN은 하이퍼엣지 그룹을 이어 붙이고, GCN baseline은 두 인접행렬을 평균한다. 큰 차이에는 하이퍼그래프와 함께 정보 보존적인 연결 방식의 이득도 섞여 있다.

단일 특징 구조 열에서는 HGNN의 이득이 0.3–4.3 points였다. 이 값이 하이퍼그래프 대 그래프 자체의 효과에 더 가까운 힌트지만, 저자들은 두 방법에 같은 융합 방식을 주는 통제 실험을 하지 않았다. 따라서 ‘NTU에서 최대 10.4 points’는 정확한 표의 결과이되, 그 전부를 하이퍼엣지의 인과적 효과로 부르기는 어렵다.

5. 적용 조건과 한계

관계가 처음부터 그룹 단위로 주어지거나, 여러 관계 유형을 잃지 않고 함께 넣어야 한다면 HGNN의 표현은 자연스럽다. 적용 전에는 하이퍼엣지가 도메인 지식의 진짜 그룹인지 단지 kNN을 다시 쓴 것인지, 큰 하이퍼엣지가 잡음을 섞지 않는지, modality별 관계를 어떤 방식으로 결합할지 확인해야 한다.

논문은 효율적으로 전통 하이퍼그래프 학습을 수행할 수 있다고 설명하지만, 본문 실험에는 실행 시간이나 메모리 측정이 없다. 또 최고 3D 성능 표는 다중 뷰 CNN 특징을 쓰는 HGNN을 원시 point cloud 방법과 함께 놓는다. 입력 표현까지 같은 조건으로 맞춘 비교로 읽기 어렵다. HGNN은 관계의 단위를 pairwise edge에서 group membership으로 바꾸는 모델링 선택을 제시한다. 모든 그래프 문제에서 만능 성능을 보였다는 뜻은 아니다.

더 긴 스펙트럴 유도와 표별 비교는 심층 보기에서 확인할 수 있다.

References

Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1), 3558–3565. https://doi.org/10.1609/aaai.v33i01.33013558