LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN

당신이 친구들에게 서로에게 귓속말로 단서를 전달하며 미스터리를 해결하는 법을 가르치려 한다고 상상해 보세요. 이것은 본질적으로 그래프 신경망(GNN)이 작동하는 방식과 같습니다. 컴퓨터 과학의 세계에서 "그래프"란 단순히 연결의 지도, 예를 들어 사람들이 점이고 우정이 선인 소셜 네트워크와 같은 것을 의미합니다. GNN은 레이어(층)를 거쳐 정보를 전달하며 전체적인 그림을 이해하도록 학습하는 똑똑한 프로그램입니다.

하지만 이 귓속말 게임에는 두 가지 까다로운 결함이 있습니다. 첫째는 "오버 스무딩(over-smoothing, 과도한 매끄러움)"입니다. 만약 큰 원 안에서 비밀을 너무 여러 번 속삭이면, 결국 모든 사람이 똑같은 말을 듣게 되어 고유한 세부 사항들이 씻겨 내려가고, 결국 아무도 누가 무엇을 말했는지 구별할 수 없게 됩니다. 둘째는 "오버 스쿼싱(over-squashing, 과도한 압착)"입니다. 거대하고 복잡한 이야기를 아주 좁고 작은 복도를 통해 반대편으로 전달하려고 애쓰는 상황을 상상해 보세요. 경로가 너무 붐비거나 길기 때문에 정보가 찌그러지거나, 왜곡되거나, 완전히 손실됩니다. 과학자들은 이를 해결하기 위해 종종 "가상 노드(virtual nodes)"를 추가해 왔습니다. 즉, 멀리 떨어진 그룹의 부분들을 즉각적으로 연결하여 속도를 높여줄 가상의 '슈퍼 친구'를 투입하는 것입니다. 하지만 핵심적인 질문은 항상 이것이었습니다. 어떤 친구에게 초능력을 부여해야 하는가? 대개 연구자들은 그저 추측하거나, 무엇이 가장 잘 작동하는지 확인하기 위해 다양한 규칙들을 시도해 보곤 했습니다.

이 논문은 이 추측 게임을 해결하기 위한 새롭고 영리한 도구인 LEED(Local Embedding Evolution Distance, 국소 임베딩 진화 거리)를 소개합니다. LEED를 아주 민감한 마이크라고 생각하면 쉽습니다. 이 마이크는 메시지가 그룹을 통과해 이동할 때 각 개인의 "목소리"(데이터 표현)가 어떻게 변하는지를 정확히 경청합니다. 군중 전체를 보고 모두가 똑같은 소리를 내는지 확인하는 대신, LEED는 모든 개별 요소에 줌을 당겨 누가 소음 속에 길을 잃고 있는지, 혹은 누가 병목 현상에 갇혀 있는지 살펴봅니다. 저자들은 LEED를 사용하여 어떤 "핵심 노드"를 가상 슈퍼 친구로 만들지 결정함으로써, 그룹의 고유성을 해치지 않으면서도 스쿼싱 문제를 해결할 수 있다는 것을 발견했습니다. 여섯 가지 데이터셋에 대한 실험을 통해, 이 새로운 방법이 기존의 추측 게임보다 컴퓨터가 더 잘, 그리고 더 빠르게 학습하도록 돕는다는 것을 입증했습니다. 이는 대화의 세부 사항에 귀를 기울이는 것이 전체 시스템을 고치는 열쇠라는 것을 증명합니다.

속삭이는 네트워크의 이야기

이 디지털 네트워크의 마법을 더 깊이 파헤쳐 봅시다. 여러분은 그래프 신경망을 거대한 "전화기 게임(Telephone game)"이라고 생각할 수 있습니다. 다만 우스꽝스러운 노래 대신, 플레이어들은 분자, 인용 문헌, 또는 사회적 연결에 관한 복잡한 데이터를 전달합니다. 표준적인 게임에서는 메시지를 너무 많은 사람을 거쳐 전달하면 내용이 엉망이 됩니다. GNN에서도 마찬가지로, 정보를 너무 많은 레이어를 통해 전달하면 각 노드(점)의 고유한 특징들이 서로 섞여 버려 모두가 동일해 보이기 시작합니다. 이것이 오버 스무딩입니다. 마치 여러분의 반 친구들 모두가 똑같은 유니폼을 입고 똑같은 유행어를 말하기 시작하는 것과 같습니다. 그러면 여러분은 가장 친한 친구와 낯선 사람을 구별할 수 없게 될 것입니다.

그 반대의 문제도 있습니다. 바로 오버 스쿼싱입니다. 이는 메시지가 거대한 그래프의 한쪽 끝에서 다른 쪽 끝으로 이동해야 하는데, 그 경로가 좁을 때 발생합니다. 50페이지짜리 편지를 엽서 한 장만 들어갈 수 있는 아주 작은 우편함 구멍을 통해 보내려고 하는 상황을 상상해 보세요. 정보는 꽉 끼고, 찌그러지고, 왜곡됩니다. 그래프 용어로, 이는 "병목 지점(bottlenecks)"에서 발생합니다. 즉, 단 하나의 노드나 몇 개의 엣지(edge)가 네트워크의 먼 곳으로부터 너무 많은 트래픽을 운반해야 하는 곳을 말합니다.

이러한 문제를 해결하기 위해 과학자들은 가상 노드를 추가하는 방법을 시도해 왔습니다. 이것들을 "슈퍼 커넥터"나 "텔레포터"라고 생각하세요. 만약 모든 사람과 연결된 마법 같은 친구를 추가한다면, 메시지는 원래의 길고 구불구불한 경로를 거칠 필요 없이, 그 텔레포터를 거쳐 목적지로 바로 점프할 수 있습니다. 이는 거리를 단축함으로써 스쿼싱 문제를 해결합니다. 하지만 여기에는 함정이 있습니다. 만약 잘못된 사람을 텔레포터로 뽑거나 너무 많은 사람을 추가한다면, 실수로 "오버 스무딩" 문제를 악화시킬 수도 있습니다. 즉, 모두가 너무 빨리 똑같은 소리를 내게 만들 수도 있다는 것입니다.

오랫동안 연구자들은 "누가 친구가 가장 많은가?"(차수, Degree) 또는 "누가 가장 많은 최단 경로에 있는가?"(매개 중심성, Betweenness)와 같은 고전적인 규칙을 사용하여 이 특별한 노드들을 선정해 왔습니다. 그들은 이 규칙들이 무엇이 가장 잘 작동하는지 확인하기 위해 실험을 반복하고 결과를 지켜보았습니다. 그것은 마치 어떤 열쇠가 실제로 맞는지 모르는 채, 거대한 열쇠 꾸러미에 있는 모든 열쇠를 하나씩 다 테스트하며 자물쇠에 맞는 열쇠를 찾는 것과 같았습니다.

LEED: 탐정의 돋보기

이 논문의 저자인 킬리언 크레상트(Killian Cressant)와 페드로 B. 벨로소(Pedro B. Velloso)는 추측하는 것을 멈추기로 했습니다. 그들은 LEED(Local Embedding Evolution Distance)라는 새로운 지표를 구축했습니다. LEED는 그래프 전체를 보고 상황이 흐릿해지는지 보는 대신, 모든 노드를 위한 돋보기 역할을 합니다. LEED는 네트워크의 각 레이어를 통과할 때 노드의 "임베딩"(자기 자신을 나타내는 내부 표현)이 어떻게 진화하는지를 추적합니다.

여기서 영리한 점은 이것입니다. LEED는 단순히 노드와 그 이웃 사이의 거리를 측정하는 것이 아니라, 네트워크가 정보를 처리하는 방식을 모방한 변환을 거친 후 이웃과의 최소 거리를 측정한다는 것입니다. 이는 마치 학생의 답변이 옆자리 친구의 답변과 너무 비슷해지고 있는지 확인하는 것과 같지만, 특히 가장 가까운 일치 항목을 구체적으로 살펴봄으로써 그들이 서로를 너무 많이 따라 하기 시작했는지를 확인하는 것입니다.

이렇게 함으로써 LEED는 두 가지를 동시에 포착할 수 있습니다:

1. 누가 길을 잃고 있는가? (다른 모든 사람과 너무 비슷해지고 있는 노드들, 즉 오버 스무딩을 나타냄)
2. 누가 병목인가? (정보 전달에 어려움을 겪고 있는 노드들, 즉 오버 스쿼싱을 나타냄)

논문은 이 두 문제가 사실 동전의 양면과 같다고 주장합니다. 하나를 해결하면서 다른 하나를 고려하지 않을 수는 없습니다. 스쿼싱을 해결하기 위해 너무 많은 연결을 추가하면, 모든 것을 너무 빨리 매끄럽게(smoothing) 만들어 버릴 수 있습니다. LEED는 "핵심 노드", 즉 그룹의 고유성을 깨뜨리지 않으면서 흐름을 고치기 위해 가상 노드가 되어야 할 구체적인 사람들을 찾아내는 데 도움을 줍니다.

실험: 새로운 전략의 테스트

새로운 탐정 도구가 실제로 작동하는지 확인하기 위해, 저자들은 일련의 실험을 수행했습니다. 그들은 MUTAG, ENZYMES, PROTEINS(화학 구조 및 생물학적 데이터의 집합)와 같은 6가지 서로 다른 데이터셋을 가져와서, 기존의 방식들과 그들의 방법을 비교 테스트했습니다.

그들은 LEED를 사용하여 핵심 노드를 선택하는 그들의 접근 방식을 두 가지 인기 있는 기존 방식과 비교했습니다:

• LVN (Local Virtual Nodes): 그래프에 작은 가상 노드 그룹을 추가하는 방식.
• PANDA: 더 많은 정보를 담을 수 있도록 특정 노드의 크기를 확장하는 방식.

과거에는 이러한 방식들이 (Degree, PageRank, Betweenness와 같은) 다양한 "중심성" 규칙을 시도하며 어떤 것이 가장 잘 작동하는지 테스트해야 했습니다. 그것은 시행착오의 과정이었습니다. 저자들은 이 모든 오래된 규칙들을 단 하나의 LEED로 대체했습니다.

결과는 유망했습니다. 테스트 결과, LVN-LEED 조합이 데이터셋 전반에서 가장 좋은 평균 성능을 달ert했습니다. 예를 들어, MUTAG 데이터셋에서 표준 GCN(기본 모델)은 약 **74.75%**의 정확도를 보였으나, LVN-LEED 모델은 **83.33%**에 도달했습니다. ENZYMES의 경우, 성능 향상이 더욱 눈에 띄었는데, **29.08%**에서 **31.09%**로 뛰어올랐습니다(특정 테스트에서는 그 이상도 기록했습니다).

저자들은 기존 방식들이 때때로 잘 작동하긴 했지만, 많은 튜닝이 필요했다는 점에 주목했습니다. 반면 LEED는 수많은 규칙을 테스트할 필요 없이 일관되게 잘 작동했습니다. 이는 데이터의 국소적 진화에 집중함으로써 네트워크가 더 잘 "호흡"할 수 있도록 돕는 적절한 노드를 찾을 수 있음을 시사합니다.

논문이 말하는 것 (그리고 말하지 않는 것)

이 논문이 실제로 무엇을 증명하는지 이해하는 것이 중요합니다. 저자들은 LEED가 (Dirichlet 에너지와 같은) 기존의 전역 에너지 측정치보다 더 정보가 풍부한 진단 도구임을 보여줍니다. 왜냐하면 LEED는 국소적인 세부 사항을 볼 수 있기 때문입니다. 또한, LEED를 사용하여 노드를 선택하는 것이 무작위 선택이나 표준 중심성 측도를 사용하는 것보다 더 나은 성능을 이끌어낸다는 것을 실험을 통해 입증했습니다.

하지만 논문은 이것이 모든 문제에 적용되는 마법의 탄환이라고 주장하지 않도록 주의를 기울였습니다. 저자들은 자신들의 결과가 특정 데이터셋에 기반한 시뮬레이션과 실험임을 명시했습니다. 그들은 명확한 노드 특징이 없는 일부 데이터셋(예: COLLAB)에서는 개선 효과가 드라마틱하지 않았으며, PANDA 프레임워크를 사용한 한 사례에서는 성능이 약간 떨어졌음을 발견했습니다(비록 유의미한 수준은 아니었지만). 이는 LEED가 강력한 도구이긴 하지만, 보고 있는 데이터의 유형에 따라 조정이 필요할 수 있음을 시사합니다.

또한 저자들은 자신들이 특정 유형의 네트워크 아키텍처(GCN)에 집중했다는 점을 언급하며, 여전히 탐구할 영역이 많음을 밝혔습니다. 그들은 향-후 연구가 LEED가 다른 유형의 네트워크와 어떻게 작동할지, 혹은 그래프를 재구성하는 더 똑똑한 방법을 설계하는 데 어떻게 사용될 수 있을지에 대한 방향을 제시했습니다. 그들은 오버 스무딩 문제를 영원히 해결했다고 주장하는 것이 아니라, 그것을 바라보는 더 날카로운 렌즈와 그것을 고치는 더 나은 방법을 제안한 것입니다.

요점

결국, 이 논문은 더 잘 듣는 것에 관한 이야기입니다. 수년 동안 과학자들은 어떤 친구에게 초능력이 필요한지 추측함으로써 그래프 신경망의 "전화기 게임"을 고치려 노력해 왔습니다. 이 논문의 저자들은 모든 속삭임을 경청하여 메시지가 어디에서 길을 잃는지, 혹은 어디에서 모두가 똑같은 소리를 내기 시작하는지를 정확히 파악하는 새로운 도구인 LEED를 만들었습니다. 이 도구를 사용하여 적절한 "가상 노드"를 선택함으로써, 네트워크가 더 빠르고 정확하게 학습할 수 있음을 보여주었습니다. 이는 때때로 큰 문제를 해결하기 위해 더 큰 망치가 필요한 것이 아니라, 세부 사항을 보는 더 나은 방법이 필요하다는 사실을 상기시켜 줍니다.