pith. sign in

arxiv: 2408.05072 · v2 · submitted 2024-08-09 · 🧮 math.AP · math.PR

An inverse problem for fractional random walks on finite graphs

Giovanni Covi , Matti Lassas This is my paper

Pith reviewed 2026-05-23 22:27 UTC · model grok-4.3

classification 🧮 math.AP math.PR
keywords inverse problemfractional random walkfinite graphconductivitygauge classtransition probabilityCalderón problemnonlocal property
0
0 comments X

The pith

Partial observations of fractional random walks on finite graphs determine the gauge class of the transition probability matrix P.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that sequences of partial observations of a fractional random walk, restricted to a fixed subset B of vertices, suffice to identify the gauge class of the transition probability matrix P. If P is known, the total number of vertices, the edge set, and the conductivity can be recovered up to a positive scaling factor. The fractional walk incorporates long jumps whose probability falls as a fractional power of graph distance and depends on the conductivity. A reader would care because the result supplies a discrete counterpart to the fractional Calderón problem and isolates a nonlocal feature in how the data relates to P. The argument works on any finite connected graph equipped with such a walk.

Core claim

We show that this kind of random walk data allows for the determination of a gauge class to which the transition probability matrix P belongs. Moreover, if the transition probability matrix P is itself known, then the amount of vertices |X|, the edge set E and the conductivity γ (up to a positive factor) can be recovered. We also show a characterization of the random walk data in terms of the corresponding transition matrices P, which highlights a new surprising nonlocal property.

What carries the argument

The fractional transition probability matrix P, whose entries decrease as a fractional power of graph distance and depend on the conductivity γ, together with the partial observation sequences recorded only on the fixed subset B.

If this is right

  • The gauge class of P is recoverable from the partial random walk data alone.
  • When P is known, the vertex count |X|, edge set E, and conductivity γ up to positive scale follow directly.
  • The observed data admits an exact characterization in terms of P that exhibits a nonlocal property not present in local walks.
  • Recovery holds for every finite connected graph carrying a conductivity and the stated fractional jump rule.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same partial-observation technique could be tested on continuous fractional operators to see whether gauge recovery persists in the Riemannian setting.
  • The nonlocal characterization might be used to design statistical tests that distinguish fractional from local random walks on networks.
  • Fixing the gauge by a normalization condition on P could convert the result into a uniqueness theorem for the matrix itself.

Load-bearing premise

The random walk must be fractional with transition probabilities decreasing as a fractional power of the distance along the graph, and all observations must be limited to one fixed observable subset B of vertices.

What would settle it

Two transition matrices P and P' that lie in distinct gauge classes but generate identical sequences of partial observations on B would falsify the claim that the data determines the gauge class.

Figures

Figures reproduced from arXiv: 2408.05072 by Giovanni Covi, Matti Lassas.

Figure 1.1
Figure 1.1. Figure 1.1: An example of graph as in our assumptions. The observable set B is represented in blue. The total amount of vertices, as well as all the edges and the conductivity, are to be recovered from random walk data. subsequent works [Cov20a, Cov22, CRZ22, CRTZ24] have studied (global) uniqueness and stability for the fractional conductivity equation, while [CdHS22] has introduced an inverse problem for a related… view at source ↗
Figure 4.2
Figure 4.2. Figure 4.2: An example of a graph G = (X, E) satisfying (A1), constructed as in Example 4.4. Here the graph J0 of vertices V0 = X \ B is represented in black, while the observable subgraph (B, E \ E0) is represented in blue. 5. Discussion of the gauge class Let G, γ respectively be a graph and a conductivity, and consider the transition matrix P˜ corresponding to the pair G, γ. Let g : GLM × R (N+M)×(N+M) → R (N+M)×… view at source ↗
Figure 6.3
Figure 6.3. Figure 6.3: An example of graph with two leaf-neighbour pairs highlighted. Here {L1, N1}, {L2, N2} ∈ Y . Observe that the couples are not ordered. Assume {a, b} ∈ Y with Rab > 4/3, and fix any c ∈ X \ {a, b}. Let x ∈ arg min Fabc, and consider the set Z := [ y∈arg max Fabc arg max Fyxa. If a ∈ N, then arg max Fabc = {y ∈ X : y ̸= b, y ∼ a}. Thus the minimum path between a and x must pass through some y ∗ ∈ arg max F… view at source ↗
Figure 6.4
Figure 6.4. Figure 6.4: The situation in the second part of Step 3, when b ∈ L. We have indicated the set arg max Fabc in blue. necessarily if z ∈ arg max Fyxa it must be dG(y, z) = 1 by Step 2, and in particular z /∈ {a, b}. Therefore, {a, b} ∩ Z = ∅ (see figure). b x a z y [PITH_FULL_IMAGE:figures/full_fig_p017_6_4.png] view at source ↗
Figure 6.5
Figure 6.5. Figure 6.5: The situation in the second part of Step 3, when a ∈ L. We have indicated the set arg max Fyxa in blue. By the above argument we are able to distinguish in each pair {a, b} ∈ Y the leaf from its neighbour, in the assumption that Rab > 4/3. Observe that it suffices to correctly identify just one pair belonging to Y in order to completely determine L and N. Thus assuming that maxℓ∈L e(ℓ) > 3 allows us to r… view at source ↗
read the original abstract

We study an inverse problem on a finite connected graph G = (X, E), on whose vertices a conductivity {\gamma} is defined. Our data consists in a sequence of partial observations of a fractional random walk on G. The observations are partial in the sense that they are limited to a fixed, observable subset B of X, while the random walk is fractional in the sense that it allows long jumps with a probability P decreasing as a fractional power of the distance along the graph. The transition probability P also depends on {\gamma}. We show that this kind of random walk data allows for the determination of a gauge class to which the transition probability matrix P belongs, which we discuss. Moreover, we show that if the transition probability matrix P is itself known, then the amount of vertices |X|, the edge set E and the conductivity {\gamma} (up to a positive factor) can be recovered. We also show a characterization of the random walk data in terms of the corresponding transition matrices P , which highlights a new surprising nonlocal property. This work is motivated by the recent strong interest in the study of the fractional Calder\'on problem in the Riemannian setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper studies an inverse problem for fractional random walks on a finite connected graph G=(X,E) with conductivity γ. Data consists of partial observations (limited to a fixed observable subset B ⊂ X) of a nonlocal random walk whose transition probabilities P decrease as a fractional power of graph distance and depend on γ. The central claims are that such data determines a gauge class for P, and that knowledge of P itself permits recovery of |X|, the edge set E, and γ up to positive scalar multiple. A characterization of the observation data in terms of P is also given, emphasizing a nonlocal property. The work is motivated by the fractional Calderón problem.

Significance. If the uniqueness statements hold, the results supply a discrete-graph counterpart to recent uniqueness theorems for the fractional Calderón problem on manifolds. The explicit nonlocal characterization of the data and the gauge-class recovery from partial observations constitute the main technical contributions; the full recovery of the graph and conductivity when P is known is a secondary but clean consequence. The finite-graph setting allows concrete matrix formulations that may be useful for numerical validation or extension to other nonlocal discrete operators.

major comments (2)
  1. [§3, Theorem 3.4] §3, Theorem 3.4: the gauge equivalence relation on P is defined via a diagonal scaling that preserves the fractional kernel form; however, the proof that the partial observations determine precisely this equivalence class appears to rely on an injectivity argument for the map from conductivities to the restricted transition submatrix on B. The argument is not load-bearing if the gauge class is the intended output, but it should be stated whether the scaling factor is uniquely determined or only up to the same positive constant that appears in the conductivity recovery.
  2. [§4, Proposition 4.2] §4, Proposition 4.2: the recovery of |X| and E from a known P uses the support of the fractional powers of the adjacency matrix. The argument assumes that the fractional exponent α is known a priori; if α is also to be recovered from the data, an additional identifiability step is required that is not visible in the current statement.
minor comments (3)
  1. [§2] The notation for the observable set B and the hidden vertices X∖B is introduced in §2 but used without reminder in later statements; a short sentence recalling the partition would improve readability.
  2. [Eq. (2.7)] Equation (2.7) defines the fractional transition kernel; the normalization constant is written as C(α,γ) but its explicit dependence on the conductivity vector γ is not expanded. Adding the formula or a reference to its derivation would clarify the dependence.
  3. [Abstract / §5] The abstract states that the random walk data 'highlights a new surprising nonlocal property.' The corresponding statement in the main text (likely Theorem 5.1) should be cross-referenced in the abstract or introduction for consistency.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: [§3, Theorem 3.4] §3, Theorem 3.4: the gauge equivalence relation on P is defined via a diagonal scaling that preserves the fractional kernel form; however, the proof that the partial observations determine precisely this equivalence class appears to rely on an injectivity argument for the map from conductivities to the restricted transition submatrix on B. The argument is not load-bearing if the gauge class is the intended output, but it should be stated whether the scaling factor is uniquely determined or only up to the same positive constant that appears in the conductivity recovery.

    Authors: We agree that a clarifying statement is warranted. Theorem 3.4 recovers the gauge class of P under the same positive scalar ambiguity that governs the recovery of the conductivity γ. The scaling factor in the gauge equivalence is therefore determined only up to this constant. We will add an explicit remark after the theorem statement in the revised manuscript to make this precise. revision: yes

  2. Referee: [§4, Proposition 4.2] §4, Proposition 4.2: the recovery of |X| and E from a known P uses the support of the fractional powers of the adjacency matrix. The argument assumes that the fractional exponent α is known a priori; if α is also to be recovered from the data, an additional identifiability step is required that is not visible in the current statement.

    Authors: The manuscript treats α as a known parameter fixed in the definition of the fractional random walk. Proposition 4.2 is stated under this hypothesis, and the support argument for recovering |X| and E relies on α being given. Recovering α itself from the data would require a separate identifiability analysis that is not claimed or performed in the paper. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained from setup

full rationale

The provided abstract and claims describe recovery of a gauge class for the transition matrix P and recovery of |X|, E, γ from known P, using partial observations of fractional random walks on finite graphs. No equations, fitted parameters, or self-citation chains are exhibited that reduce any claimed prediction or uniqueness result to the inputs by construction. The finite-graph nonlocal characterization is presented as a direct consequence of the model definition, with motivation from external fractional Calderón literature rather than load-bearing self-citation. This is the normal case of an independent mathematical derivation on a discrete setting.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions from graph theory and Markov chain theory; no free parameters or invented entities are indicated in the abstract.

axioms (1)
  • domain assumption The graph is finite and connected with a conductivity function defined on vertices.
    Basic setup stated in the abstract for the inverse problem.

pith-pipeline@v0.9.0 · 5728 in / 1030 out tokens · 21702 ms · 2026-05-23T22:27:20.320609+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [1]

    On instability properties of the fractional C alder\'on problem

    Hendrik Baers, Giovanni Covi, and Angkana Ruland. On instability properties of the fractional C alder\'on problem. arXiv: 2405.08381 , 2024

    work page arXiv 2024

  2. [2]

    Inverse problems for the fractional-laplacian with lower order non-local perturbations

    Sombuddha Bhattacharyya, Tuhin Ghosh, and Gunther Uhlmann. Inverse problems for the fractional-laplacian with lower order non-local perturbations. Transactions of the American Mathematical Society , 374(5):3053--3075, 2021

    work page 2021

  3. [3]

    Blosten, H

    E. Blosten, H. Isozaki, M. Lassas, and J. Lu. Inverse problems for discrete heat equations and random walks. arXiv:2107.00494 , 2021

    work page arXiv 2021

  4. [4]

    Uniqueness in an inverse problem of fractional elasticity, 2022

    Giovanni Covi, Maarten de Hoop, and Mikko Salo. Uniqueness in an inverse problem of fractional elasticity, 2022

    work page 2022

  5. [5]

    A reduction of the fractional C alder \'o n problem to the local C alder \'o n problem by means of the caffarelli-silvestre extension

    Giovanni Covi, Tuhin Ghosh, Angkana R \"u land, and Gunther Uhlmann. A reduction of the fractional C alder \'o n problem to the local C alder \'o n problem by means of the caffarelli-silvestre extension. 2023

    work page 2023

  6. [6]

    u land. The calder \'o n problem for the fractional S chr \

    Mihajlo Ceki \'c , Yi-Hsuan Lin, and Angkana R \"u land. The calder \'o n problem for the fractional S chr \"o dinger equation with drift. Calculus of Variations and Partial Differential Equations , 59(3):91, 2020

    work page 2020

  7. [7]

    The higher order fractional C alder \'o n problem for linear local operators: uniqueness

    Giovanni Covi, Keijo M \"o nkk \"o nen, Jesse Railo, and Gunther Uhlmann. The higher order fractional C alder \'o n problem for linear local operators: uniqueness. Adv. Math. , 399:Paper No. 108246, 29, 2022

    work page 2022

  8. [8]

    An inverse problem for the fractional S chr \"o dinger equation in a magnetic field

    Giovanni Covi. An inverse problem for the fractional S chr \"o dinger equation in a magnetic field. Inverse Problems , 36(4):045004, 24, 2020

    work page 2020

  9. [9]

    Inverse problems for a fractional conductivity equation

    Giovanni Covi. Inverse problems for a fractional conductivity equation. Nonlinear Anal. , 193:111418, 18, 2020

    work page 2020

  10. [10]

    Uniqueness for the anisotropic fractional conductivity equation

    Giovanni Covi. Uniqueness for the anisotropic fractional conductivity equation. 12 2022

    work page 2022

  11. [11]

    Stability estimates for the inverse fractional conductivity problem

    Giovanni Covi, Jesse Railo, Teemu Tyni, and Philipp Zimmermann. Stability estimates for the inverse fractional conductivity problem. SIAM Journal on Mathematical Analysis , 56(2):2456--2487, 2024

    work page 2024

  12. [12]

    The global inverse fractional conductivity problem

    Giovanni Covi, Jesse Railo, and Philipp Zimmermann. The global inverse fractional conductivity problem. 2022

    work page 2022

  13. [13]

    Qiang Du, Max Gunzburger, R. B. Lehoucq, and Kun Zhou. Analysis and approximation of nonlocal diffusion problems with volume constraints. SIAM Rev. , 54(4):667--696, 2012

    work page 2012

  14. [14]

    Qiang Du, Max Gunzburger, R. B. Lehoucq, and Kun Zhou. A nonlocal vector calculus, nonlocal volume-constrained problems, and nonlocal balance laws. Math. Models Methods Appl. Sci. , 23(3):493--540, 2013

    work page 2013

  15. [15]

    Fractional anisotropic calder\'on problem on closed R iemannian manifolds

    Ali Feizmohammadi, Tuhin Ghosh, Katya Krupchyk, and Gunther Uhlmann. Fractional anisotropic calder\'on problem on closed R iemannian manifolds. arXiv preprint arXiv:2112.03480 , 2021

    work page arXiv 2021

  16. [16]

    Transitive matrices and their applications

    Andr\' a s Farkas, P\' a l R\' o zsa, and Etelka Stubnya. Transitive matrices and their applications. volume 302/303, pages 423--433. 1999. Special issue dedicated to Hans Schneider (Madison, WI, 1998)

    work page 1999

  17. [17]

    F. R. Gantmacher. The theory of matrices. V ol. 2 . AMS Chelsea Publishing, Providence, RI, 1998. Translated from the Russian by K. A. Hirsch, Reprint of the 1959 translation

    work page 1998

  18. [18]

    Uniqueness and reconstruction for the fractional C alder \'o n problem with a single measurement

    Tuhin Ghosh, Angkana R \"u land, Mikko Salo, and Gunther Uhlmann. Uniqueness and reconstruction for the fractional C alder \'o n problem with a single measurement. Journal of Functional Analysis , 279(1):108505, 2020

    work page 2020

  19. [19]

    The C alder \'o n problem for the fractional S chr \"o dinger equation

    Tuhin Ghosh, Mikko Salo, and Gunther Uhlmann. The C alder \'o n problem for the fractional S chr \"o dinger equation. Anal. PDE , 13(2):455--475, 2020

    work page 2020

  20. [20]

    The C alder \'o n problem for nonlocal operators

    Tuhin Ghosh and Gunther Uhlmann. The C alder \'o n problem for nonlocal operators. arXiv preprint arXiv:2110.09265 , 2021

    work page arXiv 2021

  21. [21]

    Monotonicity-based inversion of the fractional S chr \"o dinger equation I

    Bastian Harrach and Yi-Hsuan Lin. Monotonicity-based inversion of the fractional S chr \"o dinger equation I . positive potentials. SIAM Journal on Mathematical Analysis , 51(4):3092--3111, 2019

    work page 2019

  22. [22]

    Monotonicity-based inversion of the fractional S chr \"o dinger equation I I

    Bastian Harrach and Yi-Hsuan Lin. Monotonicity-based inversion of the fractional S chr \"o dinger equation I I . general potentials and stability. SIAM Journal on Mathematical Analysis , 52(1):402--436, 2020

    work page 2020

  23. [23]

    On instability mechanisms for inverse problems

    Herbert Koch, Angkana R \"u land, and Mikko Salo. On instability mechanisms for inverse problems. 2021

    work page 2021

  24. [24]

    Determining the magnetic potential in the fractional magnetic C alder \'o n problem

    Li Li. Determining the magnetic potential in the fractional magnetic C alder \'o n problem. Communications in Partial Differential Equations , 46(6):1017--1026, 2021

    work page 2021

  25. [25]

    On inverse problems arising in fractional elasticity

    Li Li. On inverse problems arising in fractional elasticity. Journal of Spectral Theory , 12(4):1383--1404, 2023

    work page 2023

  26. [26]

    Determining both leading coefficient and source in a nonlocal elliptic equation

    Yi-Hsuan Lin. Determining both leading coefficient and source in a nonlocal elliptic equation. arXiv preprint arXiv:2312.15607 , 2023

    work page arXiv 2023

  27. [27]

    The calder \'o n problem for a space-time fractional parabolic equation

    Ru-Yu Lai, Yi-Hsuan Lin, and Angkana R \"u land. The calder \'o n problem for a space-time fractional parabolic equation. SIAM Journal on Mathematical Analysis , 52(3):2655--2688, 2020

    work page 2020

  28. [28]

    The C alder \'o n problem for nonlocal parabolic operators: A new reduction from the nonlocal to the local

    Ching-Lung Lin, Yi-Hsuan Lin, and Gunther Uhlmann. The C alder \'o n problem for nonlocal parabolic operators: A new reduction from the nonlocal to the local. arXiv preprint arXiv:2308.09654 , 2023

    work page arXiv 2023

  29. [29]

    R. Penrose. A generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society , 51(3):406–413, 1955

    work page 1955

  30. [30]

    Piziak and P

    R. Piziak and P. L. Odell. Full R ank F actorization of M atrices. Math. Mag. , 72(3):193--201, 1999

    work page 1999

  31. [31]

    Exponential instability in the fractional C alder\' o n problem

    Angkana R\" u land and Mikko Salo. Exponential instability in the fractional C alder\' o n problem. Inverse Problems , 34(4):045003, 21, 2018

    work page 2018

  32. [32]

    The fractional C alder\' o n problem: low regularity and stability

    Angkana R\" u land and Mikko Salo. The fractional C alder\' o n problem: low regularity and stability. Nonlinear Anal. , 193:111529, 56, 2020

    work page 2020

  33. [33]

    Quantitative approximation properties for the fractional heat equation

    Angkana R \"u land and Mikko Salo. Quantitative approximation properties for the fractional heat equation. Mathematical Control and Related Fields , 10(1):1--26, 2020

    work page 2020

  34. [34]

    On single measurement stability for the fractional calder\' o n problem

    Angkana R \"u land. On single measurement stability for the fractional calder\' o n problem. SIAM Journal on Mathematical Analysis , 53(5):5094--5113, 2021

    work page 2021

  35. [35]

    From the long jump random walk to the fractional L aplacian

    Enrico Valdinoci. From the long jump random walk to the fractional L aplacian. Bol. Soc. Esp. Mat. Apl. SeMA , (49):33--44, 2009

    work page 2009