Large graphs commonly appear in social networks, knowledge graphs,
recommender systems, life sciences, and decision making problems. Summarizing
large graphs by their high level properties is helpful in solving problems in
these settings. In spectral clustering, we aim to identify clusters of nodes
where most edges fall within clusters and only few edges fall between clusters.
This task is important for many downstream applications and exploratory
analysis. A core step of spectral clustering is performing an
eigendecomposition of the corresponding graph Laplacian matrix (or
equivalently, a singular value decomposition, SVD, of the incidence matrix).
The convergence of iterative singular value decomposition approaches depends on
the eigengaps of the spectrum of the given matrix, i.e., the difference between
consecutive eigenvalues. For a graph Laplacian corresponding to a
well-clustered graph, the eigenvalues will be non-negative but very small (much
less than $1$) slowing convergence. This paper introduces a parallelizable
approach to dilating the spectrum in order to accelerate SVD solvers and in
turn, spectral clustering. This is accomplished via polynomial approximations
to matrix operations that favorably transform the spectrum of a matrix without
changing its eigenvectors. Experiments demonstrate that this approach
significantly accelerates convergence, and we explain how this transformation
can be parallelized and stochastically approximated to scale with available
compute.

该研究探讨了一种可并行化的方法，通过对大型图的频谱进行扩展，以加速奇异值分解求解器和谱聚类，并利用多项式逼近来实现此目的。

用于大规模图聚类的随机并行可分解特征值间隔扩张

Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering

Permutation-invariant, -equivariant, and -covariant functions and
anti-symmetric functions are important in quantum physics, computer vision, and
other disciplines. Applications often require most or all of the following
properties: (a) a large class of such functions can be approximated, e.g. all
continuous function, (b) only the (anti)symmetric functions can be represented,
(c) a fast algorithm for computing the approximation, (d) the representation
itself is continuous or differentiable, (e) the architecture is suitable for
learning the function from data. (Anti)symmetric neural networks have recently
been developed and applied with great success. A few theoretical approximation
results have been proven, but many questions are still open, especially for
particles in more than one dimension and the anti-symmetric case, which this
work focusses on. More concretely, we derive natural polynomial approximations
in the symmetric case, and approximations based on a single generalized Slater
determinant in the anti-symmetric case. Unlike some previous super-exponential
and discontinuous approximations, these seem a more promising basis for future
tighter bounds. We provide a complete and explicit universality proof of the
Equivariant MultiLayer Perceptron, which implies universality of symmetric MLPs
and the FermiNet.

探讨了排列不变、等变、协变函数和反对称函数在量子物理、计算机视觉等领域的重要性， 提出了基于单个广义 Slater 行列式的反对称多项式逼近方法，并给出了等变多层感知器的明确普适性证明。

关于表示（反）对称函数

On Representing (Anti)Symmetric Functions

We study several questions in the reliable agnostic learning framework of
Kalai et al. (2009), which captures learning tasks in which one type of error
is costlier than others. A positive reliable classifier is one that makes no
false positive errors. The goal in the positive reliable agnostic framework is
to output a hypothesis with the following properties: (i) its false positive
error rate is at most $\epsilon$, (ii) its false negative error rate is at most
$\epsilon$ more than that of the best positive reliable classifier from the
class. A closely related notion is fully reliable agnostic learning, which
considers partial classifiers that are allowed to predict "unknown" on some
inputs. The best fully reliable partial classifier is one that makes no errors
and minimizes the probability of predicting "unknown", and the goal in fully
reliable learning is to output a hypothesis that is almost as good as the best
fully reliable partial classifier from a class.
For distribution-independent learning, the best known algorithms for PAC
learning typically utilize polynomial threshold representations, while the
state of the art agnostic learning algorithms use point-wise polynomial
approximations. We show that one-sided polynomial approximations, an
intermediate notion between polynomial threshold representations and point-wise
polynomial approximations, suffice for learning in the reliable agnostic
settings. We then show that majorities can be fully reliably learned and
disjunctions of majorities can be positive reliably learned, through
constructions of appropriate one-sided polynomial approximations. Our fully
reliable algorithm for majorities provides the first evidence that fully
reliable learning may be strictly easier than agnostic learning. Our algorithms
also satisfy strong attribute-efficiency properties, and provide smooth
tradeoffs between sample complexity and running time.

研究可靠的不可知学习框架中的问题，使用单边多项式逼近可学习可靠分类器和构建适当的单边多项式逼近来学习大多数时完全可靠，这些算法还满足强属性效率属性并提供样本复杂度和运行时间之间的平滑折衷。