acceptodds
Under review as a conference paper at ICLR 2027

Did Your GNN Find Anything? Exact Certification of Deep Graph Clustering

Abstract

Deep graph clustering pipelines always return a partition. On Erdos-Renyi graphs, whose wiring carries nothing beyond the degree sequence, our DMoN-lite and MAGI-lite reimplementations still return partitions of 16 communities at mean modularity 0.25 (DMoN-lite) and 16 at 0.21 (MAGI-lite). We give an exact, finite-sample certification layer that wraps a trained pipeline and returns a p-value against the null that the wiring carries no structure beyond the degrees. The null is uniform over simple graphs with the observed degree sequence, sampled by a double-edge-swap chain inside the Besag-Clifford parallel construction, and validity holds at any chain length. Carrying that guarantee to trained networks under stochastic and amortized training is what we establish. Training is stochastic, so we give seeding rules under which the score stays exchangeable and the p-value stays exact, and show that the wrapped rule must read the graph rather than the ordering of its edges. A certificate costs M + 1 fits, so we give a hub-conditional warm start that provably preserves exactness, and we show that the natural alternative an implementer would write instead certifies structure in a fraction 1.00 of structureless graphs. Most tests do not reject, so a sequential rule stops the median null test after 19 of 199 fits. Applied recursively, the same test estimates model order, with false splits controlled at level α under an explicit selection-neutrality condition. In the calibration audit's 1800 tests of three deep pipelines at α = 0.05, the wrapper's rejection rate stays between 0.005 and 0.065, the largest cell's Wilson interval [0.038, 0.108] covering α, while a Bickel-Sarkar-style threshold applied outside its stated regime rejects a fraction 1.000 of 200 structureless Erdos-Renyi graphs, every rejection a type-I error under its own null. Significance and recovery come apart: pipelines earn certificates on graphs whose planted partitions they do not recover, so a certificate belongs to a (graph, pipeline, configuration) triple rather than to a graph.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph clustering, exact test, hypothesis testing, model selection, graph neural networks, configuration model, deep graph clustering

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_hMXTOpenReview ↗
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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_1fuEOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers the deep graph clustering and presents an exact finite-sample certification wrapper based on degree-preserving graph rewires, with formal theoretical analysis. Concretely, it computes valid p-values for stochastic trained pipelines, introduces valid warm-start and sequential stopping, and realizes recursive model-order estimation

Critical strengths

S1. This paper provides a series of formal theoretical analysis to support its claims.

Critical weaknesses

W1. The overall presentation of this paper is hard to read (e.g., lengthy abstract with too many unnecessary details, full of LLM-style English, disordered overall organization of contribution statements and theoretical analysis, no toy examples, etc.), which need significant polishing.


W2. There seems no formal definitions about the graph clustering problem considered in this paper.

First, it is unclear whether graph attributes (especially node attributes) is considered. Main results in Table 1 seem to be a mixture of many settings. For instance, DMoN, MinCut, and MAGI are approaches designed for attributed graphs, while Leiden does not consider attributes. The original datasets of Cora, Citeseer, and Amazon Photo also provide node attributes, but there seems no statistics about such attributes (e.g., dimensionality of node attributes).

If this paper also covers the graph clustering (a.k.a. community detection) on attributed graphs, how does it handle the complicated correlations between graph topology and attributes, e.g., some subsets of attributes may be even inconsistent with topology, leading to significantly different clustering results when considering each source alone.

Second, it is also unclear whether the number of clusters (a.k.a. communities) is given or need to be determined by a method. Also in Table 1, Leiden can determine the number of clusters by itself while such a number should be given in advanced for DMoN, MinCut, and MAGI.

The aforementioned unclear settings may result in potential unfair comparison in experiments.


W3. It seems that experiments, which empirically validate the theoretical analysis, were conducted only on very small graphs (e.g., only several thousands of nodes), whereas some methods in Table 1 (e.g., Leiden, DMoN, MAGI, etc.) can be easily scaled up to large-scale graphs (e.g., more than 1 millions nodes from SNAP and OGB). In particular, these methods were designed for community detection on large-scale graphs with high efficiency/scalability but, to some extent, sacrificing the clustering quality. It is suggested to discuss why these scalable methods were used in experiments.


W4. This paper contains some references are with anonymous author lists and without clear publication venues even the arXiv. Such references can also not be searched via Google Scholar. It seem that they were generated by hallucinate LLMs.


W5. It seems that this paper does not anonymously provide its code and data to ensure reproducibility of experiments as some other submissions do.

Questions for authors

See W1-W5.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 1fuE

Thank you for the detailed points.

W1, presentation. The abstract is shorter, and the main text is revised for plain language: shorter sentences with fewer numbers each, terms explained where they first appear, and no slogan-like summaries. The contributions follow the order of Section 4, where each lemma, theorem and proposition is stated before Appendix A proves it, and Figure 1 is a toy example.

W2, problem setting, attributes and K. Section 2 gives formal definitions of the pipeline, the null and the certificate. Table 1 lists each pipeline's inputs: whether it reads attributes, and whether it chooses its number of clusters (Leiden) or receives a budget K_max (the deep pipelines). The budget is part of the pipeline: Section 5.4 runs K_max equal to the reference class count and a fixed default, and without labels it can be tuned on the selection edges, which keeps the held-out test exact (Section 4.3; Appendix J compares budget rules). Table 4 gives each attributed graph's attribute dimension. Attributes are held fixed, so the test asks whether the wiring carries structure given the attributes. When attributes and wiring disagree, the certificate reports on the partition the pipeline returns: on a block model whose attributes carry an unrelated partition, DMoN-lite's partition matches neither source (NMI 0.05 to the wiring labels, 0.04 to the attribute labels) and is certified by the refit test in 0.32 of graphs, against 1.00 for Leiden (Table 19). Our three deep pipelines' losses are defined on the wiring, so none follows the attributes alone. For your example of attributes that only partly disagree with the wiring, we added a block model in which each node's attribute signal is split over eight coordinates, two, four or six of them following its planted group and the rest an independent grouping, 50 graphs per cell. With only two of the eight on the planted group, the two sources alone disagree: k-means on the attributes follows the independent grouping (NMI 1.00) and Leiden on the wiring the planted groups (refit NMI 0.92). The refit test certifies Leiden on every graph and k-means on only 0.02, because the wiring does not support the attribute partition. With four on each, k-means returns one grouping or the other, and both tests certify it on exactly the 28 of 50 graphs where it returns the planted one. DMoN-lite and MAGI-lite, which read both, follow the planted groups in every mix (with no agreeing coordinate DMoN-lite missed them, as above), and both tests certify them on every graph. MinCut-lite's fit often collapses to one part, which is never certified; the refit test certifies it in 0.08 to 0.56 of graphs and the held-out test, whose fits collapse less often, in 0.58 to 1.00. With structureless wiring the largest rejection rate over 30 cells is 0.08, and its Wilson interval covers 0.05. The test does not reconcile the two sources: it asks whether the wiring supports the partition the pipeline returned, whichever source produced it (Table 20). On six attributed real graphs, native attributes and the SVD recipe give the same verdict in all 35 combinations but different partitions (Tables 21 and 22). A certificate compares a pipeline with itself on rewired graphs; Table 3 is our main comparison of K estimators, on one set of block models with budgets fixed in advance.

W3, scale. Table 14 runs both tests on SNAP and OGB graphs on one laptop, the held-out test up to 4.0 million nodes and 61.9 million edges. Every run there rejects except MinCut-lite's held-out run on com-Amazon, which returns one part, so these rows show cost; the held-out test's level at this size is checked on rewired copies of com-DBLP and com-Amazon (Table 8), and SNAP's com-* graphs are released only as largest components, which Appendix E discusses. With DMoN-lite on com-Youtube the refit test takes 1.7 hours against 6 minutes for the held-out test. On why these pipelines: the refit test multiplies the cost of a fit by M+1, so it suits pipelines whose fit is near-linear in the edges, and a weaker pipeline can change power, and the test stays valid (Corollary 1). Our deep pipelines are compact reimplementations, so these runs show the test's cost and say nothing about the published systems' accuracy.

W4, references. The one entry without a venue cited a real but anonymized manuscript, not a hallucinated one; because a reviewer could not check it, it is removed and the paper is self-contained. The paper's AI use statement says how a language model was used. All 76 printed references resolve to a DOI, arXiv record or publisher page.

W5, code and data. Anonymous code, result CSVs and the scripts that regenerate every number, table and figure: the supplementary material of this submission (anon_package.zip). Requirements are pinned, a script fetches the public datasets, and exhaustive enumeration tests of the theory run in under a minute.

AuthorsOpenReview ↗

Follow-up for Reviewer 1fuE

Dear Reviewer 1fuE,

Our reply goes through W1 to W5 in order. In the revision:

  • W1: the main text is revised for plain language, and Figure 1 is a new toy example. The contributions follow the order of Section 4, which states each lemma, theorem and proposition before Appendix A proves it.
  • W2: Section 2 gives formal definitions. Table 1 shows which pipelines read attributes and which choose their own number of clusters, and Table 4 gives the attribute dimensions. Attributes are held fixed, so the test asks whether the wiring supports the partition a pipeline returns; Table 20 covers attributes that partly disagree with the wiring. Each p-value compares a pipeline with itself on rewired graphs, and Table 3, our main comparison of K estimators, fixes each cluster budget in advance.
  • W3: Table 14 runs the refit test and a new held-out test, which fits the pipeline once, on SNAP and OGB graphs of up to 4.0 million nodes. The refit test multiplies the cost of a fit by M+1, so it suits fast pipelines like these.
  • W4: the citation to the anonymized manuscript is removed, and all 76 references in the bibliography resolve to a DOI, arXiv record or publisher page.
  • W5: anonymous code, result CSVs and a script that fetches the public datasets are in the supplementary material.

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

Thanks for the rebuttal. Since my concerns regarding W1 and W2 are not well addressed. I decide to keep my original score.

For instance, the current presentation is sill hard to read, with many lengthy text description without proper paragraphing.

The response to W2 is also hard to read and understand.

The major revisions are not properly highlighted in the newly submitted version.

AuthorsOpenReview ↗

Reply on presentation and W2

Thank you for the reply. You are right that the paper and our answer on W2 are still hard to read. In the final version we will break the long paragraphs into short ones, one point each.

W2 in short.

  • Definitions. Section 2 defines the pipeline, the null hypothesis and the certificate (Definitions 1 to 3).
  • Attributes. Table 1 shows which pipelines read node attributes. Leiden does not. DMoN-lite, MinCut-lite and MAGI-lite use a graph's own attributes when it has them, and otherwise a top-16 SVD of the adjacency matrix, recomputed on each graph. Table 4 gives the attribute dimensions.
  • What the test asks. The attributes are held fixed. The test asks whether the pipeline's partition shows anything in the wiring that the degrees do not explain.
  • Attributes that disagree with the wiring. The pipeline decides which source to follow, and the test asks the same question of the partition it returns. Section 5.4 tests this. In Table 19 the attributes follow the planted groups, an unrelated partition, or only noise. In Table 20 some attribute coordinates follow the planted groups and the rest follow an unrelated partition.
  • Number of clusters. Leiden chooses its own. Each deep pipeline is given a maximum number of clusters, fixed in advance as part of the pipeline; DMoN-lite and MinCut-lite may use fewer (Table 1, Section 5.4).
  • Fairness. No p-value ranks one pipeline against another: each compares a pipeline with itself on rewired copies of the same graph. Table 3 does compare estimators of the number of clusters, with each maximum fixed in advance, and Table 15 gives all three deep pipelines the same maximum, 4.

Where the major revisions are. Most of the main text was rewritten, so we did not mark individual changes in color. Appendix M, on the last page, lists the changes against the first version. The main ones are:

  1. Formal definitions and a toy example (Section 2, Figure 1).
  2. A held-out test, which fits the pipeline once on part of the edges and checks its partition on the other edges (Section 4.3, Theorem 1). It runs on graphs of up to 4.0 million nodes (Table 14).
  3. The number of clusters from recursive held-out tests (Theorem 2, Table 3).
  4. Null models that also keep degree correlations and, within a bin, the number of triangles (Section 4.5, Table 2).
  5. Uses on real data (Section 5.5) and conclusions (Section 6).
Reviewer_aXgFOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper addresses the question of whether partitions reported by deep graph clustering capture structure beyond what can be explained by the degree sequence alone. It proposes an exact finite-degree conditional test for the uniform null hypothesis on the observed degree sequence under the Besag–Clifford parallel construction: a rank p-value valid for any chain length. It also discusses how random training seeding, representation invariance, hub warm-starting, and sequential stopping preserve this exactness. The authors validate the effectiveness of the method on synthetic and real-world datasets.

Critical strengths

The framework achieves exact Type I error control under finite samples, does not rely on any asymptotic assumptions or require Markov chain convergence, and is one of the few methods currently capable of providing rigorous statistical guarantees for deep graph clustering outputs.

Critical weaknesses

The writing of the paper is rather difficult to follow. Many terms appear uncommon in this field, and the information density is high. It takes me some time to grasp the author’s points, and at times I cannot fully understand them. The author frequently refers to an anonymous paper that is not publicly available (at least it cannot be found on Google), so I am unable to verify whether the author’s arguments are valid. A single structural certification requires M+1 full model training runs, and the overhead for recursive model order estimation is even higher. The recursive order estimation was only validated on the classic Leiden algorithm and has not been implemented with a deep clustering pipeline.

Questions for authors
  1. Recursive model order estimation relies on the selection neutrality assumption. Under what scenarios would this assumption be violated? Do common deep clustering pipelines inherently break this assumption?

  2. The scoring function currently uses modularity by default. If replaced with other clustering quality metrics such as normalized cut and conductance, how would the power and calibration of the test change?

  3. Can this exchangeability-based exact certification framework be extended to significance testing for other graph learning tasks such as graph classification and node classification?

  4. Is it possible to support sequential control of higher-order statistics (e.g., degree-degree correlation and average local clustering coefficient) to achieve finer-grained structural certification?

5 comments
AuthorsOpenReview ↗

Response to Reviewer aXgF (1/2)

Thank you for the careful reading and the four questions, which we answer in the next comment.

Readability and density. Section 2 now defines the pipeline, the null and the certificate; terms such as hub, level, certified and NMI are defined where they first appear; Figure 1 is a toy example and Figure 2 shows both tests side by side. Secondary studies moved to the appendix. The main text grew by the one page the revision allows, to hold the results the reviews asked for.

The anonymous reference. The first version cited an anonymized concurrent manuscript and credited it with the wrapper for a rule run at one fixed seed, with the recursion, its level allocation and its false-split guarantee, with several first-version findings (the asymptotic baseline, the recovery gap for Leiden, the real-graph Leiden results) and with the design of the model-order accuracy study. The citation is removed. The paper now states and proves these parts itself, does not claim them as contributions, as before, and credits the classical precedents (Section 3).

Cost of M+1 fits. The held-out test (Theorem 1, Section 4.3) fits the pipeline once on a random 80% of the edges and scores the fixed partition on the rest against rewirings that avoid the fitted edges; it is exact for any pipeline trained only on the 80%. It certifies that partition, not the one fitted on the whole graph (Table 24 reports their agreement), and its p-value varies with the split, so the attributed and small real-graph tables combine several splits (Tables 21 to 23), while most large-graph runs in Table 14 use one. Level holds: over 24 cells the rejection rate at alpha = 0.05 is 0.000 to 0.080, the largest cell's Wilson interval [0.041, 0.150] covering 0.05. Near the detection threshold on assortative blocks it tends to have less power than the refit test, and on disassortative pairs its log-likelihood statistic can have more (Figure 3). At scale the saving is large: with DMoN-lite on com-Youtube (released as its largest component) the refit test takes 1.7 hours and the held-out test 6 minutes (Table 14).

Model order with a deep pipeline. Table 3 now has deep splitters. The held-out recursion with DMoN-lite (budget 16) matches the planted K on 0.73 of assortative graphs, and needs 1.1 to 4.5 fits per graph across splitters, against thousands for the refit recursion. We ran the refit recursion with one deep splitter, DMoN-lite (budget 4), on the blocks with c >= 5: it matches K on 0.89 of assortative graphs at 7,218 fits and 1,009 seconds per assortative graph, the held-out recursion on 0.84. The Bethe-Hessian count is as accurate on assortative blocks with no fits (0.80 over all contrasts, against 0.78 for the refit recursion with Leiden); the held-out recursion adds a false-split guarantee (Theorem 2), while the refit recursion with these splitters carries only the root test's. No splitter we tried recovers disassortative pairs reliably beyond two blocks.

AuthorsOpenReview ↗

Response to Reviewer aXgF (2/2)

Q1, selection neutrality. Proposition 1 states it precisely: whether a vertex set is a maximal truly structureless node of the fully expanded tree must not depend on the wiring inside it. Hierarchies fixed in advance or built from attributes alone satisfy it. A splitter that reads that wiring, Leiden or a trained network, in general does not, so every refit-recursion result in the paper carries only the root test's guarantee. Do deep pipelines break it inherently? We measured what selection costs (Appendix I): it depends on the graph. On ER graphs, the parts any splitter selects are not rejected detectably more often than fresh graphs with the same degrees (a bootstrap over graphs). At power-law exponent 2.5 only DMoN-lite's parts are rejected detectably more often (0.113 to 0.122, fresh graphs at most 0.051), and at exponent 2.1 every splitter's are: 0.120 to 0.288 with a Leiden child test, Leiden's own parts 0.281, fresh graphs at most 0.047 (Table 17). The held-out recursion needs no such condition (Theorem 2): its false splits stay at or below 0.033 on structureless graphs and at most 0.010 inside planted blocks, pooled over K and c, for the two splitters run there, Leiden and DMoN-lite (Table 18).

Q2, other scores. Validity cannot change, since Lemma 2 holds for any score. Table 11 is consistent with it: pooled over settings and pipelines, structureless graphs are rejected at 0.042 with modularity, 0.053 with mean conductance and 0.053 with normalized cut, each pooled Wilson interval covering 0.05; per pipeline the rates run from 0.013 to 0.087. The largest, MAGI-lite with either cut score (both reject the same graphs), has Wilson [0.051, 0.143], just above 0.05; these are the only 2 of the 12 per-pipeline intervals above it. Power does change. Averaged over pipelines and contrasts, modularity rejects 0.51 of assortative block models and 0.39 of disassortative pairs, against 0.43 and 0.30 for mean conductance and for normalized cut, and switching from modularity gains at most 0.10 in any cell. The two cut scores favor partitions with fewer parts, so MinCut-lite, which returns one part on almost every rewired block model, has no power with them. Without MinCut-lite the cut scores lose 0.02 of power on assortative and 0.04 on disassortative blocks.

Q3, other tasks. Yes. Appendix K gives exact tests for node and graph classification by retraining on rewired graphs. With a GCN retrained on degree-preserving rewirings, attributes and labels fixed, accuracy on the observed wiring is significantly higher for Cora, Citeseer, PubMed, Amazon Photo and Coauthor-CS and not for Texas, Wisconsin, Cornell and Actor, where an MLP that ignores the edges is more accurate. For graph classification with a GIN, accuracy on the observed graphs is significantly higher than on rewired datasets for NCI1 only, among the six benchmarks. The one significant graph-classification p-value (NCI1) sits at the smallest value the design allows, and the degree null describes molecules poorly (Appendix J), so those rows illustrate the construction.

Q4, higher-order statistics. Yes. The test runs unchanged on any fiber whose swap kernel is symmetric, and we add nulls that also fix the joint degree matrix and a bin of the triangle count, tested in a fixed sequence with family-wise error at most alpha (Proposition 2). With the average local clustering coefficient you mention as the level-3 statistic, Leiden stays certified on all 6 graphs we ran it on (Appendix C). 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 on its fiber). On real graphs the triangle level did not change Leiden's modularity verdict (Table 2); it separated pipelines on the graphs of up to 105 vertices, and with mean conductance Leiden is not certified at level 3 on 5 of 10 graphs.

AuthorsOpenReview ↗

Follow-up for Reviewer aXgF

Dear Reviewer aXgF,

Our first reply (1/2) covers the weaknesses you list, and the second (2/2) answers your four questions with new results. In the revised PDF:

  • The main text is rewritten for clarity, with definitions in Section 2 and a toy example in Figure 1.
  • The citation to the anonymized manuscript is removed. The paper is self-contained: it proves the guarantees it had credited to that manuscript (Lemma 2, Proposition 1) and reports the credited findings from its own runs.
  • A held-out test fits the pipeline once instead of M+1 times and stays exact (Theorem 1).
  • Run recursively, the held-out test estimates the number of clusters with deep pipelines in a few fits per graph and needs no selection-neutrality condition (Theorem 2, Table 3).

If the replies settle your concerns, we would be grateful for an updated assessment. If something remains unclear, please tell us; we can reply until November 18 (AoE).

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers. Two of them found the presentation hard to follow, so the main text is rewritten for clarity. The paper's question, its degree null and its refit test are those of the first version; the held-out test and the nulls beyond degrees are added. Appendix M lists the changes.

Unchanged, with the same numbers: the exchangeability and score lemmas (Lemmas 1 and 2) and their corollaries; the calibration audit (Appendix D); the asymptotic baseline (Appendix F); power and recovery (Appendix G); warm starts and seeding (Appendix H); stopping (Appendix H); and the refit recursion's accuracy and false splits (Table 3, refit Leiden row).

Added, each answering a review point:

  • A problem definition with formal definitions, each pipeline's inputs and a toy example (Section 2, Table 1, Figure 1): 1fuE-W1, W2.
  • A held-out test that trains the pipeline once and stays exact (Theorem 1): aXgF on the cost of M+1 fits. It runs on SNAP and OGB graphs up to 4.0 million nodes (Table 14): 1fuE-W3.
  • A held-out recursion for model order with deep splitters and no selection-neutrality condition (Theorem 2), the refit recursion run with DMoN-lite (Table 3), and a measurement of selection neutrality (Appendix I): aXgF on Leiden-only model order and Q1.
  • Nulls that also fix degree correlations and triangles, tested in sequence (Proposition 2, Table 2): hMXT-W1 and aXgF-Q4.
  • Uses on real data (Section 5.5): hMXT-Q1. Other scores (Table 11): aXgF-Q2. Node and graph classification (Appendix K): aXgF-Q3. Attributes and the cluster budget (Section 5.4) and attributes that partly disagree with the wiring (Table 20): 1fuE-W2.

Corrected, found by an audit of our code and proofs that we ran with the model named in the AI use statement: (1) a loader bug placed Planetoid test-node labels and attributes with the wrong permutation, so the first version's Cora and Citeseer NMI values and its Cora native-attribute runs were wrong; (2) reducing real graphs to their largest component conditions on connectivity: structureless graphs with Citeseer's degrees, reduced this way, are rejected by the refit test 1.00 of the time, so the first version's Citeseer certificates were not evidence (graphs are now tested whole; PubMed and Coauthor-CS are connected as released, so their refit tests keep this caveat, which Appendix E sizes for PubMed); (3) we had said hierarchies fixed in advance satisfy our selection-neutrality condition; as worded they did not, because whether a node is tested depends on its ancestors' verdicts, so Proposition 1 now states it through membership in the fully expanded tree, which such hierarchies satisfy; (4) the refit recursion seeded nodes by creation order, which the proof does not cover; (5), the removed citation, is covered under References and code below; (6) small-graph SVD features came from a solver with its own random restarts, so they were not a function of the graph, and the small-graph rows are rerun; (7) we had said three pipelines reject disassortative pairs by merging each pair, but they return many more parts than blocks; (8) a truly structureless set is now defined given the edges outside it and the attributes. None of these changes a measured false-split or calibration rate.

Removed for length: the items Appendix M lists, including the chain-length ablation of hub warm starts. Their code and results are in the code package, and the first version on OpenReview keeps their text.

References and code. The citation to an anonymized concurrent manuscript is removed and the paper is self-contained; as in the first version, the parts credited to it are not claimed as contributions (aXgF; 1fuE-W4). All 76 printed references resolve to a DOI, arXiv record or publisher page. Anonymous code, the result CSVs and the scripts that regenerate every number, table and figure: the supplementary material of this submission (anon_package.zip).

AuthorsOpenReview ↗

Summary for the area chair

We thank the reviewers for the discussion. Where each remaining point stands:

  • aXgF (Figure 1 and conclusions). The left graph of Figure 1 is an Erdős-Rényi graph, not a rewired one. The figure's point is that raw scores of different graphs cannot be compared, so the test compares each graph only with its own rewirings. The Nov 18 revision states this in Section 1, relabels Figure 1, and opens Section 6 with conclusions.
  • hMXT (practical use). On three interaction networks whose Leiden partitions have nearly the same mean fitted modularity (0.687 to 0.693), the held-out test asks whether the clusters predict the next week's new pairs, and it answers differently: it rejects in 8 of 8 weeks on email, 10 of 12 on MathOverflow and 3 of 12 on college messages (Figure 5, Table 25).
  • 1fuE (presentation and W2). We agree that the text is dense and will split the long paragraphs in the final version. Our reply restates W2 in short form, and Appendix M lists the changes against the first version.

The Nov 18 revision changes text and figure labels only. Every result in the paper and in our replies is generated from the result files in the supplementary material.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.