The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models
Authors: Lee M. Gunderson
Gecia Bravo-Hermsdorff
Peter Orbanz
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic block model
SBM
graphons
matrix pencil method
method of moments
TL;DR: We propose the graph pencil method: an elegant and efficient procedure for inferring a stochastic block model (SBM) from prescribed subgraph densities.

Abstract: In this work, we describe a method that determines an exact map from a finite set of subgraph densities to the parameters of a stochastic block model (SBM) matching these densities. Given a number K of blocks, the subgraph densities of a finite number of stars and bistars uniquely determines a single element of the class of all degree-separated stochastic block models with K blocks. Our method makes it possible to translate estimates of these subgraph densities into model parameters, and hence to use subgraph densities directly for inference. The computational overhead is negligible; computing the translation map is polynomial in K, but independent of the graph size once the subgraph densities are given.

The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models
Lee M. Gunderson Gatsby Unit University College London
Gecia Bravo-Hermsdorfff Department of Statisties University College London
Peter Orbanz Gatsby Unit
University College London
Abstract
In this work, we describe a method that determines an exact map from finite set of subgraph densities to the parameters of stochastic block model (SBM) matching these densities. Given a number K of blocks, the subgraph densities of finite number stars and bistars uniquely determines a single element of the class of all degree-separated stochastic block models with K' blocks. Our method makes it possible to translate estimates of these subgraph densities into model parameters, and hence to subgraph densities directly for inference. The computational overhead is negligible; computing the translation map is polynomial K, but independent of the graph size once the subgraph densities are given.
1 Introduction
The class of infinitely exchangeable random graphs is large class of network models that contains all graphon models [6. 21] and stochastic block models (SBMs) [1. 12]. The key statistics such random graphs are subgraph densities: each fixed, finite graph defines a subgraph density, and it is well known that every exchangeable graph distribution is completely determined by the collection of all its densities of finite subgraphs [12. 21].
In general, an infinite number of densities is required uniquely determine an infinitely exchangeable graph distribution. For subclass of models, a finite number of densities suffice. In combinatorics, these random graph distributions are called finitely forcible [21]. particular, every stochastic block model is completely determined by a finite number of subgraph densities [21]. Such finite number of subgraph densities can consistently estimated at a guaranteed asymptotic rate from a single graph-data as this graph grows large [3, 17, 30].
It has long been recognized that the role subgraph densities play for exchangeable network models is analogous to that played by moments for estimation problems on Euclidean sample spaces [5, 7, 12. 22]. On Euclidean space, the method of moments [24, 26] is powerful inference tool, in particular for mixture models [4, 14]. This suggests that subgraph densities should be well-suited for inference in stochastic block models in particular, since these models are network analogue of mixture models and only a finite number of densities must be estimated.
Nonetheless, most inference algorithms used in practice (e.g., [8, 9, 13, 18, 25)) do no rely subgraph densities, but rather on some combination of maximum likelihood estimation, MCMC sampling, variational inference, clustering of the nodes, or other heuristics. The reason is that estimating subgraph densities is only first step in the inference process once the densities are known, they must be translated into an estimate of graphon or stochastic block model.
This paper introduces new method that does so by generalizing classical strategy for inferring latent sources (sometimes known Prony's method [26]) to graph data. The classical Prony's
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

method is an example of an algorithm that recovers sparse signal from noisy data, and is related to compressed sensing [28] and the notion of matrix pencil [23].
Our method proceeds in two steps. The first step (section 3.2) is essentially an application of Prony's method to estimate properties of individual latent blocks, such their normalized degrees and their relative sizes. The second step (section 4.2) is entirely new; by leveraging the properties inferred in the first step, uses generalization of Prony's method infer properties of pairs of the latent blocks, such as the connection properties of a stochastic block model.
The proposed method solves several problems simultaneously: it estimates parameters without laborious and delicate numerical fitting, and makes it possible to efficiently sample from the model without the eequuently-encountree problem of degeneracy that plagues many intuitively attractive network models [15, 16, 19]. In contrast to other algorithms for fitting stochastic block models (e.g.. [8, 10, 11, 25)) and graphons (e.g. [2, 20, 29]), our method requires essentially zero computational overhead once the subgraph densities have been estimated.
2 Notation and Definitions
We use lower-case bold symbols to denote vectors, and upper-case bold symbols to denote matrices and higher-order tensors. Non-bold versions of these symbols refer particular entries of the bold versions, indicated by their subscripts. We use o to denote Hadamard product (i.e., element-wise multiplication), for inner product, and angled brackets () denote expectation.
graph G is defined by a set of vertices/nodes V(G) and set of edges E(G) S V(G) V(G) de- noting pairwise connections between nodes. For simplicity. here we focus on undirected, unweighted graphs, with no self-loops or parallel edges. Indexing the N [VG)] nodes by the positive integers [N], we can represent G by its N-by-N adjacency matrix A, where A.j Aja = 1 if there is an edge between nodes and j. and 0 otherwise.
A stochastic block model SBM(T, IT, B) is defined by: æ, a probability vector of length K, which assigns each node to one of K (unobserved) latent blocks/communittis:; and B, K-by-K connectivity matrix, whose entries Bx give the probability of an edge connecting a node in block k to node in block k. As we are considering undirected graphs, B symmetric.
Sampling a graph from a SBM(T, B) proceeds in two steps. First, for each node n E [N]. sample its latent block k(n)) [K] independently from π. Then, for each pair of nodes (n, n'), include an edge between them independently with probability Be(n)((w)- Thus, a stochastic block model defines a distribution over graphs with N nodes for all choices of N, and can be identified with the limit of this sequence of distributions as N 20.
As mentioned in the introduction, such infinitely exchangeable graph distributions can be character-
ized by their homomorphism densities' p(g). Indexed by (some family of) subgraphs g, homomor-
phism densities are the graphical analogue of the classical moments of a distribution [5, 12, 22]. For a stochastic block model, one can compute (l(g) by summing over all possible assignments of the vertices of the blocks of SBM(T, B) [21]]
KIV Σ 2: (o) [K]
[ (EV(
(())) SBM(
[I
T(ti)
x
B Ba(0)() (1.))E(())
II
(I)
hommomomhiss density of subgraph g in given hy and with K blocks
sum over all maps yp from vertices in g the blocks
probability of assigning the vertices those blocks
probability of the corresponding edges
In the following two sections (sections and 4), we describe how to recover the parameters of an SBM from its subgraph densities. Later, section 5, we describe how infer these subgraph densities using a graph sampled from such an SBM.
Note that the notion homomorphism only enforces that edges g be present; does not enforce the absence of edges between pairs of nodes in that do not share an edge. For example, when g has no edges, the homomorphism density is always 1. This is in contrast to the notion of induced subgraph density, which does enforce the absence of those edges.

---

3 Mapping Star Densities to Block Degrees
As the first step of our method, we obtain the normalized degrees of the blocks (equation (4)), as well as their relative sizes л. This can be seen as application of the classical matrix pencil method to the degree distribution, for which the density of the star subgraphs serve as sufficient statistics.
3.1 Classical Coin Collecting
Before we explain our graph pencil method, let us consider the simpler case of mixture model for infinitely exchangeable sequences of binary variables. Also known as the Bernoulli mixture model [14, 27], such a distribution can be thought of as the outcomes of (some number of) flips of (some number of) biased coins, where each coin is sampled i.i.d. from (possibly unequal) mixture of K different biases.
To recover the parameters of this model, one must infer the K (unobserved) latent biases bn. as well as the fraction , of coins with each bias. Note that one does not know which of the coins have the same latent bias (otherwise the inference problem would be trivial).
The moments of this distribution are the expectation of powers of these latent biases, which indexed by the exponents r E N:
(b") = Σ T
Note that these moments can be consistently estimated from the observed data, as we are averaging over the latent variables. From these moments, one can systematically infer the mixture proportion π and the biases b using the matrix pencil method.
In short, construct two matrices C and C', with entries Cg (bi+)) and Cy (b+++1))
(6))
(b))
(6K-1)
{b2)
(62)
(6k)
(b1)
(12)
(B)))
(b2)
(b3)
aktzz
C =
C²=
(3)
16K-1)
(bx)
(62K-2)
(b
(bk+1)
(62k-11
While not immediately obvious, it is easy show that the eigenvalues of C'C-1 are the entries of b. From these, it is straightforward to obtain the associated entries of π. In the next section, we show why this is the case, while superficially replacing the biases b of the latent coin types with the normalized average degrees d of the latent node blocks.
3.2 Distilling the Degree Distribution
The first step of our graph pencil method is to apply the standard matrix pencil method to the obtain the average normalized degree of each of the K latent blocks (that is, the likelihood that random node shares an edge with a node in block k). Denoted by d, the entries of this vector are:
d2 = ===" BBBBBB
These d, are latent parameters of the blocks, so we can solve for them in exactly the same way we did for by in the previous coin example. To this end, we consider the analogous moments:
(d") Σ T
As before, while म. and d, are unobserved, the resulting moments can be consistently estimated from observations. In particular, they are precisely the homomorphism densities of the star subgraphs:
(d") m( = (d") 1 (T)
(d = ((()) (V)
(d = u (V)
(6)
3

---

We then define the two matrices C and Ca with entries Co ;j = (d and C & (d" (d++)+)), and the eigenvalues of C (Co) - are the normalized degrees the K blocks. To see why, notice that C can be written as sum of K rank-1 matrices (weighted by π))
de
dz
dk
d
C
k
Σ
k
di
d
o
K-1
k
k
dk
d
K
-
di
d%
0
di
dk
:
d
dk
dk-1
= V diag(1) V
where we have defined V the matrix with entries
1
d
i.e:
d
d
d
d
K
V
(8)
dk
d2
K
-
By decomposing Cd in the same manner, we get:
C V diag(rd) V
(9)
where diag(re rd) is the diagonal matrix with entries क. nzd
We now that (Co) can be diagonalized as follows:
Cd (C=))=1 = (V diag(Td) v (V diag(T) VT)- -1
V diag(Td)) V (V") -1 diag(a π 1) V-1
V didg(Tr) diag(T V-1
V diag(d) V-1
(10)
Hence, the eigenvalues of Cdd (C+) are indeed the normalized degrees of the K latent blocks:
eigval (c=(C))))) = {d KE[K] J
(11)
Remark 1 (Degree separated assumption). This is where the assumption of degree-separated blocks used; if the normalized degrees of the blocks are not unique, then V will not be invertible.
From the entries of d, we know the entries of V, and can solve linear system equations for the corresponding entries of π:
Σ VI (d8-1)
(12)
4 From Bistar Densities to Stochastic Block Model
This second step of our graph pencil method is the main insight our paper. uses the results from the previous step to reconstruct the connection probabilities Br

---

4.1 Gluing Graphs: An Algebra
We now describe natural algebra over rooted subgraphs (see Chapter 6 of [21]). We find that using this notation makes our method easier to understand, and facilitates reasoning about its generalizations. For longer introduction, see appendix A.
Recall the definition of homomorphism subgraph densities of an SBM in equation (1). For a given distribution (T,, B), each subgraph g corresponds homomorphism subgraph densities can be seen as generalization the subgraph g, (singly-)rooted densities also require a designated "rooted" vertex Vgg). And instead of a single scalar, they correspond to (a vector of) K scalars μlg, v), indexed by the block k [K] to which the rooted vertex v mapped:
scalar density μ(g)). Rooted this notion. In addition to
(
P4 (g,
Σ
II (VV())
FP(i)
x
B Pe(is))) ((.))
II
(13)
BB
vV K MA. (())=
homomorphism density of subgraph with rooted vertex in block
probability of assigning remaining vertices to those blocks
probability of the comesponding edges
sum over maps op that send veries block &
The sum is now over maps that send the rooted vertex v to a particular block k. and the probability of assigning the vertices (gg blocks includes only the remaining "unrooted" vertices. All the edges ('gg) contribute to the product exactly as in equation (1).
A rooted vertex with single edge corresponds to the normalized degrees of the K blocks:
(rooted vertex with an edge)
d (normalized degrees of the blocks)
(14)
Rooted subgraphs may be combined via the gluing product, denoted by The gluing product corresponds to taking their disjoint union, then merging (i.e., "gluing") the rooted vertices:
(gluing rooted vertices)
Jo Y
d d²
(entrywise multiplication)
fo V
V
do d = d
y V
d o a d
(15)
Algebraically, the gluing product corresponds to entrywise multiplication of the vectors, also known the Hadamard product.
Finally, to convert rooted subgraph into an observable subgraph density, the rooted vertex may be "unrooted"" by taking the dot product with π::
(unrooting vertices)
d
(d*) (dot product with π
(16)
Table Operations using homomorphism densities of singly- rooted subgraphs.
glyph
symbol
meaning
I
d = π
vector of the K normalized degrees
y
d d
entrywise multiplication
d
homomorphism density of subgraph
Before describing how to recover the entries B, us summarize the method for recovering the normalized degrees from the previous section using the language of rooted graphs.
For an SBM with K blocks, define a vector of (at least) K rooted subgraphs, and take the outer product of this vector with itself where entries are combined via the gluing product. For example:
t
V
VOV.
y
Y
(17)
V
5

---

While the rooted subgraph densities are not directly observable, their unrooted counterparts are, and the entries of C (equation (3), left) are given by the densities of these unrooted versions:
I
V
C (vov) T
V
V
(18)
V
(The glyph containing an unrooted vertex and edges evaluates to L.)
To obtain the second matrix Cdd (equation (3), right), glue rooted subgraph ] to all entries before unrooting:
V
V
Cd = ((vor))ot)
Y V
V
(19)
Indeed, the reason that the spectrum of Co(Cd)- gives the normalized degrees d of the latent blocks is precisely because we glued an extra copy of the corresponding rooted subgraph ] in the construction Cd. The next section follows a similar recipe.
4.2 Extracting the Edge Expectations
The previous matrices C and Od were obtained by taking dot product that sums over the K blocks. This allowed us to obtain properties of a single block (e.g.. its degree dg). The first main insight of this paper is that the matrix pencil method can also be used obtain properties of pairs of blocks (i.e., their connection probability ) by summing over such pairs.
The extension of the gluing algebra to birooted subgraphs is relatively straightforward; a birooted subgraph (g; u, v) has two (distinct) rooted vertices, and their gluing product given by taking the disjoint union then separately merging the vertices rooted u and the vertices rooted e.
Table 2: Operations using homomorphism densities of doubly-rooted subgraphs.
glyph
symbol
meaning
I
d1 =
row matrix of (left) normalized degrees
ld R
column matrix of (right) normalized degrees matrix of connection probabilities entrywise multiplication
t
LoR
I
To (L oF (( observable subgraph density
For an SBM with K blocks, there are K + (K) degrees of freedom for the entries of B. So we define a vector (at least) K + (K) birooted subgraphs. To this end, we use the symmetric polynomials, with exponent at most K, in the two variables I and corresponding to the normalized degrees of the blocks corresponding to two roots.
+
J1
VOv
Y
o I
(20)
!!
T
!
In this example for K 2, the second row of v has been symmetrized with respect to the two rooted vertices, resulting in a formal linear combination of elements in the gluing algebra.

---

As before, Cooo is obtained by unrooting the entries, while for the construction of C we glue the rooted subgraph a-o corresponding entries of B.
2
11
o
2
2
2 1
2
(21)
!!
24 !
N V
2 L
1
C
2 H
2
2 2
2
(22)
2
V
Note that, once unrooted, isomorphic graphs are equivalent, c.g.: As promised, the eigenvalues of (Co00 are precisely the entries of B
V= V. V
eigval C (C (Coo)-1) = {BBuk' Kgk
(23)
Morcover, the structure of their corresponding cigenvectors allows to select specific entries B
= =
{[
Bre ASK
eigvee (C (cB(COO-)))
dr + dx dr
(24)
Thus, for each pair of blocks k and k' with normalized degrees d, and des, we can estimate their connection probability BEss, estimate the eigenvalue its corresponding eigenvector:
v (CB -1y
BEN
d
V V
drdx
Remark (Sufficiency of subgraph densities). Suppose fix finite number K of blocks, and consider all SBMs with K blocks. The 2K - subgraph densities defined by all stars with up to 2K - edges then completely determines the degrees and sizes of blocks. Adding the subgraph densities of all bistars with maximum degree at most K then completely determines the connection probabilities between blocks (as function of their degrees), and therefore the entire distribution of the random graph. In other words, the vector of these densities of stars and bistars is a sufficient statistic for the class of degree-separated stochastic block models with K blocks.
4.3 Beyond Degree Correlations: Adding "Two-Hop" Subgraphs
The method described above can be thought of "basic" minimum working example of much more general family of graph pencil methods. The subgraph densities in Co and Cd are sensitive only the degree distribution, and the subgraphs in Co and C contain information about the degree-degree correlations. While this sufficient to recover the parameters of an SBM when the normalized degrees of the blocks are well-separated, the method can be made more robust by adding additional subgraphs.
In particular, define the "two-hop" matrix of connection probabilities A = B B, where o denotes the matrix product weighted by л, i.e.:
Ag = Σ BB
(25)
These birooted subgraphs interact the others via gluing and unrooting (see table 3).
7

---

Table Incorporating the "two-hop" connection probability A into the gluing algebra.
glyph
symbol
meaning
B B
two-hop connection probability
A
entrywise multiplication
A
(Ao
A
homomorphism density of triangles
We can use this to add more columns to C and C
2
I I
2 n
W
C
21.
29
+
2 I
2 M
2 ". +2 M
(26)
11
2
4 V I 2
W
W
W
2 L
A
2 AA
W
C
2
2 2
+
2 A
2 2
+
2
A
(27)
2
A
2 2
W
Remarkably, we can use these larger matrices in exactly the same way as before (using the Moore- Penrose pscudoinverse). As shown in in figure 1, including these additional subgraphs can make the recovery of the SBM more robust.
assortative
neutral
disassortative
mean squared error
0.7
0.5
0.4
0.3
0.6
0.2
0.4
0.8
0.1
Dasic bistars
basic bistars
adoinng two-hop
adding two two-hop
optimal oracio
optimel oracle
2
1024
2048
4096
8192
1024
2048
4096
8192
1024
2048
4096
8192
number of nodes
Figure I: Adding "two-hop" subgraphs helps recover (dissassortattivity
We use 2-by-2 SBMs with varying degrees of assortativity to compare our basic method using bistars from section 4.2 (green squares) and the method that adds the two-hop subgraphs from section 4.3 (purple circles). The vertical axis measures the expected squared erтor of the probability of an edge between two random nodes, and shading denotes + standard deviation from the average value. The dashed orange line denotes the expected squared error if the latent blocks of the nodes were known, and both methods appear to converge at this optimal rate. When the SBM is particularly assortative (left) or disassortative (right), the inclusion of two-hop subgraphs results in notable improvement.
5 From Observed Graph to Stochastic Block Model
In order to apply the graph pencil method to an observed graph, we need to obtain unbiased estimators of the homomorphism densities used construct the C matrices. In particular, for subgraph g and a (large) graph G, we want to compute the fraction of injective maps from V(g) to V(G), such that if (u, v) E(g), then (p(u), :(v)) E(G).
5.1 Quickly Counting (Injective) Homomorphisms
We start with the adjacency matrix A, the identity matrix I, and the all-ones matrix Then, we perform our only difficult matrix multiplication: Σx Au, = D, Ag. where D is the diagonal

---

matrix of node degrees, and A is the (traceless) "two-hop adjacency" matrix. From these, we can recursively count all the relevant subgraphs using only entrywise multiplication.
We index our subgraphs with a tuple of non-negative integers (l, e, r), corresponding to: the number of edges incident to only the "left" node, the number of two-hop paths between the "left" and "right" nodes, and the number of edges incident to only the "right" node j. First, we add the two-hop paths:
M 1 I
(28)
((0c++10) = (00000) o (A - -cl)
(29)
Define the matrix of "left" degrees to be L = D (1 1) (i.c., the degree node if node j # i were deleted, and zero when i j), and the matrix of "right" degrees to be its transpose R L". Next, we add single edges to node i, then to node j:
((++1,,00) M(C.0)) (L- (l+
(30)
M(Cer+1) = M(4er) (R (R- (r - (M(
(31)
Finally, if an edge connecting the left and right nodes is to be included, we put a mark on the middle integer:
((ed'r) ((Cr)) o A
(32)
To obtain the counts of a subgraph g in the entire graph, simply sum the entries of the corresponding matrix M(l.er), This is analogous the "unrooting" operation from before.
M Mear ΣΣ M(Ger))
(33)
For example, [A] is twice the number of edges, the injective homomorphisms count both orienta- tions. The injective homomorphism densities are obtained by dividing this count by the number of injective maps
M(cer) ((gtter)))= N(N 1) ... (N - [V)))++1
(34)
6
Discussion
The map from stochastic block model to the density of a given subgraph can computed analytically (e.g., [12]), or approximated by simulation (sample graph from the model, count the number of occurrences of the given subgraph, and normalize appropriately).
contrast, the map from the subgraph densities to the stochastic block model is rather nontrivial. This paper provides a way to compute this map.
Since asymptotic rates are known for subgraph densities (see, e.g., [5] and [3]), and the mapping construct here is differentiable in the interior of its domain, should expect similar asymptotic rates for recovery of the model parameters. We do not currently know how the rate behaves at the boundaries. At the boundary, the method may principle output invalid probabilities, as there is at present no explicit constraint enforcing the connection probabilities to be between 0 and 1. Hence, as many other methods for inferring SBMs, our method well-hehaved the interior.
Finally, we note that the method presented here can be extended in a variety of ways, for example to directed edges, weighted edges, directed weighted edges, etc.
Code
Code implementing our method is available at http://gghhha.aooomoocom//////ie
Acknowledgments and Disclosure of Funding
LMG and PO were funded by the Gatsby Charitable Foundation.

---

References
[1] Abbe, E. and Sandon, C. (2015). Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In IEEE 56th Annual Symposium Foundations of Computer Science, pages 670-688.
[2] Airoldi, E. M., Costa, B., and Chan, S. H. (2013). Stochastic blockmodel approximation of graphon: Theory and consistent estimation. Advances in Neural Information Processing Systems, 26.
[3] Ambroise, C. and Matias, C. (2012). New consistent and asymptotically normal parameter estimates for random-graph mixture models. Journal of the Royal Statistical Society, Series B, 74:3-35.
[4] Anandkumar, A., Ge, R., Hsu, D., and Kakade, (2013). A tensor spectral approach to learning mixed membership community models. In Conference on Learning Theory, pages 867-881. PMLR.
[5] Bickel, P. J., Chen, A., and Levina, E. (2011). The method of moments and degree distributions for network models. Annals of Statistics, 39(5):2280-233) 2301.
[6] Borgs, C. and Chayes. J. (2017). Graphons: A nonparametric method to model, estimate, and design algorithms for massive networks. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 665-672.
[7] Bravo-Hermsdorff, G., Gunderson, L. M., Maugis, P.-A,, and Priebe, C. (2023). Quantifying network similarity using graph cumulants. Journal of Machine Learning Research, 24(187):1-27.
[8] Celisse, A., Daudin, J.-J., and Pierre, L. (2012). Consistency of maximun-likelihodd and variational estimators in the stochastic block model. Electronic Journal of Statistics, 6:1847 1899.
[9] Channarond, A.,
Daudin, J.J.,, and Robin, S. (2012). Classification and estimation in the stochastic blockmodel based on the empirical degrees.
[10] De Nicola, G., Sischka, B., and Kauermann, G. (2022). Mixture models and networks: The stochastic blockmodel. Statistical Modelling. 22(1-2):67-94.
[11] Deng. J., Huang, D.,, Chang, X., and Zhang, B. (2023). Subsampling based modified bayesian information criterion for large-scale stochastic block models. arXiv:2304. 06900.
[12] Diaconis, and Janson, (2008). Graph limits and exchangeable random graphs. Rendiconti di Matematica, 28:33-61.
[13] Gao, C., Lu, Y., and Zhou, H. H. (2015). Rate-optimal graphon estimation.
[14] Gordon, S.. Mazaheri, B. H., Rabani, Y., and Schulman, L. (2021). Source identification for mixtures of product distributions. In Conference on Learning Theory, pages 2193-2216. PMLR.
[15] Gunderson, L. M. and Brawo-Hermsddrff,, G. (2020). Introducing graph cumulants: What the variance of your social network? arXiv:2002.03959
[16] Karwa, V., Petrović, S., and Bajić, D. (2016). DERGMs: Degeneracy-rrsttrited exponential random graph models. arXiv:1612.0305:
[17] Kaur, G. and Röllin, A. (2021). Higher-order fluctuations in dense random graph models. Electronic Journal of Probability, 26:1-36.
[18] Latouche, P. and Robin, S. (2016). Variational bayes model averaging for graphon functions and motif frequencies inference in W-graph models. Statistics and Computing, 26:1 111-1177111551
[19] Lauritzen, S., Rinaldo, A., and Sadeghi, K. (2018). Random networks, graphical models and exchangeability. Journal of the Royal Statistical Society, Series B, 80(3):481-508.
[20] Li, Y., Fan, X., Chen, I.., Li, B., and Sisson, S. A. (2022). Smoothing graphons for modelling exchangeable relational data. Machine Learning, 11 111(1)311-344..
10

---

[21] Lovász, L. (2012). Large networks and graph limits, volume 60. American Mathematical Soc.
[22]
Lovász, L. and Szegedy, B. (2010). The graph theoretic moment problem. arXiv:
[23] Markus. A. S. (1988). Introduction to the Spectral Theory of Polynomial Operator Pencils.
American Mathematical Society.
[24] Pearson, K. (1894). Contributions to the mathematical theory of evolution. Philosophical Transactions of the Royal Society of London, 185:71-110.
[25] Peixoto, T. P. (2014). Hierarchical block structures and high-resolution model selection in large networks. Physical Review X, 4(1):01
[26] Prony, G. (1795). Essai experiméntal et analytique sur les lois de la dilatabilité des fluides élastiques, et sur celles de la force expansive l'eau et la vapeur de l'alkool, à différents températures. Journal de I' l'École Polytechnique (Paris). 1:24-76.
[27] Saeed, M., Javed, K., and Babri, H. A. (2013). Machine learning using Bernoulli mixture models: Clustering, rule extraction and dimensionality reduction. Neuracomputing, 119:366-374.
[28] Sauer, T. (2018). Prony's method: an old trick for new problems.
[29] Wolfe, P. J. and Olhede, S. C. (2013). Nonparametric graphon estimation. arXiv: 1309.5936.
[30] Zhang, Y. and Xia, D. (2022). Edgeworth expansions for network moments. Annals of Statistics, 50(2):726-753.


Reviews:
[{"review_id": "n6SJBjEqrT", "reviewer": "Reviewer_TUi3", "summary": "Given the subgraph densities of the stochastic block model (SBM), the authors consider the problem of obtaining SBM's parameters (node and edge probabilities). The authors observe a connection between this estimation problem and estimating parameters of an exponential signal. So, they cleverly teleported the classical Prony's method for obtaining signal parameters to obtaining the SBM's parameters. This observation by the authors is the main noteworthy contribution of the paper. Finally, the authors provide analytical formulae for computing the SBM parameters via eigendecompositions of matrices constructed from the subgraph densities of the SBM.", "questions": "1. The authors claim to have generalized Prony's method for their network problem. This generalization needs to be clarified and concrete. The \"quoted\" generalization in Sections 3.3 and 3.4 seems like using Prony's method for extracting edges. Please justify. \n2. It is a well-known fact in probability theory that the moments generally do not specify the distribution completely. In that sense, how can the subgraph densities (analogous to moments) determine the SBM parameters?  \n3. At the high level, is unlabelling vertices (in Eq (16)) similar to the law of total probability? That is, first consider conditional probabilities (labeled homomorphism densities) and then add them up to get the final probability (unlabelled densities). \n4. Eq (34) is a random quantity obtained from a realization drawn from SBM. The authors didn't provide any statistical guarantees on this quantity. For example, how accurate is this quantity compared to the true sub-graph density? \n5. I did not completely understand the details in Section 34. In particular, the glue algebra seems hard to understand. Could the authors provide a layman's explanation for extracting the edge expectations?", "limitations": "The authors have not discussed the limitations of their current approach. However, I think the proposed method is limited to only SBMs. I suggest the authors to comment on generalizing their method to exponential random graph models (if there is any).", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strength of the paper is to develop a simple and elegant solution for obtaining the parameters of SBM using classical Prony's method. The glue algebra and its connection to extracting edge probabilities seem interesting and intriguing.", "weaknesses": "The are three main weaknesses in the paper: \n1. it expects a lot of background knowledge from the reader ranging from SBM and its subgraph densities to glue algebra--for e.g., Equations in (1) and (13) appear out of the blue. How are the densities related to SBM?\n2. Some of the technical details appear to be heuristic rather than rigorous proof--for e.g., The use of glyphs in matrices and the glue algebra explanation in Sections 3.3 and 3.4 appear more like a heuristic rather than a rigorous proof. Why are the identities in equations (13)-(18) true?\n3. The title, the narrative in the abstract and introduction, and the actual problem solved are disconnected. Moreover, the current story of exponential random graphical models (which is not even discussed); titbits on statistical significance (lines 14 -21); and concluding remarks on summary statistics are very broad and unrelated. As an example, the last sentence in the conclusion, “...stepping-stones over two centuries old.” is meaningless for the reader who does not have a background in Prony’s analysis or its historical context. \nThe paper develops a procedure for obtaining parameters of the SBM model using subgraph densities. I suggest the authors rewrite the introduction/abstract/conclusion directly stating this message.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the thoughtful review.  \n\nSummary: \nYour summary was super accurate and succinct.  And we very much appreciate the \"cleverly teleported\".  Your suggestions are really helping the readability our paper, primarily with continuity of the narrative, and an inclusion of a pedagogical \"layperson\" Appendix on the gluing algebra.  \n\nStrengths: \nThank you!  We also find the gluing algebra \"interesting and intriguing\", ever since Lovasz used them to prove inequalities between subgraph densities.  And your suggestions are super helpful for making the paper more accessible.  \n\nWeaknesses: \n1)  Equations (1) and (13) are the expressions for the expected injective homomorphism densities of (un/labelled) subgraphs in a graph that was sampled from that SBM.  We will include a citation to Lovasz, but there is also an intuitive building-up of definitions that describes where Equations (1) and (13) come from, and how they dovetail nicely with the gluing algebra.  \n2) Related to the previous point, I'm making an Appendix on Gluing Algebra that is written pedagogically with examples, but makes sure to carefully define the gluing algebra and how to interpret the rooted and unrooted subgraphs.  \nIt first defines the subgraph densities $\\mu_g$ and how they are computed by Equation (1).  Then, to introduce (singly) labeled subgraphs, it shows how the normalized degrees $d_k$ are reflected in the notation as the singly-labelled edge.  \nPlugging in these definitions into Equations (13) -- (18), it is relatively straightforward linear algebra to see that and that using them in a matrix this way works (like in Equations (7) -- (11)).  \n3) This makes a lot of sense, we will certainly clean up the narrative.  \nOne of the original motivations for this work was related to Exponential Random Graph Models, but it no longer really belongs in the abstract/motivation.  It may belong better in the discussion, where we will clarify the connection with the SBMs inferred here (ie, they are often the distribution that is desired when using common choices for ERGMs).  \nI rather like the phrase about ``stepping-stones'' at the end, we will add to the Motivation/Background a short paragraph on the historical context of Prony's method and its varied applications.  \n\nQuestions: \n1) Sure, maybe \"generalization\" is not the best word.  We really liked your word: to \"teleport\" the solution.  Would you mind if we used something along those lines?  \n2) For exchangeable distributions over graphs, a bit more can be said about the structure of the mapping from subgraph densities/moments to distributions with those moments.  If two graphons have the same subgraph densities, then they are related to each other by a measure-preserving transformation of the nodes.  Moreover, we consider stochastic block models here, and these are indeed determined by a finite number of subgraph densities. This fact can be found e.g. in Lovasz’ “Large networks and graph limits”, where it is phrased as all graphons that are step functions (which includes SBMs) being ‘finitely forcible’, see Lovasz’ Corollary 16.47.  \n3) Precisely, and thank you, that is an excellent way to phrase it.  Hopefully, this will be cleared up in the Appendix on Gluing Algebra; \nafter showing how to understand labelled nodes as removing the sum over that node, the unlabelling of vertices will naturally be seen as taking the weighted sum of conditional probabilities (ie, multiplying by $\\pi_k$ and summing over $k$).  \nI promise this Appendix will have many examples for anyone who wants to check their understanding.  \n4) Good point.  There are quite a few works on the statistics of subgraph densities, we will mention the salient ones for dense and sparse graphs.  More generally though, as the section on quickly counting subgraphs, Equations (28) -- (34), addresses the practical issue of quickly counting in a real network the subgraphs required for this method.  It might be more appropriate for it to be moved into another Appendix on Counting Graphs.  \n5) Yes, absolutely, this is an excellent idea.  The Appendix on Gluing Algebra is coming along nicely, and we believe it will help a lot.  \n\nLimitations: \nIndeed, there needs to be a section added about the limitations.  For example, while SBMs can approximate any graphon to arbitrary accuracy, there will always be some amount of model misspecification unless the distribution is exactly an SBM.  As for the connection with exponential random graph models, it indeed makes more sense to include them here at the end --- there is some convincing evidence that, for many choices of subgraph constraints, when entropy is maximized, lead to an SBM with some finite number of blocks.  Also important to note would be the difficulty in handling SBMs with entries that are equal or close to 0 and 1.  "}, {"review_id": "hdiexTURGM", "reviewer": "Reviewer_hN5K", "summary": "The paper studies how to make inference sampling from a stochastic blocking model (SBM) given its corresponding subgraph densities. They first estimate the normalized degrees and the relative sizes of the latent blocks of a SBM, and then infer the connection properties of the SBM using generalized Prony's method. ", "questions": "How to generalize your method to capture hypergraphs with multi-edges between two vertices, signed graphs? \nCan you discuss more on how does the method capture large sparse graphs, and graph with structured sparsity?", "limitations": "I do not find distinguished limitations of the method. Nonetheless, I would think it could be incremented in the supplement if the method can be easily generalized to directed, weighted graphs.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- It is nontrivial study to consider the inverse map from subgraph densities to a stochastic blocking model.\n- Overall, the paper is not hard to follow. The proposed method and its properties may have some impacts on its community. As the authors claim, the proposed method can be well generalized to directed, weighted graphs.", "weaknesses": "Typos:\nL63: entries, give -> entry, gives\nL79: explain(ing)\nL117: Recall(ing)\nL141: allowed -> allows\n\nSuggestions:\nEq.10 looks a bit lengthy, and can be moved to Supplement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and comments.  \n\nStrengths: \nIt is nice that you found the paper easy to follow!  We really try to make it easy on the reader, and with the restructuring/moving parts to dedicated Appendices, we think it will be even more accessible.  \n\nWeaknesses: \nThe typos are much appreciated, and the restructuring makes a lot of sense.  \n\nQuestions: \nAs there are several parts of the main that are being moved to their own dedicated Appendices, there should be some space for us to describe how generalizations to, eg, directed/weighted would look like.  \nWith respect to multi-edges, there is a mathematically correct way to count weighted subgraph densities in a weighted network (see Lovasz), which when applied to the method described in this paper, would give the \"expected number of edges\" between a given pair of nodes (instead of the \"probability of one edge\").  \nFor directed edges, there are actually more subgraphs one can use (eg, we can reference both the in- and out- degrees of the nodes).  \nWith respect to sparsity, we will add another set of experiments in the sparse regime, where we keep the expected degree the same while increasing the number of nodes.  \n"}, {"review_id": "K2fG09md9q", "reviewer": "Reviewer_fpMW", "summary": "This paper adapts the matrix pencil method to estimate parameters in models with prescribed subgraph counts, and to simulate from them. A prime example are edge counts and the stochastic blockmodel. ", "questions": "The homomorphism density does not seem to take care of automorphisms of the counts; is that not an issue? \n\nIs the underlying graph supposed to be finite or infinite? All matrices appear to be finite; why is the notion of a limit important? Are there any theoretical guarantees regarding consistency of the estimation? \n\nThere is a lot of literature on graph with prescribed degree distributions, see for example \n\nBritton, T., Deijfen, M., & Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. Journal of statistical physics, 124, 1377-1397\n\nand \n\nVan Koevering, K., Benson, A. and Kleinberg, J., 2021, April. Random graphs with prescribed k-core sequences: A new null model for network analysis. In Proceedings of the Web Conference 2021 (pp. 367-378).\n\nIn Figure 2 in the supplementary material, how many numbers of nodes were used? Was it a step size of 1? \n\nThe graphs for Figure 2 are very dense; how does the proposed method work for sparser graphs? \n", "limitations": "There is no mention of any limitation of the method; there is no mention of model mis-specification, and there is no discussion of the variability in the estimates. ", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The idea to use the matrix pencil method for parameter estimation is interesting and the paper addresses an important problem. ", "weaknesses": "My main concern is that I do not think that (6) is correct. Focusing on d^3, we have \n\n\\langle d^3 \\rangle = \\sum_k  \\pi_k (\\sum_j \\pi_j B_{jk})^3 \n\nExpanding the right hand side gives \n\n \\sum_k  \\pi_k \\sum_j \\pi_j B_{jk} \\sum_r B_{rk} \\sum_s B_{sk}\n\nHowever\n\nmu (3-star) = \\sum_k \\pi_k \\sum_{j, r, s distinct} B_{jk} B_{rk} B_{sk} \n\nso the two expressions do not coincide. As equality (6) is the foundation of the proposed approach, I am not convinced of the method. \n\nMore generally the paper is not well presented. The abstract mentions exponential random graph models but they do not appear in the main paper at all. A particular version of a stochastic blockmodel is introduced which gives exchangeable edge indicators, and then it is claimed that this can be identified with the limit as the number of vertices tends to infinity. This is not clear at all; in which sense is the limit taken? Two SBMs, one on N vertices and the other one on N+1 vertices, need not be related at all. Is there a coupling construction which maintains exchangeability? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper.  The discussions they spurred have been useful for clarifying the paper, as there were some key misunderstandings.  \n\nWeaknesses: \nThe main concern, about Equation (6), is a misunderstanding by the reviewer, but suggests an excellent way that we can be more clear with our notation.  \nWhen estimating the subgraph densities from a finite graph, the unbased estimators are the \\textit{injective} homomorphisms, which require one to sum over distinct nodes.  \nHowever, when computing the subgraph densities from a graphon or Stochastic Block Model, the distinction between injective homomorphism counts (which require that the sums be over distinct labels) and non-necessarily-injective homomorphism counts disappears.  (Essentially this is because as $n\\rightarrow\\infty$, the fraction of maps that are non-injective goes to zero.)  \nSo equation (6) is correct, we should be more clear in our notation about whether the quantity is of the graphon/SBM or if it is of a finite graph sample.  \n\nAnother concern, which was shared by all reviewers, was about the mention of Exponential Random Graph Models in the beginning.  This makes a lot of sense.  We plan to move this to the ending discussion, where the connection to Stochastic Block Models is made (there is some convincing evidence that, for many choices of subgraph constraints, when entropy is maximized, lead to an SBM with some finite number of blocks.).  \n\nIn terms of identifying the limit of $n\\rightarrow\\infty$ with a graphon, we can elaborate on this a bit more (also see papers by Chayes and Borgs et al).  Consider a sequence of exchangeable distributions over graphs with $n$ exchangeble nodes, for $n=1,2,\\ldots$.  If the each distribution on $n+1$ nodes is related to the distribution on $n$ nodes by randomly deleting a node, then the sequence converges to a graphon (a symmetric measurable function over the unit interval) in terms of the cut norm.  \nTo make this more clear in the text, we will be explicit that an SBM is just a parameterization of a particular subset of such limiting graphons, and that it does not necessarily have an inherent number of nodes $n$ that must be sampled from it --- it describes all numbers of nodes at once, and therefore the limit as well.  \n\nQuestions: \nAs we are using homomorphism densities, there is no need to worry about automorphism counts in the numerator, so long as you also do not worry about it in the denominator (they cancel out either way).  \n\nThe \"underlying graph\" is the underlying graphon/SBM, from which we are sampling graphs of finite size.  As we are estimating the parameters of this model, the only notion of limit is the intuition that \"a distribution is the limit of infinite sample size\".  \n\nThe question about sparsity is very good, both theoretically and practically.  We will add another set of experiments in the sparse regime, where we keep the expected degree the same while increasing the number of nodes.  "}]

Author rebuttal:
Thank you so much to all the reviewers for taking the time to read our paper.  We really appreciate it being easy and fun to read, so the comments on how to improve the narriative were particuarly appreciated.  

The main issues seem to be the mention of Exponential Random Graph Models in the beginning.  This we will move to the end, with motivation for why we are mentioning it.  SBMs (like the ones obtained by our method) are often the distribution that is desired when using common choices for ERGMs.  And there is some convincing evidence that, for many choices of subgraph constraints, when entropy is maximized, the result is an SBM with some finite number of blocks.  We will include this in the discussion.  

Also related to structure, we are creating Appendices that give a more detailed introduction to the gluing algebra, how it is used in the method, and related proofs.  

Sparsity was also mentioned twice, so we will add another set of simulations where the graphs have constant average degree.  

With the space freed up, we can also give examples of further extensions to (for example) weighted and directed graphs.  

Thank you so much again, and we are looking forward to hearing back from you.  

Very best, 
The Authors

Meta-review: This paper developes a graphical generalization of the classical Prony method. The reviewer's agree that the problem is important and the analytical solution is clever. The authors are strongly encouraged to take the suggestions by the reviewers into account as they prepare their final manuscript.
Decision: Accept (poster)