Random graph models are playing an increasingly important role in science and
industry, and finds their applications in a variety of fields ranging from
social and traffic networks, to recommendation systems and molecular genetics.
In this paper, we perform an in-depth analysis of the random Kronecker graph
model proposed in \cite{leskovec2010kronecker}, when the number of graph
vertices $N$ is large. Built upon recent advances in random matrix theory, we
show, in the dense regime, that the random Kronecker graph adjacency matrix
follows approximately a signal-plus-noise model, with a small-rank (of order at
most $\log N$) signal matrix that is linear in the graph parameters and a
random noise matrix having a quarter-circle-form singular value distribution.
This observation allows us to propose a ``denoise-and-solve'' meta algorithm to
approximately infer the graph parameters, with reduced computational complexity
and (asymptotic) performance guarantee. Numerical experiments of graph
inference and graph classification on both synthetic and realistic graphs are
provided to support the advantageous performance of the proposed approach.

本文基于随机矩阵理论，在研究大规模的随机 Kronecker graph 时，发现其邻接矩阵近似遵循一个带有小秩信号矩阵和四分之一圆形奇异值分布的噪声矩阵，提出了一种 “去噪和求解” 的元算法，以减少计算复杂度和提高性能保证，给出了在合成和现实图上进行图推理和图分类的数字实验以支持该算法的优越性能。

大规模和密集随机 Kronecker 图的分析和近似推理

Analysis and Approximate Inference of Large and Dense Random Kronecker  Graphs

Covering option discovery has been developed to improve the exploration of
reinforcement learning in single-agent scenarios with sparse reward signals,
through connecting the most distant states in the embedding space provided by
the Fiedler vector of the state transition graph. However, these option
discovery methods cannot be directly extended to multi-agent scenarios, since
the joint state space grows exponentially with the number of agents in the
system. Thus, existing researches on adopting options in multi-agent scenarios
still rely on single-agent option discovery and fail to directly discover the
joint options that can improve the connectivity of the joint state space of
agents. In this paper, we show that it is indeed possible to directly compute
multi-agent options with collaborative exploratory behaviors among the agents,
while still enjoying the ease of decomposition. Our key idea is to approximate
the joint state space as a Kronecker graph -- the Kronecker product of
individual agents' state transition graphs, based on which we can directly
estimate the Fiedler vector of the joint state space using the Laplacian
spectrum of individual agents' transition graphs. This decomposition enables us
to efficiently construct multi-agent joint options by encouraging agents to
connect the sub-goal joint states which are corresponding to the minimum or
maximum values of the estimated joint Fiedler vector. The evaluation based on
multi-agent collaborative tasks shows that the proposed algorithm can
successfully identify multi-agent options, and significantly outperforms prior
works using single-agent options or no options, in terms of both faster
exploration and higher cumulative rewards.

本文提出了一种基于 Kronecker 图的多智能体协同探索的选项发现方法，通过鼓励智能体连接相应的最小或最大 Fiedler 向量，构建多智能体共同目标状态，从而在多智能体任务中实现更快的探索和更高的累积奖励。