최대 엔트로피 가중 독립 집합 풀링을 이용한 그래프 신경망

본 논문에서는 입력 그래프와 풀링된 그래프 간의 상호정보량(mutual information)을 최대화하는 데 기반한 그래프 신경망을 위한 새로운 풀링 레이어를 제안한다. 상호정보량의 최댓값을 직접 계산하는 것은 어려우므로, 본 풀링 방법에 대한 유도적 편향(inductive bias)으로 그래프의 샤논 용량(Shannon capacity)을 활용한다. 구체적으로, 풀링 레이어의 입력 그래프를 노이즈가 있는 통신 채널의 표현으로 해석할 수 있음을 보인다. 이러한 채널에서는 그래프의 독립 집합(independent set)에 속하는 기호들을 전송할 경우 정보 전달이 신뢰성 있고 오류 없이 이루어질 수 있다. 본 연구에서는 상호정보량을 최대화하는 것이 각 정점에 엔트로피 정보를 담은 가중치를 갖는 그래프의 최대 가중치 독립 집합을 찾는 것과 동치임을 보여준다. 이러한 정보이론적 관점에서 그래프 풀링 문제를 그래프 신경망을 통해 구현된 노이즈가 있는 통신 채널을 통해 정보 전송률을 최대화하는 문제로 재정의한다. 제안한 방법은 최대 엔트로피 가중 독립 집합 풀링(Maximum Entropy Weighted Independent Set Pooling, MEWISPool)이라 명명하며, 그래프 분류 작업과 최대 독립 집합 문제라는 조합 최적화 문제에 대해 평가하였다. 실험 결과, 다양한 벤치마크 데이터셋에서 그래프 분류 및 최대 독립 집합 문제 모두에서 최신 기술(SOTA) 수준의 우수한 성능을 달성함을 입증하였다.