RayE-Sub: Countering Subgraph Degradation via Perfect Reconstruction

Abstract

Subgraph learning has dominated most practices of improving the expressive power of Message passing neural networks (MPNNs). Existing subgraph discovery policies can be classified into node-based and partition-based, which both achieve impressive performance in most scenarios. Unfortunately, we observe that there exists a subgraph degradation trap in these two mainstream solutions. This means extracted subgraphs fail to achieve better expression. In this work, we start with an intuitive observation and theoretical analysis to explore subgraph degeneration. We then summarize the limitations of these two subgraph strategies from the perspective of reconstruction ability. To this end, we propose perfect reconstruction principle to realize high-quality subgraph extraction. To achieve this, two affiliated questions should be well-addressed. \emph{(i) how to ensure the subgraphs possessing with 'perfect' information? (ii) how to guarantee the 'reconstruction' power of obtained subgraphs?} Firstly, we propose a subgraph partition strategy \emph{Rayleigh-resistance} to extract non-overlap subgraphs by leveraging the graph spectral theory. Secondly, we put forward the Query mechanism to achieve subgraph-level equivariant learning, which guarantees subgraph reconstruction ability. These two parts, \emph{perfect subgraph partition} and \emph{equivariant subgraph learning} are seamlessly unified as a novel \emph{\underline{Ray}leigh-resistance \underline{E}quivariant \underline{Sub}graph learning} architecture (\emph{\textbf{RayE-Sub}}). A series of experiments on both synthetic and real datasets demonstrate that our approach can consistently outperform previous MPNNs architectures.