Blind Estimation of Eigenvector Centrality from Graph Signals: Beyond Low-pass Filtering

This paper characterizes the difficulty of estimating a network's eigenvector centrality only from data on the nodes, i.e., with no information about the topology of the network. We model this nodal data as graph signals generated by passing white noise through generic (not necessarily low-pass) graph filters. Leveraging the spectral properties of graph filters, we estimate the eigenvectors of the adjacency matrix of the underlying network. To this end, a simple selection algorithm is proposed, which chooses the correct eigenvector of the signal covariance matrix with minimal assumptions on the underlying graph filter. We then present a theoretical characterization of the asymptotic and non-asymptotic performance of this algorithm, thus providing a sample complexity bound for the centrality estimation and revealing key elements driving this complexity. Finally, we illustrate the developed insights through a set of numerical experiments on different random graph models.

I. Introduction

The representation of data as graphs, or networks, has become an increasingly prominent approach in science and engineering [1], [2], allowing one to uncover community structure [3], common connection patterns [4], and node importance [5]. In many settings, there is an assumed network structure lying underneath a set of interacting agents, but the precise connections in this structure are unobserved. However, we would still like to use graph-based analysis tools, such as centrality measures [6]–[9], to draw conclusions about the role of the agents in the unobserved interconnected structure.