🔢 mathematics

An inverse problem for fractional random walks on finite graphs

This paper investigates an inverse problem on finite graphs where partial observations of a fractional random walk are used to determine the graph's structure and conductivity, establishing that the transition matrix can be identified up to a gauge class and fully recovering the graph and conductivity when the transition matrix is known.

Original authors: Giovanni Covi, Matti Lassas

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Giovanni Covi, Matti Lassas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery inside a closed city. You can't see the whole city, and you can't walk the streets yourself. All you have is a group of spies (the "random walkers") who start at various points and wander around.

Here is the twist: These spies are supernatural. Unlike normal people who can only walk to the next house down the street, these spies can teleport. They can jump from one end of the city to the other in a single step, though the further they jump, the less likely they are to do it. This is what the paper calls a "fractional random walk."

Furthermore, the city has invisible "conductivity" values on every building. Some buildings are like magnets that attract the spies, while others repel them. This conductivity changes how likely a spy is to jump from one building to another.

The Mystery:
You are standing on a small, fixed island of buildings (the "observable set"). You can only see the spies when they land on your island. You cannot see them when they are in the rest of the city.

Your goal is to figure out three things just by watching the spies land on your island:

How big is the whole city? (How many buildings are there in total?)
What is the map? (Which buildings are connected by roads?)
What are the magnetic strengths? (What are the conductivity values of every building?)

The Big Discovery

The authors of this paper, Giovanni Covi and Matti Lassas, have solved this mystery. Here is how they did it, broken down into simple concepts:

1. The "Magic of Three Steps"

In a normal city where you can only walk to the next door, if you want to know about a building 10 blocks away, you need to watch the spies for 10 steps. But because our spies can teleport, they can reach any part of the city very quickly.

The authors proved a surprising fact: You only need to watch the spies for 3 jumps.

Jump 1: Tells you about buildings right next to your island.
Jump 2: Tells you about buildings two steps away (or one teleport away).
Jump 3: This is the magic number. By the third jump, the spies have bounced around enough that the pattern of their landings on your island contains all the information needed to reconstruct the entire city map and the magnetic strengths. Watching them for 4, 5, or 100 jumps doesn't give you any new clues; it's just redundant.

2. The "Shadow" Problem (The Gauge Class)

There is a catch. When you look at the data, you can't find one single unique map. Instead, you find a whole family of maps that look exactly the same from your island's perspective.

Think of it like looking at a shadow on a wall. You can see the shape of the shadow perfectly, but you don't know if the object casting it is a tall, thin person or a short, wide person wearing a hat. The "shadow" (your data) is the same for both.

The paper shows that while you can't know the exact conductivity of every building, you can know the shape of the city and the relative strengths of the magnets. You can say, "Building A is twice as magnetic as Building B," even if you don't know the exact number.

3. Finding the Edges (The Map)

Once you have the "shadow" data, how do you draw the map?
The authors used a clever trick involving the "leaves" of the graph. In graph theory, a "leaf" is a building with only one road connecting to it (like a dead-end street).

They realized that by analyzing how the spies jump between these dead-ends and their neighbors, they could mathematically "peel back" the layers of the city. They proved that if the city isn't too simple (it can't be a perfect star shape), you can uniquely identify every single road (edge) and every single building, even the ones you can't see.

Why Does This Matter?

This paper is a stepping stone for a much bigger problem in physics and mathematics called the Fractional Calderón Problem.

The Real World: Imagine trying to see inside a human body (like a brain) without cutting it open. You put sensors on the skin (the "observable set") and send in electrical signals. You want to know if there is a tumor (a change in conductivity) deep inside.
The Connection: The math used in this paper (on graphs) is a simplified, discrete version of the math used for the human body (on continuous surfaces). By solving the puzzle on the graph first, the authors are building the tools needed to solve the much harder, real-world medical imaging problem.

Summary Analogy

Imagine you are in a dark room with a few light switches you can see. You can't see the rest of the room, but you know that when you flip a switch, a light bulb somewhere else in the room turns on. Sometimes the light is bright, sometimes dim.

The paper says: "If you flip the switches you can see, and watch which lights turn on after 3 flips, you can figure out exactly how many light bulbs are in the room, where they are connected, and how bright they are, even though you can't see the dark parts of the room."

It turns a seemingly impossible puzzle into a solvable one, using the power of "teleporting" spies and a little bit of algebra.

1. Problem Statement

The paper addresses a geometric inverse problem on a finite, connected graph $G = (X, E)$ . The goal is to recover the structural and physical properties of the graph from partial observations of a fractional random walk.

The System: A random walk $\{H^x_0\}_{t \in \mathbb{N}}$ starts at a vertex $x_0$ . Unlike classical random walks restricted to adjacent vertices, this walk allows long jumps.
The Conductivity: A conductivity function $\gamma: X \to (0, \infty)$ is defined on the vertices.
Transition Probability: The probability $P(x, y)$ of jumping from $x$ to $y$ depends on the conductivity and the graph distance $d_G(x, y)$ :
$P(x, y) = \frac{1}{m(x)} \frac{\gamma^{1/2}(x)\gamma^{1/2}(y)}{d_G(x, y)^\alpha}$
where $\alpha > 0$ is a fixed fractional power, and $m(x)$ is a normalization constant ensuring the matrix is row-stochastic.
The Data: Observations are limited to a subset of vertices $B \subseteq X$ (the "observable" set). The data consists of the transition probabilities between any pair of vertices in $B$ after $k$ steps, denoted as the sequence of sub-matrices $\Lambda_\omega(P) = \{(P^k)_{11}\}_{k \in \mathbb{N}}$ .
The Objective: Recover the total number of vertices $|X|$ , the edge set $E$ , and the conductivity $\gamma$ (up to a positive scaling factor) solely from the partial data $\Lambda_\omega(P)$ .

2. Methodology

The authors employ a combination of linear algebra, graph theory, and nonlocal operator theory. The methodology proceeds in three main stages:

A. Algebraic Characterization of Data (Gauge Class)

The authors first analyze the relationship between the observed data $\Lambda_3(P)$ (data from 1, 2, and 3 steps) and the full transition matrix $P$ .

Block Decomposition: They split $P$ into blocks based on observable ( $B$ ) and unobservable ( $X \setminus B$ ) vertices:
$P = \begin{pmatrix} P_{11} & P_{12} \\ P_{21} & P_{22} \end{pmatrix}$
Reconstruction of Products: Using the Markov property, they express products like $P_{12}P_{21}$ and $P_{12}P_{22}P_{21}$ entirely in terms of the observable blocks $(P^k)_{11}$ .
Full Rank Factorization: By utilizing the Moore-Penrose pseudoinverse and full-rank factorization, they prove that if the data matches for $k=1, 2, 3$ , the unknown matrices $P$ and $\tilde{P}$ are related by a specific gauge transformation:
$P = (I_N \oplus A) \tilde{P} (I_N \oplus A^{-1})$
where $A$ is an invertible matrix acting on the unobservable subspace. This establishes that the data determines a gauge class of transition matrices, not a unique matrix.

B. Characterization of Valid Transition Matrices

Not all matrices in the gauge class correspond to a valid physical system (a graph with a conductivity). The authors derive necessary and sufficient conditions for a matrix to be a valid transition matrix derived from a symmetric interaction matrix $C$ :

Positivity: $P > 0$ .
Row-Stochasticity: $P\mathbf{1} = \mathbf{1}$ .
Transitivity: The Hadamard quotient $\hat{P} = P \oslash P^T$ must be a transitive matrix (satisfying $\hat{P}_{ik}\hat{P}_{kj} = \hat{P}_{ij}$ ).
These conditions restrict the gauge group $A$ to matrices that preserve these properties (specifically, $A$ must be row-stochastic).

C. Geometric Recovery (Edge Set and Conductivity)

Once the transition matrix $P$ (or the equivalent interaction matrix $C$ ) is identified up to the gauge, the authors recover the graph structure:

Leaf Identification: They define a ratio function $R_{ab}$ derived from the interaction matrix. By analyzing the extremal values of this ratio, they can distinguish leaves (vertices with degree 1) from their neighbors.
Distance Recovery: Using the identified leaves and the known functional form of the transition probability (which involves $d_G(x,y)^{-\alpha}$ ), they reconstruct the graph distance $d_G(x, y)$ for all pairs.
Edge and Conductivity Recovery: Once distances are known, the edge set $E$ is recovered (edges exist where distance is 1). The conductivity $\gamma$ is then recovered up to a global multiplicative constant.

3. Key Contributions and Results

Theorem 1.2 (Uniqueness and Reconstruction)

Under specific "admissibility" conditions on the graph (related to the rank of sub-matrices and the existence of leaves with sufficient eccentricity):

Cardinality: The total number of vertices $|X|$ can be computed directly from the data.
Gauge Class: The data $\Lambda_3(P)$ determines the transition matrix $P$ up to the gauge transformation $g(A, \tilde{P})$ .
Full Reconstruction: If the transition matrix $P$ is known (i.e., the gauge is fixed), the edge set $E$ and the conductivity $\gamma$ (up to a positive factor) are uniquely recoverable.

Theorem 1.3 (Characterization of Data)

This is a central theoretical result stating that data from $k=3$ steps is sufficient to characterize the entire transition matrix up to the gauge class.

Surprising Nonlocality: In classical random walks, 3 steps only reveal information about vertices within distance 3. In this fractional setting, the data $\Lambda_3(P)$ contains enough information to reconstruct the global structure because the "long jumps" allow the walker to probe distant parts of the graph immediately.
Redundancy: Data for $k > 3$ is redundant; it adds no new information for reconstruction.

Admissibility Conditions

The authors introduce conditions (A1) and (A2) to ensure the problem is well-posed:

(A1) The block $P_{12}$ has full column rank (a property of the graph topology, independent of $\gamma$ ).
(A2) The graph has at least two leaves, and the maximum eccentricity of a leaf is greater than 3.

4. Significance and Implications

Fractional Calderón Problem on Graphs: This work serves as a discrete analog to the fractional Calderón problem in continuous Riemannian manifolds. It provides a stepping stone for understanding inverse problems involving fractional operators (like the fractional Laplacian) in the Riemannian setting.
Nonlocal Inverse Problems: The paper highlights a fundamental difference between local and nonlocal inverse problems. In local settings (classical random walks), one needs infinite data to see the whole graph. In fractional settings, a finite amount of data ( $k=3$ ) suffices due to the nonlocal nature of the operator.
Applications: The framework is relevant to:
- Network Tomography: Inferring network topology from end-to-end measurements.
- Anomalous Diffusion: Modeling systems where particles make long jumps (e.g., in porous media or biological systems).
- Electrical Impedance Tomography (EIT): Discrete versions of recovering conductivity in resistor networks.
Future Directions: The authors propose using these graph results to approximate fractional conductivity operators on continuous manifolds via homogenization techniques, potentially offering new proofs for the Unique Continuation Property (UCP) in fractional PDEs.

5. Conclusion

Covi and Lassas successfully demonstrate that the inverse problem for fractional random walks on finite graphs is solvable. They prove that partial observations of long-jump random walks uniquely determine the graph's topology and conductivity (up to scaling), provided the graph satisfies mild structural conditions. The work bridges discrete graph theory and continuous fractional calculus, offering new insights into the nature of nonlocal inverse problems.