More Like this

1. Graph diffusion distance: Properties and efficient computation

   https://doi.org/10.1371/journal.pone.0249624  

   Scott, C. B.; Mjolsness, Eric (April 2021, PLOS ONE)

   Oliva, Gabriele (Ed.)

   We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponential matrices, under norm-preserving and sparsity constraints. Variants of the distance metric are introduced to consider such optimized maps under sparsity constraints as well as fixed time-scaling between the two Laplacians. The objective function of this optimization is multimodal and has discontinuous slope, and is hence difficult for univariate optimizers to solve. We demonstrate a novel procedure for efficiently calculating these optima for two of our distance measure variants. We present numerical experiments demonstrating that (a) upper bounds of our distance metrics can be used to distinguish between lineages of related graphs; (b) our procedure is faster at finding the required optima, by as much as a factor of 10 3 ; and (c) the upper bounds satisfy the triangle inequality exactly under some assumptions and approximately under others. We also derive an upper bound for the distance between two graph products, in terms of the distance between the two pairs of factors. Additionally, we present several possible applications, including the construction of infinite “graph limits” by means of Cauchy sequences of graphs related to one another by our distance measure. 

   more » « less
2. Frames for Signal Processing on Cayley Graphs

   https://doi.org/10.1007/s00041-024-10128-5  

   Beck, Kathryn; Ghandehari, Mahya; Hudson, Skyler; Paltenstein, Jenna (December 2024, Journal of Fourier Analysis and Applications)

   The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descrip- tions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal re- construction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction. 

   more » « less
3. Sparse High Dimensional Expanders via Local Lifts

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.68  

   Ben_Yaacov, Inbar; Dikstein, Yotam; Maor, Gal (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kumar, Amit; Ron-Zewi, Noga (Ed.)

   High dimensional expanders (HDXs) are a hypergraph generalization of expander graphs. They are extensively studied in the math and TCS communities due to their many applications. Like expander graphs, HDXs are especially interesting for applications when they are bounded degree, namely, if the number of edges adjacent to every vertex is bounded. However, only a handful of constructions are known to have this property, all of which rely on algebraic techniques. In particular, no random or combinatorial construction of bounded degree high dimensional expanders is known. As a result, our understanding of these objects is limited. The degree of an i-face in an HDX is the number of (i+1)-faces that contain it. In this work we construct complexes whose higher dimensional faces have bounded degree. This is done by giving an elementary and deterministic algorithm that takes as input a regular k-dimensional HDX X and outputs another regular k-dimensional HDX X̂ with twice as many vertices. While the degree of vertices in X̂ grows, the degree of the (k-1)-faces in X̂ stays the same. As a result, we obtain a new "algebra-free" construction of HDXs whose (k-1)-face degree is bounded. Our construction algorithm is based on a simple and natural generalization of the expander graph construction by Bilu and Linial [Yehonatan Bilu and Nathan Linial, 2006], which build expander graphs using lifts coming from edge signings. Our construction is based on local lifts of high dimensional expanders, where a local lift is a new complex whose top-level links are lifts of the links of the original complex. We demonstrate that a local lift of an HDX is also an HDX in many cases. In addition, combining local lifts with existing bounded degree constructions creates new families of bounded degree HDXs with significantly different links than before. For every large enough D, we use this technique to construct families of bounded degree HDXs with links that have diameter ≥ D. 

   more » « less
4. All finite transitive graphs admit a self-adjoint free semigroupoid algebra

   https://doi.org/10.1017/prm.2020.20  

   Dor-On, Adam; Linden, Christopher (February 2021, Proceedings of the Royal Society of Edinburgh: Section A Mathematics)

   Abstract In this paper we show that every non-cycle finite transitive directed graph has a Cuntz–Krieger family whose WOT-closed algebra is $$B(\mathcal {H})$$ . This is accomplished through a new construction that reduces this problem to in-degree 2-regular graphs, which is then treated by applying the periodic Road Colouring Theorem of Béal and Perrin. As a consequence we show that finite disjoint unions of finite transitive directed graphs are exactly those finite graphs which admit self-adjoint free semigroupoid algebras. 

   more » « less
5. Graphs that are cospectral for the distance Laplacian

   https://doi.org/10.13001/ela.2020.4941  

   Brimkov, Boris; Duna, Ken; Hogben, Leslie; Lorenzen, Kate; Reinhart, Carolyn; Song, Sung-Yell; Yarrow, Mark (January 2020, The Electronic Journal of Linear Algebra)

   null (Ed.)

   The distance matrix $$\mathcal{D}(G)$$ of a graph $$G$$ is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is $$\mathcal{D}^L (G)=T(G)-\mathcal{D} (G)$$, where $T(G)$ is the diagonal matrix of row sums of $$\mathcal{D}(G)$$. Several general methods are established for producing $$\mathcal{D}^L$$-cospectral graphs that can be used to construct infinite families. Examples are provided to show that various properties are not preserved by $$\mathcal{D}^L$$-cospectrality, including examples of $$\mathcal{D}^L$$-cospectral strongly regular and circulant graphs. It is established that the absolute values of coefficients of the distance Laplacian characteristic polynomial are decreasing, i.e., $$|\delta^L_{1}|\geq \cdots \geq |\delta^L_{n}|$$, where $$\delta^L_{k}$$ is the coefficient of $x^k$. 

   more » « less