DIGRAC: Digraph Clustering Based on Flow Imbalance
Authors: Yixuan He
Gesine Reinert
Mihai Cucuringu
Venue: ICLR 2022 Submitted (2022)
Keywords: flow imbalance
directed networks
graph neural networks
clustering
directed stochastic block models

Abstract: Node clustering is a powerful tool in the analysis of networks.  We introduce a graph neural network framework to obtain node embeddings for directed networks in a self-supervised manner, including a novel probabilistic imbalance loss, which can be used for network clustering.  Here, we propose directed flow imbalance measures, which are tightly related to directionality, to reveal clusters in the network even when there is no density difference between clusters. In contrast to standard approaches in the literature, in this paper, directionality is not treated as a nuisance, but rather contains the main signal. DIGRAC optimizes directed flow imbalance for clustering without requiring label supervision, unlike existing GNN methods, and can naturally incorporate node features,  unlike existing spectral methods. Experimental results on synthetic data, in the form of directed stochastic block models, and real-world data at different scales, demonstrate that our method, based on flow imbalance, attains state-of-the-art results on directed graph clustering, for a wide range of noise and sparsity levels and graph structures and topologies.

Under review as a conference paper at ICLR 2022
DIGRAC: DIGRAPH CLUSTERING BASED ON FLOW IMBALANCE
Anonymous authors Paper under double-blind review
ABSTRACT
Node clustering is a powerful tool in the analysis of networks. We introduce a graph neural network framework to obtain node embeddings for directed networks in a self-supervised manner, including novel probabilistic imbalance loss, which can be used for network clustering. Here, we propose directed flow imbalance measures, which are tightly related directionality, reveal clusters in the network even when there is no density difference between clusters. In contrast to standard approaches in the literature, in this paper, directionality is not treated as a nuisance, but rather contains the main signal. DIGRAC optimizes directed flow imbalance for clustering without requiring label supervision, unlike existing GNN methods, and can naturally incorporate node features, unlike existing spectral methods. Experimental results on synthetic data, in the form of directed stochastic block models, and real-world data at different scales, demonstrate that method, based on flow imbalance, attains state-of-the-ar results on directed graph clustering, for wide range of noise and sparsity levels and graph structures and topologies.
INTRODUCTION
Revealing underlying community structure of directed networks (digraphs) is an important problem in many application domains (Malliaros & Vazirgiannis 2013). such as detecting influential social groups (Bovet& & Grindrod 2020) and analyzing migration patterns (Perry 2003); node clustering in digraphs can be used for this community detection task (Palmer & Zheng (021). While most existing methods that could be applied to directed clustering use local edge densities as main signal and directionality as additional signal, we argue that even in the absence of any edge density differences,
directionality can play a vital role in directed clustering as it can reveal latent properties of network flows. Therefore, instead of finding relatively dense groups of nodes in digraphs which have relatively small amount of flow between the groups, as in (Girvan & Newman 2002 Newman 2006 Leskovec et al. 2008 Leicht & Newman 2008 Chen & Baker 2021 Dia et al. (017). )) our main goal is to recover clusters with strong and imbalanced flow flow among them, in the spirit of (Cucuringu et al.
2020a Laenen & Sun 2020), where directionality (i.e, edge orientation) is the main signal.
In contrast to standard approaches focusing on edge density, here edge directionality not a nuisance but the main piece of information to uncover the latent structure. The underlying intuition is that homogeneous clusters of nodes form meta-nodes in meta- graaag with the meta-graph directing the flow between clusters; directed core-periphan peripheryy structure is such an example (Elliott et al. 2020). Figure a) is an example of flow imbalance between two clusters, here on an unweighted network for simplicity: while 75% of the edges flow from the Transient cluster to the Sink cluster, only 25% flow in the other direction. As a weal-world example, Figure [bb shows the strongest flow imbalances between clusters network of US migration flow (Perry 2003); most edges flow from the red cluster (label 1) to the blue one (label 2). Figures [-cd) show examples on synthetic meta-graph.
While most competitive state-of -fh methods proposed for node clustering digraphs mainly rely on edge density and overlook the role of directionality, those that do lay emphasis on directionality, usually by incorporating cut imbalance among clusters, are usually spectral methods, for which incorporating features is non-trivial, or GNN methods that require labeling information. In general, community detection methods for networks are not able to find communities in networks in which the sole structure lies in the directionality of edges. An exception is InfoMap (Rosvall & Bergstrom 2008), a method for community detection in networks which uses directed random walks; however, still relies some edge density information within clusters.

---

Under review as a conference paper at ICLR 2022
0
1
0.6
mo
5111 dister
dusee
2
0.4
3
0.2
(a) Flow imbalance example: most of the edges flow from Transient to Sink.
(h) Strongest imbalanced flow Migration data, along with geographic locations of the counties and state boundaries (in black).
0.0
(d) Meta-graph adjacency matrix F.
(c) Meta-graph.
Figure 1: Visualization of cut flow imbalance and grethh (a) 75% of edges flow from Transient to Sink, while 25% of edges flow in the opposite direction; (b) top pair imbalanced flow on Migration data (Perry 2003): most edges flow from red (1) to blue (2); (c) & (d) are for a Directed Stochastic Block Model with a cycle meta-graph with ambient nodes, for a total of 5 clusters. 75% of the edges flow in direction 0 + 1 + 2 + 3 + O. while 25% flow in the opposite direction. Cluster 4 is the ambient cluster. In (c). dashed lines indicate flows with random equally likely directions; these flows do not exist in the meta- eeta-graph adjacency matrix F. For (d), the lighter the color, the stronger the flow.
In this paper, we introduce a graph neural network (GNN) framework, denoted DIGRAC, to obtain node embeddings for clustering digraphs (potentially weighted, possibly with self-loops, but no multiple edges). In a self-supervised manner, a novel probabilistic imbalance loss is proposed to act on the digraph induced by all training nodes. The global imbalance score, one minus whom is the sulf-supe loss function, is aggregated from pairwise normalized cut imbalances. The method is end-to-end in combining embedding generation and clustering without intermediate step. To the best of our knowledge, this is the first GNN method that derives node embeddings for digraphs that directly maximizes flow imbalance between pairs of clusters. For the implementation of the framework, we devise a directed mixed path aggregation scheme that we abbreviate DIMPA, which is simple and effective. Other aggregation schemes which detect direction information could be used. With an emphasis on the use of direction based flow imbalance objective, experimental results on synthetic data and real-world data different scales demonstrate that our method can achieve state-of the performance for wide range of network densities and topologies. Compared to its competitors, for synthetic data, our method achieves superior performance (with respect to the Adjusted Rand Index (ARI) (Hubert & Arabie 1985)); for real-world data, our method clearly outperforms them, using imbalance scores as outcome success measures.
DIGRAC's main novelty is the ability to cluster based on irrection-based flow imbalance, instead of using classical criteria such as maximizing relative densities within clusters. Compared with prior methods that focus on directionality, DIGRAC can easily consider node features and also does not require known labels. DIGRAC complements existing approaches in various aspects: (1) Our results show that DIGRAC complements classical community detection by detecting alternative patterns in the data, such as meta-graph structures, which are otherwise not detectable by existing methods. This aspect of detecting novel structures in directed graphs has also been emphasized in (Cucuringu et al., 2020a). (2) DIGRAC complements existing spectral methods, through the possibility of including exogenous information, in the form of node-level features or labels, thus borrowing their strength. (3) DIGRAC complements existing GNN methods by introducing an imbalance-batt based objective.
DIGRAC's applicability extends beyond settings where the input data is a digraph; for example, with time series data as input, the digraph construction mechanism can accommodate any procedure that encodes pairwise directional association between the corresponding time series, such as lead-lag relationships and Granger causality (Shojaie & Fox 2021). with applications such as in the analysis of information flow in brain networks (Dhamala et al. 2008), biology (Runge et al. 2019), finance [Bennttt et al. 2021 Sornette & Zhou 2005) and carth sciences (Harzallah & Sadourny (197)).
Our method for extracting flow-driven clusters in digraphs based on higher-order meta-graphs can facilitate tasks in time series analysis, ranking, and anomaly detection, as it allows one to extrapolate from local pairwise (directed) interactions to global structure inference, in the high-dimensional low hignal-to-noiss ratio regime. As another accounts A have been created, which are likely to target another subset B of real accounts by sending them messages. Most likely, there would be many more messages from A to B than from B to A,
case, consider a social network where set of fake
2

---

Under review as a conference paper at ICLR 2022
hinting that A is most likely comprised of fake accounts. In ranking applications, where the match results (or preference relationships between items) are encoded in a digraph. DIGRAC would allow for the detection of subsets of players where the relative strength of players in A is superior to that of players in B, thus facilitating the extraction of partial rankings (Cucuringu| 2016).
Main contributions. Our main contributions are as follows. (1) We propose GNN framework for
self-supervised end-to-end node clustering on digraphs, which are possibly attributed and weighted, explicitly taking into account the directed flow imbalance. (2) We propose a prohabilistic version of the global imbalance score to serve as self-supervisee loss function. To the best of our knowledge, this is the first method directly maximizing cut flow imbalance for node clustering in digraphs using GNNs. This new imbalance score is the key novelty in this paper.
(3) We extend our method to the
semi-supervised setting when label information is available.
Paper outline. Section [ reviews existing work. Section 3 introduces our DIGRAC method.
Section 4 validates its strength through extensive experiments at different scales, on synthetic and real- world data. Section conclusions and discusses limitations and future works. In Supplementary Information (SI), Section A expands on variants of our model; Section B discusses implementation provide additional results.
details; Sections C D &
Anonymized codes and preprocessed data are available at https::/ .opp -eb--ccccb----be-e-e 98ea 9
2 RELATED WORK
Directed clustering has been explored by spectral and GNN-based methods. Satuluri & Parthasarathy (011T) performs directed clustering that hinges on symmetrizations of the adjacency matrix, but not scalable as it requires large matrix multiplication. Rohe et al. (016)) proposes a spectral co-clustering algorithm for asymmetry discovery that relies in-degree and out-degree. Whenever direction is the sole information, such as in a complete network with lead-lag structure derived from time series Bennett et al. (2021), a purely degree-based method cannot detect the clusters. While /Zhang et al.) (202Ta) produces two partitions of the node set, one based on out-degree and one based on in-degree, here we produce partition that simultaneously takes both directions into account. Cucuringu et al.) (2020a) seeks to uncover clusters characterized by strongly imbalanced flow circulating among them, based on eigenvectors of the Hermitian matrix (A- A") where A is the (normalized) adjacency matrix and i the imaginary unit. /Zhang et al. (202Tb) builds upon Cucuringu et al. (2020a); Mohar (2020) and introduces a complex Hermitian matrix that encodes undirected geometric structure the magnitude of its entries, and directional information in their phase. Laenen & Sun (2020) uncovers higher-order structural information among clusters in digraphs, while maximizing the imbalance of the edge directions, but its definition of the flow ratio restricts the underlying meta-graph to path.
Ma et al. 2019) and Palmer& & Zheng 2021) introduce directed graph Laplacians, but these methods are only applicable to strongly connected digraphs, which is hardly the case in sparse networks arising in applications. |Monti et al. (2018) utilizes convolution- like anisotropic filters based on local subgraph structures (motifs) for semi- cumi-supervieed node classification tasks in digraphs, but relies on pre-defined structures and fails to handle complex networks. DGCN Tong et al. (2020b) uses first and second order proximity, constructs three Laplacians, but the method is space and speed inefficient. DiGCN Tong et al. (2020a) simplifies DGCN, builds a directed Laplacian based on PageRank, and aggregates information dependent on higher-order proximity. In addition. Zhang al. (2021b); Monti ct al. (2018), Tong et al. (2020b a) all require known labels, which are not generally available for real-world data, /atuluri & Parthasarathy (2011) Rohe et al. (2016) Cucuringu al. (2020a); Palmer & Zheng (2021); Laenen & Sun (2020) could not trivially incorporate node attributes or node labels.
In contrast, we propose an efficient GNN-based method that maximizes a probablistic flow imbalance objective, in self-supervised manner, and which can naturally analyze attributed weighted digraphs.
InfoMap by Rosvall & Bergstrom (2088) assumes that there is a "map" underlying the network, similar to vocta-graphii in DIGRAC. However, InfoMap aims to minimize the expected description length of a random walk and is recommended for networks where edges encode patterns of movement among nodes. While related to DIGRAC, InfoMap still relies on some signals within modules.
To avoid potential misunderstanding, we briefly mention some related papers that we are aware of but do not compare against in our experiments in the main text. Lancichinetti et al. (2011) proposes the OSLOM method, which is very flexible but is based on a density heuristic and hence a comparison to DIGRAC on networks without density signal would not be fair to begin with. Dugué & Perez
3

---

Under review as a conference paper at ICLR 2022
(015)) introduces directionality in the Louvain algorithm. This algorithm optimizes a modularity- tye function that compares the number of edges within communities to the expected number of edges under specified model. It is thus an approach that aims to find denser than expected groups of vertices. When all groups have the same density, as in our synthetic data sets, and the only structure lies in the directionality of the edges, this method simply cannot be expected to perform well. Traag et al. (2019), the Leiden algorithm, also builds on the Louvain algorithm, again optimizing a modularity-type function that compares the number of edges within communities to the expected number of edges under specified model. It is a powerful method for that task, but cannot be fairly compared to DIGRAC which is tailored to find imbalances.
We also do not compare DIGRAC against graph pooling methods (Bianchi et al. 2020). which are inspired by pooling in CNN and developed to discard information which is superfluous for the task at hand. A partition of the nodes which can be interpreted as clustering is only byproduct of graph pooling. Although not often stated explicitly, graph pooling methods are usually developed only for undirected networks. While graph matching as in Xu et al. (2019a b); Chowdhury & Needham (2021) and and Xu (020) can be viewed as a clustering method of networks, matching the graph of interest to disconnected graph by connecting each node in the observed graph with an isolated node of the disconnected graph, this approach is not developed for directed networks. The underlying idea of these papers is complementary to the meta-graph idea which underpins DIGRAC; in the meta-graph, the components are connected, and estimating the directionality of these connections is the main focus. Hence this work addresses very different task. We emphasize that these are all excellent methods, but they address different objectives and tasks. As confirmed by our experiments in E comparing these methods to DIGRAC is not appropriate. DIGRAC tailored to detect an imbalance signal in directed networks, and such signal cannot be present in an undirected network. As it based on imbalance, DIGRAC will not be able to detect signal in an undirected network, thus rendering it not applicable to undirected networks.
3 THE DIGRAC METHOD
Problem definition. Denote a (possibly weighted) digraph with node attributes as g (V, E, E,w, Xy), with V the set of nodes, E the set of directed edges or links, and w E oo) the set of edge weights. G may have self-loops, but no multiple edges. The number of nodes is [ Such network can
[)], and Xy E 1R is matrix whose rows encode the nodes' attributes be represented by the attribute matrix Xy and the adjacency matrix A (Ai)).jev. with A.j = if no edge exists from to By; if there is an edge e from n; to Uj. we set A.j = We. the edge weight.
Digraphs often lend themselves to interpreting weighted directed edges as flows, with a meta- meta-graph on clusters of vertices describing the overall flow directions; see Figure 0 A clustering is a partition of the set of nodes into K disjoint sets (clusters) V Co U C2 U within cluster should be similar to each other with respect flow directions, while nodes across clusters should be dissimilar, In a self-supervised setting, only the number of clusters K is given. In semi- supervised setting, for each of the K clusters, fraction set yseed ç ytrain C V of the set yarain of all training nodes are selected as seed nodes, for which the cluster membership labels are known before training. The goal of semi-supervised clustering is to assign each node v E to cluster containing some known seed nodes, without knowledge of the underlying flow meta-graph. The corresponding self-supervised clustering task does not use seed nodes.
Cx-1- Intuitively, nodes
3.1 SELF-SUPERVISED LOSS FOR CLUSTERING
Our self- self-supervised loss function is inspired by Cucuringu et al. (2020a), aiming to cluster the nodes by maximizing a normalized form of cut imbalance across clusters. We first define probabilistic versions of cuts, imbalance flows, and probabilistic volumes. For K clusters, the assignment probability matrix P E R has as row i the probability vector P (a.:) E R with entries denoting the probabilities of each node to belong to each cluster; its 1tth column is denoted by P ((AA))
The probabilistic cut from cluster C. C₁ is defined as
W(C,, Ct)
Σ
Ar. Pi.k P,
(),==(((.)) (P( (:.)) AP
(.EE(....R))
'If no attributes are available, one could use any feature matrix generated from A, such as stacking the eigenvectors of the Hermitian matrix introduced in (Cucuringu et al. 2020a), construct the feature matrix.
4

---

Under review as a conference paper at ICLR 2022
The imbalance flow between clusters Cj and Ci is defined as [W(C,, - (CG,, C+),, Ak, E {0. K- -1.
For interpretability and ease of comparison, we normalize the imbalance flows to obtain an imbalance score with values in [0, 1] as follows (we defer additional details to AIA.I...
The probabilistic volume for cluster C₁ is defined as
VOL(CA)) = VOL (out) (Cx) + -VLL (in) (Cxx = (A + As,)) P,
Then VOL(CA) 2 W(C,, C)) for all L {o...., K- - and
min (VOLV(C)),, VOL(C)) 2 max(W Ci), (C1, Cx)) I (W(C,, - W C+) The imbalance term, which is used in most of our experiments, denoted Crvolsum is defined as
(1)
CrvoLsume (k, 2
[W(C,, C&),, [0. 1].
VOL(C,) + VOL(C)
The aim is to find a partition which maximizes the imbalance flow under the constraint that the partition has at least two sets, to capture groups of nodes which could be viewed as representing clusters in the meta-graph. The normalization by the volumes penalizes partitions that put most nodes into a single cluster. The range [0, 1] follows from Eq. I Other variants are discussed in SI SI.2
average over To obtain global probabilistic imbalance score, based on Clvol_sum from Eq. 2),
pairwise imbalance scores of different pairs of clusters. Since the scores discussed are symmetric and the cut difference before taking absolute value is skew-symmetric, the pairs T = {(Cx, Ci) 0 < k < 1 < K 1, k, E 2}. We consider a "sort" variant to select these pairs; concretely, we choose the pairs of clusters with the largest 3 pairwise cut flow imbalance values, where 8 is half of the number of nonzero entries in the off-diagonal entries of the meta- graph adjacency matrix (if the peta-graph is known), or can be approximated otherwise. With T(B) {[Ck, Ci) T CI sum (k:,) l) is among the top values), where 1 S 3 S (K), we set
only need to consider
1
OvoLssam
Σ
sum (ki 1), and vom_ sum
Carrt
=
OvoL vol_sum>
B
(C).C)))T(3))
as the corresponding loss function. For example, for a "cycle" meta-graph with three clusters and no ambient nodes, we have 3 3. When consider "path" meta-graph with three clusters and ambient nodes, we have = 1. Definitions of meta-graph structures are discussed in Section In AI..3, additional variants for selecting pairs of clusters in T are considered, including an "std" variant based on hypothesis testing, and "naive" variant which includes all pairs in T. The corresponding scores and loss functions for these variants defined analogously.
3.2 DIRECTED MIXED PATH AGGREGATION (DIMPA)
To implement DIGRAC, we devise simple yet effective directed mixed path aggregation scheme, to obtain the probability assignment matrix and feed it to the loss function, as digraph extension of the successful KernelGCN method introduced by Tian et al. (2019). Thus, in order to build node embeddings, we capture local network information by taking a weighted average of information from neighbors within h hops. To this end, we row-normalize the adjacency matrix, A, to obtain A'. Similar to the regularization discussed in Kipf & Welling (0016). we add a weighted self-loop to each node and normalize by setting A (D²)-1 A where A = A II, and the diagonal matrix D' = Σ3 (i.j), for a small value r, such 0.5.
The h-hop source matrix is given by A yh We denote the set of up-to-h-hop source neighborhood matrices as A A ..... (A )m.. Similarly, for aggregating information when each node is construed as a target node of link, we carry out the same procedure for AT. We denote the set of up-to-h-hop target neighborhood matrices A (I.'') where A is the row-normalized target adjacency matrix calculated from A T
Next, define two feature mapping functions for source and target embeddings, respectively. Assume that for each node in V. a vector of features is available, and summarize these features in the input feature matrix Xy. The source embedding (the superscript s stands for source) is given by
5

---

Under review as a conference paper at ICLR 2022
Σ
WM M
Hü E Raxd
(4)
MEA
where for each M. WM is a learnable scalar, is the dimension of this embedding, and Hi MLP(<.) (Xy). Here, the hyperparameter controls the number of layers in the multilayer perceptron (MLP) with ReLU activation; we fix = throughout. Each layer of the MLP has the same number d of hidden units. The target embedding Z is defined similarly, with 8 replaced by / in Eq. (4).
Different parameters for the MLPs for different embeddings are possible. After these two decoupled aggregations, we concatenate the embeddings to obtain the final node embedding as a x (2d)
matrix Zy- CONCAT (Zi, ZZ)) The embedding vector z; for a node U, is the ith row of Zy. Z; = (Z)) Rdd An efficient implementation of DIMPA is shown in Algorithm D in SIB.&
After obtaining the embedding matrix Zy, we apply linear layer (an affine transformation) to Zy, that the resulting matrix has K columns. Next, we apply the unit softmax function the rows and obtain the assignment probability matrix P. Figure gives an overview of this implementation.
h hE2*
Embedding
Network embedding etc.
A 1grice
MLP
IP
DIMPA
Z
Angran
Cluster Assignment
Patrwise/glohal cut imbalance scomes etc.
A
Z
CONCAT
Probability
ARI, predicted
Matrix
Figure 2: DIGRAC overview: from feature matrix X y and adjacency matrix A, first compute
the row-normalized adjacency matrices A and A". Then, we apply two separate MLPs on Xy, to obtain hidden representations H' and H' Next, compute their decoupled embeddings using Eq. 4 and its equivalent for target embeddings. The concatenated decoupled embeddings are the final embeddings. For node clustering tasks, add linear layer followed by unit softmax to obtain the probability matrix P. Applying argmax on each row of P yields node cluster assignments.
EXPERIMENTS
In this section, we describe the synthetic and real- warld data sets used this study, and illustrate the efficacy of our method. When ground truth is available, performance is measured by the Adjusted Rand Index (ARI) (Hubert Arabie 1985) for node clustering, and by accuracy for node classification and link direction prediction. Normalized Mutual Information (NMI) results give almost the same ranking for the best-perfond pessfpeeforming methods as the ARI, with an average Kendall tau value of 84.2% and standard deviation 25.1 & for pairwise ranking comparison, the methods compared in our experiments. We do not focus on NMI in the main text due to its shortcomings (Liu et al. 2019).
Clustering tasks will have different ground truths, depending the pattern they are trying detect. Many network clustering methods focus on detecting relatively dense clusters, and try to optimize classical network clustering measures, such as directed modularity partition density. Ground truth for these clustering algorithms then relates to relatively densely connected subgroups the data. DIGRAC is novel method that addresses novel task, namely that of detecting flow imbalances. To the best of our knowledge, real data sets with ground-truth flow imbalances are not available to date, and hence we introduce normalized imbalance scores evaluate clustering performance based on flow imbalance. As ARI and NMI require ground-truth labels, they thus cannot be applied to the available real-world data sets. To address this shortcoming. for the real-world data sets, in Table [ we include two performance measures which we introduce in the paper, and the SI contains an additional 12 performance measures. Implementation details are provided SI B
In our experiments, we compare DIGRAC against the most recent related methods from the literature for clustering digraphs. The 11 methods are
(1) InfoMap (Rosvall & Bergstrom, 2008),
(2) Bibliometric and (3) Degree-discounted introduced in (Satuluri & Parthasarathy (011
(4) DI SIM (Rohe et al. 2016).
(5) Herm and
(6) Herm sym introduced in Cucuringu et al.
(2020a)
(7) MagNet (Zhang al.] 2021b).
(8) DGCN (Tong et al.) (2020b). (9) three
variants of DiGCN (Tong et al., 2020a). The abbreviations of these methods, when reported in
the numerical experiments, Bi sym, DD__yym, DISG_LR, Herm, Herm_sy Herm_sym, MagNet, DGCN,

---

Under review as a conference paper at ICLR 2022
DiGCN, DiGCN app, DiGCN ib, respectively, DGCN is the least efficient method in terms of speed and space complexity, followed by DiGCN ib which involves the so-called inception blocks (hence the suffix ib). DiGCN denotes the method without using approximate Laplacian based on personalized PageRank, while DiGCN_app and DiGCN_is ibb use this approximation. We use the same hyperparameter settings stated in these papers. Methods (7), (8), (9) are trained with 80% nodes under label supervision while all the other methods are trained without label supervision. DIGRAC further restricts itself to be trained on the subgraph induced by only the training nodes. For MagNet, we use 0.25 for the phase matrix, which is suggested to capture directionality the most effectively.
q
4.1 DATA SETS
Synthetic data: Directed Stochastic Block Models standard directed stochastic blockmodel (DSBM) is often used to represent network cluster structure, see for example (Malliaros & Vazirgian mis ). Its parameters are the number K of clusters and the edge probabilities; given the cluster assignment of the nodes, the edge indicators are independent. The DSBMs used in our experiments also depend on a meta-graph adjacency matrix F = (Fu..)).= and a filled version of it, and on a noise level parameters S 0.5. The meta-graph adjacency matrix is generated from the given meta meta-graph structure, called M. To include an ambient background, the filled meta-graph adjacency matrix F replaces every zero in F that is not part of the imbalance structure by 0.5. The filled meta-graph thus creates a number of umbient nodes which correspond to entries which are not part of M and thus are not part of a meaningful cluster; this set of ambient nodes is also called the ambient cluster. First, we provide examples of structures of F without any ambient nodes, where denotes the indicator function.
F = (F (...)..f=o.....
(1) "cycle": Fx,1 = 1)
(k) mod K)) + n1 = (k--1) 1) mod K)) + 2 1 R:) 1) 11 k).
(2) "path" Fx,/ (1 - ()== m1
(3) "complete": assign diagonal entries 1. For each pair (k, 1) with h < L, let FR, be 17 and 1 -
with equal probability, then assign Fi,- = FR.I-
K- and set Fx = (1 1 = w. odd) + I = w. even) + (1 (1-11) (1 w, k odd) + 71 w. / even).
(4) "star", following (Elliott et al. 2019): select the center node
When ambient nodes are present, the construction involves two steps, with the first step the same the above, but with the following changes: For "cycle" meta-graph structure, Fx., = (1
(k++)
mod (K - 1))) + (2 ((k - 1) mod (K 1))) + 0.5 1(1 = k). The second step is to assign 0 (0.5, resp.) to the last row and the last column of F (F, resp.). Figures (cd) display a "cycle" meta-graph structure with ambient nodes (in cluster 4). The majority (75%) of edges flow in the
form - 1 + 2 - -> O. while 25% flow from the opposite direction. Figure [d) illustrate the meta-graph adjacency matrix corresponding to F shown in Figure Ic).
In our experiments, we choose the number of clusters, the (approximate) ratio, p. between the largest and the smallest cluster size, and the number, n. of nodes. To tackle the hardest clustering task, all pairs of nodes within a cluster and all pairs of nodes between clusters have the same edge probability. p. Note that for M ="cycle" even the expected in-degree and out-degree of all nodes are identical. Our DSBM, which we denote by DSBM (M, 1 (ambient), n, K, p. p. 17), is built similarly to (Cucuringu et al. 2020a) but with possibly unequal cluster sizes, with more details in B.3 For each node vs E Ck. and each node Uy E Ct. independently sample an edge from node Y/ to node fy with probability p- Fx..- The parameter settings in our experiments are p E {0.001, 0.01, 0.02, 0.1}, p E 1.5), K E (3,5, 10), I (ambient) E (T, F) (True and False), n E { (1000, 5000, 30000). and we also vary the direction flip probability 7y from O to 0.45, with a 0.05 step size.
Real-world data We perform experiments on five real-world digraph data sets, namely Telegram (Bovet& & Grindrod 2020), Blog (Adamic & Glancel 2005). Migration (Perry 2003). WikiTalk
Leskoveec et al. 2010). and Lead- Lag (Bennett al. [022]] with details in BB3 We set the number of clusters K to be 4, 2, 10, 10, 10, respectively, and values of ,3 to be 5, 1, 9. 10, 3, respectively.
Note that Lead-Lag comprises of 19 separate networks constructed from yearly financial time series.
4.2 EXPERIMENTAL RESULTS
Training set-up and hyperparameter selection As training setup, we use 10% of all nodes from each cluster as test nodes, 10% as validation nodes to select the model, and the remaining 80% as training nodes. In each setting, unless otherwise stated, we carry out 10 experiments with different
7

---

Under review as a conference paper at ICLR 2022
data splits. Error bars are given by one standard error. Without node attributes, the matrix Xy: for DIGRAC is taken as the stacked eigenvectors corresponding to the largest K eigenvalues of the random-wall symmetrized Hermitian matrix used in the comparison method Herm The imbalance loss function acts on the subgraph induced by the training nodes. Hyperparameters selected via greedy search, with details in SI [B.4] FigureBra) compares DIGRAC DSBM with n = 1000 nodes, K = 5 clusters, = 1, P = 0.02 without ambient nodes, under different hyperparameter settings. Here hop h 2 should be chosen reduce complexity, as increasing does not lead to increased performance. Therefore, our default setting is hop h 2, d 32, r = 0.5.
0.4
0.4
+
CE
0.3
+ CI
std
0.1
0.3
1
LICE
0.3-
naive
60.2
20.2
420.
30.4
0.1
6.1
0.0
0.0
0.0
0.0
0.1
0.2
0.3
0.00
0.05
0.30
0.15
0.0
0.1
0.0
0.1
0.2
0.3
0
9
(a) Vary the hop h in
(b) Vary loss for DiGCN: (c) Vary selection methods
(d) Vary seed ratio in semi-supervised setting.
of imbalance pairs. Figure 3: Hyperparemter analysis (a) and ablation study (b-d) on a "cycle" DSBM with n 1000
DIMPA.
CE, LICE.
nodes, K = 5 clusters, p 1, and p 0.02, without ambient nodes.
10.0m
0.5
0.3
0.4
--3
80.2
422
3.2
0.1
0.0
0.0
0.1
0.2
03
0.0
0.1
0.2
0.3
0.0
01
0.2
0.1
0.2
(a) DSBM( "complete", T,
(b) DSyMl"cycle" F,
(c) DSBM("path") F,
(d) DSBM F.
1000, K = 10,
1000, K = 3.P
1000, K = 5,
71
1000, K = 5, =
0.02, p 1)
0.02, p 1.5)
0.02, p 1)
0.02, p
0.8
0.8
0.5
0044
30.4
01
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.3
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.1
0.2
(c) DSBM(" ("cmmcccmpltte F, (f) DSBM( "complete", T,
(g) DSBM "cycle", ; T,
(h) DSBM( "cyyll", F,
1000, K = 3
1000, K 5.
n
5000, K = 5,
71
30000, K = 5
0.1,
p.5
0.01, 1.5)
0.001,
Figure 4: Test ARI comparison synthetic data. Dashed lines highlight DIGRAC's performance. Error bars are given by one standard error.
Node clustering results on synthetic data Figure 4 compares the numerical performance of DIGRAC with other methods synthetic data. For this figure generate 5 DSBM networks under each parameter setting and use different data splits for each network, then average over the 50 runs. Error bars are given by one standard error. Additional implementation details are available in SIB
We conclude that DIGRAC attains state-of-the- results on a wide range of network densities and noise levels, different network sizes, and with different meta-graph structures, whether not there exist ambient nodes. DIGRAC outperforms its competitors by a large margin especially when there exist ambient nodes, which validates its strength of extracting the main directional signal planted in larger graph. Additional results are reported in SI[ from which similar conclusions can be drawn.
Node clustering results on real-world data For our real-world data sets, the node in- and out- degrees may not be identical across clusters. Moreover, these data sets do not contain node attributes, DIGRAC considers the eigenvectors corresponding to the largest eigenvectors of the Hermitian matrix from (Cucuringu al. 2020a) to construct an input feature matrix. Table T reveals
8

---

Under review as a conference paper at ICLR 2022
Table 1: Performance comparison on real-world data sets. The best marked in bold red and the
second best is marked in underline blue. The objectives are defined in Section 3.1
Metric
Data set
InfoMap
Bi_sym
DD_sym
DISG_LR
Herm
Herm_rw rww
DIGRAC
Telegram
0.04+0.00
0.21+000
0.21=0.00
0.21+0001
0.2+0.01
0.14=0.0
0.32:10.01
Blog
0.07
0.07+00.0
0.0+0.00
0.05+0000
0.37+-0.0
0.0+0.0
0.44-00.0
Vott vol_sum
Migration
N/A
0.03++0.00
0.01+00000
0.02++0.00
0.04++0.00
0.02+0.00
0.05++0.00
WikiTalk
N/A
N/A
N/A
0.18++0.03
0.15+00.02
0.0++0.0
0.24++0.05
Lead-Lag
N/A
0.07::0.01
0.07:10.01
0.07100.01
0.07:10.02
0.07-10.02
0.15:10.03
Telegram
0.01
0,26+00.0
0.26+000
0.26++0.01
0.25+0.02
0.23=0.0
0.27-+0.01
Blog
0.00++000
0.07+0000
0.0+00.0
0.05+000
0.37+00.0
0.0+0.00
0.44=00.0
Ouiive
Migration
N/A
0.01
0.01
0.01+
0.02++0.00
0.01
0.04
WikiTalk
N/A
N/A
N/A
0.1
0.04110.0
0.010.0
0.12.10.01
Lead-Lag
N/A
0.30.10.06
0.28.10.06
0.27.10.06
0.29
0.29
0.32.10.11
that DIGRAC provides competitive global imbalance scores in both objectives discussed and across all real-world data sets, and outperforms all other methods in all instances, the four data sets and two objective functions. The N/A entries for Wikifalk are caused by memory error, and the N/A entries for InfoMap on Migration and Lead-Lag are due its prediction of only one single cluster. Lead-Lag results in each year are averaged over ten runs, while the mean and standard deviation values are calculated with respect to the years. The experiments indicate that edge directionality contains an important signal that DIGRAC is able to capture. A comprehensive numerical comparison is available in S revealing similar conclusions.
4.3 ABLATION STUDY
Figure b) compares the performance of DiGCN replacing the loss function by Csoe sum from Eq. (3) indicated by "CI", or LICE, sum of supervised and self-supervised loss, on a DSBM((cycle T. = 1000, K = 5. 0.02, p = 1) model. We find that replacing the supervised loss function with vo leads to comparable results, and that adding vol_suu to the loss could be beneficial. Figure 3 ( compares the test ARI performance using three variants loss functions on the same digraph. The current choice "sort" performs best among these variants, indicating benefit in only considering top pairs of individual imbalance scores. More details on loss functions, comparison with other variants, and evaluation on additional metries discussed in SI[A] with similar conclusions. As illustrated in Figure d),), again on the same digraph, we also experiment on adding seeds, with the seed ratio defined as the ratio of the number of seed nodes to the number of training nodes. A supervised loss, following (Tian et al.) 2019), is then applied to these seeds; BI.3 contains additional details. In conclusion, seed nodes with a supervised loss function enhance performance, and we infer that our model can further boost its performance when additional label information is available.
5 CONCLUSION AND FUTURE WORK
DIGRAC provides an end-to-end pipeline to create node embeddings and perform directed clustering, with or without available additional node features or cluster labels. Further work will include additional experiments in the semi-supervised setting, when there exist seed nodes with known cluster labels, or when additional information is available in the form of must-link and cannot-link constraints, popular in the constrained clustering literature (Basu et al. 20088: Cucuringu al., 20166). Another future direction pertains to extending our framework to also detect the number of clusters (Riolo) al. 2017 Chen & Baker 2021), instead of specifying it a-priori, as this is typically not available in real-world applications. The current framework requires additional preliminary analysis on how many pairwise imbalance scores consider, such as by inspecting the (initial or fitted) meta- graph adjacency matrix. It would be interesting to build a more powerful framework that can automatically detect the value /3 used in the current model, to select the subset of influential pairs of imbalances.
Further research directions will address the performance in the sparse regime, where spectral methods are known to underperform, and various regularizations have been proven to be effective both on the theoretical and experimental fronts; for example, see regularization in the sparse regime for the undirected settings (Chaudhuri et al.] 2012, Amini et al. 2013] Cucuringu et al. 2020b). Finally, adapting our pipeline for directed clustering in extremely large networks, possibly combined with sampling methods or mini- batch (Hamilton et al.) 2017). is a direction worth exploring, rendering DIGRAC AC applicable to large scale industrial applications.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Lada A Adamic and Natalic Glance. The political blogosphere and the 2004 US election: divided they blog. In Proceedings of the 3rd International Workshop on Link Discovery, pp. 36-43, 2005.
Arash A. Amini, Aiyou Chen, Peter J. Bickel, and Elizaveta Levina. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41(4):2097-2122, 2013.
Sugato Basu, Ian Davidson, and Kiri Wagstaff. Constrained Clustering: Advances in Algorithms, Theory, and Applications. CRC Press, 2008.
Stefanos Bennett, Mihai Cucuringu, and Gesine Reinert. Detection and clustering of lead-lag networks for multivariate time series with an application to financial markets. 7th SIGKDD Workshop on Mining and Learning from Time Series (MiLeTS), 2021.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pp. 874-882 PMLR, 2020.
Alexandre Bovet and Peter Grindrod.
The Activity of the Far Right on Telegram www.wewwwt...aa.eeeeeeeeeeeeeeee net 10t11:1//////555555 iiciiiiciiis____eeciiiii.i
https: //ww://wwwww.om www.rreeeeaaaaaa
of Far Faa_aarr_ihhoorrreeaeaahar Telegrra____eemmmm______________ _21 2020.
Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. In 25th Anmual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 35.1-35.23, 35.23, Edinburgh, Scotland, 2012. JMLR Workshop and Conference Proceedings.
Louis HY Chen, Larry Goldstein, and Qi-Man Shao. Normal approximation by Stein's method. Springer Science & Business Media, 2010.
Yilin Chen and Jack W Baker. Community detection in spatial correlation graphs: Application to non-stationary ground motion modeling. Computers and Geosciences, 2021.
Samir Chowdhury and Tom Needham. Generalized spectral clustering via gromov- wasserstein learning. In International Conference on Artificial Intelligence and Statistics, pp. 712-720. PMLR, 2021.
Mihai Cucuringu. Sync-rank: Robust ranking, constrained ranking and rank aggregation via eigen- vector and SDP synchronization. IEEE Transactions Network Science and Engineering, 3(1): 58-79, 2016. ISSN 23274697.
doi: 10. 10.1109//NSE..21622221777
Mihai Cucuringu, Vincent Blondel, and Paul Van Dooren. Extracting spatial information from networks with low-order eigenvectors. Phys. Rev. E, 87:032803, Mar 2013. doi: 10.1103/PhysevvE. 87.032803.
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, and Richard Peng. Scalable Con- strained Clustering: A Generalized Spectral Method. Artificial Intelligence and Statistics Confer- ence (AISTATS) 2016, 2016.
Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. Hermitian matrices for clustering directed graphs: insights and applications. International Conference on Artificial Intelligence and Statistics, pp. 983-9922 992. PMLR, 2020a.
Mihai Cucuringu, Apoorv Vikram Singh, Déborah Sulem, and Hemant Tyagi. Regularized spectral methods for clustering signed networks. 2rX1v:2011.01737, 2020b.
Mukeshwar Dhamala, Govindan Rangarajan, and Mingzhou Ding- Analyzing information flow in brain networks with nonparametric Granger causality. Neurolmage, 41(2):354-38 2008 ISSN 1053-8119. doi: http:///oi..rr//0...00 wew.://///eeommmaeeee.0........ 02..020. htttstt:: :/ www sciencedirect. www.ccooccci.eeccccccoo
Nicolas Dugué and Anthony Perez. Directed Louvain: maximizing modularity in directed networks.
PhD thesis, Université d' Orléans, 2015.
10

---

Under review as a conference paper at ICLR 2022
Andrew Elliott, Paul Reidy Milton Martinez Luaces, Mihai Cucuringu, and Gesine Reinert. Anomaly detection in networks using spectral methods and network comparison approaches. arXiv preprint arXiv:1901.00402, 2019.
Andrew Elliott, Angus Chiu, Marya Bazzi, Gesine Reinert, and Mihai Cucuringu. Core-periphin structure in directed networks. Proceedings of the Royal Society A, 476(2241):2019078888 2020.
Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. arXiv preprint wrxiv:210.005609 2021.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):8211-7226 2002.
Gero Greiner and Riko Jacob. The I/O Complexity of Sparse Matrix Dense Matrix Multiplication', booktitle=LAATIN 2010: Theoretical Informatics. pp. 143-156, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 2-8-3-642-12200--
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs In Proceedings of the 3 International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Adam P Harrison and Dileepan Joseph. High performance rearrangement and multiplication routines for sparse tensor arithmetic. SIAM Journal on Scientific Computing, 40(2):C258-C28) 2018.
A Harzallah and R Sadourny. Observed lead-lag relationships between indian summer monsoon and some meteorological variables. Climate dynamics, 13(9):635-648 1997.
Lawrence Hubert and Phipps Arabic. Comparing partitions. Journal of Classification, 2(1):193-218, 1985.
Caiyan Jia, Yafang Li, Matthew B Carson, Xiaoyang Wang, and Jian Yu. Node cerributt-enhancee community detection in complex networks. Scientific Reports, 7(1):1-15, 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv::412.00 29800, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1rXiv:609..00 (0096669099077 2016.
Steinar Laenen and He Sun. Higher-order spectral clustering of directed graphs. Advances in Neural Information Processing Systems, 2020.
Andrea Lancichinetti, Filippo Radiechi, José J Ramasco, and Santo Fortunato. Finding statistically significant communities in networks. PloS one, ((4)xe18961, 2011.
Elizabeth A Leicht and Mark EJ Newman. Community structure in directed networks. Physical Review Letters, 100(1 I): 10:1181 18703, 2008
Jure Leskovec, Kevin Lang, Anirban Dasgupta, and Michael W Mahoney. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web, pp. 695-704, 2008
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1361-1370, 2010.
Xin Liu, Hui-Min Cheng, and Zhong-Yuan Zhang. Evaluation of community detection methods.
IEEE Transactions Knowledge and Data Engineering, 32(9): 2019.
Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral-based graph convolutional network for directed graphs. arXiv preprint arxivv 2019.
Fragkiskos Malliaros and Michalis Vazirgiannis. Clustering and community detection in directed networks: A survey, Physics reports, 533(4):95-142, 2013.
11

---

Under review as a conference paper at ICLR 2022
Elan Sopher Markowitz, Keshav Balasubramanian, Mehrnoosh Mirtaheri, Sami Abu-El-Haija, Bryan Perozzi, Greg Ver Steeg, and Aram Galstyan. Graph traversal with tensor functionals: A meta- algorithm for scalable learning. In International Conference Learning Representations, 2021. ew. net forum? d= 6D078XNNFGN
URL /tttps://ppenrreeee
Bojan Mohar. new kind of Hermitian matrices for digraphs. Linear Algebra and its Applications, 584:343-352, 2020.
Federico Monti, Karl Otness, and Michael M. Bronstein. Motifnet: A motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228, 2018. doi: (0000//DW.208..4435553833
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103323):8777-882, 2006.
William R. Palmer and Tian Zheng. Spectral clustering for directed networks. In Rosa M. Benito, Chantal Cherifi, Hocine Cherifi, Esteban Moro, Luis Mateus Rocha, and Marta Sales-Pardo (eds.), Complex Networks & Their Applications IX, pp. 87-99, Cham, 2021. Springer International Publishing. ISBN 778-3-030-65347-7.
Marc J Perry. State-to-state Migration Flows, 1995 to 2000. US Department of Commerce, Economics and Statistics Administration, US ..... 2003.
Ryan L Phillips and Rita Ormsby. Industry classification schemes; An analysis and review. Journal of Business Finance Librarianship, 21(1):1-25, 2016.
Maria A Riolo, George T Cantwell, Gesine Reinert, and Mark EJ Newman. Efficient method for estimating the number of communities a network. Physical Review E, 96(3):032310, 2017.
Karl Rohe, Tai Qin, and Bin Yu. Co-clustering directed graphs to discover asymmetries and directional communities. Proceedings of the National Academy of Sciences, 1 113(45):12679 2016.
Martin Rosvall and Carl T Bergstrom. Maps of random walks complex networks reveal community structure. Proceedings of the national academy of sciences, 11184):111--122 2008.
2008.
Jakob Runge, Peer Nowack, Marlene Kretschmer, Seth Flaxman, and Dino Sejdinovic. Detecting and quantifying causal associations in large nonlinear time series datasets. Science advances, (11), 2019.
Venu Satuluri and Srinivasan Parthasarathy. Symmetrizations for clustering directed graphs. In Proceedings of the 14th International Conference on Extending Database Technology, pp. 343-354, 2011.
Ali Shojaie and Emily B Fox. Granger causality: review and recent advances. arXiv preprint wrXh::2105.02675. 2021.
Didier Sornette and Wei-Xing Zhou. Non coramaemetricc determination real-time lag structure between two time series: the 'optimal thermal causal path method. Quantitative Finance, 5(6):577-591, 2005.
Yu Tian, Long Zhao, Xi Peng, and Dimitris N Metaxas. Rethinking kernel methods for node representation learning on graphs. Advances Neural Information Processing Systems, 32, 2019.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. Advances in Neural Information Processing Systems, 33, 2020a.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXiv:2004. 13970, 2020b.
Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. From louvain to leiden: guaranteeing well-connected communities. Scientific reports, 9(1):1-12, 2019.
12

---

Under review as a conference paper at ICLR 2022
Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable wasserseasn learning for graph partitioning and matching. Advances in neural information processing systems, 32:3052-300 -3662, 2019a.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserseinn learning for graph matching and node embedding. In International conference on machine learning, pp. 6932-6944 PMLR, 2019b.
Hongtengl Xu. AAAI Conference Artificial Intelligence, volume 34, pp. 6478-6485, 2020.
factorization models for graph clustering. Proceedings of the
Jingnan Zhang, Xin He, and Junhui Wang. Directed community detection with network embedding. Journal of the American Statistical Association, pp. 1-11, 2021a.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. Magnet: A neural network for directed graphs. arXiv preprint arXiv:2102.11391, 2021b.
13

---

Under review as a conference paper at ICLR 2022
A LOSS AND OBJECTIVES
A. ADDITIONAL DETAILS ON PROBABILISTIC CUT AND VOLUME
Recall that the probabilistic cut from cluster Cj to C₁ is defined as
CC) = Σ A. P P3 = - (P (c.))
JJE(I.....))
where P ((.k). P (1.) denote the hthh and 1th columns of the assignment probability matrix P, respectively, The imbalance flow between clusters Cj and C₁ is defined as
[C Ci) C&),
for k, E KO...., 1}. The loss functions proposed in the main paper can be understood in terms of probabilistic notion of degrees, as follows. We define the probabilistic out-degree of node e with respect to cluster by 2o00)) Σÿ= Aij P,A = (AP((.)));; where subscript i refers to the 7t entry of the vector AP (s.A)- Similarly, we define the probabilistic in-degree of node i with respect to cluster k by i, (A ((.)) where A is the transpose of A. The probabilistic degree of node Vy with respect to cluster & di = T + Zomn) = ((AT + A)P (L.),, = (A.. A,,) -.,)).P..t P.A.-
Zin)
For comparisons and ease of interpretation, it is advantageous to normalize the imbalance flow between clusters; for this purpose, we introduce the probabilistic volume of cluster, as follows. The probabilistic out-volume for cluster C₁ is defined as (OL (Cx) = Exs Aj, PY and (.A)), where A is the
the probabillitic in-volume for cluster CR is defined as VOL (Cx) (A"P)(.))) transpose of A. These volumes can be viewed as sum of probabilistic out-degrees and in-degrees, respectively; for example, VOL = Em= Jim) Then, holds true that
VOT, (CL) = Σ A.j PI Σ A.
PAR P = CI),,CI)
(5)
12
1.j
since entries in P are probabilities, which are in [0. 11, and all entries of A are nonnegative. Similarly, VOL (C,) 2 W(C,, C.).
The probabilistic volume for cluster Cg is defined as
VOL(C,) = VOL lou (Cx) (OL E(Ar, + +1,)) PjA
Then, holds true that VOL(C&) Z W(Ck, Ci) for all / E (O....,A K- 1} and VOL(C)) 2 max(W (C,, CJ). (C,, 2 WC -
(6)
When there exists a strong imbalance, then (C,,, W(C, Cx) max CJ), WCC,CC Cx). As an extreme case, if P,I = for all nonnegative terms in the summations in Eq. 5) and VOL (Cs) = 0, then JW (Cx, Ci) WCC,, VOL(C.).
A.2 VARIANTS OF NORMALIZATION
Recall that the imbalance term involved in most of our experiments, named Co is defined as Crvolsum (ks (C,, - W (C,,C+)) E [0, VOL(C.) + VOL(C)
An alternative, which does not take volumes into account, is given by W(C,, Ct) W C:) - W (CC,, Cx) = W(C,,C,) C,),,C+) W(C,, C.) (C,
1 [0,
Ciplain (k,
(8)
2
We call this cut flow imbalance Ciplain
does not penalize extremely unbalanced cluster sizes.
To achieve balanced cluster sizes and still constrain each imbalance term to be in [0, 1], one solution is multiply the imbalance flow value by the minimum of V (OT(C&)) and VOT.(C)), and then divide by
14

---

Under review as a conference paper at ICLR 2022
(A)))) (min VOL(()))) where T= [(C..
2).
The reason for using T is that CTPlain (k: 1) is symmetric with respect to i and 1, and CTplain (k: 1) = whenever & = L. Note that the maximum of the minimum here equals the second largest volume among clusters. We then obtain Civol_mi
as
VO (P (min( VOL(C)))
croo = Ciplain (k,
Another potential choice, denoted C1voL whose normalization follows from the same reasoning as CI _i is given by
- C(G, E
CIvol max (k,1) max(VOOL(Cs, VOL(C))
(10)
A.3 VARIANTS OF CHOOSING THE PAIRWISE IMBALANCE, SCORES
We consider three variants for choosing the cluster pairs.
(1) The "sort" variant picks the largest 3 pairwise cut imbalance values, where 3 is half of the number of nonzero entries in the off-diagonal entries of the meta-graph adjacency matrix F, if the meta-graph is known can be approximated. For example, when we have a "cycle" meta-graph with three clusters and no ambient nodes, then 3 = When we have a "path" meta-graph with three clusters and ambient nodes, then / 1.
(2) The "naive" variant considers all possible (5) pairwise cut imbalance values.
(3) The "sid" variant only considers pairwise cut imbalance values that are 3 standard deviations away from the imbalance values; the standard deviation is calculated under the null hypothesis that the between-cluste relationship has no direction preference, i.e. Fx,1 Fi,k- as follows.
Suppose two clusters have only noisy links between them (no edge in the meta- peetaggraph F). Suppose also that the underlying network is fixed in terms of the number of nodes and where edges exist; the only randomness stems from the direction of an edge. Then, for each edge between these two clusters, say, clusters Cş and Ci, the edge direction is random, i.e. the edge is from C. to C with probability 0.5, and C to C. with probability 0.5 also. Let E denote the set of edges between Cg and C if gl? is not empty, then for every edge e E gk.,,, define a Rademacher random variable X. by
( 1-1,
if the edge is from Cj to Ct,
X.
(11)
otherwise.
Then (Xe + 1)/2 ~ (er(.. is a Bernouli(0.55) random variable with mean 2 x 0.5 - 1 0 and variance 2 0.5 x (1 0.5) 1. In the case of unweighted edges, the total number of edges between C+ and C, is [
W(C,, Ci) WW Cx), and that the sum of X, terms is Erego. X. (CC,, Ct) - (C1, Cc). In the case of weighted edges, with symmetric edge weights Wi.j = W33 given and only edge direction random, it holds that W(Ck, Ci) W(G,, C&) Eeegt. XeW..
Let us assume that the edge indicators are independent and that Eeeg,, w > O. Under the null hypothesis that there no meta- graph edge between C₁ and C₁, the random variable Exeer, X.w,
v /Eecet. we has mean 0 and variance 1. Assuming that the weights are bounded above and that > Zeegka w² is bounded away from 0 with increasing network size, we can employ the Central Limit Theorem for sums of independent random variables, see for example Theorem 3.4 in Chen et al. (2010). Then, under the null hypothesis, approximately 99.7 % of the observations would fall within standard deviations from O. While this calculation makes many assumptions and ignores reciprocal edges, the resulting threshold is still useful guideline for restricting attention to pairwise imbalance values which are very likely capture true signal.
A.4 SELECTION OF THE LOSS FUNCTION
Table[[provee naming conventions of all the twelve pairs of variants of objectives and loss functions used in this paper. We select the loss functions for DIGRAC based on two representative models, and compare the performance of different loss functions. We use d 32, hidden units, h 2 hops,
15

---

Under review as a conference paper at ICLR 2022
Table 2: Naming conventions for objectives and loss functions
Selection variant CT
C
Crvol_min
C CTvoL
C
sort std naive
O Sort
sum
vol sum! vol sum
Lsort
sort
vol minn
Lsort
vol vol_min min
Sort
vol max -vol mix
plain plain
Lsort
Osid
Lstd
Osd
Osid
Lsdd
L
sum! sum!
vol sum
vol_min?
vol min
vol max
vol max
plain plain
Onavve
Coaive
vol_smm -vol_
vol_min:
vol moin
vol_min
min
vol_max
vol _ol_maa
plain -
1.0
0.5
vol sum.sort
0.8
vol
0.4
plain.sort
vol minstdd vol sum.std plainustd VoL min.naive
0.6
0.3
ARI
AR
0.4
0.2
val navee plaiuraiie
0.2
0.1
0.0
0.0
0.0
0.2
0.3
0.0
0.1
n
DSBM("ccmpletts
(b) DSBM( ("yclle". 1000, 5, = 0.02, 1)
n 1000,
5,p 0.02, 1)
Figure 5: ARI comparison of loss functions DSBM with 1000 nodes, 5 blocks, p= 1, 0.02 without ambient nodes, of cycle (left) and complete (right) meta-graph structures, respectively. The first component of the legend is the choice of pairwise imbalance, and the second component the variant of selecting pairs. The naming conventions for the abbreviations the legend are provided in Table 2
and seed nodes. Figures 5[a) a)) and and commpare twelve choices of loss combinations DSBM with n = 1000 nodes, meta-graph structure. The subscript indicates the choice of pairwise imbalance, and the superscript indicates the variant of selecting pairs. Figures ()bb and 7 are based on DSBM with n = 1000 nodes, K blocks, p = 1,p 0.02 without ambient nodes, with a cycle meta- meta-graph structure.
blocks, 1.p p = 0.02 without ambient nodes, with a complete
These figures indicate that the "sort" variant generally provides the best test ARI performance and the best overall global imbalance scores, among which using normalizations Crvo.sum and Cpsu perform the best. Ceet appears behave worse than C val_ and Lsort _ max even when using the "sort" variant select pairwise imbalance scores. One possible explanation is that C L does penalize extreme volume sizes, and that takes minimum as well as maximum which, as functions of the data, are as smooth taking summation. Throughout our experiments in the main text, we hence use the loss function Lyo sum
B IMPLEMENTATION DETAILS
B.1 CODE
To fully reproduce results, anonymized code and preprocessed data are available at https //anonymous. 4open. http://wwo.ooooooo.o.eeeee////ee 4e6a 98ea
4 376688135361
B.2 HARDWARE
Experiments were conducted on a compute node with 8 Nvidia RTX 8000, 48 Intel Xeon Silver 4116 CPUs and 1000GB RAM, compute node with 4 NVIDIA GeForce RTX 2080, 32 Intel Xeon
16

---

Under review as a conference paper at ICLR 2022
1.00
0.15
0.75
0.15
0.10
0.500
0.25
0.06
0.00
0.00
0.00
1.00
0.20
1.00
0.15
50.50
0.110
50
0.25
0.00
0.20
1.00
0.2
0.75
0..0
20.50
50.3
0.05
0.25
0.00
0.2
1.00
0.75
E0.50
20.1
0.25
0.00
Figure 6: Imbalance scores comparison of loss functions on DSBM with 1000 nodes, blocks, P 1, p 0.02 without ambient nodes, of the complete meta-graph structure. The legend the same as Figure 5la) a).
0.15
50.10
60.4
20.10
0.05
0.05
20.10
0.4
10.4
0.05
0.0
0.8
0.30
3.0.4
0.05
0.00
0.0
0.00
0.4
0.4
120.2
0.05
0.0
0.0
Figure 7: Imbalance scores comparison of loss functions on DSBM with 1000 nodes, blocks, 0 1,p 0.02 without ambient nodes, of the eyclic meta-graph structure. The legend is the same as Figure 5 a).
17

---

Under review as a conference paper at ICLR 2022
E5-2690 v3 CPUs and 64GB RAM, compute node with 2 NVIDIA Tesla K80, 16 Intel Xeon E5-2690 CPUs and 252GB RAM, and an Intel 2.90GHz 17-10700 processor with 8 cores and 16 threads.
With this setup, all experiments for spectral methods, MagNet, DIGCN and DIGRAC can be com- pleted within two days, including repeated experiments, obtain averages over multiple runs. DGCN and DiGCN ib have much longer run time (especially DGCN, which is space-consuming. and we cannot run many experiments in parallel), with a total of three days for both of them to finish. The slow speed stems from the competitor methods; some of the other GNN methods take long time to run. Table Tin the main text shows N/A values for Bi Bi_sym and for DD DD_sym exactly for this reason. Empirically, DIGRAC is the fastest among all GNN methods to which it is compared.
B.3 DATA
The results comparing DIGRAC with other methods on synthetic data are averaged over 50 runs, five synthetic networks under the same setting, each with 10 different data splits, For synthetic data, 10% of all nodes are selected as test nodes for each cluster (the actual number is the ceiling of the total number of nodes times 0,1, to avoid falling below 10% of test nodes), 10% are selected as validation nodes (for model selection and early-stopping; again, we consider the ceiling for the actual number), while the remaining roughly 80% are selected as training nodes (the actual number can never be higher than 80% due to using the ceiling for both the test and validation splits). To further clarify the training setup, in principle we could use all nodes for training. However for a fair comparison with other GNN methods we use only 80% of the nodes for training. For supervised methods our split of 80% 10% 10% is a standard split. For the non-GNN methods, all nodes are used for training.
0% of the labels in training. As DIGRAC is a self-supervised method
For both synthetic and real-world data sets, we extract the largest weakly connected component for experiments, as our framework could be applied to different weakly connected components, if the digraph is disconnected. Isolated nodes do not include any imbalance information. As customary in community detection, they are often omitted in real networks. When "ground-trutte is given, test results are averaged over 10 different data splits on one network. When no labels are available, results are averaged over 10 different data splits.
Averaged results are reported with error bars representing one standard deviation in the figures, and plus/minus one standard deviation in the tables.
Our synthetic data, DSBM, which we denote by DSBM (M, 1 (ambient)) n, K, p, p. 1)), is built similarly to (Cucuringu et al. (200aa) but with possibly unequal cluster sizes: (1) Assign cluster sizes no S n1 S ... S ng with size ratio p 2 1 as follows. If p- = then the first K
clusters have the same size n/ KJ and the last cluster has size (K [)[n// KJ If p > 1, we set
Po = - Solving _K- p6ng- = n and taking integer value gives nog = [n(1 Po) - p )
Further, set n,, = [ for i -= 1,... K 2 if K > 3, and π--1 n - i n. Then the ratio of the size of the largest to the smallest cluster is approximately p5 K p. (2) Assign each node randomly to one of K clusters, so that each cluster has the allocated size. (3) For node
0; Uj E Ca. independently sample an edge from node e; to node Uy with probability p FR.M- (4) For each pair of different clusters C, Cj with is # I, for each node U, E Ct. and each node By E C₁. independently sample an edge from node U, to node Bi with probability p F
For real-world data sets, we choose the number K of clusters in the meta-graph and the number 8 of edges between clusters in the meta- pett-graph as follows. As they are needed as input for DIGRAC, we resort to Herm rw (Cucuringu et al. 2020a) as an initial view of the network clustering. When suitable meta-graph is suggested in a previous publication, then we use that choice. Otherwise, the number K of clusters is determined using the clustering from Herm_re __w__w_w____ First, we pick a range of K, and for each K, we calculate the global imbalance scores and plot the predicted meta-graph flow Herm_rw. matrix F' based on the clustering from Herm rw. Its entries are defined as
Fkk, = L(W Ci) WCC. > 0) X W(C,,C)
(12)
C
18

---

Under review as a conference paper at ICLR 2022
These entries can be viewed as predicted probabilities of edge directions. Then, we choose K from this range so that the predicted meta- -rapp flow matrix has the highest imbalance scores and strong imbalance in the predicted meta-graph flow matrix.
The choice of 3 is follows. We plot the ranked pairs of Ciplain values from Herm_ry and select the which is at least as large as K- 2, to allow the meta-graph to be connected, and which corresponds to large drop in the plot.
Here we provide a brief description for each of the data sets; Table B gives the number, n, of nodes, the number. [g], of directed edges, the number [8T), of reciprocal edges (self-loops counted once and for и & v, a reciprocal edge u - U, + u is counted twice) as well as their percentage among all edges, for the real-world networks, illustrating the variability in network size and density (defined as [ma/[m( 1)
Telegram (Bovet & Grindrod 2020) is pairwise influence network between n 245 Telegram
channels with |&| 8, 912 directed edges. It is found in (Bovet & Grindrod 2020) that this network
reveals a core- core- peripeeryy structure in the sense of (Elliott et al. 2020). Following (Bovet & Grindrod 2020) we assume K = 4 clusters, and the core- pore-periphery structures gives 3 = =.
Blog (Adamic & Glance| 2005) records El = 19, 024 directed edges between n = 1, 212 political blogs from the 2004 US presidential election. In Adamic & Glance (2005) it is found that there is an underlying structure with K = 2 clusters corresponding to the Republican and Democratic parties.
Hence we choose K = 2 and 8 = 1.
Migration (Perry) 2003) reports the number of people that migrated between pairs of counties in the US during 1995-2000. It involves
075 countries and ||| 721, 432 directed edges after obtaining the largest weakly connected component. We choose K = 10 and B = 9, following
(Cucuringu et al.] (2020a). Since the original digraph has entries extremely large, cope with these outliers, we preprocess the input network by
Aij I(A.j > Vi,j (1, (1, ,n),
Aij Aij + j.i
(13)
which follows the preprocessing of (Cucuringu et al. 2020a). The results for not doing this prepro- cessing is provided in Table TT
WikiTalk (Leskovec et al. 2010) contains all users and discussion from the inception of Wikipedia until Jan. 2008 The n = 2, 388, 953 nodes in the network represent Wikipedia users and a directed edge from node v to node by denotes that user edited at least once a talk page of user j. There are E3 = 5,08 445 edges. We choose K = 10 clusters among candidates {2, 5, 6, 8, 10). and 3= 10.
Lead-Lag (Bennett et al. 2021) contains yearly lead-lag matrices from 269 stocks from 2001 to 2019. We choose K 10 clusters based on the GICS industry sectors (Phillips & Ormsby 2016). and choose 3 = 3 to emphasize the top three pairs of imbalance values. The lead lead-lag matrices are built from time series of daily price log returns. detailed in Bennett et al. (202T). The lead-lag metric for entry (i.j) in the network encodes a measure of the extent to which stock i leads stock and is obtained by applying a functional that computes the signed normalized area under the curve (auc) of the standard cross-correlation function (ccf). The resulting matrix is skew-symmetric, and entry (i,j) quantifies the extent to which stock leads or lags stocks j. thus leading to a directed network interpretation. Starting from the skew-symmetric matrix, we further convert negative entries to zero, so that the resulting digraph can be directly fed into other methods; note that this step does not throw away any information, and is pursued only render the representation of the digraph consistent with the format expected by all methods compared, including DIGRAC. Note that the statisties given in Table 3 are averaged over the 19 years.
Table 3: Summary statistics for the real-world networks.
data set
|
density
weighted
gr
[8 (%)
Telegram
245
8,912
1.28
10 1
True
1,572
17.64
Blog
1,222
19,024
1.49
10
True
4.617
24.27
Migration
3,075
721,432
7.63
10
True
351,100
48.67
WikiTalk
2,388,953
5,018,445
8.79
10-7
False
723,526
14.42
Lead Lag
269
29.159
4.04 10
True
0.00
0.00
19

---

Under review as a conference paper at ICLR 2022
As input features, after obtaining eigenvectors from Hermitian matrices constructed in Cucuringu (et al. (2020a), we standardize each column vector so that it has mean zero and variance one. We use these features for all GNN methods except MagNet, since MagNet has its own way of generating random features dimension one.
B.4 HYPERPARAMETERS
We conduct hyperparmeter selection via greedy search. To explain the details, consider for example the following synthetic data setting: DSBM with 1000 nodes, 5 clusters, P 1, and p 0.02, without ambient nodes under different hyperparameter settings. By default, we use the loss function and no seed nodes. Instead of grid search, we tune
32 hidden units, hop hyperparameters according to what performs the best in the default setting of the respective GNN method. The procedure starts with a random setting. For the next iteration, hyperparameters are set to the current best setting (based on the last iteration), independently. For example, if we start with a 1 = 2, c 3, and we find that under this default setting, the best a (when fixing = 2, c 3) 1.c 3) is 3, and the best is 3 (when fixing = 1, = 2), 3. two settings give similar results, we choose
is 2 and the best (when fixing
then for the next iteration, we set a = 2, b = 3, the simpler setting, for example, the smaller hop size. When reach local optimum, stop searching. Indeed, just a few iterations (less than five) were required for us to find the current setting, DIGRAC tends be robust most hyperparameters.
Figure 9 and 10 are plots corresponding to the same setting but for three different meta-graph structures, namely the complete meta-graph structure, the cycle structure but with ambient nodes, and the complete structure with ambient nodes, respectively.
In theory, more hidden units give better expressive power. To reduce complexity, we use 32 hidden units throughout, which seems to have desirable performance. We observe that for low-noise regimes, more hidden units actually hurt performance. We can draw similar conclusion about the hyperparameter selection. In terms of r, DIGRAC seems to be robust to different choices. Therefore, we use 0.5 throughout.
1.0
1.0
1.0
8
0
0.8
16
0.8
0.8
0.1
0.6
32
0.6
0.6
0.5
64
1
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.1
0.2
0.3
n
Vary d.
(b) Vary the hop h.
(c) Vary т.
Figure 8: Hyperparameter analysis on different hyperparameter settings on the complete DSBM with 1000 nodes, clusters, p = 1, and p = 0.02 without ambient nodes.
8
2
0
0.6
16
0.6
3
0.6
0.1
32
0.5
60.4
64
@0.4
00.4
0.2
0.2
0.0
0.0
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.3
(a) Vary d.
(b) Vary the hop h.
(c) Vary т.
Figure Hyperparameter analysis on different hyperparameter settings on the complete DSBM with 1000 nodes, 5 clusters, / and p 0.02 with ambient nodes.
20

---

where S C yoodd X /seed x ssedd is a set of node triplets: is anchor seed node, and vy is seed node from the same cluster as the anchor, while Us is from a different cluster; and CS(z,, 2,) the cosine similarity of the embeddings of nodes v; and vy. We choose cosine similarity sensitivity to the magnitude of the embeddings. The triplet loss designed so that, given two seed Under review as a conference paper at ICLR 2022
0.6
8
0.6
2
0.6
0
16
0.1
0.4
0.4
0.4
0.5
64
AR
1
0.2
0.0
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
(a) Vary d.
(b) Vary the hop h.
(c) Vary т.
Figure 10: Hyperparameter analysis on different hyperparameter settings on the cycle DSBM with 1000 nodes, 5 clusters, P 1, and p 0.02 with ambient nodes.
B.5 USE OF SEED NODES IN A SEMI-SUPERVISED MANNER
B.5.1 SUPERVISED LOSS
For seed nodes in yood, similar the loss function in Tian al. 2019), supervised loss function the sum of a cross-entropy loss and a triplet loss. The cross-entropy loss is given by
K Σ
LCr
Σ Vs k=1
(vr E log ((P:)))
(14)
Dreed
where the indicator function, Cs denotes the w cluster, and (D:)a denotes the 5 entry of probability vector (p,). With the function L _² + IR given by L(x, y) [x y/+ (where the subscript + indicates taking the maximum of the expression value and 0), the triplet loss is defined as
Luipleet
Σ (CCS(Z;,2)) CS(2i, 22)) (N..SS9E)EES
(15)
S
to avoid
nodes from the same cluster and one seed node from different cluster, the respective embeddings of the pairs from different clusters should be farther away than the embedding of the pair within the same cluster.
We then consider the weighted sum LCE + "teppippee as the supervised part of the loss function for DIGRAC, for some parameter "/e 0. The parameter "t arises as follows. The cosine similarity between two randomly picked vectors in d dimensions is bounded by /In(d)/d with high probability. In our experiments d = 32, and / /In(2d)/ (2d) 0.25. contrast, for fairly uniform clustering, the cross-entropy loss grows like n. which in experiments ranges between 3 and 17. Thus some balancing of the contribution is required. Following (Tian et al.) 2019), we choose % = 0.1 in our experiments.
B.5.2 OVERALL OBJECTIVE FUNCTION
By combining Eq. 14p. Eq. (5 and Eq. (3. our objective function for semi-supervised training
with known seed nodes minimizes
Asort
+ 7/s (LCF. + 74 Criptee)
(16)
where Ye. Yt O are weights for the supervised part of the loss and triplet loss within the supervised part, respectively. We set 7 = 50 as we want our model to perform well on seed nodes. The weights could be tuned depending on how important each term is perceived to be.
21

---

Under review as a conference paper at ICLR 2022
B.6 TRAINING
For all synthetic data, we train DIGRAC with maximum of 1000 epochs, and stop training when no gain in validation performance is achieved for 200 epochs (early-stoppnng. For real-world data, no "ground-truth" labels are available; we use all nodes to train and stop training when the training loss does not decrease for 200 epochs, or when we reach the maximum number of epochs, 1000.
For the two-layer MLP, we do not have bias term for each layer, and we use Rectified Linear Unit (ReLU) followed by a dropout layer with 0.5 dropout probability between the two layers, following (Tian et al. 2019). We use Adam (Kingma & Ba, 2014) as the optimizer and &g regularization with weight decay 5 10 to avoid overfitting. We use as learning rate 0.01 throughout.
B.7 IMPLEMENTATION DETAILS FOR THE COMPARISON METHODS
In our experiments, we compare DIGRAC against five spectral methods and five GNN-based supervised methods on synthetic data, and spectral methods on real data. The reason we are not able to compare DIGRAC with the above GNNs on these data sets is due to the fact that these data sets do not have labels, which are required by the other GNN methods. We use the same hyperparameter settings stated in these papers. Data splits for all models are the same; the comparison GNNs are trained with 80% nodes under label supervision.
For MagNet, we use g 0.25 for the phase matrix in /Zhang et al. (2021b), because it is mentioned that q = 0.25 lays the most emphasis on directionality, which is our main focus in this paper. Code for MagNet is from http::ttpt/// htt//githuuu com thw h hirn magnet We use the code from
code/digen py to obtain the log of probability matrix P for the methods DiGCN and DiGCN app. The only difference between these two methods is whether or not to use approximate Laplacian based on personalized PageRank. The "adj_type" options for them correspond to "or" and "appr". respectively.
ob/ main/ /ode// / digenn ibc py with option "adj_type" equals "ib". As recommended option in (Tong et al. (020aa), we use three layers for DiGCN jb and two layers for DiGCN and DiGCN_app All other settings are the same in the original paper (Tong et 2020a).
For DiGCN ib, we use the code
B.8 ALGORITIM AND COMPLEXITY ANALYSIS
To avoid computationally expensive and space unfriendly matrix operations, as described in Eq. the main text, DIGRAC uses efficient sparsity- implementation, described in Algorithm I. without explicitly calculating the sets of powers A and A We omit the subscript V for case of notation. The algorithm is efficient in the sense that it takes sparse matrices as input, and never explicitly computes a multiplication of two n x n matrices. Therefore, for input feature dimension din and hidden dimension d, if d' max (ax d) < n, time and space complexity of DIMPA, and implicitly DIGRAC, is O(E d' + 2nd K) and ((2))) + 4nd' + nK), respectively (Harrison & Joseph 2018 Greiner & Jacob 2010).
Indeed, it is a current shortcoming of DIGRAC that it does not scale well to very large networks; however, this limitation is also shared by all the GNN competitors compared against in the paper, and some of the spectral methods. DIGRAC scales well in the sense that when the underlying network is sparse, the sparsity preserved throughout the pipeline. In contrast, Bi_sym and DD DD>_ymm (Satuluri & Parthasarathy 2011) construct derived dense matrices for manipulation, rendering the methods no longer scalable. These methods resulted in N/A values in Table [ in the main text. For large-scale networks, DIMPA is amenable to minibatch version using neighborhood sampling, similar to the minibatch forward propagation algorithm in Hamilton et al.] (2017): Markowitz et al. (2021). We also aware of framework (Fey et al. (022) for scaling up graph neural networks automatically. where theoretical guarantees are provided, and ideas there will be exploited in future. We expect that the theoretical guarantees could be adapted to our situation.
22

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Weighted Mupt Neighbor Aggregation (DIMPA).
Input (Sparse) row-nornne now-normalized adjacency matrices A", AA; initial hidden representations H H"; hop hhh 2); lists of scalar weights
S2 = (w M E As,)), ) St (wM M E AAth)..
Output: : Vector representations 2, for all 02 V given by Z.
X < A H
X - A HH Z
Z [+[0
H [2 X
0000
H +0 x
for i f 2 h do
X + A X*:
+ Z + 52 X;
7'
end
= CONCAT (Z',2) Z²);
C MORE RESULTS ON SYNTHETIC DATA
C.I AN ADDITIONAL META-GRAPHI STRUCTURE
Recall that the Directed Stochastic Block Models used in our experiments depend on a meta-graph adjacency matrix F and filled version of it, F, for some number of clusters, K, and noise level 7 S 0.5. The meta-graph adjacency matrix F is generated from some meta-graph structure, called M. Based on .M, the filled meta-graph F replaces every zero in F that is not part of the imbalance structure with 0.5, independently of the choice of 17. It is the filled meta-graph F which we feed into the DSBM generation process. The filled meta-graph creates number of ambient nodes which correspond to entries which are not part of the imbalance structure and thus are not part of a meaningful cluster; the set of ambient nodes is also called the ambient cluster.
Here, we introduce an additional meta-graph structure, called "multipartite,, following (Elloo et al. 2019). First, when there are ambient nodes: we divide the index set into three sets; setting K
11,22
3K + i1, let
9
FL.1
(1- < i1 <(< +1 k < b2 12 in) (1-n))((2> 2 i S i2) n1 < k < iz i1).
When we have ambient nodes, the construction involves two steps, with the first step the same as the above but with the following changes: divide the indices into three sets, with set boundaries given by K-1 1, 3(K-1) é1. The second step is to assign 0 (respectively, 0.5) to the last row and the last column of F (respectively, F).
9
C.2 ADDITIONAL COMPARISON PLOTS AND ANALYSIS
Figure [1 compares the numerical performance of DIGRAC with other methods except InfoMap. which performs rather poorly in our synthetic experiments in the main text, on four more settings of synthetic data, namely, a cycle structure with three clusters, a complete structure with ten clusters, multipartite structure with clusters all nodes into one big cluster for all of our synthetic experiments. Considering the results in Section 5 and Figure II] we remark that DIGRAC gives state-of- sfate-of-the-asd art results on a wide range of network densities and noise levels, on different scales of the networks, and with different meta-graph structures, whether or not ambient nodes exist.
clusters, and star structure with five clusters. Indeed, Infomap
Note that the multipartite, the cycle and the star settings correspond to the intuition behind (Tong ett al. 2020a) which assumes that nodes are similar if their set of - neighborhoods are similar; here the second-order neighborhoods meta-graph structure "star", "cycle" or "multipartite", clusters could be determined by grouping nodes that share similar nn-neighbors and net-neigs together, which aligns well with the second-order proximity used in DGCN and DIGCN ib from (Tong et al., 20206). Therefore, these methods naturally well-suited for dealing with the such synthetic data. We also note that although
similar by design. For networks with underlying
23

---

Under review as a conference paper at ICLR 2022
1.0
1.0
Bi_sym
DD 5__ym
0.8
0.8
0.5
Herm_rw
0.6
MagNet
AR
0.4
DIGON
0.4
DGCN
0.2
DIGCN app
0.2
DIGCN ib
0.0
DIGRAC
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
n
DS F,
(b) DSBM "complete", T.
1000, K 3, = 0.1,p 1)
71
1000, K 10, p = 0.1, = 1)
0.35
0.6
0.30
0.5
0.25
0.4
0.20
503
40.15
0.10
0.2
0.05
0.1
0.00
0.0
0.0
0.1
0.2
0.3
0.4
0.0
0.1
0.2
0.3
0.4
7
(c) DSBM "multipartite", T, n 1000, = 1 0.1, p
(d) DSBM "star", n = 5000, = 5,p p=
Figure 11: Node clustering test ARI comparison four additional synthetic data sets. Dashed lines highlight DIGR AC's performance. Error bars are given by one standard error. Abbreviations for all the methods are given in Section 4 in the main text.
DIGRAC does explicitly use second-order proximity, it can achieve comparable performance with DGCN and DiGCN ib. This indicates DIGRAC's flexibility to adapt to directed networks with different underlying topologies, without explicitly utilizing higher-order proximity. On the other hand, DiGCN ib is fully supervised, and takes much more space and time to implement, than DIGR AC. This is partially due to the use of the so-called inception blocks in DiGCN ib, where multi- scale directed structure features are encoded and fused with a fusion function. As stated in Tong al. (2020a), the worst space complexity is (k'n)²) n²), where k' is the order of proximity to consider (we use k" = 2 throughout). The eigenvalue decomposition in the preprocessing step is O(r)). We also remark that the approximate Laplacian based on personalized PageRank, when no inception blocks used, performs no better than the simpler implementation without the approximation. We conclude that overall DIGRAC is a fast method for general directed clustering when directionality is the main signal, which performs well cuiooe- methods when the proximity neighborhood heuristic holds, while outperforming all tested methods on the complete meta-graph, where the proximity neighborhood heuristic does not hold.
D ADDITIONAL RESULTS ON REAL-WORLD DATA
D.1 EXTENDED RESULT TABLES
Tables 5 6 and provide detailed comparison of DIGRAC with spectral methods. Since
labeling information available and all the other competing GNN methods require labels, we do not compare DIGRAC with them these real data sets.
24

---

Under review as a conference paper at ICLR 2022
In Tables 4 and report 12 combinations of global imbalance scores by data set. The naming convention of these imbalance scores is provided in 2 To assess how balanced our recovered clusters are in terms of sizes, also report the size ratio, which is defined as the size of the largest predicted cluster to the smallest one, and the standard deviation of sizes, size std, in order to show how varied the sizes of predicted clusters are. For relatively balanced clustering, we expect the latter two terms to be small.
Table 4: Performance comparison Telegram. The best is marked in bold red and the second best marked in underline blue.
Metric/Method
InfoMap
Bi symyy
DD sym DD_sym
DISG LR
Herm
Herm rw
DIGRAC
Ogat
0.0410.00
0.2110.00
0.2110000
0.2110001
0.20
0.1410.00
0.32.10.01
Oeat
vol
0.47
0.6710000
0.611:0.00
0.66:10.02
0.66:10.2
0.19100.00
0.79:10.06
0.03
0.20-10.00
0.20110.00
0.2011001
0.1910.01
0.12:10.00
0.29110.11
vol max
plain
1.00:10.00
0.80+00.00
0.75+00.0
0.78++0.03
0.76+0004
0.59+0000
0.96+
0.01
0.26++0.0
0.26++0.00
0.26++0001
0.25+0002
0.35++0.00
0.28+
sum
Ond
Vvo_mmn
0.16++0.00
0.84+-0.00
0.76++0.00
0.82++0.03
0.82++0.03
0.49+00.0
0.73++0.03
Oni max
0.01
0.25++0.00
0.25++0.00
0.25
0.24
0.29++0.00
0.25+00.01
Oni
0.68+0.00
1.00
0.94
0.98
0.95
0,99+00.00
0.90:10.05
nuiive
0.01=0.00
0.26=+000
0.26++0.00
0.26#0.01
0.25
0.23+0000
0.27
sum
Oaive
mii
0.11=0.00
0.84=0.00
0.76+10.00
0.82+0003
0.82++0.3
0.32
0.72
haave
0.00=0.00
0.25
0.25
0.25+
0.24
0.20
0.24
Onaive
0.63
1.00
0,94+0000
0.98
0.95
0,99+0.00
0.89
size ratio
24.750
242.000
242.000
242.000
242.00
53
3.090
size std
35.57
104.360
104.360
104,360
104.360
63,460
26.39
Table 5: Performance comparison on Blog. The best is marked in bold red and the second best marked in underline blue.
Metric/Method
InfoMap
Bi_sym
DD_sym
DISG JR
Herm
Herm_re _rw
DIGRAC
O
vll som
katt
0.07+10.00
0.07-10.00
0.00.10.00
0.05
0.37+10.00
0.00.10.00
0.44:1:0.00
0.02:10.00
0.33+10.00
0.051:0.00
0.31
0.78:10.01
0.89-10.00
0.76:10.00
val min
Oee
0.05
0.05-10000
0.00+10.00
0.04
0.26+10.00
0.00-10000
0.40-10.00
yoot
1.00=0.000
0.33+0.00
0.05++0.00
0.31
0.78+0.01
0.89:10.00
0.76++0.00
plain
Ond
0.00=0000
0.07=0.00
0.00+0000
0.05
0.37=0000
0.00
0.44
Old
0.00=0.00
0.33+0.00
0.05++0.00
0.31
0.78=0.01
0.89:10.00
0.76++0.00
0.00=0.00
0.05=0000
0.00+00.0
0.04
0.26=00.0
0.00=00.00
0.40
vol
sid
0.7310.00
0.3310.00
0.05100.00
0.3110.00
0.78.10.01
0.89110.00
0.76.10.00
plain
0.00
0.07110.00
0.00100000
0.05100000
0.37+10.00
0.00.10.00
0.44
vol sum
naive
0.00
0.33
0.05110.00
0.31
0.78+10.01
0.89:10.00
0.76.10.00
vol
vol. max
0.00=00000
0.05+00000
0.0010000
0.0410000
0.26=10.00
0.00+10.00
0.40
0.76=+0.00
0.33+0000
0.05110.00
0.31
0.78
0.89:10.00
0.76:10.00
size ratio
1.270
8.700
2.450
6.100
11.93
44.26
1.860
size std
64.50
485
256.200
439
516.500
584
183.20
Tables 4 5 7 and [0] that DIGRAC provides competitive global imbalance scores in all of the 12 objectives introduced, and across all the real data sets, usually outperforming all the other methods. Among the tables, Table T0 provides results in terms of the distance to the best yearly performance, averaged across the 19 years; DIGRAC usually outperforms all the other methods across all the years. Note that Bi sym and DD sym are not able generate results for WikiTalk, as large n X n matrix multiplication with its transpose causes memory issue, when n = 2, 388, 953. Small values of the size ratio and size standard deviation suggest that the normalization in the loss function penalizes tiny clusters, and that DIGRAC tends to predict balanced cluster sizes.
25

---

Under review as a conference paper at ICLR 2022
Table 6: Performance comparison Migration. The best is marked in bold red and the second best marked in underline blue. InpoMap results are omitted here as it predicts single huge cluster and could generate imbalance results.
Metric/Method
Bi_ym
DD_sym
DISG
Herm
Herm_rv
DIGRAC
Sort
0.03+0.00
0.01+00.00
0.02+40.00
0.04+0.00
0.02++0.00
0.05+10.00
O
moi
0.19:0000
0.08+0.00
0.08
0.15=0002
0.05++.00
0.18+0.03
O
0.03:10.00
0.01110.00
0.01110.00
0.03:10.00
0.02-10.00
0.04
vol
Sart
0.24:10.00
0,20110.00
0.1710.00
0.40:10.01
0.49-10.06
0.29:10.04
0.01
0.01100.00
0.01
0.02:10.00
0.02-10000
0.04110.01
Vel sum
Ond
0.10:00.00
0.05++0.00
0.05+0000
0.08
0.04+00000
0.16+00.33
O vol max
0.01
0.01
0.01
0.01
0.01+00.00
0.03
0.13+00.00
0.12+00.00
0.11+0.00
0.20+#0001
0.20++0.01
0.26++0.01
plain
O sum
0.01+0.00
0.01+00000
0.01
0.02++0.00
0.01+00.00
0.04++0.01
naive
0.09+00.00
0.04++0.00
0.04+0.00
0.08+00001
0.01++0.00
0.16+00.03
O Vol max
0.01=:0.00
0,00110.00
0.01
0.01=00.00
0.00+00.00
0.03
O
nalve
0.12:40.00
0.10:00.00
0.08
0.19=00.0
0.19::0.33
0.26:10.01
plain
size ratio
7.780
6.070
4,360
36.05
1035,90
4.420
size std
135.210
132.76
103.43
335.790
353.060
264.500
Table 7: Performance comparison WikiTalk. The best is marked in bold red and the second best is marked in underline blue. InfoMap results are omitted here as its large number of predicted clusters leads to memory error in imbalance calculation.
Metric/Method
DISG LR
Herm
Herm rw
DIGRAC
Surt Jum
0.18++0.03
0.15+00.22
0.00+-0.00
0.24+L0.05
O mii
0.10:10.03
0.2210005
0.26:10.00
0.28:10.13
O
0.16.10.03
0.0910.01
0.00-10.00
0.19.10.04
Vol. max
0.87-10.08
0.9910.01
0.98-10.00
1.00.10.00
O vol Jum
0.17++0.04
0.06+0.01
0.01++0000
0.14+H0.02
sid
0.09++0.02
0.09+0002
0.27-10.00
0.18++0.08
O vol. man
0.15++0.04
0.04
0.00+F0000
0.1 0.11--0.02
sid
0.72++0.03
0.70++0.05
0.98-10000
0.84
O vol. Jum taave
0.10--0.02
0.04
0.00-10.00
0.12
0.06+:0.03
0.07
0.26:10.00
0.15++0.07
O voL maax
thive
0.09+0002
0.03
0.00=E0.00
0.09
O
nuvve
0.64+0000
0.61+0.04
0.98+10.00
0.76+
plain
size ratio
1190162.25
2217434.50
250.48
71765.14
size std
713813.72
660060.33
657941.88
643220.37
26

---

Under review as a conference paper at ICLR 2022
Table Performance comparison on Lead-Lag for year 2015. The best marked in bold red and the second best is marked in underline blue, InfoMap results are omitted here as it usually predicts single huge cluster and could not generate imbalance results.
Metric/Method
Bi_sym
DD_sym
DISG_LR
Herm
Herm_rw
DIGRAC
Son
0.07++0.00
0.07++0.00
0.06++.000
0.07++0.00
0.06++0.01
0.15+0.00
sum
O
0.53++0.06
0.50+F0.02
0.45+0000
0.50+0003
0.46++0.06
0.50++0.02
vol min
son
0.07++0.00
0.06++0.00
0.06++0.00
0.06++0.00
0.06+0.00
0.15+00001
sort
0.65+00.03
0.67++0.03
0.59+#0.03
0.65++0.03
0.65++0.02
0.55+00.07
plain
Odi sum
0.04:10.00
0.04:10.00
0.0410.00
0.04=10.00
0.04:10.00
0.11:10.02
Osii
0.27+10.03
0.271:0.02
0.24+0.02
0.27+:0.2
0.26:10.04
0.35:10.04
Odd
VoL max
0.03=00.00
0.03+10.00
0.03
0.03=00.00
0.03:10.00
0.10110.02
Rid
0.39::0.2
0.39:10.11
0.37
0.39=:002
0.40:10.02
0.38+00.04
plain
O vol
0.03-10.00
0.03
0.03
0.03:10.00
0.03+10.00
0.08
huive
0.20-10.02
0.20.10.02
0.17
0.20
0.20.10.03
0.25
min
O
0.02-10.00
0.03.10.00
0.02
0.03
0.03.10.00
0.08
vol mas
nEtVE
0.29110.11
0.2910.01
0.2610.02
0.30
0.30.10.01
0.31
plain
size ratio
3,070
3,110
3,060
2.89
2.95
15.640
size std
8.390
7.94
8.680
7.28
8.050
18.680
Table Performance comparison on Lead-Lag. Results in each year is averaged over ten runs. Mean and standard deviation (after =) are calculated over the 19 years. The best is marked in bold red and second best is marked in underline blue, InfoMap results are omitted here as usually predicts single huge cluster and could not generate imbalance results.
Metric/Method
Bi_ symsym
DD_sym
DISG
Herm
Herm_re rrw
DIGRAC
sort
0.07-10.01
0.07-10.01
0.07.10.01
0.07-10.02
0.07-10.02
0.15:10.03
O Nun
0.51
0.48110.09
0.4710.10
0.51
0.50:10.10
0.47:10.09
min
O
0.07+10.11
0.06+10.01
0.06+10.01
0.07+0001
0.07+00.1
0.14110.03
vol max
0.66:10.09
0.64:10.08
0.63
0.66=10.09
0.65+00.09
0.53+0.09
0.04+0.01
0.04++0.01
0.04
0.04=0001
0.04+:0.1
0.12+00.33
voL.um
sld
0.27+40.04
0.27++0.04
0.25+0004
0.27++0.3
0.27++0.03
0.38
sld
0.04
0.03+0.00
0.03+0.00
0.03+0000
0.03+00.0
0.11
voLmma
sld
0.40-10.05
0.3910.05
0.3810005
0.40.10.05
0.40-10.05
0.44.10.07
Razve
0.03-10.01
0.0310001
0.0310001
0.03
0.03100.11
0.08
vol sum
nuvve
0.20:10.05
0.19110.5
0.1810.05
0.1910.04
0.19100.4
0.26.10.10
O Rnive
0.03100011
0.0210.01
0,0210.01
0.02+00.00
0.02+10.00
0.08:10.03
VOL max
nuive
0,30
0.2810.06
0.2740.06
0.29
0.29:10.5
0.3210.11
size ratio
3.67
3.34
3,900
4.110
3.880
8.070
size std
9.31
9.14
10.090
10.490
10.360
17.060
27

---

Under review as a conference paper at ICLR 2022
Table 10: Performance comparison on Lead-Lag, where we evaluate the performance distance to the best one in each year. Results in each year averaged over ten Mean and standard deviation (after =) are calculated over the 19 years. The best marked bold red and the second best is marked in underline blue. InfoMap results are omitted here usually predicts single huge cluster and could not generate imbalance results.
Metric/Method
Bi_yym
DD_sym
DISG DISG_LR
Herm
Herm_rw
DIGRAC
Outi vol.um
Sor
0.07=0002
0.08+1002
0.08
0.07=0.02
0.07+0002
0.00:10.00
0.01110.0
0.05
0.061:000
0.02:10.02
0.02+10.02
0.06:10.04
O soit
0.07++0.02
0.07+:0.02
0.07+00.2
0.07+10.02
0.07-10.02
0.00-10.00
man
O
0.01-:0.02
0.03+-0.03
0.05
0.01
0.02-+:002
0.14++0.03
plain
Sid
0.08+10.02
0.08+10.02
0.08+10.02
0.08++0.02
0.08+10002
0.00:10.00
0.10+0.05
0.11#:004
0.13
0.11=0005
0.11=:0.05
0.00
VoL mii
Old
0.07+00.0
0.08++002
0.08
0.08
0.08+00.02
0.00+10.00
O plain
0.04=00.03
0.05++004
0.06
0.04=0.04
0.04+00.03
0.00
luive
0.05++0.03
0.06++0.03
0.06+0.03
0.05+00.33
0.05++0.03
0.00-10.00
O vol mia
0.06+00.07
0.07++0.06
0.08
0.07=00.08
0.07+:0.08
0.00
Bulve
0.05:10.03
0.05110.03
0.05
0.05+10.03
0.05+10.03
0.00:10.00
O plain
0.03:10.06
0.05
0.06100.06
0.04
0,04:10.06
0.01:10.02
size
1.04
0.71
1.270
1.480
1,250
5.440
size
0.58
0.41
1,360
1.770
1.630
8.340
28

---

Under review as a conference paper at ICLR 2022
DIGRAC
InfoMap
1.4
sym
3.0
DD
2.5
DISG LR
Crotun ranked
Herm
0.8
Hern
Crod Jom
0.6
0.0
0.0
3.5
Cipisin ranked pairs
0.8
Cheines rankee
0.6
2.0
1.5
0.2
2
2
Figure 12: Ranked pairs of pairwise imbalance recovered by comparing methods for different choices of normalization on the Telegram data set. Lines used to highlight DIGRAC's performance.
D.2 RANKED PAIRWISE IMBALANCE SCORES
We also plot the ranked pairwise imbalance scores for all data sets except Blog, which has only one possible pairwise imbalance score. For Lead-Lag, we only plot the year 2015 as an example; the plots for other years are similar. Figures 12 14 and 15 illustrate that DIGRAC able to provide comparable or higher pairwise imbalance scores for the leading pairs, especially on Crvolmin pairs. We also observe that except for Cyplain DIGRAC has a less rapid drop pairwise imbalance scores after the first leading pair compared to Herm and Herm_rw rww which can have few pairs with higher imbalance scores than DIGRAC.
29

---

Under review as a conference paper at ICLR 2022
DIGRAC
Bi symm
CIe/omm ranked paits
0.8
DD Sym
C/ww.m rankee pairs
DISG LR
Herm
0.6
Herm rw
0.2
0.2
1.0
Ciplain ranked pairs
0.6
CINILA ranked
0.6
0.4
0.4
0.0
0.0
0
10
20
30
40
0
10
20
30
40
Figure 13: Ranked pairs of pairwise imbalance recovered by comparing methods for different choices of normalization on the Migration data set. Lines are used to highlight DIGRAC's performance. InfoMap results are omitted as it predicts one single huge cluster and could not produce imbalance results.
DIGRAC
DISG_LF LR
Cy ranked pains
Herm_ww
yo ranked
1.0
Cyea max ranked pairs
Cipiain ranked pairs
0.6
0.2
10
20
30
40
10
20
30
Figure 14: Ranked pairs of pairwise imbalance recovered by comparing methods for different choices of normalization Wikifalk data set. Lines are used highlight DIGRAC's performance. InfoMap results are omitted here because it triggers memory error due to the large number of predicted clusters.
30

---

Under review as a conference paper at ICLR 2022
1.75
DIGRAC
1.75
1.50
Bissym
1.50
3D_sym LR
Crolmni ranked parss
1.25
C) rances
1.00
Herm
1.00
Herm_nw
0.75
0.50
0.50
0.25
0.25
0.00
0.00
1.75
1.50
Ciplain ranked pairs
0.8
1.25
Chretee ranked
1.00
0.6
0.75
0.50
0.2
0.25
0.00
10
40
10
40
Figure 15: Ranked pairs of pairwise imbalance recovered by comparing methods for different choices of normalization Lead-Lag Lag data set. Lines used to highlight DIGRAC's performance. InfoMap results are omitted here because it only predicts a single cluster.
D.3 PREDICTED META-GRAPH FLOW MATRIX PLOTS
For each data set, plot the predicted meta-graph flow matrix F' defined in Eq. (12
From Figure 16 we conclude that DIGRAC is able recover directed flow imbalance between clusters in all of the selected data sets. Figure 16a shows a clear cut imbalance between two clusters, possibly corresponding to the Republican and Democratic parties. Figure plots imbalance flows in the real data set Telegram, where cluster 3 is a core-transient cluster, cluster is core-sink cluster, cluster, while cluster is a et al. 2020; Bovet & Grindrod (020). For WikiTalk, illustrated in Figure [6d]] the lower-triangulat part entries are typically source nodes for edges, while the upper-triand triangrrr part are target nodes. For Lead-Lag, taking the year 2015 as example, DIGRAC is also able to recover high imbalance in the data.
cluster 2 a periphery-upstreee
cluster (Elliott
We also note that DIGRAC would necessarily predict the same number of clusters assumed, so that we do not need to specify the exact number of clusters before training DIGRAC; specifying the maximum number of possible clusters suffices.
31

---

Under review as a conference paper at ICLR 2022
1
0
2
3
0
2
4
6
8
0.8
0
0
0.7
2
0.6
0.6
1
0.5
4
0.4
2
6
1
3
0.2
8
0.4
0.2
(a) Blog
(b) Telegram
(c) Migration
0
2
4
6
8
1.0
2
4
6
8
1.0
0
0.8
0.7
0.6
0.5
6
0.4
8
0.2
0.2
0.0
0.0
(d) WikiTak
(e) Lead-Lag 2015
Figure 16: Predicted meta-graph flow matrix from DIGRAC of five real-world data sets.
D.4 MIGRATION PLOOTS
compare DIGRAC to five spectral methods for recovering clusters for the US migration data set, and plot the recovered clusters map, in Figure 17
The visualization in Figure (a-c) shows that clusters align particularly well with the political and administrative boundaries of the US states, previously observed in InCuuuringu et al. (201). This outcome is not deemed too insightful, as it trivially reveals the fact there there is sigmificant intra- state and inter-state migration, and does not patterns between far-away states, and more generally, between regions which are not necessarily geographically cohesive.
any of the information latent migration
D.5 COPING WITH OUTLIERS
As mentioned in Section B.3 the preprocessing step to use ratio of migration instead of absolute migration numbers is way to cope with outliers (here, extremely large entries in the original digraph) in Migration. To validate the effectiveness of this approach cope with outliers, Table provides imbalance results for Migration when we do not transform the nonzero entries into ratios. Comparing with Table [6 we witness an overall decrease the performance. In this case InfoMap no longer predicts single huge cluster. However, its predicted number of clusters is about 44, which is too large. This also implies that InfoMap is very sensitive to the magnitude of digraph entries, while DIGRAC is not. Indeed, InfoMap gives 43 (too many) clusters for Blog, 19 (too many) for Telegram, I (too small) for Migration, and 17498 (far too many) for WikiTalk.
We compare DIGRAC to five spectral methods well as InfoMap for recovering clusters for the US migration data set without the preprocessing step discussed earlier, and plot the recovered clusters map in Figure 19 Note that all methods, except DIGRAC, recover either clusters which trivially small in size or contain one very large dominant cluster (as (a), (b), (c) and to some extent, also (f)). The DISG LR clustering and InfoMap clustering provide clear geographic boundaries, but
32

---

Under review as a conference paper at ICLR 2022
40
40
25
25
-90
-120
-330
-100
-90
-70
(a) Bi_sym
(b) DD_sym
10
40
40
LEB
35
-120
-110
-100
-90
-80
-70
-120
-110
-100
-90
-80
-70
(c) DISG_LE
(d) Herm
50
35
-120
-110
-100
-00
-80
-70
-120
-110
-100
-90
-50
-70
(e) Herm rw
(i) DIGRAC
Figure 17: US migration predicted clusters, along with the geographic locations of the counties as well as state boundaries (in black). InfoMap results omitted here because it only produces one huge cluster. The input data is normalized, following Eq.
were not able recover the imbalance among clusters. Other spectral methods generally have dominant cluster containing most of the nodes, whereas DIGRAC has more balanced cluster sizes.
When employing methods that symmetrize the adjacency matrix (as in (a) and (b)), the migration flows between counties in different states will be lost in the process. Furthermore, the visualization in Figure (c) shows that clusters align particularly well with the political and administrative boundaries of the US states, as previously observed in Cucuringu et al. (2013). The same is for Figure (d). This outcome not deemed very insightful, as trivially reveals the fact that there significant intra-state and inter-state migration, and does not uncover any of the information latent migration patterns between far-away states, and more generally, between regions which are not necessarily geographically cohesive.
Figure 18 further plots the top three pairs of clusters based on four different imbalance scores given by DIGRAC. As shown in the figure, DIGRAC uncovers the migration trend from outside to inside, across states. This trend of the directed flow agrees with that discussed Perry (003)), with many people migrating from New York and California the inner states.
E DISCUSSION OF RELATED METHODS THAT ARE NOT COMPARED AGAINST IN THE MAIN TEXT
To further emphasize the importance directionality, our synthetic data sets have no difference in density between clusters; their sole signal is in the directionality of the edges. If all edge directions
33

---

Under review as a conference paper at ICLR 2022
(a) Cr top pair
(b) Cruouum: 2nd pair
Croossm 3rd pair
(d) Cr top pair
Cruoumnn 2nd pair
Crrolmin 3rd pair
(g) CrvoLmax top pair
(h) Crolmmax 2nd pair
(i) Cpoommx 3rd pair
Clplain; top pair
(k) Ciplain; 2nd pair
(l) Cpiann; 3rd pair
Figure 18: US migration predicted cluster pairs with top imbalance, along with the geographic
locations of the counties well state boundaries (in black). Red (label 1) is the sending cluster while blue (label 2) is the receiving cluster. Yellow (label 0) denotes all the other locations being considered. Subcaptions show the imbalance score and the rank based on that score.
were be removed, then no algorithm out there should be available to detect the clusters. To further support our claim why some methods mentioned Section [ in the main text are not appropriate for comparison, have applied the default setting versions of the Louvain method (Dugué & Perez 2015), the Leiden algorithm Traag et al., 2019) and OSLOM (Lancichinetti et al. 2011). to our synthetic data sets, and find that they do not detect the structure in the data, with ARI and NMI values very close to zero, and very low imbalance values. In particular, Louvain and Leiden tend to give a larger number of clusters than the ground truth which is designed have small cluster sizes. OSLOM outputs clusters with extreme sizes, either a huge cluster containing (almost always) all the nodes, or every node forming cluster by itself.
On the real-world data sets, these methods often give numbers of clusters that do not match our expectations. (Blog has two underlying parties, Telegram has four-cluster core-periphery struc- ture). Louvain clusters nodes from Blog into 8-13 clusters (too many). Telegram into 4-5 clusters (acceptable), Migration into 5-7 clusters (acceptable). Wikifalk into 150-219 clusters (too many), and Lead-Lag into 10-55 clusters (acceptable or bit too many). Leiden gives 12 (too many) clusters for Blog, 4-5 for Telegram, 5-6 for Migration, 170-248 (too many) for WikiTalk, and 10-55 clusters (acceptable bit too many) for Leud-Lag. OSLOM gives 6 clusters for Blog (too many), 16 for Telegram (too many), ), and 46 for Migration (too many). could not generate results for WikiTalk after running for 12 hours, and hence omit its discussion here. On Lead-Lag, OSLOM places every node in a single cluster for most the years, and clusters the rest the years into either a huge single cluster two clusters.
34

---

Under review as a conference paper at ICLR 2022
Table 11: Performance comparison on Migration (without preprocessing). The best is marked in bold red and the second best is marked in underline blue.
Metric/Method
InfoMap
Bi_yym
DD_sym sym
DISG LR
Herm
Herm_rv rw
DIGRAC
0.02++0.00
0.03++0.00
0.01+-0.00
0.01+00.00
0.07++0.00
0.01++0.00
0.04+0..00
vol
0.241:000
0.201:001
0.1210.02
0.14
0.21=0001
0.05+0.02
0.1820002
Oset
min
0.02=10.00
0.03+10.00
0.01100000
0.01
0.06:10.00
0.00110.00
0.04:10.00
max
Ouerr
0.6110.000
0.46:10.00
0.2910002
0.26:10.00
0.62:10.02
0,40110.00
0.32:10.11
0.00++0.00
0.01+00000
0.00+-0.00
0.00++.00
0.02++0.00
0.00++0000
0.03++0.01
vol sum
O
0.03++0.00
0.09++0.00
0.044:0.01
0.05
0.08++0.01
0.02++:001
0.11+:0.03
0.00
0.01
0.00+10.00
0.00
0.01
0.00+10.00
0.02:10.01
vol max
Oid
0.19
0.23
0.14100.11
0.12
0.32
0.25:10.01
0.21
O sum
0.00=0000
0.01
0.00+0.00
0.00
0.02==0.00
0.00=00.00
0.03
huive
0.02=#0.00
0.08
0.04+0001
0.05
0.08
0.02++0.01
0.11+
O faive
0.00=00000
0.01
0.00+0.00
0.00+0.00
0.01=00.00
0.00+00.00
0.02++0.01
maa
plain
haive
0.16++0.00
0,22+00.0
0.13+0.01
0.11+0.00
0.31
0.22++0.00
0.21++0033
size ratio
8,500
3043.80
722.620
25.780
3059.20
415.880
203.230
size std
58.96
912.100
861.280
409.900
917.230
844.750
342.38
None of the methods outperform DIGRAC on our chosen performance measures from Table except on the Lead-Lag data set. With regards to the 12 imbalance measures from Table S leaving out OSLOM before, Louvain and Leiden perform poorly all of the real data sets, except Lead-Lag. Indeed, for Lead-Lag. the number clusters we use for DIGRAC is ten according to the GICS sector memberships. However, if values are poor, which implies that ten may not be a desirable choice of the number of clusters. Further, DIGRAC usually clusters the nodes into smaller number of clusters, while Louvain and Leiden usually cluster the nodes into a larger number of clusters (usually around 30, and sometimes above 50 clusters).
the sector memberships as labels, the imbalance
Performance comparison on Lead-Lag, including Louvain and Leiden. Results in each year is averaged over ten runs. Mean and standard deviation (after +) are calculated over the 19 years. The best is marked bold red and the second best marked in underline blue. InfoMap results are omitted here as it usually predicts a single huge cluster and could not generate imbalance results. Louvain and Leiden yield essentially identical results and often attain the highest objectives, while DIGRAC almost always places either first or second across all methods considered.
Table 12:
Metric/Method
Louvain/Leiden
Bi sym
DD sym
DISG LR
Herm
Herm rw
DIGRAC
0.08
0.0710.01
0.0711001
0.0710001
0.07-0.02
0.07-10.02
0.15:00.3
Ouerr min
0.1511004
0.51-10.10
0.48100.9
0.4710.10
0.51-0.11
0.50:10.10
0.4710.09
O Vol-mas
0.08++0.02
0.07-00.01
0.06+00.01
0.06+0001
0.07=0.01
0.07+0.01
0.14+00.3
0.15:20.04
0.66-00099
0.64+:0.88
0.63++0.08
0.66=0.09
0.65++0.09
0.53
Oui
vol_sum sum
0.23+10.06
0.04+0.01
0.04+00.1
0.04+0.01
0.04=0.01
0.04+00.01
0.12+00.33
Oyid
0.46:10.11
0.27=0004
0.27::0.0
0.25+10.4
0.27-0003
0.27-10.33
0.38
Liin
Odid
0.23+:0.05
0.04=0.00
0.03+10000
0.03+00.00
0.03=0.00
0.03+10.00
0.11
ydd
0.46=20.11
0.40=0.05
0.39+10.5
0.38
0.40=0.05
0.40+:0.05
0.44
plain
Ohavve
sum
0.23
0.03=0.01
0.03+00.01
0.03
0.03=0.01
0.03+0001
0.00
naive
0.46=#0.11
0.20=0.05
0.19::0.05
0.18
0.19=0.04
0.19:00.44
0.26++0.10
O vol max
0.23
0.03
0.02-10.01
0.02-10.01
0.02-10.00
0.02-10.00
0.08
naive
plain
0.46
0,30-10.06
0.28
0.27100.66
0.29
0.2910.05
0.32.10.11
size ratio
124.530
3.67
3.34
3.900
4.110
3.880
8.070
size std
47.960
9.31
9.14
10.090
10.490
10.360
17.060
35

---

Under review as a conference paper at ICLR 2022
50
Labo
15
35
30
-120
-110
-100
-00
-80
-70
-120
-330
-100
-10
-80
-70
(a) Bi_sym
(b) DD symm
30
50
39.6
30.0
22.0
35
35
15.2
30
8.8
-120
-110
-100
-00
-80
-70
-120
-110
-100
-90
-80
-70
0.0
(c) DISG_LE
(d) InfoMap
30
50
Latol
25
-120
-110
1000
-00
-80
-70
-120
-110
-100
-90
-50
-70
(c) Herm
(f) Herm_rw
50
35
-120
-110
-100
-00
-70
(g) DIGRAC
Figure 19: US migration predicted clusters, along with the geographic locations of the counties as
well as state boundaries (in black). The input digraph has extremely large entries; unlike in Figure 17 we do not employ here the normalization given by Eq. (33). Altogether, this demonstrates the robustness of DIGRAC outliers in the data, which is not characteristic of other state-of-the- -he methods such as Herm and Herm rw.
36


Reviews:
[{"review_id": "sEvS17oE3tR", "reviewer": "Reviewer_mMXH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nOverall, the paper is well written.\n\n**Weaknesses**\n\nI am concerned with the practicality of the problem and consequently the method studied in this paper. In Section 4, the authors mention that \"real data sets with ground-truth flow imbalances are not available to date\", so they use normalized imbalance scores to evaluate clustering performance. This feels a bit like going against the natural order of how machine learning models are typically developed. Usually, we start with a real, practical problem at hand, and then we try and develop a new method to solve it, if existing methods do not yield satisfying results. However, I feel like this paper is going backwards: It starts with inventing a method that solves a possibly made-up problem. The experiments in Section 4 do not demonstrate the practical importance of clustering with respect to flow imbalances. Since this is an empirical paper, I believe that a solid empirical evidence that showcases the need for clustering with respect to flow imbalances is required.\n\nMore about empirical evaluations: The authors use 80% of all nodes for training. Isn't this percentage too much? Can't we use, e.g., 5% of all nodes for training?", "summary_of_the_paper": "This paper studies the problem of clustering directed graphs where clustering structure is defined in terms of flow imbalances between clusters. The method proposed in this paper first computes node embeddings via directed mixed path aggregation, which takes directionality into account. In order to perform clustering, the node embeddings are transformed to an assignment probability matrix, which is then used to compute a flow imbalance score. The model is trained end-to-end to maximize the flow imbalance score (or its variants). Empirical experiments show that the proposed method has good performances.", "summary_of_the_review": "I have concerns regarding both the problem setting and the empirical evaluation, so I do not view this paper as ready for publication at this time.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PS2WBPO1_1F", "reviewer": "Reviewer_SM6X", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Summary** This paper presents an empirical study of clustering nodes based on a given graph structure. The clustering model is a deep approach that produces embeddings of the nodes that can be used for other tasks like node classification, etc. \n\n**Merits**. This paper demonstrates that it can achieve the desired goal of node representations with the DIGRAC architecture and the \"DIRECTED MIXED PATH AGGREGATION (DIMPA)\" layer in particular. To better understand this deep model, the authors provide synthetic empirical results, which demonstrate the performance of the method under different kinds of data.\n\n**Concerns**. My primary concern for this paper is that I find it difficult to understand the empirical performance gains provided by the method. In many of the ARI graphs on synthetic data, it seems many of the methods are quite close together in performance. In the real data, it seems that methods overlap in their error bars. I am also wondering whether more can be said about when DIGRAC's model for clustering is appropriate for a dataset and when it is not. And how adaptive the model can be in terms of performance despite those considerations. Apologies if I have misunderstood the empirical results, if so, I would like to better understand them. ", "summary_of_the_paper": "This paper introduces DIGRAC, a novel GNN approach for clustering based on the edges that are not present in a digraph. The architecture achieves this by finding node embeddings for digraphs that directly maximizes flow imbalance between clusters. The paper presents empirical results on both real and synthetic datasets, showing the effectiveness of the proposed approach.", "summary_of_the_review": "An interesting paper with a self-supervised novel architecture for node clustering using an objective based on missing edges in a digraph. There are some concerns regarding the empirical gains provided by the method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EFH8Vq8vdgj", "reviewer": "Reviewer_h5sc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper provides an interesting pipeline for clustering in directed graphs. In particular, the idea of modeling the imbalance flow is very useful.\n- Interesting benchmark graphs. I really liked the idea of using a modified DSBM model to express information flow.\n\nWeaknesses:\n- The theoretical contributions of the paper are somewhat vague at some points, and overall could be enhanced. \n- It is not very clear what are the novel aspects of the DIMPA model.\n- The baseline models could be enhanced. \n\n\n**Detailed comments.**\n\nDespite the interesting formulation of the problem, there are several aspects of the paper that are not quite clear and need further development. Next, I provide a detailed discussion of points that need to be addressed.\n\nTo begin with, despite having an interesting formulation of the imbalance flow, the loss function defined in Eq. (2) and (3), is not well-understood. I can see the semantics behind the imbalance term, but the theoretical properties are not clear at all. Is there any theoretical characterization for this loss? Are there cases where it could lead to degenerate solutions? It would also be important to clearly present the constraints of the optimization problem. Examining how the loss behaves in terms of convergence, is also important.\n\nThe other important point has to do with the novelty of the DIMPA algorithm. It’s not clear to me what are the novel parts of this model w.r.t. previous works. As far as I understand, the paper shares common ideas with message passing GNNs as well as with the KernelGCN model. Therefore, it’s difficult to evaluate its novelty w.r.t. state-of-the-art baseline models.\n\nI really appreciated the effort that the authors put into the empirical analysis, especially on the parts related to the stochastic block model. Regarding the baseline models, the paper discusses why many “traditional” models are not part of the empirical analysis. Nevertheless, I would expect to add models that capture information flow, including for instance algorithms that rely on stochastic blockmodels (e.g., “Directed network community detection: A popularity and productivity link model”, SDM 2010). Besides, it would be interesting to have a model that is based on directed modularity (e.g., E. A. Leicht, M. E. J. Newman, “Community structure in directed networks”, PRL 2008).\n\nLastly, despite mentioning the complexity of the model, there are no scalability experiments with the running time of the algorithm and its comparison to baseline models.\n", "summary_of_the_paper": "The paper introduces DIGRAC, an end-to-end model for clustering in directed graphs. The novelty of the model stems from the fact that it optimizes the directed flow imbalance to identify clusters that go beyond density-based criteria.  The proposed problem formulation is interesting: the loss function is defined in order to capture imbalance flow among clusters. Then, a GNN model is used to obtain the probabilistic assignment matrix that defines clusters. In terms of empirical analysis, the paper performs experiments on various artificial and real-world datasets, comparing the performance of the proposed model to various baselines.", "summary_of_the_review": "The paper proposes an interesting approach to end-to-end flow-based clustering in directed graphs. Nevertheless, particular aspects of the paper, especially those related to the properties of the loss function and, partly, the experiments, need further development.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a new algorithm for clustering direct networks. The key idea behind the paper is to introduce a new flow imbalance measures and a new self-supervised GNN model to solve the task.

Overall, the paper is interesting and it introduces some new ideas although it needs additional work before being published. 

In particular,
- the experiments could be improved by emphasizing more the evaluation on vol_sum/vol_max/etc metrics and by adding additional results on them
- the clarity of the experimental results should also be improved(for example, metrics / claims around Figure 4 still a bit hard to parse)
- finally, the paper would benefit by some theoretical results on the guarantees of the algorithm(most previous work in the area present interesting theoretical guarantees)
Decision: Reject