Source-linked AI summary
struc2vec: Learning Node Representations from Structural Identity
Leonardo F. R. Ribeiro, Pedro H. P. Savarese, Daniel R. Figueiredo
TL;DR
Existing node-representation methods have limited ability to capture structural identity, motivating a dedicated approach. struc2vec measures structural similarity hierarchically and uses a multilayer graph to generate structural contexts, outperforming prior methods on structural-identity and related classification tasks.
Problem
Explicitly capturing structural identity in node representations remains a relatively underdeveloped problem, while structural identity is defined by network structure rather than attributes.
Method
struc2vec uses a hierarchy to measure structural similarity at multiple scales and a multilayer graph to generate contexts for learning node representations.
Results
struc2vec excels at structural identity compared with DeepWalk, node2vec, and RolX, including under random edge removal, and is superior on structurally dependent airport classification.
Takeaways & Limitations
Structural identity is an important property to consider when choosing node representations, especially for classification tasks whose labels depend on node roles.
Takeaways & Limitations
Optimizations reduce computational and memory requirements but can affect the framework’s capacity to generate representations for structurally similar nodes, with marginal or sometimes beneficial impact.
Abstract
from arXiv · showhide
Structural identity is a concept of symmetry in which network nodes are identified according to the network structure and their relationship to other nodes. Structural identity has been studied in theory and practice over the past decades, but only recently has it been addressed with representational learning techniques. This work presents struc2vec, a novel and flexible framework for learning latent representations for the structural identity of nodes. struc2vec uses a hierarchy to measure node similarity at different scales, and constructs a multilayer graph to encode structural similarities and generate structural context for nodes. Numerical experiments indicate that state-of-the-art techniques for learning node representations fail in capturing stronger notions of structural identity, while struc2vec exhibits much superior performance in this task, as it overcomes limitations of prior approaches. As a consequence, numerical experiments indicate that struc2vec improves performance on classification tasks that depend more on structural identity.
1 INTRODUCTION
Structural identity groups nodes by their roles in network structure rather than labels or position. struc2vec learns representations for this identity, using hierarchical structural similarity and experiments showing advantages over prior methods.
- Nodes can be grouped into equivalent functional classes, including social roles and protein functions.
- Structural identity depends on relationships defined solely by network structure, not node labels.
- Distance- and recursion-based methods are common approaches for identifying structural identity, while representation learning offers an alternative.
- DeepWalk and node2vec tend to separate distant nodes because homophily makes network proximity predictive of shared features, limiting structural equivalence.
- struc2vec learns structural identity independently of node and edge attributes, labels, network position, and connectivity between components.
- Its hierarchy ranges from degree-based similarity at the lowest level to whole-network similarity from each node’s viewpoint.
- Experiments report that struc2vec outperforms DeepWalk, node2vec, and RolX on structural identity, including under random edge removal, and on structurally dependent airport classification.
2 RELATED WORK
Prior node-embedding methods generally encode network proximity or local rooted-subgraph structure, while explicit structural-identity representations remain underdeveloped. struc2vec addresses this gap alongside role-based approaches such as RolX.
- Node embeddings support classification and clustering by placing network nodes in Euclidean space.
- DeepWalk and node2vec generate node contexts from random walks, making nearby nodes likely to receive similar embeddings.
- subgraph2vec embeds nodes with the same local structure together but defines structural equivalence as a rigid binary property based on the Weisfeiler-Lehman test.
- Explicitly capturing structural identity remains a relatively underdeveloped problem despite extensive work on richer network-node representations.
- RolX assigns nodes distributions over structural roles using enumerated structural features and a learned basis, without explicitly modeling node similarity or structural context.
- RolX may miss structurally equivalent node pairs because it does not explicitly consider node similarity or structural context.
3 STRUC2VEC
struc2vec learns node representations of structural identity by comparing hierarchical neighborhood structure, encoding those similarities in a multilayer graph, and generating structural contexts for representation learning.
- The framework seeks representations whose distances correlate with structural similarity and do not depend on node or edge attributes.
- Measuring structural similarity: It compares ordered degree sequences across progressively larger neighborhood rings to measure increasingly refined structural similarity.The comparison is defined over k-hop neighborhoods, with the structural distance non-decreasing in k.
- Measuring structural similarity: Dynamic Time Warping compares degree sequences of different sizes, while the degree-ratio cost makes small degrees more dissimilar than similarly sized large degrees.The framework permits alternative cost functions, although it uses DTW in this implementation.
- Constructing the context graph: A multilayer weighted graph places every network node in each neighborhood-similarity layer and assigns within-layer weights that decrease with structural distance.Each layer is a weighted undirected complete graph over the node set, subject to the distance being defined.
- Constructing the context graph: Directed interlayer links connect corresponding nodes across adjacent layers, with layer transitions controlled by each node’s number of above-average-similarity neighbors.Moving upward provides a more refined context when many similar nodes exist at the current layer.
- Generating context: Biased random walks on the multilayer graph generate contexts likely to contain structurally similar nodes, after which a representation-learning method can process the sequences.The resulting hierarchical context can shrink at higher layers because structural similarity cannot increase there.
4 EXPERIMENTAL EVALUATION
Experiments on synthetic and real networks show that struc2vec captures structural equivalence and hierarchy more effectively than DeepWalk, node2vec, and RolX, including under edge-removal noise. It also improves classification performance on air-traffic networks and remains practically applicable to very large networks despite unfavorable worst-case complexity.
- 4.1 Barbell graph: On barbell graphs, struc2vec groups structurally equivalent nodes together and preserves structural hierarchies, whereas DeepWalk and node2vec fail to capture these equivalences.struc2vec places bridge nodes near corresponding clique representations and separates equivalent classes; node2vec primarily reflects graph distance.
- 4.1 Barbell graph: RolX identifies some equivalent roles on the barbell graph, but it assigns equivalent clique nodes to different roles, whereas struc2vec better separates structural equivalence.RolX identifies six roles, with structurally equivalent clique nodes distributed across roles 0, 2, and 5.
- 4.2 Karate network: On the mirrored Karate network, DeepWalk and node2vec fail to group mirrored nodes, while struc2vec groups mirrored pairs and reveals a complex structural hierarchy.The learned clusters correspond to leaders, high-degree nodes connected to leaders, low-degree nodes two hops from a leader, and other structurally equivalent pairs.
- 4.3 Robustness to edge removal: 94% of mirrored pairs learned by struc2vec lie below distance 0.25, while 68% of all pairs lie above 0.25; the average all-pair distance is 5.6 times larger than the mirrored-pair average.For node2vec, the mirrored-pair and all-pair distance distributions are practically identical.
- 4.3 Robustness to edge removal: With edge sampling probability s = 0.3, corresponding nodes remain closer in latent space even though the probability that an original edge appears in both sampled graphs is 0.09.The authors interpret this experiment as evidence that struc2vec remains robust to structural noise caused by edge removals.
5 CONCLUSION
The paper frames structural identity as network-based symmetry related to node roles and proposes struc2vec to learn representations capturing it. Its hierarchical similarity metric and multilayer context graph support stronger structural-identity capture than prior methods, including in role-dependent classification tasks.
- Structural identity identifies nodes by network structure rather than node labels, reflecting the functions or roles they play.
- struc2vec learns representations that explicitly capture structural identity in networks.
- The method measures node-pair similarity with a hierarchical metric based on ordered degree sequences and generates context through a weighted multilayer graph.
- struc2vec outperforms DeepWalk, node2vec, and RolX on structural-identity capture and improves classification when labels depend more on node roles.