This paper proposes a method for vertex-wise aggregation sampling of a broad class of graph signals, designed to attain the best possible recovery based on the generalized sampling theory. This is achieved by designing a sampling operator by an optimization problem, which is inherently non-convex, as the best possible recovery imposes a rank constraint. An existing method for vertex-wise aggregation sampling is able to control the number of active vertices but cannot incorporate prior knowledge of mandatory or avoided vertices. To address these challenges, we formulate the operator design as a problem that handles a constraint on the number of active vertices and prior knowledge on specific vertices for sampling, mandatory inclusion or exclusion. We transformed this constrained problem into a difference-of-convex (DC) optimization problem by using the nuclear norm and a DC penalty for vertex selection. To solve this, we develop a convergent solver based on the general double-proximal gradient DC algorithm. The effectiveness of our method is demonstrated through experiments on various graph signal models, including real-world data, showing superior performance in the recovery accuracy compared to existing methods.
Figures & tables
Notations
Definitions
X
a set
x
a vector
xi,[x]i
the i -th element of x
∥x∥2
the ℓ2 norm of x , ∥x∥2:=∑ixi2
X
a matrix
x(i),[X](i)
the i -th row vector of X
Table 1: Notations and Definitions.
Subspace
Smoothness
Stochastic
P
A⊤
ΣF−1VF⊤
Q
Table 2: Definitions of the Matrix P for Each Prior. The Following Definitions Are Used: F=UFΣFVF⊤ and Γx=Q⊤Q .
Prior
λ
δ
γ1(0)
γ2(0)
Subspace (SB)
1.05
10−1
10−3
10−5
Smoothness (SM)
5.1
10−1
10−2
10−2
Stochastic (ST)
0.75
10−6
10−3
10−5
Table 3: Parameters for the Proposed Method.
Signal Prior
SP [ 2 ]
AVM [ 24 ]
GSSS [ 21 ]
ScFGSS [ 46 ]
Design (i)
Design (ii)
Design (iii)
SB (PGS)
−19.672
−18.474
−612.924
−604.539
−606.181
−608.050
−601.380
+ noise
−14.896
−13.730
−27.669
−38.753
−37.838
−22.354
−16.717
SM (GMRF)
−23.630
−6.125
−27.559
−27.739
−27.679
−27.395
−27.392
+ noise
−18.003
−4.600
−22.608
−26.960
−27.374
−26.428
−25.900
ST (GMRF)
−20.758
−9.036
−25.243
−26.235
−26.705
−26.617
−26.572
+ noise
−15.137
−6.158
−23.972
−25.933
−25.553
−25.373
−25.368
Table 4: Average MSEs in Decibel of the Recoveries for 20 Independent Runs on each Method.
Figure 1: An example of sampling and recovery experiment on a PGS graph signal on a random sensor graph. Fig. ( 1(a) ) shows the original PGS signal. Figs. ( 1(b) )-( 1(h) ) show the recovered signals from the noiseless sampled signals, and Figs. ( 1(i) )-( 1(o) ) show the recovered signals from the noisy sampled signals. The results in MSE are expressed in decibels, where smaller values indicate better recovery accuracy. The best and second best results in each case are in bold and underlined, respectively.
Signal Prior
Design (i)
Design (ii)
Design (iii)
SB (PGS)
24.20
33.60
31.50
SM (GMRF)
30.75
31.10
31.00
ST (GMRF)
31.85
31.85
32.00
Table 5: Average Number of Active Vertices by the Proposed Method for 20 Independent Runs.
Prior
λ
δ
γ1(0)
γ2(0)
Smoothness (SM)
1.2
10−6
10−2
10−5
Stochastic (ST)
0.33
10−6
10−2
10−5
Table 6: Parameters for the Proposed Method.
Figure 2: Sampling operators designed by the proposed method for the graph signal in Fig. 1 . Zero values are shown in black.
Figure 3: Examples of convergence behavior of the proposed method (Design (i)): objective function values and relative errors.
Prior
SP
AVM
GSSS
ScFGSS
Ours
SM
−29.429
−29.111
−42.689
−44.765
−44.065
+ noise
−18.833
8.075
−33.751
−40.807
−40.842
ST
−
−
−48.247
−67.708
−68.279
+ noise
−
−
−39.838
−61.148
−64.416
Table 7: Average MSEs in Decibel of the Recoveries for Monthly Average Temperature at 110 Stations in Switzerland.
Figure 4: Signal recovery results for the average temperature of Switzerland in October with assuming the stochastic prior. Fig. ( 4(a) ) shows the original temperature. Figs. ( 4(b) )-( 4(f) ) show the recovered temperatures. The best result is in bold.
In this paper, we study the sampling of bandlimited signals on multigraphs, where several graphs with different shift operators are defined on the same set of nodes. Since the shift operators do not commute in general, they admit only a joint block diagonalization, and the frequencies of the multigraph signal model are matrices rather than scalars. Relying on a formal algebraic convolutional signal model, we introduce a notion of frequency and bandwidth for multigraph signals that does not depend on any individual layer, and we extend the notions of removable and uniqueness sets to multigraphs. We prove that the optimality of a sampling set is determined exclusively by the common Fourier basis and its invariant subspaces, and not by any individual layer, although the individual layers provide computable sufficient conditions that certify a sampling set as a uniqueness set. Since identifying which layers provide reliable certificates requires spectral information, we propose an aggregate operator that pools the information of all the layers, is computable directly from the shift operators, and certifies uniqueness without any assumption on the individual layers. This operator leads to a greedy sampling algorithm that does not require computing the joint block diagonalization. Numerical experiments on multigraphs whose layers order the frequencies inconsistently show that the proposed algorithm selects better-conditioned sampling sets and attains lower reconstruction errors than single-layer methods.
Diffusion models generate data by reversing a forward corruption process that typically approaches a simple Gaussian prior. Recent work has extended this framework to signals supported on fixed graphs, e.g., road-network traffic and sensor-network measurements. Many graph signals have nonuniform spectral energy, whereas isotropic corruption adds the same conditional noise variance to every graph-frequency mode. Driving all modes to near-zero terminal signal-to-noise ratio (SNR) requires strong corruption, which increases the noise range that must be covered under a fixed sampling budget. We introduce Graph Residual Conjugate Diffusion (GRCD), which replaces the shared clock of graph heat diffusion with a mode-dependent clock that gives every graph-Fourier mode the same conditional SNR. GRCD fits a zero-mean graph-spectral Gaussian reference on the training split and stops at a finite terminal SNR at which the propagated reference still carries the fitted spectral variances. The Gaussian component has an exact modewise propagator in the probability-flow ODE, so sampling advances it analytically and integrates only the learned residual score numerically. We evaluate GRCD on five settings (METR-LA traffic, Molene weather, and three stochastic block models) against seven comparators under a matched protocol: Graph-Aware Diffusion (GAD), EDM (graph backbone), two adaptations of Whitened Score Diffusion (WSD), and three preconditioning controls. At four function evaluations (NFEs), GRCD lowers averaged maximum mean discrepancy (aMMD) by 22 to 36 times over the best comparator on all five settings, reaching 0.054 on METR-LA, where it clears an aMMD 0.1 target with 87% less sampling wall-clock time than the cheapest comparator that reaches it. Fitting the terminal reference reduces aMMD by 2.7 to 7.3 times at finite terminal SNR, while the factors shrink to 1.00 to 1.01 near zero.
Jinwei Li, Daniel Tenbrinck
Department of Data Science Friedrich-Alexander-Universität Erlangen-Nürnberg Erlangen, Germany
Graph reconstruction from partial observations often comes with structural side information, such as degree bounds, triangle counts, or an edge-density band. Prior-Informed Flow Matching (PIFM) reconstructs graphs by transporting a local prior toward the graph distribution, but it provides no mechanism to incorporate this side information. We put forth Constrained Primal-Dual PIFM (CPD-PIFM), which augments the sampler with Lagrange multipliers that evolve along each trajectory. The multipliers respond to constraint violations at a predicted endpoint and guide subsequent sampling steps without retraining. We prove that the sampler inherits PIFM's permutation equivariance and bound its expected terminal slack by a term that decays as the inverse square root of the number of steps, plus two approximation terms. On three link-prediction benchmarks and nine combinations of datasets and constraints, CPD-PIFM raises feasibility by 11-26 percentage points and remains competitive with fixed guidance without selecting a separate multiplier for each constraint.
Haoming Chen, Nicolas Zilberstein, Santiago Paternain +1