Unlabeled Signal Reconstruction on Product Graphs

In this paper, we consider reconstruction of smooth, aka bandlimited signals, on a product graph from a subset of unlabeled observations. That is, we do not know from which nodes the observations are gathered. Traditional graph signal reconstruction methods assume that the node indices or labels of the observed graph signals might be perfectly known. However, in practice, the node indices of observations are unavailable due to data gathering constraints. If the node and observation correspondences are ignored, the reconstruction performance naturally deteriorates. To address this limitation, we propose PGSR-Perm that jointly estimates the graph signals along with the underlying correspondences. We also derive sufficient conditions on the number of unlabeled observations required for faithful recovery. Finally, we demonstrate the efficacy of PGSR-Perm on synthetic and real-world datasets.