Revealing Decurve Flows for Generalized Graph Propagation
<|reference_start|>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 \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.<|reference_end|>
@article{lin2024revealing,
    title={Revealing Decurve Flows for Generalized Graph Propagation},
    author={Chen Lin, Liheng Ma, Yiyang Chen, Wanli Ouyang, Michael M. Bronstein
  and Philip H.S. Torr},
    journal={arXiv preprint arXiv:2402.08480},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08480},
    primaryClass={cs.LG math.DG}
}