The Power of $D$-hops in Matching Power-Law Graphs
- URL: http://arxiv.org/abs/2102.12975v1
- Date: Tue, 23 Feb 2021 05:36:58 GMT
- Title: The Power of $D$-hops in Matching Power-Law Graphs
- Authors: Liren Yu, Jiaming Xu, Xiaojun Lin
- Abstract summary: 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.
- Score: 20.88345367293753
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies seeded graph matching for power-law graphs. Assume that
two edge-correlated graphs are independently edge-sampled from a common parent
graph with a power-law degree distribution. A set of correctly matched
vertex-pairs is chosen at random and revealed as initial seeds. Our goal is to
use the seeds to recover the remaining latent vertex correspondence between the
two graphs. Departing from the existing approaches that focus on the use of
high-degree seeds in $1$-hop neighborhoods, we develop an efficient algorithm
that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods.
Specifically, we first match a set of vertex-pairs with appropriate degrees
(which we refer to as the first slice) based on the number of low-degree seeds
in their $D$-hop neighborhoods. This significantly reduces the number of
initial seeds needed to trigger a cascading process to match the rest of the
graphs. Under the Chung-Lu random graph model with $n$ vertices, max degree
$\Theta(\sqrt{n})$, and the power-law exponent $2<\beta<3$, we show that as
soon as $D> \frac{4-\beta}{3-\beta}$, by optimally choosing the first slice,
with high probability our algorithm can correctly match a constant fraction of
the true pairs without any error, provided with only $\Omega((\log
n)^{4-\beta})$ initial seeds. Our result achieves an exponential reduction in
the seed size requirement, as the best previously known result requires
$n^{1/2+\epsilon}$ seeds (for any small constant $\epsilon>0$). Performance
evaluation with synthetic and real data further corroborates the improved
performance of our algorithm.
Related papers
- 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) - 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) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds.
We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability.
We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
arXiv Detail & Related papers (2022-10-04T04:36:15Z) - 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) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model.
It is assumed that the graph's structure is known and has $N$ nodes.
Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
arXiv Detail & Related papers (2022-08-26T16:21:31Z) - 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) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels.
When restricting labels $x_i$ to binary values, the problem is NP-hard.
We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
arXiv Detail & Related papers (2021-06-03T07:22:48Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$
We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
arXiv Detail & Related papers (2021-03-02T06:53:44Z) - 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) - Better Bounds on the Adaptivity Gap of Influence Maximization under
Full-adoption Feedback [15.533908352376853]
We look for a set of $k$ nodes that maximize the expected number of nodes that are reached by an influence cascade.
We show that the adaptivity gap is upper-bounded by $lceil nrceil $, where $n$ is the number of nodes in the graph.
We also show that in 0-bounded graphs, i.e. undirected graphs, the adaptivity gap is at most $frac3e3e3-1approx 3.16$.
arXiv Detail & Related papers (2020-06-27T14:43:34Z) - Graph Matching with Partially-Correct Seeds [20.998695802214677]
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.
arXiv Detail & Related papers (2020-04-08T05:25:52Z)
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.