Revealing Decurve Flows for Generalized Graph Propagation
Chen Lin Liheng Ma Yiyang Chen Wanli Ouyang Michael M. Bronstein Philip H. S. Torr
This study addresses the limitations of the traditional analysis of
message-passing, central to graph learning, by defining {\em
\textbf{generalized propagation}} with directed and weighted graphs. The
significance manifest in two ways. \textbf{Firstly}, we propose {\em
Generalized Propagation Neural Networks} (\textbf{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. \textbf{Secondly}, we propose
the {\em Continuous Unified Ricci Curvature} (\textbf{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 \textbf{decurve 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.