Some Advances in Role Discovery in Graphs
  Role discovery in graphs is an emerging area that allows analysis of complex
graphs in an intuitive way. In contrast to other graph prob- lems such as
community discovery, which finds groups of highly connected nodes, the role
discovery problem finds groups of nodes that share similar graph topological
structure. However, existing work so far has two severe limitations that
prevent its use in some domains. Firstly, it is completely unsupervised which
is undesirable for a number of reasons. Secondly, most work is limited to a
single relational graph. We address both these lim- itations in an intuitive
and easy to implement alternating least squares framework. Our framework allows
convex constraints to be placed on the role discovery problem which can provide
useful supervision. In par- ticular we explore supervision to enforce i)
sparsity, ii) diversity and iii) alternativeness. We then show how to lift this
work for multi-relational graphs. A natural representation of a
multi-relational graph is an order 3 tensor (rather than a matrix) and that a
Tucker decomposition allows us to find complex interactions between collections
of entities (E-groups) and the roles they play for a combination of relations
(R-groups). Existing Tucker decomposition methods in tensor toolboxes are not
suited for our purpose, so we create our own algorithm that we demonstrate is
pragmatically useful.
