论文标题
通用贪婪算法的图形稀疏
Graph Sparsification by Universal Greedy Algorithms
论文作者
论文摘要
Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, numerical solution of symmetric positive definite linear systems and etc. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm called universal greedy approach (UGA)用于图形稀疏。对于一般的光谱稀疏问题，例如，从$ \ Mathbb {r}^n $中的一组$ m $ vector中的积极子集选择问题，我们提出了一个需要$ O（Mn^2+ n^3/ε^2）$的非阴性UGA算法，以找到$ \ frac $ \ frac {$ \ frac {$ \ frac {1+β};带有稀疏性的正系数$ \ le \ lceil \ frac {n} {ε^2} \ rceil $，其中$β$是向量的最小长度和最大长度之间的比率。将建立非负UGA算法的收敛性。对于图形泄漏问题，将提出另一种UGA算法，该算法可以输出$ \ frac {1+o（ε）} {1-o（ε）} $ - 光谱稀疏器，带有$ \ lceil \ lceil \ frac {n} $ n $顶点在某些温和的假设下。就图形稀疏社区所寻找的边缘数量而言，这是一种线性时间算法。文献中作者知识的最佳结果是存在几乎是线性的确定性算法的存在，即$ o（m^{1+o（1）}）$（\ o（1）= o（\ frac {（\ frac {（\ log log \ log \ log \ log \ log \ log \ log \ log \ log \ log（m））最后，广泛的实验结果，包括在图形聚类和最小二乘回归中的应用，显示了提议的方法的有效性。
Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, numerical solution of symmetric positive definite linear systems and etc. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm called universal greedy approach (UGA) for graph sparsification. For a general spectral sparsification problem, e.g., positive subset selection problem from a set of $m$ vectors from $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/ε^2)$ time to find a $\frac{1+ε/β}{1-ε/β}$-spectral sparsifier with positive coefficients with sparsity $\le\lceil\frac{n}{ε^2}\rceil$, where $β$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm will be established. For the graph sparsification problem, another UGA algorithm will be proposed which can output a $\frac{1+O(ε)}{1-O(ε)}$-spectral sparsifier with $\lceil\frac{n}{ε^2}\rceil$ edges in $O(m+n^2/ε^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.
