- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper addresses seedless matching of two correlated Erdős–Rényi graphs on the same vertex set, building on degree-profile (DP) matching (Ding et al., 2021), which computes an n×n matrix of distances between vertex degree profiles, sorts it, and declares a matching when the n smallest entries form a permutation, otherwise refining with an iterative linear-assignment clean-up. LiDP has two stages. (1) Selective computation: distances are computed in increasing order of degree difference, and as soon as the n smallest computed entries form a permutation, a certificate checks that the largest selected entry is the minimum of its row and column; Theorems 1–2 show that, when the full matrix's n smallest entries form a permutation, the certified set equals the full-computation set. Empirically 3–5% of entries are computed, giving 10–21× speedups over DP on ER graphs (up to 35× for dense graphs, 20× for bin-distance matching). (2) When certification fails, the distances warm-start a Frank–Wolfe procedure on the doubly stochastic relaxation with an exact line search (Algorithm 2); Theorem 3 states convergence to first-order stationary points, and Theorem 4 shows that under a global separation condition (9), any stationary point whose objective gap to the ground truth is below c_n²/2 is the ground truth, with Corollary 1 instantiating the constant for ER graphs. Experiments on ER graphs (n up to 10⁴), Slashdot, and yeast PPI compare runtime and accuracy against DP/DP+ and, on yeast PPI, twelve other methods.
Critical strengths
- Selective computation with a cheap certificate is a simple and practically effective idea: it preserves DP's exact-recovery behaviour in the perfect-matching regime while computing only 3–5% of the distance matrix (Table 2), and the resulting 10–35× speedups (Figure 3, Tables 4–5) are large, consistent across sizes and densities, and transfer to a second distance (bin-distance). The certificate logic (Theorems 1–2) is correct under its assumption.
- The paper is clearly written, the algorithms are fully specified, the line search in the released code matches Eq. (33), and the yeast PPI comparison (Table 3) places LiDP at the accuracy of the best methods with the lowest runtime.
Critical weaknesses
- The exact-recovery theory is conditional and is presented as a guarantee. Theorem 4 assumes the global separation condition (9), which must hold simultaneously for all pairs of permutations with a linear margin, and Corollary 1 for correlated ER graphs supposes condition (40) rather than proving that it holds with high probability for some range of (n, q, s). Nothing in the paper shows that Algorithm 2 reaches a stationary point within the required gap c_n²/2 of the optimum; Theorem 3 only yields stationarity, and its proof is delegated to properties in another paper. The abstract's "first such guarantee for near-optimal stationary points" therefore describes a conditional statement about stationary points, not a recovery guarantee for the algorithm. Relatedly, the complexity claim O((n²+nd²) log n) → O(n²+nd²) attributes DP's cost to sorting, whereas the actual saving is the empirical fraction of distances computed; in the worst case Stage 1 computes every entry and re-sorts a growing candidate pool at each degree-difference level (
match_fast4.m), so no worst-case improvement is established. - Stage 2 is Frank–Wolfe with exact line search, i.e. the FAQ algorithm warm-started from DP distances, and the empirical comparison does not isolate the contribution. Equations (6)–(8) and the code contain no momentum term, so "momentum-adaptive" is a misnomer; the only change relative to DP+'s clean-up is replacing the fixed step α = 1 by the exact line search that FAQ already uses. Figure 4 compares step-size schedules of the authors' own procedure (α = 1 being DP+), with modest differences near the noise threshold and no error bars; on yeast PPI the gain over DP+ is 0.2 pp (Table 3). FAQ appears in Table 3 only with its own initialization. Moreover, the released code departs from the paper on this path: Section 4.3 states that after certification fails the remaining distances are computed to complete the matrix, but
match_fast4.mfills the uncomputed entries by a linear fit in degree difference (linear_fitting) and has no 20% cap, andER_test.mruns a single trial per noise level (ind_run = 1) with 10 clean-up iterations. The number of runs is not stated anywhere, and the DP baseline is not in the supplement, so the high-noise results and speedups cannot be verified as reported.
Questions for authors
Clarifications that could change my assessment:
- Can condition (40) be shown to hold with high probability for correlated ER graphs, and for which (n, q, s)? Can Algorithm 2 be shown to reach the gap c_n²/2 required by Theorem 4? If not, please restate Corollary 1 and the abstract as conditional results.
- Please state the relation of Algorithm 2 to FAQ (Frank–Wolfe with exact line search) explicitly, clarify where "momentum" enters, and report FAQ warm-started with the same DP distances alongside DP+.
- Which procedure produced the high-noise results: computing the remaining distances (Section 4.3) or the linear-fit estimate in the released code? How many independent runs underlie each point of Figures 3–4 and Table 3, and can error bars be added?
- Outside the perfect-matching regime, the certificate can pass for a wrong permutation (Theorem 2 does not cover this case, and ties pass the strict check). How often does this occur in the experiments, and with what accuracy?
Suggestion (not affecting the score): Theorem 1 is an elementary observation and could be stated as a lemma; a table of the values behind Figure 4 would make the step-size comparison readable.
3 comments
Response to Reviewer m3Qn (Part 2
Q3. Procedure and error bars
It is generally assumed that if an early exit is possible, the number of computed entries is less than . Accordingly, in our implementation, once the number of computed entries exceeds , we exit immediately and compute the full . In addition, we added five separate runs in the actual tests; runtimes and paired speedups are reported as mean ± sample standard deviation.
Figure 3(a): ER graph runtime and speedup ()
| Noise | DP time (s) | LiDP time (s) | Speedup (×) | LiDP early-certification count / total runs |
|---|---|---|---|---|
| 0.0000 | 117.567 ± 0.820 | 7.845 ± 0.176 | 14.99 ± 0.32 | 5/5 |
| 0.0075 | 116.595 ± 0.765 | 9.699 ± 0.754 | 12.08 ± 0.91 | 5/5 |
| 0.0150 | 116.348 ± 1.132 | 8.367 ± 0.518 | 13.91 ± 0.45 | 5/5 |
The following two figures use 20 independent random seeds for each noise level.
Figure 4(a): ER graph node matching accuracy ()
| Noise | Fixed step size 0.5 | Fixed step size 1 | Decreasing step size | Adaptive step size |
|---|---|---|---|---|
| 0.00000 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 |
| 0.05714 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 |
| 0.11429 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 |
| 0.17143 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 |
| 0.22857 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 | 100.00 ± 0.00 |
| 0.28571 | 100.00 ± 0.00 | 75.80 ± 43.02 | 16.79 ± 22.78 | 100.00 ± 0.00 |
| 0.34286 | 22.41 ± 39.84 | 1.11 ± 0.90 | 1.82 ± 0.89 | 22.38 ± 39.85 |
| 0.40000 | 5.69 ± 22.16 | 0.46 ± 0.37 | 0.96 ± 0.66 | 5.72 ± 22.19 |
Figure 4(c): Slashdot node matching accuracy ()
| Noise | Fixed step size 0.5 | Fixed step size 1 | Decreasing step size | Adaptive step size |
|---|---|---|---|---|
| 0.00000 | 63.15 ± 0.79 | 62.91 ± 0.84 | 63.05 ± 0.89 | 63.15 ± 0.79 |
| 0.04444 | 58.82 ± 0.96 | 58.83 ± 1.04 | 58.85 ± 0.99 | 59.05 ± 1.00 |
| 0.08889 | 54.71 ± 1.41 | 54.70 ± 1.30 | 54.67 ± 1.31 | 55.12 ± 1.39 |
| 0.13333 | 49.45 ± 1.59 | 50.42 ± 1.34 | 49.97 ± 1.54 | 50.74 ± 1.37 |
| 0.17778 | 44.53 ± 1.78 | 45.63 ± 2.19 | 44.14 ± 2.01 | 46.42 ± 1.61 |
| 0.22222 | 39.28 ± 1.54 | 41.09 ± 1.65 | 36.69 ± 3.05 | 41.76 ± 1.78 |
| 0.26667 | 33.89 ± 2.20 | 34.71 ± 2.59 | 25.05 ± 4.59 | 36.63 ± 1.92 |
| 0.31111 | 28.29 ± 3.84 | 26.90 ± 6.49 | 16.64 ± 3.98 | 32.08 ± 2.91 |
| 0.35556 | 18.14 ± 3.76 | 11.38 ± 3.82 | 10.59 ± 2.06 | 22.55 ± 4.40 |
| 0.40000 | 11.21 ± 2.62 | 6.41 ± 2.30 | 6.71 ± 1.78 | 12.43 ± 3.57 |
Table 3: PPI yeast graph matching accuracy ()
| Method | 0% Acc. | 0% Time | 5% Acc. | 5% Time | 10% Acc. | 10% Time | 15% Acc. | 15% Time |
|---|---|---|---|---|---|---|---|---|
| DP+ | 100.00 ± 0.00 | 1.24 ± 0.14 | 85.08 ± 5.02 | 2.05 ± 0.17 | 76.54 ± 6.59 | 2.30 ± 0.17 | 68.29 ± 10.17 | 2.55 ± 0.04 |
| LiDP | 100.00 ± 0.00 | 0.10 ± 0.05 | 86.18 ± 4.29 | 1.79 ± 0.43 | 77.83 ± 6.86 | 2.12 ± 0.34 | 69.81 ± 11.50 | 2.43 ± 0.10 |
Q4. Wrong permutation
Thanks the reviewer points out our issue.
In our experiments, we tested different noise levels and various types of graphs, and observed no false certificate passes. Thus, the empirical frequency of incorrect certification was zero, and all certified matchings were correct in the tested cases. While this provides encouraging empirical evidence, it does not constitute a universal theoretical guarantee outside the perfect-matching regime.
Moreover, even if a false certificate pass were to occur, the resulting matching could still be of high quality. Specifically, the Appendix G in the revised manuscript shows that any permutation with a normalized common-edge score sufficiently close to one enjoys a high matching accuracy with high probability.
Gentle reminder before the ICLR rebuttal period closes
Dear Reviewer m3Qn,
We hope this message finds you well. With approximately 10 hours remaining before the ICLR rebuttal/discussion period closes, we wanted to send a gentle reminder in case you have any remaining questions or concerns that you would like us to address.
If there is anything you would like us to clarify before the deadline, we would be very grateful for a brief note as soon as possible so that we can make the best use of the remaining time. If our response has addressed your concerns, we would be very grateful if you would consider updating your rating accordingly at your discretion. Of course, we fully respect your judgment and final assessment.
Thank you again for your time and for your valuable review. Your feedback is very important to us!
Best regards, Authors of Submission 46288
Response to Reviewer m3Qn (Part 1
We greatly appreciate the reviewers’ insightful suggestions, which have helped improve the paper.
W1. Complexity
We agree that the complexity improvement should be stated more precisely, particularly regarding worst-case behavior:
Reducing sorting overhead. We have revised the implementation in
match_fast4.mto avoid repeatedly sorting the entire accumulated candidate pool. Specifically, we maintain the current n smallest evaluated distances, denoted by Sn, using a max-heap. For each newly computed distance Dij, we compare it with the root of the heap, which stores the current maximum. If Dij is smaller, we replace the root with the new entry. Each heap update requires O(logn) time, which is asymptotically absorbed by the Θ(logn) cost of computing each distance. When downstream operations require selecting the smallest elements from a larger candidate set, a linear-time selection algorithm can be used instead of a full sort.Reducing the number of distance computations. We acknowledge that, in the worst case (e.g., when all nodes have the same degree), the selective candidate set may contain O(n2) pairs, and thus no unconditional complexity improvement can be guaranteed. However, under the low-noise assumptions of the correlated Erdős–Rényi model, our new theoretical analysis in Appendix F establishes that the expected number of distinct pairwise distances evaluated is O(n2/logn), and the same bound holds with high probability. Since each distance computation requires Θ(logn) time, the total distance-computation cost is therefore O(n2+d2n) with high probability.
W1&Q1. Exact-recovery theory*
We thank the reviewer for this careful and constructive comment. We address the two questions as follows.
On condition (40). Yes. For the correlated ER graph model G(n,q,s), let γ=q(s−q). For n≥8, 0<q<s≤1, and 0<δ<1, if nq2(s−q)2≥6logn+3log(5/δ), then condition (40) holds simultaneously for all permutation pairs (P,Q) with probability at least 1−δ. We will add this statement and its proof to the revised manuscript.
On whether Algorithm 2 reaches the required gap cn2/2. We can show that, under condition (40), if the initial permutation produced by the first stage has fewer than cn=q(s−q)n/8 mismatched vertices, then Algorithm 2 reaches the required objective gap. However, we currently do not have a high-probability bound guaranteeing that the first stage always provides such an initialization when it succeeds/fails. Therefore, the recovery guarantee in Corollary 1 and in the abstract is indeed conditional. We will restate both explicitly as conditional results.
Regarding Theorem 3, it only shows that, from an arbitrary initialization, every accumulation point of the sequence {Pt} computed by Algorithm 2 is a first-order stationary point; it does not by itself guarantee the gap cn2/2. We also note that no algorithm can guarantee, from an arbitrary initialization, an output within cn2/2 of the optimum in general; otherwise this would imply a polynomial-time algorithm for an NP-hard problem.
We will revise Corollary 1, the abstract, and the surrounding discussion accordingly to make the conditional nature of the guarantee explicit.
Q2. FAQ and DP+FAQ
We thank the reviewer for this helpful suggestion. Both Algorithm 2 and FAQ employ a Frank–Wolfe-type linear assignment step. However, their update formulas differ. Using the notation of LiDP, the two updates can be compared as follows:
=\arg\max_{P\in\Pi_{n\times n}} \langle P,AP^tB\rangle,$$ $$\text{FAQ:} P^{t+1}=P^t+\alpha^t\widetilde P^t,$$ $$\text{LiDP:} P^{t+1}=P^t+\alpha^t(\widetilde P^t-P^t).$$ Unlike the update in FAQ (as presented in its original paper, Eq. (9)), our update explicitly takes a convex combination of the current doubly stochastic matrix and the newly obtained permutation matrix. Since both belong to $\mathcal B_n$, the entire update preserves doubly stochastic feasibility. The term $\widetilde P^t-P^t$ is the Frank–Wolfe search direction. We will clarify these roles and revise the terminology to avoid confusion with conventional momentum-based methods. **(2) Comparison with DP+FAQ.** Following the reviewer's suggestion, we additionally evaluate FAQ initialized using the same DP distance matrix and compare it with LiDP on the Yeast PPI dataset. The results are reported below. | Method | 5% Acc. | Time (s) | 10% Acc. | Time (s) | 15% Acc. | Time (s) | |---|---:|---:|---:|---:|---:|---:| | DP+FAQ | 91.5% | 1.6 | 85.4% | 3.9 | 80.5% | 4.7 | | **LiDP** | **92.8%** | **1.2** | **87.8%** | **1.7** | **86.4%** | **2.2** | The results show that LiDP achieves consistently higher matching accuracy and lower computational time than DP+FAQ across all tested noise levels.