Going Deeper, Staying Distinct: Graph Learning through Minimal Substitution

Deep graph models need to gather information from distant nodes while preserving the differences between node representations. In conventional message passing, this wider reach is obtained by repeatedly mixing neighboring features, which can gradually erase the distinctions needed for downstream tasks. We introduce Deep Minimal Substitution Graph Learning (DMSGL), which views deep propagation as dynamic succession within a complex network, assuming this succession follows a widely used yet structurally minimalist model of Minimal Substitution. Inspired by Minimal Substitution, we design a Message-substitution mechanism that treats the layer-wise evolution of node features as dynamic succession. Each layer incorporates nonlocal features while retaining the graph structure learned through local propagation. This broadens the information available to a node without tying long-range access entirely to repeated local smoothing. We analyze how representations vary under DMSGL and establish conditions for retaining discriminative information through deep propagation. Extensive experiments demonstrate that DMSGL maintains stable performance. Furthermore, as the model depth increases, the quality of the learned representations improves without succumbing to the over-smoothing problem typically associated with traditional message-passing mechanisms. Together, these results show that DMSGL supports going deeper while keeping node representations distinct.