PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Signal Estimation With Unknown Topology

Tirza Routtenberg

arXiv:2610.34070v1eess.SP

TL;DR

The paper addresses estimation when graph topology is latent among candidate graphs and when estimators must transfer across networks of different sizes. It develops topology-blind graph-spectral estimators, including a multi-basis design and a shared spectral function. In IEEE power-system simulations, posterior weighting achieves the lowest average and worst-topology MSE among topology-blind estimators without requiring accurate topology identification.

  • Problem

    Graph-signal estimators commonly assume known topology, while topology uncertainty complicates graph filtering and different network sizes limit reuse of per-eigenvector coefficients.

    Source: §I · p. 1

  • Method

    The paper develops topology-blind multi-basis graph-spectral estimation, structured and topology-adaptive variants, and a shared spectral-function design for cross-size transfer.

    Source: §I · p. 2

  • Results

    In IEEE power-system simulations, posterior weighting of GSP-LMMSE branches achieves the lowest average and worst-topology MSE among topology-blind estimators without requiring accurate topology identification.

    Source: §VII · p. 12

  • Takeaways & Limitations

    A shared spectral response with dimension-independent coefficients can be applied across network sizes, including to unseen graphs without retraining its coefficients.

    Source: A. Shared Spectral Function and… · p. 6

Abstract

from arXiv · show

Graph-signal estimation is commonly designed assuming that the underlying topology is known. In this paper, we consider estimation from general nonlinear measurements when the active topology is latent but is known to belong to a given family of candidate graphs. We first develop a class of topology-blind graph-spectral estimators that jointly exploit the candidate graphs, and characterize the performance loss compared to unconstrained linear estimation. We derive the minimum-mean-squared-error (MSE) multi-basis estimator and show that its optimal operator is the weighted projection of the topology-blind linear MMSE (LMMSE) operator onto the multi-graph filter space. This characterization provides exact expressions for the excess MSE and conditions for attaining the topology-blind LMMSE. To reduce the number of parameters, we develop estimators based on shared spectral responses and low-rank representations, and consider data-dependent estimators that infer the topology from the measurements, by maximum a-posteriori probability (MAP) selection or posterior weighting (multiple-model). We further extend the framework to networks of different sizes by jointly optimizing a common spectral function. We derive its MSE-optimal coefficients and decompose the resulting estimation loss into graph-filter approximation error and the additional cost of sharing a spectral response across networks. The proposed estimators admit sample-based implementations, while the shared spectral function can be applied to unseen graphs without retraining its coefficients. Simulations on IEEE power networks demonstrate the benefits of the proposed graph-spectral estimators under topology uncertainty and cross- network transfer.

I. INTRODUCTION

The paper addresses graph-signal estimation when the active topology is unknown within a candidate family, and seeks to transfer estimation across networks of different sizes. It develops graph-spectral estimators for these settings and evaluates them on IEEE power systems.

I. INTRODUCTION

  • Unknown active topology complicates graph filtering because the topology-blind LMMSE operator is generally not a filter in any one candidate graph basis.The paper also identifies cross-size transfer as a challenge because per-eigenvector filter coefficients do not carry across network dimensions.Source: §I · p. 1
  • The proposed contributions include a minimum-MSE multi-basis estimator, lower-complexity and topology-adaptive variants, and a shared spectral-function design for networks of different sizes.The paper also derives empirical-MSE designs and evaluates the estimators against robust minimax, expected-graph, multiple-model, and deep-learning methods on IEEE power systems.Source: §I · p. 2, 4) Sample-based design and evaluation · p. 2

A. Graph Signal Processing Background

  • Graph filters exploit graph-spectral structure, and polynomial filters can avoid explicit eigendecomposition and admit localized implementations.The graph Fourier transform uses the Laplacian eigenvectors as its basis and the eigenvalues as graph frequencies.Source: A. Graph Signal Processing Background · p. 2

B. Signal Model with Unknown Topology

  • The observation model allows a known, generally nonlinear measurement function that depends on the latent active topology, with additive measurement noise.Topology uncertainty may affect both the forward model and the conditional distribution of the signal.Source: B. Signal Model with Unknown Topology · p. 2

C. Estimation Problem and Performance Benchmarks

The paper establishes topology-blind MMSE benchmarks and develops a graph-spectral estimator that jointly uses candidate graph bases. Its optimal coefficients minimize MSE within that class, while its operator representation is unique even when the coefficients are not.

C. Estimation Problem and Performance Benchmarks

  • The topology-blind MMSE estimator minimizes error over measurable functions of the measurements, while the topology-blind LMMSE provides the affine benchmark.The oracle LMMSE assumes the active topology is revealed; the gap from the topology-blind LMMSE quantifies the affine cost of not observing it.Source: C. Estimation Problem and Performance… · p. 3

A. Multi-Basis GSP-LMMSE Estimator

  • The multi-basis estimator jointly combines candidate graph spectral bases without committing to one topology at inference.This extends the known-graph GSP-LMMSE approach, which is diagonal in a single graph Fourier basis.Source: A. Multi-Basis GSP-LMMSE Estimator · p. 3
  • The minimum-MSE multi-basis estimator is obtained by optimizing jointly over its candidate-basis responses, and its resulting operator is unique.The coefficient representation need not be unique; the stated optimal coefficients use a minimum-norm representation.Source: A. Multi-Basis GSP-LMMSE Estimator · p. 3
  • The multi-basis class jointly accounts for measurement covariance and spectral overlap across candidate graph bases, rather than independently combining separately designed filters.Its optimal estimator contains every topology-blind estimator restricted to any single candidate basis.Source: A. Multi-Basis GSP-LMMSE Estimator · p. 3

B. Performance Characterization

The multi-basis estimator includes single-basis graph filters and, at the population level, performs no worse than the best such filter. Its excess MSE relative to topology-blind LMMSE is characterized by a weighted projection error and can vanish under stated conditions.

B. Performance Characterization

  • At the population level, the multi-basis estimator cannot perform worse than the best topology-blind single-basis GSP estimator.The multi-basis class contains each single-basis estimator by setting the other candidate responses to zero.Source: B. Performance Characterization · p. 4
  • The multi-basis operator is the Cyy-weighted projection of the topology-blind LMMSE operator onto the multi-basis operator space.The induced loss is the squared weighted distance and vanishes exactly when the topology-blind LMMSE operator belongs to that space; symmetry of that operator is necessary.Source: B. Performance Characterization · p. 4
  • The multi-basis estimator attains topology-blind LMMSE when the conditional means are topology independent, candidate graphs share an eigenbasis, and the specified conditional cross- and auto-covariances are diagonal in it.These are sufficient conditions for attaining the benchmark.Source: B. Performance Characterization · p. 4
  • Under the stated covariance-heterogeneity assumptions, excess MSE is bounded by covariance heterogeneity across topologies, and the bound is small when covariance-weighted deviations are small or cancel.The flexible multi-basis design may increase estimation variance and numerical sensitivity in finite samples, motivating lower-complexity variants.Source: B. Performance Characterization · p. 4

C. Shared-Response Estimator and Low-Rank Extension

The shared-response model reduces multi-basis complexity by constraining candidate graphs to use a common spectral response, while low-rank extensions allow several shared templates. Topology-adaptive alternatives instead select or weight graphs from each observation.

C. Shared-Response Estimator and Low-Rank Extension

  • The shared-response constraint reduces the spectral-response parameters from MN to N for fixed graph weights, which may be prior-weighted or select one candidate basis.The optimal response for fixed weights is the minimum-MSE solution within the shared-response class.Source: C. Shared-Response Estimator and… · p. 4
  • The shared-response restriction has an MSE penalty equal to the projection loss from restricting the multi-basis estimator to that smaller operator space.For fixed weights, the shared-response operator space is a linear subspace of the multi-basis space.Source: C. Shared-Response Estimator and… · pp. 4–5
  • A low-rank extension uses r shared spectral templates with graph-dependent weights, requiring r(N + M − r) nominal degrees of freedom instead of MN.Its rank-r optimization is nonconvex and can be addressed by alternating least squares; for r = 1 it reduces to the shared-response model when graph-dependent weights are fixed.Source: C. Shared-Response Estimator and… · p. 5

D. Topology-Adaptive GSP Estimation

  • Topology-adaptive estimators first select a candidate graph or weight candidates from the observation, then apply the corresponding affine graph-filter branches.MAP selection uses the topology-conditioned likelihood when available; posterior weighting gives a multiple-model estimator that approximates MMSE using affine graph-filter branches.Source: D. Topology-Adaptive GSP Estimation · p. 5
  • Because topology selection is data-dependent, these estimators are generally nonlinear in the measurements, and their MSE has no universal ordering relative to the multi-basis estimator.Their MSE depends on both the topology-specific estimators and the induced selection regions.Source: D. Topology-Adaptive GSP Estimation · p. 5

IV. TRANSFERABLE GRAPH-SIGNAL ESTIMATION ACROSS NETWORK SIZES

The paper extends shared-response estimation to networks of different sizes by jointly fitting a common spectral function. Its optimal coefficients minimize average per-node MSE across network groups, and the resulting excess loss separates graph-filter approximation from the cost of sharing.

IV. TRANSFERABLE GRAPH-SIGNAL ESTIMATION ACROSS NETWORK SIZES

  • A common spectral function with graph-dimension-independent coefficients enables joint estimation across network groups of different sizes.The group index is known at inference and identifies the relevant candidate family; the design minimizes average per-node MSE.Source: §IV · p. 6, A. Shared Spectral Function and… · p. 6

A. Shared Spectral Function and Cross-Network Design

  • For any fixed spectral dictionary, the cross-network GSP-LMMSE estimator uses minimum-norm coefficients that minimize the average per-node MSE.The design replaces fixed-size multi-basis coefficients with a common spectral function optimized across networks of different dimensions.Source: A. Shared Spectral Function and… · p. 6
  • The excess MSE is the average weighted distance between operators induced by the shared spectral function and group-wise topology-blind LMMSE operators.Its decomposition separates within-group graph-filter approximation error from the additional cost of sharing one spectral function across groups.Source: A. Shared Spectral Function and… · pp. 6–7

B. Interpretation and Implementation

The shared spectral-function design fits one frequency response jointly to graph-specific GSP-LMMSE responses, with frequencies weighted by measurement power. Its coefficients can be applied to an unseen graph without retraining when compatibility conditions hold.

B. Interpretation and Implementation

  • The design fits a common spectral function to graph-specific GSP-LMMSE responses across graphs, weighting each frequency by its measurement power.In the power-system simulations, where 1^T x = 0, the DC mode is excluded from the estimate.Source: B. Interpretation and Implementation · p. 7
  • The learned spectral function can be applied to an unseen graph with known topology without retraining its coefficients, provided spectral scaling is compatible and target means are available.Chebyshev filters can avoid explicit eigendecomposition through sparse Laplacian–vector products; rational filters can use sparse solvers or ARMA graph filters.Source: B. Interpretation and Implementation · p. 7

V. SAMPLE-BASED ESTIMATOR DESIGN

  • The estimators can be trained by minimizing empirical MSE on labeled data, preserving graph-filter structure while directly optimizing coefficients from estimation errors.The training data may come from historical measurements or be generated using the observation model.Source: §V · p. 7

A. Fixed-Dimension Estimators

For fixed-dimension estimators, empirical-MSE designs replace population statistics with sample estimates; for cross-size transfer, a shared spectral function is learned across network groups. In both settings, the learned estimator minimizes empirical estimation error within its prescribed structure.

A. Fixed-Dimension Estimators

  • The fixed-dimension multi-basis estimator's sample-based design is the empirical-MSE minimizer within its prescribed class, not merely a heuristic plug-in approximation.The same empirical-MSE principle applies to the shared-response estimator for fixed topology weights.Source: A. Fixed-Dimension Estimators · p. 7

B. Cross-Size Shared-Function Estimator

  • For cross-size estimation, common spectral coefficients are learned by minimizing average per-node empirical MSE across network groups.The learned coefficient count remains independent of graph dimensions, and this discriminative design does not require identifying the underlying nonlinear measurement model.Source: B. Cross-Size Shared-Function Estimator · p. 8

C. Statistical Complexity

The section compares estimator parameter counts and describes IEEE power-system simulations for topology uncertainty and transfer across network sizes.

C. Statistical Complexity

  • The topology-blind LMMSE uses N^2 coefficients, the multi-basis estimator uses MN, and a rank-r model uses r(N + M − r) degrees of freedom.The multi-basis operator space has dimension at most 1 + M(N − 1); cross-size estimation learns Q coefficients independently of graph dimensions, with lower-dimensional models potentially increasing MSE.Source: C. Statistical Complexity · p. 8, (STATE) ANGLE · p. 8
  • Table III reports test-system bus and line counts, extreme nonzero graph frequencies, and RMS phase under M1 and M2.Source: Table III · p. 8

VI. SIMULATIONS

  • The evaluation addresses five questions about topology uncertainty, estimator hierarchy, training data, measurement-carried topology information, and transfer across network sizes.The authors state that code reproducing the figures and tables is available.Source: §VI · p. 8

A. Setup

  • Six IEEE test systems are modeled as weighted bus graphs; most simulations use IEEE 118-bus and NE 39-bus candidate families with 20 topologies each.Variants differ from the nominal topology by 1–9 lines for IEEE 118 and 1–6 lines for NE 39.Source: A. Setup · pp. 8–9

(STATE) ANGLE,

  • PSSE estimates mean-referenced voltage phase angles from active-power injections using AC power flow, with unit voltage magnitudes and both smoothness-prior and power-flow state models.Source: A. Setup · p. 8

A. Setup

  • The candidate graph bases can differ substantially, and results across Subsections VI-B–VI-E average 20 realizations with 95% confidence intervals.Unless stated otherwise, each topology has 500 training samples.Source: A. Setup · p. 9
  • Comparisons include robust minimax, expected-graph, classical multiple-model, deep-learning, and graph-spectral estimators, with a nominal-basis single-response ablation.The proposed multiple-model branches use graph-spectral LMMSE estimators and a graph-stationary surrogate likelihood; performance is evaluated using NMSE and worst-topology conditional NMSE.Source: A. Setup · p. 9

B. The Price of an Unknown Topology

The paper develops graph-spectral estimators for unknown-topology estimation and transfer across networks, comparing structured and data-adaptive designs with linear-estimation benchmarks. Simulations show that posterior weighting can improve topology-blind estimation, while transfer performance depends on shared spectral structure and the observation setting.

B. The Price of an Unknown Topology

  • Multiple-model GSP achieves the best topology-blind NMSE, improving average NMSE by 0.3 and 2.1 dB and worst-topology NMSE by 0.6 and 2.8 dB over blind LMMSE.These gains occur despite topology-identification rates of only 21% and 26%, versus 5% for random selection; posterior weighting suppresses unlikely candidates without identifying the active topology.Source: B. The Price of an Unknown Topology · pp. 9–10
  • At 20 dB under M1, blind LMMSE, multi-basis, rank-one, and expected-graph estimators have NMSEs within 0.1 dB, while nominal-topology GSP loses 0.1 and 1.2 dB on average.On IEEE 118, topology-aware unrestricted LMMSE underperforms blind LMMSE because it estimates N^2 coefficients from 500 samples per topology, whereas blind LMMSE pools samples across topologies.Source: B. The Price of an Unknown Topology · p. 9, Table V · p. 10

C. Estimator Hierarchy: Number of Bases and Perturbation

  • Rank-one stays within 0.06 dB of multi-basis; adding candidate bases reduces M1 average excess, while M2 retains 1.1 and 0.6 dB average excess even with all bases.As topology perturbations grow, multiple-model GSP's gain over multi-basis increases from 0.1 to 1.3 dB on IEEE 118 and from 1.6 to 3.1 dB on NE 39.Source: C. Estimator Hierarchy: Number of… · p. 10, Figure 2 · p. 10, Figure 3 · p. 10

D. Finite Training Data

  • With M1 and 20 samples per topology, blind LMMSE is 1.3 dB worse than multi-basis and catches up only at 1,000 or more samples.Multiple-model GSP with 50 samples matches the classical multiple-model estimator's NMSE with 2,000 samples; under M2, the graph-stationary likelihood is inaccurate and classical multiple-model estimation performs best with 2,000 samples.Source: D. Finite Training Data · pp. 10–11

E. Topology Information in the Measurements

  • With 50 samples per topology, the surrogate identification rate reaches 0.59 when full-covariance estimation is unreliable; with 500 samples, multiple-model GSP approaches the topology-aware benchmark as snapshots increase.On IEEE 118, multiple-model GSP improves from −8.8 to −9.6 dB, within 0.03 dB of the benchmark; on NE 39 it improves from −11.3 to −19.3 dB, compared with −19.7 dB for the benchmark.Source: Figure 5 · p. 11, E. Topology Information in the… · p. 11

F. Transfer Across Network Sizes

  • Across six networks, rational spectral transfer under M1 stays within 0.12 dB, whereas under M2 it loses 1.5–7.3 dB.For M1, Chebyshev transfer incurs 12.4 dB when extrapolating to NE 39; with only two target samples, the transferred function's average excess is 1.9 dB.Source: F. Transfer Across Network Sizes · pp. 11–12, Table VI · p. 12

VII. CONCLUSIONS

  • Posterior weighting approaches the topology-aware benchmark as snapshots increase, while multi-basis and rank-one retain near-LMMSE performance with fewer coefficients, especially with limited training data.Data-dependent estimators are most effective when topology is reflected in graph-spectral measurement covariance; rational functions of absolute graph frequency transfer accurately when spectral responses share common structure.Source: §VII · p. 12

A PROOF OF THEOREM 1

The proof establishes the multi-basis estimator’s minimum and uniqueness, then derives two corollaries concerning when the topology-blind LMMSE lies in the multi-basis space and how oracle operators relate to its projection.

A PROOF OF THEOREM 1

  • The multi-basis MSE minimizer is unique when Cyy is positive definite, with boundedness requiring rD to lie in range(SD).The minimum-norm solution yields the stated optimizer and substitution gives the minimum MSE.Source: A PROOF OF THEOREM 1 · p. 12

1) Proof of Corollary 1:

  • When the conditional means are topology independent and the covariance matrices share an eigenbasis, the topology-blind LMMSE belongs to the multi-basis operator space.The proof uses the common diagonalization of Cxy and Cyy to establish this membership.Source: 1) Proof of Corollary 1 · p. 12

2) Proof of Corollary 2:

  • The prior-weighted average of the oracle operators is feasible, and the optimal multi-basis operator is the Cyy-weighted projection of the topology-blind LMMSE operator.The proof combines this projection relation with the oracle identities to establish the corollary.Source: 2) Proof of Corollary 2 · pp. 12–13

Supplementary Material for “Graph Signal

S-I TRAINING DATA AND COMMON QUANTITIES

The supplement describes common training quantities and estimator implementations, covering topology-aware benchmarks and proposed topology-blind designs. It also details shared-response, low-rank, topology-selective, minimax, and neural-network alternatives.

S-I TRAINING DATA AND COMMON QUANTITIES

  • Training uses labeled data for each topology, with empirical mixture moments formed from topology-conditioned sample moments and prior weights.Covariance inversions use diagonal loading selected by five-fold cross-validation on training estimation MSE.Source: S-I TRAINING DATA AND COMMON QUANTITIES · p. 14

S-II TOPOLOGY-AWARE BENCHMARKS

  • Topology-aware benchmarks include a known-topology graph filter with N coefficients per topology and an unrestricted LMMSE estimator with N^2 coefficients per topology.Both are supplied the active topology at test time.Source: S-II TOPOLOGY-AWARE BENCHMARKS · p. 14

S-III PROPOSED ESTIMATORS

  • The proposed multi-basis estimator uses MN coefficients, while the shared-response design uses N coefficients and the rank-one estimator uses N + M − 1.The rank-one class lies within the multi-basis class; its training MSE lies between the multi-basis and shared-response estimators.Source: S-III PROPOSED ESTIMATORS · p. 14
  • Topology-selective GSP chooses the branch with the largest approximate posterior probability, while the multiple-model estimator weights branches by those probabilities.Both use a surrogate likelihood and are described as a plug-in approximation to the topology-blind MMSE estimator.Source: S-III PROPOSED ESTIMATORS · pp. 14–15
  • The compared alternatives also include an expected-graph filter, minimax MSE and regret estimators, full-LMMSE multiple-model branches, and a pooled-data neural network.The supplement lists their structures and coefficient counts, including N^2 coefficients for the minimax estimators.Source: S-III PROPOSED ESTIMATORS · p. 15
  • The minimax estimator uses the least-favorable prior and equalizes worst-case loss across topologies receiving positive prior weight.The minimax MSE and regret criteria respectively address the least observable topologies and those farthest from their oracle.Source: S-III PROPOSED ESTIMATORS · p. 15

S-V CROSS-NETWORK DESIGNS

The cross-network design fits a shared spectral function on known graphs and applies it to a held-out network. The supplement describes the dictionaries, evaluation setup, and few-shot comparisons.

S-V CROSS-NETWORK DESIGNS

  • For each held-out network, the learned function is evaluated using 20,000 training and 5,000 test samples per network, averaged across five independent data sets.The DC term is excluded and a penalty is added to the weighted curve fit.Source: S-V CROSS-NETWORK DESIGNS · p. 16
  • The held-out-network experiment compares Chebyshev functions on absolute, normalized, and graphon-normalized axes with a rational-function dictionary.The Chebyshev design uses order Q = 60; the rational dictionary uses four log-spaced poles in [10^-2, 10^2].Source: S-V CROSS-NETWORK DESIGNS · p. 16
  • The few-shot comparison measures excess MSE against a GSP-LMMSE estimator trained on the held-out network’s full training set.It compares target-only fits, transfer from five other networks, and joint fitting across six groups using varying target sample counts.Source: S-V CROSS-NETWORK DESIGNS · p. 16

S-VI SUMMARY

The supplement’s estimator summary covers their definitions, test-time topology information, structure, and learned coefficient counts.

S-VI SUMMARY

  • The estimator comparison organizes methods by definition, topology information at test time, structure, and number of learned coefficients.Means are additionally estimated and are not counted as coefficients.Source: S-VI SUMMARY · p. 16

Related papers

Loading 2610.34070v1…