Blind Graph Matching Using Graph Signals
Classical graph matching aims to find a node correspondence between two unlabeled graphs of known topologies. This problem has a wide range of applications, from matching identities in social networks to identifying similar biological network functions across species. However, when the underlying graphs are unknown, the use of conventional graph matching methods requires inferring the graph topologies first, a process that is highly sensitive to observation errors. In this paper, we tackle the blind graph matching problem with unknown underlying graphs directly using observations of graph signals, which are generated from graph filters applied to graph signal excitations. We propose to construct sample covariance matrices from the observed signals and match the nodes based on the selected sample eigenvectors. Our analysis shows that the blind matching outcome converges to the result obtained with known graph topologies when the signal sampling size is large and the signal noise is small. Numerical results showcase the performance improvement of the proposed algorithm compared to matching two estimated underlying graphs learned from the graph signals.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Estimating Centrality Blindly from Low-pass Filtered Graph Signals
This paper considers blind methods for centrality estimation from graph signals. We model graph signals as the outcome of an unknown low-pass graph filter excited with influences governed by a sparse sub-graph. This mode…
Blind Demixing of Diffused Graph Signals
Using graphs to model irregular information domains is an effective approach to deal with some of the intricacies of contemporary (network) data. A key aspect is how the data, represented as graph signals, depend on the …
blind source separationBlind Deconvolution of Graph Signals: Robustness to Graph Perturbations
We study blind deconvolution of signals defined on the nodes of an undirected graph. Although observations are bilinear functions of both unknowns, namely the forward convolutional filter coefficients and the graph signa…
DenoisingDetecting Low Pass Graph Signals via Spectral Pattern: Sampling Complexity and Applications
This paper proposes a blind detection problem for low pass graph signals. Without assuming knowledge of the exact graph topology, we aim to detect if a set of graph signal observations are generated from a low pass graph…
Graph LearningBlind Deconvolution of Sparse Graph Signals in the Presence of Perturbations
Blind deconvolution over graphs involves using (observed) output graph signals to obtain both the inputs (sources) as well as the filter that drives (models) the graph diffusion process. This is an ill-posed problem that…