Master’s Thesis Abstract

Minimax Rates of Community Estimation for InhomogeneousMultilayer Stochastic Block Models（非一様多層確率的ブロックモデルにおけるコミュニティ推定のミニマックスレート）
Dept. of Mathematical Informatics 48226221
Supervisor

Kota Nakagawa（中川 皓太）
Prof. Fumiyasu Komaki（駒木 文保 教授）
Individual community

Edges are generated (")
𝐴with prob.
𝑝ℓ (the same community)𝑞ℓ (different communities)𝑧 (")

1 Introduction

Global community

Communities changewith prob. 𝜌𝑧∗

𝐴($)

𝑧 ($)

𝑧 (%)

…

…

It has become increasingly common to observe multiple networks for the same nodes in various applications that investigate the relationships between elements. Multilayer networks are appeared, for instance, when constructing diﬀerent networks fromvarious interactions in social network analysis [2], orcombining and comparing brain data collected fromindividual participants [6]. In such datasets, it is necessary to analyze common structures across the entire networks while also paying attention to the differences in structures between layers.
For single-layer network structure analysis, community detection using the stochastic block model(SBM) [3] is a well-established task. In the SBM,n vertices are partitioned into K communities. The
probability of an edge being present only depends
on the combination of communities to which the twovertices belong.
While the SBM is limited to handling single networks, the inhomogeneous multilayer stochastic blockmodel (IMLSBM) is a natural extension of the SBM
and one of the theoretical framework for multilayer
networks. This framework was initially introduced ina slightly more general form by Paul and Chen [6],and Chen et al. [1] simpliﬁed and redeﬁned it for thecase where the number of communities K = 2.
The IMLSBM consists of two stages. In the ﬁrst
stage, it generates individual community assignments
for each layer from the community structure common
to the entire network, termed as global communityassignment. Individual communities are obtainedby randomly changing the elements of each global
community to another community with probability
ρ, which represents inhomogeneity and demonstrates
the situation where the structures of each layer are“correlated but not identical.” In the second stage,
networks for each layer are generated according toSBMs from the individual communities of each layer.
The model is schematically represented in Figure 1.
The goals of our study is to show the theoreticallimits of estimating global community assignment for
the IMLSBM and to construct an optimal and eﬁcient estimation algorithm. This study gives insights
into the inter-layer relationships of multilayer networks and signiﬁcantly contributes to the analysis ofGraphs

𝐴(%)

Fig. 1. Schematic diagram of the IMLSBM.

real-world network data with diverse structures.

2 Related Work
Despite its practical signiﬁcance, the theoreticalproperties of the IMLSBM are only known within alimited scope. In the homogeneous model, the minimax rates for Hamming loss in the estimation of
global community is known where n tends to inﬁnity[5], and a polynomial-time algorithm achieving thisrates was proposed by Xu et al. [7]. While theseresults provide intriguing insights into the impact ofsignal strength coupling in multilayer networks, theeﬀects of inter-layer structural diﬀerences and noiseon estimation remain unclear. Chen et al. [1] gave
the minimax rates and analysis of algorithms thatachive this rates in the inhomogeneous case, but theseresults are limited to the case of the number of communities K = 2. Considering networks which appear
in many application domains often involve numerous
communities, further extensions are necessary. To
the best of our knowledge, our study provides theﬁrst analysis of estimation limits and optimality ingeneral multilayer network models with inhomogeneous structures and three or more communities.

3 Theorical Results
The theorical contributions consist of two parts.
3.1 Minimax lower bounds
The ﬁrst result gives minimax lower bounds of global
community estimation for the IMLSBM. Under theassumption of uniform community sizes and a ﬁxed
the number of communities K, we bound the asymptotic minimax rates for expected proportion of misclustered vertices asexp {−(1 + o(1))I}(1)

where the number of vertices n tends to inﬁnity andI is the signal-to-noise ratio (SNR) of the IMLSBM.

Minimax Rates of Community Estimation for Inhomogeneous Multilayer Stochastic Block Models (Kota Nakagawa)d = 10.0

d = 50.0

d = 100.0tions, we demonstrated that the two-stage algorithm
achieves a balance between high estimation accuracy
and reduction in time complexity. Our contributions
provide essential insights into the theoretical properties of this model, and provide a foundation for futurework.

4 Numerical Experiments

Bibliography

In addition to theoretical analysis, we demonstrate
the performance of the algorithm in practical situations through numerical simulations. As a comparison method, we adopt the co-regularized spectralclustering proposed by Kumar et al. [4], which iscommonly used for community detection in multilayer networks.
We compare the performance of the two algorithms
in estimating global and individual communities, anddemonstrate that the proposed method reduces losses
in both cases (Figure 2). Additionally, comparing thecomputational time of two methods, we see that theproposed method exhibits high scalability with thenumber of layers (Figure 3).

[1] Chen, S., Liu, S. and Ma, Z., Global and individualized community detection in inhomogeneous multilayer networks, The Annals of Statistics, Vol. 50,
No. 5, pp. 2664–2693 (2022).
[2] Dickison, M. E., Magnani, M. and Rossi, L., Multilayer Social Networks, Cambridge University Press(2016).
[3] Holland, P. W., Laskey, K. B. and Leinhardt, S.,
Stochastic blockmodels: First steps, Social Networks,
Vol. 5, No. 2, pp. 109–137 (1983).
[4] Kumar, A., Rai, P. and Daume, H., Co-regularized
multi-view spectral clustering, Advances in Neural Information Processing Systems, Vol. 24 (2011).
[5] Paul, S. and Chen, Y., Consistent community detection in multi-relational data through restricted multilayer stochastic blockmodel, Electronic Journal ofStatistics, Vol. 10, No. 2, pp. 3807–3870 (2016).
[6] Paul, S. and Chen, Y., A random eﬀects stochasticblock model for joint community detection in multiple networks with applications to neuroimaging, The
Annals of Applied Statistics, Vol. 14, No. 2, pp. 993–1029 (2020).
[7] Xu, M., Jog, V. and Loh, P.-L., Optimal rates for community estimation in the weighted stochastic blockmodel, The Annals of Statistics, Vol. 48, No. 1, pp.
183–204 (2020).

5 Conclusion
We theoretically revealed the limits of global community estimation error for the IMLSBM and analyzed MAP-based estimation with spectral clustering
initialization. This is polynomial-time algorithm inthe size of input and was shown to be minimax optimal under ﬁxed number of communities and uniform
sizes for each community. Through numerical simula-loss

The signal strength depends on connection probabilities and the noise level correlates with the inhomogeneity parameter.
The proof is based on the discussion by Chen et al.
[1], which provides the minimax rates for the case of
K = 2. We extend the combinatorial arguments of
their proof and replace concentration inequalities in
it with tighter ones.
3.2 Algorithm and optimality
Second, we analyze a polynomial-time algorithm for
global community estimation in the IMLSBM andshow its minimax optimality under the similar assumptions as above and a ﬁxed K. The algorithm isan extension of the estimation algorithm proposed
by Paul et al. [1] from the case of K = 2 toK ≥ 3. It is a two-stage algorithm which involve
consistent initialization through spectral clusteringand reﬁnement based on MAP estimation. Spectralclustering is applied to an average adjacency matrix
which is trimmed vertices with high degrees to amplify SNR. Vanilla MAP estimation faces optimization challenges due to dependencies between vertices,which also makes theoretical analysis diﬃcult. However, these issues can be addressed through parameter ﬁxing by the initial point.
The proof strategy of the optimality of the algorithm is also structured in two stages. In the ﬁrst
step, we show that the output of spectral clustering
under a ﬁxed K satisﬁes consistency with the global
community. Subsequently, by ﬁxing parameters withinitial points that satisfy the consistency assumption,
we prove that the MAP estimation yields a minimax
optimal estimator.

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0modelCoRegSC
MAPBased

23

c4

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

52

loss

d = 10.0
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0

c4

52

d = 50.0

CoRegSC
MAPBased
3c4

3c4

545

d = 100.0

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0model230.7
0.6
0.5
0.4
0.3
0.2
0.1
0.05

23c45

23cFig. 2. Performance of co-regularized spectralclustering (blue) and the proposed algorithm (orange) for global (top) individual(bottom) community estimation.
modelCoRegSC
MAPBasedtime(sec)

2.0
1.5
1.0
0.5
0.0

35710L

1520Fig. 3. Computation time of co-regularized spectral clustering (blue) and the proposed algorithm (orange) under diﬀerent numbersof layers.