Community Inference from Graph Signals with Hidden Nodes
Community Inference from Graph Signals with Hidden Nodes
复制标题
DOI：
10.1109/icassp.2019.8683001
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Hoi-To Wai;Yonina C. Eldar;A. Ozdaglar;A. Scaglione
中科院分区：
文献类型：
--
作者：
Hoi-To Wai;Yonina C. Eldar;A. Ozdaglar;A. Scaglione
关于图形结构推断的许多最新作品都假定图形信号是完全可观察到的。对于具有数千或数百万个节点的大图，这需要在数据收集和处理步骤上进行高复杂性。在这里，我们研究了一个社区推断问题，这些问题是在部分观察到的（子采样）的图形信号上，该图形避开了拓扑拓扑推断，同时直接揭示了图的粗糙结构。研究了推理任务的两个变体：（i）一种盲方法，它渗透了可观察到的节点所属的社区； （ii）一种半盲方法，该方法还使用有关可观察到的节点和隐藏节点之间的子图的辅助信息来渗透所有节点的社区。这些针对社区推论的技术在分析和经验上是有效的，适用于大图。
Many recent works on inference of graph structure assume that the graph signals are fully observable. For large graphs with thousands or millions of nodes, this entails high complexity on the data collection and processing steps. Here, we study a community inference problem on partially observed (sub-sampled) graph signals which sidesteps topology inference, while revealing the coarse structure of the graph directly. Two variants of the inference task are studied: (i) a blind method that infers the communities that the observable nodes belong to; and (ii) a semi-blind method that infers the communities of all nodes using, in addition, side information about the sub-graph between observable and hidden nodes. These techniques for community inference are shown to be efficient and suitable for large graphs analytically and empirically.