# Role Discovery in Networks

arXiv: https://arxiv.org/abs/1405.7134 · HTML: https://mlsanity.com/paper/1405.7134/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2014.

## Built on by (most cited first, 12 of 12)

- [Role-Aware Modeling for N-ary Relational Knowledge Bases](https://mlsanity.com/paper/2104.09780/) (2021)
- [A Survey on Role-Oriented Network Embedding](https://mlsanity.com/paper/2107.08379/) (2021)
- [A Comparative Study on Robust Graph Neural Networks to Structural Noises](https://mlsanity.com/paper/2112.06070/) (2021)
- [Augmenting Textual Generation via Topology Aware Retrieval](https://mlsanity.com/paper/2405.17602/) (2024)
- [Representation Learning on Heterostructures via Heterogeneous Anonymous Walks](https://mlsanity.com/paper/2201.06972/) (2022)
- [Unsupervised Framework for Evaluating and Explaining Structural Node Embeddings of Graphs](https://mlsanity.com/paper/2306.10770/) (2023)
- [Structure-Guided Input Graph for GNNs facing Heterophily](https://mlsanity.com/paper/2412.01757/) (2024)
- [GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs](https://mlsanity.com/paper/2202.03884/) (2022)
- [PersonaSAGE: A Multi-Persona Graph Neural Network](https://mlsanity.com/paper/2212.13709/) (2022)
- [Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs](https://mlsanity.com/paper/2301.11120/) (2023)
- [HyperS2V: A Framework for Structural Representation of Nodes in Hyper Networks](https://mlsanity.com/paper/2311.04149/) (2023)
- [Embedding networks with the random walk first return time distribution](https://mlsanity.com/paper/2512.02694/) (2025)

## Abstract (arXiv)

Roles represent node-level connectivity patterns such as star-center, star-edge nodes, near-cliques or nodes that act as bridges to different regions of the graph. Intuitively, two nodes belong to the same role if they are structurally similar. Roles have been mainly of interest to sociologists, but more recently, roles have become increasingly useful in other domains. Traditionally, the notion of roles were defined based on graph equivalences such as structural, regular, and stochastic equivalences. We briefly revisit these early notions and instead propose a more general formulation of roles based on the similarity of a feature representation (in contrast to the graph representation). This leads us to propose a taxonomy of three general classes of techniques for discovering roles that includes (i) graph-based roles, (ii) feature-based roles, and (iii) hybrid roles. We also propose a flexible framework for discovering roles using the notion of similarity on a feature-based representation. The framework consists of two fundamental components: (a) role feature construction and (b) role assignment using the learned feature representation. We discuss the different possibilities for discovering feature-based roles and the tradeoffs of the many techniques for computing them. Finally, we discuss potential applications and future directions and challenges.