Graph convolutional networks (GCN) are viewed as one of the most popular
representations among the variants of graph neural networks over graph data and
have shown powerful performance in empirical experiments. That $\ell_2$-based
graph smoothing enforces the global smoothness of GCN, while (soft)
$\ell_1$-based sparse graph learning tends to promote signal sparsity to trade
for discontinuity. This paper aims to quantify the trade-off of GCN between
smoothness and sparsity, with the help of a general $\ell_p$-regularized
$(1<p\leq 2)$ stochastic learning proposed within. While stability-based
generalization analyses have been given in prior work for a second derivative
objectiveness function, our $\ell_p$-regularized learning scheme does not
satisfy such a smooth condition. To tackle this issue, we propose a novel SGD
proximal algorithm for GCNs with an inexact operator. For a single-layer GCN,
we establish an explicit theoretical understanding of GCN with the
$\ell_p$-regularized stochastic learning by analyzing the stability of our SGD
proximal algorithm. We conduct multiple empirical experiments to validate our
theoretical findings.

本文探讨了图卷积网络在平滑性和稀疏性之间的权衡，并提出了一种新的随机梯度下降模型来解决这个问题。通过该模型，本文对单层 GCN 在稀疏性学习中的理论性质进行了分析，并验证了理论结论。

GCN 的 $p$ 范正则化随机学习的稳定性和泛化性

Stability and Generalization of $\ell_p$-Regularized Stochastic Learning  for GCN

The diversity and Zipfian frequency distribution of natural language
predicates in corpora leads to sparsity when learning Entailment Graphs. As
symbolic models for natural language inference, an EG cannot recover if missing
a novel premise or hypothesis at test-time. In this paper we approach the
problem of vertex sparsity by introducing a new method of graph smoothing,
using a Language Model to find the nearest approximations of missing
predicates. We improve recall by 25.1 and 16.3 absolute percentage points on
two difficult directional entailment datasets while exceeding average
precision, and show a complementarity with other improvements to edge sparsity.
We further analyze language model embeddings and discuss why they are naturally
suitable for premise-smoothing, but not hypothesis-smoothing. Finally, we
formalize a theory for smoothing a symbolic inference method by constructing
transitive chains to smooth both the premise and hypothesis.

该论文提出了一种新的图形平滑方法，使用语言模型来查找缺失谓词的最近近似值来解决自然语言推理中的顶点稀疏问题，以此提高绝对百分比点的回想，并与其他边缘稀疏改进产生补充作用，同时形式化了平滑符号推理方法的理论。