The Graph Pencil Method: Mapping Subgraph Densities to Stochastic Block Models

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.

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 \langle d^3 \rangle = \sum_k \pi_k (\sum_j \pi_j B_{jk})^3 Expanding the right hand side gives \sum_k \pi_k \sum_j \pi_j B_{jk} \sum_r B_{rk} \sum_s B_{sk} However mu (3-star) = \sum_k \pi_k \sum_{j, r, s distinct} B_{jk} B_{rk} B_{sk} so the two expressions do not coincide. As equality (6) is the foundation of the proposed approach, I am not convinced of the method. More 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?

Questions

The homomorphism density does not seem to take care of automorphisms of the counts; is that not an issue? Is 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? There is a lot of literature on graph with prescribed degree distributions, see for example Britton, T., Deijfen, M., & Martin-Löf, A. (2006). Generating simple random graphs with prescribed degree distribution. Journal of statistical physics, 124, 1377-1397 and Van 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). In Figure 2 in the supplementary material, how many numbers of nodes were used? Was it a step size of 1? The graphs for Figure 2 are very dense; how does the proposed method work for sparser graphs?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

2 fair

Contribution

1 poor

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.

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.

Strengths

- It is nontrivial study to consider the inverse map from subgraph densities to a stochastic blocking model. - 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: L63: entries, give -> entry, gives L79: explain(ing) L117: Recall(ing) L141: allowed -> allows Suggestions: Eq.10 looks a bit lengthy, and can be moved to Supplement.

Questions

How to generalize your method to capture hypergraphs with multi-edges between two vertices, signed graphs? Can you discuss more on how does the method capture large sparse graphs, and graph with structured sparsity?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

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.

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.

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: 1. 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? 2. 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? 3. 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. The 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.

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. 2. 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? 3. 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). 4. 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? 5. 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

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).

Equation (6)

Thank you for your explanations. I am still not satisfied with (6). Formula (1) details \mu for a SBM on N nodes. Here N is finite from what I understand; otherwise (1) may be an infinite sum as block sizes will be infinite. So that does not seem to be intended. Consider the simple case of K=1, only one block, that is, an ER graph. Then, with edge probability p = B(1,1) and pi_1 = 1 for all i, and d_1 = p \mu (3-star) = 4 (n choose 4) p^4. In contrast, < d^3> = p^3. Equation (6) states that these two terms are equal. What am I missing?

Increase of the score in the hope that the authors will deliver their promise

Thanks for taking the time to address my questions. The title summarizes what my intention is. As long as the readability of the paper gets improved, the authors can use the phrases or explanations I provided in the review. That being said, I am not yet satisfied with answer to the question on statistics of the random quantity in Eq (34). The authors might think more on this to quantify the uncertainty (in terms of some suitable consistency measures--asymptotic or non-asymptotic) in dealing with a sample sub-graph density. Good luck.