형태를 바꾸는 군중의 수수께끼

당신이 컴퓨터에게 세상을 단순히 픽셀의 격자나 단어의 목록이 아니라, 연결의 그물망으로 이해하도록 가르치려 한다고 상상해 보십시오. 이것이 바로 **그래프 신경망(Graph Neural Networks, GNNs)**의 영역입니다. GNN은 친구 관계도, 분자 구조, 혹은 교통 경로와 같은 데이터를 다루기 위해 설계된 인공지능의 한 분야입니다. 이러한 지도에서 가장 중요한 것은 개별 항목이 무엇인지가 아니라, 그것이 이웃과 어떻게 연결되어 있는가 하는 점입니다.

하지만 이 컴퓨터들이 따라야 할 까다로운 규칙이 하나 있습니다. 바로 **대칭성(symmetry)**입니다. 만약 친구 무리가 있고 그들의 이름을 서로 바꾼다 해도, 그 무리는 여전히 동일한 무리입니다. 훌륭한 그래프 AI는 누가 A 의자에 앉아 있는지 B 의자에 앉아 있는지에 신경 쓰지 않고, 오직 누가 누구와 대화하고 있는지의 패턴에만 관심을 가져야 합니다. 이를 치환 불변성(permutation invariance)(전체 집단에 대해) 또는 치환 등변성(permutation equivariance)(개별 요소에 대해)이라고 부릅니다. 문제는 표준 AI 모델들이 이 부분에 매우 취약하다는 점입니다. 이들은 데이터가 들어오는 순서에 따라 혼란을 겪으며, 서로 다른 모습의 명단이 실제로는 정확히 같은 사회적 관계를 설명하고 있다는 사실을 인식하지 못하곤 합니다.

이를 해결하기 위해 과학자들은 AI가 노드들을 구별할 수 있도록 "무작위 노이즈"나 "무작위 ID"를 부여하는 방법을 시도했습니다. 이는 마치 군중 속의 모든 사람에게 임시로 고유한 스티커를 붙여주는 것과 같습니다. 하지만 지금까지 우리는 이 기술이 AI를 모든 가능한 패턴을 학습할 수 있을 만큼 똑똑하게 만들 수 있는지, 아니면 복잡한 규칙을 학습하는 데 한계가 있는지 완전히 알지 못했습니다. 이 논문은 그 질문을 깊이 파고들며 다음과 같이 묻습니다. "만약 이 그래프를 읽는 컴퓨터들에게 무작위 스티커를 준다면, 그들은 모든 그래프 구조를 완벽하게 이해할 수 있을 만큼 똑똑해질 수 있을까?"

무작위 스티커의 마법

이 논문의 저자인 루카스 고논(Lukas Gonon), 틸로 마이어-브란디스(Thilo Meyer-Brandis), 니클라스 베버(Niklas Weber)는 **무작위 노드 특징(random node features)**을 부여했을 때 특정 유형의 그래프 AI인 **치환 등변 신경망(Permutation-Equivariant Neural Network, PENN)**이 믿기 힘들 정도로 강력해진다는 것을 증명하고자 했습니다. PENN을 지도를 보고 미스터리를 풀려는 탐정 팀이라고 생각해 보십시오. 보통 두 용의자가 외형도 같고 친구 관계도 같다면, 탐정들은 그들을 구별할 수 없습니다. 하지만 각 용의자에게 무작위의 고유한 스티커(무작위 특징)를 준다면, 탐정들은 마침내 그들을 구별하여 사건을 해결할 수 있습니다.

이 논문의 주요 발견은 "보편적" 보장입니다. 저자들은 이러한 PENN에 무작위 스티커를 입력하면, 고정된 크기의 그래프에 존재하는 모든 측정 가능한 함수를 매우 높은 확률로 근사할 수 있음을 수학적으로 증명했습니다. 쉬운 말로 설명하자면, 만약 당신이 네트워크에 대한 특정 규칙(예: 어떤 분자가 독성이 있는지 또는 어떤 금융 네트워크가 위험한지 예측하는 것)을 학습시키고자 하고, 충분한 무작위 스티커를 제공한다면, 그 규칙을 거의 완벽하게 학습할 수 있는 PENN 구조가 존재한다는 것입니다. 이는 규칙이 지저져 있거나 복잡하더라도, 그리고 노드와 엣지에 붙어 있는 특징의 종류가 많더라도 마찬가지입니다.

"충분히 좋다"는 것은 어느 정도인가?

하지만 이 논문은 단순히 "작동한다"라고 말하는 데 그치지 않고, 작업을 완수하기 위해 AI가 얼마나 커져야 하는지를 알려줍니다. 저자들은 매끄럽고 잘 정의된 함수(수학적으로 "$k$번 연속 미분 가능한", 여기서 $k \ge 2$)를 살펴보았습니다. 그들은 **근사율(approximation rates)**에 대한 공식을 도출했는데, 이는 당신이 더 높은 정확도를 요구함에 따라 AI가 얼마나 빨리 학습할 수 있는지에 대한 일종의 속도 제한입니다.

그들은 네트워크의 깊이(레이어의 수)가 정확도를 높이기 위해 **로그 단위(logarithmically)**로만 성장하면 된다는 것을 발견했습니다. 이는 아주 좋은 소식입니다. 만약 정확도를 두 배로 높이고 싶다면, 뇌의 크기를 두 배로 키울 필요 없이 아주 약간의 깊이만 더 추가하면 됩니다. 그러나 연결의 수(0이 아닌 가중치)는 정확도를 요구함에 따라 **다항식 형태(polynomially)**로 증가합니다. 구체적으로, 복잡도는 원하는 오차 범위인 $\epsilon$의 역수($1/\epsilon$)의 거듭제곱에 따라 결정됩니다. 논문은 이 지수가 당신이 학습하려는 규칙의 "매끄러움"($k$)과 그래프의 크기($N$)에 따라 달라진다고 언급합니다. 본질적으로, 매우 복잡하고 울퉁불퉁한 규칙이나 매우 큰 그래프를 위해서는 훨씬 더 많은 연결이 필요하지만, 매끄러운 규칙의 경우 AI는 효율성을 유지합니다.

안전을 위한 "평균"의 기술

이 논문의 가장 재치 있고 실용적인 통찰 중 하나는 무작위 스티커 사용에 따른 부작용을 다룹니다. 스티커는 무작위이기 때문에, AI를 한 번 실행했을 때의 결과와 다른 스티커를 사용하여 다시 실행했을 때의 결과가 약간 다를 수 있습니다. 이는 대칭성 규칙을 깨뜨립니다. 즉, 스티키가 바뀌었다는 이유만으로 AI가 동일한 친구 집단을 다르게 취급할 수도 있다는 것입니다.

저자들은 영리한 해결책을 제안합니다: 바로 **평균화(averaging)**입니다. 만약 다양한 무작위 스티커를 사용하여 AI를 여러 번 실행하고 그 결과의 평균을 낸다면, 무작위성은 상쇄되어 AI는 다시 완벽하게 대칭적인 상태가 됩니다. 그들은 이 "평균화된" 버전이 여전히 모든 규칙을 학습할 수 있는 초능력을 유지한다는 것을 증로 증명했습니다. 이는 마치 군중에게 호박의 무게를 맞춰보라고 하는 것과 같습니다. 한 사람은 크게 틀릴 수 있지만, 백 명의 추측치를 평균 내면 매우 정확한 답을 얻을 수 있습니다. 논문은 몇 번의 실행을 평균 내는 것만으로도 완벽한 대칭성과 완벽한 학습 능력을 동시에 얻을 수 있음을 보여줍니다.

이것이 미래에 의미하는 바

저자들은 이것이 특정 데이터셋의 시뮬레이션이 아니라 이론적 증명임을 명확히 하고 있습니다. 그들은 이러한 모델이 보편적 근사자(universal approximators)가 될 수 있는 잠재력이 있음을 수학적으로 입증했습니다. 또한, 이러한 목적을 달 위해 복잡하고 맞춤 제작된 구조가 필요하다는 생각을 명시적으로 부정하며, 표준적인 PENN 구조에 무작위 특징을 추가하는 것만으로도 충분하다는 것을 밝혔습니다.

또한, 무작위 특징이 단일 실행 시의 "완벽한 대칭성"은 깨뜨릴 수 있지만, "기댓값에서의 대칭성(평균적인 행동)"은 깨뜨리지 않는다는 점을 분명히 했습니다. 이는 실제로 무작위 특징을 사용하는 것이 견고한 전략임을 시사합니다. 결론적으로, 무와 특징을 가진 PENN은 그래프 학습 작업에서 강력한 기준점(baseline)으로 간려되어야 합니다. 이들은 단순한 이론적 호기기즘이 아닙니다. 화학 분자에서 금융 시스템에 이르기까지 네트워크의 복잡한 패턴을 학습할 수 있는, 강력하고 유연한 그래프 AI를 구축하기 위한 구체적이고 수학적으로 뒷받침된 청사진을 제공합니다.