S&P: Towards Scalable and Powerful Graph Learning with Hierarchical Structural Acquisition

Graph Neural Networks (GNNs) face a fundamental dichotomy between expressiveness and scalability. Recent spectral and transformer-based models approach universal approximation capabilities but rely on computationally intensive global operators that scale poorly to large graphs. Conversely, scalable approaches often compromise structural fidelity through sampling or decoupling, resulting in incomplete structural acquisition. We identify that this trade-off stems from a homogeneous treatment of graph topology, where uniform computational complexity is applied to heterogeneous structures. We propose a paradigm shift towards Hierarchical Structural Acquisition and introduce S&P (Scalable & Powerful), a framework grounded in Fusion Frame Theory that aligns the operator with the intrinsic hierarchy of the data. S&P decomposes the global operator into intra-component and inter-component, and we prove that this design preserves universal spectral filtering capacity for non-degenerate inputs while remaining numerically stable and linear in complexity. Experiments on 14 datasets show that S&P achieves state-of-the-art accuracy, bridging the gap between scalability and expressiveness. Our code is available at https://anonymous.4open.science/r/HierarchicalSP.