An Optimization-based Approach To Node Role Discovery in Networks: Approximating Equitable Partitions
Authors: Michael Scholkemper
Michael T Schaub
Venue: NeurIPS 2023 poster (2023)
Keywords: Role Extraction
Graph Learning
Node Embeddings
Weisfeiler Lehman
Equitable Partition
TL;DR: We propose a novel perspective on role extraction grounded in the theory concerning graph isomorphism and present a cost function that is to be optimized in order to extract the roles.

Abstract: Similar to community detection, partitioning the nodes of a complex network according to their structural roles aims to identify fundamental building blocks of a network, which can be used, e.g., to find simplified descriptions of the network connectivity, to derive reduced order models for dynamical processes unfolding on processes, or as ingredients for various network analysis and graph mining tasks. In this work, we offer a fresh look on the problem of role extraction and its differences to community detection and present a definition of node roles and two associated optimization problems (cost functions) grounded in ideas related to graph-isomorphism tests, the Weisfeiler-Leman algorithm and equitable partitions. We present theoretical guarantees and validate our approach via a novel “role-infused partition benchmark”, a network model from which we can sample networks in which nodes are endowed with different roles in a stochastic way.

An Optimization- Approach To Node Role Discovery in Networks: Approximating Equitable Partitions
Michael Scholkemper Department of Computer Science RWTH Aachen University de
Michael T. Schaub
Department of Computer Science
RWTH Aachen University schaubēcs. rwth-aachen de
scholkemper@cs.
Abstract
Similar to community detection, partitioning the nodes of a network according to their structural roles aims to identify fundamental building blocks of a network. The found partitions can be used, e.g., to simplify descriptions of the network connectivity, derive reduced order models for dynamical processes unfolding on processes, or ingredients for various graph mining tasks. In this work, we offer a fresh perspective the problem of role extraction and differences community detection and present defimition of node roles related to graph-isomorphin the Weisfeiler-Leman algorithm, and equitable partitions. We study two associated optimization problems (cost functions) grounded in ideas from graph isomorphism testing and present theoretical guarantees associated with the solutions to these problems. Finally, we validate our approach via novel "role-infused partition benchmark", a network model from which we can sample networks in which nodes are endowed with different roles in stochastic way.
tests,
Introduction
Networks powerful abstraction for range of complex systems 33 45
To comprehend such
networks we often seek patterns in their connections, e.g., core-periphery structures or densely knit communities. A complementary notion community structure is that of role partition of the nodes. The concept of node roles, or node equivalences, originates in social network analysis [24]. Node roles are often related to symmetries or connectivity features that can be used simplify complex networks. Contrary to communities, even nodes that are far apart or are part of different connected components of a network can have the same role 40
Traditional approaches to defining node roles, put forward in the context of social network analysis (8) consider exact node equivalences, based structural symmetries within the graph structure. The earliest notion that of structural equivalence [26). which assigns the same role to nodes they are adjacent the same nodes. Another definition is that of automorphic equivalence (14), which states that nodes are equivalent if they belong to the same automorphism orbits. Closely related the idea of regular equivalent nodes (48), defined recursively as nodes that are adjacent to equivalent nodes.
However, large real-world networks often manifest such a way that these definitions result in a vast number of different roles. What's more, the above definitions do not define similarity metric between nodes, and it is thus not obvious how to compare two nodes that are deemed not equivalent. For example, the above definitions all have in common that nodes with different degrees also have different roles. With the aim of reducing a network's 's complexity, this is detrimental.
To resolve this problem in a principled way and to provide an effective partitioning of large graphs into nodes with similar roles, we present a quantitative definition of node roles in this paper. Our definition of roles is based on so-called equitable partitions (EPs), which are strongly related to the notion of regular equivalence [48). Crucially, this not only allows us to define an equivalence, but we can also quantify the deviation from an exact equivalence numerically. Further, the notion of EPs generalizes orbit partitions induced by automorphic equivalence classes in principled way
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and thus remains tightly coupled to graph symmetries. Knowledge of EPs in particular graph can, e.g., facilitate the computation of network statistics such as centrality measures [T. As they are associated with certain spectral signatures, EPs are also relevant for the study of dynamical processes on networks such as cluster synchronization [4 42], consensus dynamics [51], and network control problems (28). They have even been shown to effectively imply an upper bound on the expressivity
of Graph Neural Networks 30 50].
Related Literature The survey by Rossi and Ahmed (38] puts forward an application- -based approach node role extraction that evaluates the node roles by how well they can be utilized in downstream machine learning task. However, this perspective is task-specific and more applicable to node embeddings based on roles rather than the actual extraction of roles.
Apart from the already mentioned exact node equivalences originating from social network analysis, there exist numerous works role extraction, which focus identifying nodes with similar roles, by associating each node with a feature vector that is independent of the precise location of the nodes in the graph. These feature vectors can then be clustered to assign nodes to roles. A recent overview article [40] puts forward three categories: First, graphlet- based approaches [35] 39 25 use the number of graph homomorphisms of small structures to create node embeddings. This retrieves extensive, highly local information such as the number of triangles a node is part of. Second, walk- approaches 33 IT embed nodes based certain statisties of random walks starting each node. Finally, matrix- fantriix-fattoizttion based approaches [17 200 find rank-r approximation of a node feature matrix (F = MG). Then, the left side multiplicand M E TR V of this factorization is used soft assignment of the nodes clusters.
Jin et al. [21] provide a comparison of many such node embedding techniques in terms of their ability to capture exact node roles such as structural, automorphic, and regular node equivalence. Detailed overviews of (exact) role extraction and its links to related topics such as block modeling are also given in [9 10].
Contribution Our main contributions are follows:
We provide a principled stochastic notion of node roles, grounded in equitable partitions,
which enables us to rigorously define node roles in complex networks.
We provide a family of cost functions to assess the quality of a putative role partitioning. Specifically, using a depth parameter d, we can control how much of a node's 's neighborhood is taken into account when assigning roles.
We present algorithms to minimize the corresponding optimization problems and derive associated theoretical guarantees.
We develop generative graph model that can be used to systematically test the recovery of roles in numerical experiments, and use this novel benchmark model to test our algorithms and compare them to well-know role detection algorithms from the literature.
2 Notation and Preliminaries
Graphs. A simple graph G (V, E) consists of a node set V and an edge set F = fuv | u, u E V). The neighborhood N(v)= = {x or E E} of a node u is the set of all nodes connected to v. We allow self-loops vo E and positive edge weights w E Rt.
Matrices. For a matrix M, Ms, is the component the i-th row and j-th column. We use M.., to denote the i-th row vector of M and M_, to denote the j-th column vector. I, is the identity matrix and n the all-ones vector, both of size n respectively. Given a graph G = (V, E), we identify the node set V with {1, ..... n). An adjacency matrix of given graph is matrix A with entries Au, = 0 uu & E and An = (ww)) otherwise, where we set w(ur) = for unweighted graphs for all ur F. p(A) denotes the largest eigenvalue of the matrix A.
Partitions. node partition C = (C1,C2, Ck) is a division of the node set V CIÜC, ... UC into l disjoint subsets, such that each node is part of exactly one class C.. For node E V. we write C(v) to denote the class C, where v E C, We say a partition C" is coarser than C (C" 3 C)
if Cv(v) * C'(u) = C(v)= o C(u). For partition C, there exists partition indicator matrix H E {0, 13 IViK with Hag = + i Cj.
2

---

2.1 Equitable Partitions.
An equitable partition (EP) is a partition C= (C1, C2,,., Cx) such that v, a e C2 implies that
[C(x)= C,1 Σ (EN(M)
Σ <MN(w))
[C(x) c,1
for all 1 و S. k. where the Iverson bracket [C(x) C,] is 1 ((+) C3 and 0 otherwise. The coarsest EP (cEP) is the equitable partition with the minimum number of classes k. A standard algorithm to compute the cEP is the so-called Weisfeiler-Lemat (WL) algorithm [47], which itera- tively assigns a color c(v) E NN to each node v E V starting from a constant initial coloring. In each iteration, an update of the following form is computed:
(v) hash (c)),, (d(()) E N())))
where hash is an injective hash function, and {{- denotes a multiset (in which elements can appear more than once). In each iteration, the algorithm splits classes that do not conform with eq. ① At some point T, the partition induced by the coloring no longer changes and the algorithm terminates returning the cEP as {(c")-'(c" (u))le E V}. While simple, the algorithm is a powerful tool and is used subroutine in graph isomorphism testing algorithms [4] 29
On a node level, the cEP carries an immense amount of information about the structure of the network surrounding each node. One can think of it as iteratively building tree of possible paths from the start node to neighboring nodes. At the first iteration, the color ct (v) encodes the degree of node e in the graph. At the second iteration, it encodes the number of nodes with certain degree that are adjacent to v. Thus, iterating this update rule (eq. (2) encodes the structure of possible paths surrounding each node and if these trees are isomorphic for two nodes, the two remain in the same class. This tree of possible paths (also called unraveling or unrolling) is profoundly important for processes that move over the edges of network such dynamical systems 42 [1] and GNNs 50 30), and even
simple ones like PageRank [41] and other centrality measures 44
The above definition is useful algorithnically but only allows to distinguish between exactly equivalent vs. non-equivalent nodes. To obtain a meaningful quantitative metric to gauge the quality of partition, the following equivalent algebraic characterization of an EP will be instrumental: Given a graph G with adjacency matrix A and a partition indicator matrix H&PP of the cEP, it holds that:
AHæ = Hare (e
AHar =: A".
The matrix AHEP E B counts in each row (for each node) the number of neighboring nodes which must be equal to H&F (node) is assigned one of the k rows of the k x k matrix A= Thus, from any node u of the same class neighboring nodes of a given class C2 is equal to some fixed number this is precisely the statement of Equation ([. The matrix A containing the connectivity statistics between the different classes the adjacency matrix of the quotient graph, which can be viewed as a compressed graph with similar structural properties to the original. In particular, the adjacency matrix of the original graph inherits all eigenvalues from the quotient graph, as can be seen by direct computation. Specifically, let (X, 2) be an eigenpair of A", then AH = A = AHarv.
within each class (C; for = I,...,k) k),
matrix in which each row
Cr the sum of edges from
This makes EPs interesting from dynamical systems point of view: the dominant (if unique) eigenvector is shared between the graph and the quotient graph. Hence, centrality measures such as Eigenvector Centrality PageRRank are predetermined if one knows the EP and the quotient graph 41 For similar reasons, the cEP also provides insights into the long-term behavior of other (non)-linear dynamical processes such as cluster synchronization [42] or consensus dynamics (5I). Recently, there has been some study on relaxing the notion of "exactly" equitable partitions. One approach is to compare the equivalence classes generated by eq. 22) by computing the edit distance of the trees (the unravellings) that are encoded by these classes implicitly [19]. Another way is to relax the hash function (eq. (2) to not be injective. This way, "buckets" of coarser equivalence classes are created (7). Finally, using a less algorithmic perspective, one can define the problem of approximating EP by specifying a tolerance e of allowed deviation from eq. I and consequently asking for the minimum number of clusters that still satisfy this constraint (22] In this paper, we adopt the opposite approach and instead specify the number of clusters and then ask for the partition minimizing a
cost function (section 4 i.c. the most equitable partition with & classes. We want to stress that while
3

---

similar, none of these relaxations coincide with our proposed approach. For clarity, we would also like to point out that the notion sometimes called almost or externally equitable partition [2 in the literature is not the same as the approximately equitable partition we propose here. The former is an exactly equitable partition (eq. (T) that simply disregards the number of adjacent neighbors within the same class.
2.2
The Stochastic Block Model
The Stochastic Block Model (SBM) T is a generative network model which assumes that the node set is partitioned into blocks. The probability of edge between node i and node j is then only dependent on the blocks Bi) and B(j). Given the block labels the expected adjacency matrix of a network sampled from the SBM fulfills:
E AJ = H
(4)
where F the indicator matrix of the blocks and ()) = Pr(( E E(G)) is the probability with which an edge between the blocks (i) and B(j) occurs.
For simplicity, we allow self-loops in the network. The SBM is used especially often in the context of community detection, in the form of the planted partition model.
In this restriction of the SBM, there only an inside probability p and an outside probability g and if i * j. Usually, one also restricts > q. to obtain a homophilic
R. = p if i = j and U community structure i.e., nodes of the same class are more likely to connect. However, p < (heterophilic communities) are also sometimes considered.
3 Communities vs. Roles
In this section, we more rigorously define "communities" and "roles" and their difference. To this end, we first consider certain extreme cases and then see how we can relax them stochastically. Throughout the paper, we use the term communities synonymously with what is often referred to as homophilic communities, i.e., a community is set of nodes that more densely connected within the set than to the outside. In this sense, one may think of perfect community partition into & communities if the network consists of & cliques. In contrast, we base our view of the term "role" on the cEP: is the cEP, then ((v) is v's perfect role. In this sense, the perfect role partition into k roles is present when the network has an exact EP with & classes. The intuition behind perfect communities and perfect roles can be seen in appendix A.
In real-world networks, such a perfect manifestation of communities and roles rare. fact, even there was a real network with a perfect community (or role) structure, due to noisy data collection process this structure would typically not be preserved. Hence, to make these concepts more useful in practice we need to relax them. For communities, the planted partition model relaxes this perfect notion of communities of disconnected cliques to a stochastic setting: The expected adjacency matrix exhibits perfect (weighted) cliques even though each sampled adjacency matrix may not have such a clear structure. To obtain a principled stochastic notion of a node role, we argue that planted role model should, by extension, have exact cEP in expectation:
Definition 3.1. Two nodes u, V have the same stochastic role if they are in the same class in the cEP of E B[A].
The above definition is very general. To obtain a practical generative model from which we can sample networks with a planted role structure, we concentrate on the following sufficient condition. We define probability distribution over adjacency matrices such that for given role partition C. for x, E C₁ and classes C₁ there exists a permutation a C₁ - C₁ such that Pr(Ar,==1) Pr(Ay.a(z) 1) Vz E Cz. That is: two nodes have the same role if the stochastic generative process that links them to other nodes that have a certain role is the same up to symmetry. Note that if we restrict a the identity, we recover the SBM. Therefore, we will consider the SBM as our stochastic generative process in the following.
RIP model. In line with our above discussion we propose the role-infused partition (RIP) model, to create well-defined benchmark for role discovery, which allows to contrast role and community

---

163 150 Id)
10
Input: Graph adjacency A E {0, 1
number of classes k
Output: Node assignment H E {0, 1) normalize(A)
Initialize H =
3 for number of steps do
X =H
H cluster(X)
Figure I: Example of the RIP model. It depicts (a) the expected adjacency matrix and the correct according (b) SBM inference, (c) community detection, (d) role detection.
Return
Algorithm 1: Approximate Weisfeiler Lehman Algorithm.
structure. The RIP model is fully described by the parameters p E R, kn N, Proke R as follows: We sample from an SBM with parameters Q2, HB (see fig. T:
Srole: o.
if - 1
P4,5
(5)
otherwise
where HB corresponds to c & blocks of size n. There are distinct communities analogous to the planted partition model. The probability of being adjacent for nodes that are not in the same community is p. In each community, there are the same k distinct roles with their respective probabilities to attach to one another as defined by Spole- Each role has n instances each community,
Notice that the RIP model has both a planted community structure with e communities and planted role structure, since [[A] has an exact cEP with & classes (definition 3.1) 1b. We stress that the central purpose of our model to delineate the role recovery from community detection, i.e., community detection is not the endeavor of this paper. Rather, the planted communities within the RIP model are meant precisely as an alternative structure that can be found the data and serve as control mechanism to determine what structure an algorithm finds. To showcase this, consider Figure [ which shows an example of the RIP model for c = 2, = 3, n 10, = 0.1. shows a graph that has 2 communities, each of which can be subdivided into the same 3 roles. In standard SBM inference, one would like to obtain blocks each combination of community and role being assigned its own block ()). In community detection, with the objective of obtaining 2 communities, the target clustering would be to merge the first and the second into one cluster respectively (T.).. However, the target clustering for this paper aiming for roles is the one the far right dI), combining from each community the nodes that have stochastically the same neighborhood structure.
Extracting Roles by Approximating the cEP
In this section, define family of cost functions (eq. 6 that frame role extraction optimization problem. That is, we try to answer the question: Given a desired number k of role classes, what is the partition that is most similar exact equitable partition with a small number of classes is often not possible: returns the singleton partition almost all random graphs (5). Already small asymmetries, inaccuracies, noise in data collection can lead to a trivial cEP made up of singleton classes. As such, the cEP is neither a robust nor particularly useful choice for noisy or even just slightly asymmetric data. Our remedy the problem is to search for coarser partitions that are closest to being equitable.
EP? As discussed above, searching for
Considering the algebraic definition of cEP (eq. [ side (throughout the paper, we use the &g norm by
intuitively would like minimize the
difference between the left- and the default and the L norm where specified):
(6) Here D = d1 H) is the diagonal matrix with the sizes of the classes on its diagonal. We note that HD-1HT H HHH H) H H is the projection onto the column space of H. However, eq. (6) disregards an interesting aspect of the exact cEP. By its definition, the cEP is invariant under multiplication with A. That is,
TEP( A, H) = ||H HD-1H AH
A HaP HeEr(AF) for all t N
5

---

In this section, we thus look into optimizing the short-term cost function by recovering the stochastic roles in the RIP model. Given samples (s) of the same RIP model, asymptotically, the sample mean "i=14 ( [[A] converges the expectation This is especially interesting from a dynamical systems point of view, since dynamics cannot leave the cEP subspace once they are inside it. Indeed, even complex dynamical systems such as Graph To address this, we put forward the following
Neural Networks suffer from this restriction 50 30 family of cost functions.
A (A', H)
Taur (A, H) = Σ P(A)
The factor of 1 is to rescale the impacts of each matrix power and not disproportionately enhance p(A)) larger matrix powers. This family of cost functions measures how far the linear dynamical system t + A'H И diverges from a corresponding equitable dynamical system after d steps. Equivalently, it takes the d-hop neighborhood of each node into account when assigning roles. The larger d, the deeper it looks into the surroundings of a node. Note that all functions of this family have in common that if HE indicates the exact cEP, then I d (, H&EP) 0 for any choice of d.
In the following, we consider the two specific cost functions with extremal values of for our theoretical results and our experiments: For d = 1, I-EP is measure of the variance of each node's adjacencies from the mean adjacencies in each class (and equivalent to eq. (6). As such, it only measures the differences in the direct adjacencies and disregards the longer-range connections. We call this the short-term cost function. The other extreme we consider is -E-- where d + co. This function takes into account the position of node within the whole graph. It takes into account the long-range connectivity patterns around each node. We call this function the long-term cost.
In the following sections, we aim to optimize these objective functions to obtain clustering of the nodes according to their roles. However, when optimizing this family of functions, in general, there exist examples where the optimal assignment is not isomorphism equivariant (see appendix B). As isomorphic nodes have exactly the same global neighborhood structure, arguably, they should be assigned the same role. To remedy this, we restrict ourselves to partitions compatible with the cEP when searching for the minimizer of these cost functions.
4.1 Optimizing the Long-term Cost Function
In this section, consider optimizing the long-term objective eq. (7). This is closely intertwined with the dominant eigenvector A, as the following theorem shows:
Theorem 4.1:
Let H be the set of indicator matrices H E {0, 1jnxk s.t. H1, = 1 Let A E Raxn be an udjacency matrix. Assume the dominant eigenvector to the eigenvalue pl (() of A is unique. Using the &1 norm in eq. 6 the optimizer
OPT = arg min lim T (LEr(A,F) H)
HEH d-400
can be computed in O(a + nk + n log(n)), where a is the time needed to compute the dominant eigenvector of A.
The proof of the theorem directly yields a simple algorithm that efficiently computes the optimal assignment for the long-term cost function. Simply compute the dominant eigenvector and then cluster it using I-dimensional k-means. We call this EV-based clustering.
4.2 Optimizing the Short-term Cost Function
In contrast to the previous section, the short-term cost function is more challenging. fact, Theorem 4.2: Optimizing the short-term cost is NP-hard.
oc. Thus, recovering the ground truth partition is consistent with minimizing the short-term cost in expectation.
To extract the stochastic roles, we consider an approach similar to the WI algorithm which computes the exact cEP. We call this the Approximate WI. algorithm (Algorithm[T) Tp. variant of this without the clustering step proposed in [23). Starting with one class encompassing all nodes, the algorithm

---

iteratively computes an embedding vector = (I1, ..., 2b,) for each node E V according to the adjacencies of the classes:
[C(0(() (x)
MEN(O)
The produced embeddings are then clustered obtain the partition into l classes H of the next iteration. The clustering routine can be chosen freely. This is the big difference to the WL algorithm, which computes the number of classes on-the-fly- without an upper bound to the number of classes, Another difference is that the assignment from the previous iteration is not taken into account. This is a design choice and clustering X concatenated with H works similarly, In practice, we have found that omitting H makes it easier to reassign nodes that were assigned to the wrong cluster in previous iteration, thus making the algorithm more robust. also does not take away from the power of the algorithm as Morris et al. [30] show this variant to be equivalent to the original WL algorithm. The main theoretical result of this section uses average linkage for clustering:
Theorem 4.3: Let A be sampled from the RIP model with parameters E
N, Prote R Let H role: "". be the indicator matrices of each iteration when performing (t')
the exact WL algorithm on [[A]] Let ô = minoge ST minigi II(S )i__ ) Using average linkage in algorithm 7 in the clustering step and assuming the former correctly infers k, if
n -W-1(W1
(8)
28
where W the Lambert W function, then with probability at least q: Algorithm finds the correct role assignment using average linkage for clustering.
The proof hinges on the fact that the number of links from each node to the nodes of any class concentrates around the expectation. Given a sufficient concentration, the correct partitioning can then be determined by the clustering step. Notice that even though we allow for the SBM to have more blocks than there are roles, the number of roles (and the number of nodes therein) is the delimiting factor here- not the overall number of nodes. Notice also that theorem 4.3 refers to exactly recovering the partition from only one sample. Typically, concentration results refer to concentration of multiple samples from the same model. Such a result can be derived as a direct consequence of Theorem 4.3 and can be found in appendix E. The bound given in the theorem is somewhat crude in the sense that it scales very poorly as decreases. This is to be expected as the theorem claims exact recovery for all nodes with high probability.
Fractional Assignments In a regime, where the conditions of Theorem 4.3 do not hold, it may be beneficial to relax the problem. A hard assignment in intermediate iterations, while possible, has shown to be empirically unstable (see experiments). Wrongly assigned nodes heavily impact the next iteration of the algorithm. As remedy, a soft assignment proven more robust. We remain concerned with finding the minimizer H of eq. (6) However, we no longer constrain Hs, {0, 1). but relax this to 0 < H,,j < 1. H must still be www-stochastic ie. H1 = 1. That is, a node may now be fractionally assigned to multiple classes designating how strongly it belongs each class. This remedies the above problems,
while not entirely different has
algorithms such as fuzzy c-means or Bayesian Gaussian Mixture Models are able to infer the number of clusters at runtime and must also not make hard choice about which cluster node belongs to. This also allows for Gradient Descent approaches like GNNs. We investigate these thoughts empirically in the experiments section.
5 Numerical Experiments
For the following experiments, we use two variants of the Approximate WL WL algorithm (T). one where the clustering is done using average linkage and one where fuzzy c-means is used. We benchmark the EV-based clustering (4.I) and the 2 variants of the Approximate WL algorithm as well as node classes obtained from the 2vle2vec B] and the node2vec [16), struc2vec [36] and rolX [77] node embeddings (called R2V, N2V, S2V and rolX in the figures). We retrieve an assignment from the baseline benchmark embeddings by k-means. The three X2vec node embedding techniques use autoencoders with skip-gram to compress information obtained by random walks. rolX uses recursive feature extraction
[8] paired with non-negative matrix factorization. While node2vec is somewhat
7

---

175
36
tomplemm
125
0.6
-16
0.
-22
13
esampees
Figure 2: Role recovery on graphs sampled from the RIP model. (a-c) On the x-axis, we vary the number of samples that are averaged to obtain the input A. The graphs used are randomly sampled from the planted partition model. On the y-axis, we report the long-term cost 620-ER (a), the short-term cost (b), and the overlap of the clusterings with the ground-truth (c) over 100 runs along with their standard deviation. In (d), the average role assignment (rows reordered to maximize overlap) is shown for the number of samples 1.
universal node embedding technique also taking into account the community structure of a network, role2vec, struc2vec, and rolX are focussed on embedding node due its role. All embeddings are state-of-the-arg node embedding techniques used for many downstream tasks. Further, we compare the above algorithms to the GIN [50], which is trained minimize the short-term cost individually on each graph. The GIN uses features of size 32 that are uniformly initialized and is trained for 1000 epochs. To enable a fair comparison, we convert the fractional assignments into hard assignments by taking the class with the highest probability for each node. Experimental data and code is available here"
Experiment 1: Planted Role Recovery. For this experiment, we sampled adjacency matrices A from the RIP model as described in Section 3ith c = k = 5, = 10, = 0.05, Prooe E IR jg* Each component of Srole sampled uniformly random i.i.d from the interval [o, 1]. We then sample samples from this RIP model and perform the algorithms on the sample mean. The mean and standard deviation of long-tern and short-term costs and the mean recovery accuracy of the ground truth and its variance are reported in Figure[Jover 100 trials for each value of s. The overlap score of the assignment C' with the ground truth role assignment C computed as:
CocnnC [.,
overlap(C, CRR)
max
peemuotations
Figure (d) shows the mean role assignments output by each algorithm. Since the columns of the output indicator matrix H of the algorithms are not ordered in any specific way, we use the maximizing permutation a to align the columns before computing the average.
Discussion. In Figure (a), one can clearly see that the EV-based clustering outperforms all other algorithms measured by long-term cost, validating Theorem 4.1 While both Approximate WL algorithms perform similarly in the cost function, the fuzzy variant has slight edge in recovery accuracy. We can see that the tendencies for the short-term cost and the accuracy are directly adverse. The Approximate WL algorithms have the lowest cost and also the highest accuracy recovery. The trend continues until all three X2vec algorithms are similarly bad in both measures. The GIN performs better than the X2vec algorithms both in terms of cost and accuracy. However, mainly finds 2 clusters. This may be because of the (close to) uniform degree distribution in these graphs. On the contrary, the node2vec and role2vec detect the communities instead of the roles. This is surprising for role2vec since it aims to detect roles.
Experiment 2: Inferring the Number of Roles and Centrality. A prominent problem in practice that has been scarcely addressed in this paper so far is that the number of roles may not be known. Some algorithms - like fuzzy c-means or GIN - can infer the number of clusters while performing the clustering. In this experiment, we consider the protein dataset (6] and run the suite of algorithms
https://git.rwtth hwtp://wwww....ccccceceeeeee///e http:p/bbiiiittooo0000oaapaaaaaa based approach to to-node-role- discovery-in-netwoee

---

142
SOTW COST
20-4
PageBork
2e-3
Eiperwector
1e-2
Closeness
10-3
Becwcontess
2.2
22
1.4
45
2.0
2.2
4.0
10
16
14
14
1.2
10
33
15
20
10 15
22
13
25 20
30 15
22
aclssses
Figure 3: Recovery of centralities on real-world network. On the x-axis, the number of classes 2 S l I 20 that the algorithms are tasked to find is shown. On the y-axis, the mean short-term cost Cpp, the average deviation from the cluster mean then shown from left to right for PageRank, Eigenvector centrality, Closeness, and Betweenness over 10 trials on the protein dataset.
for varying 2 < l < 20. The mean short-term cost of the assigmments and its standard deviation is reported in Figure 3 Additionally for the PageRank, Eigenvector, Closeness, and Betweeness Centrality, the 1 deviations of each node from the mean cluster value are reported.
Discussion. In Figure 3 all algorithms show similar trend. The costs decrease as the number of clusters increases. The elbow method yields k = 4,., 12 depending on the algorithm. The GIN performs much better than in the previous experiment. This may be due to the fact that there are some high-degree nodes the dataset, that are easy to classify correctly. The converse is true for the fuzzy variant of Approximate WL that implicitly assumes that all clusters should have about the same size. The EV algorithm clusters the nodes well in terms of Eigenvector centrality, which is to be expected. Both struc2vec and rolX achieve the best results for Closeness, which is not captured well by the Approximate WL algorithms. The sudden dip for rolX at & = 12 is due to the fact that rolX cannot be applied when the number of clusters is larger than the number of features. We use k-means to extract the role assignment in this case.
Experiment 3: Approximate EP as Node Embedding. In this section, we diverge a little from the optimization-bu perspective the paper up to this point and showcase the effectiveness the information content of the extracted roles in down-stream learning task. This links our approach to the application- state-of-the-an node embedding techniques. In this experiment, we use an embedding based on our role assignments: For a given adjacency matrix with dominant eigenvector 1/, we compute the output of the Approximate WL algorithm H using average linkage. We also compute the output HEV of the EV-based clustering (section 4.1p. Then the embedding is defined as follows: (AHH)) ",,,,,,,,,,,, (AH),,,,
role evaluation approach of (38) and provides a better comparison with
f(i)
That is, the embedding made up the short- and long-term role assignments and role adjacencies as well as the component of the dominant eigenvector (used for the long-tem optimization). We recreate the experimental design of Ribeiro et al. (36) Section 4.4]. The networks are flight networks where the nodes are airports and the edges are flights between them. In cach graph, the airports are labeled with a class reflecting their activity, which is the target for this task. We then fit a "onells-all" logistic regression and perform a 5-fold cross- cross- validation, tuning hyperparameters for each fold. The results are reported in Table !
Discussion. Table D shows that our embedding and the struc2vec embedding perform best by margin over the other algorithms. Our embedding has slight edge each of the datasets over struc2vec. This shows that the extracted roles provide a good characterization of the roles of the nodes in the networks.
Experiment 4: Graph Embedding. We continue the line of thought of the previous experiment and consider graph-level classification tasks instead. Specifically, we consider a setting with only few learning examples. In this setting, the dimensionality of the embedding is extremely important. Therefore, we analyze which part of the above embedding is most important for the classification task, which leads to the following aggregated embedding:
1
(G) ([C1), -Ckll: IC1
Σ iEC
vz)
|CH|
iEC+

---

Table 1: Performance as a node embedding on a classification task. Mean accuracy in % and standard deviation over a 5-fold cross vross-validation on the airport networks of [36]. ours
struc2vec
rolX
role2vec
node2vec
deg
brazil
90.0 + 8.5
86.4 = 3.3
78.0 + 1.2
70.2 11.1
62.8 = 14.6
69.2 - 0.6
usa
73.8 + 0.3
72.6 + 1.8
62.9 + 0.5
64.6 + 1.5
59.9 + 1.1
53.7 +: 0.0
europe
79.8 + 6.5
76.4 1.5
60.8 + 0.9
48.9 + 2.8
64.3 + 3.9
53.6 + 0.0
Table 2: Few shot graph embedding performance. Mean accuracy in % over 10 runs of the EV embedding, Graph2Vee and the GIN. For each run, we randomly sample 10 data points for training and evaluate with the rest, As a comparison, the GIN+ is trained on 90% of the data points.
ours
G2Vec
GIN
GIN+
AIDS
95.0 = 5.2
79.9 + 4.4
80.0 14.1
97.8 + 1.4
ENZYMES
21.3 1.7
20.3 1.5
1.7
60.3 + 0.7
PROTEINS
66.5
6.4
60.
59.6
75.4 1.3
NCT1
58.5 + 4.0
53.9 1.5
50.0
82.0 + 0.3
MUTAG
81.5 7.7
66.9
77.5 11.1
94.3 = 0.5
The value for k was found by grid search over k E (2,...,40) We benchmark this against the commonly used graph embedding Graph2Vec [32] and the GIN. We use graph classification tasks from the field of bioinformatics ranging from 188 graphs with an average of 18 nodes to 41 10 graphs with an average of 30 nodes. The datasets are taken from [3] and were first used (in order of Table 2) in [37 43 13 46 12). In each task, we only 10 data points to train a 2-layer MLP on the embeddings and 4-layer GIN. Each hidden MLP and GIN layer has 100 nodes. The Graph2 Vec embedding is set to size 16, whereas the GIN receives embedding the attributes of the nodes of the respective task. The GIN is thus informed. We also report the accuracy of a GIN that is trained on 90% of the respective data sets. The results over 10 independent runs reported in Table
Discussion. Experiment 4 has the EV embedding as the overall winner of few-shot algorithms. Our claim here is not that the EV embedding is particularly powerful few-shot learning approach, but that the embedding carries lot structural information. Not only that but robust the sense that few instances are sufficient to train formidable classifier. However, it pales in comparison with the "fully trained" GIN, which performs better on every dataset.
Conclusion
This paper has brought forward rigorous definition of "role" in networks that mirrors the notion of community established before. Based on this definition, we presented the RIP model as a generative model to sample networks with predetermined roles. We also defined quality measures for role assignments and proposed an optimization-base framework for role extraction. Each of the two proposed cost functions measures how well a certain characteristic of the cEP is upheld long-term or short-term behavior. We proposed an algorithm for finding the optimal clustering for the long-term cost function and related the optimization of the other cost function the retrieval of stochastic roles from the RIP model.
Limitations The proposed cost functions are sensitive to the degree of the nodes. In scale-free networks, for example, it can happen that few extremely high-degree nodes are put into singleton clusters and the many remaining low-degree nodes are placed into one large cluster. The issue is somewhat reminiscent of choosing a minimal min-cut when performing community detection, which may result in a single node being cut off from the main graph A remedy akin to using normalized cut may thus be helpful extension to our optinization-base approach. Future work may thus consider correcting for the degree, and further strengthening our theoretic results.
10

---

Acknowledgements
This research has been supported by the DFG RTG 2236 "UnRAVeL" Uncertainty and Randomness in Algorithms, Verification and Logic- and the Ministry of Culture and Science of North Rhine- Westphalia (NRW Rickkehhprogramm))
References
[1] E. Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-635 6531, 2017. 2017.
[2] C. O. Aguilar and B. Gharesifard. Almost equitable partitions and new necessary conditions for network controllability. Autom., 80:25-31, 2017. Utt.httss://ppi httptppps//ppl..mmmmccccc......o org/CorpusID ID: 40989553
[3] N. K. Ahmed, R. A. Rossi, J. B. Lee, L. Willke, R. Zhou, X. Kong, and H. Eldardiry. role2vec: Role-based network embeddings. Proc. DLG KDD, pages 1-7, 2019.
[4] L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 684-697, 2016.
[5] L. Babai and L.. Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium Foundations of Computer Science, pages 39-46. IEEE, 1979.
[6] A. Barabási. Networkscience book datasets. URL http://nttworkscciccccebbok com/
daaources/data... htmml Accessed: 2022-10-01.
[7] F. Bause and N. M. Kriege. Gradual weisfeiler-leman: Slow and steady wins the race. In Learning on Graphs Conference, pages 20-1, PMLR, 2022.
[8] U. Brandes. Network analysis: methodological foundations, volume 3418. Springer Science & Business Media, 2005.
[9] A. Browet. Algorithms for community and role detection in networks. PhD thesis, Catholic University of Louvain, Belgium, 2014.
[10] T. P. Cason. Role extraction in networks. PhD thesis, Catholic University of Louvain, Belgium, 2012.
[11] K. Cooper and M. Barahona. Role-based similarity in directed networks. arXiv preprint 10Xiv:1012.2726, 2010.
[12] A. K. Debnath, R. Lopez de Compadre, G. Debnath, A. Shusterman, and C. Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity, Journal of medicinal chemistry, 34(2):786-797, 1991.
[13] P. D. Dobson and A. J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
[14] M. G. Everett and S. P. Borgatti. Regular equivalence: General theory. Journal of mathematical sociology, 19(1):29-52 1994.
[15] A. Grønlund, K. G. Larsen, A. Mathiasen, J. S. Nielsen, S. Schneider, and M. Song. Fast exact k-means, k-medians and bregman divergence clustering in 1d. arXiv preprint 1eXXv:1701.077 2017.
[16) A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 864, 2016.
[17] K. Henderson, B. Gallagher, T. Eliassi-Rad, H. Tong, L. Akoglu, D. Koutra, L. Li, S. Basu, and C. Faloutsos. Rolx: Role extraction and mining large networks. Technical report, Lawrence Livermore National Lab, Livermore, CA (United States), 201
11

---

[18] K. W. Henderson, B. Gallagher, L. Li, L. Akoglu, T. Eliassi-Ran Raads H. Tong, and C. Faloutsos. It's who you know: graph mining using recursive structural features. In Knowledge Discovery and Data Mining, 2011. httppp::/app...eaatiicceeoooooop
[19] T. Hendrik Schulz, T. Horváth, P. Welke, and S. Wrobel. A generalized weisfeiler-lcman graph kernel. arXiv e-prints, pages arXiv-2101, 2021.
[20] D. Jin, M. Heimann, T. Safavi, M. Wang, W. Lee, L. Snider, and D. Koutra. Smart roles: Inferring professional roles in email networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2923 2923-2933, 2019.
[21] J. Jin, M. Heimann, D. Jin, and D. Koutra. Towards understanding and evaluating structural node embeddings. arXiv preprint arXiv:2101.05730, 2021.
[22] M. Kayali and Suciu. Quasi-stable coloring for graph compression: Approximating max-flow max-flow, linear programs, and centrality. arXiv preprint arXiv:221 /912, 2022.
[23] K. Kersting, M. Mladenov, R. Garnett, and M. Grohe Power iterated color refinement. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
[24] D. Knoke and S. Yang. Social network analysis. Sage Publications, 2019.
[25] X. Liu, Y.-7. J. Chen, J. C. Lui, and K. Avrachenkov. Learning to count: A deep learning framework for graphlet count estimation. Network Science, page 30, 2020.
[26] Lorrain and H. C. White. Structural equivalence of individuals in social networks. The Journal of mathematical sociology. 1(1):49 80, 1971.
[27] M. Mahajan, P. Nimbhorkar, and K. Varadarajan. The planar k-means problem is np-hard. Theoretical Computer Science, 442:13-21 21, 2012.
[28] S. Martini, M. Egerstedt, and A. Bicchi. Controllability amalysis of multi-agent systems using relaxed equitable partitions. International Journal of Systems, Control and Communications, (1-3):100-211 2010.
[29] B. D. McKay and A. Piperno. Practical graph isomorphism, ii Journal of symbolic compulation, 60:94-112, 2014.
[30] C. Morris, M. Ritzert, M. Fey, W. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602 4609, 2019.
[31] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML, 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www.gaaahaaannngg.....
[32] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, and S. Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint 1707.05007 2017.
[33] M. Newman. Networks. Oxford University Press, 2018
[34] L. M. Pecora, Sorrentino, A. M. Hagerstrom, T. E. Murphy, and Roy. Cluster syn- chronization and isolated desynchronization in complex networks with symmetries. Nature communications, 5(1):1-8, 2014.
[35] N. Pržulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2)ee17--e183 2007.
[36] L. F. Ribeiro, P. H. Saverese, and D. R. Figuciredo. struc2vee: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference knowledge discovery and data mining, pages 385-394, 2017.
[37] K. Riesen and Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Join! IAPR International Workshops on Statistical Techniques in Patlern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 287-297. Springer, 2008
12

---

[38] R. A. Rossi and N. K. Ahmed. Role discovery in networks. IEEE Transactions on Knowledge and Data Engineering. 1124)1112-1111, 2014.
[39] R. A. Rossi, R. Zhou, and N. K. Ahmed. Estimation of graphlet counts massive networks.
IEEE Transactions on Neural Networks and Leurning Systems, 30(1):44-57 2018.
[40] R. A. Rossi, D. Jin, S. Kim, N. K. Ahmed, D. Koutra, and J. B. Lee. On proximity and structural rose-based embeddings in networks: Misconceptions, techniques, and applications. ACM Transactions Knowledge Discovery from Data (TKDD), 14(5):1-37, 2020 2020.
[41] R. J. Sánchez-Garcia. Exploiting symmetry in network analysis. Communications Physics, (1):1-15, 2020.
[42] M. T. Schaub, N. O'Clery, Y. N. Billeh, J.-C. Delvenne, R. Lambiotte, and M. Barahona. Graph partitions and cluster synchronization in networks of oscillators. Chaos: An Interdisciplinary Journal of Nonlinear Science, 26(9):094821, 2016.
[43] I. Schomburg. A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, ([ssupp__)):44333 1)::111DD4433333 2004.
[44] I. Stamm, M. Scholkemper, M. Strohmaier, and M. T. Schaub. Neighborhood structure configuration models. Proceedings of the ACM Web Conference 2023, 2022. URL https
//api.semanticet www.antcccccccolaa......m. Dot.aaaarrrrrooroII:DI::: 25228733444
[45] H. Strogatz. Exploring complex networks. Nature, 410(6825):268 276, 2001.
[46] N. Wale, I. A. Watson, and G. Karypis. Comparison descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-375, 2008.
[47] B. Weisfeiler and A. Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
[48] D. R. White and K. P. Reitz. Graph and semigroup homomorphisms on networks of relations. Social Networks, 5(2):193-234, 1983.
[49] X. Wu. Optimal quantization by matrix searching. Journal of algorithms, 12(4):663-673, 1991.
[50] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: /8100000/, 2018.
[51] Y. Yuan, G.-B. Stan, L. Shi, M. Barahona, and J. Goncalves. Decentralised minimum-time consensus, Automatica, 19(5):1227- 2013.
13

---

Appendix
A Example of Communities vs. Roles
Communities
3 Communities
Figure A1: Toy example showing two networks and their role/community structure. The left has two exact roles but how many communities it has is not clear. The right has perfect communities, but only single role.
B Example of Isomorphic Nodes that receive different role
Example graphs showing undesirable properties the optimizer eq. (6 Nodes and 2 are in the same cEP class; they even isomorphic. However, the minimizer of eq. (6) puts them into different classes. The partition minimizing eq. (6) as given by the right yields a score 0.707, whereas the best partition that respects the cEP yields 0.816.
Figure A2:
C Proof of theorem 4.1
Theorem 4.1:
Let H be the indicator matrices H {0, 1j s.l. H1, = 1 Let A Raxx be an adjacency matrix. Assume the dominant eigenvector to the eigenvalue p(A) of A is umique. Using the E norm in eq. (6, the optimizer
OPT arg min lim T (A, H)
HEH d-+00
can be computed in O(a + nk + n log(n)),, where a is the time needed to compute the dominant eigenvector of A.
Proof. Consider the long-tern bong-term cost function (eq.
7
CA,EP(A,H)
p(A) IA -DD A'lll
[I TT ((A) A' A!Hll
lim d000 [(Ih HDDDDHHH Jwo' H!|
14

---

We arrive at a formulation akin to the k-means cost function. However, we H is in general not independent of the clustering, as would be the case the usual formulation of k-means. This can be used advantageously by rewriting the above matrix equation element-wise:
W (HHH)
Σ LEC(W))
uilo un( H1,ر
(w()))
7
Σ
Iw: [C(w:)) (EC(
w)) (H)))
It is possible to completely draw out the constant factor of Σj v H H E, since the row sums of are and the components tú 2 0 are non-negative.
H (ww [C(ww))
wi)l
IEC(w.
const
(w:y
wi)l
[[(w)] LEC(w,)
We end up formulation equivalent clustering w into clusters using k-means. We can now notice that ur only 1-dimensional and as such the k-means objective can be optimized in On (og(n) nk) 49 [5].
D Proof of theorem 4.2
Theorem 4.2: Optimizing the short-term cost is Na-hard.
Proof. We reduce from the PLANAR-K MAAAARKKMMANNN problem, which is shown to be NP-hard [27]. In PLANAR-K-MA K-AANS,
given set {x 91) .... (Ins }n)] of points in the plane and number and a cost c. The problem is to find partition of the points into & clusters such that the cost the partition is at most where the cost of partition is the sum of the squared distances of each point to the center of its cluster. We now formulate the decision variant of optimizing the short-term cost which we show is NP-hard.
Definition D.1 (K-AEP). Let G (V, be graph, h E N and E R. K-AEP is then the problem of deciding whether there exists a partition of the nodes V into h clusters such that the short-term cost EP (eq. (7) using the squared L2 norm is at most c.
Let W W(X, Y) be the sum of the weights of all edges between X, Y C V. Additionally, for given partition indicator matrix H, let C2 be the set of nodes v s.t. Hy,5 = 1. For the following proof, the equivalent definition of the short-term cost function (eq. 6 using the squared L2 norm is more convenient:
(e = ΣΣΣ (W(L)).))) 3 VECA
|c,l W(C,,,,))
We now show that K-AEP is NP-hard by reduction from PLANAR-K-MEANS.
Construction, Given [ y1).... (In, yn)} of n points in the plane and a number k' and cost d' construct the following graph: We shift the given points by min1g[[]] I; in their z-coordinate and by min Y: in their y-coordinate. This makes them non-negative, but does not change the problem. Let D 1 > x? + y.- Notice that an upper bound on the cost of the k-means partition. To start, let V {a, b). Add self-loops of weight 3/) and of weight 6D to b. For each point (xi, 9:), add a node m. to V and add edges m,a of weight x; and m2á of weight yı to E.
G EV, k' + 2, c' are now the inputs K-AEP.
15

---

Correctness. We now prove that the PLANAR-KE K- K-MEANS instance has solution if and only if K-AEP has a solution. Assume that PLANAR-K K- MEANS has solution S (Si.... .... )%) that has cost c² I c. Then the solution we construct for K-AEP is S = (Si, Sk {a], (6}), where my E Sj = (ri, E S.- The cost of this solution is:
c ΣΣΣ (W(f)),
|S| (,),
Since a and are in singleton clusters, their outgoing edges do not differ from the cluster average and so incur cost. The remaining edges either go from V Vaaa, by to or from VM, bj to b. So, the sum reduces to:
c+ = ΣV Σ
(w(v,,) a)
(VS:,aa))) + (w(r,b)
S. W(S,, (01))))
SS
VES;
Since (S,(S.) ss. W(S,, {a}) is the average weight of the edges from St to a, and these edges have weight according to the x coordinate the point they were constructed from, Uz (S.) is equal to the mean coordinate within the cluster Sy. This concludes the proof of this direction,
Σ Σ
(x) (S))) + (y 1y(()))² = c' S
STES' (ZL,))ES;
For the other direction, assume we are given a solution S = (S ...,, Sk+2) to K-AEP with cost ct S.. We distinguish two cases:
Case 1: Bi s.f. S 2 {a} or 2 (b}. Assume that S; 2 {a], if also E S: then the cost is least the difference of the two self-loops:
W(()), SSA
W(S..
WES.
max W(fu), - W(fu), 2 u.v.S,
1V
2
(w((b, b) - W([a), Si))
( (6D (BD0-11) = D2 DD
instead, some my E S₁, then the cost is at least the difference of the self-loop to a and the edge from m, to a:
W(S 2
Σ W(ft},
[Sp
DES;
(wra, W([m))),
[ (3D D) = = D2 D
Thus ct 2 D is so large that any clustering of the points has at most cost 2 D thus a solution to instance exists. The case where S; 2 {b} is analogous.
the PLANAR-K-MER
Case 2: Case I doesn't 't hold. In this case, we have (S,, ..., Sk. {a}, (b)) which yields
clustering S' = -S .... S. for the PLANAR-K- K-MANS, where m, E S₁ + (Ir, Sy. This
instance has cost c c" S.
O
16

---

E Proof of theorem 4.3
Theorem 4.3: Let be sampled from the RIP model with parameters p R, C, N
N, Prote E R Let Hole: ... Hole be the indicator matrices of each iteration when performing the exact WL algorithm on E] Let 5= minoge gT mineyj [1 rll - (N mil 1----- Using
average linkage in algorithm 7 in the clustering step and assumiing the former correctly infers k,
9W-1((9 11181/99999
28
where W is the Lambert W function, then with probability at least qE Algorithm finds the correct role assignment using average linkage for clustering.
Proof. Consider the adjacency matrix AB of simple binomial random graph of size n i.e. single block of the SBM. Let 5 < 3. Using the Chernoff bound for binomial random variables, we have that the degree single node i is within the ball of size 5* with probability:
Pr (1 1);
(E[((A D)ll 2 8 n) S 2e 2n(6*)²
The probability that all nodes fall in close proximity to the expectation, is then simply:
Pr (1IA
B[A 2 8* n) - 11 2c 22c=22(6))))
Finally, in the SBM setting, we have k-2 such blocks and the probability that none the nodes are far away from the expectation in any of these blocks is:
AHH
(T) role
E B[AHH (T) role
S <1122e-2 2m nk?
Pr
7
We upper bound this by its first-order Taylor approximation:
(1 2e
20(8")²)
Sps1 - -2nk2 (22((6") 22²
(p
1)(8))2
S 5-2n( -220188
12
(p 1)(8*)2
W-1
2 2
k²
9W ((p 1) 1)82//900 /9h2)
In
282
Thus with probability at least the maximum deviation from the expected mean is 8*, which is why we simply assume this be the case going forward, i.e.:
8
max 7 [.J
Consider the LI distance of nodes inside the same cluster: This is at most k4. For nodes that belong to different clusters, this will be at least k(6 - 28*) kg- Therefore, the average linkage will combine all nodes belonging to the same role before it links nodes that belong to different roles. O
Corollary E.1. Let (11) (o) be independent samples of the RIP model with the same role assignment (Pimle must not necessarily be the same). Assuming the prerequisites of theorem 4.3 for A Σe 1=1 A1)) except eq. If
DWWi(lg-1)68
2ng²
Then with probability least q: Algorithm Sinihhhm@nnd. finds the correct role assignment using average linkage for clustering.
17


Reviews:
[{"review_id": "wQixC5Y3Gc", "reviewer": "Reviewer_ZAin", "summary": "The authors propose the notion of equitable partitions from graph isomorphism literature in order to partition the nodes of a network according to their structural roles. They study two optimization problems for approximately recovering such equitable partitions. Analogous to the SBM model, the authors devise the RIP (role-infused partition) stochastic model and validate their findings on this model. ", "questions": "1) On the considered molecular datasets, does the approximate number of equitable partitions differ (the parameter \"k\" \\in {2,20}) differ significantly from the actual number of equitable partitions, on an average? Since the average number of nodes is 30, and since I would expect most graphs to have discrete equitable partitions (i.e. one node per class), it will be interesting to know if the optimal values of k were indeed small (say 2-6).", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well-written. The proposed cost functions for computing approximate equitable partitions are very well-motivated and natural. Approximate versions of the Weisfeiler-Leman algorithm is an important question which deserves much study. The proposed RIP model is a very satisfcatory benchmark for role discovery.", "weaknesses": "The experimental work is inadequate in order to understand the impact of the proposed formalism to real-world data (Section 5, Experiment 3). The considered datasets are too few, specialized and small-sized in order to deduce that approximate equitable partitions (and approximate Weisfeiler-Leman) is at the core of role discovery.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ZAin, \n\nThank you for your review.\n\nRegarding your question, one has to keep in mind that we are concerned with finding \"global\" roles. That is, we consider the whole dataset as one graph with multiple connected components. On the proteins dataset, there are $1278$ classes of the *exact* cEP. This would be the optimal value for k since it would result in a cost of $0$ - and every $k<1278$ has an optimal cost $c>0$. \nIf we restrict ourselves to $k \\in \\{ 2,20 \\}$ (as we did for the experiments), then we cannot make a statement about the optimal value of the cost function. The problem does not decompose into finding the best approximate EP for each connected component individually. And as the problem is NP-hard we have no hope in brute forcing it for this size of the graph.\n\nRegarding our experiments, please also take a look at the general author response. \n\nThank you once more for your review. \n\nBest, \nthe authors"}, {"review_id": "K5ahqR5UFP", "reviewer": "Reviewer_WiNY", "summary": "The paper considers a relaxed definition of the coarsest equitable partition (CEP), which equals the final partition of Weisfeiler-Leman or the color refinement algorithm in the original version. The authors allow to specify the number of cells of the partition and derive a related optimization problem. From this, an algorithm for role discovery is derived, outperforming techniques such as role2vec on real-world graphs.", "questions": "* Could you explain whether Algorithm 1 can recover the cEP for a suitable choice of the parameter $k$?", "limitations": "Limitations are sufficiently discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The concept of structural roles is closely related to the Weisfeiler-Leman algorithm and fundamental for graph learning.\n* The relaxation of the final WL partition with a fixed number of cells is novel.\n* The RIP model for graph generation is innovative.", "weaknesses": "* Algorithm 1 is not analyzed sufficiently. It would be interesting to have approximation guarantees. Moreover, it would be nice to investigate the case where $k$ equals the number of cells in the cEP. I believe that the current version would not guarantee that the cEP is found since the cluster method obtains only $X$ as an argument neglecting $H$, which should be required to guarantee this. Is this correct?\n* Several other methods compute relaxed WL partitions without allowing to specify $k$ and are discussed in section 2.1. These could also be used in the experimental comparison to assess the advantages of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WiNy, \n\nThank your for your review.\n\nRegarding your question, the results of Algorithm 1 heavily depend on the clustering algorithm used. If one was to use a clustering algorithm that does not assign two data points with the same value to different clusters, then Algorithm 1 would output the cEP. \nFor example, assume the clustering algorithm used returns the same cluster for data points with the same value and different clusters for data points with different values (it may return as many clusters as it wants). Then one recovers the adapted Weisfeiler-Lehman algorithm that Morris et al. [1] used in the proof of Theorem 2. This algorithm uses only the multiset of neighboring colors (and not the previous color of the node) but is equivalent to the \"full\" WL algorithm. In the same way it is sufficient to only cluster X without access to H and still arrive at the cEP. \n\nIndeed, you can think of it this way (although this was out of scope for this particular paper): The columns of the indicator matrix H_EP of the cEP are a basis of a subspace that is invariant to multiplication with A and the starting vector (all-ones) is an element of this subspace. Thus step 4 can never leave this subspace and if we assume that the clustering step (5) also does not break this, then we never leave the subspace. Once we cannot divide the clusters any further, we have reached the cEP. \n\nWeaknesses:\nGuarantees for Algorithm 1 are extremely dependent on the clustering algorithm used. Most clustering algorithms offer no guarantees on performance which makes it exceedingly hard to provide guarantees for Algorithm 1. \nWe even have hardness of approximation - as is the case for the closely related kmeans. Indeed, combining our reduction from k-means with the hardness of approximation of Pranjal et al. [2] results in a similar \"hardness of approximation\" statement for the short-term cost. However, in our reduction the dimension is encoded through additional 'predetermined' clusters and their reduction results in a very high dimension of the vectors. Thus, this holds only for large values of $k$ whereas we are mostly interested in small values of $k$. \n\nThe other approaches specified in section 2.1 all do not permit to set a specific number of clusters - the main difference of our approach to  [3] is precisely this. They specify an $\\epsilon$ deviation that the final clustering must uphold and then aim to find the coarsest partition (which is NP-hard also). However, the number of classes is only indirectly determined by this. It may be that there exists no $\\epsilon'$ such that the number of clusters found is exactly $k$. So even searching along the values of $\\epsilon'$ would not mean that we can get exactly $k$ roles. Regarding our cost function, it will always be beneficial to have more rather than fewer clusters. This is why comparing the two approaches is extremely difficult.\n\n\nThanks again for your review!\n\nBest, \nthe authors\n\n[1] Morris, Christopher, et al. \"Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks.\" arXiv preprint arXiv:1810.02244 (2018).\n\n[2] (Awasthi, Pranjal, et al. \"The hardness of approximation of euclidean k-means.\" arXiv preprint arXiv:1502.03316 (2015).)\n\n[3] (M. Kayali and D. Suciu. Quasi-stable coloring for graph compression: Approximating max-flow, linear programs, and centrality. arXiv preprint arXiv:2211.11912, 2022.)"}, {"review_id": "txEscf2xXf", "reviewer": "Reviewer_nMtV", "summary": "This paper presents a novel perspective on the problem of node role extraction in complex networks, highlighting its distinctions from community detection. The authors propose a definition of node roles and introduce two optimization problems based on graph-isomorphism tests, the Weisfeiler-Leman algorithm, and equitable partitions. Theoretical guarantees are provided, and the approach is validated using a newly introduced \"role-infused partition benchmark\" that allows for stochastic assignment of different roles to nodes in sampled networks. The findings contribute to network analysis, graph mining, and the development of reduced order models for dynamical processes on networks.", "questions": "Most of my questions are related to the experiments:\n- There are some relevant baselines that are not compared, for example, MMSB [1] and RIDRs [2]. The first one you can also discuss the relation with your proposed method, e.g., if it is possible to extend the proposed method to soft role assignment like MMSB. The second method is also based on equitable partitions.\n\n- There are some commonly used datasets that can be used for evaluating role discovery, for example, these datasets used in [3].\n\n- In previous role discovery studies, different downstream tasks have been selected to show the effectiveness of the discovered roles, e.g., node classification and link prediction. For example, these tasks in RolX [4] and struc2vec [3]. Also, there is no evaluation of the discovered roles. For example, in RolX, the quantitative evaluation using clustering metric has been used.\n\n- Efficiency issue. Although the proposed method is technically sound, a question is how efficient the proposed method is, e.g., how large a graph this method can handle.\n\n[1] Airoldi E M, Blei D, Fienberg S, et al. Mixed membership stochastic blockmodels[J]. Advances in neural information processing systems, 2008, 21.\n\n[2] Gupte P V, Ravindran B, Parthasarathy S. Role discovery in graphs using global features: Algorithms, applications and a novel evaluation strategy[C]//2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 2017: 771-782.\n\n[3] Henderson K, Gallagher B, Eliassi-Rad T, et al. Rolx: structural role extraction & mining in large graphs[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. 2012: 1231-1239.\n\n[4] Ribeiro L F R, Saverese P H P, Figueiredo D R. struc2vec: Learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017: 385-394.\n\n==============================================\n\nAfter the rebuttal, I increased my overall rating.\n", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The research topic, role discovery in graphs, is very important and is worth studying, especially compared to the community detection problem, role discovery is also important but lacks attention.\n\n- The design of the model based on equitable partitions is technically sound and theoretically guaranteed.\n\n- Experimental results on several datasets from different perspectives show the effectiveness of the proposed method.", "weaknesses": "- Baseline selection. Some relevant and/or important baselines have not been compared.\n\n- Downstream tasks. The proposed method is not tested on widely used downstream tasks to show its effectiveness.\n\n- Dataset. There are some more widely used datasets for role discovery that are not used in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer WiNy, \n\nThank your for your review.\n\nRegarding your questions:\n1. MMSBM and RID$\\epsilon$R. While the comparison with RIDR does seem interesting, we were unable to find an implementation for neither RIDR nor inference of the mixed membership SBM. If time permits, we would like to also include RIDR in our comparison. Regarding the MMSBM, the soft assignments do not change the fact, that the MMSBM finds communities. Suppose in the RIP model, $p=0, c = k > 2, \\Omega_{role} > 0$. Then, nodes only have edges inside the clusters and all \"outside edges\" are not there. For $n \\rightarrow \\infty$, the likelihood of placing two nodes from the same ground-truth community in distinct blocks of the MMSBM (even only fractionally) goes toward $0$, thus the MMSBM will recover the communities and not the roles. \n\n2. We have conducted new experiments on the proposed datasets, please refer to the general rebuttal and attached pdf.\n\n3. We would have liked to also encompass the RolX datasets in our experiment, sadly only the raw data is linked in the paper, which they modified (added the targets) for their experiments. However, the performance should be similar to that presented in struc2vec.\n\n4. Our proposed methods are exceedingly efficient. The optimization algorithm for the long-term cost function (EV algorithm) uses $O(nk + n\\log(n))$ time. The time needed by the approximate WL algorithm is largely dominated by the clustering used. Other than that, the algorithm only consists of $k$ matrix-vector products resulting in a complexity of $O(i*(E*k+C))$, where $i$ is the number of iterations, $E$ the number of edges, and $C$ the time for clustering. \nWe have also conducted an experiment of real world time consumption in the attached pdf of the general rebuttal.\n\nOnce again, thank you for your review.\n\nBest, \nthe authors"}, {"review_id": "AfAM6DaMHo", "reviewer": "Reviewer_rRxj", "summary": "The paper offers a new perspective on the problem of role extraction while defining node roles based on the ideas of equitable partitions and and graph-isomorphism tests, the Weisfeiler-Leman algorithm. The paper studies two associated optimization problems (cost functions) inspired by graph isomorphism testing and provides theoretical guarantees for their solutions.  To validate the approach, a novel \"role-infused partition benchmark\" is introduced, enabling the generation of networks where nodes possess different roles in a stochastic manner.", "questions": "(-) It is mentioned that Equitable partitions imply an upper bound on the expressivity of Graph Neural Networks while citing references [26] and [43]. There is nothing of that sort in these papers. Could you point out where such results are mentioned in the said references. \n\n(-) As coarsest equitable partition is an important concept for the paper, an example to illustrate this concept or a proper reference to another paper is vital and missing in the draft.\n\n(-)  As mentioned in the \"weakness\", can you explain more rigorously the motivation for using equitable partitions for node role discovery.\n\n(-)  In Theorem 3, what is the interpretation of the parameter $\\delta$ and what is the computational complexity to calculate it?\n\n(A minor comment) There are minor grammatical errors, e.g.,\n\n-  \"Thus, from any node $v$ within in the same class ...\" (in is not needed).\n\n- \"This also allows for Gradient Descent approaches like e.g. GNNs.\" (like and e.g., are used simultaneously).\n\n", "limitations": "The limitations and possibly approaches to tackle these limitations are presented in the paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "(+) The paper offers a new perspective on node role extraction, focusing on equitable partitions and providing a principled stochastic notion of node roles. This approach adds to the existing methods in the field and offers a new way to define and quantify node roles in complex networks.\n\n(+) The paper presents a quantitative definition of node roles based on equitable partitions, allowing for the numerical measurement of deviation from an exact equivalence. This provides a more nuanced understanding of node roles compared to traditional definitions.\n\n(+) The technical aspects of the paper are thorough and detailed. Also, the technical details aeem to be correct. \n\n(+) Numerical experiments show the effectiveness and superiority of the proposed method over a graph neural network, GIN, for three different tasks. ", "weaknesses": "(-) While the paper briefly mentions different categories of node role extraction approaches (graphlet-based, walk-based, and matrix-factorization-based), it does not provide a detailed comparison or analysis of how the proposed equitable partitions approach compares to these existing methods. A more rigorous comparative analysis, including performance metrics and evaluation on benchmark datasets, would strengthen the paper's contribution and demonstrate the advantages of the proposed approach.\n\n(-)  The idea of Equitable partitions for node role discovery is interesting. However, the details regarding \"why this approach\" makes sense is missing. There can be other ways too? Why this method should work? At a conceptual level, a more rigorous explanation related to the definition of roles based on equitable partition is missing. I think this is crucially important. In other words, the paper focuses on providing details of \"designing\" and approach based on EP, while leaving details of \"why this is appropriate\"\n\n(-) A more thorough literature review might be needed. For instance, the following paper provides a nice simple algorithm for computing equitable partitions. (I am not sure it is better or worse; however it might be handy to have a look at it.)\n    \n- Zhang et al., \"Upper and Lower Bounds for Controllable Subspaces of Networks of Diffusively Coupled Agents,\" IEEE Transactions on Automatic control, 2014.\n\nAlso, there is some recent work on counting subgraphs (that may define node roles based on the structural attributes of the graph), for instance, \n\n- Hassan et al., \"Computing Graph Descriptors on Edge Streams.\" ACM Transactions on Knowledge Discovery from Data, 2023.\n\n(-) The paper introduces a family of cost functions to assess the quality of a role partitioning. However, it does not thoroughly discuss the selection, design, or properties of these cost functions. Providing a more in-depth exploration and analysis of the different cost functions, their properties, and how they relate to the problem of node role extraction would enhance the technical understanding of the proposed approach.\n\n(-) It is unclear how the ground truth for the sampled adjacency matrices is computed  in Experiment 1 of Section 5. Moreover, GIN is a relatively old graph neural network. There are recent methods that show better results on several downstream tasks and could have been considered for baseline comparisons. Some of these works include the work of Bouritsas et al, and Ramp\\'a\\v{s}ek et al, below.\n\n- Bouritsas et al., \"Improving graph neural network expressivity via subgraph isomorphism counting,\" IEEE Transactions on Pattern Analysis and Machine Intelligence. 2022 Feb 24;45(1):657-68.\n\n- Ramp\\'a\\v{s}ek, et al., \"Recipe for a general, powerful, scalable graph transformer,\" Advances in Neural Information Processing Systems. 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer rRxj, \n\nThank your for your review.\n\nRegarding your questions:\n1. Expressivity of GNNs: The cited references do, in fact, prove the statement. The contraposition of Lemma 2 in (Xu et. al [43]) yields \"If the WL test decides G_1 and G_2 are isomorphic, then any GNN maps G_1 and G_2 to the same embedding.\". (Morris et al. [26]) Thm 1 is more specific stating that the color $c^{(t)}(v)$ assigned to node $v$ at iteration $t$ of the WL algorithm encodes \"more\" information than the features $f^{(t)}(v)$ of a node in that: \"$c^{(t)}(v) = c^{(t)}(u) \\implies f^{(t)}(v) = f^{(t)}(u)$\". By the refinement property of WL, we have that the last iteration $T$ holds the \"most information\" and hence $c^{(T)}(v) = c^{(T)}(u) \\implies f^{(t)}(v) = f^{(t)}(u) \\forall t \\leq T$.\n\n2. References to ceP: We provide references to multiple papers that use equitable partitions in multiple ways: Graph isomorphism testing [3,4,25,41] reduction of complex systems [24,30,36,37,44] and Graph Neural Networks [26,43]. The notion of equitable partitions emerged somewhat independently in many different parts of research such as social sciences in the study of social networks, electrical engineering as a means of model order reduction, and theoretical computer science in the form of the WL test. The idea is the same, but the formalisms vary quite substantially from the color perspective of the WL test to the matrix equation adopted by the model order reduction community (and us in this paper).\n\n3. Motivation for using EPs: We motivate the use of the cEP for role extraction in section 2.1 as a means of model order reduction using the quotient graph and in section 4 by highlighting that even graph neural networks cannot extract more structural information from a graph than the cEP. We would of course like to go even further into the motivation, and will include it if space permits: The WL colors (and by extension the cEP) carry an immense amount of information about the structure of the network surrounding a node. One can think of it as iteratively building a tree of possible paths from the start node to neighboring nodes. At the first iteration, the color $c^{(t)}(v)$ encodes the degree of $v$ in the graph. At the second iteration, it encodes the number of nodes with a certain degree that are adjacent to $v$ and so on. This tree of possible paths is profoundly important for processes that move over the edges of a network such as dynamical systems and GNNs, and even simple ones like PageRank and other centrality measures. However, the colors are often too descriptive which has recently sparked a series of investigations on how to meaningfully simplify this immense descriptive power [6,16,19] (and this paper).\n\n4. Parameter $\\delta$: The parameter $\\delta$ in Theorem 3 is a parameter that determines how hard it is to recover a given SBM. This bares some resemblance to standard SBM inference techniques, that consider a threshold for which exact recovery is possible (Abbe, Emmanuel, and Colin Sandon. \"Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery.\" 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015). Intuitively, the roles (or blocks in the original SBM) may not be too similar, otherwise it takes many samples to see a significant difference. $\\delta$ describes the minimal difference of the roles in the ground truth model. $\\delta$ is easy to compute given the ground truth model. One simply computes the WL colors ($O(n^2*log(n))$) and computes the minimal difference in intermediate roles ($O(n^2)$).\n\n5. Thanks for pointing out the typos! At some point one stops seeing them. \n\nWeaknesses:\n1. Literature review: The notion of **almost** equitable partitions partitions in (Zhang et al., \"Upper and Lower Bounds for Controllable Subspaces of Networks of Diffusively Coupled Agents,\" IEEE Transactions on Automatic control, 2014.) is sometimes also called **externally** equitable partition, because it only takes into account edges between distinct classes of the partition. On those, however, it is an *exactly* externally equitable partition. It is often useful as it gives an upperbound on the controllability of a system similar to the upper bound that is given by exactly equitable partitions for GNNs. However, this does not coincide with the notion presented in this paper: Contrary to the latter notion, our **approximately** equitable partitions do not have to be exact, but may only consist of $k$ classes.\n\n2. GIN as baseline. While the GIN is relatively old, it is still often used as a baseline - and is provably among the most expressive message passing GNNs there are [43]. Due to this fact, it is more than sufficient for our purpose here. GNNs like the one you proposed would also \"break\" the WL upper bound, which improves expressiveness but isn't desirable in this scenario - as discussed in the appendix.\n\nThanks again for your review. \n\nBest, \nthe authors"}]

Author rebuttal:
Dear Reviewers, 

Thank you all for your reviews. 

A common theme in your reviews was a need to broaden the experimental part of the paper. We have thus extended our experiments by two experiments proposed by Reviewer nMtV and originally conducted by [1]. In particular, this includes the downstream task of classifying airports due to their throughput of passengers into 4 categories - the 4 roles.

Before going into detail we would like to note a few things: First, it is extremely hard to find data on which roles can be evaluated down-stream. In most role extraction approaches (struc2vec, rolX), the target classifications are constructed either from metadata or from some characteristic of the graph which is then assumed to correspond to the role. However, it is not easy to check if this assumption is correct. This is one of our main contributions: Giving a rigorous definition of "role" and a benchmark generative model on which to assess these roles. Our other main contribution is providing multiple inference algorithms and ways to assess the "goodness" of such a role assignment. 

While it was not our main goal in this paper to provide an embedding that can be used on some downstream task, we performed two new experiments, based on your feedback. Toward this, we used an embedding based on our role assignment:
For a given adjacency matrix $A$ with dominant eigenvector $\nu$, we compute the output of the approximate WL algorithm $H$ using average linkage. We also compute the output $H_{EV}$ of the EV algorithm. As the embedding of each node, we use: 
$$emb(i) = (H[i,:], (H_{EV})[i,:], (AH)[i,:], (AH_{EV})[i,:], \nu[i])$$
In other words, we embed the nodes with the short-term and long-term role assignment, the adjacencies with other roles and the component of the eigenvector corresponding to that node. For this dataset, we used $k=30$ roles on all datasets. We set $k$ by hand due to time, but want to automatically tune it for the final paper to improve performance. In all other regards, we copied the experimental design of [1], that is, we fit a "one vs all" logistic regression on the embeddings and perform a 5-fold crossvalidation tuning hyperparameters on every fold independently.
The results can be seen in the attached pdf.

We look forward to the discussion!

Best, 
the authors

[1] Ribeiro, Leonardo FR, Pedro HP Saverese, and Daniel R. Figueiredo. "struc2vec: Learning node representations from structural identity." Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 2017.

Meta-review: The reviewers raised a few concerns, including the experimental work and algorithm analysis, etc., on this paper. The authors addressed some concerns during the rebuttal/discussion phase, and finally the reviewers were relatively positive about the work.
After reading the reviews and discussions, and also taking the scores given into account, I am recommending this paper be accepted as a poster.
Decision: Accept (poster)