The unsupervised learning of community structure, in particular the
partitioning vertices into clusters or communities, is a canonical and
well-studied problem in exploratory graph analysis. However, like most graph
analyses the introduction of immense scale presents challenges to traditional
methods. Spectral clustering in distributed memory, for example, requires
hundreds of expensive bulk-synchronous communication rounds to compute an
embedding of vertices to a few eigenvectors of a graph associated matrix.
Furthermore, the whole computation may need to be repeated if the underlying
graph changes some low percentage of edge updates. We present a method inspired
by spectral clustering where we instead use matrix sketches derived from random
dimension-reducing projections. We show that our method produces embeddings
that yield performant clustering results given a fully-dynamic stochastic block
model stream using both the fast Johnson-Lindenstrauss and CountSketch
transforms. We also discuss the effects of stochastic block model parameters
upon the required dimensionality of the subsequent embeddings, and show how
random projections could significantly improve the performance of graph
clustering in distributed memory.

该研究使用基于矩阵草图的方法来解决在大规模图分析中传统方法遇到的挑战，尤其是无监督学习的社区结构划分问题，实验表明该方法在分配内存中可以获得出色的聚类效果，同时提高了聚类速度。

分布式草图缩放图聚类

Scaling Graph Clustering with Distributed Sketches

As parallel computing trends towards the exascale, scientific data produced
by high-fidelity simulations are growing increasingly massive. For instance, a
simulation on a three-dimensional spatial grid with 512 points per dimension
that tracks 64 variables per grid point for 128 time steps yields 8~TB of data,
assuming double precision. By viewing the data as a dense five-way tensor, we
can compute a Tucker decomposition to find inherent low-dimensional multilinear
structure, achieving compression ratios of up to 5000 on real-world data sets
with negligible loss in accuracy. So that we can operate on such massive data,
we present the first-ever distributed-memory parallel implementation for the
Tucker decomposition, whose key computations correspond to parallel linear
algebra operations, albeit with nonstandard data layouts. Our approach
specifies a data distribution for tensors that avoids any tensor data
redistribution, either locally or in parallel. We provide accompanying analysis
of the computation and communication costs of the algorithms. To demonstrate
the compression and accuracy of the method, we apply our approach to real-world
data sets from combustion science simulations. We also provide detailed
performance results, including parallel performance in both weak and strong
scaling experiments.

本研究提出第一个能够在分布式内存上实现 Tucker 分解的并行算法，通过压缩科学模拟产生的大规模数据，尽量保持数据准确性。对使用该算法的真实数据集进行了压缩和精度分析，并提供了详细的性能结果，包括弱和强缩放实验中的并行性能。