Learning attribute and homophily measures through random walks

We investigate the statistical learning of nodal attribute functionals in homophily networks using random walks. Attributes can be discrete or continuous. A generalization of various existing canonical models, based on preferential attachment is studied (model class P ), where new nodes form connections dependent on both their attribute values and popularity as measured by degree. An associated model class U is described, which is amenable to theoretical analysis and gives access to asymptotics of a host of functionals of interest. Settings where asymptotics for model class U transfer over to model class P through the phenomenon of resolvability are analyzed. For the statistical learning, we consider several canonical attribute agnostic sampling schemes such as Metropolis-Hasting random walk, versions of node2vec (Grover and Leskovec, 2016) that incorporate both classical random walk and non-backtracking propensities and propose new variants which use attribute information in addition to topological information to explore the network. Estimators for learning the attribute distribution, degree distribution for an attribute type and homophily measures are proposed. The performance of such statistical learning framework is studied on both synthetic networks (model class P ) and real world systems, and its dependence on the network topology, degree of homophily or absence thereof, (un)balanced attributes, is assessed.

Automated summary

This paper investigates the statistical learning of nodal attribute functionals in homophily networks using random walks. It proposes a generalization of canonical models, based on preferential attachment, and introduces a model class U for theoretical analysis and asymptotics of various functionals. The paper also explores attribute agnostic sampling schemes for statistical learning and proposes estimators for learning attribute distribution, degree distribution, and homophily measures.