Source-linked AI summary
Learning Structural Node Embeddings Via Diffusion Wavelets
Claire Donnat, Marinka Zitnik, David Hallac, Jure Leskovec
TL;DR
Structural role discovery needs embeddings that recognize similar local network topologies even when nodes are far apart, without relying on manually selected features. GraphWave uses spectral wavelet diffusion distributions and empirical characteristic functions to learn such embeddings, with mathematical guarantees and edge-linear scalability. Across experiments, it outperforms state-of-the-art baselines, with reported improvements of up to 137%.
Problem
Structural embeddings should identify similar local network roles across distant graph regions, but existing methods can require manual features, lack robustness, or lack mathematical understanding.
Method
GraphWave learns node embeddings from spectral graph-wavelet diffusion patterns by treating wavelet coefficients as probability distributions and characterizing them with empirical characteristic functions.
Results
GraphWave outperforms state-of-the-art baselines across real and synthetic experiments, with improvements of up to 137%.
Takeaways & Limitations
GraphWave provides a scalable, mathematically analyzed approach for capturing structural similarity and recovering structurally similar or equivalent nodes.
Takeaways & Limitations
The formal guarantee is stated for nodes with identical K-hop neighborhoods, with K less than the graph diameter.
Abstract
from arXiv · showhide
Nodes residing in different parts of a graph can have similar structural roles within their local network topology. The identification of such roles provides key insight into the organization of networks and can be used for a variety of machine learning tasks. However, learning structural representations of nodes is a challenging problem, and it has typically involved manually specifying and tailoring topological features for each node. In this paper, we develop GraphWave, a method that represents each node's network neighborhood via a low-dimensional embedding by leveraging heat wavelet diffusion patterns. Instead of training on hand-selected features, GraphWave learns these embeddings in an unsupervised way. We mathematically prove that nodes with similar network neighborhoods will have similar GraphWave embeddings even though these nodes may reside in very different parts of the network, and our method scales linearly with the number of edges. Experiments in a variety of different settings demonstrate GraphWave's real-world potential for capturing structural roles in networks, and our approach outperforms existing state-of-the-art baselines in every experiment, by as much as 137%.
1 INTRODUCTION
Structural role discovery seeks nodes with similar local topologies even when they are far apart, but existing approaches often require manual features or lack robustness and scalable multidimensional embeddings. GraphWave addresses this by learning structural embeddings from spectral wavelet diffusion distributions and provides mathematical guarantees, scalability, and strong empirical performance.
- Motivation: Structural role discovery identifies nodes with topologically similar local neighborhoods despite potentially distant positions in the network.Such roles can represent similar functions, including managers in corporate social networks or enzymes in molecular networks.
- Motivation: Continuous unsupervised embeddings provide a way to define structural similarity without manually predefining discrete roles or inspecting graph structure.Nodes are ε-structurally similar when the distance between their embeddings is at most ε.
- Limitations of prior work: Existing structural-embedding methods can be sensitive to topology perturbations, require hand-labeled features, rely on non-scalable heuristics, or return only a single similarity score.These limitations motivate a mathematically grounded multidimensional approach.
- GraphWave: GraphWave learns multidimensional node embeddings from diffusion of spectral graph wavelets, whose coefficients encode graph topological properties without explicit hand-labeled features.The method probes each node by propagating unit energy through the graph and characterizing the network response.
- GraphWave: GraphWave treats wavelets as probability distributions and characterizes them with empirical characteristic functions, comparing diffusion shapes rather than the specific nodes receiving diffusion.This resolves the need for an exact one-to-one mapping between distant neighborhoods and captures higher-order distributional information.
- Results: GraphWave is linear in the number of edges and outperforms state-of-the-art baselines by up to 137% across real and synthetic experiments.The contributions include mathematical recovery guarantees for structurally similar or equivalent nodes.
2 LEARNING STRUCTURAL EMBEDDINGS
GraphWave constructs node embeddings from spectral graph-wavelet diffusion patterns, converts coefficient distributions into fixed-dimensional characteristic-function features, and compares the resulting vectors. Its multiscale design captures neighborhoods at different radii while Chebyshev approximation yields edge-linear computational complexity.
- Problem formulation: The problem is to learn a continuous multidimensional structural embedding for every node in an undirected graph.The embedding represents each node’s position in a space of structural roles.
- Diffusion wavelets: GraphWave applies a spectral graph wavelet centered at each node to obtain a diffusion pattern encoding the node’s local network topology.Wavelet coefficients can be interpreted through powers of the Laplacian, including degree, path counts, and mixed adjacency-degree terms.
- Distributional representation: Treating wavelet coefficients as a probability distribution removes the need to map neighborhood nodes one-to-one when comparing structurally similar nodes.Empirical characteristic functions characterize these distributions and make structural embeddings possible.
- Distributional representation: Each scale produces a 2d-dimensional embedding by sampling the empirical characteristic function at d points and concatenating real and imaginary values.The dimensionality is independent of graph size.
- Embedding comparison: The structural distance between nodes is the ℓ2 distance between their embeddings, corresponding to comparisons among moments of wavelet-coefficient distributions.GraphWave returns similar vectors for nodes with structurally similar local neighborhoods.
- Multiscale embeddings: Larger scaling parameters diffuse farther and encode broader neighborhoods, while multiple scales are concatenated into a multiscale embedding.The final multiscale representation lies in R^(2dJ).
- Scalability: O(K|E|) complexity makes GraphWave linear in the number of edges when Chebyshev polynomials approximate the wavelet computation.This supports scaling to large sparse networks.
3 ANALYSIS OF GRAPHWAVE
GraphWave’s analysis connects spectral graph wavelets to local topology and proves that structurally equivalent or similarly perturbed nodes receive similar embeddings.
- 3.1 Network structure via diffusion wavelets: Spectral graph wavelet coefficients characterize the topological structure of a node’s local network neighborhood.The coefficients encode connectivity and can be interpreted through degrees, cycles, and paths.
- 3.1 Network structure via diffusion wavelets: A K-th order polynomial approximation of each wavelet captures information about the node’s K-hop neighborhood.The approximation error is uniformly bounded by the residual bound.
- 3.2 Embeddings of structurally equivalent nodes: Structurally equivalent nodes have wavelet coefficients within 2ϵ under a one-to-one mapping of their identical K-hop neighborhoods.The matching follows from cancellation of the localized polynomial terms and the residual bound.
- 3.2 Embeddings of structurally equivalent nodes: With an appropriate diffusion scale, structurally equivalent nodes have ϵ-structurally similar GraphWave embeddings.Similarity of the wavelet distributions transfers to similarity of their empirical characteristic functions.
- 3.3 Embeddings of structurally similar nodes: Small perturbations of a node’s K-hop neighborhood produce small changes in its wavelet coefficients and similar GraphWave embeddings.The result assumes bounded perturbations of the powers of the graph Laplacian.
4 SCALE OF HEAT DIFFUSION WAVELETS
The paper selects heat-diffusion scales by analyzing coefficient variance and convergence, balancing sufficient diffusion against excessive convergence to a uniform state.
- Scale selection: GraphWave automatically finds an appropriate range of heat-kernel scaling values for its multiscale embeddings.The range is selected using theoretical results on heat-diffusion-wavelet variance and convergence.
- Scale selection: Small s yields trivial diffusion distributions, whereas larger s drives the network toward identical node temperatures.The selected scale range avoids both insufficient propagation and near-converged diffusion.
- Variance analysis: Variance of off-diagonal heat-diffusion-wavelet coefficients decreases monotonically with the scaling parameter s.The variance is analyzed as a function of the diffusion quantity ∆(s)_a.
- Selection of smax: smax is chosen to keep wavelet coefficients localized by requiring diffusion to remain above a threshold η.The bound uses the geometric mean of λ2 and λN to balance the two convergence scenarios.
- Selection of smin: smin is chosen to ensure that each wavelet has sufficient time to spread through the neighborhood.The suggested parameter values are η = 0.85 and γ = 0.95.
5 EXPERIMENTS ON SYNTHETIC GRAPHS
Synthetic experiments test GraphWave’s ability to recover structural roles, generalize across graph settings, and remain effective under perturbations. GraphWave outperforms the compared methods across unsupervised and supervised evaluations while offering scalable computation and graceful noise degradation.
- Planted structural equivalences: GraphWave correctly identifies structurally equivalent nodes in the barbell graph, unlike RolX and struc2vec.It also differentiates nodes connecting the two cliques through a gradient-like representation of their structural roles.
- Synthetic evaluation: GraphWave outperforms the other four methods in every reported metric across both unsupervised and supervised synthetic evaluations.Compared with struc2vec, average gains are 63% in homogeneity, 61% in completeness, 137% in silhouette, 46% in prediction accuracy, and 51% in F1 score.
- Visualization: GraphWave’s embeddings accurately distinguish six structural roles in cycle graphs with attached house shapes.The PCA projection shows structurally equivalent nodes overlapping, while characteristic functions visualize differences among role-specific wavelet-coefficient distributions.
- Generalization across graphs: GraphWave outperforms RolX and struc2vec on cross-graph classification, by 8% and 23% in F1-score and by 8% and 22% in accuracy, respectively.These results assess whether learned embeddings transfer structural signatures across different graphs.
- Scalability and noise: GraphWave’s running time is supported by wavelet-coefficient computation that is linear in the number of edges and uses sparse matrix operations.Its performance also degrades gracefully under strong noise.
6 EXPERIMENTS ON REAL-WORLD GRAPHS
Real-world experiments evaluate GraphWave on mirrored social, organizational email, and airline networks. Across these settings, GraphWave captures structural equivalences and outperforms the alternative methods on the reported comparisons.
- Mirrored Karate network: GraphWave identifies mirrored structural equivalents in the Karate network with 83.2% average accuracy, compared with 82.2% for RolX and 52.5% for struc2vec.Accuracy remains consistent as the number of mirrored edges varies from 1 to 25.
- Enron email network: GraphWave captures organizational structure in Enron, placing CEOs and presidents far from other job titles while keeping traders closer to directors.Struc2vec instead produces an almost uniform distribution of distances between job-title classes.
- Enron email network: GraphWave achieves 28% higher homogeneity and 139% higher completeness than RolX in separating top and lower-level Enron job titles.It performs even better relative to struc2vec in this comparison.
- European airline networks: GraphWave outperforms alternative methods on all three airline-network clustering metrics, exceeding RolX and struc2vec by 27% and 24% in homogeneity.Its completeness gains are 12% and 44%, respectively, with a substantially higher silhouette score.
- European airline networks: Across airline networks, GraphWave places airports with the same structural role near one another even when they belong to different airlines.The comparison highlights cross-network structural equivalence, whereas struc2vec embeddings are dominated by airline identity.
7 CONCLUSION
GraphWave generates structural node embeddings with spectral graph wavelets and characteristic functions, while providing mathematical guarantees and empirical gains over state-of-the-art baselines.
- GraphWave is evaluated on clustering results for Enron and airline networks.
- GraphWave generates a structural embedding for each node using spectral graph wavelets treated as distributions and evaluated through characteristic functions.Representing wavelets as distributions is identified as central to capturing structural similarity.
- Mathematical analysis proves that structurally equivalent or similar nodes receive near-identical or similar GraphWave embeddings.
- Experiments on real and synthetic networks provide empirical evidence for the analytical results and yield large gains over state-of-the-art baselines.