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 also be used to inform machine learning on graphs. However, learning structural representations of nodes is a challenging unsupervised-learning task, which typically involves manually specifying and tailoring topological features for each node. Here we develop GRAPHWAVE, a method that represents each node's local network neighborhood via a low-dimensional embedding by leveraging spectral graph wavelet diffusion patterns. We prove that nodes with similar local network neighborhoods will have similar GRAPHWAVE embeddings even though these nodes may reside in very different parts of the network. Our method scales linearly with the number of edges and does not require any hand-tailoring of topological features. We evaluate performance on both synthetic and real-world datasets, obtaining improvements of up to 71% over state-of-the-art baselines.
The term "structural equivalence" is used incorrectly in the paper.  From sociology, two nodes with the same position are in an equivalence relation.  An equivalence, Q, is any relation that satisfies these three conditions:
  - Transitivity: (a,b), (b,c) ∈ Q ⇒ (a,c) ∈Q
  - Symmetry: (a, b) ∈ Q if and only if (b, a) ∈Q
  - Reflexivity: (a, a) ∈Q
There are three deterministic equivalences: structural, automorphic, and regular.
From Lorrain & White (1971), two nodes u and v are structurally equivalent if they have the same relationships to all other nodes.  Exact structural equivalence is rare in real-world networks.
From Borgatti, et al. (1992) and Sparrow (1993), two nodes u and v are automorphically equivalent if all the nodes can be relabeled to form an isomorphic graph with the labels of u and v interchanged.
From Everett & Borgatti (1992), two nodes u and v are regularly equivalent if they are equally related to equivalent others.
Parts of this statement are false: "A notable example of such approaches is RolX (Henderson et al., 2012), which aims to recover a soft-clustering of nodes into a predetermined number of K distinct roles using recursive feature extraction (Henderson et al., 2011)."  RolX (as described in KDD 2012 paper) uses MDL to automatically determine the number of roles.
As indicated above, this statement is also false: "We note that RolX requires the number of desired structural classes as input, ...".
The paper does not discuss how the free parameter d (which represents the number of evenly spaced sample points)  is chosen. 
This statement is misleading: "In particular, a small perturbation of the graph yields small perturbations of the eigenvalues."  What is considered a small perturbation?  One can delete an edge (seemingly a small perturbation) and change the eigenvalues of the Laplacian dramatically --  e.g., deleting an edge that increases the number of connected components.
The barbell graph experiment seemed contrived.  Why would one except such a graph to have 8 classes?  Why not 3?  One for cliques, one for the chain, and one for connectors of the clique to the chain.
In Section 4.2, how many roles were selected for RolX?
The paper states: "Furthermore, nodes from different graphs can be embedded into the same space and their structural roles can be compared across different graphs."  Experiments were not conducted to see how the competing approaches such as RolX compare with GraphWave on transfer learning tasks.
Gilpin et al (KDD 2013) extended RolX to incorporate sparsity and diversity constraints on the role space and showed that their approach is superior to RolX on measuring distances.  This is applicable to experiments in Figure 4.
I strongly recommend running experiments that test the predictive power of the roles found by GraphWave.