Rolx: structural role extraction & mining in large graphs
Abstract
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.
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.
Research Areas
