I-Hsiang Wang

Kai-Chun Chen, I-Hsiang Wang

Information velocity (IV) is a recently proposed notion to capture the speed of reliable information dissemination over a large-scale network. It is the speed at which reliable end-to-end communication over $k$ hops can be achieved within $t$ time instances, and is defined formally as the asymptotic ratio $k/t$ as $k$ tends to infinity subject to vanishing error probability. To date, even for a tandem of binary erasure channels without feedback, the optimal IV for disseminating multiple (say $m$) bits remains unknown. We make progress on this open problem by characterizing the optimal IV for the regime where the message size $m = o(k^{1/2})$. The main contribution lies in achievability, where we propose a simple bit-separation scheme that pipelines message bits in an orderly fashion with carefully designed temporal spacing so that the flows of different bits do not collide with one another with high probability. This is in sharp contrast to previous attempts in the literature where schemes involve coding over time and across nodes. To go beyond the regime $m = o(k^{1/2})$, we further investigate the setting where every node in the network has strictly causal access to the state information of the BEC links in the entire network. For such a setting with global state information (GSI), we develop an enhanced scheme and characterize the optimal IV for the regime where the message size $m = o(k)$. Interestingly, for the regime $m = o(k^{1/2})$, GSI does not improve the information velocity.

I Chien, Chung-Yi Lin, I-Hsiang Wang

Community detection in hypergraphs is explored. Under a generative hypergraph model called "d-wise hypergraph stochastic block model" (d-hSBM) which naturally extends the Stochastic Block Model from graphs to d-uniform hypergraphs, the asymptotic minimax mismatch ratio is characterized. For proving the achievability, we propose a two-step polynomial time algorithm that achieves the fundamental limit. The first step of the algorithm is a hypergraph spectral clustering method which achieves partial recovery to a certain precision level. The second step is a local refinement method which leverages the underlying probabilistic model along with parameter estimation from the outcome of the first step. To characterize the asymptotic performance of the proposed algorithm, we first derive a sufficient condition for attaining weak consistency in the hypergraph spectral clustering step. Then, under the guarantee of weak consistency in the first step, we upper bound the worst-case risk attained in the local refinement step by an exponentially decaying function of the size of the hypergraph and characterize the decaying rate. For proving the converse, the lower bound of the minimax mismatch ratio is set by finding a smaller parameter space which contains the most dominant error events, inspired by the analysis in the achievability part. It turns out that the minimax mismatch ratio decays exponentially fast to zero as the number of nodes tends to infinity, and the rate function is a weighted combination of several divergence terms, each of which is the Renyi divergence of order 1/2 between two Bernoulli's. The Bernoulli's involved in the characterization of the rate function are those governing the random instantiation of hyperedges in d-hSBM. Experimental results on synthetic data validate our theoretical finding that the refinement step is critical in achieving the optimal statistical limit.