The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks
Authors: Christopher Blöcker
Chester Tan
Ingo Scholtes
Venue: NeurIPS 2024 poster (2024)
Keywords: community detection
graph clustering
random walk
map equation
Primary area: other
TL;DR: We adapt the map equation, an information-theoretic objective function for community detection, as a differentiable loss function for optimisation with neural networks and gradient descent.

Abstract: Community detection is an essential tool for unsupervised data exploration and revealing the organisational structure of networked systems. With a long history in network science, community detection typically relies on objective functions, optimised with custom-tailored search algorithms, but often without leveraging recent advances in deep learning. Recently, first works have started incorporating such objectives into loss functions for deep graph clustering and pooling. We consider the map equation, a popular information-theoretic objective function for unsupervised community detection, and express it in differentiable tensor form for optimisation through gradient descent. Our formulation turns the map equation compatible with any neural network architecture, enables end-to-end learning, incorporates node features, and chooses the optimal number of clusters automatically, all without requiring explicit regularisation. Applied to unsupervised graph clustering tasks, we achieve competitive performance against state-of-the-art deep graph clustering baselines in synthetic and real-world datasets.

The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks
Christopher Blöcker
Chester Tan
Data Analytics Group Department of Informatics University of Zurich, Switzerland christopher. bloecker@uzh.c
Chair of Machine Learning for Complex Networks Center for Artificial Intelligence and Data Science
Siits--Mximillinss-niieee Würzburg, Germany chester: tanguni -wwerzburg.c
Ingo Scholtes'
Chair of Machine Learning for Complex Networks Center for Artificial Intelligence and Data Science Mallus-axximilians.o Universität Unxiiesiaas--nnivessttät Würzburg, Germany ingo ingo.schoo scwolteseuni www.unniwwwwzzuu.duroooom
Abstract
Community detection is an essential tool for unsupervised data exploration and revealing the organisational structure of networked systems. With long history in network science, community detection typically relies on objective functions, optimised with custom-tailored search algorithms, recent advances in deep learning. Recently, first works have started incorporating such objectives into loss functions for deep graph clustering and pooling. We consider the map equation, popular information-theoreti objective function for unsupervised community detection, and express it diffcrentiable tensor form for optimisation through gradient descent. Our formulation turns the map equation compatible with any neural network architecture, enables end-to-end learning, incorporates node features, and chooses the optimal number of clusters automatically, all without requiring explicit regularisation. Applied to unsupervised graph clustering tasks, we achieve competitive performance against state-of- oate-of-thhe-rt deep graph clustering baselines in synthetic and real-world datasets.
often without leveraging
Introduction
Many real-world networked systems are organised in communities: groups of nodes that are more similar to each other than to the rest. Communities provide insights into network structure at the mesoscale, revealing sub-systems by analysing link patterns. Motivated by different research questions, several characterisations of what constitutes "good" communities have been proposed [[] 21. however, neither of them is fundamentally more correct than any other. Moreover, no single community-detection method outperforms all others on any given network 3 motivating the ongoing efforts of research community detection. Typically, community-detectio an objective function that calculates a quality score for given partition of the network's nodes into communities. Finding the best partition is NP-hard search problem and often involves custom heuristic algorithms that attempt to minimise their objective function 5 6).
approaches formulate
Also at Chair of Machine Learning for Complex Networks, Center for Artificial Intelligence and Data Science, wawee-Maaailinsnniiiiiee Also at Data Analytics Group, Department of Informatics, University of Zurich, Switzerland
Würzburg, Germany
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Graph neural networks (GNNs) have enabled applying deep learning to graph sraph-structured data by utilising the input graph as the neural network's 's computational graph 7 g 9 Typical tasks for GNNs include node labelling, graph labelling, and link prediction, all of which involve learning meaningful representations jointly from the graph's 's topology, the nodes' features, and, possibly, the edges' features. Graph labelling relies on coarse-graining the graph through identifying groups of "similar" nodes and aggregating their links and features, also referred to as pooling [10 [2] which is related to graph clustering [13), however, these two tasks have different goals.
While GNNs excel at incorporating node and edge features with graph topology, including this information is also possible but more challenging with traditional network science approaches, typically requiring modelling or adjusting objective functions and their optimisation algorithms. On the other hand, objective functions for community detection provide precise interpretations as to why one partition considered better than another while deep-learning gearning-based approaches are black boxes. Model selection in deep learning is often done through regularisation techniques or cross-validation; in contrast, objective functions that are based on the minimum description length (MDL) principle naturally implement Occam's 's razor, preventing overfitting and enabling principled model selection without requiring extra regularisation or cros-validation [4 15
Here, we combine the benefits of traditional conmunity-detectionn approaches and deep learning and consider the map equation, an ceemmatioo-thhoreeee objective function for community detection [16] By adapting the map equation for soft cluster assignments and implementing it in differentiable tensor form, we enable end-to-end optimisation of the map equation as loss function with gradient descent and GNNs. In analogy to the map equation's 's stochastic optimisation algorithm Infomap (6) we call our approach Neuromap and evaluate it against Infomap and several recent GNN-based graph clustering methods. Applied to synthetic and real-world networks, Neuromap demonstrates competitive performance against recent deep graph clustering baselines.
Our key contributions can be summarised as follows:
1. We adapt the map equation as differentiable loss function for end-to-end deep graph clustering and propose Neuromap, a deep-learning-bae algorithm for unsupervised community detection with the map equation. Neuromap is compatible with any neural network architecture, detects overlapping communities, leverages node features for improved performance real-world networks, and, by following the minimum description length principle, does not require explicit regularisation.
alternative the popular Infomap
2. We extensively evaluate Neuromap hundreds of synthetic and ten real datasets against recent baselines paired with various neural network architectures. Neuromap outperforms the baseline on the synthetic networks in most settings and is amongst the best performers in seven out of ten real datasets.
3. By choosing a higher maximum number of clusters than previous works, we show empiri- cally that recent baselines tend to overfit and report considerably more than the ground-truth number of communities. Moreover, find that choosing small maximum number of communities is often detrimental to graph clustering performance.
2 Related work
Community detection. Communities, also called clusters modules, are groups of nodes that are more "similar" to each other than to the rest, often understood as having more links inside than between groups 2 However, this rather general characterisation leaves precise details of what constitutes a community open. Modularity compares the observed link densities inside communities against randomised version of the network [17]. The stochastic block model and its variants assume a latent block structure where the probability that two nodes are connected depends only on their block memberships 118 [9]. The map equation identifies communities as regions where random walker tends to stay for a relatively long time [6] 20). Traditional clustering approaches, such as k-means, group nodes based on their proximity in space, however, here we consider identifying communities from the link patterns in networked systems. For a detailed overview of community detection in complex networks, we refer 2
Minimum description length principle. The minimum description length principle (MDI.) model-sclection approach that formalises Occam's 's razor and frames learning as compression

---

For recent surveys of deep graph problem [5]. MDL states that the best model for data D is the one that compresses the data the most. traditional MDL, the data's two-part description length L (D) minas L (D) M) is the smallest achievable length over all models M, where I. (M) is the model's description length, and I. (D M) is the data's 's description length, given the model. MDL has been adopted for wide range of applications, including regularising neural networks' weights [2], investigating deep neural networks' data-compression capabilities [22], analysing the characteristics of datasets [23], and community detection [16, 24),
Deep graph clustering and pooling. Graph clustering has long been research focus in machine
learning [5]. Spectral approaches cluster, for example, the eigenspace of a graph's 's Laplacian
matrix or identify communities through graph cuts (26 27]. Methods based on neural embeddings
involve learning node representations with, for example, Deep [28] or node2vec [29]] followed by
applying standard clustering approaches such as k-means, assuming that similar nodes are embedded
contrastive learning (44, and self-expressiveness [35. Recently, minimum cuts M 12 modularity [3 (37), and the Bernoulli-Poissee
at similar locations [30] 31.. Other approaches include graph autoencoders 32 33
model (38 have been integrated with GNNs as loss functions for graph pooling and clustering. Such GNN-based approaches can incorporate graph structure as well as node and edge features in end-to-end optimisation of the clustering objective. Inspired by pooling in convolutional neural networks, graph pooling coarse-grains links, node features, and edge features to summarise graphs, enabling GNNs with improved performance
node and graph classification tasks TO, [2 Consequently, graph pooling has become a research focus for GNNs, emphasising the importance of graph clustering as primary objective 10 12 36
clustering, we refer to 39 40)
Background: the map equation
The map equation [6 20) an information- objective function for unsupervised community detection that follows the MDL principle [14], and has demonstrated high performance in synthetic and real networks from across domains detection as compression problem and uses random walks as proxy to model dynamic processes on networks, also called flow. The goal is describe the random walk as efficiently as possible by minimising its expected per-step description length- also called codelength by partitioning the network into groups of nodes, called modules, where the random walker tends to stay for a relatively long time. In practice, however, the map equation does not simulate random walks; instead, the codelength calculated analytically.
43 The map equation formulates community
111
1100
0000
11111 0010
010
00
010
01
101
10
I1II
10
IIII
1010
I1I
10
00
010
00
001
11010
1100
1111
0111001
10
O11
100
1000
001
11
110
o1
11010
100
10
010
1010
1110
001
011
11
00
III
110
1001
00
1001
1011
1011
III
00
III
11
O1l 10
1110 110
0001
1011 III
010
O1l
Coding principles behind the map equation. Colours indicate modules, codewords are shown next to nodes, and the black trace shows sequence of random-walker steps. Left: All nodes belong to the same module and all codewords are unique. Encoding the random walk sequence requires 60 bits, or 3.72 bits per step in the limit. Right: Partitioning the network enables reusing codewords across modules, reducing the codelength. However, for a unique encoding, we need to introduce codewords for entering and exiting modules, shown next the arrows pointing into and out of the modules. With this modular coding scheme, we can compress the description to 48 bits, or 3.01 bits per step in the limit. Middle: The two encodings of the random walker's steps.
Figure 1:
3

---

Let G = (V, be graph with nodes V. links E, and let the E Bi denote the non non-negative link weight on the link from node u v. When all nodes are assigned to the same module, the codelength is defined by the Shannon entropy H over the nodes' visit rates 44]. H (P) = Euev Pa. log2 Pa- where Pu is node u's visit rate and P- = {p. u LuEV is the set of node visit rates. In undirected graphs, we compute visit rates directly as pa, sy/ Eeev Su, where S. E'.vv Wao is node u's strength. In directed graphs, we compute the visit rates numerically with smart teleportation [5]] and power iteration. When we partition the nodes into modules, the codelength becomes a weighted average of the modules' entropies and the entropy at the so-called index level for switching between modules. Figure illluttraees the coding principle behind the map equation using Huffman codes [46]; note, however, that these codewords are only for illustration and we only care about their expected length the limit evaluate the map equation.
Minimising the map equation means balancing between small modules to achieve low module-Ievel entropies and large modules for low index-level entropy. This trade-off' between module- and index- level entropies prevents trivial solutions where all nodes are assigned to the same module or each node [1] The map equation calculates the codelength for a partition M,
assigned a singleton module
L (M) = gH (Q) + Σ Pm (Pm).
(1)
MEM
Here, 9 -m 9m is the random walker's module entry rate, 9m Lugmm Evem Putun is module M] is the set of normalised module entry rates; Pm Mexit + +Zuem Pa is the rate at which the random walker moves in module m, including the module exit rate Mexit = Σuem Evem Putwes and Pm = {mext// Pm } U {Pu/Pm u E m} is the set of normalised node visit and exit rates for module m. The random walker's transition probability from We can rewrite the map equation as (see Appendix
m's entry rate, and Q = {9m/g
node u to v is bur = wwe/ Evev Was-
L (M) = q log2 - -E 4m log2 9m
Σ mEM
Mexit loga Mexit
Σ Pu log2 Pu. + Σ Pm loga Pm- (2)
mEM
WEV
mEM
The map equation framework has been extended for overlapping communities through state-space
expansions with higher-order network models 47 48), avoiding over- wer-partitioning in sparse networks
using a Bayesian regularisation approach 49 and to deal with sparse constrained structures [50]
Moreover, the map equation framework can incorporate node features through an extension [5]
or by preprocessing data [52]. Detecting communities relies on Infomap [6], a greedy stochastic search algorithm that optimises the map equation. However, each of the above extensions requires preprocessing the input data, adjusting the loss function, or adapting the search algorithm. In contrast, adapting the map equation any custom algorithm, thus enabling flexible experimentation with variations, scalability to GPU clusters, and incorporating it into other loss functions.
loss function for optimisation with gradient descent does not require
4 The map equation goes neural
We set out to detect communities by optimising the map equation with GNNs through gradient descent, which essentially means learning coarse- coarse-graining node representations in the form of communities (Figure While the standard map equation considers hard clusters where each node is assigned to exactly one module, we introduce a soft cluster assignment matrix S,xa to make the map equation differentiable and enable overlapping clusters. We optimise S softmax (GNN, (A. X)) indirectly by optimising the GNN's parameters f, that is, its weights, with respect to the codelength L. Here, Anxn is the graph's 's adjacency matrix, x is the node features matrix, n = V is the number of nodes, is the maximum allowed number of clusters, and d is the node feature dimension.
Without loss of generality, we assume directed networks. We denote the graph's 's total weight as Whxt Eiey Σjev Wij- Let T Txxn be the random walker's transition matrix and d be the vector of weighted node in-degrees with
Wij
if EjEv Wij 0.
Tyy Ejev Wij
dt
Σ Wij- LEV
otherwise,
To compute the vector p of node visit rates, we use smart teleportation 45 and the power iteration method: With probability a, the random walker teleports to random node, chosen proportionally to

---

GNN
Soft Clusters Swe
Node features Xnd
1 00000
00000
1000
0000
010000
softmax
O 1111101000
5.5
Map Equation Loss Codelength L(A,S)
gradient calculation using backpropagation
Figure 2: Illustration of the setup for GNN-based community detection with the map equation. We learn soft cluster assignments S from the graphs adjacency matrix A and the node features X. Here, we allow up to four clusters. When no node features are available, we set A.
the nodes' in-degrees, or follows link with probability - a. This approach leads to the iterative update rule ((++1) + __ + (1 ax) p (T,, and we set (0) = d The graph's 's flow matrix F Fox encodes the flow between each pair of nodes, where F A + (1 - a) diag (p) T. We obtain the
flow Csxs between clusters from S and F as C FS. Following Equation 2 we define
1 tr (C) qm C1. diag (C) Mexit C) diag (C) Pm qm + 1
and assemble the map equation
L (A, = logg (-m loga 4m) 1, (maic logg Mexi) 1, 1 logg p) 1, - (Pm log2 Pm) 1, (3)
where 1 is the k-dimensional vector of ones, and logarithms are applied component-wise wise. The third term is constant since it only depends on the node visit rates and can be omitted during optimisation.
The map equation naturally incorporates Occam's 's razor by following the MDL principle for bal- ancing between model complexity and fit [14, [5], choosing the optimal number of communities automatically, but at most s. In contrast, recent GNN-based clustering approaches require explicit regularisation to avoid over-partitioning [TO, 36 37 38), and our results show that they often return the maximum allowed number of communities instead of determining the number of communities in a data-driven fashion (see Section 5). principle, any neural network architecture, such as a multi-layer perceptron (MLP) GNN, be used to learn the soft cluster assignment matrix S. Since the map equation involves logarithms, we add a small constant to each value in the output differentiability. We refer to the combination of using map equation loss (Equation together with a (graph) neural network to learn (overlapping) communities as Neuromap.
before the backpropagation step
Complexity and limitations. The most expensive calculation is the pooling operation C S FS which depends the network's 's density. When < and the number of edges is O (n), the complexity of Neuromap is lincar in When the network is dense, number of clusters approaches the number of nodes & n, we approach quadratic complexity. Therefore, recommend keeping << for scalability.
O (n²), the maximum
We assume connected networks, otherwise, clustering should be run on the individual components. The node features X aid the GNN in learning patterns, however, they do not contribute to the loss. When no node features are available. Neuromap can use, for example, the adjacency matrix as node features; designing expressive low-dimensional node features remains an active research area (53
5 Experimental evaluation
evaluate Neuromap on synthetic and real-world networks with different neural network architec- tures: a 2-layer graph convolutional network (GCN) 19) 2-layer graph isomorphism network (GIN) [54], and 2-layer SAGE network (55). investigate whether GNNs are required for clustering, we also include fully connected linear layer and 2-layer MLP. We include learnable temperature
5

---

parameter for the softmax operation, which we found speeds up convergence. In all cases, we use the models provided by PyTorch Geometric with SELU activation [56]. Because the specifics between architectures differ, such message-passing details and aggregation functions, they may be interpreted using different search algorithms which return different communities. We use the Adam optimiser [57], apply batch normalisation, and for comparability between different methods, set the learning rate for the linear layer to 10-1, for MLP to 10-2, and for GCN, GIN, and SAGE to 10-3 We train all models for up to 10,000 epochs with patience of 100 epochs and dropout probability 0.5. Because the datasets contain hard clusters, we convert the resulting communities to hard clusters, assigning each node to that cluster where it has its strongest membership. As baselines, we use Infomap [6] and five recent approaches for unsupervised graph clustering with GNNs: DMoN [3),, NOCD 38 DiftPool [T]), MinCut (TT), and Ortho [36]. We base our implementation Py TyTorch [58] and PyToocch Geometric [59] and ran our experiments on a workstation with an Intel 19-1 19-11900K @ 3.50GHz CPU, 32 GB of RAM, and GeForce RTX 3090 with 24 GB of memory.
5.1 Synthetic networks with planted communties
We generate directed and undirected with planted ground-truth communities 60 with n 1000 nodes, average node degree [In n.. maximum node degree mmax 2 2/n, both rounded to the nearest integer, and mixing parameter j between 0.1 and 0.8 with a step size 0.1. We set the power-law exponents for the node degree distribution to combination parameters, we generate 10 LFR networks using the implementation provided by the authors resulting in total of 320 networks. For each parameter combination, there 10 LFR networks; for each these LFR networks, we run each model 10 times, measuring its performance the average adjusted mutual information (AMI) [61] against the ground truth, and plot the average of those AMI values over the 10 networks per parameter combination. To verify that the number of communities is inferred from the data, we set the maximum number of communities LFR networks do not have node features, we use the adjacency matrix as node features.
(LFR) benchmark networks
2. and for the community size distribution to 1. For each
n. Since
undirected, k =
undirected, k = 14
directed,
directed, 14
1.0-
1.0
1.0-
1.0
AMI
0.5
0.5-
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
200
200
200
200
100
100
100
100
0-
0
0.2
0.1
0.6
0.8
0.2
0.1
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
10
8
8-
8
6-
6-
6-
6-
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
/
/ GCN
true
Infomap
Linear
MLP
GIN
SAGE
Figure 3: Performance for Neuromap using dense linear layer, MLP, GCN, GIN, and SAGE architectures with two layers and Infomap on directed and undirected LFR networks with planted communities. The results show averages of partition quality measured with AMI, number of detected communities [M], and codelength L. The shaded areas show one standard deviation from the mean.

---

We find that the detected communities' quality depends on the choice of neural network architecture (Figure Neuromap achieves the best AMI scores with SAGE. GCN, MLP, and Infomap perform slightly worse, however, with some variation depending linear layer and GIN show weaker performance but still identify relevant communities. In the sparser directed networks, Infomap performs slightly better than SAGE when the mixing is low. However, the AMI values do not tell the whole story; Infomap and MLP tend to report considerably more communities than are present in the ground truth whereas the dense linear layer and GIN tend to report much fewer communities than the ground truth, especially for higher mixing values. GCN reports more communities than are present in the ground truth in the sparser undirected networks but fewer in the directed networks. SAGE detects close to the true number of communities in all cases. Infomap achieves the lowest codelength across all networks. GCN, MLP, and SAGE achieve close to Infomap's 's codelength, whereas the dense linear layer and GIN have slightly higher codelength.
the networks" properties. The dense
undirected, k
undirected, k 14
directed,
directed, k= 14
1.0
1.0
1.0
1.0
AMI
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
10a
10a
10a
10a
10a
10a
10a
10a
10a
10a
10a
10a
10a
10"
10"
10"
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
true
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Figure 4: SAGE-based results for deep learning community-detection methods on synthetic LFR networks with planted communities. We show averages of partition quality measured by AMI and number detected communities MM.. The shaded areas show one standard deviation from the mean.
We compare Neuromap against recent deep-learning-basee same networks by swapping out the loss function while keeping everything else the same, with the exception using weight decay for NOCD as per the original paper (38]. For DiffPool, Mincut, Ortho, and DMoN, we use the implementation from PyTorch Geometric, for NOCD, we use the implementation provided by the authors Figure shows the results for SAGE; in Appendix B we also include results for the remaining architectures. Neuromap outperforms the baselines across all architectures, except for NOCD which performs better than Neuromap with GIN and with GCN on directed networks. Different from previous works, we have not limited the maximum number of communities, which allows us to analyse the methods' overfitting behaviour: While Neuromap reports close to the ground-truth number of communities, the remaining methods often overfit networks' structure and report considerably more communities (note the logarithmic scale). MinCut fails to identify meaningful communities on directed networks for mixing values μ >> 0.3. NOCD) performs best with the GCN architecture, which was also used in the original paper [3 Neuromap performs best with SAGE in our experiments.
community detection methods on the
5.2 Real-world networks with node features
We benchmark Neuromap on ten real-world datasets (Table from Py Torch Geometric [59], Py ToTch Geometric Signed Directed (62). and Open Graph Benchmark [63]. and compare against the same baselines as before. In contrast to previous works that choose a fixed number of hidden dimensions and set the maximum number of communities to constant (36] or the "ground-truth" number of communities [38 we reflect the networks' sizes in our choices: We set the number of hidden dimensions 4yn and the maximum number of communities to vn. Our choices are based on empirical observations showing that the number of communities typically scales as O (vn) [4]

---

Table 1: Properties of the real-world datasets obtained from PyTorch Geometric (PyG) [59]. PyTorch
Geometric Signed Directed (PyG-SD) 662), and Open Graph Benchmark (OGB) 633. [ the
number of nodes, [E| the number of edges, |X] the node feature dimension, Y the number of communities, and μ the mixing for the given communities.
Dataset
Source
Type
[V]
[E]
Y
μ
Cora
PyG
Undirected
2,708
5,278
1,433
0.19
CiteSeer
PyG
Undirected
3,327
4.614
3,703
6
0.26
Pubmed
PyG
Undirected
19.717
44.325
500
0.20
Amazon Computer (PC)
PyG
Undirected
13,752
143.604
767
10
0.22
Amazon Photo
PyG
Undirected
7,650
71,831
745
0.17
Coauthor CS
PyG
Undirected
18,333
81,894
6,805
15
0.19
Coauthor Physics
PyG
Undirected
34,493
247,962
8,415
0.07
Cora ML
PyG-SD
Directed
2,995
8,416
2,879
0.21
Wiki CS
PyG-SD
Directed
11,701
297,110
300
10
0.31
ogb-arxiv
OGB
Directed
169,343
583,121
128
40
0.35
However, a few words of caution are in order: while nodes' true communities determine the link patterns in synthetic networks, it is generally infeasible to obtain ground truth communities for real networks. Often, metadata labels are used as a drop-in, and the inferred communities' quality depends on how well the metadata, which is potentially noisy, aligns with the unknown ground truth [3] Moreover, determining the number of communities a network is hard and setting v should be seen simplification rather than attempt guess the exact number.
For each method and architecture, we run 25 trials and show the average achieved AMI in Figure 5 we include similar plot for the number of detected communities well as the average AMI and the detected number communities, both with standard deviations, tabulated form in Appendix C When several of the best persorerforming methods achieve similar AMI, sample t-test to determine whether one them can be considered to perform better than the other (see Appendix C). In cases where their performances do not differ significantly, mark both as best.
independent two-
Neuromap and NOCD are amongst the best performers in seven cases and DiffPool two. The GCN architecture performs best in seven cases, MLP and SAGE in four cases, and GIN in two cases. A
80
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Inforapp
Linear
GIN
SAGE
Infomap
60
AMix 100
40
0-
Cora
CiteSeer
Pubmed
Photo
AMI
40
CS
Physics
Cora ML
Wiki CS
ogb-arxiv
Figure 5: Average achieved AMI on real-world networks (higher better) with vn. Colours indicate methods while shapes indicate neural network architectures. DiffPool ran out of memory on the ogb-arxiv dataset. Detailed tabulated results with standard deviations are included in Appendix C

---

possible explanation for why the simpler linear layer and MLP architectures perform well in several cases could be that the map equation loss function captures global information in the random walker's flow patterns, making GNNs superfluous in some cases. All methods tend to detect more communities than are present in the "ground truth", however, this tendency most pronounced in DMoN, Ortho, and MinCut, which may have gone unnoticed in previous evaluations where the maximum number of communities was set to a much lower, constant value [36], thus artificially preventing overfitting. Infomap is the only baseline that does not utilise node features; instead, it relies solely on topological information, which may explain the large number of detected communities. Comparing Neuromap's s performance against Infomap's 's performance suggests that incorporating node features substantially improves the detected communities' quality in most cases (see Appendix C for significance tests) while drastically reducing the number of detected communities.
We repeat the same experiments with 512 hidden features and = | that is, the "true" number of communities, following [38] (results in Appendix [D]. Limiting the number of allowed communities often leads to better performance for DMON, MinCut, and Ortho, however, with a few exceptions, it diminishes the performance of Neuromap, NOCD, and DiffPool across all datasets and neural network architectures. Appendix D the hidden features to 4v and tabulates the differences in average AMI score between setting v versus using 512 hidden features and = (Y). In the case of Neuromap, imposing lower bound on the number communities interferes with the MDL principle, limiting what models for the data may be explored.
5.3 Synthetic networks with overlapping communities
We apply Neuromap and the baselines to small synthetic network with overlapping communities 65] We set the maximum number of communities to s {2,3), run each combination of loss function and neural network architecture for 10 trials, and keep the solutions with the lowest loss. Figure shows the results obtained with GCN, Appendix F shows results for the remaining architectures.
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
True
2
3
Synthetic network with overlapping communities where the leftmost network shows the true community structure. Nodes are drawn as pie charts to visualise their community assignments. The top and bottom rows show results for a maximum of s = 2 and
Figure 6:
communities, respectively.
We find that Neuromap, DMoN, NOCD, and MinCut identify the correct communities for 2. DiffPool does not detect overlapping communities and Ortho assigns each node to two communities. For only Neuromap identifies the correct communities. DiffPPool returns the same communities as for s = 2. All remaining methods return three communities. These results provide further evidence that the baselines suffer from overfitting when they are not provided with the correct number of communities, which, in general, is unknown. Neuromap identifies meaningful communities while inferring the number of communities in a data-driven fashion by following the MDL. principle. However, we leave more rigorous study of overlapping communities for future work.

---

6 Conclusion
Network science and deep learning on graphs tackle community detection from different perspectives. Community detection in network science typically relies on custom heuristic optimisation algorithms to optimise objective functions but often does not leverage recent deep learning advances. Recently, deep graph learning methods have started to incorporate methods from network science for deep graph clustering. We contribute to this young field by adapting the map equation, a popular unsupervised information-thheortiic community-detectio approach, as differentiable loss function for end-to-end optimisation with (graph) neural networks through gradient descent, and use Py Torch to implement approach, which call Neuromap.
We evaluated Neuromap on various synthetic and real-world datasets, using different neural net- work architectures to detect communities. Our results show that Neuromap achieves competitive performance and detects close to the ground-truth number of communities across datasets while the baselines tend to overfit and report considerably more communities. Across all tested methods, the achieved performance depends on the used neural network architecture. However, on several real- world benchmarks, Neuromap outperforms several of the the baselines even with simpler, non-GNN, neural network architectures. hypothesise that this may be because the map equation builds on capturing flow patterns, which contain global information.
While we have considered first-order networks with two-level community structures. complex real- world networks often involve higher-order dependencies and can have multi-level communities 47 66). prompting a generalisation of our approach. Furthermore, incorporating our method for graph pooling as well as uncovering the precise connection between the utilised neural network architecture and the achieved community-detection performance requires further empirical and theoretical studies.
Acknowledgments and Disclosure of Funding
We thank Martin Rosvall, Jelena Smiljanić, and Daniel Edler for fruitful discussions and helpful feedback. We indebted to Lisi Qarkaxhija for helping with PyTTrrc implementations. Christopher Blöcker and Ingo Scholtes acknowledge funding from the Swiss National Science Foundation, grant 176938, and the German Federal Ministry of Education and Research, grant 100582863 (TissueNet).
References
[1] Santo Fortunato. Community detection in graphs. Physics Reports, (8643))55-174,2000 2010.
[2] Santo Fortunato and Mark EJ Newman. 20 years of network community detection. Nature Physics, 18(8):848-8555 8800, 2022.
[3] Leto Peel, Daniel B. Larremore, and Aaron Clauset. The ground truth about metadata and community detection in networks. Science Advances, 3(5):e160254) 2017.
[4] Vincent D Blondel, Leap Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008, oct 2008.
[5] V. A. Traag, L. Waltman, and N. J. van Eck. From louvain to leiden: guaranteeing well- connected communities. Scientific Reports, 9()):2233, Mar 2019.
[6] Daniel Edler, Ludvig Bohlin, and Martin Rosvall. Mapping higher-order network flows in memory and multilayer networks with infomap. Algorithms, 10(4), 2017.
[7] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1 20(1):61-80 2009.
[8] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 06-11 Aug 2017.
10

---

[9] Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
[10] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[11] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference on machine learning, pages 874-883. PMLR, 2020.
[12] Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. In Advances in Neural Information Processing Systems, volume 36, pages 7 71603- 71618. Curran Associates, Inc., 2023.
[13] Satu Elisa Schaeffer. Graph clustering. Computer science review, (()::2766,, 2007.
[14] Jorma Rissanen. Modeling by shortest data description. Automatica, 14(5):465-471 1978.
[15] Peter D Grünwald, In Jae Myung, and Mark Pitt. Advances in minimum description length: Theory and applications. MIT press, 2005.
[16] Martin Rosvall and Carl T. Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 108(4)1118--1123, 2008.
[17] M. E. J. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577-888) 2006.
[18] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-137) 1983.
[19] Tiago P Peixoto. Efficient monte carlo and greedy heuristic for the inference of stochastic block models. Physical Review E, 89(1):11204, 2014.
[20] M. Rosvall, D. Axelsson, and C. T. Bergstrom. The map equation. The European Physical Journal Special Topics, 178(1):13-23, Nov 2009.
[21] Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5-13, 1993.
[22] Léonard Blier and Yann Ollivier. The description length of deep learning models. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[23] Ethan Perez, Douwe Kiela, and Kyunghyun Cho. Rissanen data analysis: Examining dataset characteristics via description length. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8500-8513. PMLR, 18-24 Jul 2021.
[24] Tiago P. Peixoto. Hierarchical block structures and high-resolution model selection in large networks. Phys. Rev. X, 4:01 1047, Mar 2014.
[25] Kai Yu, Shipeng Yu. and Volker Tresp. Soft clustering on graphs. Advances in neural information processing systems, 18, 2005.
[26] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905 2000.
[27] Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395-416. Dec 2007.
[28] Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '14 page 701-710, New York, NY, USA, 2014, Association for Computing Machinery.

---

[29] Aditya Grover and Jure Leskovec. Node2vee: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '1, page 355-864, New York, NY, USA, 2016. Association for Computing Machinery.
[30] Aditya Tandon, Aiiad Albeshri, Vijey Thayananthan, Wadee Alhalabi, Filippo Radicchi, and Santo Fortunato. Community detection in networks using graph embeddings. Physical Review E, 103(2);022316, 2021.
[31] Sadamori Kojaku, Filippo Radicchi, Yong- Yeol Ahn, and Santo Fortunato. Network community detection via neural embeddings. arXiv preprint arXiv:2306. 13400, 2023.
[32] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889-898, 2017.
[33] Nairouz Mrabah, Mohamed Bouguessa, Mohamed Fawzi Touati, and Riadh Ksantini. Re- thinking graph auto-encoder models for attributed graph clustering. IEEE Transactions on Knowledge and Data Engineering, 2022.
[34] Maedeh Ahmadi, Mehran Safayani, and Abdolreza Mirzaei. Deep graph clustering via mutual information maximization and mixture model. Knowledge and Information Systems, Apr 2024.
[35] Sambaran Bandyopadhyay and Vishal Peter. Unsupervised constrained community detection via self-expressive graph neural network. In Uncertainty in Artificial Intelligence, pages 1078-1088. PMLR, 2021.
[36] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 24(127):1-21, 2023.
[37] Tsuyoshi Murata and Naveed Afzal. Modularity optimization as a training criterion for graph neural networks. In Complex Networks IX, pages 123 135, Cham, 2018. Springer International Publishing.
[38] Oleksandr Shchur and Stephan Günnemann. Overlapping community detection with graph neural networks. Deep Learning on Graphs Workshop, KDD, 2019.
[39] Liu Yue, Xia Jun, Zhou Sihang, Wang Siwei, Guo Xifeng, Yang Xihong, Liang Ke, Tu Wenxuan, Liu Xin Wang, et al. A survey of deep graph clustering: Taxonomy, challenge, and application. arXiv preprint arXiv:2211.1287. 2022.
[40] Su Xing, Xue Shan, Liu Fanzhen, Wu Jia, Yang Jian, Zhou Chuan, Hu Wenbin, Paris Cecile, Nepal Surya, Jin Di, et al. A comprehensive survey on community detection with deep learning. IEEE Trans. Neural Netw Learn. Syst, 2022.
[41] Andrea Lancichinetti and Santo Fortunato. Community detection algorithms: comparative analysis. Phys. Rev. E, 80:0561177 17, 2009.
[42] Rodrigo Aldecoa and Ignacio Marin. Exploring the limits of community detection strategies in complex networks. Sci. Rep., 3:2216, 2013.
[43] Lovro Šubelj. Nees Jan van Eck. and Ludo Waltman. Clustering scientific publications based on citation relations: A systematic comparison of different methods. PLOS ONE, 11(4):1-23, 04 2016.
[44] C. E. Shannon. A mathematical theory of communication. Bell Syst. Tech. J., 27:379-423, 1948.
[45] R. Lambiotte and M. Rosvall. Ranking and clustering of nodes in networks with smart telepor- tation. Phys. Rev. E, 85:056107, May 2012.
[46] David A. Huffman. A method for the construction of minimum-redunddan codes. Proceedings of the IRE, 40(9): 1101-1101, 1952.
12

---

[47] Martin Rosvall, Alcides V. Esquivel, Andrea Lancichinetti, Jevin D. West, and Renaud Lam- biotte. Memory in network flows and its effects on spreading dynamics and community detection. Nature Communications, 5(1))4630, Aug 2014.
[48] Anton Holmgren, Christopher Blöcker, and Martin Rosvall, Mapping biased higher-order walks reveals overlapping communities, 2023.
[49] Jelena Smiljanić, Christopher Blöcker, Daniel Edler, and Martin Rosvall. Mapping flows on weighted and directed networks with incomplete observations. Journal of Complex Networks, 96))cnabb44, 12 2021.
[50] Daniel Edler, Jelena Smiljanić, Anton Holmgren, Alexandre Antonelli, and Martin Rosvall. Variable markov dynamics as a multi-focal lens to map multi-scale complex networks, 2022.
[51] Scott Emmons and Peter J. Mucha. Map equation with metadata: Varying the role of attributes in community detection. Phys. Rev. E. 100:022301, Aug 2019.
[52] Aleix Bassolas, Anton Holmgren, Antoine Marot, Martin Rosvall, and Vincenzo Nicosia. Map- ping nonlocal relationships between metadata and network structure with metadata-depenndet encoding of random walks. Science Advances, 8(43):cabn7558, 2022.
[53] Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra. Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference on Learning Representations, 2023.
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[55] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[56] Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. Advances in neural information processing systems, 30, 2017.
[57] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[58) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, Perfo-merformance Deep Learning Library. In Advances in Neural Information Processing Systems 32, pages
Curran Associates, Inc., 2019.
[59] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1903vv/903.000 2019.
[60] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 78:0461 10, Oct 2008.
[61] Simone Romano, James Bailey, Vinh Nguyen, and Karin Verspoor. Standardized mutual infor- mation for clustering comparisons: One step further in adjustment for chance. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 11 1153-1151, Bejing, China, 22-24 Jun 2014. PMLR.
[62] Yixuan He, Xitong Zhang. Junjie Huang, Benedek Rozemberezki, Mihai Cucuringu, and Gesine Reinert. Pytorch geometric signed directed: A software package on graph neural networks for signed and directed graphs. In Learning on Graphs Conference, pages 12-1. PMLR, 2024.
[63] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Li Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs Advances in neural information processing systems, 33:22 18-22133, 2020.
13

---

[64] Amir Ghasemian, Homa Hosseinmardi, and Aaron Clauset. Evaluating overfit and underfit in models of network community structure. IEEE Transactions on Knowledge and Data Engineering, 32(9):1722-1735, 2020.
[65] Alcides Viamontes Esquivel and Martin Rosvall. Compression of flow can reveal overlapping module organization in networks. Phys. Rev. X, 1:021025, Dec 2011.
[66] M. Rosvall and C. T. Bergstrom. Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems. PLoS One, 6:e18209, 2011.
[67] David F. Gleich. Pagerank beyond the web. SIAM Review, 57(3):321-33,, 2015.
14

---

A Map equation details
Let G = (V, E) be a graph with nodes V, links E, and let the E Ri denote the non-negative weight on the link from node in closed form as Pu s,/ Evev 8, in undirected graphs, where s, = Dvev Weo is node u's strength. In directed graphs, Pu can be calculated numerically with smart teleportation and a power iteration by solving the recursive set of equations Pv = Luvve and + (1 (1-a) a) Σnev Putuv. where
Further, let Pa be node u's ergodic visit rate, which can be calculated
s Ever Wuv is node u's out-strength, buo = Wye/ LVEv Weo is the random walker's transition probability from node to node and ar is teleportation parameter, typically set to 0.15 [45] Smart teleportation similar to PageRank [67] but, instead uniformly teleporting to nodes, the random walker teleports to links proportional to their weight.
calculates the average For given partition M of the nodes into modules, the map equation [T6]
per-step description length also called codelength for describing the position of random walker on the graph:
L (M) = (Q) + Σ Pm (Pm).
MEM
Here, 9 -m m 9m is the random walker's module entry rate, 4m Em Enem Pubue is module m's entry rate, and Q = /m/ m M is the set of normalised module entry rates, Pm = Mexit Eu Pu is the rate which the random walker moves module m, including the exit rate Mexit Zuem Eogm Patuv, and Pm Mexi Pm U {Pa/Pm Pm m} is the of normalised node visit rates and exil rates for module m.
A.1 Rewriting the map equation
The map equation be rewritten by expanding the entropy terms and cancelling common factors
L (M) qQ)
Σ Pm H (Pm)
(5)
Qm
log2
Im
Σ
Dm
Mexit
loga
Mexit
Σ umm
Pu
logz
Pu
(6)
Dm
Pm
Dmi
Pm
mEM
mEM
Applying logarithm rules gives
Σ + mEM
Im log, 9m
Σ
Im logg
(7)
mEM
Σ
Mexi log, Mexit +
Σ
Mexit loga Pm
Σ
Σ
Pu log, Pu + Σ
Σ
Pu loga Pm.
(8)
mEM
mEM
mEM uem
mEM wEm
and further simplification yields
= logg
4m loga 9m
+
Σ
Pm loga Pm
Mexi loga Mexit
Σ
Pr: log Pu-
(9)
MEM
mEM
mEM
WEV
In undirected networks where 9m
Mexits this can be further simplified (20]
= glog2
2
Σ 9m loga 4m +
Σ Pm loga Pm
Σ WVV
Pa logg Pu.
(10)
mEM
MEM
The last term in Equation (O).. that the nodes' contribution the codelength, is constant because it does not depend on the module structure, and can be omitted during optimisation.
A.2 Node flow with soft cluster assignments
While the nodes' codelength contribution is constant with hard clusters (Equation (TO)), expressing the map equation with soft cluster assignments allows modelling the flow of nodes that are assigned more than module in at least two different ways which we illustrate in Figure
The first option is to reflect the nodes' partial cluster assignment for assigning codewords. Consider node with visit rate Pu. and partial assignments of to clusters mı whose usage rate is pm1 and 2
15

---

.222
2811
332
-322
.281
232
.32
-322
.281
232
.464
.361
.322
.322
2811
.222
.322
332
.281
232
L 3.12 bits
L 3.13 bits
(d)
.258
.258
258
258
258
.55
258
258
258
258
.288
258
258
.258
258
258
258
258
.258
258
3.3 bits
3.1
Figure Modelling node flow with soft cluster assignments. The labels show each node's contribution the overall codelength based on their visit rates. (a) The one-level partition where all nodes belong to the same community. (b) With hard communities, the middle node must be assigned to either the blue orange community. Here, this leads to higher codelength than for the one-level partition. (c) Reflecting nodes' partial assignments the codelength contributions splitting them into several smaller pieces whose visit rates
the original node's visit rate. Important objects are split into several less important objects, requiring longer codewords because of their lower visit rates. Overall, this tends to increase the codelength and prevent identifying overlapping modules. (d) Treating nodes' contribution to the codelength as constant keeps the nodes intact and allows important nodes to retain their higher visit rates, leading shorter codewords. As the codelength highlights, only this approach would identify communities in this example.
to cluster ma whose usage rate is Pm.- Then, half of u's flow, that is Ps. falls into each of the two clusters and u's contribution to the overall codelength is Pu 2 Ipm 2
loga Pu. Pe
Pa.. In general, loga pamg
let node w's assignment to cluster m, be Sui [0, 1] with Σ Sus 1. and let m,'s usage rate be Pm. Then, node u's contribution to the overall codelength is - -2, SurPa log, SuiPu Essentially, this approach splits each node with assignments more than one cluster into corresponding parts, resulting in potentially many small pieces with low visit rates.
Pm;
The second option is to treat the nodes indivisible when computing their codeword lengths but reflecting their soft assignments in the contribution to the overall codelength. Using the same example above, node w's contribution to the overall codelength is 2 loga Ps. 2 loga Pa. which Pm1 lower because the values inside the logarithms are bigger. general, u's 's contribution to the codelength is Σ; SuiP.. loga Pmn." appear inside the logarithm.
pmy
where the difference to the previous option is that Sui does not
16

---

B Results on synthetic networks with different (G)NN architectures
Here, we report further results on the synthetic LFR networks with planted communities for Neuromap. DMoN, NOCD, DiffPool, MinCut, and Ortho using the following architectures: a dense linear layer, a 2-layer MLP, a 2-layer GCN, and 2-layer GIN. The setup described in the main text.
B.1
Linear-layer-basee results
undirected, k
undirected, k
14
directed, 7
directed, k 14
1.0
1.0
1.0
1.0
AMI
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
10a
10a
10a
10a
10a
10a
10a
10a
10a
10
10
10"
10"
10"
10"
0.2
0.4
0.8
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.6
0.8
J
true
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Figure 8: Linear-layer-based results for deep-learning community-detection methods on synthetic LFR networks with planted communities. The results show averages of partition quality measured by AMI and number of detected communities [M]. The shaded areas show one standard deviation from the mean.
B.2
ML.P-based results
undirected,
undirected,
14
directed,
directed,
1.0
1.0
1.0
AMI
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.1
0.6
0.8
10a
10a
10a
10a
10a
10a
10a
10a
104
10
10
10a
10"
10"
10"
109
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
"
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Figure 9: MLP-based results for deep-learning community-detedd methods on synthetic LFR networks with planted communities. The results show averages of partition quality measured by AMI and number of detected communities [M]. The shaded areas show one standard deviation from the mean.
17

---

B.3 GCN-based results
undirected, k
undirected, k 14
directed,
directed, k 14
1.0
1.04
1.0
1.0
AMI
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.6
0.8
10a
10a
10a
10a
102
10a
10a
10a
10'
10
10
10"
100
109
109
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.6
0.8
true
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Figure 10: GCN-based results for deep-learning community-detection methods on synthetic LFR networks with planted communities. The results show averages of partition quality measured by AMI and number of detected communities [M]. The shaded areas show standard deviation from the mean.
B.4 GIN-based results
undirected, k =
undirected, k
14
directed, 7
directed, k 14
1.0
1.0
1.0
1.0
AMI
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.8
10
10a
103
103
10a
10a
102
10a
10
10
10
109
10P
10"
10"
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.8
true
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Figure 11: GIN-based results for deep-learning community deteection methods synthetic LFR networks with planted communities. The results show averages of partition quality measured by AMI and number of detected communities [M]. The shaded areas show standard deviation from the mean.
18

---

C Results on Real-World Networks
Here, we report further results on real-world networks for setting the number of hidden dimensions 4yn and the maximum number of communities to 8 vn. Specifically, we visualise the average detected number of communities per loss function and neural network architecture for each dataset. We tabulate the average AMI and average number of detected communities, including standard deviations. Two-sample t-tests show when Neuromap or baseline performs significantly better than the other.
C.1 Number of detected communities on real-world networks
Neuromap
DMoN
NOCD
DitiPool
Ortho MinCut
Linear
MLP
GCN
GIN
SAGE
Cora
CiteSeer
Pubmed
PC
Photo
10R
16
CS
Physics
Cora ML
Wiki CS
ogb-andiv
Figure 12: Average detected number of communities real-world networks. Colours indicate methods while shapes indicate (G)NN architectures. The dashed horizontal lines show the correct number of communities for each dataset while the solid horizontal lines show the chosen maximum allowed number of communities, here 8 = vn. DiffPool ran out of memory on the ogb-arxiv dataset. We omit Infomap in the plot due to the large number of detected communities.
19

---

C.2 Tabulated AMI results on real-world networks
Here, we report the detailed AMI performance for Neuromap, DMoN, NOCD, DiffPPol, MinCut, Ortho, and Infomap on weal-world networks for setting the number of hidden dimensions to 4yn and the maximum number of communities to s Vn. When several of the pest-perfrrming methods achieve similar AMI, we use an independent two-sample t-test to determine whether one of them can be considered to perform better than the other. In cases where their performances do not differ significantly, we mark both as best.
Table 2: Average AMI in % (higher is better) and their standard deviations real-world networks. For each dataset, we highlight the best scores in bold and underline the second-best score. We tested each method with 2-layer MIP, GCN, GIN, and SAGE architectures, except for Infomap, which is not based on deep learning. OOM stands for "out of memory".
Method
Arch.
Com
CiteSeer
PabMed
PC
Ploto
CS
Plysies
Coca ML
Will CS
ogb-antiv
Neuromap
LIN
7.9
19.5+
1722 12.2
00:00.1
1.0 0.0
76.7
06.5 1.2
214=113 11.9
41.9
2.3
7.7
MI.
36.6
L
252 L.
2.64
30. 11.2
78:12:20
65.0+222
$1.5 115=11
43.0 2.4
32.0 13
OCN
38.5+22 2.0
162+ 3
205+ 1.2
62.+225
66.0-30
7..4+166
60.5+114 1.4
96.1
1.2
41.1 3.2
42.5+112 1.7
GIN
46.1120
28.1
2.61177
43.2
582160
52
57.5
54.9 4.5
2.
SAGE
1.
18.31
20.11.0
4..6
88.1
70.01.4
51.
39.1
44.8
1488122
43.6 13.610
DM&N
LIN
1.2
5.4.16
0.7
3.
4.
25.2 10.8
5.7
0.108.
4..9
3.0
MLP
36.6=11.2
2.
6.
15.4
40.2
1-2
12.8
GCN
88.6
2.34
18.32:02
0.3
0..
58.1 0.2
28.4 #:4
35.2
10.5++0..
170++00
05.6+008
20.2+:32
SAGE
NOCD
LIN
5.1
0.1++003
4.2+225
0.9
60.3
73.9
63.3
59.1
46.2
43.8
42.4
26
0.6
06.3 1.8
63.7
S7.6 1.1
28.7
SAGE
19.8 0.8
1.4
03.7
63.7
42.4
42.4 0.4
DitPPol
00:00
MLP
9.0
6.7 + 1:3
189 1.4
1.440.4
0.
61.5 4.8
10.1
1-2
25.8 2.6
OOM
39.8
2.0
1.5
638 7.5
73.3
2.0
02
$3.5
$5.7
GIN
30.9
3.6
21.3
3.9
14.5 13.
92.8 446
30.3
3.9
41.0
$1.6
2.8
11.3 1.11
OOM
SAGE
38.5
2.4
16.4 L.4
21.9 1.5
3.1 1.0.
16.7 1.1.1
71.4 5.4
59.2
29.6
2.2
S8.1 2.8
0OM
MinCu:
LIN
26.1
2.5
16.5 1.3
2.0
0.0 0.0
0.0
57.5 0.6
36.8 L. 0.9
30.4
1.2
16.0 1.4
3.8 3.5
MLP
34.7
= 6.66
20.55+00.1
6.1 2.4
0.0 1.0
6.2 9-9
53.9 = 6.4
29.4+99.. 9.9
29.6
= 1.8
26.1 4.2
8.0 2.7 38.9 + 4.7
GCN
26.2
1.5
12.72007
1100228
15.9 21.2
46.2
16.6
44.7 = 8.8
12.2 6L8.
26.2 = II.
12.1 0.5
GIN
38.3 3.8
18.++007
10.8+413
6.8+0.88
35.5 19.3
$2.7
19.5
51.7
5-4
6.9 4.5.
1.3+6.2
10.5+ 7.3
SACIE
31.5 1.5
16.2++0.8
15.5++0.3
41.6+00.6
46.9 0.5
47.1
+ 0.5
30.5 + 2.4
$5.9 - 0.7
$2.3 + 0.5
35.0 1.5
Onho
LIN
7.0 0.7
5.++07
16.5+0044
18.8
26.7 11.4
45.4+22.0
26.7 1.5
15.6 1.1
25.6 0.9
19.1+-03
MLP
5,3 0.3
0.8
0.44104
19.8 1.38
30.5 40
16.1
32.0 1.1
5,3
1.5
25.88.00
18.5104
OCN
22.9
0.9
10.9....
158 0.5
10.71.0.3
46.011 1.4
$1. 1.0
32.4 1.0
19.2 1.1
$2.1
36.51.07
GIN
81.7
01 1.3
17.8
13.
$1.
4..3
44.1
0.6
20.0
267 1.1
20.4::0.6
26.1 16.1::00
SAGE
18.0 0.9
8.4
9.9
3..4
46.5 2.6
52.8 a 1.2
36.4 1.1
16.3 1.1
31.7 7.722:0.
24.9
Infomap
30.2 0.2
281
16.0
4..5
67.3 1.1
40.6 a 0.2
26.7 0.1
35.7 35.700..3 0.3
$7.9
30.9
C.3 Significance of best Neuromap results vs. best baseline
Table 3: Independent two-sample t-test between 25 samples of AMI values for Neuromap vs. the best baseline for 4 hidden features and = Vn. The p-values indicate for which datasets the null hypothesis "the samples have the same mean" can be rejected. Blue p-values highlight cases where Neuromap performs significantly better than the best bascline; red p-values highlight cases where the best baseline performs significantly better than Neuromap.
Dataset
Best Neuromap
Best Baseline
p
Cora
GIN
46.1 + 2.0
NOCD MLP
46.1 + 1.1
0.92
CiteSeer
GIN
23.1 + 1.2
NOCD MLP
34.8 0.9
3.3e 35
PubMed
GIN
24.6 + 1.7
DifiPool GCN
23.7 1.5
0.05
PC
GCN
52.1 + 2.3
NOCD GCN
1.9
0.69
Photo
GCN
65.0
+ 3.8
NOCD SAGE
6.67
0.14
CS
MLP
78.1 1 2.0
NOCD MLP
7.7
4.4e-10
Physics
LIN
1.2
DifiPool GCN
6.64
1.5e
Cora ML
SAGE
39.1
NOCD MLP
1.4
5.7e-18
Wiki CS
SAGE
44.8 2 2.2
NOCD GCN
4.6
0.23
ogb-arxiv
SAGE
43.6 - 1.0
NOCD GCN
4.4
0.38
20

---

C.4 Significance of Neuromap results vs, Infomap
Table 4: Independent two-sample t-test between 25 samples of AMI values for Neuromap with different (G)NN architectures vs. Infomap for 4yn hidden features and = vn. The p-values indicate when the null hypothesis "the samples have the same mean" can be rejected. Blue p-values highlight cases where Neuromap performs significantly better than Infomap: red p-values highlight cases where Infomap performs significantly better than Neuromap.
Dataset
LIN
MLP
GCN
GIN
SAGE
Cora
0.05
6.8e-3 3
2.4e-8
8.1e
9.4e-15
CiteSeer
7.5e 12
4.2e
2.8e-20
0.06
2.1e
PubMed
0.65
2.1e-16
4.2e-16
2.5e-18 188
2.2e-17
PC
1.8e
4.7e 14
6.0e
2.4e
3.9e
Photo
1.8e 42
6.6e
2.3e
0.48
5.2e
CS
7.6e 36
1.1e 32
2.9e 32
7.5e 26
5.1e 28
Physics
2.7c-86 35
1.2c-28
5.8c 31
3.2e
2.7c-27
Cora ML
9.6e
1.4e
0.01
7.0e 5
1.7e
Wiki CS
7.0e 9
8.3e 12
4.5e
3.9e
3.4e
ogb-arxiv
1.8e-16
1.3e-11
5.4e-16
4.6e-13
8.9e-23
C,5 Tabulated number of detected communities on real-world networks
Here, we report the average number of detected communities for Neuromap, DMoN, NOCD, DiffPool, MinCut, Ortho, and Infomap on real-world networks for setting the number of hidden dimensions to 4yn and the maximum number of communities to 8 Vn.
Table 5: Average number of detected communities and their standard deviations on real-world networks. We tested each method with 2-layer MLP, GCN, GIN, and SAGE architectures, except for Infomap, which is not based on deep learning. OOM stands for "out of memory".
Method
Andh
Cam
Plycics 365
Wi&CS
ogteanxie
Nearomap
MI.P
2.5
30-088
1.+
483-1.
123 17.5=22
GCN
6..4+4.4
21:2=:3
19.6
613=007
S1.1 7.0
203
2.70
1.:
64:13
68.08.
14.222
149=18
220-27
6.
5.1.11
SAGB
15.
81113
220
41.3
48
365
DMAN
LIN
155
18.5
25.1
25:::117
2.1
1.
10.0
7.
65:2622
10.9 5.6
76 16.26.0
MLP
520 0.2
37.9 D3
21.82-320
51.42:305 36.3
$1.2 15.0
63.
76.3
5500202 0.2
92.9 27.1
1180 12.2
GUN
51.9 03.9:2003
36.0 8 DO
100.0 0.0
117002000 0.0
$7.0
135.0.2 D.
1860050000 0.0
548:000
105.0 2
412.
GIN
51.0 01B
$7.0
1.0
10000-0000 0.0
1100
6.1
$1.-9-11 1-7
156.9 033
185-9-00.
54.5 0.8
97.3 1.0
8 71-3
SAGE
51.8 0.4
58.0 2: D.O
100.0 0.2
116.8
0.7
56,5 0.4
135.0 42
18600 0.11
54.82044
10800 :
412.0
NOCD
20.3 :: 10.2
17.5.8221.5
12.1 3-3
1.7 1
1.0.0.02 0.2
34.7
21.5
24:
11:2.2
129
MLP
1.1
9.9
92. 27
145
GCN
51.11
709-77
540=088
24.2
20.9
249-26
78.
36.6
320
25.1
35.7
DutPool
26:1111
0.0
12205
1.100
6.161
81155
10202
4.
COM
MLP
51.8
0.2
4.6
2.404
16.5
56.0
10.014
COM
GUN
J8.2
1..
5.7.
128423
190
T.T
OOM
GIN
11.6 2.2
17.4
7.316
85500
62
7.0
6.1
16:3
4.7
OOM
SAGE
49.7
58.0 0.2
2.0
82:00
0.7
10.7
10.:21
04
10.12:12
COM
MinCor
LIN
51.3 0.9
54.5 1.9
8.0
10202
11100
29-5 8.2
56.0 010)
48.5 4.9
81.6 50.0
MLP
61.5 02.5::100
58.0 D.O
2.A
10:00
12440.4
41.5
1186- 24.6
38.
1014
19.2
165.0 10.5
GCN
52.0 0.0
58.0 2: DUO
154.D
60.5 25.2
62.8 20.8
158.2
187.0 40.2
0.00
108.0
6.0
97.4 20.5
GIN
21.5 20.0
56.7 2: S.5
15.0
110 4.2
10.1 d: 5.5
75.0 63.8
6.1 6.7
JB. 6.0
404 14.5
10G 4.2
$2.0
1.0.0
0.3
185.0
170.5
550
6.0 105.0
ST45
UT.4
3655
12.0
126.9
3 9.1
379.8 22.1
90.2
8L. 22.4
Infoomp
282.2 1.1 678.
9219 8.1
153.1
4.4
834A
11608 11.4
3.7.1+3.8
7.7.0-8..4
(8-00 22-1
21

---

D Results on real-world networks with fixed number of hidden channels
We provide further results on real-world networks with a different configuration the neural networks: we set the number of hidden channels to 512 and set the maximum number of communities to the "ground-truth" number of communities, that is |
D.1
Average Achieved AMI
80
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Infomap
Linear
MLP
GCN
GIN
SAGE
Informap
60
AMI 1000
20-
0-
Cora.
CiteSeer
Pubmed
PC
Photo
60
40-
AMI
0-
CS
Physics
Cora ML
Wiki CS
ogb-arxiv
Figure 13: Average achieved AMI on real-world networks (higher is better) for |Y], that is. the "ground-truth" number of communities. Colours indicate methods while shapes indicate neural network architectures. DiffPool ran out of memory on obg-arxiv.
D.2 Average Number of Detected Communities
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
Linear
MLP
GCN
GIN
SAGE
10.0-
7.5
0.0
CiteSeer
Pubmed
Photo
20-
10
Physics
Cora
Wiki
ogb-arxlv
Figure 14: Average detected number of communities real-world networks. Colours indicate methods while shapes indicate neural network architectures. The dashed horizontal lines show the correct number of communities for each dataset, which is also the maximum allowed number of communities. We omit Infomap in the plot due to the large number of detected communities.
22

---

D.3 Tabulated AMI results on real-world networks
Here, we report the detailed AMI performance for Neuromap, DMoN, NOCD, DiffPPol, MinCut, Ortho, and Infomap on real-world networks for setting the number of hidden dimensions to 512 and the maximum number of communities s |Y| When several of the perffrrmnnn methods achieve similar AMI, we use an independent two-sample t-test to determine whether one of them can be considered to perform better than the other. In cases where their performances do not differ significantly, we mark both as best.
Table 6: Average AMI in % (higher is better) and their standard deviations real-world networks. For each dataset, we highlight the best scores in bold and underline the second-best score. We tested each method with 2-layer MLP, GCN, GIN, and SAGE architectures, except for Infomap, which is not based on deep learning. OOM stands for "out of memory".
Method
Auch.
Cosa
CleeSeer
PubMed
PC
Photo
CS
Plysics
Cora ML
WilL CS
ogb-arxiy
Neuomap
LIN
10.9 10.3
6.9
0.3 37
0.0 = 0.0
0.0 0.0
7.77
08.5
5.3
9.1
11.7=11.1 11.0
MLP
82.7 2: 4.6
186 2.6
22.9 4.6
33.6 13.
513 11.1
748:2:4
0.
216
2.0
38.7 488
30.0::14 1.
GCN
11.7 2:0.0
128
19.22.3.8
49.9
61.42 4.2
68.4224
5.0
26.6 2.
36.9 42
00.2
0022:10 1.5
GIN
05.8
16.1
16.1
3.
30.3
65.2
450
20. 8.5
21.7
222 2.2
SAGE
32.5+ 5.0
12.9
69.2
690+28
66
262222
41.0=22.
599 1.6
DMcN
LIN
18,3 11.7
6.2
9.1
10
2.1221
12.99
19.9
120
9.1::112
08
MLP
06.1 5.2
20.2:13..6
19.0-16.5
42
36.7
12.1111
515:1:5
512
8.5
3..6
29.7
OCN
37
377.21:44 4.2
18.4
19.3.14.0
66.11. 1.9
ST.7 2.8
06.5 06.110
1..116611
31.8 L 3.5
2..221.2
00.6 0.04
GIN
27.4 8.3
11.5
1..3
25.8
12.6 4.9
89.5
27.4 2.1
22.22:3..5
27.1
SAGE
37.0
18.0 3.44
17.5
46.4
38.0
66.3 1.6
47.2 4.8
33.0 8.8
38.6
60.2 0022::00 1.4
NOCD
LIN
2.0 1.3
3.0 1.6
0.255:005
1.0 2.5
2.1 3.0
2.75
1:2:1:4.5
5.6 1.2
2.
1.0.1.44
MLP
83.1
14.7
29.6
10.5
261
47.9
25.1
15.4
740 1.4
50.8
39.3 6.3
2.
28.9
115
GUN
4.66
1
1.3 T.3
22
64.4 4.1
68.0
7.3
216 11.2
42
10.6
GIN
15.1
1..24.444
17.0-16.6
3.7
40.3 4.1
60.9 3.8
42.44.9 4.9
SL5 3.9
27.1332
SAGE
12.711..77
116188
22.6..4.9 4.9
47.7 17.7122
633 3.5
69.7
1 1.0
54. 4.7
36 2.8
41.7 13
22
Ditiooo
LIN
0.8.1.1.
1.2.0.
0.0
0.0 0.0
0.0
20,0 14.2
17.2 182
0.0 0.0
0.0
OOM
MLP
4.9.1 1.3
1.141
10.3..3..
166.0.4 0.4
3.5.1 1.4
50.6667
304 7.9
S.L 1.0
1..3.3344
DOM
OCN
28.5:1.4.11
12.41.255
18.33...
9..4
6.66
50.6
6.7
225 5.1
20.3 4.8
DOM
GIN
14.02-4.88
3.1
2.1 1.7
5.0 D.6
5.7 BUB
28.1
28.2 1..22:122 12.2
12.5 B.8.
5.1
COM
SAGE
24.4
1..25:2
28.9
3.1 0.6
1282
65.6 4.5
03.6 9.0
17.1 2.9
3U. 3.2
DOM
MinCat
LIN
30.6:t:4.3
16.7
21.0 1.0
3.1 6.5
1.0
0..9-13..0
S3.T
= 54
19.4 1644
$8 : 21.
MLP
2:..5
15.5 3.5
19.7 2: 6.3
28.8 13.3
2..4 2.7
66.5
4L3
312
3T
GCN
31.911...7
19.1 2.88
20.2114..1 18.5224422 4.2
46.3 2.0
36.11:2.
12.11114
46.7 1..35.53
28.2
0.2
11.199
27.7 1.4
GIN
05.7 1.9
18.9 3.0
$2.4 1. 7.5
40.2 10.21.1 4.9
60.7 1:4
96.1 4.3
220
2.
2 11.0
142 1 4.6
SAGE
23..6.1...4
13.9 1.3
1T.1 1.111.1
63.7 1. 2.5
$4.0 2.8
02.3111.
962
1.88
29.4 2 5.7
ST.1 19
373
17-3100 0.5
Onho
LIN
8.2 1.2
8.0.1:23
15.7 4.6
12.4 6.5
13.6
5T.4
42.6
13615. 5.1
12.7 3.7
1..7.1.00
17.1111
MLP
4.4 1.0
3.5 1.0
8.3.1.300
22-7
21.11:2
55.8127
29.7 7.4
13:11
28.1118
17.9 1.3
OCN
22.0-1:3.0
10.2-t:2.1
8.4
45.1 1.9
$4.4 3.6
02:2-12.0
82.0
1200::00 5.9
19.1 32
35.7 19
$16
GIN
19.2
0.4++-24 2.9
0.3 3.0
$7.4
3.0
51.8+9.77
31.7
5.4
17.0 2.6
20.2++2
25.5+122 122
SAGE
21.5
7.6.1 2.5
15.9 3.38
29.4
36.6 3.2
60.911211
40.1 6.3
15.9 322
34.21.2
29.
Inforop
35.2++.0.2
23.6++0.1
16.0++0.1
49.5 0.5
57.3 1.1
0.2
267 0.1
35.7
$7.0++02
35.9 33.9-0... 0.1
D.4 Significance of best Neuromap results vs. best baseline
Table 7: Independent two-sample t-test between 25 samples of AMI values for Neuromap vs. the best baseline for 512 hidden features and s |Y The p-values indicate for which datasets the null hypothesis "the samples have the same mean" can be rejected. Red p-values highlight cases where the best baseline performs significantly better than Neuromap.
Dataset
Best Neuromap
Best Baseline
p
Cora
GIN
35.8 = 4.1
DMoN GCN
37.2 + 4.2
0.25
CiteSeer
GIN
16.1 = 3.2
NOCD MLP
29.6 + 10.8
2.4e 06
PubMed
MLP
22.9 = 4.6
NOCD SAGE
22.6 + 4.9
0.83
PC
GCN
49.9 = 3.6
NOCD GCN
49.6
0.73
Photo
GCN
61.4=4.2
NOCD GCN
64.4
0.02
CS
MLP
74.8 = 2.4
NOCD MLP
74.0
0.15
Physics
LIN
59.5
NOCD MLP
56.8
0.17
Cora ML
GCN
26.5 2.8
NOCD MLP
5.3
-2
Wiki CS
SAGE
41.0
NOCD GCN
12.3
0.05
ogb-arxiv
GCN
40.2 - 1.6
NOCD GCN
43.6 + 0.5
4.8e
23

---

D.5 Significance of Neuromap results vs. Infomap
Table 8: Independent two-sample t-test between 25 samples of AMI values for Neuromap with different (G)NN architectures vs. Infomap for 512 hidden features and = Y The p-values indicate when the null hypothesis "the samples have the mean" can be rejected. Blue p-values highlight cases where Neuromap performs significantly better than Infomap: red p-values highlight cases where
Infomap performs significantly better than Neuromap.
Dataset
LIN
MLP
GCN
GIN
SAGE
Cora
1.6e
0.01
9.2e-6
0.47
0.02
CiteSeer
6.4e
1.0e-15
1.le-15
2.7e -1
5.1e 16
PubMed
1.2e-16
1.5e-7
0.01
0.95
4.9e
PC
1.8e
5.1e
0.55
4.4e
1.6e
Photo
1.8e
0.02
6.3e
5.7e-5
1.le
CS
6.2e-24
24
198e-29
29
3.0e
2.5e
8.8e~26 26
Physics
3.1c-16
6.5c-19
7.3c
1.6e-12
7.2c-16
Cora ML
1.7e-14
5.
2.5c-14
9.9e
6.5e-15
Wiki CS
2.4e-11
0.42
0.29
5.3e
3.4e
ogb-arxiv
3.7e-68
4.5e 14
2.0e-12
1.3e-19
5.4e-12
D.6 Tabulated number of detected communities on real-world networks
Here, we report the average number of detected communities for Neuromap, DMoN, NOCD, DiffPool, MinCut, Ortho, and Infomap on real-world networks for setting the number of hidden dimensions to 512 and the maximum number of communities to Y|
Table 9; Average number of detected communities and their standard deviations real-world networks. We tested each method with 2-layer MLP, GCN, GIN, and SAGE architectures, except for Infomap, which is not based deep learning. OOM stands for "out of memory".
Plysic
CS
ugberraiv
Neusompp
OCN
DMuN
6.9
1.2
30:000
2.3:::10
4.5.
60=
5.1
MLP
3.0000
10.0
80::000
15.0::00
5.0.C...0
700002
10.0
40.0
OCN
7.0 1..
6.002.000
3.0000
80::0000
15.0::00
5.0.1.022
7:0022
10.0
40.0
GIN
7.0+0
5.9-+.0.3
$0-+000
0.-+00..
80-+-00
1500+000
5.0
T0-
1000+000 0.2
30.5 +
SAGE
7.0 0.2
5.9 0.3
3.0=0000
1000000. 0.0
8.0+-00 0.0
15.0=000
5.0
7.
10.0+ 0.0
40.0- 0.0
MOCD
LIN
7:0.2:100 11.0
1.5 1.4
L7
3.211.1
28:21:2
10:8::2.
T. D.0
9.5
1I.1
MLP
7.0.1:10.
6,0 1.001:11.0
3.0:::00
9.9
T.4:1:0.
13.5 1.1
T. 0.2
9.8 n6
20.9
GCN
7.0 01.
6.0 0.0
3.0:::0
100 0.0
8.0 0.0
1500:000
6.0.1..0
TO 0.0
10.0 0.0
36.21 1.4
GIN
6.2.1 016
5.5 0.5
2.9 2933
0.6
63 1.0
12.7 1.4
48400
64 0.6
9.4 066
20.3 1.22
SAGB
T.0.0.0..
6.0 00 D.)
3.0:::000
100 8: 0.2
8:0-2.00 0.0
1500::0000
6.0
To: 0.0
100 0.0
31.8 1.8
DinPad
LIN
2.7
8:2 0.6
1.0:000
1.0+0000
1.0 0.0
6.9 2.5
1.5
10= 0.0
25 0.6
O0M
MLP
7:0 8.0
6.0 I.O
5.0 0.0
DA
2.6 0.7
11.6
5.0
70= B.0
6.2 0.9
OOM
OCN
7.0 8.0
6,0 I.O
3.0 0.0
6.3 1A
5.777.
10.0
5.n.6..0
70 B.0
5.5 100
OOM
GIN
8.7
3.0 0.7
2.2 0.4
4.6 1.2
43:.1
6.2 S.1
4.200.0
83
39213
OOM
SAGB
7.0 81.
6,0 21 I.O
3.0 0.0
3/2 DL4
1.3.1
S.4
5.0.10.00
T.0 BJD
7.0 0.3
OOM
MinOut
7:t
6.0
1.1
To
60
9.1
7:0
6.0
5.0+000
S.A
8.--
15.0
70-
0.0
OCN
0.0
13.3=00.
6.1-1.
MLP
0.
15:0=:00
7.
10.0
OCN
3.0:0:..
0.0
80:0:00
15.0=:00
5.0.1...0
7.
10:0
40.0
7.0
6.0.2.0.0
3.0:
80
15.0
7.0
10.0
40.0
7.0
10.01::00
8.0
15.02:00
5.0.1..000
7.0
1:00
Infomap
282.2
698.9
921.9 9:1
5.5.1
223.5
8.4.6
11008 11.4
399.4.9:3..
8.6
4810.0 22.4
24

---

E Performance impact of hidden layers and max. number of communities
Here, we report the performance difference in terms of achieved average AMI score between using (i) 4yn hidden layers and maximum of = vn communities, and (ii) 512 hidden layers and maximum of = [ communities, that is, the "ground-trute values show much better worse the methods perform when using setup (ii) as compared to setup (i). That is, positive value, shown in green, means that setup (ii) gives better result while a negative value, shown in red, means that setup (i) gives better result.
number of communities. The tabulated
We find that, for Neuromap, NOCD, and DiffPool, setup (i) generally works better. In contrast, DMoN, MinCut, and Ortho often perform better with setup (ii), indicating that they require knowing the correct number of communities perform well.
Table 10: Performance difference in terms of achieved average AMI score between (i) 4y hidden layers and maximum of v communities, and (ii) 512 hidden layers and maximum of 8 = Y communities, that is, the "ground-truth" number communities. OOM stands for "out of memory".
Method
Arch.
Cora
CiteSeer
PubMed
PC
Photo
CS
Physics
Cora ML.
Wiki CS
ogh arxiv
Neuromap
LIN
12.00
-6.70
16.30
0.00
0.00
-4.80
4.3.0
-19.10
-30.20
-4.70
MLP
33.90
-2.20
-0.30
-11.20
+11.50
-3.30
+2.30
-9.90
-5.20
-2.0
GCN
-6.80
-3.40
-1.00
-2.20
-3.00
-2.00
+3.70
-9.90
-4.20
-2.10
GIN
-0.30
-7.00
-8.50
-2.7
-7.90
-3.90
-7.70
-12.50
-5.20
-5.80
SAGE
-9.10
-5.40
-0.00
+1.90
41.10
-1.90
-2.0
-12.90
-3.80
-3.70
DMoN
LIN
+14.10
+6.00
+8.40
-2.40
-1.70
+-29.90
+-26.20
+18.30
+-1.30
-3.20
MLP
-0.50
-2.30
+12.30
-29.60
+13.20
+-31.00
+16.80
-2.00
+7.10
+16.00
GCN
-1.40
-2.00
+1.00
+.2.6
+7.20
+13.50
+14.80
-3.90
+1.50
+2.20
GIN
-9.80
-8.00
-6.70
-0.10
-3.00
+3320
+9.70
-7.30
-7.50
+0090
SAGE
-2.10
-0.20
+99000
+13.60
-.90
+2.10
NOCD
LIN -2.20
+0.60
-3.50
++0.70
+.2.00
-15.70
-12.10
+0.30
-1.40
-0.20
MI.P
-13.00
-5.20
-3.70
+2240
-5.40
+-0.10
+6.60
-7.20
-2.80
+19.20
GCN
-8.50
-8.50
-1.90
-2.30
4-120
4-4.70
+4.50
-14.50
-1.00
00.00
GIN
-8.30
-7.20
-1.30
-1.00
-2.000
-3.70
-5,90
-8.80
-9.70
55000
SAGE
DiffPool
LIN
+0.40
+0.10
0.00
0.00
0.00
-220
-1.70
0.00
-240
0OM
MLP
-1.10
-2.60
-8.00
0.00
+0.40
13.90
- 18.77
-4.10
-6.00
OOM
GCN
-1133
-5.50
-7.40
-4.30
6640
OOM
GIN
16.90
13310
14.20
-9.20
27.10
211.00
- 12.80
-19.10
66.20
OOM
13:90
-3.00
-3900
-5.80
MinCut
LIN
+4.50
+-18,80
+3.10
+-1.00
+-11.10
+-1.30
+3.30
+3.40
0.00
MLP
-4.3
-5.00
+14.60
-38.50
+-1.20
+12.60
+14.90
-6.40
+9.30
+13.60
GCN
+5.70
+7.50
-30.40
GIN
-3.60
0.00
++0.40
-25 -5.66
+13.77
+-28.00
-5.60
+15.10
+223.50
+3.90
SAGE
+2210
-2.30
++1.00
+2.10
4-7.10
+-1.200
+15.70
-6.0
+4.80
+4.30
Ortho
+1.20
-0.80
-6.40
+15.90
-10.90
-2.00
ML.P
-0.90
-0.30
-2.10
++2.60
-3.50
-0.50
-2.30
-1.00
-3.70
-0.60
GCN
-0.90
+-2.60
+44.40
+-0.600
49.60
-0.10
4-3.00
+0.30
GIN
-11.50
-8.10
-7.30
433.40
43.60
47.70
+66.0
-11.10
-6.20
+1.40
SAGE
+3.50
-0.50
+6.00
-6.00
-9.70
+8.10
+5.70
-0.40
+2.50
+4.60
Infiomap
0.00
0.00
25

---

Further results on synthetic network with overlapping communities
Here show the detected communities on synthetic network with overlapping communities with a dense linear layer, 2-layer MLP, a 2-layer GIN, and a 2-layer SAGE architecture. We use [V] hidden channels and the maximum number of communities E {2,3].
E1
Linear-layer-basee results
Neuromap
DMoN
NOCD
DiftPool
MinCut
Ortho
True
3
Figure 15:
Linear-layer-basee based results on a synthetic network with overlapping communities where the leftmost network shows the community structure. Nodes are drawn pie charts to visualise their community assignments. The top and bottom rows show results for maximum of s 2 and
3 communities, respectively.
F.2
MLP--aased results
Neuromap
DMoN
NOCD
DifiPool
MinCut
Ortho
True
MLPP-based results on synthetic network with overlapping communities where the leftmost network shows the true community structure. Nodes are drawn pie charts to visualise their community assignments. The top and bottom rows show results for maximum of s = 2 and s 3 communities, respectively.
Figure 16:
26

---

F33
GIN-based results
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
True
2
8 = 3
GIN-based results on synthetic network with overlapping communities where the leftmost network shows the true community structure. Nodes are drawn pie charts to visualise their community assignments. The top and bottom rows show results for maximum 2 and 3 communities, respectively.
Figure 17:
F.4
SAGE-based results
Neuromap
DMoN
NOCD
DiffPool
MinCut
Ortho
True
2
3
Figure 18:
SAGE-based results synthetic network with overlapping communities where the true community structure. Nodes are drawn as pie charts to visualise
leftmost network shows the their community assignments. The top and bottom rows show results for maximum of 2 and 3 communities, respectively.
27

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Abstract and introduction introduce the research gap and summarise the developed method and experimentally achieved results on a high level.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitation of our work in section 4.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: We focus on adapting the well-established map equation framework for community detection with (graph) neural networks and show its utility empirically, however, our work does not include theoretical results or proofs.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [es]]
Justification: Our main contribution is adapting the map equation as differentiable loss function for optimisation with (graph) neural networks. We present the mathematical formulation of our adaptation in section 4. In section 5, we describe our experimental setup, including hyperparameter settings for our experiments.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We made our code available through a public GitHub repository and the synthetic networks through a Zenodo repository. The used real-world networks are publicly available.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We detail our experimental settings, including hyperparameters, in section 5.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the average achieved performance with standard deviations.
8. Experiments Compute Resources
28

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe the utilised computational hardware in section 5.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: We have reviewed the code of ethics and find that we conform with it.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: We consider the task of detecting communities in complex networks. While any algorithm can potentially abused for malicious purposes, we believe that, our case, this would be rather contrived scenario.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [No]
Justification: We find not applicable to provide safeguards in the context of detecting communities in complex networks to understand their organisational structure.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original works of the models we use as baselines as well as the sources of the datasets we use.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work involves neither crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our work involves neither crowdsourcing nor research with human subjects.
29


Reviews:
[{"review_id": "gqXBQwez0X", "reviewer": "Reviewer_5LnL", "summary": "This paper proposes a deep learning approach for graph clustering called NeuroMap, which can be seen as a neural version of InfoMap. The idea is to minimize the a relaxation of the InfoMap objective using gradient descent. The proposed approach can be combined with different neural network architectures (MLP, GNN, etc.), works with directed graphs, and can identify overlapping communities. Results using synthetic (LFR) and real datasets (up to 170K nodes) show that NeuroMap often outperforms the baselines in terms of Adjusted Mutual Information.", "questions": "1. What are the specific challenges in developing a relaxation of the map objective compared with other clustering objectives?\n\n2. Why InfoMap should be chosen as a classical community detection algorithm to be made neural?\n\n3. Why is the combination of relaxation and gradient descent more effective than the classical heuristics applied to optimize the map objective?", "limitations": "I believe that there are limitations beyond the scalability and need of features (see my comments above) but these are indeed important limitations recognized by the authors.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "1. The paper is easy to follow.\n\n2. The experiments are based on multiple datasets (real and synthetic).\n\n3. The proposed method does not require specifying the number of clusters.", "weaknesses": "1. There are multiple papers proposing relaxations of clustering objectives optimized via deep learning.\n\n2. It is not clear why InfoMap is the ideal community detection algorithm to be made neural given the variety of existing solutions and results showing that there isn't an algorithm that is superior across datasets.\n\n3. The paper lacks any theoretical or empirical analysis trying to explain why relaxation with gradient descent is more effective than the combinatorial heuristics used to optimize the Map objective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback and highlighting the strengths of our approach. Below, we are happy to clarify the questions:\n\n1. Developing a relaxation of the map equation is somewhat more straightforward since no explicit regularisation term is required to avoid trivial solution. A more practical challenge lies in choosing what (graph) neural network architecture to use for optimising the map equation (as well as the baseline objective functions). To the best of our knowledge, our work is the first that systematically explores the performance of different (graph) neural network architectures in combination with different objective functions. Precisely determining when and why certain architectures work better than others remains an open research question.\n2. The strength behind the map equation is the minimum description length principle which is used for model selection and to balance between model complexity and fit. As a descriptive method, the map equation does not fit a generative model or considers the deviation from some null model.\n3. Our results show that relaxation and gradient descent are not per-se more effective than the classical search heuristics used in Infomap, however, it can be better in some cases. While Infomap switches the community assignment for a single node per optimisation step, optimisation with gradient descent can gradually change the community assignments of multiple nodes simultaneously. Our experiments show that, depending on the utilised (graph) neural network architecture, the achieved codelength, number of communities, and agreement with ground-truth communities vary. Essentially, using a different (graph) neural network architecture may be interpreted as applying a different search algorithm, each of which has different characteristics, therefore returning partitions with different properties, i.e., higher/lower codelength, number of communities and AMI values.\n\nIn summary, we believe that the three points above also clarify our contribution over the work published by Tsitsulin et al. at NeurIPS 2023: We show that using the information-theoretic objective function MapEquation rather than modularity makes an additional regularisation - whose integration is one of the major challenges addressed in Tsitsulin et al. - obsolete. Moreover, we go beyond this work by showing that different message passing architectures effectively yield different search algorithms, which opens up interesting questions for future work. Furthermore, our empirical evaluation shows that several of the baselines overfit when they are not provided with the correct number of communities. In contrast, based on the map equation, our approach chooses the number of communities automatically, even when the correct number of communities is unknown.", "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": "", "extra_scores": {}}, {"review_id": "2GyHGLGO6a", "reviewer": "Reviewer_4xY5", "summary": "The authors formulate the well-known MAP equation for community detection as an unsupervised objective for graph clustering with GNNs. The implement this \"soft\" neural MAP equation in various GNN architectures, showing reasonable performance on both synthetic and real-world graph clustering tasks.", "questions": "Q1: I'm curious, do you in fact agree that your approach is best compared to DMoN?\n\nQ2: Is my characterization about the novelty fair? Are there other architectural/practical differences that I missed or that you wish to highlight?", "limitations": "Yes, adequate", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "There are many strengths of this paper:\n\n1) Presentation: the paper is quite well-written and the figures are very clear. I did not find any serious (or even minor) confusions in prose, notation, or figure details. The organization of the paper makes sense and helps the reader understand the results.\n\n2) Novelty: in my opinion, the paper is best compared to Tsitsulin et al. 2023 which introduced the modularity-based DMoN pooling method for neural graph clustering. The paper improves upon DMoN in a few key ways:\n * By adopting the InfoMap objective instead of the Modularity objective, DMoN's need for the collapse regularization is removed, which likely greatly helps with convergence and learing a good community model. It also simplifies the model in general.\n * Empirically, using the InfoMap objective in graph clustering seems to achieve or surpass the performance of all competitors (including DMoN), on synthetic LFR graphs, real graphs, and a toy graph with overlapping communities.\n * The authors do a better job than Tsitsulin et al. at noting the independence of the objective and the neural graph encoder architecture. The encoder architectures are explicitly varied in this work on both synthetic and real graphs, and across all methods on which the encoder architecture can vary.\n\n3) Significance: the clear exposition of the method, empirical dominance, and good commentary about the relationships between network science and neural graph clustering make this a solid contribution to the field.", "weaknesses": "The main weakness of this paper is that the proposed modeling approach has limited novelty compared with that from Tsitsulin et al. 2023:\n\n1) Both papers propose to use a neural graph encoder to obtain a soft clustering embedding matrix $\\mathbf{S}$.\n2) Both papers train the encoder by adopting an objective from network science (here, Infomap; previously, Modularity) and pass $\\mathbf{S}$ in place of the hard-clustering (one-hot) community assigment matrix.\n\nThe primary difference between the approaches is that the proposed objective does not need the regularization component introduced in Tsitsulin et al. 2023 to deal with the collapse condition, i.e. all nodes are assigned to one cluster. However, the reason for this is simply the choice of the InfoMap objective -- as the authors explain, this objective has inherent ability to balance cluster size with clustering complexity (a result that has been well-known for >10years).\n\nOverall, the authors combine pre-existing work to achieve a better neural graph clusterer which nonetheless closely resembles existing graph clusterers that have adopted objectives from network science. This weakeness does not necessarily block acceptance, but it should be well-noted that the novelty is limited.\n\nThere are very few other weaknesses -- the paper is quite well-written, and the experiments convincingly show that the InfoMap objective is probably better overall than previous objectives.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment and encouraging words. For the anwers to your questions, we kindly refer to our aggregate response to all reviewers. In this aggregate response, we also clarify the novelty of our work and highlight our contributions over the work of Tsitsulin et al.\n\nWe hope that we could clarify your questions and would be happy to present our work at NeurIPS 2024!", "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": "", "extra_scores": {}}, {"review_id": "RZ71HyjHqb", "reviewer": "Reviewer_sjQQ", "summary": "The paper proposes an information-theoretic centered approach for clustering nodes of a given graph. The main intuition at the core of the manuscript is to rewrite the map equation in a differentiable form and to train a Graph Neural Network (GNN) with the intent of minimizing its value (thus optimizing the clustering of the provided nodes). As GNNs are naturally suited to process features available on the nodes of the provided domain, this allows to incorporate such information in the optimization of the considered equation and hopefully achieve better assignments. Experiments on both synthetic and real datasets show good performance of the proposed method that generally matches or outperforms prior art.", "questions": "None.", "limitations": "Generally yes, the authors for instance discussed the complexity of the model and how this can become quadratic for dense graphs (or when large number of clusters are used), and how discovering why different GNNs lead to different performance remains an open question in the manuscript.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes an interesting approach for inferring clusters of nodes from a given graph. The manuscript is generally well written, and rather easy to follow (although some details could be better explained in the main text of the paper, see weaknesses). The approach is generally efficient (time complexity is linear in the number of edges for sparse graphs), and experiments on a variety of datasets show good performance w.r.t. previously presented approaches (with the proposed method achieving comparable or superior performance to prior art).", "weaknesses": "Overall, I don’t have particular criticisms for the paper. The main items I would like the authors to address are:\n\n1) I believe equation 1 could be better explained in the paper. In particular, $q_m$ and $m_{exit}$ are not defined in the paper, and their meaning is outlined only at a high level. Having a more formal definition of such values would improve the clarity of the manuscript (I would personally also clarify that the entropy function re-normalizes the probabilities in such equation, as I believe $Q$ and $P_m$ do not sum up to 1 in equation 1)\n\n2) While the performance of the proposed solutions are indeed good compared to previous approaches, if we inspect table 2 in the supplemental material, we can see that the results produced by the proposed Neuromap and and NOCD are quite close on CORA, PC, Wiki CS and ogb-arxiv, once we take into account the standard deviation of the models. As a result of this, stating that Neuromap achieves best results on these datasets is potentially misleading. I would suggest the authors to report the result of a statistical significance test to highlight when the proposed model actually achieves (with high chance) superior performance w.r.t. the best baseline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time invested in our work and the positive assessment of our manuscript. \n\nWe agree that the detailed explanation of the symbols $q_m$ and $m_{exit}$ in section 3 can be improved. It is also correct that $Q$ and $P_m$ in Eq. (1) do not sum to 1 and are implicitly normalised when plugged into the entropy function. Upon acceptance of the paper, we will improve the explanations by including formal definitions of all the symbols -- in the interest of space in a new appendix.\n\nTo assess when Neuromap significantly outperforms the best baseline, we have used an independent two-sample t-test and report the findings in the PDF attached to our aggregate response to all reviewers. Upon acceptance of the paper, we will include these results in a new appendix.\n\nThank you for your suggestions, which have helped us to further improve our manuscript!", "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": "", "extra_scores": {}}, {"review_id": "MwV2MjR5VX", "reviewer": "Reviewer_AyCW", "summary": "The paper titled \"The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks\" presents a novel approach for community detection in networked systems by combining the traditional map equation with modern graph neural networks (GNNs). The authors propose Neuromap, a method that adapts the map equation into a differentiable form for optimization through gradient descent, enabling the integration of node features and end-to-end learning. The paper claims competitive performance against state-of-the-art graph clustering baselines on both synthetic and real-world datasets, emphasizing automatic cluster number determination without the need for explicit regularization.", "questions": "The improvement in overfitting being one of the major advantages of the method, is that possible the author can dive a little deeper into the underlying driver (other than only referencing to how MDL addresses the concern of Occam's razor)?", "limitations": "There is limitation regarding complexity/scalability.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel Integration: The paper successfully integrates the traditional map equation with GNNs, offering a new approach for community detection that leverages the strengths of both methodologies.\n\n- Comprehensive Evaluation: Extensive experiments on both synthetic and real-world datasets demonstrate the competitive performance of Neuromap compared to existing methods.", "weaknesses": "- Complexity Concerns: The complexity analysis indicates potential scalability issues for dense networks or when the number of clusters approaches the number of nodes.\n\n- Presentation: for example, it is unclear that what MDL principle is, and how it relates to this work in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our work. \n\nFor the comments on scalability, we kindly refer to our aggregate response.\n\nOn the question about the MDL principle:\n\nThe minimum description length (MDL) principle is an information-theoretic model-selection approach that has long been used to balance between model complexity and fit [1,2]. The general idea behind MDL is, given some data $D$, to select the model $M$ that enables describing the data as efficiently as possible, i.e., using as few bits as possible. Applied to the map equation, the model $M$ corresponds to the network's community structure, and the data $D$ corresponds to the statistics of a random walk at ergodicity. The map equation is essentially a generalisation of the Shannon entropy to a system of systems: it is a weighted sum of entropies, containing one entropy term per sub-system (or: module) as well as an entropy term for the system of systems (entropy over the modules). Two interacting objectives balance between model complexity and fit. First, choosing small modules leads to low module-level entropy but a large number of modules. Second, choosing few modules reduces the index-level entropy but leads to large modules, which have higher module-level entropy. In combination, these two aspects facilitate choosing the module, i.e., modules, that lead to the best compression of the data, i.e., the random walk's statistics at ergodicity.\n\nWe hope that this clarifies this question and would be happy to present our work at NeurIPS 2024!\n\n[1] Rissanen, Jorma. \"Modeling by shortest data description.\" Automatica 14.5 (1978): 465-471.\n[2] Grünwald, Peter D., In Jae Myung, and Mark A. Pitt, eds. Advances in minimum description length: Theory and applications. MIT press, 2005.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their positive assessment of our work. We were glad to see that reviewer 5LnL found our paper "well-written" without "any serious (or even minor) confusion in prose, notation, or figure details" and that our "experiments convincingly show that the InfoMap objective is probably better overall than previous objectives". We were delighted to see that reviewer 5LnL agrees that our work makes substantial contributions compared to work by Tsitsulin et al., which was published at NeurIPS 2023. We were also pleased that reviewer AyCW praised the novelty of integrating the map equation with GNNs, which offers "a new approach for community detection that leverages the strengths of both methodologies." and that he/she appreciated our "comprehensive evaluation".

In this aggregate response, we comment on our motivation to use the map equation and clarify our contribution over prior works using different objective functions:

- Our motivation to choose the map equation for integration with (G)NNs is twofold: First, because the map equation follows the minimum description length principle, it automatically balances model complexity and explanatory power without requiring an explicit regularisation term to prevent trivial solutions. Second, it has been highlighted in several studies that community detection with the map equation provides excellent results across data from different domains [1,2,3].
- We agree with reviewer 4xY5 that our approach is best compared to DMoN. The approaches are similar insofar as both adopt an objective function for community detection from network science and optimise it through gradient descent based on (G)NNs. However, while the DMoN paper only considers GCN for optimisation, we consider five (G)NN architectures (linear layer, MLP, GCN, GIN, SAGE) and systematically evaluate their performance in combination with different objective functions, which is a contribution in itself.
- Our results show that relaxation and gradient descent are not per-se more effective than the classical search heuristics used in Infomap, however, it can be better. While Infomap moves a single node per optimisation step, gradient descent can change all nodes' community assignments a little bit at the same time. Our experiments show that, depending on the utilised (G)NN architecture, the achieved codelength, number of communities, and alignment with the ground-truth communities vary. Essentially, using a different (G)NN architecture may be interpreted as applying a different search algorithm, each of which has different characteristics, therefore returning partitions with different properties, i.e., higher/lower codelength, number of communities and AMI values.
- Indeed, a larger number of links or communities leads to increased computation time. In the case of links, this is because each entry of the flow matrix, i.e. each link, needs to be considered for computing the map equation objective. However, this is not limited to the map equation but also holds for modularity and other community-detection objective functions. In the case of communities, this is because the pooling operation becomes more expensive. In practice, both aspects are likely not an issue because real-world networks are sparse and have much fewer communities than nodes [4].

Our contribution over the work published by Tsitsulin et al. at NeurIPS 2023 lies in using the information-theoretic objective function map equation rather than modularity which makes an additional regularisation - whose integration is one of the major challenges addressed in Tsitsulin et al. - obsolete. Moreover, we go beyond this work by showing that different message passing architectures effectively yield different search algorithms, which opens up interesting questions for future work. Furthermore, our empirical evaluation shows that several of the baselines overfit when they are not provided with the correct number of communities. In contrast, based on the map equation, our approach chooses the number of communities automatically, even when the correct number of communities is unknown.


Following the suggestion of the reviewers, we propose to improve the camera-ready version of our paper as follows:

- We agree that the explanation of symbols $q_m$ and $m_{exit}$ can be improved. It is also correct that $Q$ and $P_m$ in Eq. (1) do not sum to 1 and are implicitly normalised when plugged into the entropy function. Upon acceptance of the paper, we will improve the explanations by including formal definitions of all the symbols in a new appendix.
- To assess when Neuromap significantly outperforms the best baseline, we have used an independent two-sample t-test and report the findings in the attached PDF. Upon acceptance of the paper, we will add these results to the appendix.


[1] R. Aldecoa and I. Marín. 2013. Exploring the limits of community detection strategies in complex networks. Scientific Reports 3 (2013), 2216  
[2] A. Lancichinetti and S. Fortunato. Community detection algorithms: A comparative analysis. Phys. Rev. E, 2009.  
[3] L. Šubelj, N. J. van Eck, and L. Waltman. Clustering Scientific Publications Based on Citation Relations: A Systematic Comparison of Different Methods. PLoS One 11, 2016.  
[4] A. Ghasemian, H. Hosseinmardi, and A. Clauset. Evaluating overfit and underfit in models of network community structure. IEEE Trans. Knowl. Data Eng., 2020.

Meta-review: This paper is a welcome bridge between the less-fashionable field of community detection and graph neural networks. InfoMap is a well-understood method family from the computational social science community, and while the adaptation to an existing framework "just" introduces another loss function, as Reviewer 5LnL pointed out in their review, NeuroMap is a conceptually elegant and interesting adaptation. The experiments support the method's performance. Therefore, I recommend acceptance.

Nitpick: in Section 4, I would suggest the computational complexity to be expressed in terms of the number of edges in the graph – this way, there is no need to separate dense and sparse regimes.
Decision: Accept (poster)