Revealing Decurve Flows for Generalized Graph Propagation

This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining {\em $\mathbf{\text{generalized}}\mathbf{\text{propagation}}$} with directed and weighted graphs. The significance manifest in two ways. $\mathbf{\text{Firstly}}$, we propose {\em Generalized Propagation Neural Networks} ($\mathbf{\text{GPNNs}}$), a framework that unifies most propagation-based graph neural networks. By generating directed-weighted propagation graphs with adjacency function and connectivity function, GPNNs offer enhanced insights into attention mechanisms across various graph models. We delve into the trade-offs within the design space with empirical experiments and emphasize the crucial role of the adjacency function for model expressivity via theoretical analysis. $\mathbf{\text{Secondly}}$, we propose the {\em Continuous Unified Ricci Curvature} ($\mathbf{\text{CURC}}$), an extension of celebrated {\em Ollivier-Ricci Curvature} for directed and weighted graphs. Theoretically, we demonstrate that CURC possesses continuity, scale invariance, and a lower bound connection with the Dirichlet isoperimetric constant validating bottleneck analysis for GPNNs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field. We observe an intriguing ``{\em $\mathbf{\text{decurve}}\mathbf{\text{flow}}$}‘’ - a curvature reduction during training for models with learnable propagation, revealing the evolution of propagation over time and a deeper connection to over-smoothing and bottleneck trade-off.