Graph Matching with Partially-Correct Seeds

• URL: http://arxiv.org/abs/2004.03816v2
• Date: Tue, 5 Jan 2021 17:32:14 GMT
• Title: Graph Matching with Partially-Correct Seeds
• Authors: Liren Yu, Jiaming Xu, and Xiaojun Lin
• Abstract summary: We show that our new $2$-hop algorithm requires substantially fewer correct seeds than the $1$-hop algorithm when graphs are sparse. By combining our new performance guarantees for the $1$-hop and $2$-hop algorithms, we attain the best-known results. Numerical experiments corroborate our theoretical findings, demonstrating the superiority of our $2$-hop algorithm on a variety of synthetic and real graphs.
• Score: 20.998695802214677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph matching aims to find the latent vertex correspondence between two edge-correlated graphs and has found numerous applications across different fields. In this paper, we study a seeded graph matching problem, which assumes that a set of seeds, i.e., pre-mapped vertex-pairs, is given in advance. While most previous work requires all seeds to be correct, we focus on the setting where the seeds are partially correct. Specifically, consider two correlated graphs whose edges are sampled independently from a parent \ER graph $\mathcal{G}(n,p)$. A mapping between the vertices of the two graphs is provided as seeds, of which an unknown $\beta$ fraction is correct. We first analyze a simple algorithm that matches vertices based on the number of common seeds in the $1$-hop neighborhoods, and then further propose a new algorithm that uses seeds in the $2$-hop neighborhoods. We establish non-asymptotic performance guarantees of perfect matching for both $1$-hop and $2$-hop algorithms, showing that our new $2$-hop algorithm requires substantially fewer correct seeds than the $1$-hop algorithm when graphs are sparse. Moreover, by combining our new performance guarantees for the $1$-hop and $2$-hop algorithms, we attain the best-known results (in terms of the required fraction of correct seeds) across the entire range of graph sparsity and significantly improve the previous results in \cite{10.14778/2794367.2794371,lubars2018correcting} when $p\ge n^{-5/6}$. For instance, when $p$ is a constant or $p=n^{-3/4}$, we show that only $\Omega(\sqrt{n\log n})$ correct seeds suffice for perfect matching, while the previously best-known results demand $\Omega(n)$ and $\Omega(n^{3/4}\log n)$ correct seeds, respectively. Numerical experiments corroborate our theoretical findings, demonstrating the superiority of our $2$-hop algorithm on a variety of synthetic and real graphs.

Related papers

• Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) [2.313664320808389]
  We present the OmniMatch algorithm for seeded multiple graph matching.<n>We demonstrate the effectiveness of our algorithm across numerous simulations and in the context of shuffled graph hypothesis testing.
  arXiv  Detail & Related papers  (2025-06-03T12:54:24Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
  We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each. This is the first graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs.
  arXiv  Detail & Related papers  (2022-09-25T20:00:28Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  We give a characterization of a minimal sized set of atomic interventions to check the correctness of a claimed causal graph. We generalize our results to the settings of bounded size interventions and node-dependent interventional costs. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs.
  arXiv  Detail & Related papers  (2022-06-30T15:52:30Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
  We analyse the performance of the emphprojected power method (PPM) as a emphseeded graph matching algorithm. PPM works even in iterations of constant $sigma$, thus extending the analysis in (Mao et al. 2023) for the sparse Correlated Erdos-Renyi(CER) model to the (dense) CGW model.
  arXiv  Detail & Related papers  (2022-04-08T14:31:26Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• The Power of $D$-hops in Matching Power-Law Graphs [20.88345367293753]
  We develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Under the Chung-Lu random graph model with $n$ vertices, max degree $Theta(sqrtn)$, and the power-law exponent $2beta3$, we show that as soon as $D> frac4-beta3-beta$, by optimally choosing the first slice, with high probability our algorithm can correctly match a constant fraction of the true pairs.
  arXiv  Detail & Related papers  (2021-02-23T05:36:58Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.