An Empirical Comparison of Graph Laplacian Solvers
An Empirical Comparison of Graph Laplacian Solvers
复制标题
图拉普拉斯求解器的实证比较
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Gilbert
中科院分区：
文献类型：
--
作者：
E. Boman;Kevin Deweese;J. Gilbert
求解拉普拉斯线性系统在各种实际和理论应用中都是一项重要的任务。这个问题的解在理论上是线性乘以多对数的，但是这些算法在实践中很难实现。我们检查现有的解决方案技术，以确定当前可用的最佳方法以及它们对哪些类型的问题有用。我们使用各种求解器对各种问题进行计时实验，并给出我们的结果。我们发现在网络图和一类设计用来对其建模的合成图之间存在不同的求解器行为。一个加权无向图G的拉普拉斯矩阵定义为LG = DG−AG，其中DG是包含所有关联边权和的对角矩阵，AG是加权邻接矩阵。LG是一个对称的、正半定的、对角占优的m矩阵，其零空间包含常数向量。在结构化图的拉普拉斯算子上求解线性系统，如二维和三维网格，在有限元分析（应用于电导率和导热性，以及流体流动建模[5]）和图像处理（应用于图像分割，油漆，回归和分类[22]）中一直很重要。Sandia是一个多项目实验室，由Sandia公司管理和运营，它是洛克希德马丁公司的全资子公司，为美国能源部的国家核安全管理局服务，合同为DE-AC04-94AL85000。†由英特尔公司和DOE科学办公室合同#DEAC02-05CH11231部分支持。作为网络分析中的重要计算任务出现（应用于最大流量问题[8]，图稀疏化[26]和谱聚类[19]）。对求解拉普拉斯算子的兴趣与对求解更一般的对称对角占优（SDD）矩阵的兴趣密切相关。如果矩阵A = A，且≥∑i6=j |，则矩阵A为SDD。解决这些问题的一种方法是首先将它们简化为拉普拉斯矩阵[3,13]，然后用拉普拉斯解算器求解。上面应用中的一些拉普拉斯线性系统是从SDD线性系统派生出来的。由于从一个SDD矩阵到一个图拉普拉斯矩阵的简化是渐进的便宜的，理论上最好的SDD求解器依赖于拉普拉斯求解器。在过去的几十年里，理论计算机科学界在渐近有效的拉普拉斯解算器上做了大量的工作。Spielman和Teng[27]展示了如何在线性乘以多对数的工作中解决这些问题，后来由Koutis， Miller和Peng[27]改进，但这些算法具有复杂的描述和可疑的大常数，阻碍了它们的实际实现。Kelner等人提出的算法[18]具有算法描述简单的优点，但最初的实验结果[4,16]表明，该算法在实践中难以竞争。据我们所知，目前还没有对可用解算器进行全面的实验研究。我们的目标是提供对可用解算器的初步理解，并确定来自更多理论解算器的想法可以在实践中加以利用以进行改进。我们相信从相关的应用程序中获得一组测试问题，以及一组用于评估当前和未来的拉普拉斯求解器在这些测试问题上的性能的性能度量是很重要的。我们希望了解拉普拉斯解算器的性能如何随测试问题的类别而变化。这是一项正在进行的工作，我们将这篇论文设想为一个活生生的文档，它将不断改进，以纳入新的解决方案、更好的测试问题和更有用的性能分析。为此，作者欢迎就如何提高我们对拉普拉斯解算器的理解提供反馈。对于第一轮实验，我们只使用作为图拉普拉斯函数的图/矩阵，以及可以很容易转换为图拉普拉斯函数的邻接矩阵。我们使用的图的边数在1万条到1千万条之间。更大的图表留给未来的并行实验。我们只使用每个图的最大连通分量来保证零空间维数为1。在这些实验中，我们从三个不同的来源收集了四组测试图/矩阵。第一个来源是佛罗里达大学（UF）稀疏矩阵集合[10]。我们将这些图分为两类，一类是2D/3D网状结构问题，另一类是来自web或引文网络的不规则度分布图。这些细节大部分都在UF集合中指定。DIMACS10挑战子集合中有一组图表，它们似乎具有2D/3D结构，尽管它们没有被归类为我们所包含的2D/3D图表。仅使用UF集合中的未加权邻接矩阵并将其转换为拉普拉斯矩阵。在某些情况下，有向图通过加上转置来对称。第二组图是使用Feastpack图生成器[20,25]生成的Block Two-Level Erdös r<s:1> (BTER)图。该生成器被设计用于生成具有度分布和聚类属性的图，类似于包含在不规则UF集中的现实世界网络。图的生成基于以下输入参数：近似顶点数、平均度、最大度、最大聚类系数和全局聚类系数。它给出了广义对数正态分布和离散幂律分布之间的选择；我们总是选择前者。我们试图生成具有Kolda等人所描述的真实参数的图形，根据我们从UF不规则测试集中使用的图形对它们进行建模。我们这样做是为了比较原始图和设计用来模拟它们的合成图之间的性能。第三组图源于图像分割问题。通过将像素视为顶点，用它们之间的正权边来度量不相似性，可以将图像视为图。我们使用Felzenszwalb和Huttenlocher的图像分割代码[12]从图像中生成图形。图形以原始图像的主题命名：猫、城市、食物和空间图像。这些图都是9点网格。他们对我们的实验感兴趣的不是他们的结构，而是他们的边权，因为这是我们唯一的加权图的测试集。
Solving Laplacian linear systems is an important task in a variety of practical and theoretical applications. This problem is known to have solutions that perform in linear times polylogarithmic work in theory, but these algorithms are difficult to implement in practice. We examine existing solution techniques in order to determine the best methods currently available and for which types of problems are they useful. We perform timing experiments using a variety of solvers on a variety of problems and present our results. We discover differing solver behavior between web graphs and a class of synthetic graphs designed to model them. 1 Graph Laplacians and SDD Systems The Laplacian matrix of a weighted, undirected graph G is defined as LG = DG−AG, where DG is the diagonal matrix containing the sum of incident edge weights and AG is the weighted adjacency matrix. LG is a symmetric, positive semidefinite, diagonally dominant M-matrix, with a nullspace containing the constant vector. Solving linear systems on the Laplacians of structured graphs, such as two and three dimensional meshes, has long been important in finite element analysis (with applications in electrical and thermal conductivity, and fluid flow modeling [5]) and image processing (with applications in image segmentation, inpainting, regression, and classification [22]). More recently, solving linear systems on the Laplacians of large graphs without mesh-like structure has ∗Sandia is a multi-program laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000. †Partially supported by Intel Corp. and Contract #DEAC02-05CH11231 from DOE Office of Science. emerged as an important computational task in network analysis (with applications to maximum flow problems [8], graph sparsification [26], and spectral clustering [19].) Interest in solving Laplacians is closely associated with interest in solving slightly more general symmetric diagonally dominant (SDD) matrices. A matrix A is SDD if A = A and ai,i ≥ ∑ i6=j |ai,j |. One way of solving these problems is to first reduce them to a Laplacian matrix [3, 13] and then solve them with a Laplacian solver. Some of the Laplacian linear systems in the applications above derive from SDD linear systems. Since the reduction from an SDD matrix to a graph Laplacian is asymptotically cheap, the theoretically best SDD solvers rely on Laplacian solvers. In the last few decades the theoretical computer science community has done significant work on asymptotically efficient Laplacian solvers. Spielman and Teng [27] showed how to solve these problems in linear times polylogarithmic work, later improved upon by Koutis, Miller, and Peng [21], but these algorithms have complicated descriptions and suspected large constants, preventing their practical implementation. An algorithm proposed by Kelner et al. [18] has the advantage of a simple algorithm description, but initial experimental results [4, 16] suggest it will have trouble competing in practice. To our knowledge there is not a comprehensive experimental study of available solvers. Our goal is to provide an initial understanding of available solvers, and to determine where ideas from more theoretical solvers could be leveraged to make improvements in practice. We believe it is important to procure a set of test problems from relevant applications, and a set of performance metrics for evaluating current and future Laplacian solver performance on these test problems. We hope to understand how Laplacian solver performance varies depending on the category of test problem. This is ongoing work and we envision this paper as a living document that will iteratively improve to incorporate new solvers, better test problems, and more useful performance analysis. To that end, the authors welcome feedback on how to improve our understanding of Laplacian solvers. 2 Test Graphs/Matrices For this first round of experiments we only use graphs/matrices that come to us as graph Laplacians, and adjacency matrices that can be easily converted to graph Laplacians. We use graphs with between 10 thousand edges and 10 million edges. Larger graphs are left for future parallel experiments. We use only the largest connected component of each graphs to ensure nullspace dimension of one. We put together four sets of test graphs/matrices in these experiments from three different sources. The first source is the University of Florida (UF) sparse matrix collection [10]. We divide these graphs into two categories, 2D/3D mesh-like structural problems, and graphs with irregular degree distributions that come from web or citation networks. For the most part these details are specified in the UF collection. There is a set of graphs from the DIMACS10 challenge subcollection which appear to have 2D/3D structure even though they are not classified as such that we include under 2D/3D graphs. Only unweighted adjacency matrices from the UF collection were used and converted to Laplacians. In some cases directed graphs were symmetrized by adding the transpose. The second set of graphs are Block Two-Level Erdös Rényi (BTER) graphs generated with the Feastpack graph generator [20, 25]. This generator was designed to produce graphs with degree distributions and clustering properties similar to the real world networks included in the irregular UF set. A graph is generated based on the following input parameters: approximate number of vertices, average degree, maximum degree, maximum clustering coefficient, and global clustering coefficient. It gives a choice between a generalized log normal distribution and a discrete power law distribution; we always choose the former. We attempted to generate graphs with realistic parameters as described by Kolda et al. [20], modeling them after the graphs we use from the UF irregular test set. We do this to compare performance between the original graphs and the synthetic graphs designed to model them. The third set of graphs arises from image segmentation problems. An image can be considered as a graph by treating pixels as vertices, with positive weight edges between them measuring dissimilarity. We use Felzenszwalb and Huttenlocher’s image segmentation code [12] to produce graphs from images. Graphs are named after the subject of the original image: cats, cities, food, and space images. These graphs are all 9 point meshes. Their interest for our experiments is not their structure, but rather their edge weights as this is our only test set of weighted graphs.