그래프 동질성 강화: 이질적 그래프 학습에서 이산적 특징의 역할을 재해석

Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning

그래프 신경망(GNN)은 그래프 구조 데이터를 모델링하는 강력한 도구로 부상했습니다. 그러나 기존 GNN은 연결된 노드가 서로 다른 특징이나 레이블을 갖는 이질적 그래프에서 어려움을 겪는 경우가 많습니다. 이러한 문제를 해결하기 위한 다양한 방법이 제안되었지만, 이러한 방법은 주로 구조적 디자인에 초점을 맞추고 있으며 이질성 문제의 근본 원인을 직접적으로 해결하지 못합니다. 실제로, 우리의 실험 결과에서 21가지 최신 GNN이 어려운 이질적 데이터셋에서 가장 기본적인 다층 퍼셉트론(MLP)보다도 성능이 떨어지는 것을 확인했습니다. 이러한 중요한 과제는 구조적 디자인을 넘어 그래프 이질성을 해결하기 위한 혁신적인 접근 방식을 요구합니다. 이러한 격차를 해소하기 위해, 우리는 신중하게 설계된 그래프 변환을 통해 그래프 동질성을 직접적으로 증가시키는 새로운 패러다임을 제안하고 연구합니다. 본 연구에서는 그래프 이질성을 해결하기 위한 간단하면서도 효과적인 프레임워크인 GRAPHITE를 제시합니다. 우리가 알고 있는 한, 본 연구는 그래프를 명시적으로 변환하여 그래프 동질성을 직접적으로 향상시키는 첫 번째 방법입니다. 동질성의 정확한 정의에서 영감을 받아, 제안하는 GRAPHITE는 유사한 특징을 공유하는 노드 간의 동질적인 메시지 전달을 용이하게 하기 위해 특징 노드를 생성합니다. 또한, 이론적 및 실험적으로 제안하는 GRAPHITE가 원래 이질적인 그래프의 동질성을 크게 증가시키지만, 그래프 크기는 약간만 증가한다는 것을 보여줍니다. 어려운 데이터셋에 대한 광범위한 실험 결과, 제안하는 GRAPHITE는 이질적 그래프에서 최첨단 방법보다 훨씬 뛰어난 성능을 보이며, 동질적 그래프에서는 최첨단 방법과 유사한 정확도를 달성합니다.

Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data. However, existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels. While numerous methods have been proposed to address this challenge, they primarily focus on architectural designs without directly targeting the root cause of the heterophily problem. These approaches still perform even worse than the simplest MLPs on challenging heterophilic datasets. For instance, our experiments show that 21 latest GNNs still fall behind the MLP on the Actor dataset. This critical challenge calls for an innovative approach to addressing graph heterophily beyond architectural designs. To bridge this gap, we propose and study a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation. In this work, we present a simple yet effective framework called GRAPHITE to address graph heterophily. To the best of our knowledge, this work is the first method that explicitly transforms the graph to directly improve the graph homophily. Stemmed from the exact definition of homophily, our proposed GRAPHITE creates feature nodes to facilitate homophilic message passing between nodes that share similar features. Furthermore, we both theoretically and empirically show that our proposed GRAPHITE significantly increases the homophily of originally heterophilic graphs, with only a slight increase in the graph size. Extensive experiments on challenging datasets demonstrate that our proposed GRAPHITE significantly outperforms state-of-the-art methods on heterophilic graphs while achieving comparable accuracy with state-of-the-art methods on homophilic graphs.