Towards joint graph learning and sampling set selection from data

Antonio Ortega; Eduardo Pavez; Shashank N. Sridhara

REVIEW 3 major objections 5 minor 24 references

Towards joint graph learning and sampling set selection from data

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that the vertex-importance weights produced by joint graph and vertex-importance learning can select the sampling set directly, making the conventional learn-then-sample pipeline unnecessary for many reconstruction tasks.

desk verdict The central theoretical link between learned vertex importance and D-optimal sampling is false on a simple example, so the paper's main claim is unsupported; the empirical comparison also conflates sampling method with reconstruction model. read the letter →

arxiv 2412.09753 v2 pith:JFADYUWU submitted 2024-12-12 cs.LG eess.IVeess.SP

Shashank N. Sridhara , Eduardo Pavez , Antonio Ortega This is my paper · ORCID

classification cs.LGeess.IVeess.SP

keywords graphsignalsamplinglearningverteximportancediagonallydominantLaplacianD-optimalitysetselectionreconstructionGaussianMarkovrandomfield

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how to choose which nodes to sample when the graph itself is unknown and must be learned from data. It claims that the vertex-importance values obtained while learning a diagonally dominant graph Laplacian already encode enough information to pick a good sampling set, so a separate sampling step can be skipped. The proposed VIS method takes the k highest-importance nodes; VISR additionally penalizes spatially close selections through a p-hop filter. On synthetic data both reach reconstruction accuracy competitive with, and often better than, the conventional two-step pipeline at lower computational cost. The payoff would be a single learning procedure that outputs both the graph and the sampling set.

What carries the argument

The central object is the diagonally dominant graph Laplacian model $\mathbf{L} + \mathbf{Q}$, where $\mathbf{L}$ is a combinatorial graph Laplacian and $\mathbf{Q}$ is a diagonal matrix of vertex-importance weights. The argument works by comparing the D-optimal sampling objective $-\log\det[\mathbf{H} + \gamma(\mathbf{L}+\mathbf{Q})]$ with the joint learning objective $-\log\det(\mathbf{L}+\mathbf{Q}) + \operatorname{tr}((\mathbf{L}+\mathbf{Q})\mathbf{S})$, and using Weyl's theorem to justify that the largest diagonal entries of $\mathbf{Q}$ indicate the best sampling nodes. For VISR, a p-hop localized polynomial filter $\mathbf{Z}^{(p)} = \sum_{l=1}^p (\mathbf{D}^{-1}\mathbf{A})^l$ provides repulsion by penalizing inner products between selected nodes and candidates.

What would settle it

A reader could test the link directly by generating synthetic graphs where the highest-importance nodes are placed close together, then comparing the D-optimal determinant $\det(\mathbf{H}+\gamma(\mathbf{L}+\mathbf{Q}))$ and the reconstruction MSE achieved by the VIS top-importance set against the greedy D-optimal set and against random sampling with the same reconstruction model; if the top-importance set consistently has a worse determinant or worse MSE, the paper's core premise is refuted.

Watch

Extended reading notes

Core claim

The paper's central claim is that when the graph is unknown, the sampling set can be read off from the vertex-importance weights learned jointly with the graph, rather than by first learning a graph and then running a separate sampling algorithm. The authors show that the D-optimal sampling objective and the joint graph-and-importance learning objective share a similar log-determinant structure, and they argue via Weyl's theorem that the vertices with the largest learned importance values approximately solve the D-optimal sampling problem. On this basis they propose Vertex Importance Sampling (VIS), which selects the highest-importance nodes, and Vertex Importance Sampling with Repulsion (VISR), which adds a p-hop locality penalty so selected nodes are spatially spread. Experiments on simulated data show that VIS and VISR achieve reconstruction accuracy competitive with, and at low sampling budgets better than, a two-step pipeline using combinatorial graph Laplacian learning followed by state-of-the-art sampling algorithms.

Load-bearing premise

The central claim depends on assuming that the nodes with the largest learned importance weights are approximately the nodes that would be chosen by the D-optimal sampling objective; if that approximation fails, the proposed methods have no demonstrated reason to beat other sampling rules.

Editorial extensions

If this is right

Once the diagonally dominant graph Laplacian is learned, the sampling set costs no extra computation because it comes directly from the learned vertex-importance diagonal.
VISR's repulsion mechanism improves reconstruction at higher sampling budgets by preventing spatially clustered selections.
Joint graph-and-importance learning followed by VIS or VISR has lower complexity than learning a combinatorial graph Laplacian and then running an expensive sampling algorithm.
Using $\mathbf{L}+\mathbf{Q}$ for reconstruction outperforms using only $\mathbf{L}$ at all tested noise levels, so the improvement is not solely due to the sampling rule.
At low sampling budgets, VIS and VISR achieve about twice the reconstruction accuracy of existing sampling algorithms that operate on a learned combinatorial Laplacian.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the premise holds, the log-determinant shared by sampling and learning objectives suggests that other optimality criteria, such as A-optimal or E-optimal sampling, could also be mapped onto vertex-importance learning objectives.
A natural extension, which the paper names as future work, is to fold the sampling objective directly into the graph-learning optimization so that sampling set and graph are produced by a single iterative procedure rather than by learning first and then reading off importance.
The reported advantage at low sampling budgets may come mostly from the improved reconstruction model $\mathbf{L}+\mathbf{Q}$; a reader could test this by running VIS with reconstruction using only $\mathbf{L}$ and comparing against random sampling with $\mathbf{L}+\mathbf{Q}$ reconstruction.
The p-hop repulsion rule in VISR is reminiscent of sensor-placement and point-cloud sampling heuristics, so the method may transfer to problems where node locations are available as side information, even when the graph is estimated from data.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a reasonable engineering idea that currently lacks a valid theoretical foundation. The paper proposes VIS and VISR, which use the vertex importance vector q from a jointly learned graph Laplacian L+Q to build sampling sets for graph signal reconstruction. That is a genuine, if modest, extension of your earlier RAGS work, and the algorithms are transparent and cheap. The experimental section is also honest enough to acknowledge that the reconstruction model (L+Q) rather than the sampling rule may be responsible for the gains at low budgets.

The problem is Section 4. The authors argue that because the D-optimal objective (12) and the DDGL learning objective (2) both contain log-determinants, the optimal sampling indices 'most likely' match the largest q_i, with a pointer to Weyl's theorem. That is not a proof, and it is false in general. For k=1, the determinant lemma gives the D-optimal node as argmax_i [(L+Q)^{-1}]_{ii}, which depends on the full inverse, not just q_i. On a 3-node path Laplacian with Q=diag(1,8,1), the inverse diagonal is (0.53,0.11,0.53), so D-opt prefers node 1 or 3 while VIS picks node 2. The trace term being constant at optimality does not create the needed variational connection. So the 'foundational step' is currently an unsupported heuristic.

The experiments do not rescue the claim. In Section 5.2, VIS/VISR reconstruct with Ω=L+Q while all baselines use Ω=L, and the paper explicitly credits the better model for the low-budget advantage. That means the sampling-set-specific value of VIS/VISR is not demonstrated. Figures have no error bars, and no code or parameter values (μ, graph-learning regularization) are given, so the results are hard to reproduce.

What is good: the paper identifies a real cost in the two-step approach, the proposed algorithms are cheap and simple, and the discussion of p-hop repulsion is sensible. The comparison with the greedy D-opt baseline in Figure 3a is at least internally consistent, since all three methods reconstruct with the same model; VISR's advantage there is worth looking at, though the number of runs is small.

Verdict: the paper deserves referee time, because the gap is fixable—add a derivation or a condition under which top-q sets are near-optimal, or reframe the paper as a purely empirical heuristic with matched-model comparisons. As it stands, I would not cite the central claim, but I would bring it to a reading group to discuss the counterexample.

Recommendation: send to peer review with major revision requested.

Referee Report

3 major / 5 minor

Summary. The paper considers the problem of selecting a sampling set for graph signals when the graph itself must be learned from data. Instead of the conventional two-step procedure of learning a graph and then running a sampling algorithm, the authors propose to use the vertex importance weights q_i obtained from joint graph and vertex importance learning (DDGL) to define the sampling set directly. Two algorithms are proposed: VIS, which selects the nodes with the largest q_i, and VISR, which adds a repulsion term based on a p-hop graph filter to spread the selected samples. The authors connect the sampling objective to D-optimality through an approximate error covariance, and they evaluate VIS and VISR against greedy D-optimal sampling and against AVM, BSGDA, and RAGS on synthetic data.

Significance. The problem is well motivated: if sampling sets could be obtained as a byproduct of graph learning, the expensive sampling stage of the two-step approach would be avoided. The algorithms are simple and the same-model comparison in Fig. 3a gives some empirical evidence that VISR is competitive with greedy D-optimal sampling at higher sampling budgets. The authors are also transparent in Section 5.2 that the better reconstruction model L+Q, rather than the sampling set itself, drives the low-budget gains in Fig. 3b. However, the theoretical link between vertex importance and D-optimality is the load-bearing contribution and is currently unsupported; the comparison with external baselines is not matched across reconstruction models, so the paper's central claim is not yet established. If the heuristic link is replaced by a validated approximation or by carefully matched experiments, the work could become a useful practical contribution.

major comments (3)

[Section 4, Eqs. (12) and (2)] The claim that the indices of H_ii=1 maximizing (12) are "most likely" the largest vertex importances q_i is not supported and is false in general. For k=1, the matrix-determinant lemma gives argmax_i logdet(H+γ(L+Q)) = argmax_i [(L+Q)^{-1}]_{ii}, which depends on the full inverse of L+Q and not only on q_i. For the 3-node path Laplacian L with Q=diag(1,8,1), [(L+Q)^{-1}]_{ii}=(0.528,0.111,0.528), so D-optimal sampling selects node 1 or 3, while VIS (13) selects node 2. The observation that the trace term in (2) is constant at optimality does not create a variational link to (12), because (2) contains no H term and the determinant in (12) depends on H through the diagonal of (1/γ)H+Q. A quantitative bound or explicit conditions under which top-q sets are near-optimal is required; otherwise VIS and VISR should be presented as heuristics, with the claim of approximating D-optimality supported by exhaustive small-graph experiments rather than an appeal to Weyl's theorem.
[Section 5.2, Fig. 3b] The comparison against AVM, BSGDA, and RAGS is confounded by the use of different reconstruction models. Baselines reconstruct with Ω1=L, while VIS and VISR use Ω2=L+Q, and the paper itself concludes from Fig. 3c that L+Q is a better reconstruction model. Hence the low-budget gains in Fig. 3b cannot be attributed to the sampling set selected by VIS or VISR. To establish the central claim, the authors should compare all sampling methods under the same reconstruction operator, for example all methods using L+Q or VIS and VISR using L, and ideally report an ablation that fixes the reconstruction model while varying only the sampling set.
[Theorem 3.1, Eq. (8)] The proof of approximation (8) is omitted, with only a reference to Neumann series. Since this approximation is the basis for the D-optimal objective (9) and hence for the entire sampling formulation, the proof should be included rather than deferred. At minimum, the precise condition on μ that makes the Neumann series argument valid should be stated, so that a reader can verify the validity of the approximation instead of taking it on faith from the claim "due to space limitations."

minor comments (5)

[Eq. (9)] The constraint is written as ∑_{k=0}^N H_ii = |S|, which is a typo; it should be ∑_i H_ii = |S|.
[Eq. (11)] The Sherman-Morrison update appears to have a typo in the denominator: it should be 1 + δ_{i_k}^T G_{k-1}^{-1} δ_{i_k}, not the expression with two δ^T factors.
[Abstract] There is a typo in the abstract: "scenario s" should be "scenarios."
[Section 5.1] The "significant intersection" between VIS and greedy D-optimal sampling sets is assessed visually; this should be quantified, for example with Jaccard similarity across budgets.
[Algorithm 1 and Section 4.1] The notation for the localized filter is inconsistent: the text writes z_i^(p), while Algorithm 1 uses z_x^p and z_y^p. The p-hop repulsion parameter is also set by a rule borrowed from [13] without any sensitivity study, so it is unclear how robust the method is to this choice.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Section 4 top-vertex-importance heuristic is unproven and confounded experiments are acknowledged, but the derivation does not reduce to its own inputs.

full rationale

I find no step in which a claimed prediction is equivalent, by construction or by fitted-parameter renaming, to its input. The learning objective (2) produces Q; the sampling objective (9)/(12) is posed independently for Ω = L+Q; and the paper's Section 4 link between top q_i and D-optimality is an informal assertion ('will be most likely the same indices') supported by an appeal to Weyl's theorem, not by setting the two objectives equal or by defining H in terms of Q. That assertion is a correctness/soundness gap (it is false in simple examples), not a circular reduction. The self-citations [10] and [13] supply the joint-learning algorithm, the claim that the trace term in (2) is constant at optimality, and a p-hop repulsion rule; none of these is used as a uniqueness theorem or as the target sampling result, and the comparison with greedy D-optimality in Figure 3a provides an independent check under the same reconstruction model. The Section 5.2 comparison with AVM/BSGDA/RAGS is confounded by using different reconstruction operators, but the paper explicitly states 'we can attribute the superior performance of VIS and VISR at a low sampling budget to using a better signal reconstruction model,' so it does not disguise the model advantage as a sampling-set-only result. Theorem 3.1 has an omitted proof and Section 4's Weyl argument is unproven; these are missing-support issues, not circularity.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the Gaussian model and on an informal, unproved connection between learned vertex importance and D-optimal sampling. The model parameters and regularization weights are not reported, making exact reproduction difficult.

free parameters (2)

mu = not reported
Regularization weight for graph Laplacian regularization in reconstruction (4). It appears in the approximated error covariance (8) via gamma=2mu-mu^2 and in the D-optimal objective (9), but no value or tuning procedure is given.
graph learning regularization = not reported
Solving (1) and (2) may require hyperparameters (e.g., on edge weights or diagonal entries) that are not stated, affecting the learned L and Q.

assumptions (4)

domain assumption Graph signals are i.i.d. zero-mean Gaussian with inverse covariance equal to the graph variation operator (L or L+Q).
Used in both the graph learning objective (1)-(2) and the D-optimal sampling objective (9). If the data does not follow this model, the derivations do not apply.
domain assumption The first-order Neumann series approximation in (8) is valid for small mu.
The proof of Theorem 3.1 is omitted; the approximation underpins the D-optimal objective (9).
ad hoc to paper The trace term in graph learning objective (2) is constant at optimality, so the log-determinant terms can be compared.
Used in the informal argument connecting (12) and (2). No proof is given that this justifies selecting nodes by vertex importance.
ad hoc to paper Ranking nodes by vertex importance q_i approximates the solution of the D-optimal sampling objective.
The paper states this 'will be most likely' via Weyl's theorem, which is not a formal guarantee.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Towards joint graph learning and sampling set selection from data." pith.science (2026). https://pith.science/paper/JFADYUWU

@misc{pith2026241209753,
  author       = {Pith},
  title        = {Pith review of: Towards joint graph learning and sampling set selection from data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JFADYUWU}},
  note         = {Machine review of arXiv:2412.09753}
}

read the original abstract

We explore the problem of sampling graph signals in scenarios where the graph structure is not predefined and must be inferred from data. In this scenario, existing approaches rely on a two-step process, where a graph is learned first, followed by sampling. More generally, graph learning and graph signal sampling have been studied as two independent problems in the literature. This work provides a foundational step towards jointly optimizing the graph structure and sampling set. Our main contribution, Vertex Importance Sampling (VIS), is to show that the sampling set can be effectively determined from the vertex importance (node weights) obtained from graph learning. We further propose Vertex Importance Sampling with Repulsion (VISR), a greedy algorithm where spatially -separated "important" nodes are selected to ensure better reconstruction. Empirical results on simulated data show that sampling using VIS and VISR leads to competitive reconstruction performance and lower complexity than the conventional two-step approach of graph learning followed by graph sampling.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

important

INTRODUCTION Graph signal processing (GSP) provides a powerful framewor k for analysis, denoising, sampling, and interpolation of signa ls deﬁned on graphs [ 1, 2, 3]. Sampling graph signals is a fundamental prob- lem in GSP [ 2, 4, 5, 6], where the goal is selecting a subset of graph nodes to reconstruct a smooth signal from the signal samples . In some ...

work page
[2]

NOTATIONS AND BACKGROUND 2.1. Graph signal processing Throughout the paper, we represent sets using calligraphic upper- case,S, matrices by bold uppercase, X, vectors by bold lowercase, x, and scalars by plain lowercase, x. A graph G = (V,E ) consists of a set of vertices V of size N and an edge set E ⊆V×V . A graph signal is a vector f ∈ RN , whose i-th ...

work page
[3]

L or L + Q)

GRAPH SIGNAL SAMPLING FORMULATION Our graph signal sampling formulation is based on the same si gnal model used for graph learning, i.e., f∼N (0, Σ = Ω †), where Ω is a positive semi-deﬁnite graph operator (e.g. L or L + Q). We deﬁne the sampling process as [ 2, 5, 4] yS = fS + n = I⊤ S f + n, where n∈ R|S| is the noise introduced during sampling and IS i...

work page
[4]

informative

SAMPLING BASED ON VERTEX IMPORTANCES When Ω = (L + Q), we can rewrite ( 9) as H⋆ = arg min Hii={0,1},∑ N k=0 Hii=|S| −logdet[H + γ(Q + L)], which can be rewritten by factoring γ as H⋆ = arg min Hii={0,1},∑ N k=0 Hii=|S| −logdet[( 1 γ H + Q) + L]. (12) Comparing the sampling and graph learning objectives, ( 12) and (2), we observe that their ﬁrst terms (lo...

work page
[5]

These node locations are ﬁxed across all ex- periments

EXPERIMENTS To experimentally validate our proposed sampling algorith ms, VIS and VISR, we use synthetic data where node locations are obta ined by uniformly sampling from the [0, 1]× [0, 1] Euclidean plane at N = 100 locations. These node locations are ﬁxed across all ex- periments. We consider a Gaussian process with covariance m atrix Joint L-Q learnin...

work page
[6]

We generate M = 100 random signals, each drawn from mul- tivariate Gaussian distribution fk ∼N (0, S), and add noise n∼ N (0, σ2 nI), where σn is the noise level

and (2), respectively. We generate M = 100 random signals, each drawn from mul- tivariate Gaussian distribution fk ∼N (0, S), and add noise n∼ N (0, σ2 nI), where σn is the noise level. We compare different sam- pling sets by reconstructing the sampled signal with noise u sing (4). We evaluate the average MSE between reconstructed and origi nal signals as...

work page
[7]

CONCLUSION AND FUTURE WORK In this work, we showed that a sampling set can be directly obt ained from the learned vertex importance. Compared to the convent ional two-step approach of ﬁrst learning the graph (CGL) and apply ing expensive sampling algorithms, our proposed approach of le arning DDGL and using the vertex importance as auxiliary informati on ...

work page
[8]

Antonio Ortega, Introduction to graph signal processing , Cambridge University Press, 2022

work page 2022

Show all 24 references

[9]

Discrete signal processing on graphs: Sampl ing theory,

Siheng Chen, Rohan V arma, Aliaksei Sandryhaila, and Jel ena Kovaˇ cevi´ c, “Discrete signal processing on graphs: Sampl ing theory,” IEEE Trans. Signal Process. , vol. 63, no. 24, pp. 6510–6523, 2015

2015
[10]

Sig- nal processing techniques for interpolation in graph struc tured data,

Sunil K Narang, Akshay Gadde, and Antonio Ortega, “Sig- nal processing techniques for interpolation in graph struc tured data,” in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, 2013, pp. 5445–5449

2013
[11]

Efﬁcient sampling set selection for bandlimited graph signals using graph spectral proxies,

Aamir Anis, Akshay Gadde, and Antonio Ortega, “Efﬁcient sampling set selection for bandlimited graph signals using graph spectral proxies,” IEEE Trans. Signal Process. , vol. 64, no. 14, pp. 3775–3789, 2016

2016
[12]

Practical graph s ignal sampling with log-linear size scaling,

Ajinkya Jayawant and Antonio Ortega, “Practical graph s ignal sampling with log-linear size scaling,” Signal Process. , vol. 194, pp. 108436, 2021

2021
[13]

Fast graph sampling set selection using gersh- gorin disc alignment,

Y uanchao Bai, Fen Wang, Gene Cheung, Y uji Nakatsukasa, and Wen Gao, “Fast graph sampling set selection using gersh- gorin disc alignment,” IEEE Trans. Signal Process. , vol. 68, pp. 2419–2434, 2020

2020
[14]

Learning graphs from data: A signal representat ion perspective,

Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard, “Learning graphs from data: A signal representat ion perspective,” IEEE Signal Processing Magazine , vol. 36, no. 3, pp. 44–63, 2019

2019
[15]

Gr aph learning from data under laplacian and structural constrai nts,

Hilmi E. Egilmez, Eduardo Pavez, and Antonio Ortega, “Gr aph learning from data under laplacian and structural constrai nts,” IEEE Journal of Selected Topics in Signal Processing , vol. 11, no. 6, pp. 825–841, 2017

2017
[16]

An efﬁcient algorith m for graph laplacian optimization based on effective resistanc es,

Eduardo Pavez and Antonio Ortega, “An efﬁcient algorith m for graph laplacian optimization based on effective resistanc es,” in 2019 53rd Asilomar Conference on Signals, Systems, and Computers. IEEE, 2019, pp. 51–55

2019
[17]

Joint graph and vertex importance learning,

Benjamin Girault, Eduardo Pavez, and Antonio Ortega, “ Joint graph and vertex importance learning,” in 2023 31st Euro- pean Signal Processing Conference (EUSIPCO) . IEEE, 2023, pp. 1858–1862

2023
[18]

Irregularity-aware graph fourier transforms ,

Benjamin Girault, Antonio Ortega, and Shrikanth S Narayanan, “Irregularity-aware graph fourier transforms ,” IEEE Transactions on Signal Processing , vol. 66, no. 21, pp. 5746–5761, 2018

2018
[19]

A probabilistic inte rpre- tation of sampling theory of graph signals,

Akshay Gadde and Antonio Ortega, “A probabilistic inte rpre- tation of sampling theory of graph signals,” in 2015 IEEE In- ternational Conference on Acoustics, Speech and Signal Pro - cessing (ICASSP), 2015, pp. 3257–3261

2015
[20]

Graph-based scalable sampling of 3d point cloud attribute s,

Shashank N Sridhara, Eduardo Pavez, Ajinkya Jayawant, Antonio Ortega, Ryosuke Watanabe, and Keisuke Nonaka, “Graph-based scalable sampling of 3d point cloud attribute s,” Submitted to IEEE TIP , arXiv preprint arXiv:2410.01027 , 2024

arXiv
[21]

Near - optimal sensor placements in gaussian processes: Theory, e f- ﬁcient algorithms and empirical studies.,

Andreas Krause, Ajit Singh, and Carlos Guestrin, “Near - optimal sensor placements in gaussian processes: Theory, e f- ﬁcient algorithms and empirical studies.,” Journal of Machine Learning Research, vol. 9, no. 2, 2008

2008
[22]

Horn and Charles R

Roger A. Horn and Charles R. Johnson, Matrix Analysis, Cam- bridge University Press, 2 edition, 2012

2012
[23]

Eigendecomposition-free sampling set selection for graph signals,

Akie Sakiyama, Y uichi Tanaka, Toshihisa Tanaka, and Antonio Ortega, “Eigendecomposition-free sampling set selection for graph signals,” IEEE Transactions on Signal Processing , vol. 67, no. 10, pp. 2679–2692, 2019

2019
[24]

A distance-base d for- mulation for sampling signals on graphs,

Ajinkya Jayawant and Antonio Ortega, “A distance-base d for- mulation for sampling signals on graphs,” in 2018 IEEE Inter- national Conference on Acoustics, Speech and Signal Proces s- ing (ICASSP), 2018, pp. 6318–6322

2018

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

important

INTRODUCTION Graph signal processing (GSP) provides a powerful framewor k for analysis, denoising, sampling, and interpolation of signa ls deﬁned on graphs [ 1, 2, 3]. Sampling graph signals is a fundamental prob- lem in GSP [ 2, 4, 5, 6], where the goal is selecting a subset of graph nodes to reconstruct a smooth signal from the signal samples . In some ...

work page

[2] [2]

NOTATIONS AND BACKGROUND 2.1. Graph signal processing Throughout the paper, we represent sets using calligraphic upper- case,S, matrices by bold uppercase, X, vectors by bold lowercase, x, and scalars by plain lowercase, x. A graph G = (V,E ) consists of a set of vertices V of size N and an edge set E ⊆V×V . A graph signal is a vector f ∈ RN , whose i-th ...

work page

[3] [3]

L or L + Q)

GRAPH SIGNAL SAMPLING FORMULATION Our graph signal sampling formulation is based on the same si gnal model used for graph learning, i.e., f∼N (0, Σ = Ω †), where Ω is a positive semi-deﬁnite graph operator (e.g. L or L + Q). We deﬁne the sampling process as [ 2, 5, 4] yS = fS + n = I⊤ S f + n, where n∈ R|S| is the noise introduced during sampling and IS i...

work page

[4] [4]

informative

SAMPLING BASED ON VERTEX IMPORTANCES When Ω = (L + Q), we can rewrite ( 9) as H⋆ = arg min Hii={0,1},∑ N k=0 Hii=|S| −logdet[H + γ(Q + L)], which can be rewritten by factoring γ as H⋆ = arg min Hii={0,1},∑ N k=0 Hii=|S| −logdet[( 1 γ H + Q) + L]. (12) Comparing the sampling and graph learning objectives, ( 12) and (2), we observe that their ﬁrst terms (lo...

work page

[5] [5]

These node locations are ﬁxed across all ex- periments

EXPERIMENTS To experimentally validate our proposed sampling algorith ms, VIS and VISR, we use synthetic data where node locations are obta ined by uniformly sampling from the [0, 1]× [0, 1] Euclidean plane at N = 100 locations. These node locations are ﬁxed across all ex- periments. We consider a Gaussian process with covariance m atrix Joint L-Q learnin...

work page

[6] [6]

We generate M = 100 random signals, each drawn from mul- tivariate Gaussian distribution fk ∼N (0, S), and add noise n∼ N (0, σ2 nI), where σn is the noise level

and (2), respectively. We generate M = 100 random signals, each drawn from mul- tivariate Gaussian distribution fk ∼N (0, S), and add noise n∼ N (0, σ2 nI), where σn is the noise level. We compare different sam- pling sets by reconstructing the sampled signal with noise u sing (4). We evaluate the average MSE between reconstructed and origi nal signals as...

work page

[7] [7]

CONCLUSION AND FUTURE WORK In this work, we showed that a sampling set can be directly obt ained from the learned vertex importance. Compared to the convent ional two-step approach of ﬁrst learning the graph (CGL) and apply ing expensive sampling algorithms, our proposed approach of le arning DDGL and using the vertex importance as auxiliary informati on ...

work page

[8] [8]

Antonio Ortega, Introduction to graph signal processing , Cambridge University Press, 2022

work page 2022