메시지 전달 방식의 한계를 넘어: 표현력이 뛰어나고 해석 가능한 그래프 학습을 위한 상징적 대안

Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning

그래프 신경망(GNN)은 신약 개발과 같은 중요한 분야에서 필수적인 기술이 되었지만, 그 '블랙박스'적인 특성은 신뢰성을 확보하는 데 큰 걸림돌이 됩니다. 자체 설명 기능을 갖춘 GNN은 이러한 격차를 줄이기 위해 노력하지만, 종종 기본적인 한계(예: 1-Weisfeiler-Lehman(1-WL) 표현력의 한계, 미세한 수준의 해석력 부족)을 가진 표준 메시지 전달 방식을 기반으로 합니다. 이러한 문제점을 해결하기 위해, 우리는 이러한 제약을 극복하도록 설계된 상징적 프레임워크인 SymGraph를 제안합니다. SymGraph는 연속적인 메시지 전달 방식을 이산적인 구조 해싱과 위상 기반 역할 기반 집계로 대체하여, 이론적으로 1-WL의 한계를 뛰어넘고, 미분 가능한 최적화의 오버헤드 없이 더 뛰어난 표현력을 달성합니다. 광범위한 실험 결과는 SymGraph가 최첨단 성능을 달성하며, 기존의 자체 설명 GNN보다 우수한 성능을 보인다는 것을 보여줍니다. 주목할 만한 점은 SymGraph가 CPU만을 사용하여 훈련 시간을 10배에서 100배까지 단축시킨다는 것입니다. 또한, SymGraph는 기존의 규칙 기반 방법과 비교하여 더 세밀한 의미의 규칙을 생성하여, 과학적 발견과 설명 가능한 AI에 큰 잠재력을 제공합니다.

Graph Neural Networks (GNNs) have become essential in high-stakes domains such as drug discovery, yet their black-box nature remains a significant barrier to trustworthiness. While self-explainable GNNs attempt to bridge this gap, they often rely on standard message-passing backbones that inherit fundamental limitations, including the 1-Weisfeiler-Lehman (1-WL) expressivity barrier and a lack of fine-grained interpretability. To address these challenges, we propose SymGraph, a symbolic framework designed to transcend these constraints. By replacing continuous message passing with discrete structural hashing and topological role-based aggregation, our architecture theoretically surpasses the 1-WL barrier, achieving superior expressiveness without the overhead of differentiable optimization. Extensive empirical evaluations demonstrate that SymGraph achieves state-of-the-art performance, outperforming existing self-explainable GNNs. Notably, SymGraph delivers 10x to 100x speedups in training time using only CPU execution. Furthermore, SymGraph generates rules with superior semantic granularity compared to existing rule-based methods, offering great potential for scientific discovery and explainable AI.