- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The research objective is to determine, through rigorous significance testing, whether deep graph clustering captures community structure beyond what can be explained by degree-preserving random graphs. A key feature of the proposed approach is that it generates exchangeable null graphs using edge-swap chains and treats the trained clustering pipeline as a black box.
The experiments use synthetic and real-world graphs to evaluate the validity of the test in terms of type-I error control, comparisons with asymptotic tests, the discrepancy between statistical power and clustering recovery, and p-values obtained on real-world graphs.
Critical strengths
S1. As illustrated in Figure 1, even random graphs can exhibit modularity values close to 0.3 (in fact, modularity is strongly influenced by the number of nodes). While modularity can serve as a relative measure for comparing graph partitions, its absolute values are difficult to interpret. In contrast, the proposed method constructs a null distribution from the scores obtained by applying the same pipeline to degree-preserving random graphs and evaluates statistical significance using p-values. This is a well-justified approach.
S2. The experimental evaluation is extensive, using numerous synthetic graphs and seven real-world graphs to assess type-I error control, comparisons with asymptotic tests, the discrepancy between statistical power and clustering recovery, and p-values on real-world graphs.
Critical weaknesses
W1. Most real-world graphs exhibit structural properties beyond their degree sequences, such as community structure, high triangle counts, and degree correlations. Rejecting the null hypothesis is almost trivial in many cases. Indeed, Table 1 shows that nearly all entries reject the null hypothesis with p-values at the minimum attainable level. Also, the paper does not show situations where the proposed method provides useful information for practical decision-making. The authors should experimentally demonstrate concrete scenarios in which the proposed method is useful.
Questions for authors
Q1. Can the authors identify concrete scenarios or use cases in which the proposed method would be useful for analyzing real-world graphs?
4 comments
Follow-up for Reviewer hMXT
Dear Reviewer hMXT,
Our reply covers W1 and Q1. In the revised PDF:
- W1: we agree that real graphs reject the degree null easily. The test now also conditions on degree correlations and triangles (Proposition 2, Table 2). With modularity, this rarely changes the verdict: Leiden stays certified on all 10 graphs, and the four pipelines disagree only on Karate, Dolphins and PolBooks. So Table 2 also reports the share of Leiden's modularity above the degree-null mean that triangle-preserving rewirings reproduce. With mean conductance, Leiden is not certified at the triangle level on 5 of the 10 graphs (Section 5.5).
- Q1: Section 5.5 fits clusters to a window of MathOverflow interactions and tests them on the next window's new pairs. Across one-day, one-week and 30-day windows, fitted modularity is highest on the one-day windows, yet the test rejects least often there. The test can therefore guide how much history to fit before using the clusters to predict new pairs.
If the reply settles your concerns, we would be grateful for an updated assessment. If something remains unclear, please tell us; we can reply until November 18 (AoE).
I appreciate the authors' substantial effort in conducting many additional experiments using real datasets. However, I am still not fully convinced that the paper demonstrates the practical usefulness of the proposed scheme in real-world scenarios.
Reply on practical usefulness
Thank you. We agree that our examples are uses on public data rather than in a deployed system, and that on most real graphs the degree-level verdict alone says little. As your S1 notes, absolute modularity is hard to interpret, so without labels a fitted score cannot tell whether clusters are worth acting on. The clearest real-data case is one practical question asked on three interaction networks: do clusters fitted on a week of interactions predict which new pairs interact in the next seven days (Table 25; Appendix J describes the windows)?
- Leiden's mean fitted modularity is nearly the same on all three networks, 0.687 to 0.693 (Figure 5, dashed lines), so it does not tell them apart.
- The held-out test answers the question week by week: it rejects in 8 of 8 weeks on email, 10 of 12 on MathOverflow and 3 of 12 on college messages. On college messages, held-out modularity averages below its null mean (-0.060 against -0.048), while on MathOverflow it is above it (-0.001 against -0.043). Week size matters too: college's 3 rejections are its 3 largest weeks, and most of its weeks have few new pairs (median 52, against 180 on MathOverflow; Table 25 lists the means, 215 and 207).
- On MathOverflow the same table bears on how much history to fit. The per-pair effect, held-out modularity above its null mean, stays at 0.042 to 0.064 for up to 14 days of history while rejections rise with the number of pairs; at 30 and 60 days it reaches 0.085 and 0.134.
Our other examples (an attribute-driven pipeline on noisy wiring, pipelines whose verdicts differ at the triangle level, and molecules where the test should not be used) are as in our response to your review. The revision posted with these replies opens Section 6 with conclusions, including what the test tells a user without labels.
Response to Reviewer hMXT
Thank you. We agree that real graphs reject the degree null, so a p-value at its floor says little. The first version's Table 1 also tested largest-component graphs, which made the Citeseer floors uninformative (Comment 0, correction 2). Section 5.5 now asks what a certificate says that fitted modularity does not.
Sharper nulls. The test now also conditions on degree correlations and triangles (Proposition 2, Table 2). With modularity, Leiden stays certified at the triangle level on all 10 graphs, at the floor of the p-value on 8, so there the verdict alone is not the output; the effect size is. On the 9 graphs whose level-3 chain replaced at least half the edges, triangle-preserving rewirings reproduce 26 to 90% of the excess modularity, likely too high on the 5 that had not settled. Verdicts differ between pipelines on Karate, Dolphins and PolBooks, and with mean conductance Leiden is not certified at level 3 on 5 of the 10 graphs. As a control, a random graph with triangles and no communities is "certified" by degree-only tests in 1.00 of cases and at the triangle level in 0.00 (0.05 after burn-in).
A decision on real data: when does a partition predict new pairs? Fit on a window of MathOverflow interactions and test the partition on the next window's new pairs. With Leiden the held-out test rejects in 3 of 10 one-day windows and 12 of 12 30-day windows, while fitted modularity falls from 0.87 to 0.54, so fitted modularity is highest where the test finds the least. With the test window fixed at the next seven days, held-out pairs still grow with history (65 to 366). Up to 14 days the per-pair effect, held-out modularity above its null mean, stays at 0.042 to 0.064 while rejections rise with the number of pairs; at 30 and 60 days the effect itself grows, to 0.085 and 0.134 (Table 25). The decision this informs is how much history to fit before trusting the clusters for prediction. The test fixes only degrees, so a rejection can also reflect triadic closure (Appendix J).
Where a certificate should not be used. On molecule benchmarks 0.91 of MUTAG graphs score below their degree-null mean: connected near-trees are not typical graphs with their degrees, so a non-rejection there says nothing about what a pooling layer could find (Appendix J).
Attributes under noisy wiring. After rewiring 0.90 of Amazon Computers' edges, MAGI-lite with native attributes stays certified in 1.00 of replicates and Leiden in 0.00; with SVD features instead of attributes no deep pipeline does (Section 5.5). The test reads only the wiring, so the attributes led MAGI-lite to structure that the unrewired edges keep; the decision is whether to trust an attribute-driven pipeline when the wiring is noisy.