acceptodds
Under review as a conference paper at ICLR 2027

LiDP: A Selective-and-Adaptive Framework for Distance-Based Random Graph Matching

Abstract

Graph matching is an NP-hard problem of recovering vertex correspondences between correlated graphs. Degree-profile methods, which compare vertices based on their local statistics, are attractive due to their exact recovery guarantees and computational efficiency. However, these methods typically require computing distances between all pairs of vertices, and their performance may deteriorate in high-noise regimes. To address these challenges, we propose a two-stage framework for random graph matching. First, selective distance computation preserves the exact recovery guarantee of degree-profile matching while reducing the complexity from to . When recovery fails under high noise, the computed distances warm-start a continuous optimization method with convergence guarantees. Under suitable assumptions, we establish exact recovery for stationary points with sufficiently small objective gaps to the ground truth. To the best of our knowledge, this is the first such guarantee for near-optimal stationary points in nonconvex doubly stochastic graph matching. Experiments on synthetic and real-world networks show – speedups in low-noise regimes and substantially improved robustness under high noise.

Primary area:
optimization
Keywords:
Random Graph matching, Degree profile, Erdős–Rényi graphs

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_m3QnOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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.m fills the uncomputed entries by a linear fit in degree difference (linear_fitting) and has no 20% cap, and ER_test.m runs 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:

  1. 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.
  2. 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+.
  3. 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?
  4. 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
AuthorsOpenReview ↗

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:

  1. Reducing sorting overhead. We have revised the implementation in match_fast4.m to avoid repeatedly sorting the entire accumulated candidate pool. Specifically, we maintain the current nn smallest evaluated distances, denoted by Sn\mathcal{S}_n, using a max-heap. For each newly computed distance DijD_{ij}, we compare it with the root of the heap, which stores the current maximum. If DijD_{ij} is smaller, we replace the root with the new entry. Each heap update requires O(log⁡n)O(\log n) time, which is asymptotically absorbed by the Θ(log⁡n)\Theta(\log n) 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.

  2. 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)O(n^2) 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/log⁡n)O(n^2/\log n), and the same bound holds with high probability. Since each distance computation requires Θ(log⁡n)\Theta(\log n) time, the total distance-computation cost is therefore O(n2+d2n)O(n^2+d^2n) 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)\mathcal G(n,q,s), let γ=q(s−q)\gamma=q(s-q). For n≥8n\ge 8, 0<q<s≤10<q<s\le 1, and 0<δ<10<\delta<1, if nq2(s−q)2≥6log⁡n+3log⁡(5/δ),nq^2(s-q)^2 \ge 6\log n+3\log(5/\delta), then condition (40) holds simultaneously for all permutation pairs (P,Q)(P,Q) with probability at least 1−δ1-\delta. We will add this statement and its proof to the revised manuscript.

On whether Algorithm 2 reaches the required gap cn2/2c_n^2/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/8c_n=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}\{P^t\} computed by Algorithm 2 is a first-order stationary point; it does not by itself guarantee the gap cn2/2c_n^2/2. We also note that no algorithm can guarantee, from an arbitrary initialization, an output within cn2/2c_n^2/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.
AuthorsOpenReview ↗

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 DijD_{ij} entries is less than n2/5n^2/5. Accordingly, in our implementation, once the number of computed entries exceeds n2/5n^2/5, we exit immediately and compute the full DD. 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 (n=10000n=10000)
Noise δ\sqrt{\delta}DP time (s)LiDP time (s)Speedup (×)LiDP early-certification count / total runs
0.0000117.567 ± 0.8207.845 ± 0.17614.99 ± 0.325/5
0.0075116.595 ± 0.7659.699 ± 0.75412.08 ± 0.915/5
0.0150116.348 ± 1.1328.367 ± 0.51813.91 ± 0.455/5

The following two figures use 20 independent random seeds for each noise level.

Figure 4(a): ER graph node matching accuracy (n=1000n=1000)
Noise δ\sqrt{\delta}Fixed step size 0.5Fixed step size 1Decreasing step sizeAdaptive step size
0.00000100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00
0.05714100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00
0.11429100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00
0.17143100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00
0.22857100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00100.00 ± 0.00
0.28571100.00 ± 0.0075.80 ± 43.0216.79 ± 22.78100.00 ± 0.00
0.3428622.41 ± 39.841.11 ± 0.901.82 ± 0.8922.38 ± 39.85
0.400005.69 ± 22.160.46 ± 0.370.96 ± 0.665.72 ± 22.19
Figure 4(c): Slashdot node matching accuracy (n=750n=750)
Noise δ\deltaFixed step size 0.5Fixed step size 1Decreasing step sizeAdaptive step size
0.0000063.15 ± 0.7962.91 ± 0.8463.05 ± 0.8963.15 ± 0.79
0.0444458.82 ± 0.9658.83 ± 1.0458.85 ± 0.9959.05 ± 1.00
0.0888954.71 ± 1.4154.70 ± 1.3054.67 ± 1.3155.12 ± 1.39
0.1333349.45 ± 1.5950.42 ± 1.3449.97 ± 1.5450.74 ± 1.37
0.1777844.53 ± 1.7845.63 ± 2.1944.14 ± 2.0146.42 ± 1.61
0.2222239.28 ± 1.5441.09 ± 1.6536.69 ± 3.0541.76 ± 1.78
0.2666733.89 ± 2.2034.71 ± 2.5925.05 ± 4.5936.63 ± 1.92
0.3111128.29 ± 3.8426.90 ± 6.4916.64 ± 3.9832.08 ± 2.91
0.3555618.14 ± 3.7611.38 ± 3.8210.59 ± 2.0622.55 ± 4.40
0.4000011.21 ± 2.626.41 ± 2.306.71 ± 1.7812.43 ± 3.57
Table 3: PPI yeast graph matching accuracy (n=1004n=1004)
Method0% Acc.0% Time5% Acc.5% Time10% Acc.10% Time15% Acc.15% Time
DP+100.00 ± 0.001.24 ± 0.1485.08 ± 5.022.05 ± 0.1776.54 ± 6.592.30 ± 0.1768.29 ± 10.172.55 ± 0.04
LiDP100.00 ± 0.000.10 ± 0.0586.18 ± 4.291.79 ± 0.4377.83 ± 6.862.12 ± 0.3469.81 ± 11.502.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.

AuthorsOpenReview ↗

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

Reviewer_nSrLOpenReview ↗
Rating
1
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
3(+2)
Read review
Paper summary

The authors propose LiDP, an algorithm used for random graph matching in the Erdős–Rényi model using the degree profile (DP) statistic of Ding et al.. The degree profile distance DijD_{ij} is used to match node ii in graph AA to node jj in graph BB. This distance can be expensive to compute, so LiDP uses the degree difference Dij′=∣deg⁡A(i)−deg⁡B(j)∣D_{ij}'= |\deg_A(i) - \deg_B(j)| as an initial heuristic for which true values DijD_{ij} to compute. When the nn smallest values of the degree profile distance matrix DD induce a perfect matching between AA and BB, LiDP is able to recover the matching. When the selective stage fails, LiDP uses the partial result and iteratively refines it using a Frank-Wolfe algorithm. The paper also gives a conditional exact-recovery guarantee. Experiments evaluate LiDP on both synthetic Erdős–Rényi graphs and real-world graphs.

Critical strengths

(1) Selective computation seems like a promising heuristic in practice. Table 2 reports than over 94% of DD can skipped using LiDP.

Critical weaknesses

(1) The O(n2+nd2)O(n^2 + nd^2) time complexity of LiDP's selective stage (Algorithm 4) is not justified. Ding et al. sets L=Θ(log⁡n)L = \Theta(\log n) in their Theorem 2. After the degree profile vectors have been precomputed, direct computation of one value DijD_{ij} takes Θ(L)=Θ(log⁡n)\Theta(L) = \Theta(\log n) time. Then, it remains to be shown that at most O((n2+nd2)/log⁡n)O((n^2 + nd^2) / \log n) values of DD are ever computed. This is unclear from the algorithm, as it seems that the set KK on line 5 could be O(n2)O(n^2). For example, if all nodes in both AA and BB had degree dd, then on the first iteration of the loop with k=0k = 0, the set KK on line 5 would contain all pairs of nodes. Then, all values of DD would be computed, requiring at least Ω(n2L)=Ω(n2log⁡n)\Omega(n^2 L) = \Omega(n^2 \log n) time, independent of dd.

There are other gaps in the analysis as well. How are the sets KK on line 5 computed? How are the nn smallest items of SnS_n maintained? These two are probably fixable by sorting by degree + careful accounting and by linear time selection methods, respectively, but given that the submission's claimed contribution is the improved complexity, these details should be spelled out.

(2) The notation (particularly in Section 3.2 and Appendix B.1) is not self-contained, and I had to refer to Ding et al. to supply the missing details.

Questions for authors

(1) What is the choice of LL? How are the values DijD_{ij} computed?

(2) Is there a bound on the number of values of DD that LiDP computes in the Erdős–Rényi model?

(3) How are the sets KK and SnS_n implemented in Algorithm 4?

2 comments
AuthorsOpenReview ↗

Response to the reviewer nSrL

We sincerely thank the reviewer for their careful reading and highly constructive feedback. The process of addressing your insightful questions has substantially enriched the manuscript and made it much more comprehensive. We especially appreciate your time and dedication, which is truly invaluable in the current academic environment.

Q1.choice of LL and computation of DijD_{ij}

We adopt the experimental setting from Ding et al. (https://github.com/xjmoffside/degree_profile). While the parameter LL is not explicitly exposed in their implementation, the subsequent two theorems are established based on the complexity of computing DijD_{ij} being Θ(L)=Θ(log⁡n)\Theta(L) = \Theta(\log n).

Q2.Bound on the number of values of D

Yes. The reviewer is correct that, in a worst-case scenario (e.g., when all nodes have exactly the same degree dd), the set K\mathcal{K} could contain O(n2)O(n^2) pairs in the first iteration, potentially leading to a time complexity of Ω(n2log⁡n)\Omega(n^2\log n).

However, as stated in our paper, our theoretical analysis is based on the Erdős–Rényi (ER) graph assumption. Under this model, node degrees follow a binomial distribution and are highly concentrated around their expected value. Consequently, the pathological worst-case scenario is unlikely to occur.

To address this concern, we have added a theoretical analysis in Appendix F, establishing that, under the low-noise regime of the correlated Erdős–Rényi model, the total number of pairwise distances computed by LiDP is bounded by O(n2log⁡n)O\left(\frac{n^2}{\log n}\right) with high probability. This leads to an overall time complexity of O(n2+nd2)O(n^2+nd^2) with high probability. We will also clarify in the revised manuscript that this complexity improvement is conditional on the underlying random graph model and the assumed noise regime, rather than an unconditional guarantee.

Q3. Construction of K\mathcal{K} and Maintenance of Sn\mathcal{S}_n

Maintenance of Sn\mathcal{S}_n: We initialize Sn\mathcal{S}_n by taking nn computed distances and sorting their corresponding triplets. To maintain the nn smallest elements efficiently, we treat Sn\mathcal{S}_n as a max-heap. For each subsequently computed DijD_{ij}, we compare it only with the root (the current maximum) of the heap. If DijD_{ij} is smaller, we remove the maximum and insert the new triplet. Since computing DijD_{ij} already requires Θ(log⁡n)\Theta(\log n) time, the O(log⁡n)O(\log n) heap update is asymptotically absorbed and does not increase the overall time complexity. If full sorting is required at each iteration for downstream tasks, we can instead extract all elements and apply a linear-time selection algorithm rather than performing a full sort.

Construction of K\mathcal{K}: The formula for Kk\mathcal{K}_k is defined in Line 5 of Algorithm 3. A node pair (i,j)(i,j) is added to Kk\mathcal{K}_k if and only if it satisfies three conditions:

  1. The degree difference satisfies D^ij≤k\widehat{D}_{ij}\leq k; (D^ij\widehat{D}_{ij} is the degree difference between node i and node j; k is the maximum degree difference of the batch to be computed in the current round.).
  2. The ii-th row or the jj-th column has not yet been covered by the elements of the Sn\mathcal{S}_n;
  3. The distance DijD_{ij} has not been computed yet.
AuthorsOpenReview ↗

Gentle reminder before the ICLR rebuttal period closes

Dear Reviewer nSrL,

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

Reviewer_ktR8OpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a Light Degree Profile (LiDP) framework which finds a correspondence between two full, correlated, un-weighted graphs of same size. The authors focus on getting speedup of 10x to 20x by not computing the complete n^2 distance matrix, but rather focusing on the degree-differences by prioritizing calculations for vertex pairs that have small degree differences, since true matches tend to have similar local degrees and then terminate early using a mathematical certification step to stop as soon as true bijection is achieved. They show that for synthetic and real-world datasets there is a huge markup in speed.

Critical strengths
  • The algorithmic contribution to the degree profile based graph matching is substantial.
  • The theoretical contributions are sound.
Critical weaknesses
  • There has been quite a few different approaches of sub-graph matching (of which graph matching is a special case) using methods such as topology-based pruning with weighted noisy edges for e.g. see "Uncertainty-aware efficient subgraph isomorphism using graph topology"; "Graph Matching with Bi-level Noisy Correspondence" . So while the paper feels like a jump in terms of degree-profile methods, there have been other approaches which have already tackled a more complex problem.
  • While some edge deletion is targeted, random dense edge insertion is not focused upon.
Questions for authors
  • How does the given approach compare with the other more complex approaches?
  • What happens when random dense edge insertion happens?
3 comments
AuthorsOpenReview ↗

We sincerely thank the reviewer for the positive evaluation of our algorithmic and theoretical contributions, and we have completed the experiments of concern with promising results.

W1&Q1. Other baselines.

We thank the reviewer for pointing us to these relevant references. While they address broader or different matching scenarios, degree-profile methods offer a distinct strength: exact recovery with high probability under suitable random-graph and noise assumptions, despite graph matching being NP-hard. LiDP builds on this foundation by improving computational efficiency in the low-noise regime while preserving the recovery guarantees, and by enhancing empirical robustness under higher noise.

To further illustrate the practical differences between LIDP and the two mentioned algorithms, we have added comparison experiments on the Yeast PPI network.

Table. Node matching accuracy (%) and runtime (s) on the yeast PPI network.

Method0% noise: Acc.Time (s)5% noise: Acc.Time (s)10% noise: Acc.Time (s)15% noise: Acc.Time (s)
Kusari–Sun84.5%0.51379.8%1.21873.0%1.81461.5%2.383
COMMON84.2%0.02370.7%0.03257.9%0.04542.7%0.055
LiDP100%0.1392.8%1.287.8%1.786.4%2.2

LiDP achieves the highest accuracy across all tested noise levels. LiDP is also faster than Kusari–Sun, although COMMON remains faster. These results demonstrate the practical value of our improvements to theoretically grounded degree-profile methods.

$ $

W2&Q2. Random dense edge insertion.

We thank the reviewer for this observation. We clarify that our PPI experiments already involve edge insertion, although the inserted edges are not fully random. To directly address the reviewer’s concern, we further construct random dense edge insertion on the PPI dataset by adding 5%, 10%, and 15% edges, repeat the experiments ten times at each noise level, and report the average results in the following table.

Table. LiDP matching accuracy and runtime on the yeast PPI network under edge-insertion settings.

Cases0% noise: Acc.Time (s)5% noise: Acc.Time (s)10% noise: Acc.Time (s)15% noise: Acc.Time (s)
Original PPI100%0.1392.8%1.287.8%1.786.4%2.2
PPI+ edge insertion100%0.1390.2%1.886.0%2.280.8%2.5

Thanks for the results. I have updated the score.

We sincerely appreciate your positive feedback, which is a tremendous encouragement to us.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response Summary: New Experiments and Theoretical Clarifications

We sincerely thank all the reviewers for their time and highly constructive feedback. The process of addressing your insightful questions has substantially enriched our manuscript and made it much more comprehensive. We are very encouraged that Reviewer ktR8 found our revisions satisfactory and upgraded the score from 3 to 4. We have now completed all requested experiments and theoretical clarifications for Reviewer nSrL and Reviewer m3Qn, and we look forward to their feedback.

Here is a summary of the major updates made to the paper:

1. Response to Reviewer ktR8 (Comparison & Robustness)

  • Other complex baselines: We added comparisons against more complex methods (Kusari–Sun, COMMON) on the Yeast PPI dataset. LiDP achieves superior accuracy (e.g., 100% vs. ~84% at 0% noise) and faster runtime than Kusari–Sun, demonstrating the practical value of our framework.
  • Random dense edge insertion: We constructed dense edge insertion experiments (adding 5%, 10%, 15% edges, repeated 10 times). Results show LiDP remains highly robust and efficient under edge insertion, with only minimal degradation in accuracy.

2. Response to Reviewer nSrL (Complexity & Implementation)

  • Bound on DD values: We added a new theorem in Appendix F. We proved that under the correlated ER model, the number of evaluated distances is bounded by O(n2/log⁡n)O(n^2/\log n) with high probability, leading to an overall O(n2+nd2)O(n^2+nd^2) time complexity.
  • Implementation of K\mathcal{K} and Sn\mathcal{S}_n: We clarified that $\mathcal{S} _n$ is maintained via a max-heap, with O(log⁡n)O(\log n) updates asymptotically absorbed by the Θ(log⁡n)\Theta(\log n) cost of computing DijD_{ij}. The construction of Kk\mathcal{K}_k is explicitly detailed based on degree difference, row/column coverage, and uncomputed status.

3. Response to Reviewer m3Qn (Theoretical Claims & Experimental Details)

  • Conditional Theory: We proved that condition (40) holds with probability at least 1−δ1-\delta under specific (n,q,s)(n, q, s) conditions. We explicitly restated Corollary 1 and the Abstract as conditional results.

  • Relation to FAQ: We mathematically clarified the difference:

    FAQ uses

    Pt+1=Pt+αtP~tP^{t+1}=P^t+\alpha^t\widetilde P^t

    while LiDP uses the convex combination

    Pt+1=Pt+αt(P~t−Pt)P^{t+1}=P^t+\alpha^t(\widetilde P^t-P^t)

    to preserve doubly stochastic feasibility. New experiments show LiDP consistently outperforms DP+FAQ in both accuracy and runtime.

  • Procedure & Error Bars: We clarified the early-exit threshold (n2/5n^2/5) and updated all figures/tables with standard error bars based on 5 to 20 independent runs.

  • Wrong Permutations: We observed zero false certificates in all experiments. Even if a false pass occurs, Appendix G shows that permutations with high common-edge scores still guarantee high matching accuracy.

We believe the paper is now significantly stronger. We kindly invite Reviewer nSrL and m3Qn to review our response.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.