Rolx: structural role extraction & mining in large graphs
Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra,
Christos Faloutsos, Lei Li
Given a network, intuitively two nodes belong to the same role if they have similar
structural behavior. Roles should be automatically determined from the data, and
could be, for example, “clique-members,” “periphery-nodes,” etc. Roles enable
numerous novel and useful network-mining tasks, such as sense-making, searching for
similar nodes, and node classification. This paper addresses the question: Given a
graph, how can we automatically discover roles for nodes? We propose RolX (Role
eXtraction), a scalable (linear in the number of edges), unsupervised learning
approach for automatically extracting structural roles from general network data.
We demonstrate the e↵ectiveness of RolX on several network-mining tasks: from
exploratory data analysis to network transfer learning. Moreover, we compare
network role discovery with network community discovery. We highlight fundamental
di↵erences between the two (e.g., roles generalize across disconnected networks,
communities do not); and show that the two approaches are complimentary in nature.