1. Intro

加深GNN的必要性： 更好地利用远距离信息，尤其是异配图；

加深GNN的困难之处：

  1. graph bottleneck：
  2. over-squashing：
  3. over-smoothing：

其中的重点是过平滑问题；本文关注过平滑， 即节点的特征称指数级速度收敛，图上的信号变得过于平滑，从而导致失去了特性，尤其会对异配图的表征学习造成严重影响。

“少量的平滑性是对回归和分类任务是有必要的。”

以前的工作主要通过节点特征的相似性来反应平滑性，没有明确考虑over-smoothing的随着深度的收敛速度。也没有一个更加广泛、更加统一的评价平滑性的指标。

2. 平滑性的指标

1.1 传统的指标：

图上的狄利克雷能量：$\mathcal{E}(\mathbf{X}^n)=\frac{1}{\|V\|}\sum_{i\in V}\sum_{j\in N(i)}\|X_i^n-X_j^n\|^2_2$

mean average distance(MAD): $\mathcal{E}(\mathbf{X}^n)=\frac{1}{\|V\|}\sum_{i\in V}\sum_{j\in N(i)}1-\frac{\mathbf{X_i^n}^T\mathbf{X_j^n}}{\|X_i^n\|\|X_j^n\|}$

总差变（Total variance）：$\mathcal{E}(\mathbf{X^n})=\sum_{i}\sum_{j \in N(i)}|X_i^n-X_j^n|$

1.2 更统一的定义和指标

Target: establish a unified, rigorous, and tractable definition of over-smoothing:

首先定义节点相似度（定义0相似度+满足三角不等式）；接着在此基础上定量地定义过平滑现象为：随着深度地增加，相似度收敛于负指数函数。

首先定义节点相似度（定义0相似度+满足三角不等式）；接着在此基础上定量地定义过平滑现象为：随着深度地增加，相似度收敛于负指数函数。