Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space

Anthony Philippakis, Neil Mallinar, Parthe Pandit, Mikhail BelkinarXiv 2024 · DOI · arXiv

Abstract

We study the Laplacian of the undirected De Bruijn graph over an alphabet $A$ of order $k$. While the eigenvalues of this Laplacian were found in 1998 by Delorme and Tillich [1], an explicit description of its eigenvectors has remained elusive. In this work, we find these eigenvectors in closed form and show that they yield a natural and canonical basis for the cut- and cycle-spaces of De Bruijn graphs. Remarkably, we find that the cycle basis we construct is a basis for the cycle space of both the undirected and the directed De Bruijn graph. This is done by developing an analogue of the Fourier transform on the De Bruijn graph, which acts to diagonalize the Laplacian. Moreover, we show that the cycle-space of De Bruijn graphs, when considering all possible orders of $k$ simultaneously, contains a rich algebraic structure, that of a graded Hopf algebra.

Introduction

De Bruijn (dB) graphs are fundamental structures in computer science, with critical applications in bioinformatics for genome assembly and natural language processing for n-gram analysis. These graphs represent the overlaps between strings of length $k$, known as $k$-mers. Despite their importance, the spectral theory of dB graphs has remained incomplete. While the eigenvalues of the dB Laplacian have been known for over 25 years, the corresponding eigenvectors—which describe the graph's connectivity, cuts, and cycles—have lacked a closed-form description.

The De Bruijn graph $G_4$ over a binary alphabet, illustrating the overlap structure between $k$-mers.

Without these eigenvectors, researchers have lacked a canonical method to decompose $k$-mer count vectors or perform harmonic analysis on genomic data. This paper addresses this gap by providing the first closed-form description of these eigenvectors, allowing for a deeper understanding of the graph's structural properties.

Methodology

The authors bridge graph theory and multilinear algebra through several key innovations:

  1. Tensor Duality: Words of length $k$ are treated simultaneously as graph vertices and as order-$k$ tensor products of a vector space. This algebraic framing enables the use of powerful tools from representation theory.
  2. Deletion Operators: The authors define "left" and "right" deletion operators ($\theta_L, \theta_R$) acting on these tensors. They demonstrate that the graph's adjacency, incidence, and Laplacian matrices can be expressed as simple combinations of these operators.
  3. Graph Fourier Transform: By applying a Discrete Fourier Transform (DFT) to the alphabet itself, the authors develop a graph-specific Fourier transform. In this "Fourier space," the complex dB Laplacian simplifies into a "tri-diagonalized" operator.
  4. Toeplitz Decomposition: In the Fourier domain, the Laplacian decomposes into independent, tri-diagonal Toeplitz blocks. These matrices have well-known closed-form eigenvectors involving trigonometric terms, which are then mapped back to the original graph.

Key Theoretical Insights

A central discovery is the "Padded" Basis. Eigenvectors are constructed by taking "Fourier words" (words avoiding specific "average" characters) and padding them with de Bruijn vectors. This process yields a natural, orthogonal basis for the graph's cycle and cut spaces.

A circular string, which can be interpreted as a cycle within the De Bruijn graph structure.

Furthermore, the authors identify a Universal Cycle Basis: the cycle basis constructed for the undirected dB graph Laplacian also serves as a basis for the cycle space of the directed dB graph. This suggests a deep underlying symmetry between the two graph types.

Perhaps most strikingly, the authors reveal that the cycle spaces for all possible values of $k$ form a graded Hopf algebra (specifically a shuffle algebra). This connects the combinatorial structure of strings to advanced fields like quantum field theory and representation theory.

Main Results

The paper establishes several significant mathematical results:

  • Theorem 3.1: Provides explicit, closed-form equations for the eigenvectors of both the vertex and edge Laplacians.
  • Orthogonality: Unlike traditional bases for cycle and cut spaces, the basis derived here is strictly orthogonal, facilitating efficient computation and signal processing.
  • Dimension Proof: A new combinatorial proof is provided for the dimension of the cycle space: $|A|^k - |A|^{k-1} + 1$.
  • Lattice Structure: The authors prove that $k$-mer count vectors form a lattice within the cycle space, establishing these eigenvectors as the mathematically "correct" way to decompose genomic data.

Discussion and Future Directions

While this work focuses on the undirected Laplacian, the resulting cycle basis's applicability to directed graphs is a major step forward. The authors suggest that future research should focus on developing a "discrete exterior calculus" to integrate these findings into practical genomic pipelines.

Additionally, extending this "1D" string analysis to 2D "image patches" could provide new insights into the spectral properties of images in computer vision. Finally, these closed-form expressions offer a promising path for designing new "string kernels" in machine learning, capable of measuring similarity between circular strings across varying lengths simultaneously.

Summary updated

Abstract

We study the Laplacian of the undirected De Bruijn graph over an alphabet $A$ of order $k$. While the eigenvalues of this Laplacian were found in 1998 by Delorme and Tillich [1], an explicit description of its eigenvectors has remained elusive. In this work, we find these eigenvectors in closed form and show that they yield a natural and canonical basis for the cut- and cycle-spaces of De Bruijn graphs. Remarkably, we find that the cycle basis we construct is a basis for the cycle space of both the undirected and the directed De Bruijn graph. This is done by developing an analogue of the Fourier transform on the De Bruijn graph, which acts to diagonalize the Laplacian. Moreover, we show that the cycle-space of De Bruijn graphs, when considering all possible orders of $k$ simultaneously, contains a rich algebraic structure, that of a graded Hopf algebra.
BibTeX
@misc{philippakis2024eigenvectors,
  author = {Anthony Philippakis and Neil Mallinar and Parthe Pandit and Mikhail Belkin},
  title = {{Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space}},
  year = {2024},
  eprint = {2410.07622},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.07622},
}

Loading related content...

Figure