In this paper, we study the problem of recovering the community structure of a network under federated myopic learning. Under this paradigm, we have several clients, each of them having a myopic view, i.e., observing a small subgraph of the network. Each client sends a censored evidence graph to a central server. We provide an efficient algorithm, which computes a consensus signed weighted graph from clients evidence, and recovers the underlying network structure in the central server. We analyze the topological structure conditions of the network, as well as the signal and noise levels of the clients that allow for recovery of the network structure. Our analysis shows that exact recovery is possible and can be achieved in polynomial time. We also provide information-theoretic limits for the central server to recover the network structure from any single client evidence. Finally, as a byproduct of our analysis, we provide a novel Cheeger-type inequality for general signed weighted graphs.
翻译:在本文中,我们研究了在联合近视学习下恢复网络社区结构的问题。在这个模式下,我们有几个客户,每个客户都有近视观点,即观察网络的一个小子集。每个客户都向中央服务器发送一个经过审查的证据图表。我们提供了一个高效的算法,从客户证据中计算一个经一致签名的加权图,并恢复中央服务器的基本网络结构。我们分析了网络的地形结构条件,以及用户的信号和噪音水平,以便恢复网络结构。我们的分析表明,准确的恢复是可能的,可以在多元时间内实现。我们还为中央服务器从任何单一客户证据中恢复网络结构提供了信息理论限制。最后,作为我们分析的副产品,我们为签署的通用加权图表提供了一种新的Cheeger型不平等。