Sparse Partial Least Squares for Coarse Noisy Graph Alignment

Graph signal processing (GSP) provides a powerful framework for analyzing signals arising in a variety of domains. In many applications of GSP, multiple network structures are available, each of which captures different aspects of the same underlying phenomenon. To integrate these different data sources, graph alignment techniques attempt to find the best correspondence between vertices of two graphs. We consider a generalization of this problem, where there is no natural one-to-one mapping between vertices, but where there is correspondence between the community structures of each graph. Because we seek to learn structure at this higher community level, we refer to this problem as "coarse" graph alignment. To this end, we propose a novel regularized partial least squares method which both incorporates the observed graph structures and imposes sparsity in order to reflect the underlying block community structure. We provide efficient algorithms for our method and demonstrate its effectiveness in simulations.

1. INTRODUCTION

Consider signals arising simultaneously on two graphs of size n₁, n₂, respectively. These graphs may represent two distinct social networks with graph signals capturing the amount of discussion of a particular topic on a given day. While different users may populate each social network with potentially no overlap, the patterns of discussion are likely to be correlated, particularly within communities of common interest. For example, the communities of politically-engaged Facebook and Twitter users are both likely to actively discuss the same breaking news stories at the same time, even if there is no direct "cross-talk" between the two networks. We consider an idealized version of this situation, where m paired signals, sampled independently, are observed on the networks and . Many existing popular community detection methods (for a single network, or networks with a shared set of nodes) examine low-rank approximations of the covariance matrix of graph signals [1], [2]: intuitively, if two nodes are in the same community, their responses to external stimuli, represented as graph signals, are likely to be highly correlated and so methods that capture the major patterns of covariance are likely to identify communities.