Faster Algorithms for Generalized Mean Densest Subgraph Problem
- URL: http://arxiv.org/abs/2310.11377v1
- Date: Tue, 17 Oct 2023 16:21:28 GMT
- Title: Faster Algorithms for Generalized Mean Densest Subgraph Problem
- Authors: Chenglin Fan, Ping Li, Hanyu Peng
- Abstract summary: We show that a standard peeling algorithm can still yield $21/p$-approximation for the case $0p 1$.
We propose a new and faster generalized peeling algorithm (called GENPEEL++ in this paper)
- Score: 26.3881083827734
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The densest subgraph of a large graph usually refers to some subgraph with
the highest average degree, which has been extended to the family of $p$-means
dense subgraph objectives by~\citet{veldt2021generalized}. The $p$-mean densest
subgraph problem seeks a subgraph with the highest average $p$-th-power degree,
whereas the standard densest subgraph problem seeks a subgraph with a simple
highest average degree. It was shown that the standard peeling algorithm can
perform arbitrarily poorly on generalized objective when $p>1$ but uncertain
when $0<p<1$. In this paper, we are the first to show that a standard peeling
algorithm can still yield $2^{1/p}$-approximation for the case $0<p < 1$.
(Veldt 2021) proposed a new generalized peeling algorithm (GENPEEL), which for
$p \geq 1$ has an approximation guarantee ratio $(p+1)^{1/p}$, and time
complexity $O(mn)$, where $m$ and $n$ denote the number of edges and nodes in
graph respectively. In terms of algorithmic contributions, we propose a new and
faster generalized peeling algorithm (called GENPEEL++ in this paper), which
for $p \in [1, +\infty)$ has an approximation guarantee ratio $(2(p+1))^{1/p}$,
and time complexity $O(m(\log n))$, where $m$ and $n$ denote the number of
edges and nodes in graph, respectively. This approximation ratio converges to 1
as $p \rightarrow \infty$.
Related papers
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - 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) - Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An
Index-based Approach [9.13755431537592]
In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(mtimesleft( 2+ alpha (G) right)+n)$ to $O(m+n)$ for any given value of $varepsilon$ for a complete signed graph.
Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting.
arXiv Detail & Related papers (2023-01-01T10:57:36Z) - Finding the KT partition of a weighted graph in near-linear time [1.572727650614088]
Kawarabayashi and Thorup gave a near-trivial time deterministic algorithm for minimum cut in a simple graph $G = (V,E)$.
We give a near-linear time randomized algorithm to find the $(1+varepsilon)$-KT partition of a weighted graph.
arXiv Detail & Related papers (2021-11-02T05:26:10Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
We study the problem of list-decodable mean estimation, where an adversary can corrupt a majority of the dataset.
We develop new algorithms for list-decodable mean estimation, achieving nearly-optimal statistical guarantees.
arXiv Detail & Related papers (2021-06-16T03:34:14Z) - The Generalized Mean Densest Subgraph Problem [30.33731479053404]
We introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$.
Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases.
A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice.
arXiv Detail & Related papers (2021-06-02T02:58:35Z) - Adapting $k$-means algorithms for outliers [1.9290392443571387]
We show how to adapt several simple sampling-based algorithms for the $k$-means problem to the setting with outliers.
Our algorithms output $(varepsilon)z$ outliers while achieving an $O(varepsilon)$-approximation to the objective function.
arXiv Detail & Related papers (2020-07-02T14:14:33Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy.
For small enough $epsilon$, we show an improved algorithm with sample complexity.
arXiv Detail & Related papers (2020-06-06T13:34:41Z)
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.