Research map / Graph learning / Graph algorithms and clustering
Robust Graph Matching when Nodes are Corrupt
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces weak (random) and strong (adversarial) node-corruption models for correlated Erdős–Rényi graph matching, proving impossibility results and showing the k-core and maximum overlap estimators' achievability under conditions.
Problem
Graph matching between two edge-correlated graphs when a positive fraction of nodes is corrupted, either randomly (biological-style noise) or adversarially (hacked users in social networks).
Approach
Defines two node-corruption models: WCG where a random node subset has all incident edges resampled independently, and SCG where an arbitrary adversary rewires incident edges after observing the graphs; derives necessary and sufficient conditions for k-core matching under WCG and shows maximum overlap achieves positive-fraction recovery under SCG when only one graph is corrupted.
Key results
- Under the WCG model no estimator can be precise on corrupted nodes, and almost alpha-recovery is bounded by alpha* = 1 - gamma + lambda(1-lambda)gamma^2.
- With p = C log(n)/n and k = sqrt(log n), the k-core estimator is precise and, if C > 1/(s^2 alpha*), matches exactly the uncorrupted node set with high probability.
- Under SCG with only one network corrupted, the maximum overlap estimator achieves alpha-recovery for gamma < s(1-alpha^2)/4 (log-degree regime).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use k-core matching with k = sqrt(log n) when C > 1/(s^2α*) | WCG graph matching · WCG | recovery | Helped |
| Use k-core matching with k = sqrt(log n) when C > 1/(s^2α*) | WCG graph matching · WCG | precision | Helped |
| Use k-core matching with k = sqrt(log n) when C < 1/(s^2α*) | WCG graph matching · WCG | recovery | Helped |
| Introduce weak random node corruption | Any graph-matching estimator · WCG | recovery | Hurt |
| Introduce weak random node corruption | Any precise graph-matching estimator · WCG | correct recovery of corrupt nodes | Hurt |
| Use maximum overlap matching when only one network is compromised and γ < s(1-α²)/4 | SCG graph matching · SCG, p = C log(n)/n, λ ∈ {0,1} | recovery | Helped |
| Use maximum overlap matching when only one network is compromised and γ < 1 - sqrt(1 - s²p(1-p)(1-α²)/2) | SCG graph matching · SCG, p constant, λ ∈ {0,1} | recovery | Helped |
| Allow an adversary to corrupt nodes arbitrarily after observing the graphs | Any estimator returning a matching of size Θ(n) · SCG, γ > 0 | precision | Hurt |
| Compromise both networks using the described high-degree adversarial rewiring | Maximum overlap estimator · SCG, λ = 1/2, p = C log n/n | correctly matched nodes | Hurt |
Surprising findings
- Under SCG with lambda=1/2, a simple adversarial action can cause the maximum overlap estimator to match no nodes correctly.
- Detection of corrupted nodes is impossible under the strong adversary model.
Limitations
- Computationally feasible algorithms (GRAMPA, degree profiling, canonical labeling) perform far from the k-core asymptotic guarantees in simulations.
- k-core and maximum overlap estimators are not polynomial-time.
- Results are asymptotic and rely on Erdős–Rényi graph assumptions.
Experimental setup
Metrics: alpha-recovery precision overlap
Baselines: GRAMPA degree profiling canonical labeling
Builds on: correlated Erdős–Rényi graph matching k-core estimator for graph matching
Closest papers by meaning
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.85)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.84)
- Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (NeurIPS 2025 · similarity 0.84)
- Robust Graph Neural Networks via Unbiased Aggregation (NeurIPS 2024 · similarity 0.84)
- Bounding the Expected Robustness of Graph Neural Networks Subject to Node Feature Attacks (ICLR 2024 · similarity 0.84)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.