Autoregressive~(AR) generation almost dominates sequence generation for its
efficacy. Recently, non-autoregressive~(NAR) generation gains increasing
popularity for its efficiency and growing efficacy. However, its efficiency is
still bottlenecked by quadratic complexity in sequence lengths, which is
prohibitive for scaling to long sequence generation and few works have been
done to mitigate this problem. In this paper, we propose a novel MLP variant,
\textbf{A}ttentive \textbf{M}ulti-\textbf{L}ayer \textbf{P}erceptron~(AMLP), to
produce a generation model with linear time and space complexity. Different
from classic MLP with static and learnable projection matrices, AMLP leverages
adaptive projections computed from inputs in an attentive mode. The
sample-aware adaptive projections enable communications among tokens in a
sequence, and model the measurement between the query and key space.
Furthermore, we marry AMLP with popular NAR models, deriving a highly efficient
NAR-AMLP architecture with linear time and space complexity. Empirical results
show that such marriage architecture surpasses competitive efficient NAR
models, by a significant margin on text-to-speech synthesis and machine
translation. We also test AMLP's self- and cross-attention ability separately
with extensive ablation experiments, and find them comparable or even superior
to the other efficient models. The efficiency analysis further shows that AMLP
extremely reduces the memory cost against vanilla non-autoregressive models for
long sequences.

提出了一种具有线性时间和空间复杂度的新型多层感知机（AMLP）来解决非自回归生成模型中的二次复杂度问题，并通过在文本转语音合成和机器翻译任务中的实验证明，AMLP 与 NAR 模型的结合在效率上明显优于竞争模型。

注意力多层感知器用于非自回归生成

Attentive Multi-Layer Perceptron for Non-autoregressive Generation

Conductance-based graph clustering has been recognized as a fundamental
operator in numerous graph analysis applications. Despite the significant
success of conductance-based graph clustering, existing algorithms are either
hard to obtain satisfactory clustering qualities, or have high time and space
complexity to achieve provable clustering qualities. To overcome these
limitations, we devise a powerful \textit{peeling}-based graph clustering
framework \textit{PCon}. We show that many existing solutions can be reduced to
our framework. Namely, they first define a score function for each vertex, then
iteratively remove the vertex with the smallest score. Finally, they output the
result with the smallest conductance during the peeling process. Based on our
framework, we propose two novel algorithms \textit{PCon\_core} and
\emph{PCon\_de} with linear time and space complexity, which can efficiently
and effectively identify clusters from massive graphs with more than a few
billion edges. Surprisingly, we prove that \emph{PCon\_de} can identify
clusters with near-constant approximation ratio, resulting in an important
theoretical improvement over the well-known quadratic Cheeger bound. Empirical
results on real-life and synthetic datasets show that our algorithms can
achieve 5$\sim$42 times speedup with a high clustering accuracy, while using
1.4$\sim$7.8 times less memory than the baseline algorithms.

本文提出了一个基于 peeling 的图聚类框架 PCon ，并使用该框架提出了两个线性时间和空间复杂度的算法 PCon_core 和 PCon_de ，可以在处理十亿级别的图数据时实现高准确度的聚类效果，而且 PCon_de 的近似度理论上提升到了常数级，相较于基线算法可以在速度上提升 5~42 倍且更节省内存。

可扩展和有效的基于传导度的图聚类

Scalable and Effective Conductance-based Graph Clustering

Recently, random feature attentions (RFAs) are proposed to approximate the
softmax attention in linear time and space complexity by linearizing the
exponential kernel. In this paper, we first propose a novel perspective to
understand the bias in such approximation by recasting RFAs as self-normalized
importance samplers. This perspective further sheds light on an \emph{unbiased}
estimator for the whole softmax attention, called randomized attention (RA). RA
constructs positive random features via query-specific distributions and enjoys
greatly improved approximation fidelity, albeit exhibiting quadratic
complexity. By combining the expressiveness in RA and the efficiency in RFA, we
develop a novel linear complexity self-attention mechanism called linear
randomized attention (LARA). Extensive experiments across various domains
demonstrate that RA and LARA significantly improve the performance of RFAs by a
substantial margin.

本文提出了一种基于自归一化重要性采样器的线性随机化注意力机制，结合了随机特征关注性的表达性和计算效率，能够以线性时间和空间复杂度近似整个 softmax 注意力，与随机特征关注性相比，具有很大的性能优势。