{"id":"7cd8cd56-668c-42e6-8a7d-d7d520ad428b","arxiv_id":"2412.09753","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Vertex importance scores from joint graph and vertex importance learning can be used to select sampling sets, with a repulsion variant improving performance at higher sampling rates.","lead":"The paper proposes two sampling set selection methods, VIS and VISR, that build on vertex importance scores learned jointly with a graph Laplacian from data. These methods aim to avoid the cost of running a dedicated graph sampling algorithm once the graph is learned.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The informal Weyl-theorem argument linking top vertex importance to D-optimal sampling in Sec. 4 is unproven and false in simple examples, so the central claim rests on an unsupported heuristic; matched-model experiments and an exact small-graph check are needed.","rationale":"The reader's weakest assumption is the same one I would stress. The entire contribution is the claim that learned vertex importances q_i can stand in for the D-optimal sampling objective. Section 4's derivation is not a derivation: comparing the log-determinant term of (12) with (2) and invoking Weyl does not characterize the argmax over H. The counterexample with a 3-node path shows the claim is not merely unproven; it is false without additional structure. For k=1, D-optimality selects nodes with largest diagonal of (L+Q)^{-1}, not necessarily largest Q_ii. This makes the theoretical bridge load-bearing but broken. I also note the Section 5.2 confound, but that is secondary: even with the confound fixed, the q-to-D-optimal step still needs either a proof/condition or a much broader empirical validation. An exhaustive enumeration on small learned graphs is the cheapest decisive check; if top-q sets consistently match exact D-optimal sets there, the practical claim may survive as heuristic even without a theorem. If they do not, the paper should be revised to present VIS/VISR as purely heuristic and compare on matched reconstruction models. Since the current verdict already asks for conditions and the paper's empirical idea is promising, CONDITIONAL remains appropriate; my concern does not move the verdict.","tokens_in":7916,"tokens_out":12527,"duration_ms":140884,"concrete_test":"Take a small graph (N=8–12) learned by the same DDGL procedure in (2) on several synthetic datasets. Enumerate all C(N,k) subsets for k=2,3,4 and compute the exact D-optimal objective (9) with Ω=L+Q; compare the VIS top-q set by Jaccard overlap and by the logdet ratio logdet(Ω+(1/γ)H_VIS)/logdet(Ω+(1/γ)H_opt). If overlap is low or the ratio differs from 1 by more than a few percent for any realistic learned (L,Q), the Section 4 premise is refuted and VIS/VISR should be presented as purely heuristic algorithms.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim depends on Section 4's assertion that the indices of H_ii=1 maximizing det[(1/γ)H+Q+L] are 'most likely' the largest q_i, justified by comparing (12) with (2), an appeal to Weyl's theorem [15, Cor. 4.3.9], and a visual overlap with greedy D-opt. This is not a theorem and is false in general. For k=1, the determinant lemma gives argmax_i logdet(L+Q+(1/γ)e_i e_i^T) = argmax_i [(L+Q)^{-1}]_{ii}, which depends on the whole inverse, not only on q_i. Example: L is the 3-node path Laplacian and Q=diag(1,8,1); then (L+Q)^{-1}_{ii}=(0.528,0.111,0.528), so D-optimal selects nodes 1 or 3, while VIS selects node 2. For k>1 the selection is a combinatorial function of L+Q. The 'trace term is constant at optimality' remark does not create a variational link between (2) and (12), since (2) has no H term. Thus there is no quantitative bound, no condition on L,Q under which top-q sets are near-optimal, and the claimed 'foundational step' is currently an unsupported heuristic. The empirical comparison in Section 5.2 is also confounded: baselines reconstruct with Ω1=L while VIS/VISR use Ω2=L+Q, and the paper itself credits the better model for the low-budget gains, so the sampling-set-specific advantage is not yet demonstrated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8301,"tokens_out":5095,"duration_ms":53636,"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":[{"comment":"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":"Section 4, Eqs. (12) and (2)"},{"comment":"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.","section":"Section 5.2, Fig. 3b"},{"comment":"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.\"","section":"Theorem 3.1, Eq. (8)"}],"minor_comments":[{"comment":"The constraint is written as ∑_{k=0}^N H_ii = |S|, which is a typo; it should be ∑_i H_ii = |S|.","section":"Eq. (9)"},{"comment":"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.","section":"Eq. (11)"},{"comment":"There is a typo in the abstract: \"scenario s\" should be \"scenarios.\"","section":"Abstract"},{"comment":"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.","section":"Section 5.1"},{"comment":"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.","section":"Algorithm 1 and Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"No additional concerns beyond those stated in the report. The paper is a short conference-style contribution; the unsupported Section 4 claim and the confounded comparison in Section 5.2 need to be addressed before it is ready for journal publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nWhat 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.\n\nVerdict: 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.\n\nRecommendation: send to peer review with major revision requested.","headline":"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.","tokens_in":8769,"tokens_out":2523,"would_cite":false,"duration_ms":24488,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph signal sampling","graph learning","vertex importance","diagonally dominant graph Laplacian","D-optimality","sampling set selection","graph signal reconstruction","Gaussian Markov random field"],"falsifier":"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.","tokens_in":7716,"feed_emoji":"🌐","tokens_out":3988,"duration_ms":44102,"temperature":0.7,"pith_summary":"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.","feed_headline":"Learned vertex weights can choose the sampling set directly","feed_subtitle":"VIS and VISR match graph-learn-then-sample reconstruction accuracy at lower cost on synthetic data.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the joint graph and vertex importance learning formulation and the result that the covariance is $(\\mathbf{L}+\\mathbf{Q})^{-1}$.","marker":"[10]"},{"why":"Supplies the D-optimal sampling objective and the NP-hard combinatorial formulation that the paper approximates.","marker":"[5]"},{"why":"Provides the graph Laplacian regularization reconstruction and the closed-form solution used in the experiments.","marker":"[6]"},{"why":"Contributes the p-hop localized filter and the sampling-rate-dependent rule for choosing p that VISR adapts.","marker":"[13]"},{"why":"Gives the efficient graph Laplacian learning algorithm used as the baseline two-step approach.","marker":"[9]"},{"why":"Supplies Weyl's theorem and the matrix-determinant lemma used to connect the learning and sampling objectives.","marker":"[15]"}],"fun_headline_variants":["Sampling set chosen directly from learned vertex weights","Joint graph learning and sampling: no two-step needed","Vertex importance drives efficient signal sampling","One-shot graph learning and sampling selection","Sampling from vertex importance: simpler, competitive"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sampling set chosen directly from learned vertex weights","Joint graph learning and sampling: no two-step needed","Vertex importance drives efficient signal sampling","One-shot graph learning and sampling selection","Sampling from vertex importance: simpler, competitive"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000225,"raw_usage":{"total_tokens":1432,"prompt_tokens":877,"completion_tokens":555,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":488}},"tokens_in":493,"tokens_out":555,"duration_ms":5638,"temperature":1.0,"reasoning_tokens":488,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:45:06.294866+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Sig- nal processing techniques for interpolation in graph struc tured data,","cited_arxiv_id":null,"evidence_quote":"Provides the joint graph and vertex importance learning formulation and the result that the covariance is $(\\mathbf{L}+\\mathbf{Q})^{-1}$."},{"cited_title":"These node locations are fixed across all ex- periments","cited_arxiv_id":null,"evidence_quote":"Supplies the D-optimal sampling objective and the NP-hard combinatorial formulation that the paper approximates."},{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Provides the graph Laplacian regularization reconstruction and the closed-form solution used in the experiments."},{"cited_title":"Fast graph sampling set selection using gersh- gorin disc alignment,","cited_arxiv_id":null,"evidence_quote":"Contributes the p-hop localized filter and the sampling-rate-dependent rule for choosing p that VISR adapts."},{"cited_title":"Discrete signal processing on graphs: Sampl ing theory,","cited_arxiv_id":null,"evidence_quote":"Gives the efficient graph Laplacian learning algorithm used as the baseline two-step approach."},{"cited_title":"Gr aph learning from data under laplacian and structural constrai nts,","cited_arxiv_id":null,"evidence_quote":"Supplies Weyl's theorem and the matrix-determinant lemma used to connect the learning and sampling objectives."}],"review_version":1}