GraphMinNet: Learning dependencies in graphs with light complexity minimal architecture

Graph Neural Networks (GNNs) have demonstrated remarkable success in various applications. Despite their success, traditional GNNs are inherently limited by their local message-passing paradigm and often struggle to capture long-range dependency (LRD) effectively. This paper introduces GraphMinNet, a novel GNN framework tailored to graph-structured data, inspired by minimal Gated Recurrent Units that are specific to sequence learning. Our framework provides a mathematically provable capacity for modeling LRD with linear computational complexity while maintaining permutation equivariance and stability. By integrating node features with graph structural and positional information, the framework also possesses provably stronger expressiveness than the 1-WL test. We provide rigorous theoretical analyses to establish the framework's properties, including its ability to capture LRD, expressivity, Lipschitz stability, permutation equivariance, and linear complexity. Extensive experiments on ten diverse datasets, including molecular graphs, image graphs, and synthetic networks, demonstrate that GraphMinNet achieves state-of-the-art performance while being computationally efficient. Our results show superior performance on the majority of datasets and competitive results on the others, validating the effectiveness of our approach in capturing both local and global graph structures. Our code is available at this repository.