Learning Graph Representations via Structural Identity

79 concepts74 papers1 proposal

Most traditional graph representation and embedding techniques rely on a simple assumption: proximity implies similarity. If two nodes are close to each other in a network, or if they frequently co-occur in short random walks, they should have similar vector representations.

However, this spatial view of networks fails to capture a fundamental property of complex systems: structural identity. Consider two managers working in completely different companies, or two peripheral web pages on unrelated topics. They do not share connections, nor are they reachable within a few hops of each other. Yet, they perform identical functional roles within their respective local topologies.

A growing body of research shifts the focus from where a node is to what a node does. By defining similarity based on neighborhood structures rather than physical distance, these methods allow models to discover global structural roles—such as hubs, bridges, and outliers—across disconnected parts of a graph.


Extracting the Structural Fingerprint

To identify nodes with similar functional roles without relying on their specific coordinates or neighbor identities, we must construct a coordinate-free "fingerprint" of a node's surroundings. Researchers have approached this problem through several distinct mathematical lenses.

Neighborhood Degree Sequences and Alignment

One intuitive way to capture a node's role is to look at the connectivity profiles of its neighbors. As proposed by Daniel R. Figueiredo et al. in struc2vec: Learning Node Representations from Structural Identity, we can recursively evaluate a node's neighborhood by inspecting the ordered degree sequences at incremental hop distances (1-hop neighbors, 2-hop neighbors, etc.).

Because different nodes have varying numbers of connections, these degree sequences will naturally differ in length. To compare them robustly, the authors utilize Dynamic Time Warping (DTW). DTW aligns sequences of different lengths, allowing the framework to recognize structural equivalence even if one hub has slightly more connections than another. This sequence-alignment paradigm has been adapted to decentralized and specialized domains; for instance, Qiying Pan et al. in FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy and Minheng Chen et al. in Using Structural Similarity and Kolmogorov-Arnold Networks for Anatomical Embedding of Cortical Folding Patterns leverage DTW to align neighborhood signatures without requiring a global view of the graph's edges.

Node A (Hub) ----> 1-Hop Degrees: [10, 8, 7, 5]  \___ Aligned via DTW
Node B (Hub) ----> 1-Hop Degrees: [9, 9, 6]      /   (High Structural Similarity)

Diffusion and Spectral Signatures

An alternative to explicit sequence matching is to observe how information or energy flows outward from a node. Instead of counting edges, we can treat heat diffusion patterns as probability distributions.

In Learning Structural Node Embeddings via Diffusion Wavelets, Claire Donnat et al. demonstrate that characterizing these diffusion patterns via empirical characteristic functions provides mathematical guarantees of structural similarity. If two nodes distribute "heat" to their surroundings in the same way over time, they share an equivalent functional role, regardless of where they sit in the network.

Similarly, Charu Sharma et al. in Learning Representations using Spectral-Biased Random Walks on Graphs use neighborhood signatures derived from Laplacian spectra to bias random walks. Instead of stepping to a physical neighbor, the walk is biased toward nodes that share similar structural fingerprints, forcing the representation to prioritize global structural equivalence over local spatial proximity.


Reconstructing Neighborhood Distributions

Traditional graph autoencoders focus on link reconstruction—predicting whether an edge exists between node $u$ and node $v$. While effective for proximity-based tasks, this objective misses the broader topological context.

To capture structural identity, modern architectures reconstruct the entire distribution of a node's neighborhood. In Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction, Mingyue Tang et al. utilize Wasserstein distance (Optimal Transport) to measure the discrepancy between a node's true neighborhood distribution and its reconstructed counterpart. By optimizing for the global transport cost of the neighborhood rather than individual binary links, the latent space is forced to preserve structural roles.

Standard GAE:  Node A ---> Predicts Link to Node B (Local Proximity)
Wasserstein:   Node A ---> Reconstructs Neighborhood Shape (Global Role)

Once these structural signatures are mapped to valid distance metrics, they can be integrated directly into standard machine learning workflows. As shown by Yu Yang 0001 et al. in Measuring in-network node similarity based on neighborhoods: a unified parametric approach, transforming neighborhood similarity into metric spaces enables algorithms like K-means to automatically partition networks into distinct structural roles (such as hubs, mainstream nodes, and outliers) based purely on local connectivity patterns and subgraphs.


Overcoming Symmetries and Heterophily

Focusing on structural identity solves two major bottlenecks in deep learning on graphs: automorphic equivalence and heterophily.

Distinguishing Symmetrical Roles

Standard message-passing Graph Neural Networks (GNNs) often fail to distinguish nodes that share identical local symmetries, a limitation rooted in the Weisfeiler-Lehman isomorphism test. To break this limitation, Fengli Xu et al. developed Automorphic Equivalence-aware Graph Neural Network, which explicitly identifies structural roles using localized "Ego-AE" sets to capture symmetries within a node's immediate topology.

Furthermore, a node's absolute degree can often distort its structural profile. To decouple a node's connectivity pattern from its scale, Yicong Jiang et al. in Semi-supervised Community Detection via Structural Similarity Metrics utilize the cosine of the angle between connectivity vectors. This allows the system to group nodes that share similar linking profiles even if their total number of connections varies drastically.

Standard GNNs operate on the assumption of homophily ("birds of a feather flock together"). When a network exhibits heterophily—where connected nodes belong to different classes—standard message passing acts as a low-pass filter, washing out useful features.

By shifting to structural identity, models can navigate these non-assortative environments. For example, Dongxiao He in Block Modeling-Guided Graph Convolutional Neural Networks integrates classic social network block modeling into GCNs. Instead of uniformly aggregating features from neighbors, the model weights information based on the structural similarity of their classes:

$$\text{Weight}(u, v) \propto \text{StructuralSimilarity}(\text{Class}(u), \text{Class}(v))$$

This ensures that even if a node connects exclusively to neighbors of a different class, the network recognizes the underlying structural pattern of those interactions, allowing accurate classification and community detection across both homophilic and heterophilic graphs.

Key Foundational Work

Analyzing Reading Behavior by Blog Mining (2007) — contributed 1 concept elements to this direction.
Link communities reveal multiscale complexity in networks (2010) — contributed 1 concept elements to this direction.
Exploring the Power of Links in Data Mining (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_structural_similarity_clustering_259c68c6,
  title = {structural similarity clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-similarity-clustering/rdr_259c68c6731e43ce935a5d7762634995},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_structural_similarity_clustering_259c68c6_v1,
  title = {structural similarity clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structural-similarity-clustering/rdr_259c68c6731e43ce935a5d7762634995/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake