{'fraction_non_alphanumeric': 0.03952011291460833, 'fraction_numerical': 0.009433074570689249, 'mean_word_length': 4.887950138504155, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding

While most network embedding techniques model the relative positions of nodes in a network, recently there has been significant interest in structural embeddings that model node role equivalences, irrespective of their distances to any specific nodes. We present PhUSION, a proximity-based unified framework for computing structural and positional node embeddings, which leverages well-established methods for calculating node proximity scores. Clarifying a point of contention in the literature, we show which step of PhUSION produces the different kinds of embeddings and what steps can be used by both. Moreover, by aggregating the PhUSION node embeddings, we obtain graph-level features that model information lost by previous graph feature learning and kernel methods. In a comprehensive empirical study with over 10 datasets, 4 tasks, and 35 methods, we systematically reveal successful design choices for node and graph-level machine learning with embeddings.


Introduction
Node embeddings model node similarities in a multidimensional feature space: the more similar two nodes are in a network, the closer they lie in this space. Two broad categories of node similarity are prevalent in the literature: (i) positional proximity, which embeds close nodes similarly [1]; and (ii) structural similarity, which embeds nodes similarly if they have similar roles or patterns of interaction with other nodes, irrespective of their relative locations [2]. In turn, these similarities lead to positional or proximity-preserving embeddings, and structural or role-based embeddings, respectively.
Characterizing the relationship between proximitypreserving and structural node embeddings is an open and contested problem, with recent works making opposing claims. For instance, Rossi  ize these classes of methods as fundamentally different methodologically and in terms of applications [3]. Meanwhile, concurrent work proposed a theoretical framework in which the analogous concepts are actually equivalent for downstream tasks [4]. However, according to [3], it is unclear how this theoretical framework maps onto real-world graph mining methods.
A seminal work, NetMF [5], showed that various positional node embeddings amount to the same embedding technique (matrix factorization) applied to various matrices capturing pairwise node proximity scores. Going further, we propose PhUSION, a proximitybased unified framework for computing structural and positional node embeddings. PhUSION has three steps: (i) computation of pairwise node proximities, (ii) application of a nonlinear filter, and (iii) application of a dimensionality-reducing embedding function. We show which steps can be used for proximity-preserving or structural embedding and which step makes them different, revealing similarities and differences between the two classes of methods.
Additionally, PhUSION generalizes existing methods and yields novel ones from 35 different combinations of design choices, some of which improve on the variations studied in the literature. We extensively perform an empirical study of possible design choices for both structural and proximity-preserving node embeddings, to understand what works and why. In particular, nonlinear filtering has very recently been identified [6] as a key ingredient to the success of proximity-preserving node embedding. We analyze this observation in much greater detail for proximity-preserving embeddings and for the first time apply it to structural embeddings.
We extend PhUSION to embed entire graphs, a problem for which separate solutions have been proposed using graph signatures and similarity scores derived from node proximity matrices [7,8] and aggregated structural node embeddings [9]. Since we have shown that node proximity matrices can be used to derive structural node embeddings, we interpret previous methods [7,8] as embedding aggregation; we use PhU-SION to learn more expressive graph features by ag-gregating our more informative node embeddings, that model information we show that previous works cannot.
Our contributions are summarized as follows: • Unifying Embedding Perspective: We propose PhUSION, which can use pairwise node proximity matrix to generate embeddings that model node similarity based on structural roles or positional proximity. Our analysis of PhUSION shows the technical similarities and differences between structural and proximity-preserving node embeddings, a contested open question [3,4]. • Study of Successful Design Choices: On benchmark tasks for proximity-preserving and structural embedding choices, we investigate the combination of node proximity matrices, nonlinear transformation, and embedding functions. Our results uncover new insights that can improve both proximity-preserving and structural embeddings. • Graph-Level Learning: We turn PhUSION into a method for learning features for entire networks from their node proximity matrices based on node embedding aggregation. We interpret previous graph kernels [8] and feature learning methods [7] as simplified versions of PhUSION, and show what information we can capture with more expressive design choices that these previous works cannot.

Related Work
Frameworks for Node Embedding. Node embeddings are latent feature vectors for nodes in a network that are similar for similar nodes. Most embedding methods define node similarity in terms of proximity (e.g. direct or indirect connection) within a single graph. In contrast, structural embedding methods capture a node's structural role independent of its proximity to specific nodes; this independence makes embeddings comparable across distant parts of a graph [10] or separate graphs [11,9]. Both kinds of embeddings may be obtained using a diverse range of shallow and deep learning methods. For more information, we refer the reader to a survey [1] on proximity-preserving or positional embeddings, and a recent comprehensive empirical study on structural or role-based embeddings [10]. The plethora of node embedding methods has raised interest in finding unifying frameworks for different methods, which can also lead to new technical advances. For example, many proximity-preserving embedding methods were shown to implicitly factorize different proximity-based node similarity matrices; this insight inspired the NetMF method based on explicit ma-trix factorization [5]. It is known that many (proximitypreserving) node embedding methods can be summarized as a two-step process of node similarity matrix construction and dimensionality reduction [12]. However, PhUSION is the first framework to subsume both proximity-preserving and structural embedding methods. Moreover, in light of recent work [6], we carefully study a third step of applying a nonlinearity before performing dimensionality reduction. Graph Comparison. For comparing entire graphs, aggregating node embeddings (as we do) is competitive to deep neural networks, graph kernels, and feature construction [9]. Because a graph's node proximity matrix captures important information, many works have sought to use this within-graph information for cross-graph comparison. A challenge is that nodes in different graphs may not correspond. Feature learning method NetLSD [7] and graph kernel RetGK [8] solve this problem by only considering node self-similarities, which forgoes directly modeling a node's similarity to other nodes (cross-node similarities). Other graph similarity functions such as DeltaCon [13] model crossnode similarities, but are restricted to graphs defined on the same set of nodes. However, PhUSION can model within-graph cross-node similarities for more expressive general cross-graph comparison.

Unified Theoretical Framework
In this section, we present the abstract steps of our PhU-SION framework for node and graph feature learning, before describing concrete choices in the next section.
Preliminaries. We consider a graph G with node set V and adjacency matrix A containing edges between nodes. We learn an n × d matrix Y of d-dimensional node embeddings, where the i-th row Y i is a feature representation for node i. For ease of reference, we define common quantities for graph learning and node embedding, along with parameters specific to certain node proximity functions, in Tab. 1. Structural vs Positional Embeddings. Structural node embedding should learn similar features for automorphically equivalent or near-equivalent nodes [10,4], even if they are distant from each other in the network. On the other hand, for nodes to have similar positional embeddings, they must be close in the network. Although these are two very different embedding outcomes, the steps we present below can generate either kind of embedding; later, we will show concretely where the difference arises.
3.1 Node Feature Learning For learning node features from a graph with adjacency matrix A, we perform the following three steps:  PPMI [5] vol(G) Σi,jAij T Window size b Parameter for negative sampling Heat kernel [2,7] gs Filter kernel with scaling parameter s Λ Diagonal matrix of eigenvalues of L U Eigenvectors of L (L = UΛU T ) FaBP [14] hh [15] β Decay parameter Step 1: Calculate node proximities S using a function Ψ(A); Step 2: Filter these proximities via a nonlinearity func-tionS = σ(S); and Step 3: Embed the transformed proximities using a dimensionality reduction function: Y = ζ(S).
Our node embedding framework can be precisely summarized by function composition: Multiscale Node Embeddings. Many proximity functions can be tuned with scaling parameters to capture more local or global proximity [2,16]. We can create multiscale embeddings by concatenating embeddings using the same node proximity function at several different scales: where embeddings at each individual scale are computed with Eq. (3.1) using the desired scale parameter to compute node proximity: Y (si) = ζ(σ(Ψ(A; s i ))).

Graph Feature Learning
We can aggregate a graph's node embeddings into a single feature vector that describes the entire graph using a function ρ():

4.1
Step 1: Computing Node Proximities Ψ(). The first step of our framework, PhUSION, is to create a matrix of pairwise node proximities S ∈ R n×n . S ij should be large for nodes that are close in the graph (e.g. neighbors) and small for faraway nodes. Different proximity matrices have been used not only for node embedding but throughout graph mining, including: • Positive pointwise mutual information (PPMI) [5]: • Heat kernel (HK) [2]: S = Ug s (Λ)U . • Belief Propagation (FaBP) [14]: S = (I + aD − cA) −1 .

4.2
Step 2: Nonlinear Transformations of Node Proximities σ(). As a preprocessing step before embedding, we can filter the node proximities with a nonlinear function σ(S). Recent work [6] argues that such nonlinearity is largely responsible for the performance gain of recent deep learning-inspired node embedding methods. Thus, we consider the following functions: • No nonlinearity: σ(S) = S (Identity function).
• Elementwise logarithm (Log): For proximitypreserving embedding with PPMI, we set σ(S) i,j = log(max{S i,j , 1}) [5]. For other matrices with values concentrated in [0, 1], we propose to keep more information by only filtering out negative or zero elements: where min(S + ) is the smallest positive element in S. • Thresholded binarization (Bin-p) [6]: Let a ∈ N be the p-th percentile (p% smallest element) in S. Then σ(S) is defined elementwise as: Step 3: Embedding Node Proximities ζ(). Given a (filtered) similarity matrixS, node embeddings learn low-dimensional feature representations using various dimensionality reduction techniques. We represent the embedding process as a function ζ(S).
with singular value decomposition (SVD) [5]. Based on rank-d SVDS ≈ U d Σ d V d , we can obtain the node embeddings as ζ(S) = U d Σ 1 2 d . • Another way to generate a d-dimensional embeddings from an n × n similarity matrixS is characteristic function sampling (CFS). For even dimensionality d, we compute the embedding of each node u by sampling real and imaginary components from its empirical characteristic function, φ u (t) = n v=1 exp(itS vu ), evaluated at d 2 evenly spaced landmarks t 1 , . . . , t d/2 between 0 and 100 [2]. CFS is a permutationinvariant function applied row-wise toS that models the distribution of a node's proximity scores [2].
Proof. We give the constructions in App. A.1.

What Makes Node Embeddings Positional or Structural?
We isolate the embedding function ζ() as the responsible design choice for making PhUSION yield positional or structural embeddings. Concretely, embedding a proximity matrix using SVD produces positional embeddings, while using CFS (or any other permutation-invariant row function) produces structural embeddings. On the other hand, any choice of Ψ() and σ() can yield positional or structural embeddings. Theorem 4.2. Let connected graphs G 1 , G 2 have an isomorphism π : V 1 → V 2 , i.e. a bijective mapping between the nodes and A 2 = PA 1 P , where the binary matrix P has nonzero elements exactly at the entries so that π encodes an automorphism within G. Assume that node proximity and nonlinearity functions Ψ() and σ() preserve this automorphism: . Also assume that disconnected nodes have proximity score 0 (unchanged by nonlinearity), so thatS = σ(Ψ(A)) = [S 1 , 0; 0,S 2 ]. Let Y be the combined embeddings of G, which can be split into embeddings Y (1) and Y (2) corresponding respectively to the nodes originally in G 1 and G 2 . Then: 2. If Y = CFS(S), or more generally any permutationinvariant function ζ(S), then Y π(i) .

Proof. See supplementary App. A.2.
Note: Some existing methods learn structural embeddings with implicit or explicit matrix factorization [19,11], which in PhUSION would produce positional embeddings. The key difference is that these methods do not factorize a pairwise node proximity matrix, but a structural similarity matrix (where disconnected nodes may have a nonzero similarity score). One advantage of PhUSION is that the node proximity matrices we use are well studied throughout graph mining.

Unifying Graph Embedding Methods
Our PhUSION framework also produces features that describe an entire graph, when we aggregate its nodes' embeddings into a single feature vector. Here, we show that two recent graph kernels and feature maps are in essence special cases of PhUSION.
PhUSION:NetLSD. NetLSD computes graph features from its heat kernel matrix at multiple scales [7]. For scales s 1 , . . . , s d , the resulting d-dimensional feature vector has as its i-th entry h (si) , the trace of the heat kernel matrix at scale s i . For size invariance, the authors propose normalizing an n-node graph's features by the heat trace of the n-node empty graph, which amounts to multiplying by 1 n . Thus, the exact normalized NetLSD features are: Theorem 5.1. NetLSD (using the heat kernel with empty graph normalization) is a special case of Eq. Proof. At scale s k , the one-dimensional node embedding of node i is given by y ii . Thus, for d scales s 1 , . . . , s d , the multiscale embedding of node i given by Eq.
ii ]. Aggregating these node features into graph features using Eq.
. When S is the heat kernel matrix, each term becomes Tr(S (si) ) = h (si) .
PhUSION:RetGK. The scalable graph kernel (RetGK II ) [8] based on approximate feature maps [20] is defined as where the j-th entry of y i is the return probability of a random walk of length j starting from node i (formally R j ii ), and φ is a feature map approximating a vector-valued kernel [20]. It can thus be seen that RetGK has essentially the same form as the other methods: Theorem 5.2. Without node attributes and with φ and κ both set to the linear kernel, RetGK is a special case of Eq. (3.3) where: for multiple values of the parameter s, Ψ() computes the graph's s-step random walk transition matrix as its proximity matrix S, ζ(S) = diag(S), σ() is the identity function, and ρ() averages the embeddings.
In practice, [8] proposes to set φ to be a random Fourier feature map to approximate the Gaussian kernel [20], and κ to be a Gaussian or Laplace kernel, applying the successive embedding trick used for graph kernels [21]. Node attributes may be incorporated by taking the Kronecker product of the attribute vectors with the embeddings [8]. All of these techniques readily apply to any of the other methods we have proposed.

Expressive Graph Comparison with PhUSION.
Postprocessing aside, we can interpret RetGK and NetLSD as instances of PhUSION: they average multiscale embeddings learned from different node proximity matrices (HK for NetLSD, RW for RetGK). However, they use a 1-dimensional embedding function mapping nodes to their corresponding diagonal elements in S. Of course, this simple embedding loses off-diagonal information in S (namely, inter-node proximities), which our embeddings capture. To show the greater expressivity of our embeddings Y by a fair comparison, we also use mean pooling for our ρ(Y), although more complex aggregation functions could be used [9].

Experiments
To extensively evaluate PhUSION in a variety of contexts, we consider several real datasets for node classification (Tab. 2a) for which positional and structural role-based embeddings have been shown to be most effective ( § 6.1). For the latter, we also use synthetic data exhibiting clear role equivalences, the structure of which we can precisely control [2,10]. We also evaluate aggregated structural embeddings for graph classification ( § 6.2) on real benchmark datasets (Tab. 2b). 6.1 Node-level Embedding. First we evaluate PhUSION in the node classification task with positional and structural node embeddings. Setup. We combine 7 node proximity functions Ψ() and 5 different nonlinearities σ() (including Identity). Following our theoretical analysis ( §4.4), we use SVD to generate positional node embeddings and CFS to generate structural embeddings. In total, the PhUSION framework gives us 35 different node embedding methods of each type, including positional embeddings NetMF [5], InfiniteWalk [6], and HOPE [15] and structural embedding method GraphWave [2] as special cases. We tune hyperparameters with grid search and report the procedure and best parameters in App. B. Interestingly, we find that the best parameters strongly model local node proximity. We follow the supervised machine learning setup of [19]: we randomly sample 80% of the dataset for training and the rest for testing. For multi-label prediction, we use the one-vs-rest logistic regression model [5] and evaluate using micro-F1 scores.
6.1.1 Positional Node Embedding. We report raw results for all 35 positional node embedding methods derived from PhUSION in Fig. 1. Table 3 performs a drilldown on a per-design choice basis.
Results. We can see that PPMI does an excellent job, while L + is also competitive. As for the nonlinearity σ(), our findings support recent work [6] that adding nonlinearity is a critical part of outperforming the original spectral embedding approaches: it is almost always beneficial for all proximity matrices. On average, we find that Log does the best; however, Bin-p also performs better than Identity (no nonlinearity), and indeed the best embedding method for two of the three datasets (PPI and Wikipedia) uses binarization.
The use of binarization as nonlinearity and L + for proximity was proposed by InfiniteWalk [6], and the use of PPMI node proximities with Log nonlinearity is the NetMF method [5]. Our findings confirm that these recently identified design choices are indeed among the most successful overall. However, new design choices are competitive with them and may warrant further exploration. Moreover, no single choice of nonlinearity function σ() performs best, nor does performance vary monotonically with the sparsity of the resulting matrix (Bin-50 performs better than both Bin-5 and Bin-95). Corroborating [6], deeper characterization of various choices of σ() and their effects is of continued interest. Observation 1.(1) Nonlinearity has a complex effect, Figure 1: Node classification performance (micro-F1 scores) with positional embedding. Nonlinearity generally helps, but the best nonlinearity function varies across proximity matrices, and the best proximity matrix varies across datasets. but is essential in improving the performance of positional node embedding. (2) Generally, design choices identified by recent works [5,6] are among the most successful across datasets, but new combinations are often competitive.
6.1.2 Structural Node Embedding. We now evaluate the 35 methods we obtain from the PhUSION framework for structural role-based node embedding in two major tasks, node classification and clustering.
Node Classification. We again perform supervised machine learning to predict the node labels from the node embeddings, but in this case on datasets where the labels correspond to nodes' structural roles. We plot the accuracy of each combination of design choice in Fig. 2, and the average rank, mean and maximum accuracy of each individual design choice in Tab. 4. Node Clustering. Following the literature on structural node embedding [2,10], we also assess our methods us-ing networks that are constructed to manifest distinctive structural roles. Our goal is to cluster nodes with similar structural roles. We follow the dataset construction (cf. App. C) and clustering setup of [2]. These datasets exhibit clear role equivalence (perturbed by noise). For brevity, we only report results from embeddings without nonlinearity. We assess the clustering quality using homogeneity, completeness, and silhouette score.
Results. Node Classification. We see different trends than positional node embeddings. In this case, nonlinearity is not always helpful; indeed Identity is on average much more competitive. However, all datasets, using another proximity method or nonlinearity improves on GraphWave as proposed, highlighting the flexibility of PhUSION. We find that a very simple nonlinearity, binarization, produces the best methods on two datasets: as CFS models the distribution of entries in each row, embedding a binary distribution simply models how many large proximities a node has to other  nodes. This corroborates a recent claim [10] that simple structural information suffices for these datasets. Node Clustering. The results in Tab. 4 (right) show that a variety of proximity matrices successfully cluster nodes by their structural roles, in some cases better than the heat kernel used in GraphWave [2]. We show similar results on unperturbed graphs in the supplementary § C.
Observation 2. Within our PhUSION framework, we discover design choices for structural embedding that improve on downstream tasks compared to existing methods. In particular, we discover that some design choices used for positional node embeddings, like nonlinearity, can improve structural embeddings as well.

Comparing Design Choices for Positional & Structural Embeddings.
Based on all our nodelevel experiments, we see that although the same design choices prior to embedding (Ψ(), σ()) can be used for po-sitional or structural embeddings, in practice the best design choices for each kind of embedding tend to be different. For instance, nonlinearity is almost always helpful for positional node embeddings, but only sometimes helpful for structural embeddings. Proximity functions PPMI and L + tend to be successful for positional node embeddings, but do not produce the best structural embeddings (clearly seen on the clustering tasks). This analysis raises an important question: Can we characterize node proximity matrices that produce good embeddings of either type? We perform initial exploratory analysis in App. E, investigating properties of the matrices produced by each combination of Ψ() and σ(). We find that the row-wise sums of elements in matrices producing good positional node embeddings tend to have a bell-shaped distribution, whereas we observe power-law distributions in matrices that produce good structural embeddings. Table 5: Graph classification using averaged node embeddings (Eq. 3.3) and baselines (gray). We improve on NetLSD (3/3 datasets) and RetGK (2/3 datasets), which leverage simpler features from HK and RW matrices, using our embeddings of these matrices. We may also use different proximity matrices like Adj, which can further increase performance. embeddings may begin with the same node proximity designs, in practice the best designs for each kind of embedding method tend to differ.

Observation 3. While positional and structural node
This may be one reason why the survey work [3], characterizing existing examples of positional and structural node embedding methods, judged their methodology to be fundamentally different (even though our framework and the theory of [4] show a methodological connection in principle).

Graph-Level Embedding. We now investigate
PhUSION's effectiveness in learning graph features from various node proximity matrices. Intuitively, we expect that our more expressive features will allow us to classify graphs more accurately than previous works.

Setup.
Our experiments evaluate the graph classification accuracy on PTC-MR, IMDB-M and PROTEINS datasets [22]. As our focus is learning from the graph structure alone, we ignore node attributes. We only use CFS (i.e. structural embeddings), which are comparable across graphs [9], and do not use nonlinearity σ() as the baselines do not. We use a linear SVM to predict graphs' labels from their features; we report the 10-fold cross-validation accuracy averaged over 5 trials [9].
We compare against NetLSD [7] and RetGK [8], alternative ways of deriving graph features from HK and RW proximity matrices, respectively ( §5). We use NetLSD's default 250 heat kernel values logarithmically spaced in the range {10 −2 , 10 2 }. We run RetGK using its defaults of 50th-order random walk return probabilities and its proposed exact and approximate successive kernel embedding (κ and φ in §5). We describe our hyperparameter settings in supplementary App. B; we parallel the settings of NetLSD and RetGK, and carefully avoid giving ourselves any unfair advantage over them (in fact, they have a slight advantage if anything: we leave NetLSD with its default higher dimensionality and RetGK with its default successive kernel embeddings).
Results. In Tab. 5, we see that our methods generally improve on NetLSD and RetGK as a way of getting graph features from their node proximity matrices. In particular, embedding RW using Eq. 3.2 outperforms RetGK, which is also based on the RW proximity matrix, on two out of three datasets (PTC-MR and IMDB-M). Similarly embedding HK outperforms NetLSD, which also uses the heat kernel matrix, on all three datasets (and outperforms all other methods on two datasets). This is strong evidence that by modeling each node's full distribution of proximities rather than its self-proximity, PhUSION captures more useful information.
Because we keep the embedding dimension the same as (or lower) than NetLSD and RetGK, which capture only a single value for a node at each proximity scale (whereas we return a 10-dimensional embedding), we necessarily consider much fewer scales. Our good comparative performance indicates that modeling more graph information at fewer scales is generally superior to modeling less information at more scales.
Observation 4. PhUSION gives us a way to learn graph features from a given node proximity matrix that yield greater accuracy than previous works [7,8], likely because of their expressivity ( § 5).

Additional Analysis.
For all our classification tasks, we also study the effect of proximity order for multiscale embeddings in the supplementary App. D. In general, we find that modeling strongly local information with low-order proximity yields good performance (and is computationally cheapest).

Conclusion
We have proposed the first unifying perspective that encompasses both proximity-preserving and structural node embedding methods, clarifying their contested technical relationship [4,3]. This allows us to learn either kind of node embedding from any node proximity matrix that can be computed on a graph, which arises throughout the field of graph mining. Our threestep framework PhUSION opens up a variety of design choices (we empirically study 35), encompassing existing methods and also producing novel ones. We provide insights into productive design choices for nodelevel graph mining using either kind of embedding. By aggregating a graph's embeddings, we can derive graphlevel features from the node proximities; we show pre-cisely what information we can capture that is lost by other graph kernels and feature learning methods.
Within PhUSION there is still room to explore more design choices, such as other embedding functions (e.g. nonlinear autoencoders used by a few methods for positional node embedding [17], or trainable characteristic function sampling recently proposed for node and graph embedding [23]). For graph embedding, other designs use successive kernel embedding and the incorporation of node attributes [8]. Furthermore, fast approximate computation of node proximities can allow PhUSION to scale to very large graphs [5,2].

A Proofs
A.1 Existing Node Embedding Methods as Special Cases of Eq. (3.2). For all the methods in Theorem 4.1, we list the specific choices of node proximity Ψ(), nonlinearity σ(), and embedding ζ() functions (as well as whether or not they use multiscale proximity) that make them conform to our framework.
• GraphWave [2]: the node proximity Ψ() computes the graph's heat kernel matrix, the nonlinearity σ() is the identity function, and the embedding function ζ() is characteristic function sampling. The multiscale version of GraphWave is given by Equation 3.2.
• InfiniteWalk [6]: the node proximity Ψ() computes the PPMI matrix in the window size limit T = ∞, or the Laplacian pseudoinverse L + as an approximation of this quantity up to a low-rank correction term. The nonlinearity σ() is Log (or, for the Laplacian pseudoinverse, the authors consider Bin-p), and the embedding function ζ() is SVD.
• HOPE [15]: the node proximity Ψ() computes the personalized pagerank matrix or the common neighbors matrix A 2 , the nonlinearity σ() is the identity function, and the embedding is SVD (possibly approximated for scalability [15]).
• GraRep [16]: the node proximity Ψ() is derived from powers of the adjacency matrix, the nonlinearity σ() is Log, and the embedding function is SVD; this method computes multiscale node embeddings by concatenating embeddings derived from different powers of the adjacency matrix.
• sRDE [18]: the node proximity Ψ() in a signed network is computed using a signed random walk with restart procedure, the nonlinearity σ() is the identity function, and the embedding function ζ() consists of computing a histogram (which is also permutationinvariant) of each node's signed proximity scores.
A.2 Embedding Functions that Produce Positional vs. Structural Node Embeddings Here we give the proof of Theorem 4.2: Proof. Part 1: SVD yields different embeddings for automorphic nodes. Recall that finding the SVD ofS = [S 1 , 0; 0,S 2 ] is equivalent to finding the eigendecomposition ofSS : the singular vectors (columns of U) are the eigenvectors and the singular values (diagonal entries of Σ) the square roots of eigenvalues ofSS . Since the embeddings are formed from the first d columns of U and Σ, we equivalently analyze the eigendecomposition ofSS .
1.S 1 andS 2 are similar matrices and thus have the same eigenvalues and eigenvectors.
2.SS has the same eigenvalues asS 1 (equivalently, S 2 ). First, we show that all eigenvalues ofS 1 ,S 2 are eigenvalues ofSS : Conversely, we also show that all eigenvalues ofSS are eigenvalues ofS 1 ,S 2 . Without loss of generality we can write any eigenvector v ofS split in half and thusS 1 v 1 = λv 1 andS 2 = v 2 , meaning that λ is also an eigenvalue ofS 1 andS 2 . This is of course an extreme case for a highly contrived example (perfectly automorphic nodes in perfectly disconnected components of a graph), but in general we can see (and the research community has found experimentally on real-world networks) that the SVD embeddings encode positional rather than structural information, and nodes in very different parts of the graph will generally not be close in the embedding space. Part 2: Permutation-invariant row functions such as CFS yield identical embeddings for automorphic nodes. Let n be the number of nodes in either graph G 1 or G 2 . Then the first n nodes in G correspond to G 1 and the second n nodes in graph correspond to G 2 . So for node i ∈ [1, . . . , n], the ID of its counterpart under the isomorphism π is π(i)+n. Thus, we want to show that the rows of node i and node π(i) + n iñ S are equivalent up to permutation. Formally, we show that for any i, j ∈ [1, . . . , n],S ij =S π(i)+n,π(j)+n . Let e i be the i-th standard basis. ThenS ij =S 1ij = e iS1 e j = e i P S 2 Pe j = e π(i)S2 e π(j) =S 2 π(i)π(j) = S π(i)+n,π(j)+n . This shows that any nonzero element in the i-th row ofS (which must occur in the first n elements) has a corresponding element among the second j elements of the (π(i) + n)-th row. Of course, the second n elements in the i-th row and the first n elements in the (π(i) + n)-th row ofS are zeros. Thus, these rows have the same elements and are identical up to permutation.

B Node Proximity Hyperparameters
For positional node embeddings: All embeddings have the standard 128 dimensions [5]. We tuned the hyperparameters of the node proximity functions PPMI, PPR, HK, and FaBP on the Wikipedia dataset via grid search over the following values: 3. PPMI: we tried window size T ∈ [2,5,10] and found that T = 10 achieves best performance.
4. FaBP: we tried parameter values a, c ∈ [0.01, 0.1, 1, 10], but in the end we found that the heuristic proposed in [14] for setting a and c works best: For graph classification: For HK, we use scale parameters s ∈ {0.01, 0.1, 1, 10, 100} to parallel NetLSD. For proximity functions computed by matrix powers (Adj and RW), we consider powers k ∈ {1, 2, 3, 4, 5}. At each of the five parameter settings, we learn 10-dimensional embeddings and use Eq. 3.2 to form a multiscale embedding with 50 dimensions (to match or stay below the modeling capacity of NetLSD and RetGK). Between NetLSD's higher (250) dimension and RetGK's successive kernel embeddings, our experimental setup gives NetLSD and RetGK each a small advantage.

C Clustering Structural Node Embedding:
Additional Details and Results We use the synthetic graph generation pipeline provided by GraphWave [2]. The graphs are given by 5 basic shapes of one of different types ("house", "fan", "star") [2] that are placed on a cycle of length 30. In the main paper, we add 10% random edges to perturb the otherwise perfect role equivalences of nodes in the same part of different shape; however, in Tab. 6, we include clustering results on noiseless networks exhibiting perfect role equivalence. We use agglomerative clustering (with single linkage) to cluster the node embeddings learned by each method.

D Proximity Order in Structural Embedding
The order of proximity that node embeddings model has been shown to be very important. While some methods by default model low-order (e.g. 2nd-order) proximities [10], other methods try to balance low-order and high-order proximities to capture local and global information. This has been done with multiscale embeddings, whether positional [16] or structural [2]. Setting hyperparameters that govern the order of proximity is thus important to understand. Setup. For node and graph classification, we consider the effect of varying the order for methods consisting of powers of a (filtered) similarity matrixS (i.e. Adj or RW) when computing multiscale embeddings (Eq. 3.2). We only consider up to 4th order for positional node embeddings due to the larger size of those datasets (which is also why we omit the largest dataset Blog-Catalog). For any value of k, we compute the embeddings from each power ofS,S 2 , . . . ,S k (using Log nonlinearity for positional node embeddings and Identity for structural embeddings, nonlinearity functions which performed well on average for each kind of embedding in § 6) and concatenate the resulting embeddings. Note that for graph classification experiments, we now learn a 50-dimensional embedding at each scale, as we are not comparing to baseline methods now.
Results. The results are shown in Fig. 3. We can see, confirming the intuition of prior structural embedding methods [10] that lower order proximity is sufficient for best performance and saves the computational expense of computing higher order node proximities (which amounts to additional multiplications of increasingly dense matrices).
Observation 5. Modeling low-order node proximity (however, beyond first-order proximity, or direct edge connections alone) is generally sufficient for both kinds of embedding methods.

E Proximity Matrix Properties for Effective
Node Embeddings A powerful tool for the design of future node embedding methods would be an intrinsic characterization of successful design choices for node embedding; this could allow for effective model selection without relying on extrinsic evaluation (i.e. performance on downstream tasks as in § 6). The node embedding step usually leverages standard dimensionality reduction techniques; from a graph mining perspective, the most interesting part is the construction of (potentially nonlinearly transformed) node proximities. Thus, we seek to understand: how can we characterize choices Ψ(σ(A)) that yield useful (positional or structural) node embeddings? While effective intrinsic analysis of node embedding methods is a major open question, we present some initial exploratory analysis to prompt further investigation.

E.1 Positional Embeddings
In a node proximity matrix, the sums of each row correspond to the total proximity scores each node has to all other nodes. Our Low order proximities are sufficient to achieve good performance.
intuition is that if we are to expect good positional node embeddings, most nodes should have a moderate amount of total proximity to other nodes-too low, and the embedding objective will have too little similarity information to learn an effective embedding; too high, and the embedding objective will try to embed this node indiscriminately similarly to many other nodes. Setup. In Fig. 4, we visualize the distribution of row sums of all node proximity matrices, arising from each combination of node proximity and nonlinearity function that we evaluated in this work. Results. Some of these distributions exhibit a bell curve shape with the values concentrated in the middle of the distribution, while others exhibit a power law distribution with a single long tail. (Note that for the Bin-5 nonlinearity, the tail is on the left as most values in the matrix are 1, so low row sums are the exception. In general, the tail consists of the large row sums, as is typical for most power law distributions.) Many successful design choices produce a bell shape In general, some of the best-performing embedding methods (darker colors) come from matrices whose row sum distributions follow a bell curve rather than a power law.
distribution of row sums. For example, the Log nonlinearity filter (the best-performing nonlinearity on average) produces bell-shaped row sum distributions for all proximity matrices. Bin-95 produces a somewhat bellshaped distribution for PPMI, one of the best-performing proximity matrices. In general, this lines up with our intuition to expect mostly moderate row sums.
Observation 6. Some of the matrices yielding the best positional node embeddings have a bell curve rather than a power law distribution of row sums: that is, most nodes have moderate total proximity scores to all other nodes.

E.2 Structural Embeddings
The CFS embedding method treats each row of the proximity matrix as a probability distribution. When learning structural embeddings using CFS, GraphWave notes that two cases will be uninformative for structural embedding: if the distribution of row entries is either too uniform or if it has too few nonzero values. Setup. To measure the row-wise uniformity of the matrices, we consider the variance of each row. Meanwhile, we use entropy to diagnose rows with a few large entries and otherwise mostly small ones. Thus, we plot the rowwise distribution of variances and entropy for each proximity matrix, as well as the distribution of row sums as in § E.1. For brevity, we do not consider nonlinearity. Note that for PPR and L + , we truncate entropy values close to −∞ to −10 for ease of visualization.
Results. For most proximity matrices, the row-wise distribution of all three statistics tends to follow a power law distribution. The row-wise sum and variance distributions for the PPMI matrix, which generally leads to some of the the weaker structural embedding methods, tend to follow this pattern much more noisily. Proximity matrices PPR and FaBP, on the other hand, tend to follow an extreme power law distribution with a very thin tail. This may indicate that a moderate power law distri- Figure 5: Distribution of row distribution statistics (degree, variance, and entropy) of proximity matrices (without nonlinearity) on USA Airports dataset used for structural embeddings. Methods leading to more accurate structural embeddings have darker color. Some of the best embeddings come from matrices whose rows' variance and entropy follow a power law distribution.
bution may be the most informative for structural embeddings. The contrast with proximity-preserving embeddings ( § E.1), where the most successful embeddings tended to come from matrices with a bell-curve distribution of row sums, corroborates our finding that the best positional and structural node embedding methods tended to use very different design choices.
Observation 7. Proximity matrices that yield good structural embeddings often follow a power law distribution of row-wise statistics. The contrast with Obs. 6 indicates that proximity matrices that lead to successful positional or structural node embeddings may have fundamentally different properties.