Blind Extraction of Equitable Partitions from Graph Signals

Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications context such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network’s edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions. Finally, we establish theoretical bounds on the error that this spectral detection scheme incurs and perform numerical experiments that illustrate our theoretical results and compare both algorithms.

1. INTRODUCTION

Networks have become a powerful abstraction for complex systems [1], [2]. To comprehend such networks, we often seek patterns in their connections, which would allow us to comprehend the system in simpler terms. A common theme is to divide the nodes—and by extension the units of the underlying system—into groups of similar nodes. For instance, in the context of community detection, we consider nodes as similar if they are tightly-knit together, or share similar neighborhoods [3]. This notion of node similarity is thus bound to the specific position of the nodes in the graph, i.e., the identity of their neighboring nodes. In contrast, we may want to split nodes into groups according to whether they play a similar role in the graph [4], irrespective of their exact position. As an example, consider a division into hubs and peripheral nodes according to their degree, a split for which the exact identity of the neighboring nodes is not essential. While in this specific example defining a degree-similarity measure between nodes is simple, how to define a similarity measure between nodes in a position independent manner is a non-trivial question in general.