- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies group detection: identifying sets of nodes whose collective structure is of interest, rather than classifying individual nodes or labeling a supplied list of candidate subgraphs. The proposed approach learns a graph-coarsening geometry from example groups so that previously unseen groups become individual supernodes.
The framework has three parts. First, the paper defines two properties of a target subspace: capture, which measures how well it preserves the contrast between a group and its surroundings, and confusability, which measures how much it preserves distinctions within the group. Second, it learns a target subspace using a bank of linear Chebyshev graph filters. The experiments fit these filters through a channel-pooled quadratic surrogate with a generalized eigenvalue solution. Third, an adjacency-constrained, screened version of Ward clustering constructs a hierarchy of connected supernodes. The theoretical analysis connects the subspace properties to coarsening distortion and gives a sufficient score-gap condition under which a target group appears in the hierarchy.
Experiments cover planted synthetic groups, label-derived illicit-wallet groups in Elliptic++, and several community-recovery benchmarks. The strongest results are on Amazon and on temporal transfer in Elliptic++. Results on the additional community benchmarks are more mixed.
My overall impression is that there is a worthwhile idea here, supported by mathematical development. However, the experiments do not yet establish the full group-detection claim, and the scalability of the actual coarsening algorithm needs much clearer evidence. There are also reporting inconsistencies that should be resolved before the numerical results can be assessed confidently.
Critical strengths
The main strengths, for me, are:
-
Problem formulation. The paper makes a clear distinction between flagging individual nodes and recovering the groups they form. Learning a coarsening geometry from example groups is an interesting way to address that gap without requiring candidate subgraphs upfront.
-
Theoretical framework. Capture and confusability give useful interpretations of two competing requirements: keeping a group separate from its surroundings while allowing its members to merge. The analysis also explicitly handles the mismatch between Euclidean block averaging and screened projection, rather than overlooking it.
-
A learned component. The Chebyshev filter bank has relatively few parameters, and the pooled training surrogate admits a generalized eigenvalue solution. Applying the same filters to new graphs is an appealing design, even though the scalability of the subsequent coarsening stage needs clarification.
-
Some meaningful experimental choices. The temporal evaluation on Elliptic++ is valuable, and the authors take care to remove obvious temporal cues. Deduplicating Amazon communities before splitting is another important precaution. The appendix also acknowledges the proxy nature of the illicit groups and reports less favorable results on DBLP, which helps make the evaluation more transparent.
Critical weaknesses
The most important weaknesses, in my view, are:
-
The evaluation does not fully establish detection. Most metrics ask whether each ground-truth group has a good match somewhere in the output partition. They do not measure how many returned blocks are irrelevant. This is a significant gap for a method motivated by detecting rare suspicious groups.
-
Scalability of the full method is insufficiently documented. Sparse Chebyshev filtering is efficient, but the actual algorithm uses global, partition-dependent deflated Ward scores. The paper does not adequately explain how these are updated at scale or provide runtime and memory measurements.
-
The comparisons do not isolate the contribution. Louvain does not receive the training-group supervision available to the proposed method. On Elliptic++, both the classifier and the grouping procedure change, making it difficult to attribute the improvement specifically to coarsening.
-
The theory is not tightly connected to the implemented learning procedure. The experiments optimize a surrogate without a general approximation guarantee to the exact objective. The recovery theorem establishes that a group appears somewhere in the hierarchy, not that the selected cut recovers it. Neither the certificate’s practical tightness nor the surrogate’s effect on capture and confusability is demonstrated sufficiently.
-
The claimed structural scope exceeds the evidence. The experiments mainly study planted groups with varying internal density and conventional communities. They do not clearly establish performance on disassortative structures. Separately, restricting outputs to connected blocks excludes targets whose members connect only through outside nodes.
-
Reporting inconsistencies reduce confidence. The incompatible precision, recall, and F1 values in Appendix E.3 need correction, alongside conflicting descriptions of feature dimensions and detection thresholds. These may be editorial errors, but they affect reproducibility and interpretation.
Questions for authors
-
Which output blocks are actually reported as target groups? Beyond matching each ground-truth group to its best block, can you report detection precision and recall that account for irrelevant predictions?
-
How are the exact deflated Ward scores computed on the large graphs? Please clarify whether the experiments implement Equation 17 exactly, how scores are updated after a merge, and the runtime and peak memory of the full pipeline.
-
How much of the improvement comes from coarsening itself? On Elliptic++, could you compare connected components and learned coarsening using identical node predictions? For community recovery, how does the method compare with baselines that also receive example communities?
-
Does the pooled surrogate improve the quantities used in the theory? Can you measure capture, confusability, and the exact edge objective before and after training, and compare against direct optimization on smaller graphs?
-
How informative is the recovery certificate in practice? What fraction of target groups satisfy U_S<L_S? Also, what additional conditions would ensure recovery at the selected global cut, rather than appearance somewhere in the hierarchy?
-
What happens on disassortative or heterophilous structures? Could you evaluate connected targets that are not internally dense and distinguish this setting from disconnected targets, which the connected-block restriction cannot recover?
-
Does Elliptic++ inference depend on knowing which test wallets have labels? The appendix describes majority voting over known-label members. Please clarify whether label availability affects predictions or only evaluation, and how unknown wallets influence the reported group purity.
-
Can you reconcile the reporting inconsistencies? In particular, Appendix E.3 reports macro F1 of 0.911 alongside mean precision of 0.79 and recall of 0.89, which are incompatible under the stated averaging. Please also resolve the differing feature dimensions and detection thresholds.
7 comments
W2 & Q2
Implementation. We revised Algorithm 2 and expanded Appendix D.1. Each Ward round merges only two supernodes, so the deflated Ward scores can be updated incrementally instead of being recomputed: after a merge, only the pairs that involve the new block and its neighbors are re-scored, and the rank-one projector update (Lemma 20) keeps each update cheap. The implementation never forms an matrix, and with these incremental updates, our method scales near-linearly in practice. The implementation proceeds as follows.
- Per-block state. Each block stores its volume, cut weight, neighbor weights, and two -vectors, and , where is an -orthonormal basis of the target. A merge combines them linearly, in time.
- Closed-form coarse geometry. The block Gram matrix equals the volume-normalized coarse Laplacian plus , so it is read directly from the block adjacency.
- Local deflation. The deflated score of a candidate merge needs one small solve with this matrix, supported on the two blocks and their coarse neighbors. Screening keeps it well conditioned, so we solve on a 2-hop ball capped at 32 blocks.
- Rank-one update. After a merge, the block projector changes by a rank-one term (Lemma 20), so the target-residual matrix is updated in and the cumulative score is read off without global recomputation.
- Lazy priority queue. Only pairs involving the new block are rescored (at most 32 new queue entries per merge), and other entries keep their keys, which lower-bound their deflated scores. The search stops as soon as the best evaluated score is below the smallest remaining key.
Cost. The cost per merge is , where is the number of rescored candidates, the local ball size, and the degree sum of the merged blocks. Together with the queue operations, this gives the near-linear runtime bound of Eq. (129), which holds when , the average rescoring count, and the average coarse degree stay bounded.
Runtime. We also document the runtime in Appendix E.8, which gives the complexity analysis of the deflated Ward coarsening (Eq. 129) and the runtime and peak memory of every experiment (Table 9).
In these measurements, the global-cut pipeline takes 10.5 min with 3.11 GB on full SNAP Amazon (334,863 nodes) and 14.5 min with 3.71 GB on full SNAP DBLP (317,080 nodes). The eight synthetic graphs take 56.1,s with 0.57 GB, and the 15 Elliptic++ days take 32.6 min with 5.70 GB. On 10K--100K-node subgraphs, coarsening time scales approximately linearly (log--log slope 1.07). All of our experiments run on a single laptop CPU (Apple M2 Pro, 16 GB), with no GPU.
W3 & Q3
Thank you for this point. We agree that the contribution should be isolated, and the updated paper adds new experiments for exactly this purpose (Appendices E.6--E.10). Each one holds everything fixed except the component under test. We describe them below, in the order of the two concerns.
(1) Louvain does not use the training groups. In Appendix E.6 (Tables 5--6) we added ProCom, CLARE, and SEAL, which are trained on the same 100 training communities as our method and are evaluated with the same matching rule. Louvain is kept only as an unsupervised reference. With the same supervision, our learned cut reaches AP 0.810 on Amazon, 0.376 on DBLP, and 0.465 on LiveJournal, versus at most 0.500, 0.211, and 0.289 for these three baselines.
(2) Isolating the learned target. In Appendix E.9 (Tables 10--11, Figure 9), which is new, we keep the training groups, the Ward coarsening, and the cut rule fixed and change only the target subspace. We compare our learned target with resolvent powers, a low-pass bank, and a random bank.
- On the synthetic graphs, F1 is 0.738 for the learned target versus 0.362 for the best fixed target, and the detection rate is 75.6% versus 3.3%.
- On Amazon, F1 is 0.875 versus 0.857 and the detection rate is 96.4% versus 93.2%.
- Table 11 shows that this gain comes from the quantities our theory identifies. On the test groups, capture is 0.0528 for the learned target versus 0.0248 and 0.0189 for the fixed banks, and mean confusability is 0.0065 versus 0.0328 and 0.0462.
The same conclusion holds against the static spectral target in Appendix E.2 of the submission (F1 0.832 versus 0.376 at density 0.5; detection rate 0.911 versus 0.250). In Appendix E.10 (new), our closed-form target matches Adam training from its initialization on Amazon (F1 0.875 versus 0.874) and is better on the synthetic graphs (0.738 versus 0.616).
W3 & Q3 (Continue)
(3) Isolating the cut rule. In Appendix E.5 of the submission, we replace our learned cut with an oracle cut that knows the true group boundaries. Our method detects 699 versus 701 groups on Amazon and 1,410 versus 1,418 on DBLP, so the learned cut recovers nearly all that the learned target makes recoverable. The gains therefore come from the target, not from the cut.
(4) Elliptic++: separating the classifier from the grouping. In Appendix E.7 (Table 7, new) we compare against two controls.
- GNN + connected components predicts illicit nodes and forms groups from connected components. It changes only the grouping step.
- Ward + GCN applies the same Ward clustering to supervised GCN features. It changes only the target.
Our method is best against both. B$^3$ F1 is 0.416 versus 0.204 and 0.320, and matched-group F1 is 0.206 versus 0.098 and 0.129. It also returns 197 groups versus 3,950 for GNN + connected components, so the flagged groups are far more selective. The other group-level baselines on Elliptic++ (RevClassify and ProCom) reach matched-group F1 of 0.048 and 0.076.
W4 & Q4
The theory is tightly connected to the implemented procedure, in three ways.
- The recovery analysis applies to the surrogate's target. The recovery analysis holds for any target subspace , including the subspace produced by the pooled surrogate, and does not require that optimize Eq.~(16). The question is how effectively surrogate training produces high capture and low confusability, and the surrogate response controls both directly. Write
Let and be the smallest positive and largest eigenvalues of , and define the surrogate response energy of a graph signal as . The exact retained energy is , so
\le \lVert Q^\tau_{\mathcal R_\Theta}x\rVert_{M_\tau}^2 \le \frac{E_{\mathrm{sur}}(x)}{a_\Theta}$$ Applying this to the normalized complete-group direction $\widehat v_S$, and to the internal fluctuations through $\chi_{\mathrm{sur}}(S)=\max_{w\in\widehat F_S^\tau}E_{\mathrm{sur}}(w)$, gives\frac{E_{\mathrm{sur}}(\widehat v_S)}{b_\Theta} \le C^\tau_{\mathcal R_\Theta}(S) \le \frac{E_{\mathrm{sur}}(\widehat v_S)}{a_\Theta}, \qquad \frac{\chi_{\mathrm{sur}}(S)}{b_\Theta} \le \chi^\tau_{\mathcal R_\Theta}(S) \le \frac{\chi_{\mathrm{sur}}(S)}{a_\Theta}.
Thus, surrogate response energies control the exact capture and confusability through the conditioning of the joint screened Gram matrix. The surrogate objective acts on these energies through boundary and internal edge contrasts. Its internal penalty suppresses the variation of $\ell_\Theta^{\mathrm{sur}}=\widetilde D^{-1/2}M_\tau F_\Theta$ along internal edges, and for a connected group a zero internal penalty makes this response constant on the group, which implies zero exact confusability. The boundary term encourages separation from neighboring nodes. - **Training improves exactly the quantities in the theory.** In Appendix E.10, the closed-form solution attains 90.1\% (synthetic) and 87.8\% (Amazon) of the best exact objective found by Adam through the full Gram whitening, at 0.5 s versus 280 s and 4.4 s versus 463 s. Further exact-objective refinement does not improve recovery: initialized from the closed form, Adam gives group F1 of 0.616 versus 0.738 on synthetic graphs and 0.874 versus 0.875 on Amazon. In Appendix E.9 (Table 11), training raises test capture from 0.019 to 0.053 on synthetic graphs and from 0.008 to 0.071 on Amazon, compared with untrained random filters, and lowers mean confusability on synthetic graphs from 0.046 to 0.0065 and median confusability on Amazon from 0.0157 to 0.0014. - **The selected cut recovers groups.** We designed three cut rules on the same hierarchy: a global cut, a learned cut, and a nested cut for overlapping groups, and compare them in Appendix E.6. The learned cut improves group F1 over the global cut in all six settings, for example from 0.865 to 0.902 on Amazon, from 0.696 to 0.716 on DBLP, and from 0.739 to 0.746 on LiveJournal with 100 training communities, and the nested cut raises it further to 0.923, 0.741, and 0.763. The training-selected cut also loses little to the oracle cut chosen with test labels (Appendices E.2 and E.5): at density 0.5, group F1 is 0.832 versus 0.852, and on held-out Amazon communities it detects 699 of 759 versus 701 with the oracle cut. On DBLP, it detects 1,410 versus 1,418 of 2,500. All 759 held-out Amazon communities appear as blocks at some level of the learned hierarchy.
We thank the reviewer for the valuable and constructive feedback. In response, we substantially expanded the empirical evaluation (Appendices E.6--E.11): comparisons with learned baselines on community and Elliptic++ benchmarks, an overlapping-group cut, runtime and memory measurements, ablations of the learned target, and measurements connecting our results to the theoretical guarantees. These new results further demonstrate the performance of our method and connect to the empirical findings to our theory. Our point-by-point responses follow. All references to figures, appendices, etc., refer to the updated version of the paper.
Setting and benchmarks. Learning to detect groups from labeled example groups and transferring to unseen graphs is a new problem setting, and to our knowledge there are very few dedicated methods and no established benchmarks for it. The closest existing methods come from community detection and search (ProCom, CLARE, SEAL) and from financial group detection (RevTrack), and we compare against all of them. Because no ready-made benchmark exists, we construct our evaluation from the strongest available sources: the community benchmarks used by ProCom (Amazon, DBLP, LiveJournal) with fixed train/test community splits, Elliptic++ with held-out time steps, and synthetic graphs where the ground-truth groups and their shapes and sizes are controlled.
W1& Q1
Our evaluation penalizes irrelevant output, and our method returns far fewer and more precise groups than the baselines. We added ranked and one-to-one metrics in which every unmatched output counts as a false positive, in addition to the best-match recovery metrics. Our method scores clearly higher on them (Appendices E.4, E.6, and E.7).
How the reported groups are selected. The learned spectral geometry makes target groups merge at low cost, and explicit selection rules that use only the training groups then separate them from background blocks. On the community benchmarks, the learned cut scores every block of the coarsening hierarchy with a quality model trained on the training communities, using the block's size, graph structure, and merge history. It selects the blocks that maximize predicted quality net of a per-group penalty, discards singletons, and ranks the output by this score (Appendix E.6). This requires no node-level class labels. On Elliptic++, we additionally learn a node classifier on the wallet features and the learned screened responses, and flag a supernode as illicit when most of its members are predicted illicit (Appendix E.4).
Metrics that penalize irrelevant blocks. We report detection precision, the fraction of reported groups that match a test group, and detection recall, the fraction of test groups that are matched, under a one-to-one matching (more than 51% overlap in both directions), so that every unmatched output is a false positive. Every unmatched prediction, including a second detection of an already matched group, counts against precision. On the community benchmarks, we rank each method's output by confidence and report average precision (AP) and P@∣T∣, the fraction of hits among the top ∣T∣ predictions, where ∣T∣ is the number of test communities (Appendix E.6, Tables 5--6). On Elliptic++, we report matched-group precision and F1 under the same one-to-one rule (Appendices E.4 and E.7).
Results. With 100 training communities, our learned cut reaches AP 0.810 on Amazon, 0.376 on DBLP, and 0.465 on LiveJournal, versus at most 0.500, 0.211, and 0.289 for ProCom, CLARE, and SEAL, and it also has higher P@∣T∣ on all three datasets. On Amazon, it returns 1,147 groups, compared with 5,000 for ProCom. On Elliptic++, our method returns 197 groups on the held-out days, compared with 3,950 for GNN + connected components. Its matched-group precision is 0.266 versus 0.061, and it obtains the highest matched-group F1 (0.206, versus at most 0.098 for ProCom, CLARE, SEAL, RevClassify, and GNN + connected components). RevClassify returns a list of similar size (about 195 groups) but matches only 5 gangs on average, versus 29 for our method (Table 7).