Graph Cascades: 구조 인지형 그래프 머신러닝을 위한 전염 기반 중간 규모 재배선 (Mesoscopic Rewiring)

우리는 순수하게 국소적인 에지 (local edges) 또는 완전히 전역적인 어텐션 (global attention)을 넘어 중간 규모 (intermediate-scale)의 그래프 구조를 포착하는 Graph Neural Networks (GNNs) 및 Graph Transformers (GTs)를 위한 중간 규모 재배선 (mesoscopic rewiring) 전략인 Graph Cascades를 소개합니다. 전염 기반 확산 프로세스 (contagion-based diffusion processes)를 사용하여, Graph Cascades는 $O(|V|+|E|)$ 시간 내에 반복적인 다중 홉 강화 (multi-hop reinforcement)에 의해 지지되는 노드 쌍이 직접적인 이웃으로 승격되는 보조 그래프를 구축합니다. 우리는 강화 기반 재배선 (reinforcement-based rewiring)이 도움이 되는 시점을 이론적으로 규명합니다: 강화 기반 에지 선택이 직접적인 인접성 (direct adjacency)보다 레이블과 더 잘 일치하게 되는 충분 조건, 2-홉 강화가 완벽하게 동질적 (homophilic)인 SBM 증거, 그리고 그래프 유효 저항 (graph effective resistance)을 통한 중간 규모 연결성 (mesoscopic connectivity)의 공식화가 포함됩니다. 실증적으로, 노드 분류 (node-classification) 벤치마크 전반에 걸쳐 Graph Cascades는 여러 GNN 및 희소 GT (sparse-GT) 백본을 개선하며, 이질적 (heterophilic) 그래프와 중간 또는 높은 차수의 동질적 (homophilic) 그래프에서 가장 신뢰할 수 있는 성능 향상이 관찰되었습니다. 또한 이론적 조건은 중간 규모 재배선이 유익하지 않을 가능성이 높은 영역인 저차수 정규 그래프 (low-degree regular graphs) 및 구조적 병목 현상 (structural bottlenecks)이 있는 그래프를 식별하며, 이러한 예측은 관찰된 실패 사례와 일치합니다. 추가적으로 우리는 재배선된 그래프의 성능과 구조적 특성 사이의 밀접한 상관관계를 관찰했습니다.