Graph contrastive learning attracts/disperses node representations for
similar/dissimilar node pairs under some notion of similarity. It may be
combined with a low-dimensional embedding of nodes to preserve intrinsic and
structural properties of a graph. In this paper, we extend the celebrated
Laplacian Eigenmaps with contrastive learning, and call them COntrastive
Laplacian EigenmapS (COLES). Starting from a GAN-inspired contrastive
formulation, we show that the Jensen-Shannon divergence underlying many
contrastive graph embedding models fails under disjoint positive and negative
distributions, which may naturally emerge during sampling in the contrastive
setting. In contrast, we demonstrate analytically that COLES essentially
minimizes a surrogate of Wasserstein distance, which is known to cope well
under disjoint distributions. Moreover, we show that the loss of COLES belongs
to the family of so-called block-contrastive losses, previously shown to be
superior compared to pair-wise losses typically used by contrastive methods. We
show on popular benchmarks/backbones that COLES offers favourable
accuracy/scalability compared to DeepWalk, GCN, Graph2Gauss, DGI and GRACE
baselines.

该论文通过引入对比学习方法延伸了 Laplacian Eigenmaps，称之为 COntrastive Laplacian EigenmapS (COLES)，并证明了 COLES 基本上最小化了 Wasserstein 距离的代理，COLES 的损失属于所谓的块对比损失中的一种， 相对于 DeepWalk，GCN，Graph2Gauss，DGI 和 GRACE 基线模型，COLES 在常见基准测试 / 骨干网络上具有更好的准确性 / 可扩展性。

对比拉普拉斯特征映射

Contrastive Laplacian Eigenmaps

We consider the problem of estimating a function defined over $n$ locations
on a $d$-dimensional grid (having all side lengths equal to $n^{1/d}$). When
the function is constrained to have discrete total variation bounded by $C_n$,
we derive the minimax optimal (squared) $\ell_2$ estimation error rate,
parametrized by $n$ and $C_n$. Total variation denoising, also known as the
fused lasso, is seen to be rate optimal. Several simpler estimators exist, such
as Laplacian smoothing and Laplacian eigenmaps. A natural question is: can
these simpler estimators perform just as well? We prove that these estimators,
and more broadly all estimators given by linear transformations of the input
data, are suboptimal over the class of functions with bounded variation. This
extends fundamental findings of Donoho and Johnstone [1998] on 1-dimensional
total variation spaces to higher dimensions. The implication is that the
computationally simpler methods cannot be used for such sophisticated denoising
tasks, without sacrificing statistical accuracy. We also derive minimax rates
for discrete Sobolev spaces over $d$-dimensional grids, which are, in some
sense, smaller than the total variation function spaces. Indeed, these are
small enough spaces that linear estimators can be optimal---and a few
well-known ones are, such as Laplacian smoothing and Laplacian eigenmaps, as we
show. Lastly, we investigate the problem of adaptivity of the total variation
denoiser to these smaller Sobolev function spaces.

在高维离散空间中，假设函数具有有限的总变异性，本文通过导出最小化 (平方) L2 估计误差率，表明了：总变异性去噪（融合拉索）优于拉普拉斯平滑和拉普拉斯特征图等较简单的估计器。

超越 1 维的全变差类：极小极大速率和线性平滑器的限制

Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of  Linear Smoothers

Nonlinear dimensionality reduction (NLDR) algorithms such as Isomap, LLE and
Laplacian Eigenmaps address the problem of representing high-dimensional
nonlinear data in terms of low-dimensional coordinates which represent the
intrinsic structure of the data. This paradigm incorporates the assumption that
real-valued coordinates provide a rich enough class of functions to represent
the data faithfully and efficiently. On the other hand, there are simple
structures which challenge this assumption: the circle, for example, is
one-dimensional but its faithful representation requires two real coordinates.
In this work, we present a strategy for constructing circle-valued functions on
a statistical data set. We develop a machinery of persistent cohomology to
identify candidates for significant circle-structures in the data, and we use
harmonic smoothing and integration to obtain the circle-valued coordinate
functions themselves. We suggest that this enriched class of coordinate
functions permits a precise NLDR analysis of a broader range of realistic data
sets.

本文提出了利用统计数据集构建圆形值函数的方法，并使用持久性上同调的机器来识别数据中显著的圆形结构，通过谐波平滑和积分得到圆值坐标函数，进一步拓宽了坐标函数的类别，以更精确地进行 NLDR 分析。