TY - GEN

T1 - Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs

AU - Chien, Eli

AU - Li, Pan

AU - Milenkovic, Olgica

N1 - Funding Information:
Acknowledgment: The work was supported by the NSF grant 1956384 and the NSF Center for Science of Information (CSoI) housed at Purdue University.
Publisher Copyright:
© 2021 IEEE.

PY - 2021

Y1 - 2021

N2 - The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed 'partial clique-expansion' to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.

AB - The landing probability of a vertex in a hypergraph is the probability of a random walk ending at the vertex after making a prescribed number of steps. Landing probabilities are of importance for a number of learning tasks on hypergraphs, including higher-order PageRanks and (local) community detection. We perform the first mean-field study of landing probabilities of random walks on hypergraphs and examine clique-expansion and tensor-based methods. In particular, we evaluate the mean-field characteristics of the two methods over a class of random hypergraph models for the task of seed-set community expansion. We determine parameter regimes in which one method outperforms the other and propose a new hybrid expansion method termed 'partial clique-expansion' to reduce the projection distortion and reduce the complexity of tensor-based methods on partially expanded hypergraphs.

UR - http://www.scopus.com/inward/record.url?scp=85123428936&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85123428936&partnerID=8YFLogxK

U2 - 10.1109/ITW48936.2021.9611457

DO - 10.1109/ITW48936.2021.9611457

M3 - Conference contribution

AN - SCOPUS:85123428936

T3 - 2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings

BT - 2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE Information Theory Workshop, ITW 2021

Y2 - 17 October 2021 through 21 October 2021

ER -