Gel'fand's inverse problem for the graph Laplacian

Emilia Blåsten, Hiroshi Isozaki, Matti Lassas, Jinpeng Lu

Abstract

We study the discrete Gel'fand's inverse boundary spectral problem of determining a finite weighted graph. Suppose that the set of vertices of the graph is a union of two disjoint sets: $X=B\cup G$, where $B$ is called the set of the boundary vertices and $G$ is called the set of the interior vertices. We consider the case where the vertices in the set $G$ and the edges connecting them are unknown. Assume that we are given the set $B$ and the pairs $(\lambda_j,\phi_j|_B)$, where $\lambda_j$ are the eigenvalues of the graph Laplacian and $\phi_j|_B$ are the values of the corresponding eigenfunctions at the vertices in $B$. We show that the graph structure, namely the unknown vertices in $G$ and the edges connecting them, along with the weights, can be uniquely determined from the given data, if every boundary vertex is connected to only one interior vertex and the graph satisfies the following property: any subset $S\subseteq G$ of cardinality $|S|\geqslant 2$ contains two extreme points. A point $x\in S$ is called an extreme point of $S$ if there exists a point $z\in B$ such that $x$ is the unique nearest point in $S$ from $z$ with respect to the graph distance. This property is valid for several standard types of lattices and their perturbations.

Introduction

The inverse boundary spectral problem, famously posed by Gel'fand, asks whether one can determine the internal properties of an object—such as its shape or conductivity—solely from measurements taken at its boundary. In the discrete realm, this translates to reconstructing the topology and edge weights of a finite graph from its "vibrational" data: the eigenvalues of the graph Laplacian and the values of the corresponding eigenfunctions at boundary nodes. While historically challenging due to "isospectral" graphs (different structures with identical spectra), this paper identifies a geometric condition that ensures unique reconstruction.

The Two-Points Condition and Boundary Control

The authors utilize the Boundary Control (BC) method, which treats the graph as a dynamic system where waves propagate from the boundary into the interior. A central innovation is the "Two-Points Condition." This condition requires that any subset of at least two interior vertices must contain at least two "extreme points"—nodes that are the unique closest neighbors to specific boundary points.

Illustration of the extreme point concept: boundary vertices (white) and their unique nearest interior neighbors (black) within a subset.

By analyzing the "arrival times" of waves traveling through the network, the researchers can effectively "triangulate" the position and connectivity of every hidden node. This sonar-like mapping process breaks the symmetries that typically lead to non-uniqueness in inverse problems.

Reconstructing Lattice Structures and Defects

The theoretical results are particularly relevant for physical systems modeled as lattices, such as graphene or crystal structures. The paper proves that standard square, hexagonal, and triangular lattices satisfy the necessary geometric conditions for unique reconstruction.

A comparison showing a perfect hexagonal lattice (left) and a lattice with internal defects (right), both of which can be uniquely identified using boundary spectral data.

Crucially, the method is robust enough to handle "perturbed" lattices—structures with missing edges or local defects. This suggests significant potential for non-destructive testing in material science, where one might detect microscopic flaws in a material like graphene by measuring its macroscopic vibrational response at the edges.

Conclusion and Future Directions

The study establishes that for a wide class of graphs, the internal geometry and physical parameters (weights and potentials) are fully encoded in the boundary spectral data. While some complex structures like the Kagome lattice may require additional boundary nodes to satisfy the Two-Points Condition, the current framework provides a rigorous foundation for solving discrete inverse problems. Future work may extend these techniques to more complex boundary interfaces and real-world scattering matrix data for nanotechnology applications.

Summary updated

Abstract

We study the discrete Gel'fand's inverse boundary spectral problem of determining a finite weighted graph. Suppose that the set of vertices of the graph is a union of two disjoint sets: $X=B\cup G$, where $B$ is called the set of the boundary vertices and $G$ is called the set of the interior vertices. We consider the case where the vertices in the set $G$ and the edges connecting them are unknown. Assume that we are given the set $B$ and the pairs $(λ_j,ϕ_j|_B)$, where $λ_j$ are the eigenvalues of the graph Laplacian and $ϕ_j|_B$ are the values of the corresponding eigenfunctions at the vertices in $B$. We show that the graph structure, namely the unknown vertices in $G$ and the edges connecting them, along with the weights, can be uniquely determined from the given data, if every boundary vertex is connected to only one interior vertex and the graph satisfies the following property: any subset $S\subseteq G$ of cardinality $|S|\geqslant 2$ contains two extreme points. A point $x\in S$ is called an extreme point of $S$ if there exists a point $z\in B$ such that $x$ is the unique nearest point in $S$ from $z$ with respect to the graph distance. This property is valid for several standard types of lattices and their perturbations.
BibTeX
@article{blasten2023gel,
  author = {Emilia Blåsten and Hiroshi Isozaki and Matti Lassas and Jinpeng Lu},
  title = {{Gel'fand's inverse problem for the graph Laplacian}},
  journal = {Journal of Spectral Theory},
  year = {2023},
  doi = {10.4171/jst/455},
}
Figure