# An Automorphic Distance Metric and Its Application to Node Embedding for Role Mining

Authors: Víctor Martínez; Fernando Berzal; Juan-Carlos Cubero
Journal: Complexity
 (2021)

---

## Abstract

Role is a fundamental concept in the analysis of the behavior and function of interacting entities in complex networks. Role discovery is the task of uncovering the hidden roles of nodes within a network. Node roles are commonly defined in terms of equivalence classes. Two nodes have the same role if they fall within the same equivalence class. Automorphic equivalence, where two nodes are equivalent when they can swap their labels to form an isomorphic graph, captures this notion of role. The binary concept of equivalence is too restrictive, and nodes in real-world networks rarely belong to the same equivalence class. Instead, a relaxed definition in terms of similarity or distance is commonly used to compute the degree to which two nodes are equivalent. In this paper, we propose a novel distance metric called automorphic distance, which measures how far two nodes are from being automorphically equivalent. We also study its application to node embedding, showing how our metric can be used to generate role-preserving vector representations of nodes. Our experiments confirm that the proposed automorphic distance metric outperforms a state-of-the-art automorphic equivalence-based metric and different state-of-the-art techniques for the generation of node embeddings in different role-related tasks.


---

## Body

## 1. Introduction

Role discovery is defined as the process of finding sets of nodes following similar connectivity patterns or structural behaviors [1]. The role of a node can be understood as the function that node plays in the network. Different studies have shown the importance of roles in different domains, including predator-prey food webs [2], international relations [3], or the function of proteins in proteomes [4].Unfortunately, this problem has received limited attention when compared to community detection [5–7], despite that role discovery identifies complementary information and has found applications in several useful network data mining tasks. For example, roles can be used to model and characterize the behavior of entities in a network, to predict structural changes, and to detect anomalies [8]. Since the same roles can be observed across different networks, this information has been successfully exploited for transfer learning [9]. Role information can also be used for enhancing the visualization of interesting patterns in graphs [10]. Additional applications of role discovery have been described in the scientific literature [1].Formally, two nodes have the same role if, given an equivalence relation, they belong to the same equivalence class [11, 12]. Different equivalence classes have been studied for nodes in networks.Structural equivalence, where two nodes play the same role if they are connected to exactly the same neighbor nodes, has been widely studied [13, 14]. These nodes will have exactly the same topological properties, such as degree, clustering coefficient, or centrality, since they are indistinguishable from a structural point of view. However, different authors have pointed out the limitations of structural equivalence for modeling roles or positions, which is the name that roles receive in sociology, since structural equivalence is more related to the concept of locality than the actual concept of role [15]. If the constraint of having to be connected to exactly the same neighbors is relaxed to being connected to neighbors with exactly the same topological function, we obtain automorphic equivalence classes, where two nodes are equivalent if they can swap their labels to form an isomorphic graph [16, 17]. Automorphically equivalent nodes will also have exactly the same topological properties, but, without the requirement of locality imposed by structural equivalence, pairs of nodes at distances larger than two can still have the same role. Therefore, automorphic equivalence is more closely related to the intuitive concept of role, which is understood as the function of a node within a network.Other equivalence classes, less relevant than the previously mentioned ones, are not covered in this work. Regular equivalence deserves a special mention due to its importance as a relaxation of automorphic equivalence that only requires being connected to nodes with the same function, omitting the actual count of connections [18]. Regular equivalence does not preserve topological properties and is more suited to hierarchically organized networks [2].These binary equivalences are strict mathematical abstractions that rarely occur in real-world networks, leading to all nodes being assigned a different role. In practice, equivalences are relaxed to similarities, allowing two nodes to play the same role by partially satisfying the constraints imposed by the mathematical definition of structural, automorphic, or regular equivalence.In this paper, we present a novel automorphic distance metric, capturing distances between nodes in terms of automorphic equivalence. According to the network structure, two nodes will be at a distance that is proportional to how far they are from being automorphically equivalent. This leads to a softer definition of automorphic roles, instead of forcing all nodes to fit in strict classes of roles. However, when needed, these distances can be used to discover and instantiate specific role classes. Our distance function satisfies metric axioms, as we prove below, does not require external parameters nor feature engineering, and is computable for nodes across different networks. We also present different applications of our proposal, with special emphasis on generating node embeddings that preserve node roles. Node embeddings are vector representations of nodes capturing relevant information in terms of pairwise distances [19]. Much work has been done in embedding techniques that preserve neighborhoods or communities [20–22]. However, role-preserving embeddings have only recently begun to be studied [23, 24].Our paper is structured as follows. In Section2, we discuss the relevant related work in automorphic distance metrics. In Section 3, we describe our proposed automorphic distance metric and study its admissibility as a distance metric, as well as its computational complexity. In addition, we present an approximated algorithm to compute our proposed automorphic distance that offers higher scalability. In Section 4, we analyze its performance for different role-related tasks and show how it outperforms previously proposed approaches. Finally, conclusions and suggestions for future research are presented in Section 5.


## 2. Related Work

Different metrics have been proposed to measure node similarity. One of the most popular metrics is SimRank [25], which iteratively computes similarity scores based on the hypothesis that two nodes are similar if they link to similar nodes. Different extensions of SimRank have been proposed [26]. SimRank recursively computes the similarity of two nodes according to the average similarity of all their neighbor pairs, which can also be interpreted, as suggested by its original authors, as how soon two random walkers will meet if they start from these nodes. Thus, this definition is not suitable as a metric of similarity capturing automorphic equivalence because it requires the two nodes to be close to play the same role. Other similarity measures not based on SimRank have been proposed, such as PageSim [27] and Leicht’s vertex similarity [28]. However, these similarities have been formally rejected as valid metrics for capturing automorphic equivalence [29].Since automorphic equivalence ensures the same topological properties, some authors have tried to capture automorphic equivalence by defining a similarity function over a set of network topological properties [30]. The problem of these feature-based methods is that they require combining different complex hand-crafted features provided by experts, which is far from a trivial process in practice. In addition, they cannot guarantee, which set of features will correctly approximate automorphic equivalence, resulting in a very limited approach for automorphic equivalence discovery.As far as we know, RoleSim [29, 31] is the only proposed metric that tries to formally capture the concept of automorphic equivalence without using limited approximations based on hand-crafted topological features. Omitting the decay factor they introduce, by setting it to 0 in order to capture the global network topology, this similarity measure is iteratively computed until convergence as(1)sx,y=maxMx,y∑u,v∈Mx,ysu,vdegx+degy−Mx,y,where degn is the degree of a node n and Mx,y is the optimal assignment of nodes in the neighborhood of x to nodes in the neighborhood of y maximizing the expression, that is, the pairs of neighbors of x and y with maximal similarity. In the original manuscript, this function is presented as a role similarity metric by proving the corresponding distance metric axioms. RoleSim is a form of generalized Jaccard coefficient based on a recursive definition of the similarity of neighbor roles. Despite the admissibility of RoleSim, their approach presents several limitations. The RoleSim similarity can be considered an automorphic distance by taking its complementary or Jaccard distance: dx,y=1−sx,y. The problem is that the Jaccard coefficient is a normalized metric, which leads to a normalized distance. As will be shown in our experimentation, this normalization has a negative impact on the results obtained by RoleSim. In addition, this similarity function exhibits serious inconsistencies. For example, in the graph shown in Figure 1, where node d has a one-to-many relationship to xi nodes, the node pair a,c has the same exact similarity as any pair a,xi, independent of the number of xi nodes. This simple example shows the limitations of RoleSim when trying to capture the automorphic similarity.Figure 1
Example graph where RoleSim yields inconsistent values. Noded has a one-to-many relation to xi nodes.As far as we know, no distance metric has been proposed that is able to capture the concept of automorphic distance in a consistent way, without relying on approximations based on extracted topological properties nor forcing the normalization of the distance function.


## 3. A Novel Automorphic Distance Metric

An isomorphism is a bijection between the nodes of two graphs where two nodes are adjacent in one graph if and only if the nodes that result from applying the bijective function are also adjacent in the other graph. An automorphism is an isomorphism from one graph to itself. Therefore, two nodes are automorphically equivalent if there exists an automorphism creating a correspondence between them.One form of testing for automorphic equivalence is computing the canonical form of graphs. Graph canonicalization is the task of computing a labeling for nodes in a graph such that every isomorphic graph yields the same canonical labeling. Given a canonicalized graph, two automorphically equivalent nodes must have been assigned the same label. As previously stated, automorphic equivalence is too restrictive to appear in real-world networks, leading to most nodes having different canonical labels.The solution that we propose to this problem is the definition of distances between labels, which ultimately allows the definition of distances between nodes based on the concept of automorphic equivalence. This distance will be proportional to the number of changes that need to be done in the network to transform one label or equivalence class into another. A zero distance implies that two nodes are automorphically equivalent and play exactly the same role. According to this distanced, we can say that nodes x and y are more automorphically similar or have a more similar role to u and v, if dx,y<du,v. In order to propose a valid distance metric, we must also prove that our metric satisfies the metric distance axioms.Our work is based on the 1-dimensional Weisfeiler–Lehman test of isomorphism [32, 33], also known as color refinement, which is an algorithm to compute the canonical labeling of graphs. These canonical labels can be used to solve related problems, such as the computation of efficient graph kernels [34]. The Weisfeiler–Lehman algorithm works by initially assigning a label to each node according to its degree, so nodes with the same degree have the same initial label. Then, the algorithm iteratively updates these labels by the following procedure. First, it takes the labels from neighbor nodes, concatenates them according to certain arbitrary order (the same ordering must be applied for all nodes), and finally appends the label of the node at the beginning of the obtained list. Each different sequence is substituted by a newly generated unique label, so nodes exhibiting exactly the same sequence are assigned the same label. This refinement process is repeated until labels stabilize, that is, when every pair of nodes with the same label in the previous iteration have the same label in the current iteration. Therefore, after m iterations, which depend on the network diameter, the canonical form is achieved, and an additional iteration is required for testing the stabilization condition. These final labels are the canonical form of the graph and, therefore, two nodes with the same final label are automorphically equivalent. An example of running the algorithm in a simple graph is shown in Figure 2.Figure 2
The Weisfeiler–Lehman canonicalization algorithm applied to a simple graph. (a) Original graph, (b) initial labeling, (c) first iteration, (d) first relabeling, (e) second iteration, and (f) second and final relabeling.
(a)(b)(c)(d)(e)(f)It can be noted that some pairs of the labels appearing in the same iteration of the Weisfeiler–Lehman algorithm are more similar than others. The automorphic distance between two nodes can be defined as the distance between their canonical labels. We propose a scheme to compute distances between the labels that are obtained by the Weisfeiler–Lehman algorithm. Since distances are only defined for labels appearing in the same iteration, a special label associated with nodes of degree 0, which we call the empty labelℓ∅, is considered for convenience. Isolated nodes are directly assigned this label and left out of the iterative process.Since labels created in the initial assignment are based on the node degree, we define the distance of labels of nodesx and y as the number of links that must be added to or removed from node x to transform it into node y. This can be easily computed as their absolute degree difference as follows:(2)dℓ0x,ℓ0y=degx−degy,where ℓ0n is the initially assigned label to node n. This definition of distance for initial labels is also valid for isolated nodes, with degree 0, which have been assigned the empty label.Given these distances for initial labels, the distance between labels for the subsequent iterations can be computed as the distance of the optimally matched pairs of labels of their neighbors from the previous iteration. The distance of labels from thei-th iteration can be computed as(3)dℓix,ℓiy=minMi−1x,y∑u,v∈Mi−1x,ydℓi−1u,ℓi−1v,where Mi−1x,y is the optimal assignment of neighbors of x to neighbors of y that minimizes the expression and, therefore, it is just the sum of distances between neighbors of x and y. If the neighborhood of one node is larger than the neighborhood of the other, leading to unmatched nodes, these nodes are directly matched with virtual nodes, which are labeled ℓ∅. The distances of unmatched nodes to the empty label can be seen as the cost, in terms of distance, of inserting and transforming a virtual isolated node to obtain a node with the label of the unmatched node. The optimal assignment, which would consider On! alternatives using a naive brute force approach, can be computed in polynomial time using the Hungarian algorithm [35].Initially, equation (2) and, in subsequent iterations, equation (3) are used to compute a distance table. At any given time, only distances from two iterations need to be maintained: the distances currently being computed and the distances from the most recent previous iteration.The described iterative process is carried out for each iteration of the 1-dimensional Weisfeiler–Lehman algorithm until label stabilization. The automorphic distance between a pair of nodes is defined as the distance between their canonical labels. It should be noted that labels can be represented using any set of symbols. However, for simplicity, we represent labels as positive integers.The complete algorithm is shown in Algorithm1. The function neighborsx returns the set of labels of the neighbor nodes of x. The function sorts sorts a set of elements. The ordering among elements is not relevant for the algorithm, but the same ordering must always be applied. The function concatenatex1,…,xn returns the concatenation of elements x1,…,xn. Finally, the function uniques generates and returns a unique symbol, such as an integer, for each observed unique string s, where uniques=uniques′ if and only if s=s′.Algorithm 1:Automorphic distance algorithm.
procedure Automorphic DistanceInput: Set of nodes N of an undirected graph.Output: Pairwise automorphic distances dx,y for each pair of nodesx,y∈N×N.for eachxinNdoℓ0x⟵degxend forfor eachx,yinN×Ndodℓ0x,ℓ0y⟵degx−degyend fori⟵1stabilized⟵falsewhile notstabilizeddostabilized⟵trueR⟵for eachxinNdohix⟵concatenatesortneighborsxcix⟵concatenateℓi−1x,hixℓix⟵uniquecixifR⋅containsℓixand notRℓix=ℓi−1xthenstabilized⟵falseelseRℓix=ℓi−1xend ifend forif notstabilizedthenfor eachx,yinN×Ndo▷ Using the Hungarian algorithm.dℓix,ℓiy⟵minMi−1x,y∑u,v∈Mi−1x,ydℓi−1u,ℓi−1vend fori⟵i+1end ifend whilefor eachx,yinN×Ndodx,y⟵dℓix,ℓiyend forend procedure


### 3.1. Example

In this section, we show an illustrative example applying the proposed automorphic distance metric to the network shown in Figure2(a).The proposed algorithm for computing the automorphic distance initially assigns a label to each node according to its degree, as shown in Figure2(b). Therefore, two nodes will have the same label if and only if they have the same degree. The initial distance table, represented as an upper triangular matrix due to the symmetry of distances, which will be proved in Section 3.2.3, is shown in Table 1. This distance table is computed using equation (2) according to the initial label assignments. For example, the distance between the labels 1 and 4 is 3, since this value is the absolute degree difference of the corresponding nodes.Table 1
Initialization of the distance table.
ℓ/ℓℓ∅1234ℓ∅0123410123201230140After initialization, the algorithm enters into its main loop and performs its first iteration. For each node, the labels of its neighbors are ordered and concatenated with its own label, as shown in Figure2(c). For example, the only node with label 3 has the associated string 3|2,2,4, since its neighbors have labels 2, 4, and 2. These concatenated strings are replaced by a new label, chosen so that two nodes are assigned the same new label if and only if they had the same concatenated string. This process generates a new labeling as shown in Figure 2(d). Given these new labels, the algorithm computes their pairwise distances using equation (3), which are shown in Table 2.Table 2
Distance table after the first relabeling.
ℓ/ℓℓ∅56789ℓ∅078410850333360442706480290For example, in order to compute the distance between labels 5 and 9, the optimal assignment between their neighbors minimizing the summation of distances, according to the previous iteration, must be obtained. In the previous iteration, 3 and 4 were the labels of the neighbors of nodes with label 5. Likewise, 1, 1, 2, and 4 were the labels of the neighbors of nodes with label 9. The Hungarian algorithm matches these neighbor labels to minimize their sum of distances:3,2 and 4,4 according to Table 1. Since the two neighbor labels 1 of label 9 were left unmatched, they are both matched with the empty label as 1,ℓ∅. Given this optimal assignment, we can compute the distance between labels 5 and 9 as(4)d15,9=d03,2+d04,4+d01,ℓ∅+d01,ℓ∅=1+0+1+1=3.We can use the same algorithm to compute the distance between any other pair of labels. For example, to compute the distance between labels 6 and 7, we first identify their neighbor labels in the previous iteration: 2, 2, and 4 for label 6 and 4 for label 7. Using the Hungarian algorithm, both labels 4 are matched with each other and both labels 2 are matched with the empty label, since there are no remaining labels to match them with. Therefore, the distance between labels 6 and 7 is computed as follows:(5)d16,7=d02,ℓ∅+d02,ℓ∅+d04,4=2+2+0=4.Following this iterative process, the algorithm performs a second iteration. Concatenated strings are computed as shown in Figure2(e) and labels are updated as shown in Figure 2(f). It can be easily seen that labels have stabilized, obtaining the canonical labeling of this graph. The stabilization condition can be tested by performing an additional iteration and observing that nodes with label 13 are assigned the same label, while the other nodes are assigned an unique new label. This new labeling would be equivalent to the labeling obtained in the current iteration, the condition required to achieve stabilization. The pairwise distances computed in this iteration are shown in Table 3.Table 3
Distance table after the second and final relabeling.
ℓ/ℓℓ∅10111213141516ℓ∅01824168102725100102128131111012161413712081011131302191714021151506160For instance, let us compute the distance between labels 11 and 16. We start by finding the optimal assignment that minimizes the pairwise distances of their neighbor labels in the previous iteration, which are5,5, and 8 for label 11 and 5,7,7, and 8 for label 16. The Hungarian algorithm obtains the optimal matching 5,5,5,7, and 8,8, with an additional ℓ∅,7, due to the difference of the node degrees associated with labels 11 and 16. Once this optimal matching has been obtained, we can easily compute the distance between labels 11 and 16 using equation (3) as follows:(6)d211,16=d15,5+d15,7+d18,8+d1ℓ∅,7=0+3+0+4=7.The automorphic distance between a pair of nodes is defined as the distance between their canonical labels, which are the final labels assigned in the iteration where stabilization is achieved. Therefore, in our example, the distance between nodes is given by Table3. For example, we can see how nodes with canonical labels 13 and 14 are close to being automorphically equivalent, since their automorphic distance is only 2. In contrast, nodes with canonical labels 14 and 15 have a large automorphic distance, equal to 21, which indicates that they are far from being automorphically equivalent.


### 3.2. Metric Admissibility

In this section, we prove that the distance function that we have defined is a valid metric or distance function. In order to assert this statement, we must prove the following four conditions: nonnegativity, identity of indiscernibles, symmetry, and triangle inequality.To prove these conditions, we note that equation (3) can be recursively decomposed as(7)dℓix,ℓiy=minMi−1x,y∑u,v∈Mi−1x,ydℓi−1u,ℓi−1v=minMi−1x,y∑u,v∈Mi−1x,yminMi−2u,v∑u′,v′∈Mi−2u,vdℓi−2u′,ℓi−2v′=⋯=∑x′,y′∈M′x,ydℓ0x′,ℓ0y′=∑x′,y′∈M′x,ydegx′−degy′,where M′x,y is the set of pairs of nodes that appear in the recursive summation at the deepest level of recursion as a result of choosing the optimal assignment in each iteration.


#### 3.2.1. Proof of Nonnegativity

Nonnegativity requires that the distance function satisfiesdℓix,ℓiy≥0 for any possible pair of nodes x and y. Given the decomposition of our metric as shown in equation (7), it is straightforward to see that the summation of absolute values is guaranteed to be always equal to or greater than 0.


#### 3.2.2. Proof of the Identity of Indiscernibles

The identity of indiscernibles implies that the distance function satisfiesdℓix,ℓiy=0 if and only if ℓix≡ℓiy. The Weisfeiler–Lehman algorithm guarantees that automorphically equivalent pairs of nodes are assigned the same canonical label, and nonautomorphically equivalent pairs of nodes are assigned different canonical labels.Equation (7) is only equal to zero when degx′=degy′ for every pair of nodes in M′x,y. Two nodes can only have the same canonical label if they are automorphically equivalent, as guaranteed by the Weisfeiler–Lehman algorithm. If two nodes are assigned the same canonical label, their neighbors must have been assigned equivalent labels in all the iterations. Since the distance of a label to itself is 0, we can see that the summation yields 0, leading to a zero distance for nodes when ℓix≡ℓiy.On the other side, when two nodes have different canonical labels, their neighbors must have been assigned different labels during the execution of the algorithm. This implies that, in the recursive decomposition shown in equation (7), at least one pair of nodes will not match nodes with the same initial labels, leading to a distance greater than 0 for nodes ℓix≢ℓiy.


#### 3.2.3. Proof of Symmetry

The condition of symmetry requires that the proposed distance function must satisfy the propertydℓix,ℓiy=dℓiy,ℓix. We can prove that equation (7) is symmetric as(8)dℓix,ℓiy=∑x′,y′∈M′x,ydegx′−degy′=∑y′,x′∈M′y,xdegy′−degx′=dℓiy,ℓix,since M′x,y is equal to M′y,x when we swap the nodes. The order of the nodes in each pair does not affect the result of our distance function.


#### 3.2.4. Proof of the Triangle Inequality

The triangle inequality requires that the inequalitydℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy is satisfied by the proposed automorphic distance function.By the definition of the proposed distance, we know that(9)dℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy⇒∑a,b∈M′x,ydega−degb≤∑a,c∈M′x,zdega−degc+∑c,d∈M′z,ydegc−degd.We know that the absolute value satisfies the triangle inequality and thus the lower value that the right side can take is(10)∑a,b∈M′x,ydega−degb≤∑a,d∈M″x,y,zdega−degd,where M″x,y,z is the set of pairs resulting from chaining or combining M′x,z and M′z,y so that a,d∈M″x,y,z if and only if, a,c∈M′x,z and c,d∈M′z,y.For this inequality to hold, it requires the nonexistence of a pairing of nodes better than the matching done in the left-hand side. Since the Hungarian algorithm ensures that matchings are optimal, minimizing their sum of distances, the matching at the right-hand side cannot be better than optimal and, therefore, the value of the right-hand side can only be equal to or greater than the value on the left-hand side, satisfying the triangle inequality condition.


### 3.3. Metric Computational Complexity

In this section, we analyze the time and spatial computational complexity of our proposed metric.The initialization of labels based on the degree of nodes hasOn time and spatial complexity, where n is the number of nodes in the network. The computation of the table for the initial distances has On2 time and spatial complexity, since the distance is computed for every pair of nodes.Each iteration of the algorithm requires computing the sorted list of labels of the neighbors for each node. This task can be accomplished for each node with computational and spatial complexityOk, where k is the degree of the node, when using radix, bucket, or counting sort. Thus, computing these strings for all nodes has Onk time and spatial complexity. Renaming these labels can be done in On time using hash-based data structures. To compute the pairwise distances between labels in the current iteration, the Hungarian algorithm, with computational complexity Ok3, must be computed for each pair of nodes, leading to On2k3 time complexity and On2 spatial complexity. Finally, checking if the labels have stabilized can be done in On using a hash-based index.The number of iterations,m, required for 1-dimensional Weisfeiler–Lehman algorithm to converge is closely related to the diameter of the network [32]. Even though the number of iterations is theoretically bounded by n, it has been widely observed that real-world networks tend to exhibit the small-world phenomenon, presenting a small diameter [36, 37] and leading to a small number of iterations required for convergence.Therefore, by combining these partial results, the total time complexity isOmn2k3, where n is the number of nodes in the graph, k is the degree of nodes, and m is the number of iterations required for convergence. The spatial complexity of the algorithm is On2, since only the distances and labels from the previous and the current iteration must be maintained at any given time.Most of these steps can be easily parallelized, since most of them are independent of each node and are only based on the results from the previous iteration. For example, the initial labels for each node can be assigned independently. Once we have assigned these labels, the computation of their pairwise distances can be split among all the available processors, since they are independent. The iterative assignment of labels in each loop iteration can also be parallelized using a concurrent data structure to ensure that the new labels are properly generated. Furthermore, the pairwise distances between these new labels can be easily computed in a parallel way, since they are completely independent as they only rely on the distance table computed in the previous iteration.


### 3.4. A More Efficient Approximation

The quadratic time complexity with respect to the number of nodes in the network limits the applicability of our proposed approach in large networks. In this section, we introduce a more scalable approximation of our approach.The proposed alternative approach is based on the idea of efficiently clustering similar labels just before computing distances between labels. This clustering only applies to the computation of distances, not to the steps related to the Weisfeiler–Lehman algorithm. Instead of requiring a distance matrix including all pairs of nodes, this approximated approach only requires computing the distance matrix between the obtained clusters. The distances between pairs of labels are approximated as the distance between the clusters to which they belong to. Therefore, using this approximation, the step where distances between pairs of labels are computed becomes quadratic with respect to the number of clusters, which are set by the experimenter and can be much lower than the number of nodes in the network.The proposed approximation algorithm is shown in Algorithms2–4. The base structure of the algorithm remains unchanged, but a new label clustering step is introduced just before computing the distances between pairs of labels. This clustering procedure is based on choosing a representative label for each cluster. A set for storing representative labels, initially containing only the empty label, is created. While the size of the set of representative labels is less than the number of clusters c specified as a parameter, a new representative label is added to this set as follows. A number of labels s is sampled from a set of remaining labels, which initially contains all the labels obtained except the empty label. The minimal distance to every representative label, i.e., the smallest distance to any label in the set of representative labels, is computed for each sampled label. The sampled label with the largest minimal distance is chosen as a representative label. Next, the chosen representative label is added to the set of representative labels and removed from the set of remaining labels. This greedy procedure approximates a set of representative labels with large distances among them.Algorithm 2: Approximated automorphic distance algorithm.
procedure APPROXIMATED AUTOMORPHIC DISTANCEInputs:-Set of nodesN of an undirected graph.-Number of clustersc.-Number of sampless.Outputs:-Approximated pairwise automorphic distancesdx,y for each pair of clusters x,y∈Ci×Ci.-Mappinggix from each label to its cluster representative.for each x in N doℓ0x←degxend forC0,g0←GREEDY_LABEL_CLUSTERINGN,c,s,0for eachx, yinC0×C0dodx,y←COMPUTE_DISTANCEx,y,0,g0end fori←1stabilized←falsewhile notstabilizeddostabilized←trueR←for each x in N dohix←concatenatesortneighborsxcix←concatenateℓi−1x,hixℓix←uniquecixIfR⋅containsℓixand notRℓix=ℓi−1xthenstabilized←falseelseRℓix←ℓi−1xend ifend forif notstabilizedthenCi,gi←GREEDY_LABEL_CLUSTERINGN,c,s,i,gi−1for eachx, yinCi×Cidodx,y←COMPUTE_DISTANCEx,y,i,gi−1end fori←i+1end ifend whileend procedureAlgorithm 3:Distance computation.
procedure COMPUTE_DISTANCEInputs:-Labelsx and y.-Iterationi.-Mapping from each label to its cluster representativeg (optional).▷ The mapping is only used for i>0.Output: Computed distance d.Ifi=0thend←x−yelse▷ Using the Hungarian algorithm.d←minMi−1x,y∑u,v∈Mi−1x,ydgℓi−1u,gℓi−1vend ifend procedureAlgorithm 4:Greedy label clustering.
procedure GREEDY_LABEL_CLUSTERINGInputs:-Set of nodesN of an undirected graph.-Number of clustersc.-Number of sampless.-Iterationi.-Mapping from each label to its cluster representativeg (optional).▷ The mapping is only used for i>0.Outputs:-Set of cluster representativesC.-Mappinggnx from each label to its cluster representative.C⟵ℓ∅L⟵ℓix:∀x∈NwhileC<cdoS⟵sampleL,sr⟵argmaxu∈Sargminv∈CCOMPUTE_DISTANCEu,v,i,gC.addrL.removerend whileL′⟵ℓix:∀x∈Nfor eachlinL′dognl⟵argminr∈CCOMPUTE_DISTANCEl,r,i,gend forend procedureEach representative label represents a cluster. A cluster is assigned to each nonrepresentative label by choosing the closest cluster according to the distance to its representative label.The proposed approximation has a significant impact on our algorithm computational complexity. The spatial complexity becomesOc2+nk, where c is the number of clusters and can be set to c≪n, since only distances between pairs of clusters obtained in the same iteration must be stored.The time complexity of the proposed approximation can be obtained as follows. The steps, which are also present in the original algorithm, without the clustering step, now have a computational complexityOnk+mc2k3 as a result of computing only distances between pairs of clusters. The time complexity of the greedy clustering step is Osc2k3 for the step where representative labels are chosen, where s is the number of the sampled labels, and for the step where clusters are assigned to each nonrepresentative label is Onck3. The greedy clustering procedure must be executed m times until the convergence of the Weisfeiler–Lehman algorithm. Therefore, the computational complexity introduced by the clustering procedure is Omsc2k3+mnck3.Given these complexities, the time complexity of the complete algorithm isOmsc2k3+mnck3. Since c and s can be manually set to be much smaller than the number of nodes in the network, this approach is more scalable and can be applied to large networks.


## 3.1. Example

In this section, we show an illustrative example applying the proposed automorphic distance metric to the network shown in Figure2(a).The proposed algorithm for computing the automorphic distance initially assigns a label to each node according to its degree, as shown in Figure2(b). Therefore, two nodes will have the same label if and only if they have the same degree. The initial distance table, represented as an upper triangular matrix due to the symmetry of distances, which will be proved in Section 3.2.3, is shown in Table 1. This distance table is computed using equation (2) according to the initial label assignments. For example, the distance between the labels 1 and 4 is 3, since this value is the absolute degree difference of the corresponding nodes.Table 1
Initialization of the distance table.
ℓ/ℓℓ∅1234ℓ∅0123410123201230140After initialization, the algorithm enters into its main loop and performs its first iteration. For each node, the labels of its neighbors are ordered and concatenated with its own label, as shown in Figure2(c). For example, the only node with label 3 has the associated string 3|2,2,4, since its neighbors have labels 2, 4, and 2. These concatenated strings are replaced by a new label, chosen so that two nodes are assigned the same new label if and only if they had the same concatenated string. This process generates a new labeling as shown in Figure 2(d). Given these new labels, the algorithm computes their pairwise distances using equation (3), which are shown in Table 2.Table 2
Distance table after the first relabeling.
ℓ/ℓℓ∅56789ℓ∅078410850333360442706480290For example, in order to compute the distance between labels 5 and 9, the optimal assignment between their neighbors minimizing the summation of distances, according to the previous iteration, must be obtained. In the previous iteration, 3 and 4 were the labels of the neighbors of nodes with label 5. Likewise, 1, 1, 2, and 4 were the labels of the neighbors of nodes with label 9. The Hungarian algorithm matches these neighbor labels to minimize their sum of distances:3,2 and 4,4 according to Table 1. Since the two neighbor labels 1 of label 9 were left unmatched, they are both matched with the empty label as 1,ℓ∅. Given this optimal assignment, we can compute the distance between labels 5 and 9 as(4)d15,9=d03,2+d04,4+d01,ℓ∅+d01,ℓ∅=1+0+1+1=3.We can use the same algorithm to compute the distance between any other pair of labels. For example, to compute the distance between labels 6 and 7, we first identify their neighbor labels in the previous iteration: 2, 2, and 4 for label 6 and 4 for label 7. Using the Hungarian algorithm, both labels 4 are matched with each other and both labels 2 are matched with the empty label, since there are no remaining labels to match them with. Therefore, the distance between labels 6 and 7 is computed as follows:(5)d16,7=d02,ℓ∅+d02,ℓ∅+d04,4=2+2+0=4.Following this iterative process, the algorithm performs a second iteration. Concatenated strings are computed as shown in Figure2(e) and labels are updated as shown in Figure 2(f). It can be easily seen that labels have stabilized, obtaining the canonical labeling of this graph. The stabilization condition can be tested by performing an additional iteration and observing that nodes with label 13 are assigned the same label, while the other nodes are assigned an unique new label. This new labeling would be equivalent to the labeling obtained in the current iteration, the condition required to achieve stabilization. The pairwise distances computed in this iteration are shown in Table 3.Table 3
Distance table after the second and final relabeling.
ℓ/ℓℓ∅10111213141516ℓ∅01824168102725100102128131111012161413712081011131302191714021151506160For instance, let us compute the distance between labels 11 and 16. We start by finding the optimal assignment that minimizes the pairwise distances of their neighbor labels in the previous iteration, which are5,5, and 8 for label 11 and 5,7,7, and 8 for label 16. The Hungarian algorithm obtains the optimal matching 5,5,5,7, and 8,8, with an additional ℓ∅,7, due to the difference of the node degrees associated with labels 11 and 16. Once this optimal matching has been obtained, we can easily compute the distance between labels 11 and 16 using equation (3) as follows:(6)d211,16=d15,5+d15,7+d18,8+d1ℓ∅,7=0+3+0+4=7.The automorphic distance between a pair of nodes is defined as the distance between their canonical labels, which are the final labels assigned in the iteration where stabilization is achieved. Therefore, in our example, the distance between nodes is given by Table3. For example, we can see how nodes with canonical labels 13 and 14 are close to being automorphically equivalent, since their automorphic distance is only 2. In contrast, nodes with canonical labels 14 and 15 have a large automorphic distance, equal to 21, which indicates that they are far from being automorphically equivalent.


## 3.2. Metric Admissibility

In this section, we prove that the distance function that we have defined is a valid metric or distance function. In order to assert this statement, we must prove the following four conditions: nonnegativity, identity of indiscernibles, symmetry, and triangle inequality.To prove these conditions, we note that equation (3) can be recursively decomposed as(7)dℓix,ℓiy=minMi−1x,y∑u,v∈Mi−1x,ydℓi−1u,ℓi−1v=minMi−1x,y∑u,v∈Mi−1x,yminMi−2u,v∑u′,v′∈Mi−2u,vdℓi−2u′,ℓi−2v′=⋯=∑x′,y′∈M′x,ydℓ0x′,ℓ0y′=∑x′,y′∈M′x,ydegx′−degy′,where M′x,y is the set of pairs of nodes that appear in the recursive summation at the deepest level of recursion as a result of choosing the optimal assignment in each iteration.


### 3.2.1. Proof of Nonnegativity

Nonnegativity requires that the distance function satisfiesdℓix,ℓiy≥0 for any possible pair of nodes x and y. Given the decomposition of our metric as shown in equation (7), it is straightforward to see that the summation of absolute values is guaranteed to be always equal to or greater than 0.


### 3.2.2. Proof of the Identity of Indiscernibles

The identity of indiscernibles implies that the distance function satisfiesdℓix,ℓiy=0 if and only if ℓix≡ℓiy. The Weisfeiler–Lehman algorithm guarantees that automorphically equivalent pairs of nodes are assigned the same canonical label, and nonautomorphically equivalent pairs of nodes are assigned different canonical labels.Equation (7) is only equal to zero when degx′=degy′ for every pair of nodes in M′x,y. Two nodes can only have the same canonical label if they are automorphically equivalent, as guaranteed by the Weisfeiler–Lehman algorithm. If two nodes are assigned the same canonical label, their neighbors must have been assigned equivalent labels in all the iterations. Since the distance of a label to itself is 0, we can see that the summation yields 0, leading to a zero distance for nodes when ℓix≡ℓiy.On the other side, when two nodes have different canonical labels, their neighbors must have been assigned different labels during the execution of the algorithm. This implies that, in the recursive decomposition shown in equation (7), at least one pair of nodes will not match nodes with the same initial labels, leading to a distance greater than 0 for nodes ℓix≢ℓiy.


### 3.2.3. Proof of Symmetry

The condition of symmetry requires that the proposed distance function must satisfy the propertydℓix,ℓiy=dℓiy,ℓix. We can prove that equation (7) is symmetric as(8)dℓix,ℓiy=∑x′,y′∈M′x,ydegx′−degy′=∑y′,x′∈M′y,xdegy′−degx′=dℓiy,ℓix,since M′x,y is equal to M′y,x when we swap the nodes. The order of the nodes in each pair does not affect the result of our distance function.


### 3.2.4. Proof of the Triangle Inequality

The triangle inequality requires that the inequalitydℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy is satisfied by the proposed automorphic distance function.By the definition of the proposed distance, we know that(9)dℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy⇒∑a,b∈M′x,ydega−degb≤∑a,c∈M′x,zdega−degc+∑c,d∈M′z,ydegc−degd.We know that the absolute value satisfies the triangle inequality and thus the lower value that the right side can take is(10)∑a,b∈M′x,ydega−degb≤∑a,d∈M″x,y,zdega−degd,where M″x,y,z is the set of pairs resulting from chaining or combining M′x,z and M′z,y so that a,d∈M″x,y,z if and only if, a,c∈M′x,z and c,d∈M′z,y.For this inequality to hold, it requires the nonexistence of a pairing of nodes better than the matching done in the left-hand side. Since the Hungarian algorithm ensures that matchings are optimal, minimizing their sum of distances, the matching at the right-hand side cannot be better than optimal and, therefore, the value of the right-hand side can only be equal to or greater than the value on the left-hand side, satisfying the triangle inequality condition.


## 3.2.1. Proof of Nonnegativity

Nonnegativity requires that the distance function satisfiesdℓix,ℓiy≥0 for any possible pair of nodes x and y. Given the decomposition of our metric as shown in equation (7), it is straightforward to see that the summation of absolute values is guaranteed to be always equal to or greater than 0.


## 3.2.2. Proof of the Identity of Indiscernibles

The identity of indiscernibles implies that the distance function satisfiesdℓix,ℓiy=0 if and only if ℓix≡ℓiy. The Weisfeiler–Lehman algorithm guarantees that automorphically equivalent pairs of nodes are assigned the same canonical label, and nonautomorphically equivalent pairs of nodes are assigned different canonical labels.Equation (7) is only equal to zero when degx′=degy′ for every pair of nodes in M′x,y. Two nodes can only have the same canonical label if they are automorphically equivalent, as guaranteed by the Weisfeiler–Lehman algorithm. If two nodes are assigned the same canonical label, their neighbors must have been assigned equivalent labels in all the iterations. Since the distance of a label to itself is 0, we can see that the summation yields 0, leading to a zero distance for nodes when ℓix≡ℓiy.On the other side, when two nodes have different canonical labels, their neighbors must have been assigned different labels during the execution of the algorithm. This implies that, in the recursive decomposition shown in equation (7), at least one pair of nodes will not match nodes with the same initial labels, leading to a distance greater than 0 for nodes ℓix≢ℓiy.


## 3.2.3. Proof of Symmetry

The condition of symmetry requires that the proposed distance function must satisfy the propertydℓix,ℓiy=dℓiy,ℓix. We can prove that equation (7) is symmetric as(8)dℓix,ℓiy=∑x′,y′∈M′x,ydegx′−degy′=∑y′,x′∈M′y,xdegy′−degx′=dℓiy,ℓix,since M′x,y is equal to M′y,x when we swap the nodes. The order of the nodes in each pair does not affect the result of our distance function.


## 3.2.4. Proof of the Triangle Inequality

The triangle inequality requires that the inequalitydℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy is satisfied by the proposed automorphic distance function.By the definition of the proposed distance, we know that(9)dℓix,ℓiy≤dℓix,ℓiz+dℓiz,ℓiy⇒∑a,b∈M′x,ydega−degb≤∑a,c∈M′x,zdega−degc+∑c,d∈M′z,ydegc−degd.We know that the absolute value satisfies the triangle inequality and thus the lower value that the right side can take is(10)∑a,b∈M′x,ydega−degb≤∑a,d∈M″x,y,zdega−degd,where M″x,y,z is the set of pairs resulting from chaining or combining M′x,z and M′z,y so that a,d∈M″x,y,z if and only if, a,c∈M′x,z and c,d∈M′z,y.For this inequality to hold, it requires the nonexistence of a pairing of nodes better than the matching done in the left-hand side. Since the Hungarian algorithm ensures that matchings are optimal, minimizing their sum of distances, the matching at the right-hand side cannot be better than optimal and, therefore, the value of the right-hand side can only be equal to or greater than the value on the left-hand side, satisfying the triangle inequality condition.


## 3.3. Metric Computational Complexity

In this section, we analyze the time and spatial computational complexity of our proposed metric.The initialization of labels based on the degree of nodes hasOn time and spatial complexity, where n is the number of nodes in the network. The computation of the table for the initial distances has On2 time and spatial complexity, since the distance is computed for every pair of nodes.Each iteration of the algorithm requires computing the sorted list of labels of the neighbors for each node. This task can be accomplished for each node with computational and spatial complexityOk, where k is the degree of the node, when using radix, bucket, or counting sort. Thus, computing these strings for all nodes has Onk time and spatial complexity. Renaming these labels can be done in On time using hash-based data structures. To compute the pairwise distances between labels in the current iteration, the Hungarian algorithm, with computational complexity Ok3, must be computed for each pair of nodes, leading to On2k3 time complexity and On2 spatial complexity. Finally, checking if the labels have stabilized can be done in On using a hash-based index.The number of iterations,m, required for 1-dimensional Weisfeiler–Lehman algorithm to converge is closely related to the diameter of the network [32]. Even though the number of iterations is theoretically bounded by n, it has been widely observed that real-world networks tend to exhibit the small-world phenomenon, presenting a small diameter [36, 37] and leading to a small number of iterations required for convergence.Therefore, by combining these partial results, the total time complexity isOmn2k3, where n is the number of nodes in the graph, k is the degree of nodes, and m is the number of iterations required for convergence. The spatial complexity of the algorithm is On2, since only the distances and labels from the previous and the current iteration must be maintained at any given time.Most of these steps can be easily parallelized, since most of them are independent of each node and are only based on the results from the previous iteration. For example, the initial labels for each node can be assigned independently. Once we have assigned these labels, the computation of their pairwise distances can be split among all the available processors, since they are independent. The iterative assignment of labels in each loop iteration can also be parallelized using a concurrent data structure to ensure that the new labels are properly generated. Furthermore, the pairwise distances between these new labels can be easily computed in a parallel way, since they are completely independent as they only rely on the distance table computed in the previous iteration.


## 3.4. A More Efficient Approximation

The quadratic time complexity with respect to the number of nodes in the network limits the applicability of our proposed approach in large networks. In this section, we introduce a more scalable approximation of our approach.The proposed alternative approach is based on the idea of efficiently clustering similar labels just before computing distances between labels. This clustering only applies to the computation of distances, not to the steps related to the Weisfeiler–Lehman algorithm. Instead of requiring a distance matrix including all pairs of nodes, this approximated approach only requires computing the distance matrix between the obtained clusters. The distances between pairs of labels are approximated as the distance between the clusters to which they belong to. Therefore, using this approximation, the step where distances between pairs of labels are computed becomes quadratic with respect to the number of clusters, which are set by the experimenter and can be much lower than the number of nodes in the network.The proposed approximation algorithm is shown in Algorithms2–4. The base structure of the algorithm remains unchanged, but a new label clustering step is introduced just before computing the distances between pairs of labels. This clustering procedure is based on choosing a representative label for each cluster. A set for storing representative labels, initially containing only the empty label, is created. While the size of the set of representative labels is less than the number of clusters c specified as a parameter, a new representative label is added to this set as follows. A number of labels s is sampled from a set of remaining labels, which initially contains all the labels obtained except the empty label. The minimal distance to every representative label, i.e., the smallest distance to any label in the set of representative labels, is computed for each sampled label. The sampled label with the largest minimal distance is chosen as a representative label. Next, the chosen representative label is added to the set of representative labels and removed from the set of remaining labels. This greedy procedure approximates a set of representative labels with large distances among them.Algorithm 2: Approximated automorphic distance algorithm.
procedure APPROXIMATED AUTOMORPHIC DISTANCEInputs:-Set of nodesN of an undirected graph.-Number of clustersc.-Number of sampless.Outputs:-Approximated pairwise automorphic distancesdx,y for each pair of clusters x,y∈Ci×Ci.-Mappinggix from each label to its cluster representative.for each x in N doℓ0x←degxend forC0,g0←GREEDY_LABEL_CLUSTERINGN,c,s,0for eachx, yinC0×C0dodx,y←COMPUTE_DISTANCEx,y,0,g0end fori←1stabilized←falsewhile notstabilizeddostabilized←trueR←for each x in N dohix←concatenatesortneighborsxcix←concatenateℓi−1x,hixℓix←uniquecixIfR⋅containsℓixand notRℓix=ℓi−1xthenstabilized←falseelseRℓix←ℓi−1xend ifend forif notstabilizedthenCi,gi←GREEDY_LABEL_CLUSTERINGN,c,s,i,gi−1for eachx, yinCi×Cidodx,y←COMPUTE_DISTANCEx,y,i,gi−1end fori←i+1end ifend whileend procedureAlgorithm 3:Distance computation.
procedure COMPUTE_DISTANCEInputs:-Labelsx and y.-Iterationi.-Mapping from each label to its cluster representativeg (optional).▷ The mapping is only used for i>0.Output: Computed distance d.Ifi=0thend←x−yelse▷ Using the Hungarian algorithm.d←minMi−1x,y∑u,v∈Mi−1x,ydgℓi−1u,gℓi−1vend ifend procedureAlgorithm 4:Greedy label clustering.
procedure GREEDY_LABEL_CLUSTERINGInputs:-Set of nodesN of an undirected graph.-Number of clustersc.-Number of sampless.-Iterationi.-Mapping from each label to its cluster representativeg (optional).▷ The mapping is only used for i>0.Outputs:-Set of cluster representativesC.-Mappinggnx from each label to its cluster representative.C⟵ℓ∅L⟵ℓix:∀x∈NwhileC<cdoS⟵sampleL,sr⟵argmaxu∈Sargminv∈CCOMPUTE_DISTANCEu,v,i,gC.addrL.removerend whileL′⟵ℓix:∀x∈Nfor eachlinL′dognl⟵argminr∈CCOMPUTE_DISTANCEl,r,i,gend forend procedureEach representative label represents a cluster. A cluster is assigned to each nonrepresentative label by choosing the closest cluster according to the distance to its representative label.The proposed approximation has a significant impact on our algorithm computational complexity. The spatial complexity becomesOc2+nk, where c is the number of clusters and can be set to c≪n, since only distances between pairs of clusters obtained in the same iteration must be stored.The time complexity of the proposed approximation can be obtained as follows. The steps, which are also present in the original algorithm, without the clustering step, now have a computational complexityOnk+mc2k3 as a result of computing only distances between pairs of clusters. The time complexity of the greedy clustering step is Osc2k3 for the step where representative labels are chosen, where s is the number of the sampled labels, and for the step where clusters are assigned to each nonrepresentative label is Onck3. The greedy clustering procedure must be executed m times until the convergence of the Weisfeiler–Lehman algorithm. Therefore, the computational complexity introduced by the clustering procedure is Omsc2k3+mnck3.Given these complexities, the time complexity of the complete algorithm isOmsc2k3+mnck3. Since c and s can be manually set to be much smaller than the number of nodes in the network, this approach is more scalable and can be applied to large networks.


## 4. Experimental Evaluation

This section contains our experimental evaluation of the proposed automorphic distance metric. In addition to the theoretical results described in the previous sections of the manuscript, we aim to show how our proposal properly captures the concept of node role based on automorphic equivalence and its different practical applications.The experimental evaluation of the proposed distance metric is a complicated task due to the lack of a standard evaluation methodology for role-based metrics. In order to evaluate our distance metrics and compare the obtained results with other state-of-the-art approaches, we propose different experimental settings, which are described in the following sections.


### 4.1. Performance Evaluation of Distance Metrics

In this section, we evaluate and compare the proposed original automorphic distance metric with RoleSim considered as a distance metric. We follow an evaluation methodology based on the idea that nodes playing the same role in the network must show similar topological properties. Therefore, close nodes with regard to an automorphic distance metric should have similar topological properties, and their distance should be correlated with the similarity between these properties. For example, nodes with a similar role in the network should also exhibit a similar centrality, and similar nodes playing the role of bridges between different communities should exhibit similar topological properties measurable by different metrics proposed in the field of network analysis.We propose measuring the performance of these distance metrics by evaluating how well these metrics capture global network structural properties. This can be done by computing the Pearson correlation coefficient between the distances given by the evaluated methods for a given pair of nodes and the absolute difference of their scores associated with a given network structural property, as follows:(11)score=corrdℓix,ℓiy:∀x,y∈N×N,sx−sy:∀x,y∈N×N,where corrA,B is the Pearson correlation between two sequences A and B, N is the set of nodes in the network, dℓix,ℓiy is the distance between a pair of nodes x and y, and sn is the score given by the network structural property for a node n.In order to capture the most important role-related topological features, we included several network structural properties in our experimentation. First, we included PageRank [38], a well-known algorithm for measuring the importance of each node in a network. This iterative algorithm outputs a probability distribution that represents the likelihood of reaching each node by randomly moving through the network. Second, we considered closeness [39], which measures node centrality as the reciprocal of the sum of the shortest path lengths to all other nodes. Finally, we also included betweenness [40], which measures node centrality proportionally to the number of shortest paths passing through each node.Our experimentation was carried out using five networks from very diverse domains. Due to the high computational complexity of the evaluated methods, we restricted this experiment to small networks with a few hundred nodes at most. The included networks are listed as follows:(i)
A communication network of 36 nodes and 62 links between employees in a sawmill [41]. Two nodes, each one representing an employee, are linked if they contacted a number of times higher than a given threshold.(ii)
A social network of bottlenose dolphins, with 62 nodes and 159 links, based on observations between 1994 and 2001 [42]. A link represents frequent association between dolphins, which are represented as nodes.(iii)
A network containing 77 nodes and 254 links of character coappearances in the novel “Les Misérables” [43], written by Victor Hugo. Each node represents a character and each link represents the coappearance of two characters in the same chapter.(iv)
A network, with 112 nodes and 425 links, of noun and adjective adjacencies for the novel “David Copperfield” [44], written by Charles Dickens. Each node represents a word that is a noun or an adjective, whereas a link represents adjacency of two words in the text.(v)
A network, composed of 131 nodes and 1074 links, representing the Brazilian air-traffic in 2016 [24], which was extracted from the National Civil Aviation Agency (ANAC). Nodes represent airports and links represent the existence of commercial flights between pairs of airports.The results we obtained are shown in Table4. The distances computed by the automorphic distance are highly correlated with the considered role-related structural properties, outperforming RoleSim in most cases. Except for the dolphin network, our distance shows a high correlation with PageRank and closeness. Although positive, indicating that it is capable of capturing part of this information, RoleSim clearly performs worse in terms of capturing these structural properties. Both distances present a lower correlation with betweenness, especially in the dolphin and Les Misérables networks, where RoleSim is not correlated at all.Table 4
Pearson correlation coefficients illustrating the correlation of automorphic distance metrics and topological properties.
NetworkMethodPage RankClosenessBetweennessSawmillAutomorphic0.79870.76330.7856RoleSim0.32490.48580.1389DolphinsAutomorphic0.73100.41760.2185RoleSim0.44760.42290.0032Les misérablesAutomorphic0.69760.67580.5205RoleSim0.25450.31970.0720CopperfieldAutomorphic0.94900.76360.8811RoleSim0.44800.65830.2493Brazil airportsAutomorphic0.88580.92720.5344RoleSim0.42710.59420.1328The highest correlation for each network and each structural metric is marked in bold.These results suggest that our proposal outperforms RoleSim in capturing role-based topological information and that distances computed by our approach are more closely related to the roles of nodes. In the following section, we will evaluate our distance in the task of generating continuous representations for nodes based on their role.


### 4.2. Computing Role-Based Node Embeddings

A central problem in machine learning is finding representations that ease the visualization or extraction of useful information from data [45]. A common solution is the computation of embeddings that represent complex objects in a vector space preserving certain properties [46]. Node embedding, also known as graph embedding, is the task of mapping each node in a graph to a dimensional space trying to preserve the similarity or distance between pairs of nodes. Therefore, similar nodes will be located in similar regions of the space. Node embeddings have lately gained attention, since they have achieved good results in different machine learning tasks [46]. Several models have been proposed for node embedding. However, these techniques try to preserve the connectivity of the network by obtaining embeddings that preserve the neighborhood and the community of nodes [22, 47]. This information has proven to be useful due to the presence of homophily, also known as assortativity, in real-world networks [48], where entities tend to be connected to similar ones, a feature that allows us to explain certain features of the nodes. Even though the connectivity information captured by these techniques is relevant, these techniques fail to capture information related to the role or function of the nodes in the network, which is a highly valuable information that is complementary to the information obtained by locality-based embedding techniques.Recently, different techniques for computing role-based embeddings, capturing the roles of nodes by placing nodes that play a similar function in the network close in the resulting vector space, have been proposed. In this work, we consider two state-of-the-art techniques that have received a lot of attention: node2vec [23] and struc2vec [24]. Both methods learn continuous representations capturing node structural equivalence and identity, respectively. These approaches are based on applying the skip-gram model [49], which was initially proposed as a model for natural language, over node contexts extracted from the network using biased random walks.On the one hand, the node2vec method computes these contexts combining the breadth-first search (BFS), with the intention of reflecting structural equivalence, and depth-first search (DFS), with the intention of reflecting homophily. This behavior is achieved using two parameters:p and q. The return parameter p controls the likelihood of returning back to the previous node in the random walk. The in-out parameter q controls the tendency of moving to close or far nodes. If q>1, the random walks are biased towards close nodes. Otherwise, the random walks are biased towards visiting more distant nodes. We used the node2vec implementation available at https://github.com/aditya-grover/node2vec.On the other hand, the struc2vec method computes these contexts by inducing a hierarchy that captures different levels of information. This hierarchy is used to build a weighted multilayer network, with a layer for each level in the hierarchy, which is used to generate node contexts by performing biased random walks with the intention of reflecting structural identity. We used the implementation available athttps://github.com/leoribeiro/struc2vec.In order to compute node embeddings using role-based distances, we apply the classical multidimensional scaling (MDS) [50, 51] to the distance matrices.The following sections are devoted to the detailed study of two particular cases, where we evaluate the embeddings obtained using the proposed definition of automorphic distance compared to the previously introduced approaches. For each case, we show how 2-dimensional embeddings can capture relevant information related to the function of the nodes in the network. These sections are intended to provide some insights into the properties of the obtained embeddings, whereas the numerical evaluation is left for the next section.


#### 4.2.1. Zachary’s Karate Club Network

Zachary’s karate club network is a popular social network representing the 34 members of a university karate club as its nodes and their interactions outside the club, as its links [52]. During the study carried out by Zachary, a conflict arose between the two club administrators, leading to the split of the club into two groups according to the leader each member decided to follow. For this reason, this network has served as a prototypical case study for community detection algorithms and some network analysis techniques.Zachary observed that the formed groups were highly homogeneous and assortative. Therefore, nodes tended to be connected to nodes that took the same decision. In this context, different embedding techniques have been proposed in the past for generating embeddings distributing nodes in multidimensional spaces according to the leader they decided to follow [47]. This information is crucial when the task is related to community detection. However, these embeddings fail, by nature, to reveal the role of each node in the network. In this study, we evaluate and compare the results obtained by the previously introduced techniques in the task of computing embeddings that are able to capture the role of each node in Zachary’s karate club network.We assigned a class to each node according to objective role-related properties. The two leaders are colored in red. Nodes interacting with the two leaders are colored in green. Nodes not interacting with any of the two leaders are colored in yellow. Finally, the remaining nodes, which interact with only one of the leaders, are colored in blue. Figure3 shows the network drawn using the Fruchterman–Reingold force-directed layout algorithm [53] and the embeddings obtained by applying our automorphic distance, RoleSim, node2vec, and struc2vec.Figure 3
Zachary’s karate club network and its node embeddings with node role coloring. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)Due to the large number of possible parameter combinations in node2vec and struc2vec, the authors decided to use the same values that were used by their original authors in case studies included in their respective papers. For struc2vec, we used the same parameters they used in their Section4.2, where they also studied this network for a different task. Therefore, we set the number of walks per source to 5, the walk length to 15, and the skip-gram window size to 3. For node2vec, we used the same parameters that they used in their case study of the Les Misérables network with the intention of capturing structural equivalence, as shown in their Section 4.1. Therefore, we set p=1 and q=2. Since they did not provide the values of the other parameters, we used the same as those for struc2vec.In the resulting embeddings, shown in Figure3, it can be seen how all techniques seem to capture at least partial information about the function of the nodes. For example, all techniques place the two leaders, represented by the red nodes, in close positions. This observation also applies to green nodes, which represent persons who interact with both leaders. Furthermore, green nodes are highly clustered in all the embeddings.However, both node2vec and struc2vec show a poor separation of the different classes. RoleSim seems to separate the classes better, but still places green nodes inside the cloud of blue nodes. In the three embeddings, the two leaders are placed pretty close to normal club members, without capturing their unique function in the network.In contrast, it can be seen that the four roles are linearly separated in the embedding generated using our distance metric. In addition, it can be seen how the two leaders are clearly mapped as outliers and placed notably apart from the other nodes representing normal members of the club.


#### 4.2.2. World Trade Network

In network data mining, homophily is commonly exploited in node classification tasks, since nodes tend to exhibit the same class as their neighbors [54]. Even though this situation occurs in a large number of networks from very diverse domains, homophily based classification techniques fail when the classes of the nodes are defined by the role they play in the network, instead of the community they belong to.An illustrative example of this situation is a network containing data on trade of miscellaneous metal manufactures among 80 countries, according to data gathered in 1993 and 1994 from the Commodity Trade Statistics published by the United Nations [55, 56]. Each country is represented by a node in the network. Each commercial relationship is represented by an arc, which we consider an undirected edge in practice. In this case, arcs correspond to trading high technology products or heavy manufactures between countries.In addition, the authors of this dataset annotated countries in the network with their structural world economic position in 1994. World economic positions are a classification of countries in the context of the world-system theory that explains some complex dynamics observed in the real-world [57]. This classification splits countries into three possible categories: core countries (colored in green), semiperiphery countries (colored in blue), and periphery countries (colored in red). In short, core countries have a high economic, military, and political power, which allows them to control the world economic system. The periphery is composed of less developed countries, owning a disproportionately small share of global wealth. Finally, the semiperiphery consists of countries that do not clearly fall in the previous two categories and exhibit a more intermediate status.In this case, for struc2vec, we used the same parameters their authors used in the analysis carried out in Section4.1 of their manuscript. Therefore, we set the number of walks per source to 20, the walk length to 80, and the skip-gram window size to 5. For node2vec, we also used these parameters with p=1 and q=2.Figure4 shows the trade network drawn using the Fruchterman–Reingold force-directed layout algorithm and the embeddings obtained by applying different techniques. Again, all techniques seem to capture role-related information as shown by the elongated shape of all the embeddings, curved in the case of RoleSim, with core and periphery countries placed at both ends.Figure 4
World trade network and its corresponding node embeddings. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)It can be seen that the automorphic distance, RoleSim, and struc2vec achieve a good separation of core and periphery countries, with some overlapping with countries in the semiperiphery. However, struc2vec shows a highly elongated shape, also present in the case studies included in their manuscript. Finally, node2vec seems to perform worse than the other approaches. In spite of being able to separate the peripheral countries, it does not perform well in the separation of the central countries and those in the semiperiphery.


### 4.3. Performance Evaluation of Computed Node Embeddings

The case studies analyzed in the previous section allowed us to gain some insight about the embeddings generated by our distance metric in comparison to other state-of-the-art approaches. However, in order to perform a more objective and exhaustive evaluation, we extend this analysis by carrying out a quantitative performance evaluation in this section.As previously stated, the evaluation of techniques for role discovery is a complicated task due to the lack of available evaluation datasets with role-based ground-truth data. This difficulty extends to the evaluation of techniques for generating embeddings capturing the notion of the node role. The most common solution is indirectly evaluating these embeddings based on their application to other tasks with evaluable or measurable performance metrics. For example, these embeddings can be evaluated by means of a classification problem, where labels related to node roles are predicted using the generated embeddings. However, there is no guarantee that the labels are completely determined by the roles of nodes in the network. Therefore, these experiments only evaluate which techniques capture the driving factors of these labels better, and in which node roles may only partially contribute or not contribute at all. This criticism extends to other tasks previously used to evaluate role-based embeddings, such as link prediction.In order to overcome these limitations while offering an objective evaluation procedure, we propose a new approach to evaluate techniques for computing role-based embeddings for nodes. Our proposal consists of measuring how well the embeddings produced by these techniques can reconstruct global network structural properties based on the same arguments we used in Section4.1. Nodes with a similar role in the network also exhibit similar topological properties. Therefore, evaluating how well these embeddings can be used to reconstruct these topological properties is an indirect way of assessing the quality of these embeddings.In our experimentation, we considered the network structural properties previously described in Section4.1. For each method and each property, we trained a linear regression model using the ordinary least squares method. For a given node, these trained linear models take its embedding as input and output the predicted score for the node corresponding to the structural property. We carried out our experimentation using five-dimensional embeddings. We chose this number of dimensions as a reasonable number, enough to capture complex role-related patterns.In order to carry out an unbiased evaluation, these models were trained using a five-fold crossvalidation, with 80% of the nodes as training set and the remaining 20% as the test set. In addition to crossvalidation, since all the evaluated methods include an element of randomness, we ran five different executions of the evaluation procedure using different random seeds, both for the generation of the embeddings and the crossvalidation procedure. The root mean squared error (RMSE) was used as the evaluation metric. The reported error for a method on a given dataset is the average RMSE obtained in the multiple executions of the five-fold crossvalidation using different seeds.In this experiment, we included the approximated version of our proposal, node2vec, and struc2vec. RoleSim was left out due to its high computational complexity, which limits its applicability to large networks.Methods included in the comparison have different parameters that must be adjusted. Due to the high computing requirements for executing each technique multiple times, we limited our experimentation to a restricted set of parameters. For our approximation of the automorphic distance metric, we chose 30 clusters and samples as parameters, since it is a reasonable value considering the size of the studied networks, which are presented below.For node2vec and struc2vec, we limited our experimentation to different parameter settings included in their original papers. For node2vec, we used 0.50, 1, and 2 as values for thep parameter. The q parameter was also set to 0.50, 1, and 2. In order to avoid running a large number of parameter combinations, which is computationally intensive, we fixed the remaining parameters to the default values used in the original paper: number of walks per source to 10, length of walk per source to 80, and skip-gram window size to 10. For struc2vec, we report the best results using the following parameter combinations. We tested 10 and 20 walks per source with lengths 15 and 80. For the skip-gram model, we used window sizes of 5 and 10. The algorithm was executed with all the optimizations enabled: OPT1, OPT2, and OPT3.Five different networks were used in our experimentation:(i)
A network, composed of 399 nodes and 5995 links, representing European air-traffic in 2016 [24], built using data from the Statistical Office of the European Union (Eurostat). Nodes representing airports and links represent the existence of commercial flights between pairs of airports.(ii)
Another network, with 1190 nodes and 13599 links, representing air-traffic in 2016 from the United States of America [24]. The network was built using data from the Bureau of Transportation Statistics.(iii)
A communication network, with 1005 nodes and 16706 links, based on mailing data from a large European research institution [58]. Each node represents a person, and each link represents that two nodes shared at least one email.(iv)
Another communication network, composed of 1133 nodes and 5451 links, built using mailing data from the University Rovira i Virgili in Tarragona [59], located in Spain. Each node represents an user, and each link represents that at least one email was sent between the two users.(v)
A network, with 1010 nodes and 3649 links, representing the thesaurus written by Peter Mark Roget [43]. Each node represents a category and each link represents a relation between a pair of categories.The results obtained for this evaluation procedure are shown in Table5. The best-performing parameters for struc2vec and node2vec were omitted for the sake of clarity. Note that the absolute error is small in all cases due to the order of magnitude of the scores computed using the included network properties. These results show how the embeddings computed using the approximation of the proposed automorphic distance metric achieve a lower RMSE than the other approaches in 13 out of 15 cases. Only node2vec outperforms our approach in two cases for closeness, where it performs especially well compared to the other approaches.Table 5
Obtained RMSE for the considered methods, networks, and structural network properties.
MethodPageRankClosenessBetweennessEU airportsAutomorphic7.67×10−42.34×10−27.18×10−3struc2vec1.66×10−34.15×10−28.23×10−3node2vec2.39×10−35.58×10−29.38×10−3USA airportsAutomorphic6.41×10−43.59×10−27.81×10−3struc2vec9.66×10−44.69×10−27.99×10−3node2vec1.10×10−34.43×10−28.28×10−3EU-emailAutomorphic2.72×10−45.36×10−22.63×10−3struc2vec7.38×10−46.45×10−23.83×10−3node2vec9.16×10−44.95×10−24.15×10−3Univ-emailAutomorphic2.92×10−42.00×10−22.63×10−3struc2vec5.23×10−42.49×10−23.73×10−3node2vec6.58×10−42.83×10−24.18×10−3RogetAutomorphic2.68×10−43.17×10−22.52×10−3struc2vec3.70×10−43.62×10−23.27×10−3node2vec4.68×10−41.74×10−23.67×10−3The lowest RMSE for each dataset and structural network property is marked in bold.These results suggest that our proposal can capture node-related information better than other state-of-the-art approaches, as shown by the lower error achieved in the task of reconstructing topological properties.


## 4.1. Performance Evaluation of Distance Metrics

In this section, we evaluate and compare the proposed original automorphic distance metric with RoleSim considered as a distance metric. We follow an evaluation methodology based on the idea that nodes playing the same role in the network must show similar topological properties. Therefore, close nodes with regard to an automorphic distance metric should have similar topological properties, and their distance should be correlated with the similarity between these properties. For example, nodes with a similar role in the network should also exhibit a similar centrality, and similar nodes playing the role of bridges between different communities should exhibit similar topological properties measurable by different metrics proposed in the field of network analysis.We propose measuring the performance of these distance metrics by evaluating how well these metrics capture global network structural properties. This can be done by computing the Pearson correlation coefficient between the distances given by the evaluated methods for a given pair of nodes and the absolute difference of their scores associated with a given network structural property, as follows:(11)score=corrdℓix,ℓiy:∀x,y∈N×N,sx−sy:∀x,y∈N×N,where corrA,B is the Pearson correlation between two sequences A and B, N is the set of nodes in the network, dℓix,ℓiy is the distance between a pair of nodes x and y, and sn is the score given by the network structural property for a node n.In order to capture the most important role-related topological features, we included several network structural properties in our experimentation. First, we included PageRank [38], a well-known algorithm for measuring the importance of each node in a network. This iterative algorithm outputs a probability distribution that represents the likelihood of reaching each node by randomly moving through the network. Second, we considered closeness [39], which measures node centrality as the reciprocal of the sum of the shortest path lengths to all other nodes. Finally, we also included betweenness [40], which measures node centrality proportionally to the number of shortest paths passing through each node.Our experimentation was carried out using five networks from very diverse domains. Due to the high computational complexity of the evaluated methods, we restricted this experiment to small networks with a few hundred nodes at most. The included networks are listed as follows:(i)
A communication network of 36 nodes and 62 links between employees in a sawmill [41]. Two nodes, each one representing an employee, are linked if they contacted a number of times higher than a given threshold.(ii)
A social network of bottlenose dolphins, with 62 nodes and 159 links, based on observations between 1994 and 2001 [42]. A link represents frequent association between dolphins, which are represented as nodes.(iii)
A network containing 77 nodes and 254 links of character coappearances in the novel “Les Misérables” [43], written by Victor Hugo. Each node represents a character and each link represents the coappearance of two characters in the same chapter.(iv)
A network, with 112 nodes and 425 links, of noun and adjective adjacencies for the novel “David Copperfield” [44], written by Charles Dickens. Each node represents a word that is a noun or an adjective, whereas a link represents adjacency of two words in the text.(v)
A network, composed of 131 nodes and 1074 links, representing the Brazilian air-traffic in 2016 [24], which was extracted from the National Civil Aviation Agency (ANAC). Nodes represent airports and links represent the existence of commercial flights between pairs of airports.The results we obtained are shown in Table4. The distances computed by the automorphic distance are highly correlated with the considered role-related structural properties, outperforming RoleSim in most cases. Except for the dolphin network, our distance shows a high correlation with PageRank and closeness. Although positive, indicating that it is capable of capturing part of this information, RoleSim clearly performs worse in terms of capturing these structural properties. Both distances present a lower correlation with betweenness, especially in the dolphin and Les Misérables networks, where RoleSim is not correlated at all.Table 4
Pearson correlation coefficients illustrating the correlation of automorphic distance metrics and topological properties.
NetworkMethodPage RankClosenessBetweennessSawmillAutomorphic0.79870.76330.7856RoleSim0.32490.48580.1389DolphinsAutomorphic0.73100.41760.2185RoleSim0.44760.42290.0032Les misérablesAutomorphic0.69760.67580.5205RoleSim0.25450.31970.0720CopperfieldAutomorphic0.94900.76360.8811RoleSim0.44800.65830.2493Brazil airportsAutomorphic0.88580.92720.5344RoleSim0.42710.59420.1328The highest correlation for each network and each structural metric is marked in bold.These results suggest that our proposal outperforms RoleSim in capturing role-based topological information and that distances computed by our approach are more closely related to the roles of nodes. In the following section, we will evaluate our distance in the task of generating continuous representations for nodes based on their role.


## 4.2. Computing Role-Based Node Embeddings

A central problem in machine learning is finding representations that ease the visualization or extraction of useful information from data [45]. A common solution is the computation of embeddings that represent complex objects in a vector space preserving certain properties [46]. Node embedding, also known as graph embedding, is the task of mapping each node in a graph to a dimensional space trying to preserve the similarity or distance between pairs of nodes. Therefore, similar nodes will be located in similar regions of the space. Node embeddings have lately gained attention, since they have achieved good results in different machine learning tasks [46]. Several models have been proposed for node embedding. However, these techniques try to preserve the connectivity of the network by obtaining embeddings that preserve the neighborhood and the community of nodes [22, 47]. This information has proven to be useful due to the presence of homophily, also known as assortativity, in real-world networks [48], where entities tend to be connected to similar ones, a feature that allows us to explain certain features of the nodes. Even though the connectivity information captured by these techniques is relevant, these techniques fail to capture information related to the role or function of the nodes in the network, which is a highly valuable information that is complementary to the information obtained by locality-based embedding techniques.Recently, different techniques for computing role-based embeddings, capturing the roles of nodes by placing nodes that play a similar function in the network close in the resulting vector space, have been proposed. In this work, we consider two state-of-the-art techniques that have received a lot of attention: node2vec [23] and struc2vec [24]. Both methods learn continuous representations capturing node structural equivalence and identity, respectively. These approaches are based on applying the skip-gram model [49], which was initially proposed as a model for natural language, over node contexts extracted from the network using biased random walks.On the one hand, the node2vec method computes these contexts combining the breadth-first search (BFS), with the intention of reflecting structural equivalence, and depth-first search (DFS), with the intention of reflecting homophily. This behavior is achieved using two parameters:p and q. The return parameter p controls the likelihood of returning back to the previous node in the random walk. The in-out parameter q controls the tendency of moving to close or far nodes. If q>1, the random walks are biased towards close nodes. Otherwise, the random walks are biased towards visiting more distant nodes. We used the node2vec implementation available at https://github.com/aditya-grover/node2vec.On the other hand, the struc2vec method computes these contexts by inducing a hierarchy that captures different levels of information. This hierarchy is used to build a weighted multilayer network, with a layer for each level in the hierarchy, which is used to generate node contexts by performing biased random walks with the intention of reflecting structural identity. We used the implementation available athttps://github.com/leoribeiro/struc2vec.In order to compute node embeddings using role-based distances, we apply the classical multidimensional scaling (MDS) [50, 51] to the distance matrices.The following sections are devoted to the detailed study of two particular cases, where we evaluate the embeddings obtained using the proposed definition of automorphic distance compared to the previously introduced approaches. For each case, we show how 2-dimensional embeddings can capture relevant information related to the function of the nodes in the network. These sections are intended to provide some insights into the properties of the obtained embeddings, whereas the numerical evaluation is left for the next section.


### 4.2.1. Zachary’s Karate Club Network

Zachary’s karate club network is a popular social network representing the 34 members of a university karate club as its nodes and their interactions outside the club, as its links [52]. During the study carried out by Zachary, a conflict arose between the two club administrators, leading to the split of the club into two groups according to the leader each member decided to follow. For this reason, this network has served as a prototypical case study for community detection algorithms and some network analysis techniques.Zachary observed that the formed groups were highly homogeneous and assortative. Therefore, nodes tended to be connected to nodes that took the same decision. In this context, different embedding techniques have been proposed in the past for generating embeddings distributing nodes in multidimensional spaces according to the leader they decided to follow [47]. This information is crucial when the task is related to community detection. However, these embeddings fail, by nature, to reveal the role of each node in the network. In this study, we evaluate and compare the results obtained by the previously introduced techniques in the task of computing embeddings that are able to capture the role of each node in Zachary’s karate club network.We assigned a class to each node according to objective role-related properties. The two leaders are colored in red. Nodes interacting with the two leaders are colored in green. Nodes not interacting with any of the two leaders are colored in yellow. Finally, the remaining nodes, which interact with only one of the leaders, are colored in blue. Figure3 shows the network drawn using the Fruchterman–Reingold force-directed layout algorithm [53] and the embeddings obtained by applying our automorphic distance, RoleSim, node2vec, and struc2vec.Figure 3
Zachary’s karate club network and its node embeddings with node role coloring. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)Due to the large number of possible parameter combinations in node2vec and struc2vec, the authors decided to use the same values that were used by their original authors in case studies included in their respective papers. For struc2vec, we used the same parameters they used in their Section4.2, where they also studied this network for a different task. Therefore, we set the number of walks per source to 5, the walk length to 15, and the skip-gram window size to 3. For node2vec, we used the same parameters that they used in their case study of the Les Misérables network with the intention of capturing structural equivalence, as shown in their Section 4.1. Therefore, we set p=1 and q=2. Since they did not provide the values of the other parameters, we used the same as those for struc2vec.In the resulting embeddings, shown in Figure3, it can be seen how all techniques seem to capture at least partial information about the function of the nodes. For example, all techniques place the two leaders, represented by the red nodes, in close positions. This observation also applies to green nodes, which represent persons who interact with both leaders. Furthermore, green nodes are highly clustered in all the embeddings.However, both node2vec and struc2vec show a poor separation of the different classes. RoleSim seems to separate the classes better, but still places green nodes inside the cloud of blue nodes. In the three embeddings, the two leaders are placed pretty close to normal club members, without capturing their unique function in the network.In contrast, it can be seen that the four roles are linearly separated in the embedding generated using our distance metric. In addition, it can be seen how the two leaders are clearly mapped as outliers and placed notably apart from the other nodes representing normal members of the club.


### 4.2.2. World Trade Network

In network data mining, homophily is commonly exploited in node classification tasks, since nodes tend to exhibit the same class as their neighbors [54]. Even though this situation occurs in a large number of networks from very diverse domains, homophily based classification techniques fail when the classes of the nodes are defined by the role they play in the network, instead of the community they belong to.An illustrative example of this situation is a network containing data on trade of miscellaneous metal manufactures among 80 countries, according to data gathered in 1993 and 1994 from the Commodity Trade Statistics published by the United Nations [55, 56]. Each country is represented by a node in the network. Each commercial relationship is represented by an arc, which we consider an undirected edge in practice. In this case, arcs correspond to trading high technology products or heavy manufactures between countries.In addition, the authors of this dataset annotated countries in the network with their structural world economic position in 1994. World economic positions are a classification of countries in the context of the world-system theory that explains some complex dynamics observed in the real-world [57]. This classification splits countries into three possible categories: core countries (colored in green), semiperiphery countries (colored in blue), and periphery countries (colored in red). In short, core countries have a high economic, military, and political power, which allows them to control the world economic system. The periphery is composed of less developed countries, owning a disproportionately small share of global wealth. Finally, the semiperiphery consists of countries that do not clearly fall in the previous two categories and exhibit a more intermediate status.In this case, for struc2vec, we used the same parameters their authors used in the analysis carried out in Section4.1 of their manuscript. Therefore, we set the number of walks per source to 20, the walk length to 80, and the skip-gram window size to 5. For node2vec, we also used these parameters with p=1 and q=2.Figure4 shows the trade network drawn using the Fruchterman–Reingold force-directed layout algorithm and the embeddings obtained by applying different techniques. Again, all techniques seem to capture role-related information as shown by the elongated shape of all the embeddings, curved in the case of RoleSim, with core and periphery countries placed at both ends.Figure 4
World trade network and its corresponding node embeddings. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)It can be seen that the automorphic distance, RoleSim, and struc2vec achieve a good separation of core and periphery countries, with some overlapping with countries in the semiperiphery. However, struc2vec shows a highly elongated shape, also present in the case studies included in their manuscript. Finally, node2vec seems to perform worse than the other approaches. In spite of being able to separate the peripheral countries, it does not perform well in the separation of the central countries and those in the semiperiphery.


## 4.2.1. Zachary’s Karate Club Network

Zachary’s karate club network is a popular social network representing the 34 members of a university karate club as its nodes and their interactions outside the club, as its links [52]. During the study carried out by Zachary, a conflict arose between the two club administrators, leading to the split of the club into two groups according to the leader each member decided to follow. For this reason, this network has served as a prototypical case study for community detection algorithms and some network analysis techniques.Zachary observed that the formed groups were highly homogeneous and assortative. Therefore, nodes tended to be connected to nodes that took the same decision. In this context, different embedding techniques have been proposed in the past for generating embeddings distributing nodes in multidimensional spaces according to the leader they decided to follow [47]. This information is crucial when the task is related to community detection. However, these embeddings fail, by nature, to reveal the role of each node in the network. In this study, we evaluate and compare the results obtained by the previously introduced techniques in the task of computing embeddings that are able to capture the role of each node in Zachary’s karate club network.We assigned a class to each node according to objective role-related properties. The two leaders are colored in red. Nodes interacting with the two leaders are colored in green. Nodes not interacting with any of the two leaders are colored in yellow. Finally, the remaining nodes, which interact with only one of the leaders, are colored in blue. Figure3 shows the network drawn using the Fruchterman–Reingold force-directed layout algorithm [53] and the embeddings obtained by applying our automorphic distance, RoleSim, node2vec, and struc2vec.Figure 3
Zachary’s karate club network and its node embeddings with node role coloring. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)Due to the large number of possible parameter combinations in node2vec and struc2vec, the authors decided to use the same values that were used by their original authors in case studies included in their respective papers. For struc2vec, we used the same parameters they used in their Section4.2, where they also studied this network for a different task. Therefore, we set the number of walks per source to 5, the walk length to 15, and the skip-gram window size to 3. For node2vec, we used the same parameters that they used in their case study of the Les Misérables network with the intention of capturing structural equivalence, as shown in their Section 4.1. Therefore, we set p=1 and q=2. Since they did not provide the values of the other parameters, we used the same as those for struc2vec.In the resulting embeddings, shown in Figure3, it can be seen how all techniques seem to capture at least partial information about the function of the nodes. For example, all techniques place the two leaders, represented by the red nodes, in close positions. This observation also applies to green nodes, which represent persons who interact with both leaders. Furthermore, green nodes are highly clustered in all the embeddings.However, both node2vec and struc2vec show a poor separation of the different classes. RoleSim seems to separate the classes better, but still places green nodes inside the cloud of blue nodes. In the three embeddings, the two leaders are placed pretty close to normal club members, without capturing their unique function in the network.In contrast, it can be seen that the four roles are linearly separated in the embedding generated using our distance metric. In addition, it can be seen how the two leaders are clearly mapped as outliers and placed notably apart from the other nodes representing normal members of the club.


## 4.2.2. World Trade Network

In network data mining, homophily is commonly exploited in node classification tasks, since nodes tend to exhibit the same class as their neighbors [54]. Even though this situation occurs in a large number of networks from very diverse domains, homophily based classification techniques fail when the classes of the nodes are defined by the role they play in the network, instead of the community they belong to.An illustrative example of this situation is a network containing data on trade of miscellaneous metal manufactures among 80 countries, according to data gathered in 1993 and 1994 from the Commodity Trade Statistics published by the United Nations [55, 56]. Each country is represented by a node in the network. Each commercial relationship is represented by an arc, which we consider an undirected edge in practice. In this case, arcs correspond to trading high technology products or heavy manufactures between countries.In addition, the authors of this dataset annotated countries in the network with their structural world economic position in 1994. World economic positions are a classification of countries in the context of the world-system theory that explains some complex dynamics observed in the real-world [57]. This classification splits countries into three possible categories: core countries (colored in green), semiperiphery countries (colored in blue), and periphery countries (colored in red). In short, core countries have a high economic, military, and political power, which allows them to control the world economic system. The periphery is composed of less developed countries, owning a disproportionately small share of global wealth. Finally, the semiperiphery consists of countries that do not clearly fall in the previous two categories and exhibit a more intermediate status.In this case, for struc2vec, we used the same parameters their authors used in the analysis carried out in Section4.1 of their manuscript. Therefore, we set the number of walks per source to 20, the walk length to 80, and the skip-gram window size to 5. For node2vec, we also used these parameters with p=1 and q=2.Figure4 shows the trade network drawn using the Fruchterman–Reingold force-directed layout algorithm and the embeddings obtained by applying different techniques. Again, all techniques seem to capture role-related information as shown by the elongated shape of all the embeddings, curved in the case of RoleSim, with core and periphery countries placed at both ends.Figure 4
World trade network and its corresponding node embeddings. (a) Force-directed layout, (b) automorphic embedding, (c) RoleSim embedding, (d) node2vec embedding, and (e) struc2vec embedding.
(a)(b)(c)(d)(e)It can be seen that the automorphic distance, RoleSim, and struc2vec achieve a good separation of core and periphery countries, with some overlapping with countries in the semiperiphery. However, struc2vec shows a highly elongated shape, also present in the case studies included in their manuscript. Finally, node2vec seems to perform worse than the other approaches. In spite of being able to separate the peripheral countries, it does not perform well in the separation of the central countries and those in the semiperiphery.


## 4.3. Performance Evaluation of Computed Node Embeddings

The case studies analyzed in the previous section allowed us to gain some insight about the embeddings generated by our distance metric in comparison to other state-of-the-art approaches. However, in order to perform a more objective and exhaustive evaluation, we extend this analysis by carrying out a quantitative performance evaluation in this section.As previously stated, the evaluation of techniques for role discovery is a complicated task due to the lack of available evaluation datasets with role-based ground-truth data. This difficulty extends to the evaluation of techniques for generating embeddings capturing the notion of the node role. The most common solution is indirectly evaluating these embeddings based on their application to other tasks with evaluable or measurable performance metrics. For example, these embeddings can be evaluated by means of a classification problem, where labels related to node roles are predicted using the generated embeddings. However, there is no guarantee that the labels are completely determined by the roles of nodes in the network. Therefore, these experiments only evaluate which techniques capture the driving factors of these labels better, and in which node roles may only partially contribute or not contribute at all. This criticism extends to other tasks previously used to evaluate role-based embeddings, such as link prediction.In order to overcome these limitations while offering an objective evaluation procedure, we propose a new approach to evaluate techniques for computing role-based embeddings for nodes. Our proposal consists of measuring how well the embeddings produced by these techniques can reconstruct global network structural properties based on the same arguments we used in Section4.1. Nodes with a similar role in the network also exhibit similar topological properties. Therefore, evaluating how well these embeddings can be used to reconstruct these topological properties is an indirect way of assessing the quality of these embeddings.In our experimentation, we considered the network structural properties previously described in Section4.1. For each method and each property, we trained a linear regression model using the ordinary least squares method. For a given node, these trained linear models take its embedding as input and output the predicted score for the node corresponding to the structural property. We carried out our experimentation using five-dimensional embeddings. We chose this number of dimensions as a reasonable number, enough to capture complex role-related patterns.In order to carry out an unbiased evaluation, these models were trained using a five-fold crossvalidation, with 80% of the nodes as training set and the remaining 20% as the test set. In addition to crossvalidation, since all the evaluated methods include an element of randomness, we ran five different executions of the evaluation procedure using different random seeds, both for the generation of the embeddings and the crossvalidation procedure. The root mean squared error (RMSE) was used as the evaluation metric. The reported error for a method on a given dataset is the average RMSE obtained in the multiple executions of the five-fold crossvalidation using different seeds.In this experiment, we included the approximated version of our proposal, node2vec, and struc2vec. RoleSim was left out due to its high computational complexity, which limits its applicability to large networks.Methods included in the comparison have different parameters that must be adjusted. Due to the high computing requirements for executing each technique multiple times, we limited our experimentation to a restricted set of parameters. For our approximation of the automorphic distance metric, we chose 30 clusters and samples as parameters, since it is a reasonable value considering the size of the studied networks, which are presented below.For node2vec and struc2vec, we limited our experimentation to different parameter settings included in their original papers. For node2vec, we used 0.50, 1, and 2 as values for thep parameter. The q parameter was also set to 0.50, 1, and 2. In order to avoid running a large number of parameter combinations, which is computationally intensive, we fixed the remaining parameters to the default values used in the original paper: number of walks per source to 10, length of walk per source to 80, and skip-gram window size to 10. For struc2vec, we report the best results using the following parameter combinations. We tested 10 and 20 walks per source with lengths 15 and 80. For the skip-gram model, we used window sizes of 5 and 10. The algorithm was executed with all the optimizations enabled: OPT1, OPT2, and OPT3.Five different networks were used in our experimentation:(i)
A network, composed of 399 nodes and 5995 links, representing European air-traffic in 2016 [24], built using data from the Statistical Office of the European Union (Eurostat). Nodes representing airports and links represent the existence of commercial flights between pairs of airports.(ii)
Another network, with 1190 nodes and 13599 links, representing air-traffic in 2016 from the United States of America [24]. The network was built using data from the Bureau of Transportation Statistics.(iii)
A communication network, with 1005 nodes and 16706 links, based on mailing data from a large European research institution [58]. Each node represents a person, and each link represents that two nodes shared at least one email.(iv)
Another communication network, composed of 1133 nodes and 5451 links, built using mailing data from the University Rovira i Virgili in Tarragona [59], located in Spain. Each node represents an user, and each link represents that at least one email was sent between the two users.(v)
A network, with 1010 nodes and 3649 links, representing the thesaurus written by Peter Mark Roget [43]. Each node represents a category and each link represents a relation between a pair of categories.The results obtained for this evaluation procedure are shown in Table5. The best-performing parameters for struc2vec and node2vec were omitted for the sake of clarity. Note that the absolute error is small in all cases due to the order of magnitude of the scores computed using the included network properties. These results show how the embeddings computed using the approximation of the proposed automorphic distance metric achieve a lower RMSE than the other approaches in 13 out of 15 cases. Only node2vec outperforms our approach in two cases for closeness, where it performs especially well compared to the other approaches.Table 5
Obtained RMSE for the considered methods, networks, and structural network properties.
MethodPageRankClosenessBetweennessEU airportsAutomorphic7.67×10−42.34×10−27.18×10−3struc2vec1.66×10−34.15×10−28.23×10−3node2vec2.39×10−35.58×10−29.38×10−3USA airportsAutomorphic6.41×10−43.59×10−27.81×10−3struc2vec9.66×10−44.69×10−27.99×10−3node2vec1.10×10−34.43×10−28.28×10−3EU-emailAutomorphic2.72×10−45.36×10−22.63×10−3struc2vec7.38×10−46.45×10−23.83×10−3node2vec9.16×10−44.95×10−24.15×10−3Univ-emailAutomorphic2.92×10−42.00×10−22.63×10−3struc2vec5.23×10−42.49×10−23.73×10−3node2vec6.58×10−42.83×10−24.18×10−3RogetAutomorphic2.68×10−43.17×10−22.52×10−3struc2vec3.70×10−43.62×10−23.27×10−3node2vec4.68×10−41.74×10−23.67×10−3The lowest RMSE for each dataset and structural network property is marked in bold.These results suggest that our proposal can capture node-related information better than other state-of-the-art approaches, as shown by the lower error achieved in the task of reconstructing topological properties.


## 5. Conclusions

In this paper, we have proposed a novel distance metric for nodes that relaxes the strict concept of automorphic equivalence. To the best of our knowledge, this is the first work to propose a consistent nonnormalized distance metric that captures the concept of automorphic equivalence without approximating it using feature engineering. In addition, we have shown that the proposed distance function is a valid distance metric by proving the required conditions. Furthermore, we have shown how our metric can be exploited to generate node embeddings that capture role information. Finally, we have carried out different experiments in order to show how our proposal can outperform other state-of-the-art techniques in different role-related tasks.Our proposal creates new opportunities in problems related to role discovery. Future work includes exploiting our distance metrics in problems related to anomaly detection in networks and transfer learning based on roles shared by nodes across different networks.



---

*Source: 5571006-2021-10-13.xml*