Role Discovery in Networks

Ryan A. Rossi; Nesreen K. Ahmed

Source-linked AI summary

Role Discovery in Networks

Ryan A. Rossi, Nesreen K. Ahmed

arXiv:1405.7134v3May 28, 2014cs.SIphysics.soc-ph

TL;DR

Role discovery asks how to identify structurally similar nodes across graphs, supporting analysis beyond proximity-based communities. The article surveys graph-based and feature-based approaches, and proposes a framework that constructs role features before assigning nodes to roles. It emphasizes flexible, application-dependent representations while identifying challenges in feature selection, evaluation, scalability, and large-scale deployment.

Problem
Existing role discovery has received limited attention despite applications beyond small sociological networks, and strict graph equivalence is too rigid for practical structural similarity.
Method
The article proposes a taxonomy and generic framework that transforms graphs into feature representations, constructs role features, and assigns nodes to roles using those features.
Results
The article organizes role discovery into graph-based and feature-based approaches and surveys the feature operators, assignment methods, and model-selection decisions used for feature-based roles.
Takeaways & Limitations
Feature-based roles offer greater flexibility for representing complex roles and can incorporate attributes as additional features for application-specific discovery.
Takeaways & Limitations
Feature-based flexibility makes it more difficult to identify the features required to capture the intended roles, while evaluation must balance accuracy and efficiency.

Abstract

from arXiv · show

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.

1 INTRODUCTION

Role discovery identifies nodes with similar structural patterns, distinct from communities defined by proximity. This article surveys role-discovery techniques and develops a feature-based framework spanning feature construction and role assignment.

The survey motivates applications including anomaly detection, classification, active learning, network sampling, and anonymization, while noting that role discovery remains less studied than community partitioning.
Role discovery relaxes strict structural equivalence into the weaker, more practical notion of structural similarity.
Role discovery groups nodes with similar structural patterns, including star-centers, star-edges, near-cliques, and bridges.
The article proposes a taxonomy covering graph-based and feature-based roles, while also providing foundations for hybrid or broader feature-representation approaches.
Unlike communities, roles need not contain nearby or connected nodes because membership depends on structural similarity rather than graph distance.
Its feature-based framework separates transforming graphs into features from assigning nodes with similar feature vectors to roles.

2 ROLE FOUNDATIONS

Role discovery groups nodes by a chosen notion of equivalence or structural similarity, capturing recurring node-level connectivity patterns. The main equivalences range from strict structural matching to probabilistic similarity, motivating a taxonomy of graph-based, feature-based, and hybrid methods.

Role definition: Role discovery divides graph nodes into classes whose members are equivalent under a specified relation.The paper relaxes exact equivalence toward broader structural similarity.
Structural equivalence: Structural equivalence requires two nodes to connect to exactly the same neighbors, making it strict and often impractical for large real-world graphs.Structurally equivalent nodes are also indistinguishable in several network measures and cannot be more than two links apart.
Automorphic equivalence: Automorphic equivalence groups nodes exchangeable through a graph automorphism, allowing structurally distinct node sets such as W ∪M to form one role.Structural equivalence is a special case of automorphic equivalence.
Regular equivalence: Regular equivalence groups nodes that connect to role-equivalent nodes rather than requiring connections to identical nodes.It may be exact or approximate, so a graph can admit multiple valid role groupings.
Stochastic equivalence: Stochastic equivalence assigns nodes to the same role when they share the same probability distribution of edges to other nodes.This probabilistic relaxation motivates stochastic blockmodels.

2.2 Methods for Graph-based Roles

Graph-based role methods compute roles directly from graph representations such as adjacency matrices. They include blockmodels, similarity-based methods, spectral techniques, and predefined role detectors, with tradeoffs among scalability, interpretability, and accuracy.

Method taxonomy: Graph-based roles are computed directly from the graph, whereas feature-based roles first transform the graph into feature vectors.Feature-based roles are the paper’s main focus, while graph-based methods are reviewed for completeness.
Blockmodels: Blockmodels group nodes by structural or stochastic equivalence and summarize interactions among roles in a compact role-interaction graph.Examples include stochastic blockmodels, generalized blockmodels, and mixed-membership stochastic blockmodels.
Similarity methods: CONCOR repeatedly correlates adjacency-matrix rows until entries reach 1 or −1, using similarity rather than an explicit criterion.The method begins with Corr(A, A) and iteratively forms new correlation matrices.
Blockmodels: Stochastic blockmodels allow deviations from exact equivalence by assigning nodes to roles with role-pair edge probabilities represented in a matrix P ∈Rk×k.The number of roles k may be specified by the user or learned from data.
Tradeoffs: Adjacency-similarity methods compare matrix rows and can be fast when properly configured, while blockmodels may offer more meaningful, accurate, or interpretable roles.The useful tradeoff depends on the application.
Spectral methods: Spectral methods derive roles from selected eigenvectors representing structural patterns such as star-centers, star-edges, bridges, and near-cliques.They need not use only eigenvectors associated with the largest eigenvalues.
Predefined roles: SVD-based methods can identify predefined star-center types, including authority nodes with many incoming edges and hub nodes with many outgoing edges.These roles were developed for analyzing web pages and their link structure.
Scalability: Graph-based models can be difficult to compute on massive networks; dMMSB takes around a day for 1,000 nodes because it is quadratic in node count.The paper contrasts this scalability problem with potentially faster adjacency-similarity techniques.

2.3 Feature-based Roles

Feature-based roles transform graph or attributed-graph representations into features, then assign roles using similarity or equivalence in that feature space. This approach offers flexibility for complex roles but makes feature selection more dependent on expert guidance or application-specific tuning.

Feature-based role formulation: Feature-based roles transform a graph into features and assign roles based on feature equivalence or similarity.For attributed graphs, transformations may produce node, link, or non-relational features.
Feature-based role formulation: The framework shifts node equivalence from the graph representation to a feature representation, either preserving earlier equivalences or reinterpreting them more flexibly.The article primarily emphasizes reinterpretation and extension on feature representations for practical flexibility and efficiency.
Node equivalence and similarity: Strict feature equivalence assigns the same role to nodes with identical values across every structural feature.This corresponds to identical feature-vectors before relaxing equivalence into similarity.
Node equivalence and similarity: Relaxed feature similarity assigns nodes to the same role when their feature-vectors are sufficiently similar under a standard similarity or distance measure.Similarity is expressed as S(x_u, x_v) ≈ 1, while distance-based formulations use D(·) = 0 for identical vectors.
Prior approaches: Prior approaches construct local structural features and use methods such as NMF to assign roles, while other work seeks consistency with sociological equivalences.Examples include degree or egonet features, NMF, and AIC-based specifications.
Discussion: Feature-based representations can express complex roles more flexibly than traditional graph-based approaches, but identifying suitable features requires expert guidance or application-specific tuning.The flexibility improves representational scope while shifting difficulty toward feature design.

2.4 Hybrid approaches

Hybrid role-discovery methods combine graph-based information with learned feature representations. They either use graph-derived roles before feature construction or incorporate additional data sources during role assignment, with scalability remaining a key constraint for the first class.

Hybrid approaches: Hybrid approaches combine graph and feature representations, using graph structure before or after feature learning.The taxonomy distinguishes methods by whether graph-based processing precedes role feature construction or follows feature learning.
Graph-based initialization: One hybrid class uses graph-based roles as initial attributes, then relational feature learning incorporates those attributes with the graph.The learned features can subsequently support automatic learning of the number and assignment of hybrid roles.
Graph-based initialization: This first hybrid class loosely constrains feature-based roles toward the parametric form assumed by a statistical blockmodel.The approach uses refined features while retaining information from the initial graph-based role discovery.
Graph-based initialization: The main disadvantage of graph-initialized hybrid methods is limited scalability because of blockmodel constraints, although more scalable graph-based alternatives remain promising.The passage identifies SBM and MMSB as examples of blockmodels whose scalability limits this class.
Multiple data sources: A second hybrid class uses multiple graphs or attribute sets to regularize or influence role assignment after learning a graph-derived feature representation.Tensor factorization and collective matrix-tensor factorization are proposed mechanisms for combining these sources.

3 FRAMEWORK FOR FEATURE-BASED ROLES

The framework discovers feature-based roles by transforming graphs into feature representations and assigning nodes with similar feature vectors to roles. Its interchangeable components support application-specific tradeoffs, including scalability, flexibility, and attribute integration.

Framework components: The framework has two fundamental steps: role feature construction and role assignment.Graphs are transformed into feature representations, after which nodes with similar feature vectors are assigned to the same roles.
Framework components: Feature-learning systems and role-assignment methods are interchangeable, allowing choices based on structural patterns and application constraints such as scalability.Feature construction may use local or global features, while role assignment may use low-rank approximation or clustering.
Design flexibility: Application-specific constraints can be imposed during feature construction or role assignment, including sparseness, diversity, and locality.The framework is designed to accommodate constraints at either stage of the pipeline.
Design flexibility: The framework balances complexity and efficiency according to application-specific constraints and can be tuned for specific applications.The paper also describes the framework as flexible for application-driven role discovery.
Design flexibility: Feature-based roles can capture arbitrary structural patterns through data-driven and non-parametric approaches.This flexibility is presented as an advantage over traditional graph-based roles.
Design flexibility: Attributes can be incorporated as additional features before or after learning and constructing novel features.Roles defined over features can also generalize beyond a direct graph representation.

4 ROLE FEATURE CONSTRUCTION

Role feature construction generates relational and non-relational features from graph structure and attributes. The paper organizes this process into four decisions covering feature classes, operators, search, and selection.

Overview: Feature construction generates features from graph structure or non-relational information for role discovery.The input graph may include node attributes X_v and edge attributes X_e, with additional features added during construction.
Four-step process: The feature-learning process comprises four steps: selecting relational feature classes, choosing operators, searching the feature space, and selecting features.These steps determine what features are constructed, how they are generated, how candidates are explored, and how features are scored and pruned.
Four-step process: The taxonomy supports exhaustive, randomized, and guided feature-search strategies.Feature search is one of the explicit decisions in the proposed role-feature construction taxonomy.
Four-step process: Feature selection evaluates and incrementally prunes features during learning.The goal is to determine which constructed features should remain in the representation.

4.1 Relational Feature Classes

The taxonomy defines four feature classes according to the relational information used in computation: structural, link-value, node-value, and non-relational features. These classes can support feature construction for nodes or links.

Feature classes: The four feature classes are structural, link-value, node-value, and non-relational features.They are distinguished by whether computation uses graph structure, edge attributes, node attributes, or non-relational information.
Structural features: Structural features use only graph structure, including degree, clustering coefficient, betweenness, subgraph patterns, and path or walk measures.Examples include wedges, triangles, and other graph patterns.
Attribute-based features: Link-value features use feature values of links adjacent to, or within ρ hops of, the target node or link.Aggregates such as the mode can produce additional features from adjacent-link values.
Attribute-based features: Node-value features use feature values of nodes adjacent to, or a few hops from, the target node.For example, neighboring political affiliations can be aggregated into a node-value feature.
Attribute-based features: Non-relational features use attributes while ignoring link-based information.They can be computed from a target node’s feature vector or from the collection of node features.
Combining features: Feature-based roles can combine these feature classes, but link features must first be transformed into node features through an operator.The resulting node features can then be used for role assignment.

4.2 Relational Feature Operators for Roles

Feature operators define the searchable space from which role features are constructed. Their selection can be guided by domain knowledge, network characteristics, and application-specific evaluation criteria.

Operator space: Feature operators define the space of candidate features that can be searched and ultimately used to define roles.The paper notes that these operator classes can generate an infinite number of features.
Operator applicability: Many operators can compute features for both links and nodes using multiple classes of inputs.Operators relying on non-relational information, such as text analysis, are not applicable to structural features but can support attribute-based features.
Operator selection: Domain-specific knowledge may identify a small subset of operators that is meaningful for a given network and application.Local subgraph operators may suit social networks, whereas global operators may be more appropriate for technological networks.

4.3 Feature Search Strategy

Feature search strategies explore a space defined by raw inputs and relational operators, using exhaustive, random, or guided approaches. Feature sets should represent important structural patterns without redundancy, while automatic construction trades interpretability for scalability and novel pattern discovery.

Feature search strategies are typically exhaustive, random, or guided, differing in how much of the possible feature space they explore.Exhaustive search considers all features enabled by the inputs and operators, whereas random search samples only part of that space.
Useful role features should be representative of important structural patterns and minimal, with redundant features removed.The relative importance of these properties depends partly on the role-assignment technique used later.
Manual feature construction relies on expert-selected feature types and operators rather than iterative scoring and selection.Its tuning costs can make manual construction impractical for many tasks.
Automatic non-parametric construction iteratively generates features, discards redundant ones, and stops when no further novel or useful features emerge.This approach is suited to large-scale analysis and poorly understood roles, but the resulting roles are typically harder to interpret.

4.4 Relational Feature Selection: Scoring & Pruning

Relational feature selection evaluates candidate role features and prunes them to obtain a representative, minimal set. Similarity matrices and application-specific objectives provide alternative ways to score redundancy, usefulness, and task relevance.

Unsupervised feature selection scores candidate features and selects or prunes them to reduce redundancy and noise.The resulting feature set is intended to remain representative while becoming smaller and less redundant.
A similarity matrix records pairwise feature similarities and can be interpreted as a weighted graph whose edges represent feature relationships.Possible scoring measures include Pearson or Spearman correlation, information gain, gain ratio, and Gini index.
Table 5 summarizes systems that search and select features for relational learning.
Feature evaluation may incorporate application-specific knowledge, such as retaining a candidate when it improves holdout-set classification accuracy.This provides a guided alternative to purely unsupervised feature evaluation.

4.5 Generalized Role Feature Learning Template

The generalized role feature learning template transforms relational graph data and attributes into a compact feature representation through iterative construction, similarity-based graph pruning, and termination when no new features remain. Its design is guided by application assumptions about useful structural patterns.

The framework’s choices should be guided by application-specific assumptions about the graph and the roles being constructed.
The algorithm initializes primitive features, repeatedly searches for new features, unions them with prior features, and prunes redundant or noisy features.Search terminates when the feature set no longer changes or when the iteration limit is reached.
The template learns a feature representation from graph data and attributes that captures relational dependencies and structural properties compactly.It is designed to preserve fundamental patterns while revealing novel features.
The feature graph connects feature pairs whose similarity exceeds threshold λ, so connected components identify groups of dependent features for pruning.Within each component, the earliest or least-correlated feature may be retained while others are removed.

5 ROLE ASSIGNMENT

Role assignment maps similar node feature vectors to roles using clustering or low-rank approximation, with hard versus soft membership as a separate design choice. Model-selection procedures can choose the number of roles by balancing fit or error against complexity.

Role assignment groups nodes with similar feature vectors using clustering methods or low-rank approximation of the node-feature matrix.Clustering includes hierarchical, partitioning, and soft-clustering methods, while low-rank methods include SVD, PCA, MDS, and NMF.
In SVD-based assignment, retaining the influential singular values yields latent roles whose node memberships are represented by rows of the reduced factor.Reducing dimensionality combines similar graph features so hidden roles become apparent.
NMF represents each node’s role memberships in W and each role’s contributions to estimated feature values in H.Its non-negativity constraint is described as making it easier to interpret than SVD.
Model-selection templates increase the number of roles while model cost decreases, and MDL balances model complexity against error.The search can also be guided by an application objective such as cross-validated AUC for classification.
Hard assignment gives each vertex one role, whereas soft assignment permits mixed membership in multiple roles.Soft assignment generally requires more storage and may be impractical for fine-grained dynamic-graph snapshots.

6 DISCUSSION AND CHALLENGES

The discussion identifies dynamic, scalable, application-aware, and heterogeneous role discovery as important open problems. It emphasizes balancing accuracy with efficiency while addressing feature quality, memory, parallelism, and evolving network data.

Dynamic and streaming graphs: Dynamic and streaming role discovery remains important because user preferences and behavior are tied to time.Existing approaches include ROLE-DYNAMICS and DBMM, while tensor-based representations are proposed as another direction.
Dynamic and streaming graphs: Online methods must update role memberships, underlying role definitions, and potentially stale feature sets as new data arrives.This creates a need for incremental learning of representative features and appropriate time windows.
Additional directions: Soft role assignments can represent nodes participating in multiple structural patterns, such as a bridge within a clique or a star center within a clique.This contrasts with assigning each node a single hard role.
Evaluation and scalability: Evaluation frameworks are needed to compare accuracy, interpretability, approximation error, and efficiency, since users must balance these tradeoffs for their applications.The paper notes that prior role discovery work has not systematically evaluated these algorithmic tradeoffs.
Evaluation and scalability: Scaling remains challenging: traditional graph-based methods struggle with very large networks, while feature-based methods still lack parallel and distributed implementations.Further concerns include feature memory exceeding sparse-graph storage and the absence of MPI/MapReduce role learning.
Additional directions: Role discovery can benefit from integrating textual data, initial attributes, and application interests into feature learning, but these approaches require systematic evaluation.The paper also identifies heterogeneous networks and noisy or ambiguous links as settings needing further investigation and preprocessing.