struc2vec: Learning Node Representations from Structural Identity

By Leonardo F. R. Ribeiro, Pedro H. P. Saverese, Daniel R. Figueiredo. 2017

1,286 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Molecular Biology, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Deep Graph Infomax (2018, background): “Most prominently, the random-walk objective is known to over-emphasize proximity information at the expense of structural information (Ribeiro et al., 2017), and performance is highly dependent on hyperparameter choice (Grover & Leskovec, 2016; Perozzi et al., 2014).”
Representation Learning on Graphs: Methods and Applications (2017, background): “However, more recently, Ribeiro et al. [50] and Donnat et al. [20] have developed node embedding approaches that are speciﬁcally designed to capture structural roles.”
A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “Struct2vec [145] considers the structral identify of nodes by a hierarchical metric for node embedding.”
Learning Structural Node Embeddings via Diffusion Wavelets (2017, methodology): “Similarly, struc2vec [27] uses a heuristic to construct a multilayered graph based on topological metrics and simulates random walks on the graph to capture structural information.”
Deep Graph Contrastive Representation Learning (2020, methodology): “However, DeepWalkbased methods can be seen as reconstructing the graph proximity matrix, such as high-order adjacent matrix [4], which excessively emphasize proximity information defined on the network structure [5].”
Graph Learning: A Survey (2021, neutral): “[95] formulated a framework named Struc2vec.”
Log2vec: A Heterogeneous Graph Embedding Based Approach for Detecting Cyber Threats within Enterprise (2019, background): “Word2vec-based graph embedding is another kind receiving high concerns [14, 39, 42, 54].”
Network Representation Learning: A Survey (2017, background): “struct2vec [38] first encodes the vertex structural role similarity into a multilayer graph, where the weights of edges at each layer are determined by the struc-”
AliGraph: A Comprehensive Graph Neural Network Platform (2019, methodology): “A series of classic GNNs such as Structure2Vec [42], GCN [30], FastGCN [7], AS-GCN [24] and GraphSAGE [20] can be characterized by instantiating the operators in the framework.”
Continuous-Time Dynamic Network Embeddings (2018, background): “Future work will investigate using the continious-time dynamic network framework to generalize heterogeneous network embedding methods [18] and attributed network embedding methods [38], among other approaches [26, 56].”
Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network (2018, background): “Struc2vec [28] exploits additional structural equivalence of two nodes for node embedding.”
Multi-scale Attributed Node Embedding (2019, methodology): “…learning latent space representations of nodes such that those that share neighbors (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016; Perozzi et al., 2017), structural roles (Ribeiro et al., 2017; Ahmed et al., 2018) or attributes are located close together in the embedding space.”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “sks are often link prediction and clustering. However, once the literature started deﬁning relative node closeness with respect to structural neighborhood similarities (e.g., Henderson et al. (2012); Ribeiro et al. (2017); Donnat et al. (2018)), node embeddings and structural representations became ”
Adversarial Graph Augmentation to Improve Graph Contrastive Learning (2021, methodology): “Experiments showed that these GNN models learn to over-emphasize node proximity [23] and may lose subtle but crucial structural information, thus failing in many tasks including node-role classiﬁcation [16,35,37,38] and graph classiﬁcation [17].”
Graph embedding on biomedical networks: methods, applications and evaluations (2019, methodology): “Further, struc2vec (Ribeiro et al., 2017) is proposed for better modeling the structural identity (e.g., nodes in the network may perform similar functions).”
Geom-GCN: Geometric Graph Convolutional Networks (2020, methodology): “phily holds (i.e., similar nodes are more likely to be proximal, and vice versa), but may be inappropriate to the disassortative graphs (Newman, 2002) where node homophily does not hold. For example, Ribeiro et al. (2017) shows disassortative graphs where nodes of the same class exhibit high structu”
Graph Contrastive Learning with Augmentations (2020, methodology): “On a parallel note, for graph data, traditional methods trying to reconstruct the adjacency information of vertices [22, 23] can be treated as a kind of “local contrast”, while over-emphasizing the proximity information at the expense of the structural information [24].”
Link Prediction Based on Graph Neural Networks (2018, background): “Latent features cannot capture structural similarities between nodes [11], and usually need an extremely large dimension to express some simple heuristics [12].”