Local ultrametric approximation of graph distance based Laplacian diffusion

Patrick Erik Bradley · 2024

Read Local ultrametric approximation of graph distance based Laplacian diffusion by Patrick Erik Bradley (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20591.txt.

Description

Abstract The error estimation for eigenvalues and eigenvectors of a small positive symmetric perturbation on the spectrum of a graph Laplacian is related to Gauß hypergeometric functions. Based on this, a heuristic polynomial-time algorithm for finding an optimal locally ultrametric approximation of a graph-distance power Laplacian matrix via the Vietoris-Rips graph based on the graph distance function is proposed.

Catalog record

CREATORPatrick Erik Bradley
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20591

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Local ultrametric approximation of graph distance based Laplacian diffusion Patrick Erik Bradley Abstract The error estimation for eigenvalues and eigenvectors of a small positive symmetric perturbation on the spectrum of a graph Laplacian is related to Gauß hypergeometric functions. Based on this, a heuristic polynomial-time algorithm for finding an optimal locally ultrametric approximation of a graph-distance power Laplacian matrix via the Vietoris-Rips graph based on the graph distance function is proposed. In the end, the error in the solution to the graph Laplacian heat equation given by extension to a locally p p -adic equation is estimated. Keywords: Complex systems, ultrametric analysis, graph theory, diffusion, Laplacian spectrum, hypergeometric functions 1 Introduction Complex systems, whether living or not, can under certain aspects be viewed as large networks. These in turn can be modelled as edge-weighted graphs. In order to simulate processes on complex systems, the graph Laplacian corresponding to the underlying network needs to be processed, as it appears in many equations describing processes, like e.g. diffusion. An important step is the computation of eigenvalues of the graph Laplacian. In the case of a very large graph, this is prohibitively inefficient. For this reason, approximative methods for eigenvalue computations are helpful. However, if the kernel function of the graph Laplacian is a function of an ultrametric distance on the vertex set, then this computational issue is much more tractable. The discrepancy between a finite metric and a global ultrametric might be too large, as is known in cluster analysis, here it is proposed to use a more optimal local ultrametric. The last ingredient is the theory of p -adic graph Laplacians which embeds the discrete graph theory into an analytic theory on continuous spaces. This can be used as a framework in order to capture finite graphs with an indefinite number of vertices and edges, or in order to allow for graph updates. The latter leads to a p -adic theory of diffusion on time-dependent graphs [ 8 , 15 ] . The context of this work is in the application of ultrametric analysis to complex systems, and concretely in the project Distributed Simulation of Processes in Buildings and City Models this theory is proposed as a means to efficiently effect parallel computations of process simulations like heat flows on large graph datasets and includes the assessment of errors with respect to equations with actual, but large, graph Laplacians. The topologies of a building or city model are finite and satisfy the T_{0} -separation axiom, and such have a natural graph representation, as was observed by Alexandrov [ 2 ] . Inspired by [ 19 , 20 ] , ultrametric diffusion on multiple T_{0} -topologies on a finite set is introduced and studied in [ 7 ] . What would be of interest is to be able to view the theory of ultrametric diffusion on graph-represented topologies as approximating Brownian motion on continuous ultrametric spaces via some kind of scaling limit, similarly as in [ 17 ] for the p -adic numbers or [ 16 ] for the p -adic integers, and furthermore to view this in some way as an approximation to classical Brownian motion on continuous real spaces. The aims of the present article can be summarised as follows: 1. Partition a finite weighted graph in such a way that each piece as well as the quotient graph whose vertices are those pieces, are as ultrametric as possible. 2. Estimate the error in the solution of the heat equation where the Laplacian kernel function is a power of the inverse graph distance between vertices by approximating the graph distance with its subdominant ultrametric. This approach relates locally hierarchic data to Mumford curves via local p -adic encodings of and suitable Radon measures on the pieces within an infinite compact space, as described in [ 7 , 6 ] . The analytic approach can be summarised as follows: Given a finite metric space (X,d) and its subdominant ultrametric space (X,\delta) , the corresponding adjacency matrices A_{d} and A_{\delta} satisfy: A_{d}=A_{\delta}+A_{\varepsilon} where \varepsilon(x,y)=d(x,y)-\delta(x,y) for x,y\in X . Then use perturbation theory as in [ 5 ] and [ 10 , II.1] to approximate the spectrum of the corresponding Laplacian L_{d} . The two matrices A_{d} and A_{\delta} share a common minimum spanning tree (MST) T , on which d(x,y)=\delta(x,y) for any edge (x,y) of T . The first aim is now placed into this context as follows: Given an edge-weighted finite simple graph G=(V,E,w) , partition the vertex set V : V=\bigsqcup\limits_{i=1}^{m}V_{i} and obtain the following induced subgraphs: G_{i}=(V_{i},E_{i},w_{i}) by restriction, and the quotient graph H=(V_{H},E_{H},w_{H}) with V_{H}={\left\{V_{1},\dots,V_{\left\lvert V\right\rvert}\right\}} and w_{H}(e)=\min{\left\{w(e^{\prime})\mid\text{$e^{\prime}\in E(G)$ between representatives of $o(e)$ and $t(e)$}\right\}} where o(e) and t(e) denote the origin and the terminus of edge e , respectively. The task is now to replace each adjacency matrix of G_{i} , as well as that of H with the subdominant ultrametric of the induced graph distance on G_{i} and then to approximate the spectrum using perturbation theory. The deriviation of error bounds for approximating the solutions of the heat equation for G with solutions of the new ultrametric Laplacian heat equations is tackled in two ways: first, a general upper bound is proven for each coefficient in the analytic expansion of eigenvalues. This leads to hypergeometric functions, cf. e.g. [ 18 ] , and is a result of independent interest. Based on this, the second approach is to give intervals containing the perturbed eigenvalues, and this comes from enclosing the graph distance in between its subdominant ultrametric and a minimal larger rescaled version thereof. This then results in an error bound given by this interval. 2 Affine-Linear Matrix Perturbations Let A(t) for t\in T be a family of N\times N matrices in \mathds{C}^{N\times N} . According to [ 14 , Matrix Proposition (e)] , if T=\mathds{R}\ni t\mapsto A(t) is a so-called C^{Q} -curve of Hermitian matrices, then the eigenvalues and the eigenvectors can be chosen to be in the function space C^{Q} which contains the real-analytic functions. A particular instance of this is when A(t) is an affine-linear map: \displaystyle A(t)=A_{0}+tA_{1} (1) with A_{i} symmetric real-valued N\times N -matrices for i=0,1 . Since in this case, the eigenvalues are real-analytic functions, they can in principle be evaluated at t=1 , in order to calculate the eigenvalues of A(1)=A_{0}+A_{2} , or at least, in principle, to estimate the error of approximating eigenvalue \lambda(t) with its constant term \lambda_{0} which is an eigenvalue of A_{0} . In the following, it is assumed that in ( 1 ), A_{1} is positive semi-definite, and speak of a positive perturbation . 2.1 General error bound Using the notation from [ 4 ] , write \Lambda_{k}=\dg\left(V_{0}^{\top}A_{1}V_{k-1}\right) for k\in\mathds{N} , where \dg converts a square matrix to its diagonal part, V_{0} is an orthonormal basis of eigenvectors of the symmetric matrix A_{0} , and \displaystyle V_{k}=V_{0}\left(\Pi^{\dagger 0}\circ V_{0}^{\top}\left(V_{0}\Lambda_{k}+V_{1}\Lambda_{k-1}+\dots+V_{k-1}\Lambda_{1}-A_{1}V_{k-1}\right)\right) (2) cf. [ 4 , §4] . It is assumed that the eigenvalues \lambda(t) and eigenvectors v(t) of A(t) are analytic in t . Then \Lambda_{k} and V_{k} contain the coefficients of their analytic expansions in the diagonal and in the columns, respectively. Using the Frobenius norm \left\|\cdot\right\|_{F} , obtain the following Proposition, where d_{\min} is

Read the complete text