In this paper, we explore the approximation theory of functions defined on
graphs. Our study builds upon the approximation results derived from the
$K$-functional. We establish a theoretical framework to assess the lower bounds
of approximation for target functions using Graph Convolutional Networks (GCNs)
and examine the over-smoothing phenomenon commonly observed in these networks.
Initially, we introduce the concept of a $K$-functional on graphs, establishing
its equivalence to the modulus of smoothness. We then analyze a typical type of
GCN to demonstrate how the high-frequency energy of the output decays, an
indicator of over-smoothing. This analysis provides theoretical insights into
the nature of over-smoothing within GCNs. Furthermore, we establish a lower
bound for the approximation of target functions by GCNs, which is governed by
the modulus of smoothness of these functions. This finding offers a new
perspective on the approximation capabilities of GCNs. In our numerical
experiments, we analyze several widely applied GCNs and observe the phenomenon
of energy decay. These observations corroborate our theoretical results on
exponential decay order.

本研究基于 $K$-functional 得出的近似结果，探索了定义在图上的函数的近似理论，并建立了使用图卷积网络（GCNs）评估目标函数近似的下界的理论框架，并研究了 GCNs 中通常观察到的过度平滑现象。

平滑与逼近的桥梁：图神经网络过度平滑的理论洞见

Bridging Smoothness and Approximation: Theoretical Insights into  Over-Smoothing in Graph Neural Networks

We propose the Kuramoto Graph Neural Network (KuramotoGNN), a novel class of
continuous-depth graph neural networks (GNNs) that employs the Kuramoto model
to mitigate the over-smoothing phenomenon, in which node features in GNNs
become indistinguishable as the number of layers increases. The Kuramoto model
captures the synchronization behavior of non-linear coupled oscillators. Under
the view of coupled oscillators, we first show the connection between Kuramoto
model and basic GNN and then over-smoothing phenomenon in GNNs can be
interpreted as phase synchronization in Kuramoto model. The KuramotoGNN
replaces this phase synchronization with frequency synchronization to prevent
the node features from converging into each other while allowing the system to
reach a stable synchronized state. We experimentally verify the advantages of
the KuramotoGNN over the baseline GNNs and existing methods in reducing
over-smoothing on various graph deep learning benchmark tasks.

我们提出了 Kuramoto Graph Neural Network (KuramotoGNN)，一种新颖的连续深度图神经网络 (GNN)，它采用 Kuramoto 模型来减轻过度平滑现象，在 GNN 中，随着层数的增加，节点特征变得无法区分。Kuramoto 模型捕捉了非线性耦合振荡器的同步行为。通过耦合振荡器的视角，我们首先展示了 Kuramoto 模型与基本 GNN 之间的联系，然后证明了 GNN 中的过度平滑现象可以解释为 Kuramoto 模型中的相位同步。KuramotoGNN 通过频率同步来替代相位同步，防止节点特征收敛到彼此，同时允许系统达到稳定的同步状态。我们在各种图深度学习基准任务上实验证明了 KuramotoGNN 相对于基准 GNN 和现有方法在减少过度平滑方面的优势。

从耦合振子到图神经网络：通过库拉莫托模型方法减少过度平滑

From Coupled Oscillators to Graph Neural Networks: Reducing  Over-smoothing via a Kuramoto Model-based Approach

Graph neural networks are increasingly becoming the go-to approach in various
fields such as computer vision, computational biology and chemistry, where data
are naturally explained by graphs. However, unlike traditional convolutional
neural networks, deep graph networks do not necessarily yield better
performance than shallow graph networks. This behavior usually stems from the
over-smoothing phenomenon. In this work, we propose a family of architectures
to control this behavior by design. Our networks are motivated by numerical
methods for solving Partial Differential Equations (PDEs) on manifolds, and as
such, their behavior can be explained by similar analysis. Moreover, as we
demonstrate using an extensive set of experiments, our PDE-motivated networks
can generalize and be effective for various types of problems from different
fields. Our architectures obtain better or on par with the current
state-of-the-art results for problems that are typically approached using
different architectures.

本文提出了一类基于偏微分方程数值方法的图神经网络架构来解决传统卷积神经网络可能存在的过度平滑问题，通过实验证明该方法可以处理不同领域的问题并在某些领域获得优于或相当于当前最先进结果。