Trading Quality for Efficiency of Graph Partitioning: An Inductive Method across Graphs
Authors: Meng QIN
Chaorui Zhang
Bo Bai
Gong Zhang
Dit-Yan Yeung
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Partitioning
Community Detection
Inductive Graph Embedding

Abstract: Many applications of network systems can be formulated as several NP-hard combinatorial optimization problems regarding graph partitioning (GP), e.g., modularity maximization and NCut minimization. Due to the NP-hardness, to balance the quality and efficiency of GP remains a challenge. Existing methods use machine learning techniques to obtain high-quality solutions but usually have high complexity. Some fast GP methods adopt heuristic strategies to ensure low runtime but suffer from quality degradation. In contrast to conventional transductive GP methods applied to a static graph, we propose an inductive graph partitioning (IGP) framework across multiple evolving graph snapshots to alleviate the NP-hard challenge. IGP first conducts the offline training of a novel dual graph neural network on historical snapshots to capture the structural properties of a system. The trained model is then generalized to newly generated snapshots for fast high-quality online GP without additional optimization, where a better trade-off between quality and efficiency is achieved. IGP is also a generic framework that can capture the permutation invariant partitioning ground-truth of historical snapshots in the offline training and tackle the online GP on graphs with non-fixed number of nodes and clusters. Experiments on a set of benchmarks demonstrate that IGP achieves competitive quality and efficiency to various state-of-the-art baselines.

Under review as a conference paper at ICLR 2022
TRADING QUALITY FOR EFFICIENCY OF GRAPH PAR- TITIONING: AN INDUCTIVE METHOD ACROSS GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Many applications of network systems can be formulated as several NP-hard com- binatorial optimization problems regarding graph partitioning (GP), c.g., modular- ity maximization and NCut minimization. Due the NP-hardness, balance the quality and efficiency of GP remains a challenge. Existing methods use advanced machine learning techniques obtain high- -ualliya solutions but usually have high complexity. Some fast GP methods use heuristic strategies to ensure low runtime but suffer from quality degradation. In contrast to conventional transductive GP methods applied to single graph, we propose an inductive graph partitioning (IGP) framework across multiple associated graphs leviate the NP-hard challenge. IGP first conducts the offline training of dual graph neural network on historical graph snapshots to capture properties of the system. The trained model is then generalized to newly generated graphs for fast high-quality online GP without additional optimization, where a better trade-off between quality and efficiency is achieved. IGP is also a generic framework that can capture the permutation invariant GP ground-truth of historical snapshots the offtine training and tackle the online GP on graphs with non- non-fixed number of nodes and clusters. Experiments on set of benchmarks demonstrate that IGP achieves competitive quality and efficiency over various state-of-the-ar baselines.
system or scenario to al-
INTRODUCTION
For various complex systems, e.g., communication networks, graph is generic model to describe the entities and their relations using a set nodes and edges. Graph partitioning (GP) a classic inference task that aims to partition the nodes of a graph into several groups (i.e., clusters) with dense linkage distinct from other groups Since the extracted clusters are believed to correspond to several real-world substructures of system, e.g., cells in wireless networks (Dai & Bail 2017), many network applications are formulated as GP tasks (Qin et al., 2019: Patil & Kulkarni (021).
Mathematically, GP be described some NP-hard combinatorial optimization problems, e.g., modularity maximization (Newman) (006) and normalized cut (NCut) minimization (Von Luxburg. 2007). Due the NP-hardness, balance the quality and efficiency of GP remains challenge but some real applications have both requirements of high quality and low runtime, e.g., accurate GP on wireless cellular network with several thousand nodes in a few seconds (Dai & Bai 2017).
On the one hand, prior work has demonstrated the ability of machine learning (ML) techniques achieve high GP quality. Typical ML-based methods include non-negative matrix factorization (Wang et al. 2011) and generative probabilistic models (Karrer & Newman 2011). Graph embed- ding emerges as a promising technique for GP in recent studies. These methods first learn low- dimensional node representations via random walk (Perozzi et al.] (014) or deep learning (Wang) al., 2016 Yang et al.) 2016) to capture high-order proximities and nonlinear characteristies of downstream clustering mod-
graph. The GP result is derived by feeding the learned embedding ule (c.g, K Means). However, most ML-based methods have to use iterative optimization algorithms (e.g.. gradient descent) to learn large-scale parameters for each graph with high complexity.
On the other hand, to reduce the overall runtime and satisfy real-time constraints some appli- cations is another major focus. Some fast GP methods apply heuristic strategies to approximate conventional objectives, c.g., greedy modularity maximization (Blondel et al.) 2008) and multi-level coarsening for graph-cut minimization (Dhillon et al. 2007). Several graph embedding approaches

---

Under review as a conference paper at ICLR 2022
also adopt fast approximation to reduce the inference time, e.g., random projection for high-order proximities (Zhang et al.) 2018a). Despite their high efficiency (e.g., low runtime), they may suffer from unexpected quality decline due to the inherent information loss of heuristic approximation.
The aforementioned state-of-the-art (SOTA) GP methods are inherently transductive. which inde- pendently optimize the model each static graph and can only tackle GP on such a unique graph. We try to achieve a better trade-off between quality and efficiency from a new inductive per- spective across multiple associated graphs of system or scenario. An inductive graph partition- ing (IGP) framework is proposed based on the fact that most real-world complex systems generate a set of graphs via common knowledge in terms of several underlying distributions, e.g., power-law distributions. This hypothesis is also adopted in the simulation of various network systems (Wehrle) et al. 2010). The multiple graphs can be (i) associated snapshots evolving over time or (ii) indepen- dent (sub)graphs of a scenario without temporal dependency e.g., ego-nets in social media. IGP first trains a high-quality GP model on historical snapshots in an offline way, which aims to fully capture properties of the system or scenario regardless of time cost. The trained model is then generalized to newly generated graphs for online GP without additional optimization, which significantly reduces the runtime on these new graphs and is believed to have high-quality GP results. For instance, we can conduct the offline training of IGP on existing known ego-nets of a social network and general- ize it to new unseen ego-nets. In real applications, it is usually assumed that we have enough time to prepare a high-quality model using historical known data in an offline way, which is also one-time- effort only. Our focus is to achieve better trade-off between quality and efficiency of online GP on new graphs after deploying the trained model to system with model parameters fixed.
Technically, IGP follows a graph embedding scheme for unsupervised node-level tasks (i.e., GP) across graphs using the inductive nature of graph neural networks (GNN). Although some inductive GNNs have the potential to be generalized new unseen nodes and graphs (Hamilton et al. 2017 Veličković et al. 2018), they still suffer from the following limitations for GP.
In this study, we consider GP on multiple graphs where topology is the only available information source, i.e., without graph attributes. As some systems allow the addition and deletion of entities, we assume that the number of nodes N is non-fixed for multiple graphs. Although existing inductive GNNs can be applied to graphs with non-fixed N, they were originally designed for attributed graphs and rely on fixed dimensionality of node features. Our preliminary experiments indicate that some classic settings of GNN for the case without node features (e.g., using a constant matrix with fixed dimensionality as the feature input) may suffer from poor GP quality. Some methods extract features via dimensionality reduction (e.g., PCA (Nazi et al. 2019h) map the topology (e.g., adjacency matrix) with non-fixed N to a fixed-dimensional feature space, which is still time-consuming.
Moreover, different system snapshots be assigned with different number of clusters K. Some inductive GNN based approaches adopt an end-to-end (E2E) framework to achieve a better approx- imation classic GP objectives (e.g., GAP (Nazi et al., 2019) for NCut minimization and ClusNet (Wilder et al. 2019) for modularity maximization), with partitioning results derived via a fully- connected (FC) output layer. Despite their high quality, they can only tackle the inductive GP across graphs with fixed K, due to fixed dimensionality of the output layer. These E2E methods still need to be trained from scratch for new graphs with non-fixed K, which is cone-consuming
Although prior studies have demonstrated the ability of inductive GNNs to tackle (semi- Jsupervised tasks (e.g.. node classification) on new unseen nodes and graphs (Hamilonn et al.) 2017 Veličković ett al., (2018), few of them consider unsupervised node-level tasks (e.g., GP) across graphs. Our experiments also indicate that some standard settings of inductive GNNs for unsupervised tasks (e.g., using classic unsupervised training loss of graph embedding for GNN (Hamilton et al. 2017)) may still lack robustness for the online GP on newly generated graphs.
In addition to obtaining better trade-off between quality and efficiency over conventional trans- ductive GP methods via a novel inductive framework across graphs, we also make the following contributions to address the aforementioned limitations of inductive GNNs. (i) To tackle the on- line GP with non non-fixed N, we develop an efficient feature extraction module for inductive GNNs via graph coarsening. (ii) In contrast E2E methods, IGP adopts an inductive graph embedding scheme across graphs which can tackle the online GP with non-fixed K. (iii) Note that GP is an unsupervised node-level task, where the cluster labels are permutation invariant, e.g., label assign- ments (41, 12. (2) = (1, 2, 2) and (4, 12, la) = (2, 1, 1) are the same in terms of GP with 4 as the
2

---

Under review as a conference paper at ICLR 2022
cluster label of node U4. IGP can further incorporate such permuttion invariant label information (e.g., GP ground-truth) of historical graphs to the offline training by combining several GP objec- tives (e.g., modularity maximization and NCut minimization) with novel dual GNN structure which ensures strong robustness for the online GP on new graphs.
2 PROBLEM STATEMENTS AND PRELIMINARIES
In this study, we consider GP on a set of graphs S {91, G2..... .Gr from a common system or scenario. Each graph Gr S can be represented G. = (V,, Ex) with Vi {uf,..., UN and & {(uj, uf) of uf E V.} } as the sets of nodes and edges. For each 9.. topology is the only available information source without graph attributes. We use an adjacency matrix A E RN to describe its topology with N, nodes, where (At).; (At)ji
if (ef,of) E & and (At)sj (A.),a otherwise. Since some systems allow addition and deletion of entities, different snapshots in S can have different node sets, i.e., 3G, G. E S s.t. V1 * V.. Since there may be no temporal dependency among {91.-.. GT} in some cases (e.g.. multiple ego-nets in social media), we do not consider the node correspondence among (Vi,-.. VrJ. We follow the hypothesis adopted in the simulation of various network systems (Wehrle et al. 2010 that graphs in S are independently generated via several underlying distributions of common system or scenario.
assume that
Graph Partitioning. Given a graph Gr. GP aims to partition the node set Vj into K₁ subsets (i.e., clusters) C, = {Ci.-.. .K } so that (i) within each cluster the linkage is dense but (ii) between different clusters the linkage is relatively loose. The result C, also satisfies C, nC 0 for Vr o 8. Mathematically, GP can be formulated as several NP-hard combinatorial optimization problems, e.g., NCut minimization (Von Luxburg 2007 and modularity maximization (Newman) 2006).
Given a graph 9e NCut minimization aims to get the GP result C2 that minimizes the NCut metric:
arg ming, NCut(C,) = 1 -.=, [cut(C], CC),o)(())
K.
where C+ = V/= - C₁ is the complementary set of Ct cut C+) = EejEct, eō; (At)is is the cut between C₁2 and C% vol(C)) En.,yee (At)iy is the volume of Cp. The objective (1 be equivalently expressed in the following matrix form:
arg minH, L,H,H s.t. H.H,, H, IK.,
(2)
where L, = IN, Dj 0.5 A,D, diagonal matrix with d; E, (A) IN is an N N-dimensional identity matrix. H, E x is the membership indicator, where (Hr);r = [d] vol(C,) -110. if of C and (H,),-
0.5 is the Laplacian matrix of A D, = diag (di..... ddx,) is
otherwise.
Modularity maximization is another conventional NP-hard objective of GP. Given a graph G, it aims to find partition C, that maximizes the modularity metric:
arg mine, Mod(C,) = 1 E, of,efECt (A,); - d,dz
(3)
2e
where e = E, / is the number of edges. The objective can also be rewritten in matrix form:
argınInH, tr(HH² Q+Hi) s.t. tr, H.) =Ne
where Q E N, is the modularity matrix with (Qt)s = (At)s - (2c). H, E N.K, is the membership indicator, where (H,):r 1 if of E C and (H,) = otherwise.
Inductive Graph Embedding. Given single graph G. conventional transductive graph embedding aims to learn function f: } + {ut E R R1*k] that maps each node vf to k-dimensional vector uf. The key characteristics of G, (e.g., clustering structure) should be preserved in the embedding space, where node pair (of, of) with similar properties (e.g., in the same cluster) should have similar representations (ui, u (e.g., with close distance in the embedding space). The learned representations }u{} are used as the input of several downstream tasks on including GP.
To alleviate the NP-hard challenge of GP, we consider a novel inductive graph embedding scheme, where model parameters of f are shared by all the graphs in S. We divide S into training set
3

---

Under review as a conference paper at ICLR 2022
GP Resulls
Heloxiod
Now Results
(G Jwntt(G))
Original Groph E..
Adjassay Generaioc S/aatrts A.
Reonstrurtion Dty.
(3) Faslare
In Feabire Encoder.
tea. prouun--ruttil
(C,) wint (C)
Clustrrng
2.2 Bod Foad
Frallaee
Emb
Receretro miia Neigholnd.
atd Frat Brve" Fastur
(Eonoage possing occurs in the origfnll topelags
+ Model
Module
Encoder
Reqularicnn) BP
Dual GNN Structure
Dual Flsed)
Stracture
Choier
Supeegraph IIEM Graph Coarsesing
LA & 2.83
x TTaall GNN uy"
Y-Shrre persruters
gaonnd triti G
dlD Chstering Bay. Okj.
Figure 1: IGP across mul-
Snapahotsii,
Histoiical System
Oflline Training
Snapehols
high-quality GP
(b) Quline
NewSeslem
Compontt I Compeent Avn. Label-in Grigh gru
Fazader
Indano
Jun. Labekiind
All. Matris A
Ind. Emb U
Labes
Diserioninater D
FC Classffer
Adr, Loumiing Obj.
occurs each
rassuuge poosing
tiple associated graphs.
Figure 2: A running example of the offline training of our dual GNN structure.
I' S and a test set S r, which represent the sets of historical known and newly generated graphs. We first train f on I in an offline way to fully capture structural properties of historical graphs. Although graph embedding and GP are unsupervised procedures, we assume the permuta- tion invariant GP result C. (i.e., label information) of each historical graph G, E is available in the offline training, which can be used to enhance the offline embedding optimization. In general, the training label information {Cr E I'} can be from the (i) ground-truth of system applications (e.g., cells in wireless cellular network decomposition) or (ii) results of some high-quality (but usually time-consuming! GP baselines. It indicates another application that we can use GP results of some strong baselines to regularize the offline training of IGP. After the training, we directly obtain the embedding {u } from f for each new graph Ge- E I' with model parameters fixed. The online GP on new graph Gr is the downstream task, where we assume the number of clusters Ke is given. The GP result of Gy is derived by applying clustering algorithm (e.g., KMeans) to {u }.
3 METHODOL.OGY
We propose an IGP framework with the overview shown in Fig. [ including the (i) offiine training of a dual GNN structure historical graphs and (ii) online generalization to new graphs via an inductive graph embedding scheme. Fig. D a running example of the offline training in IGP.
Model Architecture. Inspired by the adversarial auto-encoder (AAE) (Makhzani et al., 2015). we introduce a novel dual GNN structure, including a generator G and a discriminator D that are jointly optimized via an adversarial process. To the best of our knowledge, the dual GNN structure is our original design, which is different from SOTA AAE-based graph embedding methods (Pan al., 2018) that regularize the embedding via the adversarial process between a probability distribution. In contrast, our dual GNN structure incorporates the permutation invariant label information of historical graphs {Ge E [] to the learned embedding via (i) a parameter sharing
strategy and (ii) an adversarial process between { and auxiliary label-induced gruphs (G(")) ).
Concretely, in the offine training, we assume the topology and GP result (used as the 'ground-truth') of each historical graph G, are available, which are descrihed by an adjacency matrix A, E R.N. and an indicator matrix R, E N,N,K,, We define (R.) = I if node of is in cluster C by the 'ground-truth' and (Rę): = 0 otherwise. Due to the disjoint constraint of GP, only one entry in each row of R2 is 1 with other entries in the same row set to O. In addition to the original graph Gt, an auxiliary label-induced graph g(9)) with A (g) R.R.T as the adjacency matrix describing its topology, is introduced to encode the structure of "ground-truth based on the following Fact 1.
(Fact 1) For a historical graph G. with K, clusters, its auxiliary label-induced graph g( has K, fully connected components with each component corresponding to one unique cluster of G.- Namely, there is an edge between nodes of and of in g! only when they are in the same cluster, thus encoding the label information of "ground-truth" (see Appendix A for the proof).
In the example of Fig. 2 with 8 nodes {1, .1.......a 8}. {1, 2,3,,3, 4) and (5. 6. 7, 8J w.r.t. the 2 clusters in the GP result (i..., 'ground-truth") of G.
g(o) has fully connected components
The generator G includes a feature encoder and a label-induced encoder, forming a dual GNN structure with shared parameters dG. The feature encoder takes A, and a feature matrix X, as inputs, and derives graph embedding U., i.e, U, = G(A,, dG) The label-induced encoder takes A and X, inputs, and outputs auxiliary embedding U(9) i.e., U(O) G(A( Xzzōa)-
4

---

Under review as a conference paper at ICLR 2022
GNN is originally designed for attributed graphs, where each node of must have feature vector de- scribed by the i-th row of a feature matrix X,. In this study, we consider GP without node attributes. Instead of using conventional settings of GNN for graphs without attributes (e.g., use constant matrix for the input features), we extract additional structural feature X, based on the neighbor sim- ilarity encoded in A,. IGP captures the permutation invariant label information of historical graphs by combining the dual GNN structure with classic GP objectives. We adopt the objectives of (i) modularity maximization and (ii) NCut minimization tings of X,. For modularity maximization in
two examples, corresponding two set- ( the modularity matrix Q₁ encodes the reweighted neighbor similarity based on A,, so we let X Qs. For NCut minimization in (2) the Lapla- cian matrix L, gives the primary characteristics of graph structure, where M, D 0.5 A, U.5 the key component regarding neighbor similarity. Hence, we let X, = M,. Both Q. and M, are the reweighting of A,, where the pair of nodes (vt, v5) with similar neighbor-inducee features ((X.)..: (x)) are more likely to be partitioned into the same cluster. Our experiments further demonstrate that the extraction of X₁ is essential to ensuring the high GP quality of IGP.
However, the feature dimensionality of X, is N₂ (i.e., the number of nodes) which may not be fixed over t. We introduce an efficient feature extraction module via heavy-edge matching (HEM) graph coarsening (Hendrickson & Leland, 1995) to map X, E ge to a matrix Ze E RNNxL with fixed dimensionality L. For No > L. we extract reweighted edges E/-) = (w(et, w))) of)
(X)) (At)ks = }} and apply HEM to E(")) It merges the original graph G. with Nr nodes into a supergraph 9 with L supemoods via a greedy strategy of continuously merging the node pair
with largest weight in E(()) into a supernode, e.g., merging a graph with 8 nodes into 2 supernodes -0.5 if node of is merged into supernode of- and (Cz), = otherwise. We then let Z. = X,C, be the reduced features. Since C₁ is a sparse matrix, one can obtain Z, by setting its j-th column to (Zi)..) = En,egg- (C)))((X)). For N₂ L, we let Z, X 0 x (L.NNj). In contrast to existing methods using HEM to reduce topology complexities (Dhillon et al. 2007). we are the first to extract feature input Z, for inductive GNNs (with non-fixed N,) via HEM. It is more efficient than dimensionality reduction (e.g.. PCA of A,) in SOTA GNNs (Nazi et al. (201)). since HEM is widely used in fast GP methods (Liang al.. 2021). The derived Z, is also more informative than the input features in some classic settings of inductive GNNs (c.g.. let Z, be constant matrix (Xu et al. 2019)).
in Fig. 2 HEM outputs a coarsening matrix C, M where (C,),,
1
Let F and E be the input and output of the I-th layer of feature encoder label-induced encoder in G with F(O) = Z. The 1-th GNN encoder layer is defined as
F tanh(D, A, 00.5 -0.5 (1 0.5 ww!
(5)
where A, = A'. + IN. (A', E (9)) is the adjacency matrix with self-edges; D, diag(d) d.x)) ) is the diagonal degree matrix; w is the trainable parameter matrix shared by the two encoders; (F("), ). is the latent feature vector of node of. In 5). (F(!) )s. is the nonlinear aggregation of the features of {of} Un(ef) in the previous layer, where r((U)) is the neighbor set of vf. It is also known the message passing of GNN, where neighbors of of propagate their features to of for aggregation. By Fact 1, A ensures that message passing of the label-induced encoder only occurs in each connected component w.nt. each cluster in the 'ground-truth (e.g.. the 2 components in Fig. 2 while message passing of the feature encoder occurs in the original topol- ogy of G. The last layers of the feature and label-induced encoders output the graph embedding U, E N x and auxiliary label-induced embedding U!")) E N, xk where U!o) = G(A (9) Xx)) preserves more informative label-induced properties than U, G(A,, X.). We further use the non-linear inner product of U, to reconstruct the neighbor-induced features X,:
tanh (.U?)
(6)
The discriminator D is an auxiliary classifier to distinguish U!!) from U.. while the generator G tries to generate plausible embedding U, to fool D. Such an adversarial process helps G to generate embedding U, close to U(%). We denote D y; D(S,; 8D), where S, E {U,, U(")) and & are
the input and set of model parameters; y: E R N. is a column vector with (ye); as the probability
that (St).: (U(#)) )e rather than (St) = (Ut) - Let p(l-1) and P(D) be the input and output of
5

---

Under review as a conference paper at ICLR 2022
the 1-th layer in D with (()) Sr. The (-th layer of D defined
P (1) Ww! + +bp bb-
where { (W bb-")) are trainable model parameters. partieular, we use sigmoid as the acti- vation function of the last layer instead of ReLU.
D
Model Optimization. As Fig. the offline training of IGP is based on three objectives: (1)
adversarial learning (AL), (ii) feature reconstruction (FR), and (iii) clustering regularization (CR),
The AL objective helps incorporate the permutation invariant label information of historical graphs to the unsupervised embedding learning via an adversarial process between D and G. On the one hand, D tries distinguish _. from Ug. The objective of D w.r.t a graph G3
arg minso (G.) =
log(1 - D(U))) + Σ, log D(U
>.] /Ne.
(8)
On the other hand, G tries to fool D by minimizing the following loss w.r.t. G
(G) - E, log D(U,)) /Ne-
Such an adversarial process directs G to output the embedding U, that is close to U! thus enabling G to capture the permutation invariant label information of historical training graphs.
The FR loss forces G to derive the embedding U, that encodes the key properties of the neighbor- induced features X, w.r.t. G. by minimizing the reconstruction error between X, and X,:
LFR( ||X X
(10)
In addition the AL loss, IGP can also capture the permutation invariant label information via the regularization of several GP objectives, e.g., modularity maximization (4) and NCut minimization (2. We introduce the CR objective for graph G. that minimizes the following loss:
LCR (G.)
-r H H,H,),
(11)
where H, is the membership indicator encoding the 'ground-truth" with the same definitions in
and (2). Since the constraints on H,, e.g., tr tr(H: / H.) = N₂ and H. H, = Ix,, are always satisfied for the given 'ground-truth' we do need to consider the discrete constraints on H2, To the best of our knowledge, we are the first to use the CR objective to incorporate the permutation invariant label information (encoded by H, of historical training data) to the unsupervised embedding learning, whereas H, is the parameter to be optimized or output in existing GP methods (Wilder et al. 2019
Finally, we derive the objective of G w.r.t. Gr by combining 9 (10). and (II:
arg min & (9.) = (..) (Lr + BT.c
(12)
where {a, 3} are hyper- paremetrrssss to balance LFR and LCR.
In the joint offline optimization of D and G, we use the Xavier method to initialize model parameters (ōD. de The Adam optimizer is applied to iteratively update őn and åG based on the gradients of loss (8) and (12). In each epoch, randomly sample a certain number of historical graphs from the training set to update {ō,, 8g). Finally, we save the model parameters {5% 8% that result in the best average GP quality on the validation within a certain number of epochs n.
After offline training, we generalize IGP to new graphs for fast online GP. As in Fig. | for each new graph Gr, derive its embedding U, by passing {A,, ).) forward the feature encoder of G with its parameters åG fixed. As we assume that the number of clusters K₂r is given, we apply KMeans to Up. which outputs the GP result w.r.t. the given Kr. Therefore, the runtime of online GP on Gy includes (i) the feature extraction of Z, (ii) one feedforward propagation through the feature encoder, and (iii) the downstream clustering. Due the space limit, we conclude the offline training and online generalization procedures of IGP in Appendix B
4 EXPERIMENTS
Datasets. We evaluate IGP on synthetic benchmarks (with settings) and 4 real datasets. Statistics of the datasets are depicted in Table where T, N, |8), and K are the number of graphs, nodes,

---

Under review as a conference paper at ICLR 2022
edges, and clusters. The 11 datasets cover the cases with (i) fixed N and K. (ii) fixed N but non-fixed K, as well as (iii) non-fixed N and K. GN-Ner (Girvan & Newman 2002) and LFR- Net (Lancichinetti et al. 2008) are synthetic benchmarks that can simulate properties of real-world network systems. In each benchmark, we generated a set of graphs and their GP ground-truth via several distributions. GN-Net and LFR-Net use Pmn and y to control clustering structures of each graph. We denote the GN-Ner with a setting of Pin as GN- (Pin E {0.5, 0.4, 0.33). The 3 datasets of GN-Net are with fixed N and K. We use L(c, p) (c [f,n], 1 E {0.3, 0.6)) to represent the LFR-Net with a setting of μt, where f and denote cases with fixed and non-fixed N. As Pia decreases and μ increases, the clustering structures become increasingly difficult to identify Taxi (Piorkowski et al. 2200)), Reddit (Yanardag & Vishwanathan 2015), Enron (Rossi & Ahmed ) and AS (Leskovec et al., 2005) are real datasets from vehicle network, an email network, a social network, and an autonomous system. As the 4 real datasets do not provide ground-truth regarding K, to ensure the fairness of comparison, where each graph is with a common K for all the methods to be evaluated, we adopted widely-used strategy that uses the auxiliary Louvain algorithm (Blondel et al. 2008 to estimate K for each graph. Details of the datasets are given in Appendix
Baselines. We compared IGP over 15 baselines with 4 categories. (i) SNMF (Wang et al. 2011 and spectral clustering (SC) (Von Luxburg, (007) are classic transductive GP methods. (ii) VERSE TTitsulin et al., 2018). MILE (Liang al. 2021), and PhUSION (PhN) (Zhu al.. 2021) are graph embedding approaches for high-quality representations, while NPR (Yang et al. 2020). RandNE (Zhang et al.) 2018a), and ProNE (Zhang et al. 2019) are efficient embedding methods with fast approximation. All these embedding methods are transductive. (iil) Metis (Hendrickson & Leland, 1995), hMetis (Selvakkumaran & Karypis 2006), and GraClus (Dhillon 20.7) are last trans- ductive GP baselines with heuristic approximation. (iv) GraSAGE (GSAGE) (Hamilton et al. 2017) and GAT (Veličković et al.] 2018) are SOTA inductive GNNs, while GAP (Nazi et al. 2019) and ClusNer (Wilder et al. 2019)) are E2E methods based on inductive GNNs. Besides the 15 methods,
we also include other strong baselines (e.g.. node2vec) with details given in Appendix C.3
Both variants of IGP were evaluated. For simplicity, we use IGP-M and IGP-C to denote the variants adopting the objectives of modularity maximization and NCut minimization, respectively.
Quantitative Evaluation. In our quantitative evaluation, we consider GP on graphs where K is given. On all the datasets, we adopted quality metrics of modularity and NCut as in B and ( On datasets with ground ground-truth (i.e., GN-Net and LFR-Net), we also used quality metrics of NMI and accuracy (AC) (Cui et al.] 2018) to measure the correspondence between GP results and ground- truth. Usually, larger modularity, NMI and AC, as well as smaller NCut imply better quality. Moreover, the total runtime of a method to derive its final GP result was used as the efficiency metric with lower runtime indicating higher efficiency.
Most conventional baselines (e.g., SC) are transductive, which can only be applied to a static graph, but IGP alleviates the NP-hard challenge of GP in an inductive framework across graphs. To illus- trate such superiority of IGP beyond transductive baselines, for each dataset, we used the first 80% of the graphs as the training set Fr with the remaining 10% and 10% deployed as the validation set I'v and test set l'. In this setting, Fr U UTv and I" represent the sets of historical and newly generated graphs, respectively. We conducted the offline training of IGP on IT and generalized to I' for online GP. In the offline training, we save the model parameters of IGP with the best aver- age quality on I'v, where we use NMI and modularity as the validation quality metric for datasets with and without ground-truth, respectively. Since we focus on the trade-off between quality and efficiency on new graphs, the evaluation was conducted on 1", where we had to apply transductive baselines to each test graph in I' from scratch due to their transductive nature.
For inductive GNN baselines (i.e., GraSAGE and GAT), we use the same training and evaluation settings with IGP, i.c., offline training on PT and online generalization to I'. Since we consider GP on graphs without attributes, we use a constant matrix 1,, x (with fixed feature dimensionality L.). where each entry is set to as the input features of these GNNs, which is a widely-used setting of inductive GNNs for the case without attributes (Xu et al. 2019). In the offline training of inductive GNN baselines, we adopted the widely-used unsupervised loss of GraSAGE (Hamilton et al. 2017) to train them on Fr, since most existing inductive GNNs (even with a supervised loss like cross- entropy) cannot directly integrate the permutation invariant label information from Tr.
7

---

Under review as a conference paper at ICLR 2022
Table 2: Ablation study on ((n,.6).
Table I: Statistics of the datasets.
T
N
K
NMI(*1)
AC(
Mod(%1)
Nent ()
GN-0.5
2,000
5,000
48,065-49.314
250
IGP-M
56.48
53,42
34,22
82.76
GN-0.4
2,000
5,000
48,335 49,698
250
w/o AL
52.13
49,30
33.35
84.05
GN-0.3
2,000
5,000
48,488-49.99
250
w/o
11.19
6.28
10.08
1.0c3
1(F0.3)
2,000
5,000
22.539.25.
57. 104
w/o CR
49,97
46,70
32.70
86.08
11
2,000
5,000
22,585-25,639
58 107
w/o
16.39
6.14
1.27
3.01c4
Lln.0.3)
2,000
5,999
22.999-29,677
59-117
w/o GNN
1.14
3.92
0.01
1.08c4
L6n.0.6)
2,000
5,000-6,000
22.680-29,931
61-118
IGP-C
$2.71
47.47
31.95
92,40
Toxi
3,000
1,279
48,354.40.771
7-12
w/o AL
26.15
26.70
113,10
Reddit
1,870
501 3,648
4,780
14 121
w/o FR
15.46
5.46
0.45
2,08e4
w/o
35.16
26.78
111.62
Enron
410
502-3,261
554-5,097
10-31
103-6,474
487-26,467
7-39
w/o Z.
13.88
5.57
0.28
2.88e4
w/o GNN 8.45
4.78
0.32
5.12e4
For the E2E GNN methods (i.e., GAP and ClusNer), we could only conduct the offline training and fast online generalization datasets with fixed K (i.e., on GN-Ner), but we had to train them from scratch on the test set of other datasets with non-fixed K, due to the fixed dimensionality of their E2E output layers. As recommended in (Nazi et al. 2019) and (Wilder et al. 2019), we used PCA and node2vec to map the adjacency matrices {Ac} to a feature space with fixed dimensionality for the input features of GAP and ClusNet. Moreover, we used their own unsupervised training loss, which approximates the objectives of NCut minimization and modularity maximization, respectively.
For all the embedding- -aased methods (including the transductive embedding baselines, inductive GNNs, and IGP), we used K MMeans as the downstream clustering module. We ran K'Means 10 times to avoid its limitation of getting locally optimal solutions, which is included in the total runtime. To ensure the fairness of comparison, the embedding dimensionality of all the embedding-based methods was set to be the same on each dataset. For other E2E baselines (e.g., Metis, GAP, and ClusNer). we directly derived the GP results from their outputs. Since Taxi, Reddit, Enron, and AS do not provide the GP ground -runnd (in terms of the membership C₂) on each historical training snapshot of these datasets, we used the GP result of the baseline with best average modularity on Tv to derive the membership indicator H; for IGP, which is the second source of historical label information defined in Section 2 Note that we do not need to derive H, in the evaluation phase when generalizing the trained model to test set 1"
We tuned parameters of all the methods on I'v of each dataset to report best quality metries. Both the mean and standard deviation of all the quality and efficiency metrics on I' of each dataset were recorded. Evaluation results in terms of average NMI, modularity, and runtime are visualized in Fig. 3 Due to the space limit, we give (i) the visualization results w.r.t. AC and NCut, (ii) mean and standard deviation of all the metrics, and (iii) parameter settings in Appendix C.5 most cases of Fig. 3 IGP-M (red circle) and IGP-C (blue circle) are in the top group with best quality, even though we did not train them on test set I", where other transductive baselines were fully trained. Surprisingly, IGP even has the best second-best quality metrics in some cases. Moreover, the runtime of IGP-M and IGP-C is also competitive to some fast GP baselines (e.g.. Metis). Although the runtime of inductive GNN baselines (with fast online generalization) is slightly faster than IGP, they still suffer from poor quality, which implies that the feature extraction module and hybrid training loss of IGP are essential to ensure its high quality. From the view of alleviating the hP-hard challenge of online GP on newly generated graphs, IGP achieves a better trade-off between quality and efficiency. According to the visualization results in Fig. 3 we introduce the trade-off' score in Appendix C.5 which can quantitatively evaluate the trade-off between quality and efficiency by computing the area covered by an induced rectangle of each data point in the visualized 2D space.
Ablation Study. For IGP-M and IGP-C, we also validated the effectiveness of (i) AL loss, (ii) FR loss. (iii CR loss, (iv) feature input Ze, and (v) GNN by respectively excluding the corresponding components from the original model. In case (iv), we used constant matrix 1 N, r. with all entries set to to replace Z, while we use an FC network that only takes Z, as input to replace GNNs in G with same layer configurations. Example results on L(n,. .6) in terms of NMI. AC, modularity, and NCut are shown in Table According to Table 2 the FR loss, Z., and GNNs are key components to ensure the high quality of IGP, since there is significant quality decline for case (ii), (iv), and (v). The AL and CR losses further enhance the quality by incorporating permutation invariant label information of historical graphs. Other detailed ablation studies are given in Appendix C.5
Extended Applications. Besides the aforementioned experiments, we consider two extended appli- cations. First, when the number of clusters K of new graph is not given, IGP also has the potential
8

---

Under review as a conference paper at ICLR 2022
3.95
SNME MILE-
PLN
IGP-PF IGP-C
PraNE
SYMP
SC
0.56
TOF
APrasE
MILE SYMP
KRMO IGP-
DGraClun
SPONE
SED
SNMY
6J nCraCho
DGraClt
0.44
MMec So MRP
0.56
MaMel
2345
GSAGE
<0.5
3,55
Mrlg
GAT
GRAGE
RAMENE
VERSE
20.
0.20
GAT GSAGE EAP
oRaneNE
ClyNN VERSE
2-0
0.52
GRAGE GAT
GAP
Cle VERSE
46
200
0.205
SRUGAP ClasNe VERSE
Time (9c5
(a) GN-0.3
(b) GN-0.4
NC
EreAt AEoiNE
SC
JaP-
GAP+
3.98
Gracia
Co.6
PRY/
GAP
0.65 Mor-
ChoNer
PAN-
3.91
RandNE
Madis Ageeets
0.9
BGraChn AhMeis
VERSE ClanNer
YERSE-
2.00
Medl
AbMutt
SNMPS
<3.95
3.95
GAT)
842
GAT
YERSE
RIGNNE
SNMP4
GraClis
Meila
80
20
X00
20
40
20
Time
Time (se5,
Time (565,
13
(C) GN-0.5
L(A0.3)
CraCles
1GFMM
& MMdds
SNMPS VERSY
CheNNee
Mediltato
05
GraChi
PrENE
VERSE
PINa
SIGNT
TwNNE
MILE
ClanNen VIESS
GAPS
0
JGP-M
IGP-
PreNE
SALE
Psc
ChaNNer
VERSE-
Meth
0.9
AlMels
PSC
PSC
ARMris
0.5
NRP
1.25
JDEAGE MILLK
Metk
BandNE
SNME
0.55
GRAGE
SNMF4
MILE
10
24
20 Time feee, L)
240
25
2-0
20 Time (sec
Time (scc
Time 1se
LT70666
(f) (1n0.3)
STANE TUP-
ChaNNe
GAG-MM AkMuda GraUSi
Clackett
5:74
JURM
VERSE,
GGP-M syMp
0.
GraCia
SNMFS VERSE
(1)
GAM
Minalar (1)
NMJ tts
94
MMris
AaMeiic
RandNE
PRN
0.25
6:72
GAP+
GRAGE
GSAGE
NWP RandVE
PSC
RandNI:
GAT
MILE
BBC
Melh SAGGE
Mells pac
Clund
CAT MILK
Matt
260
Time Iee.
Time Iseo
fec
(ezc,
3
L(n.0.6)
(h) Taxi
(i) Reddit
CAP
SILE
VERSE Chuod
DSGT-C
Figure 3: Visualization results on the 11 datasets
SNMF4 VERSS"
psc
Misia
Medtttarry
in terms of quality metrics of NMI (f) and mod-
&ProNE
ularity (1) (y-axis), well efficiency metric of runtime (L) (œ-axis). The number records, evaluation results of AC and NCut, well analysis of the trade-off between quality and ef- ficiency are given in Appendix C.5
pGraCles
6.55 Mads
8:45
RoseNE [AA
AR
GAAGE
<0,5
RAT
Time
Time fees
(i) AS
Enron
to estimate K, where we apply an auxiliary model selection method (c.g., XMeans) to the derived embedding U.. Second, in contrast the hypothesis that all the given snapshots are from a common system or scenario following several underlying distributions, it is promising that one conducts the offline training on historical data of one scenario but generalizes the model to other scenarios for fast online GP. Especially, we consider the application where we train IGP on synthetic graphs but generalize to real datasets. The two extended applications are elaborated in Appendix D
CONCLUSION
In this paper. we proposed novel IGP framework to alleviate the Na-hard challenge of GP, ob- taining a better trade-off between quality and efficiency. In IGP, we first conduct offline training of a novel dual GNN structure on historical known graphs and generalize the model to newly gen- erated graphs for fast high-quality online GP. IGP is generic framework that can incorporate the permutation invariant label information of GP to the offline training by combining unsupervised GP objectives (e.g., modularity maximization and NCut minimization) with the dual GNN struc- ture. Since we introduced an inductive graph embedding scheme and an efficient feature extraction module, IGP can also tackle online GP graphs with non-fixed number of nodes and clusters. In Appendix|E] we give discussions of possible future work, e.g., further reducing the runtime, scaling IGP up to graphs with large number of nodes, and transferring IGP across scenarios.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. JMLR, 18(1):64466653) 65311, 2017.
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. JSTAT, 2008(10):P10088, 2008.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In Proc. of ICLR, pp. 1801.10247, 2018.
Petr Chunaev, Timofey Gradov, and Klavdiya Bochenina. Community detection in node-attributed social networks: How structure-attriuut correlation affects clustering quality. Procedia Com- puter Science, 178:355-364, 2020.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE TKDE, 31(5)8833-852, 2018.
Lin Dai and Bo Bai. Optimal decomposition for large-scale infrastructure--based wireless networks. IEEE TWC. 16(8):995-4996, 2017.
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Weighted graph cuts without eigenvectors multilevel approach. IEEE TPAMI, 29(1 19119499444195 2007.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. PNAS, 99(12):72117786, 2002.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proc. of ACM SIGKDD, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proc. of NIPS, pp. 1024-1034, 2017.
Bruce Hendrickson and Robert W Leland. A multi-level algorithm for partitioning graphs. Proceed- ings Supercomputing. 95(28):1-14, 1995.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Proc. of ICLR, pp. 1905.12265. 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Proc. of NIPS, pp. 4563-4572, 2018.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83(1):016107, 2011.
Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing com- munity detection algorithms. Physical Review E, 78(4):0461 10, 2008
Jure Leskovee, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrink- ing diameters and possible explanations. In Proc. of ACM SIGKDD, pp. 177-187, 2005.
Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. Mile: multi-level framework for scalable graph embedding. In Proc. of AAAI, pp- 361-372, 2021.
Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey. Adversarial autoencoders. arXiv: /5/p:////.00444 2015.
Azade Nazi, Will Hang. Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. 1xXiv:193.00061 2019.
Mark EJ Newman. Modularity and community structure in networks. PNAS, 103(23):8577-8888, 2006.
S Pan, R Hu, G Long, J Jiang, L Yao, and C Zhang. Adversarially regularized graph autoencoder for graph embedding. In Proc. of IJCAI, 2018.
10

---

Under review as a conference paper at ICLR 2022
Siddheshwar V Patil and Dinesh B Kulkarni. Graph partitioning using heuristic kernighan-Iie -in algo- rithm for parallel computing. Next Generation Information Processing System, pp. 281-288. Springer, 2021.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proc. of ACM SIGKDD, pp. 701-710, 2014.
Michal Piorkowski, Natasa Sarafijanovic, and Matthias Grossglauser. parsimonious model of mobile partitioned networks with clustering. In Proc. of IEEE COMSNETS, pp. 1-10. IEEE, 2009.
Meng Qin and Kai Lei. Dual-channel hybrid community detection in attributed networks. Informa- tion Sciences, 551:146-167, 2021.
Meng Qin, Di Jin, Kai Lei, Bogdan Gabrys, and Katarzyna Musial-Gabrys. Adaptive community detection incorporating topology and content social networks. Knowledge-bused systems, 161: 342-356, 2018.
Meng Qin, Kai Lei, Bo Bai, and Gong Zhang. Towards profiling view for unsupervised traffic classification by exploring the statistic features and link patterns. In Proc. of ACM SIGCOMM Workshop Network Meets Al & ML, pp. 50-56, 2019.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In Proc. of ACM SIGKDD, pp. 1150-1160, 2020.
Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analytics and visualization. Proc. of AAAI, pp. 4292-4293, 2015.
Navaratnasothic Selvakkumaran and George Karypis. Multiobjective hypergraph--arttiionnng al- gorithms for cut and maximum subdomain-dege degree minimization. IEEE TCAD, 2543):504-517, 2006.
Xing Su, Jianjun Cheng, Haijuan Yang, Mingwei Leng, Wenbo Zhang, and Xiaoyun Chen. Inensa: Detecting communities incrementally from time-evolving networks based on node similarity. In- lernational Journal of Modern Physics C, 31 2020.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proc. of WWW, pp. 1067-1077, 2015.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proc. of WWW, pp. 539-548, 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proc. of ICLR, pp. 1710. 2018.
Ulrike Von Luxburg. tutorial on spectral clustering. 2007.
Statistics & Computing, 17(4):395-416.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proc. of ACM SIGKDD, pp. 1234-1234, 2016.
Fei Wang, Tao Li, Xin Wang, Shenghuo Zhu, and Chris Ding. Community discovery using nonneg- ative matrix factorization. DMKD, 2933)2993-521, 101
Klaus Wehrle, Mesut Günes, and James Gross. Modeling and tools for network simulation. Springer Science & Business Media, 2010.
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization on graphs. In Proc. of NIPS, pp. 4672-4683, 2019.
Keyulu Xu, Weihua Hu. Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proc. of ICLR, pp. 1810.00826, 2019.

---

Under review as a conference paper at ICLR 2022
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proc. ACM SIGKDD, pp. 1365- 1374, 2015.
Liang Yang, Xiaochun Cao, Dongxiao He, Chuan Wang, Xiao Wang, and Weixiong Zhang. Mod- ularity based community detection with deep learning. In Proc. of IJCAI, volume 16, pp. 2252- 2258, 2016.
Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, and Sourav S. Bhowmick. Homogeneous network embedding for massive graphs via reweighted personalized pagerank. VLDB Endow, 13 (5):670-633, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In Proc. of ICLR, pp. 1907 007.00493, 2020.
Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. Prone: Fast and scalable network representation learning. In Pruc. of ICCAI, volume 19, pp. 4278-4284, 2019.
Ziwei Zhang, Peng Cui, Haoyang Li, Xiao Wang, and Wenwu Zhu. Billion-scale network embed- ding with iterative random projection. In Proc. of ICDM, pp. 787-796. IEEE, 2018a.
Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu. Timers: Error-bounded svd restart dynamic networks. In Proc. of AAAI, pp.
2018b.
Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node proximity is all you need: Unified structural and positional node and graph embedding. In Proc. of SDM, pp. 163-171. SIAM, 2021.
A PROOF OF FACT
By the disjoint constraint of GP, i.e., C for Vr * s, each node can only belong to one unique cluster. For the membership indicator matrix R,, only one entry in each row of R, must be with the rest entries the same row set O. For the auxiliary adjacency matrix A R.R.T. consider each entry ())))) Σ [RR),, (Re) with respect to the pair of nodes (ui, uf)
K,
If nodes (of, ef) are in the same cluster C, i.e., of, of C₁ we have Ris Rÿs 1. We can further derive (A(3)), (Rt) (Re) = 1. It indicates that there is edge between (u uf) with weight 1, when they are in the same cluster.
If nodes (uf, 2f) not in the same cluster, i..., of E C and of C. (r # s), we have R., and Rys 1. but (A) Dig O. Namely, there is no edge between nodes (uf uz) when they are in different clusters.
(9)
In summary, there is an edge between (uf, uz) in the auxiliary label-induced graph G( only if they are partitioned into the same cluster according to the given partitioning result C, = ...,.... Ck,) Especially, each node of C²₁. (i) must have edges connected to all
(used as the 'ground-truth) the other nodes in the same cluster C and (ii) do not have edges connected to nodes in different clusters C (r * s), thus forming a fully connected component with respect to cluster C. Hence, for a graph G. with K2 clusters, its corresponding auxiliary label-induced graph g( has K, fully connected components, with each component corresponding to one unique cluster of G..
B DETAILED ALGORITHM OF IGP
In contrast to conventional transductive GP methods applied to a single static graph, IGP is an inductive framework that explores the structure properties across set of graphs S (G1, Gr). In IGP, we first train novel dual GNN structure on historical system snapshots in an offline way (regardless of the training time cost). We then generalize the trained model to newly generated snapshots of the same system for fast high-quality online GP without additional optimization, where a better trade-off between quality and efficiency can be achieved. For simplicity, we divide S into training set TT, validation set Iv, and test set I', where Pr U Tv and I' represent the set of historical and newly generated system snapshots, respectively. Namely, snapshots in PT U Tv should occur before those in l'.
12

---

Under review as a conference paper at ICLR 2022
Algorithm 1: HEM Graph Coarsening
Input: input graph Ge; neighbor-induced features X number of nodes N₁; reduced dimensionality L Output: coarsening matrix C;
extract the node set " and reweighted edges = from Ge and X;
2 (()) + =f") //Initialize the edge set of the 1st coarsening level
k +- /Initialize the level index
N2 | //Initialize the number of (super)nodes
while No >
v((++1) < //Iittiaiize the node set of next level E e(k+1) < 0 //Initialize the edge set of next level sort e based on weights in descending order arrange the sorted result queue ((((1)
while ((((+)) + do
10
pop (ufth ((tt) from ((E()))
uf vill) and ula)
(((k) then
12
delete of and (1)) from v:a))
13
merge (k) and o/4) into supernode of (k+1)
add oi (1+1)) to v(k+1)
15
adjust e(k) and Et e(h+1) w.r.t D!() and De ((++))
16
N Ny- //Update the number of supemodes
18
then if N: ((==1) < y u
19
return C₁ based on the merging membership of Va (*++))
((++1) (((+1) (())
el clk+1) - c(k+!) u
22
23
k k + //Update the level index
return C₁ based on the merging membership of (((A)
24
B. FEATURE EXTRACTION
For set of graph snapshots S (91....9r} with non-fixed node set (V...., Vr (i.e., with non-fixed number nodes N₂), we introduce an efficient feature extraction strategy HEM graph coarsening, which maps the neighbor-induced feature X, E R.N. (X, = Q or X, M,) to a reduced feature matrix Z, E N. with fixed dimensionality L. Algorithm | and Algorithm summarize the procedures of HEM graph coarsening and the feature extraction module.
For each graph G. S, L < Nr. Algorithm [ first merges G. into a supergraph 9; (with (Xt)s, (At)is = 1} and outputs a coarsening matrix C, E N.xt that describes the merging membership. Concretely, (C.); |05 -0.5 if node of is merged into supernode v/ (i.e., of E of")) and (Ct)k = O. other- wise. Based on C, given by Algorithm[] Algorithm
supernodes) based on reweighted edges e(w) {w(of, w/), e/)
derives reduced feature matrix Z, Z, = X,C, By the sparsity of C,, we can set its j-th column to (Ze)..j = Enery (C,),, In contrast, when T > Nr. Algorithm 2 padding strategy.
directly derives Z. = X, ON.x(L-No) via a simple
B.2 OFFLINE TRAINING ON HISTORICAL SYSTEM SNAPSHOTS
In the offline training of IGP, assume that the partitioning result C, ......., ,kk, (i.e.. "ground-truth ) of each historical graph G. E Pr U TV is available, which is permutation invariant in terms of cluster labels. For simplicity, correlate each historical graph G, e Pr Ty with 2-tuple (A,, C.). The offline training procedure of IGP summarized Algorithm 3 where L is fixed dimensionality for the reduced features Z,; {a, B} are hyper-parameters of the training loss
13

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Feature Extraction of IGP
Input: input graph Gi; neighbor-induced features X number of nodes N2; reduced dimensionality L Output: reduced features L 2 N₁ then
let Zu = -[x,, [Xe,ONxxte Sx,0xxxc-Nool //Pad Z, with zeros
else if I. N₂ then
derive the coarsening matrix Ct 3p via Algorithm derive the merging membership V; based on C₁
for each supernode 0z Vi do
(Zz)..s t- ON, ///iiiiialize the j-th column of Zu for each node U; E 0 do (Zi).s + (z)). + (X.)
Algorithm 3: Offline Training of IGP (on Historical System Snapshots)
Input:
training set TT; validation set I'v; reduced feature dimensionality L; hyper- syper-parameters of training loss {ar, 33; number of historical snapshots sampled in each epoch repetitions to update model parameters (w.rt. each sampled snapshot in epoch) m:; learning rates [T), JJ maximum number of epochs
Output: best model parameters {62, 8b}
initialize the variable q" that saves the best average quality metric
initialize model parameters {&G, dD} via the Xavier algorithm
for epoch from to do
for sample_count from p do randomly sample a graph G. E PT get the associated 2-tuple (A., C.) of derive the neighbor-induced features X, based on adjacency matrix A. derive the reduced features Z, from [,) via Algorithm 2 derive the membership indicator H, based on the "ground-truth" C, for update_cov _count from to m do derive the loss function LD via equation update dD via &p + Optimizer(1p) (TI, åp. derive the loss function LG via equation
10
LL with &g fixed
12
Bāp
13
12
14
update &G via 6c <- Optimizer(Mc:: dG. BMG
ULC with 6n fixed
15
@ - 0 //Intiiaiize the variable that saves the average quality metric of current epoch for each G. E I'v do
17
get associated 2-tuple (Av, Cv) of G..
18
derive the neighbor-induced features X₂ hased on adjacency matrix A
derive the reduced features Z, from {Av, ) via Algorithm 2 derive the graph embedding Up from the feature encoder in G
19
21
apply K'Means to U, to derive partitioning result Če evaluate partitioning quality based on Če (and Cp)
22
② + + //Update ạ
24
g - //Compute the average quality metric
25
if i better than q" then
26
[6b, } &- {ōp, ) //Update the best model parameters
27
7" //Update the best average partitioning quality
Lo: is the number of historical snapshots sampled in each epoch; {πId Toa are learning rates of the optimizers updating {ōp, 8G); n is the maximum number of epochs. For a selected training sample in each epoch, repeatedly updating model parameters (m 1) times sometimes lead to better partitioning quality (on the validation and test set). Algorithm 3 finally saves the model parameters (5,, ) with the best quality metric the validation set Tv.
14

---

Under review as a conference paper at ICLR 2022
Algorithm 4: Online Generalization of IGP (to Newly Generated System Snapshots)
Input: newly generated graph Ge E ,', adjacency matrix Ar, reduced feature dimensionality I., number of clusters Ky (w.rt. (v)
Output: partitioning result C₁' w.r.t. G:r
derive the neighbor-induced feature X, based adjacency matrix A.
derive the reduced features Z from X.r) via Algorithm? 2
derive the graph embedding U.r from the feature encoder
apply Mcaans to Ur to derive the partitioning result Cy with K2 clusters
B.3 ONLINE GENERALIZATION TO NEWLY GENERATED SYSTEM SNAPSHOTTS
In the online generalization of IGP, we fix the learned model parameters {6 82. and directly derive graph embedding U.. with respect to each newly generated graph Gr E I" from feature encoder of G. Since assume that the number of clusters Kr of each graph Gr E I' is given in the online GP, we apply KMeans to Up to derive the partitioning result C² with Ky clusters. In this case, the total runtime of online GP on each newly generated graph Gr I' includes (i) the efficient feature extraction of Zy, (ii) one feedforward propagation of {Ar, Zr} through feature encoder, and (iii) the downstream (KMMaan) clustering. In conclusion, summarize the online generalization procedure of IGP in Algorithm
B.4 COMPLEXITY ANALYSIS
For a given graph Gr, we use the efficient matrix multiplication to derive the neighbor-induced features Q and M,. Concretely, we set Q2 = A, de d,/(2u) and M. = D-122 2-1//A,D-1// where d, = [d', .dv,] and D, = diag(d","" ... ,xx,) are the degree vector and degree diagonal matrix of G. Although the complexities of computing Q2 and M, are both at most O(N?), ), they can be easily paralleled via GPUs, which significantly reduces the runtime. Moreover, the complexity of the HEM graph coarsening (i.e., Algorithm 1h is no more than O(N,)& log E l). with [&, denoting the number of edges G. and E & Nr. The complexity to derive Z, via X, and C, (i.e., Al Algorithm 2 is no more than ONN, ). where n² is the maximum number of nodes merged into a supernode; is the number of supernodes (which is also the reduced feature dimensionality of Z.). Hence, the complexity to derive the reduced feature matrix Z, based on X, is more than O(N]EE log [& + L,")).
Let ((-1) be the feature dimensionality of the I-th GNN layer of the feature encoder or auxiliary label-inducer encoder in G, where we have I ()) L. We used the efficient sparse-dense matrix multiplication to implement the graph convolutional operation described in equation (5). where the sparsity of A, is considered. The complexity one feedforward propagation through the feature encoder is no more than ( (()) () +...) = ((E,)LL'), where L' L()) and (1)) (1-1), Hence, the overall time complexity of one feedforward propagation through the feature encoder is linear in the number of edges of the input graph G.
Let be the dimensionality of graph embedding. Usually, we have i < No. For a graph with K; clusters, the complexity of K MeMaans is no more than O(NKKkI)) for iterations. In particular, the runtime of the downstream clustering (i.e., K Means algorithm) can also be significantly reduced parallel implementations.
C EXPERIMENT DETAILS
C.I EVALUATION METRICS
In experiments, used the (unsupervised) metrics of modularity and NCut to evaluate the partitioning quality of each method on all the datasets. The formal definitions of modularity and NCut are given in equation and equation (T) (see Section 2).
For datasets with partitioning ground-truth (i.c., GN-Ner and LFR-Ner), we also used the metrics of normalized mutual information (NMT) and accuracy (AC) (Cui et al. 2018), which can measure the
15

---

Under review as a conference paper at ICLR 2022
Table 3: Detailed statistics of the datasets.
T
Min N
Max N
Avg N
Min [2]
Max [2]
Avg [2]
Min K
Max K
Avg K
GN-0.5
48,065
49,114
48,752
GN-0.4
2,000
5,000
5,000
5,000
48,335
49,698
48,999
250
250
250
GN-0.3
48,488
49,981
49,246
3g.0.3)
22,539
25,707
23,925
2,000
5,000
5,000
5,000
64
22,585
25,639
23,927
58
107
79
L1.0.3)
5,000
5,999
5,503
22,999
29,670
26.311
59
117
87
2,000
6)
5,000
6,000
5,493
22,680
29,931
26,289
61
118
87
Taxt
3,000
1,279
1,279
1,279
38,554
40,171
39,291
7
12
9
Reddit
1,870
501
3,648
946
525
4,780
1,133
14
121
32
410
502
3.261
1,048
3,097
1,376
AS
733
103
6,474
4,183
487
26,467
16,324
39
29
correspondence between the partitioning result (given by the method to be evaluated) and ground- truth (given by the dataset). In general, better correspondence indicates better partitioning quality. For a graph Ge with K, clusters, we use H₃ = { H and C2 = [Cf Ck2 } to denote the ground-truth and partitioning result, where H; C V; and C C V; represent node member sets of the r-th cluster. Given H2 and Ct, the definition of NMI is as follow:
-2EH,EH, Ecyec, Tew
log n. XX,
NMI(H,, Ci) = EHŞEH, T- x log Te +cJeEc The log R.
n
(13)
where n, | is the number of nodes in the r-th cluster of ground-truth; nt = |C_| is the number of nodes in the s-th cluster of partitioning result; nr.s = | n CJI is the number of nodes that are simultancously partitioned into the r-th cluster of ground-truth and the s-th cluster of partitioning result. Let L; (...... (x) and ground-truth with respect to node sequence (ui.... ,oy,). where l and rf are cluster labels of
and RG (ri.... v.).) be label sequences of the partitioning result
node v/- The definition of AC is as follow:
AC(R,, L.) E.e, map(())
(14)
No
where map(-) is the Kuhn-Munkres mapping function that gives the best membership map from Le to Re; 8(a, b) is the Kronecker delta function with o(a, 6) = when a = and 8(a, 6) = otherwise. Usually, larger modularity, NMI, and AC, well as smaller NCut indicate better partitioning quality of a given GP method.
C.2 DATASET DETAILS
The detailed statistics of the 11 datasets (with 7 synthetic benchmarks and 4 real datasets) used in experiments are depicted in Table where T, N, [E), and K are the number of snapshots, nodes, edges, and clusters, respectively.
GN-Net (Girvan & Newman 2002) is widely-used synthetic benchmark for GP, in which the graph topology and GP ground-truth of each graph can be generated via the stochastic block model (Abbe] 2017). We fixed N 5, 000 and evenly partitioned the nodes into K 250 clusters. For two uniformly selected nodes v; and uj. if they re assigned in the same cluster (i.e., 0i Uy E CD), the probability to generate an edge (vi, vz) is Pin- Otherwise (i.e., U, E C, and vy E C. (r * s)), the probability to generate an edge (V,, U2) is (1 -1-28 Pim-m///KK Pan E {0.5, 0.4, 0.33 to generate 3 datasets. For each dataset, we independently generated 2, 000 graphs. In each graph, we also randomly shuffled the node indices to ensure that there is no index correspondence hetween any two graphs in the dataset (as we defined in Section D}. Especially, with the decrease of Pin. the clustering structures become increasingly difficult identify. For simplicity, we denote the GN-Net with a specific setting of pin as GN-Pin (c.g.. GN-0.5, GN-0.4, and GN-0.3). Note that all the datasets of GN-Net are with fixed N and K.
1). In particular, we set
LFR-Ner (Lancichinetti et al. 2008 is a more challenging synthetic benchmark that can simu- late lawer-law properties of node degree and cluster size of real-world network systems. It uses (k, kmaxs Cmins Cmax (1) to independently generate a single graph, where k and kmax are the aver- age and maximum node degree; Cmin and Cmax the minimum and maximum cluster size; μ is
16

---

Under review as a conference paper at ICLR 2022
the mixing ratio between the external degree and total degree of each node v, with respect to the cluster 2/ belongs to. In particular, we fixed (k, kmax, Cuin, Cmax) = (10, 100, 10, 200) and set {0.3, 0.6). With the increase of μ., the clustering structure is increasingly difficult to identify- We consider both cases with fixed and non-fixed N, where we respectively fixed N = 5. 000 and set N to random integer within [5000, 6000) to generate 2, 000 graphs for each case. Similar to GN-Net, we also independently generated each graph in a dataset and ensure that there is no index correspondence between any two graphs via the random shuffle of node indices. For simplicity, we use L(c, μu) (c E {f.n)] n2)) to represent the dataset with a specific setting of μ., where f and n denote the case with fixed and non-fixed N (e.g., Lff. 0.3), Lif. 0.6). L(n, 0.3), and L(n, 0.6)). Moreover, K is non-fixed in LFR-Net.
Tax (Piorkowski et al. 2009 a real GPS dataset including trajectories of 1, 279 taxis in Beijing, which forms a mobile ad hoc network system. We sampled 3, 000 graph snapshots from the dataset in chronological order. In each graph, we treated each taxi as a node and constructed the topology based on the top-50 neighbors with the closest distance for each node. Since Taxi does not provide ground-truth regarding K for GP, we used Louvain algorithm (Blondel et al. 2008) to estimate the K' value for each graph in this dataset. Hence, it is with fixed N and non-fixed K.
Reddi Yanardag & Vishwanathan 2015) is a social network dataset extracted from Reddit. Each graph snapshot in the dataset corresponds to an online discussion thread. We extracted 1, 1,870 graphs with N 2 500 from the dataset. Different graphs are with different number of users (i.e., nodes), varying from 501 to 3, 648. The comment interactions between users in each discussion thread are described as topology of the corresponding graph. Since Reddit does not provide ground-truth regarding K, we also used Louvain estimate K for each graph. Hence, Reddit is with non-fixed N and K. Note that different snapshots have different node sets (i.e., with non-fixed N) and node indices in each snapshot start from 0. It indicates that there is no correspondence between node indices of any two snapshots in the dataset.
Enron (Rossi & Ahmed 2015) is a real interaction network extracted from the email system of Enron company, which contains email records from 1980-01-01 to 2004-02-04. We extracted 410 snapshots with N 2 500 from the records in chronological order, in which we treated each user as a unique node and constructed the topology based email interactions. Note that different graphs have different sets of users that have interaction behaviors. Moreover, we also used Louvain algorithm to estimate K for each graph, since Enron does not provide ground- regarding K. Therefore, it is with non-fixed N and K. We also ensure that there is no node index correspondence between any two graphs by permuting node indices of each graph from 0.
A Leskovec et al. 2005) is a real dataset extracted from the border gateway protocol (BGP) logs of communication network, which describe the topology among set of autonomous systems (AS). It contains 733 daily instances spanning from 1997-08-11 to 2000-01-02. Each BGP router is abstracted as a unique node with communication between routers extracted as the graph topology. As the dataset allows addition and deletion of routers, different graphs are with different set of nodes. Since AS does not provide the ground-truth K, we also applied Louvain determine K for each snapshot. Therefore, it is with non-fixee fixed N and K, where there is no index correspondence between any two graphs.
In summary, the 3 datasets of GN-Net are with fixed N and K. The 4 datasets of LFR-Net cover both the cases of (i) fixed N but non-fixed K as well as (ii) non-fixed N and K. Taxi is a real dataset with fixed N but non-fixed K, while Reddit, Enron, and AS are with non-fixed N and K. Note that both GN-Net and LFR-Net are synthetic benchmarks that can simultaneously generate graph topology and GP ground-truth of each snapshot. Taxi, Reddit, Enron, and AS are real datasets without ground-truth (regarding K), so we applied Louvain algorithm to these datasets to determine the K value of each single snapshot, which ensures the fairness of comparison, i.c., each snapshot shoule be assigned with a common K for all the methods to be evaluated.
hhtph///wwwtrrroooooococcccoc/oe based--n----ddd- -n--axii-
17

---

Under review as a conference paper at ICLR 2022
C.3 BASELINE METHODS
In addition to the 15 baseline methods introduced in Section we also evaluated partitioning quality and runtime of other 5 strong baselines, which include degree-correcter stochastic block model
(DCSBM), IncSNA (Su et al.) 2020), (Karrer & Newman, 201T). Deep Walk (Perozzi et al.] 2014),
node2vec (Grover & Leskovec (016), LINE (lang et al. (013). TIMERS (Zhang et al., 2018b)
and GIN (Xu et al.] (2119). In summary, we have in total evaluated the quality and efficiency of 22 baselines with 4 categories.
First, SNMF, DCSBM, and SC are classic transductive GP methods based on several GP objectives (e.g.. SC for NCut minimization and DCSBM for modularity maximization), which aim to achieve high-quality partitioning results (but may have high complexity). Moreover, IncSNA is an incrmental GP baselines that can utilize the node correspondence between graphs to incrementally update the GP results for multiple associated graphs.
Second, Deep Walk, node2vec, LINE, VERSE, MILE, PHUSION, NPR, RandNE, and ProNE are unsupervised transductive graph embedding baselines. In particular, LINE, NPR, RandNE, and ProNE are efficient embedding methods with several fast approximation strategies for the embedding learning (but may have low partitioning quality). In con- trast, DeepWalk, node2vec, VERSE, MILE, and PhUSION are baselines that aim to derive high-quality representations (but may have high complexity) Besides, TIMERS a typical incremental graph embedding method that can incrementally update the learned embedding for graphs with node correspondence.
Third, Metis, hMetis, and GraClus are classic fast transductive GP baselines that aim to achieve low runtime with the heuristic approximation of classic GP objectives (which may suffer from quality degradation due to the information loss of heuristic approximation).
Fourth, GraSAGE, GAT, and GIN, GAP, and ClusNet are inductive GNN baselines. In par- ticular, GraSAGE, GAT, and GIN are SOTA inductive GNN following the graph embedding scheme, i.e., learning node representations to support downstream tasks including GP. Note that we do not consider supervised training loss of these inductive GNNs (e.g., using the cross-entropy loss for a softmax output layer combined with the GNN), because GP is a typical unsupervised task and the cluster labels are permutation invariant. In contrast, GAP and ClusNet are E2E GP baselines based on inductive nature of GNN, where an FC output layer is integrated into the GNN to directly output the partitioning results.
Note that the first three types of methods are inherently transductive, which only focus on GP on single static graph but cannot be generalized to other new graphs. Hence, we had to apply these transductive baselines to each newly generated system snapshot (i.e., each snapshot in test set r') from scratch. For the fourth type of baselines (i.e., inductive GNN approaches), we used the same settings with IGP (i.e., offline training on training set IT and online generalization to test set r'). In particular, we can only use the inductive nature of E2E GNN methods (i.e., GAP and ClusNer) on datasets with fixed number of clusters K (i.c., on GN-Ner). However, we have to use the same settings with transductive baselines (i.e., training GAP and ClusNer from scratch for each new test graph) on rest datasets with non-fixed K, due to the fixed dimensionality of their output layers. Note that not all the datasets have node correspondence between graphs. The incremental GP and graph embedding baselines (i.e., IncNSA and TIMERS) can only be applied to datasets with node correspondence. To include IncNSA and TIMERS in our evaluation, we applied them to the original version of Taxi and AS that have node correspondence. Some other experiment settings regarding the baseline methods have been already introduced in Section
C.4 IMPLEMENTATION DETAILS
We used PoTorch to implement the dual GNN structure of IGP. The feature extraction module (i.e.. Algorithm [ and Algorithm 2 was implemented via NumPy and PyTorch, while we used the im- plementation of K Meeanss of scikit-learn as the downstream clustering module. All the experiments were conducted
server with Intel Xeon CPU (E5-2650v4@)) @.20GHH, 48 cores), 1 Tesla V100 GPU, 61GB memory, as well as the Ubuntu Linux operating system. In this setting, modules imple- mented by PyTorch were speeded up via GPU.
18

---

Under review as a conference paper at ICLR 2022
Table 4: Parameter settings and layer configurations of IGP.
IGP-M
IGP-C
Layer Confiuraatinns
[or, J.m.B. P))
(gG. nD)
(c, B.
(9G. mD)
D
GN-0.5
(I11,111000
(Se-4,5e-4)
(I,I,I,000))
(le-4,le44
GN-0.4
(1.11.1000)
(5c-4,50-4)
(1.L1,1000)
(1c-A.1o4)
2048-1024-512
512-128-64-16-1
GN-0.3
(1,5,111000)
(5e-1,5e-4)
(1,11,1000)
(le-1.Ie-4)
1400,3)
14.0.6)
(1.11.1000)
(1,3,1,1000)
(Ie-4,le.4)
(5e-4,5e-4)
(1,1e3,2,1000)
(1,1e2,5,1000)
(5e-5,5e:5)
(le4,,le4)
4096. 2048 1196-204855122222 512:256
256. 128 64 16.1
L.
(1.11,1000)
(5e-4,5e-4)
(1.1e2,511000)
(le-L,Te-4)
Mm..6)
(1.3..1100)
(1e.4.le.4)
(1,1e3,2,1000)
5,5ee))
4096-2048-512-355
256-128 12-----166611
Tasi
(1,01.1,2000)
(5e-5,5e:5)
(1,162,1,2000)
(5e-5.5e-5)
1024-512-256
256-64-32-16-1
Reddi
(100.1111000)
(5e:5,5e:5)
(1,0.1.1,100)
(5e-4,5e-4) 4)
2048: 1024 512-256
256 256-64-16-1
AS
(1.0..1.500)
(5e-5,5e-5)
(1,162,1.500)
(5e-5,5e-5)
6200-4096-2048- 204-102---00
256-128-64-16-1
Envon
(1,311300)
(5e-5,5e-5)
(1,162,1,300
(3e-5,5e-5)
1024-312-256
256-128-64-16-1
For all the embedding based methods, including transductive embedding baselines (i.e., second type of the baseline), inductive GNNs (i.c., GraSAGE, GAT, and GIN), and IGP, we used KMeans as the downstream clustering module. In contrast, we can directly obtain the partitioning results from outputs of the rest baselines. Note that K'Means for graph embedding based methods and optimization algorithms of several classic GP baselines (i.e., SNMF, DCSBM, Metis, hMetis, and GraClus) have the limitation of obtaining locally optimal solutions. We adopted the strategy to run Meaan of embedding based methods and optimization algorithms of classic baselines 10 times, which was included in the total runtime of corresponding methods. The partitioning membership with minimum loss function value (e.g., the sum of squared distance between data and cluster center for K Meeans) was reported as the final partitioning result for evaluation. When testing the runtime of each method, we ensured that only the method to be evaluated was running on the experiment server, i.e., there were no multiple methods simultancously running on the test server.
On the validation set Iv of each dataset, we tuned parameters and determine proper layer configura- for both
tions for the two variants of IGP. Concretely, we adjusted a E {1, 10] and m E 21, ...5 5)
5) and 3 E {0.1, 1, 100, 1000} for IGP-M and IGP-C, respectively. The recommended parameter settings and layer configurations of IGP-M and IGP-C on each dataset are depicted in Table + where dimensionality of the first and last layer of G are set to be L. (i.e., dimensionality of reduced feature) and is (i.e., dimensionality of graph embedding), respectively. Note that we use the same layer configurations for IGP-M and IGP-C on each dataset. Moreover, we the maximum number of epochs n 100 for all the datasets.
IGP-M and IGP-C, while we tuned 3 E {0.1, 1, 2, .......... 5)
C.5 DETAILED EVALUATION RESULTS AND DISCUSSIONS
C.5.1 QUANTITATIVE EVALUATION
In addition to the visualization results of NMI, Modularity, and runtime in Fig. we also visual- ized the evaluation results in terms of average AC, NCut, and runtime on test sets of the 11 datasets in Fig. 4 where one can have the observation consistent with Fig. 3 In most cases, both IGP-M and IGP-C are in the top groups with best quality metrics. The total runtime of IGP-M and IGP-C is also competitive the fast transductive GP baselines.
In the experiments, we recorded the mean value μ and standard deviation a of all the evaluation metrics and runtime for all the methods (on test I of each dataset). In particular, we use format (a)' to represent each evaluation result. The quantitative evaluation results on GN-Net and LFR- Ner in terms of NMI and AC are depicted in Table and Table 6 The evaluation results on all the datasets in terms of modularity and NCut are illustrated in Table 7 Table 8 Table 9 and Table 10 Moreover, Table M1 and [2 give the runtime of all the methods. For both IGP-M and IGP-C, we also recorded the time of (i) feature extraction (i.c., Algorithm 2 (ii) one feedforward propagation (through the feature encoder of G), and (iii) downstream clustering (i.c., 10 independent runs of KMeans), which together contribute to the total runtime of IGP. Runtime of the three modules is denoted as 'Feat', 'Prop', and 'Clus', respectively.
According to evaluation results in Table 5) Table Table 7 Table Table 9 Table 10 Table and Table 12 which are consistent with the visualization results in shown Fig. (see Section we have the following major observations.
19

---

Under review as a conference paper at ICLR 2022
9:73
3:55
6.4
6:3
KGP-88
DGraClls
PPoNE
KYMP M
PRY
N (1)
500
MMris
AlMeli
PANN
ChoNet
VERSE
0.94
IGE4
DGraClas
IGP
SCP MILE
SAMEE
PAN+
NEw:
100
GAT
CAP
CioNa
<0.5
241
6:7
Metis
Medk
RandNK
REGAP ClegNet VERSE
302
CraChis
PGP-M
JGP
MILE
SYMPR
<0.9
0.52
Muels
45
RaMAEE
SAP Cha VERSE
200 CraCh HGPSE
100
SCpp MILK
PAN
Time fsce
jace,
Time (ses.
(a) GN-0.3
(b) GN-0.4
KGF- PPoNE
RGNC
MILE SAAD
SC
792
HAT NRPGAP
ClbNNe
Top.c
Bc
RaEASE
ConNe
5.95
Made
0,9
MMets
PKN+
2.95
3.97
OSAGE
RasdNE
ORaadNN
JGNC
5C MILE-
VERSE,
Gratlss
ChoNete
VESRSE
43
GraChas
Metaa
PPPrNN
poc
VERSE
200
PrNNE
PAN SXMP-8
$3.55
MILE CleaNet VERSE,
102
00
SXME
GAP
2-00
P00
Time
Time
Time
(C) GN-0.5
(d) LfA003)
JGPM
Chasde"
ESAGE RINONE
ClasNer
OJGP-M
200
GAT GSAGE
ClesNer
OOGGP.C C
9Cp.C
Gratilas
SYME
PAN+
Meds Metk
GAP
GreCher UGP-T Maii
SCP
GraCllas
GroCims
RuslNP
bac
1oc
SNME
0.55
HESALLE
ARP
VERSE-
SNMP
SIGP-C
'MLLEE
DSC
SYMP
GAPe
PAN-
30
20
4
2-00
26
40
5-0
20
500
Time (900
Time r0es
Time 156
Time (ecc
(e) (4F.0.6)
(f) 1l.0.3)
PrNNE
Cluaaer
PAN-
2000
BSSGGE CAN
ClasNer
GSAGE
230
Nh?
ProNp
VERSE
3.95
GAP+
PIN+
SNME
140
30
GAI
0.3
Metts
EXAGE
AlMeds
GAP
100
130
Meth
VERSS-2
Crocles
PONNE SYMP
+
PLN
IGP-
4
MILE
0.25
poc
40
200
20
-000
Time Iee. a
Time Sec. 15
Time (3
Time (sar,
L(n.0.6)
(h) Taxi
(i) Reddit
HandNE
VERSE
MILE
NRP
Scar
ClaNd
PriNE
NRP
ClaoNe
Figure 4: Visualization results on the 11 datasets
GraCli
4S0
terms of quality metrics of AC (f) and NCut
10
PrNNE
-MILE pac
VERSE
PRN
10
AG 3
(L) (y-axis), as well as efficiency metric of run- time (4) (x-axis). The number records are given
JoP M
Time cenc.
Time
Table 8
and T2
(i) AS
kk) Enron
For all the datasets, IGP-M and IGP-C are the top group with best quality metrics. More- over, their runtime is also competitive to fast GP baselines (e.g., Metis, hMetis, GraClus, RandNE, etc.) and other inductive GNNs with fast online generalization (c.g.. GraSAGE, GAT, and GIN). From the perspective of alleviating the NP-hard challenge of GP, IGP can achieve a significant trade-off between quality and efficiency of online GP on newly gener- ated system snapshots. We further quantitatively evaluate the significant trade-off obtained by IGP via novel trade-off score in Appendix C.5.2
Surprisingly, in some cases, IGP even has the best or second-bess quality metrics. Note that IGP is novel inductive framework. in which we do not conduct additional optimization on the test set of each dataset, but other conventional transductive basclines (c.g., SP, Deep- Walk, etc.) can fully explore the structural properties of each test graph. It indicates the potential of IGP to capture additional characteristics shared by multiple historical snapshots beyond conventional transductive approaches applied to one single new graph.
On GN-Net and LFR-Net, partitioning quality of all the methods declines with the decrease of Pin and increase of μu, where both IGP-M and IGP-C are always in the top group with best quality metrics. It demonstrates the strong robustness of IGP, especially when the intrinsic clustering structure of the given graph is not distinct.
20

---

Under review as a conference paper at ICLR 2022
Table 5: Quantitative evaluation results in terms of NMI (%) (T).
GN-0.5
GN-0.4
GN-0.3
lrf0.3)
T(f06,61
Lp.0.3)
(2,0.6)
SNMF
99.53 (0.21)
98.79 (0.36)
94.37 (0.69)
83.53 (1.60)
(2.56)
83.59 (1.59)
49.98 (2.19)
DCSBM
67.92 (10.49)
$7.68 (10.4)
49.76 (6.04)
(6.25)
27.27 (2.89)
44.73 (7.48)
07.32.2243)
SC
99.75 (0.10)
98.73 (0.24)
94.26 (0.41)
98.19 (0.39)
(3.65)
98.21 (0.35)
24.66 (2.76)
DeepWalk
99.40 (0.
97.60 (0.30)
82.81 (0.85)
91.27 (0.77)
55.71 (2.19)
93.36 (0.78)
56.40 (2.03)
node2vec
99.44 (0.09)
98.89 (0.19)
88 (0.77)
95.15 (0.73)
59.11 (2.21)
95.22 (0.68)
59.88 (2.07)
LINE
93.73 (0.54)
68.70 (0.75)
53.25 (0.31)
80.72
42,69 (2.59)
79.89 (1.56)
38.78 (3.29)
VERSE
92.09 (0.99)
84.75 (1.57)
61.15 (1.50) 50)
89.80 (0.89)
44,97 (3.16)
89.94 (0.97)
45.87 (3.05)
MILE
(0.09)
(0.13)
93.39 (0.48)
93.87 (0.95)
20.37 (2.32)
20.67
PHUSION
99.46(00.08
98.81 (0.20)
93.89 (0.57)
94.85 (0.75)
54.18 (2.64)
94,90 (0.72)
55.52 (2.38)
94.98
(0.86)
77.90 (1.24)
(2.39)
(3.05)
22.26
RandNE
98.33 (0.26)
94.08 (0.47)
79 19.1811 (1.01)
57.63 (2.06)
18:57 (2.16)
58.08 (2.08)
18.87 (1.95)
ProNE
99.80
99.54 (0.08)
96.62 (0.36)
93.33 (0.81)
55,88 (3.04)
93.31 (0.89)
$7.61 (2.63)
Metia
98.68 (0.33)
94.68 (0.41)
(0.77)
(0,74)
(2.48)
(0.71)
45.53 (2.28)
hMetis
(0.16)
93.82 (0.30)
82.08 (0.68)
88,85 (1.27)
41.65 (3.28)
89.13 (1.17)
42.64 (2.99)
GrCClus
99.54 (0.19)
98. (0.30)
90.72 (0.76)
90.58 (1.14)
53,06 (3.00)
90.60 (1.09)
$1,90 (2.75)
GrASAGE
45.76 (0.13)
45.98 (0.09)
43.21 (0.21)
22.52 (2.21)
15,79
24.67 (2.03)
16.66 (1.77)
GAT
46.09 (0.24)
45.03 (0.25)
44.55 (0.20)
22,99 (1.88)
15.49 (1.78)
25.91 (1.94)
15.83 (1.70)
GIN
43.29 (0.19)
43.26
43.49 (0.17)
18.49 (1.83)
13.32 (1.47)
(1.71
13.43 (1 ..22)
GAP
72.69 (0.52)
64.37 (0.39)
56.13 (0.31)
93.73 (1.76)
47.30 (3.23)
93.64 (1.65)
48.01 (3.11)
ClusNet
(1.85)
17.65 (2. 10)
13.10 44)
89.84 (1.31)
55.49 (2.04)
90.10 (1.27)
56.04 (1.78)
IGP-M
99.85 (0.05)
99.38 (0.11)
96.26 (0.32)
97.21 (0.49)
56.07 (2.33)
97.30 (0.44)
$6.48 (2.08)
IGP-C
99.85 (0.04)
99.46 (0.09)
95.50 (0.43)
96.44 (0.57)
$2.11 (2.79)
(0.59)
52.71 (2.52)
Table 6: Quantitative evaluation results in terms of AC (%) (t).
GN-0.5
GN-04
GN-0.3
11f0.3)
1/f0.6)
((m.0.)
T(a.0.6)
SNMF
98.70 (0.50)
97.46 (0.78)
50.25 (1.32)
73.27
72.96 (2.56)
41.95 (2.40)
DCSBM
38.08 (13.89)
25.83 (9.88)
16.40 (3.93)
22.35 (4.39)
13.65 (2.02)
21.37 (4.96)
(1.75)
SC
98.69 (0.39)
96.67 (0.54)
89.29 (0.85)
95.09 (0.73)
26.01 (3.62)
97.27 (0:96)
12:26 (1.59)
WeepWalk
96.40 (0.38)
93.15 (0.91)
69.03 (1.52)
87.91 (2.01)
54.97 (2.10)
87.65 (2.13)
55.12 (1.97
node2vec
(0.51)
95.53 (0.64)
(1.47)
(2.10)
(2.07)
(2.05)
58.79 (1.9)
LINE
87 (1.06)
46.90 (1.34)
20.36 (0.66)
(3.07)
38.22
70.55 (3.17)
33.63 (3,50)
VERSE
80.76 (1.89)
70.02 (2.53)
35.39 (2.16)
83,89 (2.07)
40,25 (3.33)
83.56 (2.14)
41.03 (3.11)
MILE
98.67 (0.31)
96.91 (0.50)
87.48 (0.91)
(1.60)
10.19 (0.93)
92.57 (1.55)
9.94 (0.86)
PhUSION
96.49 (0.54)
94.76 (0.66)
86.77 (1.11)
89.14
$1.83 (2.49)
88.80 (1.75)
$2.75 (2.25)
NRP
81.61 (1.36)
72.90 (1
56.39 (1.78)
42.27 (2.46)
20.42 (1.74)
38.75 (2.64)
16.43 (1.70)
RandNE
93.07 (0.68)
86.36 (1.03)
63.77 (1.49)
40.67 (1.77)
12.91 (1.25)
40.64 (1.73)
12.80 (1.17)
ProNE
(0.36)
(0.42)
(0.80)
(2.55)
(2.95)
(2.52)
$3.51 (2.76)
Metis
(0.62)
91.25 (0.82)
66.48 (1.55)
58.70 (2.288
(1.77)
(2.57)
35.37 (1.55)
hMeess
88.01 (0.44)
84.44 (0.72)
83.16 66.841..00
66.62 (3.16)
32,80 (2.91)
65.99 (2.49)
33.26 (2.63)
GraClus
97.54:00.84)
(0.94)
(3.40)
(3.02)
71811 (3.33)
46.50 (2.78)
GmSAGR
(0.13)
7.66 (0.13)
(0.12)
7.55 (0.25)
5.79 (0.
7.58 (0.34)
5.66 (0.19)
GAT
9.20
8.66 (0.16)
(0.13)
8.52 (0.36)
6,22 (0.16)
8.78 (0.40)
5.69 (0.19)
GIN
7.61 (0.12)
7.51 (0.11)
(0.1))
6.97 (0.23)
5,83 (0.15)
6,08 (0.30)
5.37 (0.21)
GAP
(1.04)
29.71 (0.76)
(0.57)
83.63 (6)
40.06 (3.34)
83.06
40.08 (3.41)
ClusNet
4.51
2,94
(0.23)
86.45 (2.47)
$6.20
86.87 (2.36)
56.25 (1.65)
IGP.M
98.96 (0.28)
97.36 (0:46)
91,96 (0.73)
94.29 (1.41)
53,57 (2.21)
94.24 (1.38)
33.422.044
IGP-C
98.93 (0.31)
97.48 (0.46)
90.47 (0.85)
92.58 (1.49)
47.38 (2.68)
92.46 (1.46)
47.47 (2.59)
Similar IGP, the E2E GNN baselines (i.c., GAP and ClusNet) can also apply fast online generalization to datasets with fixed K (i.e., on GN-Ner). Namely, we also trained GAP and ClusNet on training set of GN-Ner and directly generalized them corresponding test sets for online GP, in which we directly derived the partitioning results from their output layers. However, the online GP of GAP and ClusNer is with poor quality, which indicates that the online generalization of the graph embedding scheme in IGP is more robust than that of the E2E approaches, especially when clustering structure of a dataset is not distinct. Furthermore, we still need to train GAP and ClusNer from scratch for each new test graph on datasets with non-fixed K due to the fixed dimensionality of their output layers, which is time-consuming. In contrast, the graph embedding scheme of IGP can still tackle fast online GP with non-fixed K.
In contrast to the reduced structural feature Z, in IGP, we used constant matrix 1N as feature inputs of inductive GNN baselines (i.e., GraSAGE, GAT, adn GIN), which is a standard setting of most inductive GNNs for graphs without available node attributes (Xu et al. 2019). The widely- unsupervised training loss of GraSAGE (Hamilton et al.) 2017)) was also adopted in the offtine training of these inductive GNNs. Although the inductive GNN baselines have slightly faster runtime over IGP, they still suffer from poor partitioning quality on all the datasets. The results further validate that the extracted
21

---

Under review as a conference paper at ICLR 2022
Table 7: Quantitative evaluation results in terms of Modularity (%) (1) on datasets with ground-truie
GN:0.5
GN:0.4
GN40.3
T1,0033)
14,0.6)
Lim0.3)
Trn.D.6)
SNMF
47,95 (0.23)
37.79 (0.27)
27.28 (0.29)
(1.58
29.22 (0.63)
(6.03 (1.50)
29.43 (0.60)
DCSBM
(5.55)
9.33 (2.40)
3.86 (0.72)
11.37 (2.46)
4.77 (0.96)
11.00 (2.68)
4.71 (0,74)
48.13 (0.20)
37.81 (0.23)
27.07 (0.23)
67.32 (0.20)
(1.06)
67.50 (0.26)
23.62 (2.83)
Walk
47.88 (0.20)
37.27 (0.28)
21.97 (0.46)
(1.11
33.92 (0.54)
(1.14)
34.06 (0.48)
Bode2vee
47.89 (0.19)
37.91 (0.21)
24.62 (0.45)
63,23 (1.14)
34.47 (0.54)
63.30 (1.14)
34.64 (0.47)
LINE
42.47 (0.59)
15.96 (0.61)
(0.17)
55,88 (1.84)
23.34 (0.98)
55.21 (1.74)
20.76 (1.93)
VERSE
41.33 (0.91)
28.62 (1.05)
12.79 (0.69)
(1.18)
29.34 (1.13)
60.52 (1.19)
29.40 (1.08)
MILE
48.21 (0.18)
(0.20)
26.96 (0.27)
66.37 (0.34)
(1.25)
66.55 (0.42)
(1.14)
PhUSION
47.89 (0.20)
37.79 (0.22)
27.03 (0.29)
(1.00)
33,80 (0.50)
63.26 (0.91)
34.06 (0.48)
NRP
45.21 (0.41)
34,31 (0.39)
22.27 (0.46)
24.32 (1.29)
7.07 (0.72)
25.00
5.69 (0.80)
RandNE
47.29
35.61 (0.34)
21,08 (0.47)
(1.20)
3.26 (0.34)
18.48 (1.21)
3.38 (0.32)
ProNE
48.20 (0.18)
38.20 (0.19)
27.92 (0.24)
60.96 (1.19)
32,64 (0.81)
60.98 (1.17)
33.24 (0.70)
47.29
35.24 (0.30)
(0.36)
(1.12)
(L.17)
(0.39)
hMeeti
44.78 (0.22)
34.62 (0.28)
22.39 (0.31)
57,51 (1.14)
31.80 (0.60)
57.44 (0.96)
31,99 (0.49)
GraClus
47,83 (0.26)
$7,34(00.0)
(0.488)
53.54 (1.98)
31.61 (0.92)
53.43 (1.87)
31.71 (0.83)
GrISAGE
0.08 (0.03)
0.04 (0.03)
0.01 (0.01)
0.28 (0.17)
0.18 (0.11)
0.56 (0.27)
0.17 (0.16)
GAT
0.48 (0.05)
0.27 (0.05)
0.08 (0.03)
0.99 (0.17)
0.08 (0.12)
1.71 (0.22)
0.02 (0.11)
GIN
0.05
0.03 (0.03)
(0.03)
(0.11)
0.06 (0.08)
4.73 (0.29)
4.19 (0.18)
GAP
19.35 (0.63)
9.95 (0.36)
5.24 (0.19)
(0.59))
32.96 (0.73)
66.65 (0.57)
32.96 (0.77)
ClusNet
0.03 (0.10)
0.02 (0. 12)
0.01 (0.13)
65.52 (0.53)
35.10 (0.51)
65.77 (0.54)
35.25 (0.44)
IGP-M
48.25 (0.18)
38.17 (00.20)
27.92 (0.22)
66.26 (0.54)
34.14 (0.53)
06 (0.56)
34.22 (0.47)
IGP-C
48.25 (0.18)
38.19 (00.19)
27.68 (0.25)
65.72 (0.59)
31.81 (0.65)
65.83 (0.64)
31.95 (0.62)
Table 8: Quantitative evaluation results in terms of Modularity (%) (1) on datasets w/o ground-truth.
Taxi
Reddit
AS
Enrow
SNMF
73.72 (0.41)
68.29 (7.16)
53.32 (2.55)
73,88
DCSBM
73.71 (0.60)
(5.17)
(2.16)
4.36
SC
(0.59)
61.19 (7.68)
(3.1466.60)
71.43 (19.05)
IncSNA
71.96 (0.79)
4.13 (1.13)
Walk
73.72 (0.54)
65.66 (8.91)
56,48 (2.90)
74.72
node2vec
73.64 (0.54)
69.31 (7.90)
58. (2.80)
76.86 (13.31)
LINE
73.95 (0.54)
$7.25 (12.92)
(4.87)
70.94
VERSE
73.69 (0.51)
(13.77)
$2.25 (10.59)
73.43 (18, 95)
MILE
72.91 (1.21)
59.09 (17.94)
56.83 (3.20)
74.78 (18.98)
PhUSION
72.93 (0.59)
67.69 (6.18)
58.18 (2.78)
67 84 (12.37)
NRP
6.07 (9.55)
4.01 4.01 (5.99)
4.61 (3.39)
0,24 (6.53)
RandNE
(5,04))))) (0.72)
5,30 (0.54)
21.53 (12.32)
ProNE
73.61 (0.64)
62.88 (5.27)
(3.87)
62.80 (9.98)
TIMERS
30.80
(1.29)
Mets
70.48 (0.31)
52.34 (10.68)
$2.75 (3.86)
65 63,04 (17.07)
hMMeti
73.44 (0.80)
54,27 (11.02)
56.03 (4.33)
67.5 54 (18.16)
GraClus
73.05
45,27 (11.5)
46.81 (4.83)
62.02 (3)
GraS
GGE AGE
(1.1I)
6.94 (3.72)
5.69 (1.47)
9.41 (6.55)
GAT
1.11 (0.42)
8.69 (11.82)
(0.84)
4,20 (4.89)
GIN
(0.4-))
4,82 (7.30)
5.62 (7.60)
10.82 (3.61)
GAP
(1.30)
65.08 (6.24)
58.31 (2.68)
75.47 (12.57)
ClusNet
72.54 (1.27)
55.31 (10.37)
55.87 (2.42)
72.56 (18.75)
ICP.M
74.01 (0.51)
69.38 (5.49)
(2.71
(13.55)
IGP-C
74.00 (0.42)
69.37 (5.47)
35.40.22.26
74.15 (11.78)
feature Z, as well as hybrid training loss of IGP (which can incorporate the permutation invariant label information of historical training snapshots) are essential to ensure its high partitioning quality.
For the total runtime of IGP on all the datasets, the downstream clustering (e.g., K'Means with 10 independent runs) major bottleneck. However, the downstream clustering module is also the key component that enables IGP to deal with online GP with non-fixed K. In our future work, we intend to further reduce the runtime of IGP by replacing the downstream clustering module with generic E2E module that can directly derive the par- titioning result with respect to a specific (non-fixed) K via an output layer.
In most cases, IGP-M and IGP-C have similar quality metrics. On datasets in which the clustering structures more difficult to identify (e.g., L(f. 0.6) and L(n, 0.6)), IGP-M has better partitioning quality than that of IGP-C. It implies that the modularity matrix Q is more informative than the normalized adjacency matrix M, be the neighbor similarity feature X, in IGP. Moreover, the neighbor-induce feature X, is also the key component to ensure the strong robustness of IGP, especially when clustering structures of given graph are indistinct.
22

---

Under review as a conference paper at ICLR 2022
Table 9: Quantitative evaluation results in terms of NCut (4) on datasets with ground-truth.
GN-0.5
GN-0.4
GN-0.3
((00.3)
[1,0666)
Lom,0.3)
Lia.6.6)
SNMF
(10.94
214.23
352.04 (8.94)
(5.66)
98.49 (10.95)
(6.33)
(1..72(11.89)
DCSBM
3.74c3 (2.33e3)
1.7344 (4.37e3)
3.26c3 (1.723)
2.25c3
4.10c3 (2.143))
2.51e3
SC
294.67 (388.31)
211804
(34.26)3
35.38 (35.34)
129.48 30)
(4.20
88.11 (43.17)
WoepWalk
283,44 (114,49)
(20222 14)
(,05631298.3
42.39 61.17(16.20 (39.00)
89.76 (35.83)
Rode2vee
224.85 (84.62)
346.07 (142.89)
164.81
55.11 (94.33)
(37.93
50.57 (63.56)
87.03 (34.39)
LINE
374.65 (251.98)
1.25e3 (33188)
(532.29)
2.
2.20e3 (1.303)
2.83e3 (1.13e3
(1.12e))
VERSE
363.71
463. 89 (64.89)
939 (56 (7)
43.07 96)
(11.6
47,99 (70.43)
(.042
MILE
(86,44(86640))
262.43 (81.67)
356.62 (7.27)
36.87 (62.47)
60.60 (7.52)
33.36
65. (9,75)
PhUSION
160.17
222.93 (5.29)
360.98 (7.67)
24.87 (4.02)
74.25 (7.70)
27.21 (3.59)
80.54 (8.46)
NRP
806.64 (190.88)
2.18c3 (374.90)
5.82c3 (621.38)
191c3 (660.70)
7.48c3 (6c3)
3.84c3 (848.78)
9.63c3 (1 36c3)
RamdNE
464.84
1,36g3 (372.75)
5.0773 (877.58)
2.24e3 (314.1))
1.31e4 (2.30c3)
2.83e3 (1.8333)
1.41e4 (2.56c3)
ProNE
(77.47)
295.37 (92.08)
47.03 (125.66)
78.78 (8.51)
59.34 78)
85.04 (9:65)
Meus
(3.88)
242.91 (6.56)
(12.66
38.60 (5.76)
87.21 (9.53)
(7.72)
(10.46)
hMeiss
189.03 (4.85)
304.87(11.92 (11.92)
531 (13.98)
69.77 (97.05)
76.78 (7.44)
(129,09))
83.35 (8.72)
GraClus
(37.66)
229.87 (74,71)
396,54 (24.44)
39.55 (7.91)
79,57 (9.25)
44,04 (7.73)
86.74 (10.02)
GRG
1.8765 (1.25e4)
2.05e5 (1 (1299c4)
[42c511.1764)
(4
3.716415.1ee
4.79e4 (6. 36:3)
5.50 79:3)
GAT
7.70c4 (9.07c3)
9.49p4 (9.97)3)
1.36:5 (1.27c4)
L8164 16c3)
3.1764 (5 66c3)
3.26 (5. 31c3)
3.40p4 (6 86c3)
GIN
1.36e5 (1.054e4)
1.4555 (1.10e4)
1.53e5 (1.11e4)
26
(7.5033)
4.45e4 52c3)
4.05e4 (9.36c3)
GAP
4.38e3 (1.21e3)
7.99c3 (2.00e3)
1.28e4
17.33
(2.74)
69,5463 (7.84)))
18.35 (2.51)
(9.2432
ClusNet
3.5864(8..380)
2.80e4 (223)
2.91e4 (2.233)
2.97e2 (1 66c2)
1.1 (4.182)
2.91e2 (1.562)
1.1963 (4.22e))
IGP-M
(71.77
317.82 (91,
345 (2(19.55
32.39
75,92 (8.29)
34.84135.44 44)
82.76 (8.97)
IGP-C
(73.72(73.70)
289.53 (88.19)
354.95 (29.97)
(21.72)
85.00 (9.02)
38,96
92.40 (10.05)
Table 10: Quantitative evaluation results in terms of NCut (L) on datasets without ground-truth.
Tax
Reddie
AS
Faron
SNMF
0.7851 (0.1299)
6,7052 (8.4353)
10.0464 (10464(1.60) (1.6011)
23.0720 (1.34e2)
DCSBM
0.7908 (0.1338)
7.22c3 (3.89e3)
4.76e2 (3.74=2)
3.05e3 10e)))3)
SC
0.7677 (0.1294)
2.8457 (1.5721)
2.2442 (0.2929)
0.7977 (0.5563)
IncNSA
0.5393 (0.0877)
8,26c3 (3.84c3)
DeepWalk
0.7999 (0.)
56.7501 (3.5162)
6,9109 (131
54,3684 (2,48c2)
2ode2vec
0.8069 (0.1201)
4,4548 (4.0488)
1055 (1.0540)
14,9095 (87 (0220)
LINE
0.7685 (0. (260)))
9.31e2 (1.45e3)
2.98c2 (5 46:2)
1.0422 (4.30e2)
VERSE
0.7983 (0.1247)
1. 1,26c3 (1.5364)
11 8885 (9.2661)
I 1.4c22 (6.50c2)
0.8378 (0.1261)
9.9%:2 (1.56e3)
8.6199 (2.5743)
1,3722 (6.10)2)
PhLSSIONN
0.8541 (0.1372)
40.3041 (69. 9684)
6,2456 (1.0257)
91 8462 ( (133e22)
NRP
51,7825 (57.8389)
6.84e2 (7. (322)
1,72e3 (1. (5e)))
4.66c2 (8.2))
RandNE
0,8050 (0.1239)
5,33c3 (3.50c3)
6.62c3 (3 (3.08:3)
3.26e3 (2.35c3)
ProNE
0.7824 (D.1251)
52.6408 (4.52e2)
12.8754 (4.0178)
35, (1.09e2)
TIMERS
3,4756 (0. (0.5099)
1,38c3 06:2)
Metis
1.0955 (0.1264)
2. 2.94e2 (4.45e2)
15.3312 (3.7055)
2.95e2 (4.39e2)
MMeeii
0.8305 1577
6.76e2 (7 88c2)
3087 (1 59:2)
4.26c2 (6,40e2)
GraClus
0,8493 10.1
2.20c3 (1.75c3)
17.8574 (6.7540)
3 3.08c2 (7.82c2)
GraSAGE
12,4076 (2.1775)
6,59c3 (3.9763)
1.05e4 (3.85e3)
4,39c (1.6823)
GAT
1.20c3 (4.26e2)
5.21e3 (2. 86e3)
5,27e3 84e3))
2.1723 (9.5322)
GIN
25.31 (4.63)
6. (3 74e3)
1.1 (3.01le)
6.34c3 (2.60e3)
GAP
0.9371 (0.1529)
4.1535 (4.4771)
6.1307 (1. (1.2355)
1.3524 (0.4140)
ClusNet
6.9216 (42.5113)
28.2975 (53:4356)
31,4675 (49.0738)
23,6067 (99.4427)
IGP-M
0.7711 (0.1241)
4,7408 (2.1934)
7,2568 (1.2706)
4,3338 (16.9436)
IGP-C
0,7736 (0.1253)
4.7084 (2.1537)
9.6586 (3.4559)
4,3581 (16.5047)
C.5.2 TRADE-OFF ANALYSIS
In this paper, we focus on the trade-off between quality and efficiency of online GP on newly gen- erated graphs from a system. To the best of our knowledge, to evaluate the trade-off between two aspects that conflict with each other using comprehensive metric remains an open issue. We pro- pose a trade-off score (TOS) to quantitatively evaluate the trade-off between quality and efficiency of given GP method. Concretely, the calculation of TOS is based on the normalized area covered by an induced rectangle of a data point in the quality-efficieney visualization result (like Fig. 3 Fig. glivves two running examples regarding how to calculate TOS for given GP method. Our goal is to let larger TOS indicate a better trade-off between quality and efficiency.
In our evaluation, we use NMI, AC, modularity, and NCut the quality metrics, while we evaluate the efficiency of a specific method via its total runtime. Let Q and E be the value of a quality metric and the runtime with respect to GP method to be evaluated. Given the tuple Q), each method used in our experiments can be visualized as a data point in a 2-D space as illustrated in Fig. 3 When we use NMI or AC the quality metric Q. we further derive the normalized metric via
Q Q/1,
(15)
23

---

Under review as a conference paper at ICLR 2022
Table 11: Quantitative evaluation results in terms of runtime (sec) (L) on datasets w/ ground-trutte
GN-0.5
GN-0.4
GN-0.3
T(f.0.3)
14f066)
Lrm..3)
Lz,,0.6
SNMF
(63.29
251.32(55.10))
326.90 (63.67)
(32.13)
136.21 (0.64)
155.84 (43.87)
194,13 (54.34)
DCSBM
143,91(14.99
(16.88)
(19.99(19.77)
123.05 (7.95)
127.26 (11.40)
161.94 (24.38)
165.57 (28.21)
SC
49.38 (0.60)
(0.69)
(1.08)
21,04
42.54 (2.21)
(3.85)
53.26 (6.95)
WeepWalk
(0.57)
36.63 (0.67)
42,92 (0.95)
(0.38)
18.04 (0.53)
16.87 (1.04)
19.45 (1.19)
mode2vee
54.36 (0.58)
54.63 (0.71)
59.75 (1.01)
30.97 (0.62)
33.55 (0.61)
34.81 (2.03)
35.86 (2.00)
LINE
34.29 (1.72)
29.38 (1.99)
24.16 (1.74)
(0.5
8.51 (0.62)
10.84 (1.87)
13.28 (1.52)
VERSE
185.28
185.95
184.87 (1.
112.85 (0.92)
(0.97)
123.72 (6.
125.10 (6.80)
MILE
50.77 (3.76)
16.31 (11.6))
21.36
23.38 (3.60)
PhUSION
113.65 (1.333
115.98 (0.58)
85.62 (0.49)
86.59 (0.45)
105.61 (11.14)
105.61 (10.95)
NRP
(0,28)
14.03 (0.57)
16.58 (1.34)
2.44 (0.23)
2.82 (0.24)
5.24 (0.49)
5.07 (0.57)
RandNE
17,83 (0.09)
12:48 (0.14)
14.73 (0.22)
2.12 (0,18)
2.49 (0.22)
2.54 (0.30)
2.91 (0.33)
ProNE
18,85 (0.13)
21.36 (0.30)
6.67 (0.23)
7.46 (0.33)
7.85 (0.70)
8,81 (0.71)
2.21 (0.06)
2.60 (0.04)
3:23 (0.08)
(0.07)
147
1.21 (0.10)
(0.09)
hMMeti
12.68 (0.43)
13,59 (0.48)
15:53 (0.58)
5.51 (0.21)
7.58 (0.26)
6.29 (0.50)
8.62 (0.67)
GraClus
1.59 (0.08)
1.77 (0.07)
L88 (0.10)
0,88 (0.08)
0.94 (0.04)
0.95 (0.04)
1,03 (0.05)
GmSAGE
8.12
(0.31)
8.18 (0.30)
2.58 (0.17)
2.50 (0.16)
(0.3)
3.38
GAT
5.70 (0.12)
5.56 (0.15)
5.37 (0.12)
2.03 (0.16)
2.37 (0.19)
2.77 (0.31)
2.81 (0.29)
4.49 (0.07)
4.58 (0.10)
(0.06)
(0.14)
(0.15)
1.83 (0.22)
(U.23)
GAP
19.63 (0.66)
19.59 (0.59)
19.59 (0.61)
66.45 (1.96)
66.94 (1.75)
76.79 (6.73)
77.66 (6.57)
ClusNet
38.66 (0.23)
39.21 (0.21)
40.16 (0.24)
73.28 (4.97)
76.96 (4.27)
88.50 (7.63)
90.07 (8.14)
IGP-M
9.93 (0.25)
11.19 (0.32)
13.63 (0.35)
2,48 (0.18)
3,56 (0.26)
2,95 (0.32)
4.19
Feat
0.42 (0.01)
0:42 (0.01)
0.42 (0.01)
0,20 (0.01)
0.20 (0.01)
0,23 (0.02)
0.23 (0.02)
Prup
0.02 (0.001)
0.02 (0.001)
(0.0005)
(0.0006)
(0.0005)
0.03 (0.0022
(0.002)
Clus
9.49 (0:25)
10,76 (0.32)
13.18 (0.55)
2.25 (0.18)
3.33 (0.26)
2.67 (0.31)
3,93 (0.45)
IGP-C
(0.28)
11.42 (0.30)
14.11 (0.50)
2.84 (0.20)
3.55 (0.25)
3.36 (0.37)
4,24 (0.44)
Feat
0.46 (0.01)
0.46 (0.01)
0.471 (0.01)
0.24 (0.01)
0.25 (0.01)
0.28 (0.03)
0.28 (0.03)
Prup
0.02 (0.002)
0.01 (0.0003)
0.02 (0.0003)
0,03 (0.0004)
0.03 (0.0004)
0.03 (0.002)
0.03 (0.0022
Clus
9.45 (0.28)
(0.30)
(0.50)
(0.20)
(0.25)
3.05 (0.35)
3,93 (0.42)
Table 12: Quantitative evaluation results in terms of runtime (sec) (4) on datasets w/o ground-truth.
Tasi
Reddiz
AS
Enron
SNMF
(1.4()
217.1.9372.55
112.31 (83.53)
1.68 (1.25)
6.15 (0.15)
(12.63)
197.17 (135.89)
3.17 (1.54)
SC
1.34 (0.08)
0.35 (0.52)
15.13 (9.66)
0.28 (0.33)
lacSNA
0.99 (0.24)
1.43 (0.81)
DeepWalk
8.97 (0.09)
9.99 (6.05)
34.33 (14.71)
(1.74)
node2vec
(0,31)
25,37 (17.83)
29.90 (14.21)
4.27 (1.49)
(0.08)
2.40 (0.73)
3.76
1.38 (0.14)
VERSE
20,17 (0.16)
25.39 (11.43)
98.61 (40. 19)
(0.17
MILE
(5.48)
6,56 (2.79)
8.49 (2.36)
2.51 (0.66)
PAUSION
6.47 (0.07)
4.92
77.74 (49.35)
(1.24)
NRP
0.75 (0.06)
0.36 (0.20)
1.58 (0.63)
0.20 (0.19)
RandNE
0 (0.02)
0.48 (0.27)
(0.31)
(0.07)
ProNE
0.99 (0.03)
0.76 (0.51)
4,89 (2.65)
0,42
TIMERS
(2.94)
19.0664.66)
Metis
0.22
(0.46)
0.37 (0.11)
0.10
hMetis
2.22 (0.12)
0.42 (0.24)
2.60 (1:25)
0.32 (0.13)
GraClus
1.02
0.18 (0.05)
0.42 (0.15)
0.14
GrSAGE
0.21 (0.02)
(0.19)
1.29 (0.62)
0.17 (0.04)
GAT
0.21 (0.02)
(..1))
0.69 (0.30)
0.14 (0.03)
GIN
0.16 (0.01)
(.,10)
0.67 (0.29)
0.13 (0.03)
GAP
8.66 (2.59)
6,32 (4.48)
70.53 (45. 17)
3:20 (0.89)
ClusNet
19.10
(3.92)
49.93
(1.15)
IGP-M
0.43 (0.02)
0.29 (0)
2.37 (1.25)
0.21 (0.06)
Feat
0.24 (0.004)
0.007 (0.008)
1.12 (0.73)
0.03 (0.01)
Prop
0.003 (0.0001)
0.01 (0.009)
0.13 (0.05)
0,003 (0.001)
Clus
0.19 (0.02)
0.27 (0.
1.12 (0.48)
0.18 (0.05)
IGP-C
0.43 (0.02)
0.30 (4)
2.38 (1.28)
0.22 (0.06)
Feat
0.24 (0.005)
0.008 (0.009)
(0.75)
0.03 (0.01)
Prop
0.003 (0.0001)
0.01 (0.009)
0.13 (0.05)
0.003 (0.001)
Clus
0.19 (0.01)
0.28 (0.12)
1.10 (0.49)
0.19 (0.05)
since the value range of NMI or AC is Q E j0, quality. Furthermore, when modularity the quality metrie, the value range is [-1, 1), in which larger modularity indicates better quality. Hence, we derive the normalized metric as
1] and larger NMI or AC indicate better partitioning
@ =Q + 1)/2.
(16)
In contrast, smaller NCut metric implics better partitioning quality with value range Q E [0, +oo) Therefore, when using NCut the quality metric Q, we normalize it via
Q (Qm Q)/Q.n
(17)
24

---

Under review as a conference paper at ICLR 2022
TOS rea covered by the induced rectangle
E
Normalized NML AC, Modularity
Normalized Ncut
E
Normalized Runtime
Normalized Runtime
Figure 5: Rumning examples of the calculation of trade-off score (TOS).
Table 13: Trade-off scores (1) between NMI and runtime datasets with ground-trutie
GN.0.3
GV.0.5
M(60.3)
[450666
L0x.0.)
Lim.0.6)
SNMF
U
0
0,0315
0
DCSBM
0,2602
0.2206
0.2272
0.0216
0.0179
0
0,0402
0.7634
0,7887
0.7697
0.8219
0,2460
0.8184
0.1789
Walp
0.7194
0,8221
0.8299
0.8251
0,4833
0.8363
0,5075
node2vee
0,7213
0.7564
0.7444
0.7233
0.4455
0.7475
0,4882
LINE
0.4931
0.6001
0.7887
0.7562
0,4002
0.7454
0.3613
VERSE
0.2657
0.1691
0.1319
0.1134
0.0726
0.2123
0,1631
MILE
0.7712
0,7750
0.7720
0.8201
0,1718
0.8415
0.1818
PhUSION
0.6058
0,5047
0.4770
0.3197
0.1974
0.3301
0,2532
0.5472
RandNE
0.7561
0,8902
0.9363
0.5669
0,1823
0.5717
0.1859
ProNE
0,9031
0.9146
0,9157
0.8851
0.5282
0.8879
0,5500
Metis
0,8006
0,9362
0.9767
0.8423
0,4404
0.8479
0,4515
hMotis
0.7818
0,8833
0.9065
0,8506
0.3933
0.8567
0.4075
GraClos
0,9735
0.8996
0,5269
GraSAGE
0.4213
0,4435
0.4404
0.2307
0,1550
0.2419
0.1637
GAT
0,4382
0.4395
0.4488
0.2263
0,152
0.2547
0,1560
GIN
0,4288
0.4241
0.4239
0.1822
0.1313
0.1741
0.1330
GAP
0,5277
0,5894
0.6609
0.4551
0.2406
0.4924
0,2880
ClusNet
0.1149
0.1467
0.3887
0,2414
IGP-M
0.9225
0,9459
0.9526
0,9535
0,5461
0.9554
0.5526
Ranking
1
IGP-C
0,9457
0.9432
0.5075
Ranking
2
3
2
4
with Qm as the maximum NCut value through all the methods to be evaluated. For efficiency metric E (i.c.. runtime), smaller value of E indicates higher efficiency with value range E E [0, +oo), so we further normalize F. via
E E=m Em/
(18)
where En denotes the maximum runtime through all the methods to be evaluated. Finally, we define TOS with respect the given quality and efficiency metries (Q, E)) as the (normalized) area covered by the induced rectangle illustrated in Fig.51 Namely, we have
TOS(Q, = =
(19)
in which larger TOS implies better trade-off between quality and efficiency.
The TOS values with respect to the quality metrics of NMI, AC, modularity, and NCut are depicted in Table 13 Table 14 Table [5] and Table [6]] respectively. In our experiments, we saved model parameters of IGP with best metrics terms of NMI and modularity on validation sets of datasets with and without ground-truth, respectively. Namely, we used NMI and modularity as validation metrics for datasets with and without ground-truth. For TOS metrics with respect to NMI and modularity (see Table 13 and Table 15). both IGP-M and IGP-C have the best and second-best TOS values in most cases. indicating that IGP can achieve the best trade-off when using NMI and modularity the (validation) quality metrics. Furthermore, IGP-M and IGP-C can also achieve the top-5 TOS metrics with respect to AC and NCut on all the datasets. summary, IGP can achieve a better trade-off between quality and efficiency of the online GP over various baseline methods.
25

---

Under review as a conference paper at ICLR 2022
Table 14: Trade-off scores (1) between AC and runtime on datasets with fround-truth
GN:0.3
GN-0.4
GN--.5
1.50.3)
Lx70066)
Liv0.3)
L.m.0.63
SNMF
0
0
0
0.0275
DCSBM
0.1274
0,0988
0.1274
0.0106
0,0090
0.0192
SC
0.7616
0.7723
0.7616
0.7960
0.1789
0.8105
0,0890
Deep
0,8049
0.7846
0.8049
0.7777
0.4769
0.7852
0,4960
Bode2vee
0.7223
0.7307
0.7223
0.6843
0,4402
0.7062
0.4793
LINE
0.7250
0,4097
0.7250
0.6759
0.3583
0.6583
0.3133
VERSE
0.1157
0.1397
0.1157
0. 1059
0.0650
0.1972
0. 1459
MILE
0.7634
0.7573
0.7634
0.8091
0,0859
0.8277
0.0874
PhUSION
0.4628
0,4840
0,4628
0,3005
0.8888
0.3089
0,2405
NRP
0,7666
0.6850
0.7666
0.4147
0,2000
0.3750
0.1600
RandNE
0,9052
0.8191
0,9052
0,4000
0.1267
0.4000
0,1261
ProNE
0.9055
0.8974
0,9055
0.7830
0.4919
0.7824
0,5108
Metis
0.9690
0.9023
0,9690
0,5821
0.3475
0,5814
0.3507
hiMetis
0.8285
0.7950
0.8285
0.6378
0,3097
0.6343
0,3178
GraClus
0.9682
0,9439
0,9682
0.7151
0,4587
0.7139
0.4625
GmAAGE
0.0754
0.0739
0.0754
0,0740
0.0568
0.0743
0.0556
GAT
0.0896
0.0845
0.0896
0,0839
0.0611
0.0863
0.0561
GIN
0.0745
0.0736
0.0687
0.0601
0.0532
GAP
0.3537
0.2720
0.3537
0.4060
0,2037
0.4367
0,2405
ClusNet
0.0370
0.0244
0.0370
0.3740
0.2445
0.3940
0.3015
IGP-M
09442
0.9267
0,9442
0.9248
0.5217
0,9254
0.5227
Ranking
3
3
1
IGP-C
09439
0.9269
0,9439
0.9054
0.4614
0.9054
0.4643
Ranking
2
4
Table 15:
Trade-off scores (1) between modularity and runtime on all the datasets.
G/-0.3
GV--044
GN-0.3
(470.33
(4,0666
Ltn,0.3)
L(m.0.6)
Taxl
Reddlr
AS
baron
SNMF
0
0
0
0.0294
0.7769
0.3299
0.7970
DC'BB
0.1962
0.2091
0.1962
0.0263
0.0344
0
0,0770
0.6039
0.4919
0,43%
SC
0.5715
0,5505
0,5715
0.7003
0.4354
0.6979
0.4485
0.8115
0.8047
0.6608
0,8454
In:SNA
0,8175
0.5169
Walk
0.6173
0.5781
0.6173
0,7179
0.5809
0.7272
0.6031
0,4830
0.7902
0.6462
0.6271
node2ves
0.5536
0.5274
0.5536
0.6204
0.5068
0.6410
0.5488
0.0211
0.7477
0.6710
0.6972
LINE
0,5994
0,5065
0,5994
0.7302
0,5782
0.7241
0.5625
0,8267
0.7776
0.7113
0,7965
VERSE
0.1012
0,1283
0,1012
0,1013
0.1045
0.1894
0.2301
0.0212
0.6698
0.3805
0
MILE
0.5733
0,5395
0,5733
0.7268
0.5115
0.7446
0,5347
0,3770
0.7714
0.7504
0,7653
PLUSION
0.3547
0,3519
0,3547
0.2751
0.2457
0,2840
0,3056
0,5875
0.8194
0.4791
0.7338
NRP
0.6820
0.6310
0.6820
0.6098
0.5243
0.6048
0.5146
0.5107
0.5192
0.5189
0.4963
RandNE
0.7012
0.6416
0,7012
0.5825
0.5069
0.5831
0,5092
0.8578
0.5264
0.5245
0.5998
ProNE
0.6799
0.6349
0.6799
0,7633
0.6269
0.7659
0.6360
0.8256
0.8115
0,7270
0.7971
TIMERS
0.4739
Metis
0.7289
0.6686
0,7289
0,7556
0.6455
0.7564
U.6474
0.8431
0.7612
0.7623
0.8213
hMetis
0.6814
0.6337
0.6814
0.7540
0.6223
0.7566
0.6307
0.7717
0.7699
0.7699
0.8245
GraClus
0.7337
0.6815
0,7337
0.7625
0.6535
0.7626
0.6581
0,8215
0.7257
0.7325
0.8044
GraSAGE
0.4816
0.4825
0.4816
0.4914
0.4917
0.4931
0.4921
0.6030
0.5338
0.5250
0.5423
0.4892
0.4894
0,4892
0,4970
0.4917
0.4998
0,4929
0,5002
0.5426
0.5212
0.5175
GIN
0.4899
0,4903
0,4899
0,4953
0.4932
0.5177
0,5160
0,5362
0,5235
0.5263
0.5504
GAP
0,5426
0,5034
0,5426
0,4041
0.3381
0,4381
0.3988
0,4907
0.8014
0.5084
0.7383
ClusNet
0.4107
0.4157
0,4107
0,3581
0,2938
0.3759
0. 0,3625
0.0471
0,7531
0.5820
0.6574
IGP-M
0.7072
0.6576
0,7072
0,8154
0.6552
0.8172
0.6566
0,8514
0.8458
0.7747
0,8626
Ranking
IGP-C
0.7072
0.6570
0,7072
0,8104
0.6419
0.8120
0.6453
0,8516
0.8457
0.7676
0,8612
Ranking
3
2
4
2
3
2
C.5.3 ROBUSTNESS ANALYSIS
We further test the robustness of IGP across graphs using a more challenging setting of the LFR-Net. Different from the quantitative evaluation in Appendix C.5.I where fixed settings of (Je, kmax, Cuiincmma) and μ were used, we randomly set μ E 00.30.66, k E [10, 20), kmax E 200), Cain E [10, 20), Cmax E [100, 200). and N E [500, 10000] to independently gener- ate 1,000 graphs with GP ground-truth for the robustness analysis. In this case, the difference between synthetic graphs (in terms of their underlying distributions) is much larger than that in Appendix C We adopted the same experiment settings and evaluation protocols as in Ap- pendix C.5.I to compare the quality, efficiency, and trade-off between the two aspects of all the methods on this new dataset.
The robustness analysis results in terms of NMI, AC, modularity, NCut, runtime, and TOS val- ues between each quality metric (from the four metrics) and one efficiency metric are depicted in Table In most cases, IGP-M can achieve the best TOS values. The TOS values of IGP-C are also competitive to those of IGP-M. In summary, the robustness analysis results demonstrate that our
26

---

Under review as a conference paper at ICLR 2022
Table 16: Trade-off scores (1) between NCut and runtime on all the datasets.
GN-0.3
GN-D.4
GN-0.5
1450.3)
T,500.6)
Lun,0.3)
Ltn.0.6)
Taxi
Reddit
AS
Envon
SNMF
0
0
0
0.037673
0
0.8933
0.4300
0.9134
DCSBM
0,4637
0,3682
0.3278
0.0427
0.0617
0
0.1404
0.6949
0
0.4375
SC
0,8081
0.7978
0.7705
0,8362
0.6855
0.8326
0.7245
0,9332
0.9980
0.9231
0,9862
IocSNA
0,9504
0.2978
0.9862
DeepWalk
0.8627
0.8403
0.8337
0.8837
0.8657
0.8950
0.8983
0.5557
0.9465
0.8254
0.7117
node2vec
0,8137
0.7636
0.7477
0.7590
0.7521
0.7842
0.8140
0.0244
0.8826
0.8479
0.7865
LINE
0.9078
0.8682
0.8397
0.8665
0,8818
0.8777
0.8988
0,9499
0.8615
0.9561
0.9165
VERSE
0.4318
0.1991
0.1429
0.1261
0.1611
0,2358
0.3549
0.0012
0.7290
0.4994
0
MILE
0.8238
0.7805
0.7127
0,8728
0.8418
0.8935
0.8785
0.4358
0.8358
0.9562
0.8567
PhUSION
0.6437
0,5103
0,4792
0.3368
0.3636
0.3477
0,4553
0.6790
0.9719
0.6054
NRP
0.9134
0.9296
0,9354
0.9263
0.7819
0. 0,8899
0,8036
0
0.9039
0.8474
0.9173
RandNE
0.9234
0,9500
0,9498
0.9190
0.6348
0.9260
0.7317
0,9903
0.2610
0.4373
0,4796
ProNE:
0,9304
0.9175
0,9165
0,9471
0,9432
0.9503
0,9532
0,9505
0.9892
0.9742
0.9738
TIMERS
0.7980
Metis
0.9869
0,9877
0,9890
0.9906
0.9868
0.9917
0,9899
0,9882
0.9586
0.9968
0.9488
hMetis
0.9492
0.9401
0,9404
0,9554
0.9424
0.9596
0,9542
0,8893
0.9046
0.9835
0.9182
GraClus
0,9917
0.9913
0,9919
0,9920
0,9910
0,9932
0.9931
0,9487
0.6939
0.9964
0,9447
GrSSAG
0.0740
0
0
0,9799
0.0869
0.8882
0.2738
GAT
0.1082
0.5257
0,5742
0.4615
1426
0.3121
0.3755
0.2779
0.5514
0.6528
GIN
0,2875
0.2674
0,2883
0.2491
0.0695
0.2621
0,9712
0.1465
GAP
0,8617
0,8801
0,8880
0,4852
0.5076
0.5256
0,5991
0,5704
0.9704
0.6419
0,8414
ClusNet
0,7112
0.7178
0.5768
0.4289
0,4220
0.4508
0.5244
0.0543
0.9660
0.7448
0,7591
IGP-M
0.9502
0,9503
0,9529
0,9799
0,9719
0,9812
0.9769
0,9780
0.9980
0,9874
0,9889
Ranking
3
3
3
3
3
IGP-C
0,9546
0.9495
0.9529
0,9772
0,9717
0.9785
0.9765
0.9782
0.9980
0.9871
0,9883
Ranking
4
4
2
Table 17: Robustness analysis on LFR-Net with various parameter settings.
NMI
AC
Mod
NCut
Runtime
NVI
TOS
(4 Quality Metrie vs Kuutine)
AC
Mod
NCCt
SNMF
1517(2215)
(11.66)
(9.26)
73.46 (54.79)
221.8% (258.6) 69)
0.0213
0.0195
0.0186
0,0262
DCSBM
(1.97(10.50)
21.44
(5.00)
(1.0e4)
227.85 (261 93)
SC
(0.77(16.63)
(19.25)
(11.4()
(118.07)
11.81 (12.39)
0.8607
0.838
0.7029
0.9467
DW
49.73(1143)
(8.33
(6.76(9.93)
107.92 86)
16.40 (9:82)
0.8327
0.8151
0.6810
0.9263
N2V
92.72(9.68)
(8.24
(9.88
161.28 (443.88)
(24.57)
0.7589
0.6038
0.8162
LINE
56.32 64.32(21.41)
32.37 (25.18)
7,74c5
(9.c6699.55 (9.54e3)
10:70 (8.14)
0.6130
0.5368
0.6308
0,8276
VERSE
81.96 (1.39(11.88)
44.23 (9.30)
86.66 (77.58)
(51.15)
0.4909
0.4712
0.4146
0.5740
MILE
86. (14.70)
(12.98)
47.63 (10.60)
(883..588355
14.29 (10.74)
0.8108
0.8078
0.6919
0.9341
PAUSION
88.08 (1201
(10.99)
(9.94))
57.01 (48.21)
127.04
0.4027
0.3897
0.3258
0.4420
NRP
49.03 56.13(14.61)
16.68 (6.81)
5.50c3 (6. (6.40c3
3.21 (2.68)
0.5534
0.4242
0.5752
0.8937
RandNE
29.49 43.43()17.83)
8.34
1.1ce4 (1.54)4)
2,99 (2.51)
0.4286
0.291
0.5346
0.7838
ProNE
90.90(13.43)
(11.5))
(9.56
373.46 (1.39c3)
8.35 (6.53)
0,8757
0,8308
0.7050
0,9572
Metis
(4.77(1.39
(5.14
(6.34(
69.46 (48.30)
1.52 (0.94)
0.7427
0.6471
0.6970
0.9922
hMetis
78.53()4.62)
68.81 (12.20)
(9.17)
891.54 (3.10e3)
9.23 (6.57)
0.7535
0.6602
0.6869
0.9449
GraClus
88.70(9.76)
(7.70)
370.67 (7.30)
64c3)
0.78 (0.35)
0,8840
0.7833
0.6970
0.9903
GmSAGE
9.19 (6.38)
0.88 (1.35)
5.88c4 (4.94c4)
3.11 (2.52)
0.2306
0.0906
0.4975
0.0000
GAT
(4.55(
9.83 (4.78)
0.49 (0.96)
4,57e4 (3. 89c4)
2.98 (2.39)
0.2423
0.097
0.4959
0.2199
GIN
(5:411
8.31 (5.07)
1.04 (1.28)
5.12c4 (4.23c4)
2,55 (2.04)
0.1587
0.0822
0.4995
0.1278
GAP
86.70(11.10)
71.95 (9.78)
18.01
42.37 (34,88)
129.57 (112.81)
0.3740
0.31035
0,3192
0.4310
ClusNet
(7.84(9.23)
84.95 (7.70)
(10.4))
(415.82))
76.61 (51.80)
0.5831
0.5639
0.4910
0.6587
IGP-M
91.78 (2.99(1097)
(9.77
(643.66)
3.54 (2.95)
0.9097
0.9035
0.7320
0.9814
TOS Rank.
1
1
3
IGP-C
87.24(15.80)
(14.90)
47.46(11.07
171.9(544445)
3.96 (3.37)
0.8572
0.8607 2
0.7245
0.9797
TOS Rank.
5
2
IGP method is robust to the large distribution difference of graphs in the same system or scenario, while ensuring its ability to achieve significant trade-off between quality and efficiency.
C.5.4 CONVERGENCE ANALYSIS
We also analyzed the convergence of the offline training procedure of IGP (i.c., Algorithm B). In each epoch of the offline training on dataset, recorded the average partitioning quality (in terms of NMI, AC, modularity, and NCut) with respect to the learned embedding {U,} (i) on training set TT and validation set Tv (i.e., historical system snapshots). Moreover, we also evaluated the average partitioning quality of the generalized embedding (U.) on test set I' (i.e., new snapshots) in each epoch. To further validate the effectiveness of auxiliary label-induced embedding (U(2)). ).
27

---

Under review as a conference paper at ICLR 2022
|00000000000000000000000000
000000000000000000000
[UP) on training
(U() training set
on training set
0.8
[0, tminning
validation set
[U]] on
[0] on test set
0.6
0.4
0.4
10
20
30
40
50
10
20
30
40
50
Iterations
Iterations
(a) Convergence curves of average NMI
(b) Convergence curves of average AC
) training
on training set training
0.36
90
Madularity
NCut
0.34
80
on validation
on validation
0.32
on test set
(U) on test
40
50
Iterations
Iterations
(c) Convergence curves of average modularity
(d) Convergence curves of average NCut
Figure 6: Convergence curves of IGP-M on 6(n,,6) in terms of NMI, AC, modularity, and NCut.
(U()) training
on training set
0.8
[U] on training set
0.8
training set
[U]] on validation set
validation
NMI
0.6
[U]] test
UU)
0.4
0.2g
10
20
30
40
50
20
Iteaations
Iterations
(a) Convergence curves of average NMI
(b) Convergence curves of average AC
120
( on training set
0.35
110
training
Modularity lariity
100
training
U on Iraining set
90
0.25
on validtrrinn ses
80
(U,
validation
on test set
(U)
Iterations
Iterations
(c) Convergence curves of average modularity
(d) Convergence curves of average NCut
Figure Convergence curves of IGP-C on L(1,6) in terms of NMI, AC, modularity, and NCut.
the average partitioning quality of (U(+)) on training set was also recorded in each epoch during the offline training. Note that we do not need to derive (U( for Iv and l'
We evaluation records the challenging L(n, 0.6) dataset, whose clustering structures dif-
ficult to identify, as an example. The convergence curves (within the first 50 epochs) of the average
NMI, AC, modularity, and NCut with respect to (i) {U(") training set Pr, (ii) {U,} train- ing set Fr. (iii) {U,) on validation set Tv, and (iv) (U,) on test set for IGP-M and IGP-C are illustrated in Fig. and Fig. respectively.
28

---

Under review as a conference paper at ICLR 2022
Table 18: Detailed ablation study on L(f0.6).
NMT ())
AC (S)(()
Modularity (%))()
Neut
IGP-M
IGP-C
IGP-M
IGP-C
IGP-M
IGP-C
IGP-M
IGP-C
IGP
(2.33)
(2.79)
(2.57)
(2.68)
(0.14
(0.65)
(8.29)
84,99 (9.02)
w/o AL
(2.86
(3.29))
26.64 (2.59)
33.27
(0.80)
77.05 (7.33)
101.79
w/o FR
(1.80
(1.70
6.57 (0.34)
(0.55)
(1.38
5,73 (0.62)
6.90c2 (1.59e)
1.0223
W/o CR
(3.60((.06)
(3.25
(2.84)
(2.57
32.61 (0.72)
(0.76)
78.93 (7.19)
102.31 (8.70)
w/o Z,
(4.13(1.65)
(1.3)
5.71 (0.13)
(0,14)
0,24 (0.15)
(0.19)
2.62e4 (4.49c3)
(4.4233)
wib GNN
(0.20)
8.75 (0.55)
4.22 (0.15)
(0.15)
0.01 (0.01)
0.86 (0.23)
1.70c3 (4.99e2)
(7.443)
Table 19: Detailed ablation study on L(n0.66).
NMI(%)
AC (1)
Modularity (7)
NCui ())
IGP-M
IGP-
IGPM
IGP-C
IGP.
IGP-C
IGP.M
TGP-C
IGP
(2.08)
(2.5)
(2.04)
(2.59
(4.22(0.47)
(0.66
82.76 (8.97)
92.40 (10.05)
w/o
(2.53
(3.01
(2.41)
33.35 (2.11)
(0.70
(8.63)
2.08g4 (10.10(10.23)
w/o FR
(1.19
(1.66
6,28 (0.45
(.118)
(1.77
(.11
1.01c3 (237.60) 66)
w/o CR
(2.79)
(2.16
(2.73)
(0.71) (0.70) (2.50))
86.08 (8.71)
111.62
wlo Z₁
(1.59)
(02460 (1.38
5.57 (0.18)
1.27 (0.47)
0.28 (0.15
2.88c4 (4.766)
woo GNN
1.14(0.25)
8:45 (0.45)
(0.18)
4.78 (0.22)
0.01 (0.02)
(.33
(2.863)))
(7.9437
One can have similar observations in Fig. 6 and Fig. Concretely, the partitioning quality (in terms of NMI, AC, modularity, and NCut) of ( continuously improves in the first several epochs on the training, validation, and test set. More importantly, the average NMI and AC of {u!"} on training set Ir are always 1 in all the epochs for both IGP-M and IGP-C. It indicates that the partitioning results derived from the auxiliary label-induced embedding {U{*) have perfect map- ping the ground-truth. For both IGP-M and IGP-C, the average modularity and NCut of (U()) also keep at values that are much better than metrics of }U,} on the training, validation, and test set. The convergence curves with respect {U further verify that the introduced label-induced embedding (u can capture much more information regarding 'ground-truth' of the training set (i.e., historical system snapshots) than the learned embedding {U,}. which enables IGP to capture the permutation invariant label information during the offtine training. It also ensures the strong robustness of IGP beyond existing baselines.
In summary, the convergence curves in Fig. 6 and Fig. 7 validate the effectiveness of the offline training procedure and the dual GNN structure of IGP.
C.5.5 ABLATION STUDY
In addition example results shown in Table conducted additional ablation studies GN-0.3, L(f.0.6), and L(n,0.6), in which the clustering structures are more difficult to identify compared with other datasets. In each case of the ablation study (see Section 4.. the mean value μ and standard deviation a of all the quality metrics (on test set I') were recorded. The detailed ablation study results on L(f.0.6), L(n,0.6), and GN-0.3 (in the format (())) are illustrated in Table 18| Table 19. and Table 20 respectively.
Note that Table 20 Table 18, and Table 19 have consistent results. The FR loss, feature input Z,, and GNN are key components to ensure the high quality of IGP, because there are significant quality declines in cases without the three components. Moreover, the AL and CR losses are the components to further enhance the partitioning quality, as they can incorporate the permutation invariant label information of historical snapshots to the offline training of IGP.
D EXTENDED APPLICATIONS
D.1 MODEL SELECTION
As defined in Section 2 we assume that the number of clusters K is given in the downstream GP. For online GP in which K is not given, IGP also has the potential to estimate the K value for a given graph. As a demonstration, we applied XMeans. model selection method, to the derived embedding {U,} of both IGP-M and IGP-C to estimate K for each snapshot in the test sets of L(,,3), I(f,-6) [nn.3) and 1(n,.0) In the 4 datasets, ground-truth regarding the K value is
29

---

Under review as a conference paper at ICLR 2022
Table 20: Detailed ablation study GN-0.3.
NMT ())
AC (%I(1)
Modularity (8)())
NCut
IGP-M
IGP-C
IGP-M
IGP-C
IGP-M
IGP-C
IGP-M
IGP-C
IGP
(0.3))
95,50 (0.43)
(0.73
90.47 (0.85)
(0.92
345.82(19.15) (0.65)
354.95 (29.97)
wlo AL
95.00 (0.57)
(0.41)
89.75 (1.00
(0.98)
27.51 (0.25)
227.44(99.99)
363,44 (42.56)
Woo FR
(0.69)
72.47 (0.93)
16.87
(1.46)
7.27 (0.27)
(5.46)
1.95e4 (2.84c3)
(827.22
w/o CR
(0.45)
95.03 (0.41)
(0.8)
(0.86)
27.11 (0.26)
(0.24)
404.90
371.18 (83.18)
w/o Z,
(0.18)
(0.17)
7.34 (0.12)
7.73
0.03 (0.03)
0.03 (0.03)
1.68c5 (1.28c4)
1.65c5 (1.32e4)
wio GNN
30.08 (0.69)
56.25(1.28)
(0.50)
(1.66))
4.53 (0.19)
(0.32)
6.11e3 (646.84)
996.69 (439.41)
120
L.f..3):GroundTTT Truthh
L(f..3)IGP-M
LIf.3)1GP-C
100
#Clusters
80
60
LAf. Grouudd Truth
L(f.6):IGP-M
L(F.6):GP-C
40
60
100
120
140
160
180
200
Figure 8: Model selection results of IGP-M and IGP-C on the test set of Lff.0.)) and L(f.06).
given by the dataset and K' is non-fixed for multiple test graphs. With the increase of j., the clustering structures of L(f, (4) and L(n, μu) are increasingly difficult to identify. In particular, we use the same parameter settings and layer configurations with that in Table The range of K of XMeans for each dataset was set according to the maximum and minimum number of clusters as illustrated in Table The model selection results and ground-truth with respect to the test sets of L(J, (4) and L(n, pd) respectively.
depicted in Fig. and Fig 9
The model selection results in Fig. and Fig 9 are similar. When J 0.3 (with distinct clustering structures), the model selection results of both IGP-M and IGP-C fit well to ground on most test snapshots of L(f, 0.3) and L(n, 0.3). Note that the potential of model selection of IGP is still largely influenced by the intrinsic clustering structures of a dataset. The estimated K values are still far from ground-truth when μ 0.6 (with indistinct clustering structures) on 0(f,0.6) and L(n, 0.6). In summary, IGP has the potential to estimate the number of clusters K of newly generated graph snapshots with distinct clustering structures.
D.2 TRANSFERRING TEST
To test the potential of IGP to transfer from one (training) scenario to other different (generalization) scenarios, we consider a challenging application in which we first conduct offline training of IGP on completely synthetic graphs and directly generalize the trained model to the real datasets for fast online GP (without additional optimization).
In particular, we expect the synthetic graphs used for offline training cover various structural proper- ties of real-world network systems. We adopt LFR-Net (see Appendix C22 as the model to generate synthetic training graphs. In contrast the parameter settings of LFR-Net in our quantitative eval- uation (see Appendix C.2). we randomly set N E [500, 6000), k E [10, 100). kmax E [50, 200), Cuin E [5, 100), Cmax E [50, 400), and μ E [0.1, to independently generate 2, 000 synthetic snapshots, where we ensure that kinax k and Cmax > Crin for each snapshot.
In our experiments, we conducted offline training on the aforementioned synthetic snapshots and generalized the trained model to test sets of the four real datasets used in our quantitative evaluation (i.e.. Taxi, Reddit, AS, and Enron as introduced in Appendix C.2) We used the same layer configu- rations as in Table with respect to each real dataset and tried different parameter settings of IGP-M and IGP-C to report their best average quality. The recommended parameter settings of IGP-M and IGP-C are shown in Table 21 Evaluation results on test sets of the four real datasets (in terms of modularity and NCut) are depicted in Table 22 where 'Real' and 'Syn.' represent the results with respect to (i) training on training set of the original real datasets (same the results in Table g and
30

---

Under review as a conference paper at ICLR 2022
120
(lnn.3::Groud-TTuutt B- 31n.3)IGP-M
3YIPP
#Clusters
100
80
Ground Truth
LIM..))GGPMM
LO..GYIGP-C
40
60
100
120
160
180
200
Figure 9: Model selection results of IGP-M and IGP-C on the test set of L(n,0.3) and L(n,0.6).
Table 21: Parameter setting of IGP in the transferring test.
IGP-M
IGP-C
(a,, B, m. p)
(gG. nD)
(a, J.m.B.mp m.
(tc.. (D))
Taxi Reddir
II, 1000)
(Ie-4 lo-4)
(I,0.I, I, 1000)
(Ie-4, lc-4)
(1,0.1, 1000)
(Ic44 1o-4)
(1. 10,10,1 1. 1000)
(5-5,50-5)
AS Enron
0.1. 1000)
(Ie44 lc.4)
(1,5,1, 1000)
(Ie-4, le-4)
(1. 1. 1000)
(Ie-, Io-4)
(1,0.I, 1000)
5o-5)
Table T0 and (ii) training on the aforementioned synthetic snapshots, respectively. According to we have the following key observations.
Table 22
In some cases (e.g., on Taxi and Reddir), the quality metrics of training on synthetic graphs are close to those training on the original real datasets for both IGP-M and IGP-C, which are also competitive to the strong baselines as illustrated in Table X and Table 10) It preliminarily validates the potential IGP to be transferred from completely synthetic graphs to real datasets.
However, in other cases, there are still significant quality declines for both the variants of IGP, which indicate that the transferring capability of IGP is largely affected by the domain similarity between the synthetic training set and real test set. The negative transferring can be alleviated by carefully generating or selecting synthetic snapshots with the assistant of validation information from the target real datasets. We leave the study of this application in our future work.
Compared with IGP-C, IGP-M has better transferring quality metrics in most cases. The quality declines of IGP-C are also more significant than those of IGP-M. It further validates that the modularity matrix Q used in IGP-M is more informative than the normalized adjacency matrix M, used in IGP-C.
Note that IGP has similar motivations with SOTA pre-training methods for graphs, e.g., Pretrain- GNN (Hu et al. 2020) and GCC (Qiu et al. 2020). in which we pre-train a GNN-based model on historical graphs (in offline way) and generalize it to new snapshots. The major difference between IGP and SOTA pre-training methods is that a fine-tuming procedure with another optimiza- tion algorithm (based on a certain fine-tuning loss) on new test graphs required for most pre- training methods after the offline (pre-)training. In particular, the fine-tuning procedure may still be time-consuming for new test graphs, where several iterative optimization algorithms (e.g., gradient descent) are applied.
In this study, we focus on the NP-hard challenge of GP and try to achieve a better trade-off between quality and efficiency. To some extent, the proposed IGP framework sacrifices some opportunities to mune the (pre-)trame (traint model, which ensures the low runtime on new test graphs. our future research, we intend to consider promising application that pre-train high-quality GP model on completely synthetic graphs and fast fine-tune the praaiet model on new graphs (via some efficient fine-tuning strategies), with the guarantee of high partitioning quality and low runtime.
31

---

Under review as a conference paper at ICLR 2022
Table 22: Transferring test results on real datasets.
Modularity (7)
NCut (
Taxi
Enron 74.01 (0.51) 69. 38 (5.49) (2.82 ((3.5
Reuldi
AS
Tasi (0.12) (2.4) (126(1
Reddit
AS
Enron
Real
(16.94)
IGP-M
Syn.
74.04 (0.46) 69.31 (6.04) 54.71 (1796
(0.1) (.14(182) (1.4(1.21)
18.47 (98.84)
IGP-C
Real
74.00)
(5.47 55.4012.26) (11.7
(.77
(.715 (36663
4.3581 (16.50)
Syn.
73.78 (5.17) (1.00) (10.9)))))))
(..1) (2.35) 46.55 (56.27) 2,0651 (0.82)
E POSSIBLE FUTURE WORK
We summarize several promising future research directions as follows.
Further Reducing the Runtime, According to the results in Table IT and Table 12 the downstream clustering module (i.e., MMMans with 10 independent runs) consumes most of the runtime of IGP. Although replacing the clustering module with an FC output layer (trained in an E2E way) to directly output the partitioning results can further reduce the total runtime, the downstream clustering module is a key component enables IGP to tackle online GP with non-fixed K. In contrast, existing E2E GP methods still need to be trained from scratch for new graphs with non-fixed K. In our future research, we intend to further reduce the runtime of IGP by exploring a generic E2E scheme that can directly derive the GP results (e.g., via an output layer) and tackle the online GP with non-fixed K. One possible solution is to simultaneously train multiple output layers (with different output dimensionalityy to derive multiple partitioning results with respect to all the possible values of K. Another possible strategy is to output partitioning results in a hierarchical structure (that covers the results with respect to all the possible values of K) based on the idea of hierarchical clustering.
Dealing with Distribution Shifts. As discussed in Appendix D.2, our IGP framework has similar motivations with SOTA pre-training methods for graphs (Hu et al., 2020 Qiu et al. 2020). Namely, conduct the offline (pre-)training of inductive GNNs (regardless of time cost) but sacrifice some opportunities to fine-tune IGP on new test graphs for a better trade-off between quality and effi ciency of the online GP. The fine-tuning transferring by utilizing validation information from new targeted graphs. Moreover, to select the proper set of pre-training datasets is still an open issue in recent researches regarding the pre-training and fine-tuning scheme. In our future work, we intend to conduct the offline (pre- )training of IGP on completely synthetic graphs (that covers properties of various real network systems) and explore an efficient strategy to fine-tune the model on real new system snapshots (of other scenarios) with the guarantee of high partitioning quality and low runtime.
new graphs of targeted scenarios can avoid the negative
Scaling Up to Large Graphs.
Scaling GNNs up to graphs with large number of nodes is signifi- cant direction in recent researches, where several sampling strategies are used to split a large graph into multiple subgraphs (Chen et al. 2018 Huang et al. 20188] Zeng et al. 2020). i.e., mini-batches with small number of nodes. Note that IGP is an inductive framework across graphs, which can also be trained on and generalized to multiple subgraphs sampled from large graph (in terms of large number of nodes). Most of existing GNNs that can be scaled up to large graphs usually focus on (semi-) ssperviiue node-level tasks (e.g., node classification) with available node attributes, while we consider challenging inductive unsupervised node-level task (i.e., GP) across graphs without graph attributes in this study. In our future work, we intend to further explore efficient (i) feature extraction and (ii) subgraph sampling strategies for IGP on large graphs without available attributes. In particular, we can first split large graph into multiple small subgraphs via a sampling module features {X.} for each sampled graph. IGP can then be applied to
and extract the neigh-induced multiple sampled graphs and derive graph embedding {U.} with respect to each subgraph. One possible challenge in this application is to ensure the consistency of embeddings
(U,) of multiple subgraphs sampled from a common large graph (e-g., embeddings of all the subgraphs are mapped into a common latent space) without any auxiliary information given by the node attributes.
Theoretical Bound Analysis. Existing theoretical analysis regarding the combinatorial nature of GP Newman 2006 Von Luxburg 2007 is usually based on one single graph. However, we considered the GP across multiple graphs using the inductive nature of GNNs. The GP quality on a test graph is not only related to the expressive ability of inductive GNN, but also related to the similarity between the training and test graphs. To give strict theoretical bound analysis of IGP (c.g.. for modularity maxinization and NCut minimization) is also significant direction of in feature work.
32

---

Under review as a conference paper at ICLR 2022
We intend extend the theoretical analysis of GP on single graph to multiple associated graphs with the consideration of (i) expressive ability of GNNs and (ii) similarity between graphs in terms of their underlying distributions.
Application to Attributed Graphs. In this study, we considered inductive GP without attributes. Although GP is originally defined only based graph toplogy (e.g., NCut minimization and mod- ularity maximization), our IGP method can be easily extended to include node attributes by con- catenating the reduced neighbor-induced features Z, and the attribute matrix of attributed graph. However, prior research (Qin et al. 2018 Chunaev et al. 2020 Qin & Lei 202T) has demonstrated that there exist complicated correlations between graph topology and attributes. On the one hand, attributes may provide some complementary information beyond topology that can further improve the quality of some graph inference tasks including GP. On the other hand, attributes may also carry some noise and mismafched characteristics, which result in unexpected quality declines, e.g., in terms of modularity and NCut for GP. In our feature work, we intend consider an adaptive corporation scheme between these two heterogeneous sources for inductive GP. Concretely, when attributes carry consistent characteristics with topology, we can fully utilize attributes to improve the GP quality. In contrast, when topology 'mismatches' with attributes, need to control the contribution of attributes to avoid unexpected quality decline for GP.
33


Reviews:
[{"review_id": "zubHdq1uS-G", "reviewer": "Reviewer_7xoz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths of this paper are as follows.\n\n+ The problem consider is important and practical. Graph partitioning is an important pre-processing step in many applications. Moreover the model of being sampled i.i.d. has practical relevance and also considered in many prominent works in the graph networks literature.\n\n+ For the most part, the paper is written well, with detailed explanantion of the methodology and the results. The experiments are also exhaustive and sound. They considered an exhaustive list of baselines, and show that they perform nearly well or better than most methods on the range of tasks considered.\n\n+ They use publicly available datasets and the results can largely be reproduced.\n\nThe weakness of this paper is as follows.\n\n- The paper does not do a good job of crisply characterizing how their methods differ from prior works. The reasons why their method is better, that the authors state, seem somewhat shallow/arbitrary. They claim that computing gradients etc are expensive/time-consuming. Yet their method is based on adversarial auto-encoders, which need to be trained via gradient based optimization methods. So it seems like this is not a real difference. The only difference I can see is that, this paper considers a different NN architecture and training method compared to some of the other GNN based methods (e.g., Hamilton et al.,). I would like the author's to be a bit more precise and scientific & also credit prior works better.\n\n- Along the lines of (1) it is not entirely clear to me why this method works. Adding intuition about some of the choices would make it much better. At the moment it seems like, they created a new method, threw it at the datasets, and it happened to work. Some more principled study on why it works would greatly help the paper.\n\n- The paper does not report CIs in the experiment. Some of the points are so close to each other, that without CIs its unclear if its real improvement or just noise. This is important, since the thrust of the claims made by this paper is in the experiments, and having rigoros statistical analysis gives more confidence in the results.", "summary_of_the_paper": "This paper considers the problem of solving the graph partitioning problem repeatedly over many different graphs. Graphs are sampled i.i.d. from an unknown but fixed distribution and the goal of the algorithm is to solve the GP problem on each of the graphs. There are two quantities that are opposing; efficiency (on one hand we can solve an NP-hard problem each time but would be prohibitively time consuming) and quality (on the other hand we can generalize from the learnings on the other graph since they are related via the i.i.d. distribution). This paper proposes a NN architecture that uses a subset of the graphs in the family to learn an embedding, and then derives the solution to the other instances by using this embedding via a matrix multiplication. Using a number of simulated and real-world datasets they show that this method works well empirically.", "summary_of_the_review": "My main review is based on the weaknesses I stated above. I am not totally confident about the importance/merit of the approach provided in this paper. Thus, I am giving a weak reject. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ad25AMYQDSO", "reviewer": "Reviewer_r3jt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points:\n\nOverall, the paper is well written and the experimental part seems comprehensive. \n\nA few comments.\n\n1) Theorem 1 is stated in a very informal way. It seems not good to add discussion on one concrete example in Figure 2 in a statement of a theorem. I would suggest that please move that outside and discuss the potential meanings and implications of theorem 1 on examples separately. \n\n2) Figures 1 and 2 both are too small and it is hard to read details there.\n\n\n\n", "summary_of_the_paper": "The authors propose an inductive graph partitioning framework across multiple evolving graph snapshots to alleviate the NP-hard challenge. It first conducts the offline training of a dual graph neural network on historical snapshots to capture the structural properties of a system. The trained model is then generalized to newly generated snapshots for fast high-quality online GP without additional optimization, where a better trade-off between quality and efficiency is achieved. ", "summary_of_the_review": "The paper seems well written. Here are a few typos.\n\n1) The first line on the first paragraph of section 2: $S=...$, a comma is missing after the symbol $\\mathcal{G}_2$.\n\n2) On page 6, in the sentence just above equation (12), *we drive* should be *we derive*...\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YX68BTNzUpc", "reviewer": "Reviewer_BgbP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has various strong points, including an extensive experimental evaluation with numerous other baselines, \n\n- What is the advantage that the dual GNN offers over other choices in prior work (Pan et al. 2018, Nazi et al. 2019)?  \n\n- Under what conditions on the training dataset does the framework work well? Is it easy to test those conditions? E.g., from equation (11) that encodes a \"k-cut size\" it seems that you implicitly assume small changes from snapshot to snapshot?  Is this what you mean by saying that the graphs are snapshots of a given complex system?\n\n- Can you please elaborate on how the uncoarsening is done to get the actual community participation of the query graph G?\n \n- Having an axis with >T secs is not very informative for the proposed method. Can you please be more specific about the runtimes? \n\n- Can you test your method on communities with community groundtruth? \n\n- For the synthetic experiments using the stochastic blockmodel, it would have been nice to see a comparison with the paper  \"Supervised community detection with line graph neural networks\" by Chen et al. that provides state-of-the-art results.   \n\n", "summary_of_the_paper": "In this work the authors focus on an important problem, building an inductive framework for graph partitioning. This is a major problem with the potential of improving the performance of various classic transductive  algorithms for graph partitioning, both in terms of output quality, but also in terms of speed when a new snapshot  of a system needs to be partitioned into communities. This is a recent line of research, see, e.g., Nazi et al. 2019 \"GAP: Generalizable Approximate Graph Partitioning Framework\".  The proposed framework can address snapshots with differing number of nodes, by projecting them down to coarsened versions of the network. There are two versions of the framework, based on normalized cut and modularity objectives respectively. The framework can be potentially used with other measures as well. A nice idea is to leverage the unsupervised communities extracted from modularity optimization, or spectral algorithms through a dual GNN structure, that can then be used to partition fast unseen instances.  ", "summary_of_the_review": "The paper has various strong points, but the write-up can be improved. I found overall the paper hard to read; e.g., the choice of the dual GNN is not well justified (what issues is it resolving from GAP), reading the theorem 1 was kind of confusing, as the statement feels more as an observation derived from the definition of a partition etc.  I also found the term of permutation invariant for labels (0,1,1) vs (1,0,0) a bit confusing, as up to that point, I was expecting labels to be indicator vectors of which community a node participates in. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LOirJ0Vr08A", "reviewer": "Reviewer_njQS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- Performs graph partitioning on multiple graph snapshots while not requiring any form of correspondence of nodes between snapshots.\n- Proposed architecture includes a few novel elements.\n\nWeaknesses:\n\n- Presentation of results is extremely poor. Figure 3 is trying to show way too much! It took me several minutes of staring at the figure, zooming in and out, and examining multiple legends to understand what is being shown. Be selective in the results that you show in the main body, and provide the rest in the supplementary. Text in figures and tables is too small.\n- ~~Proposed problem setting specifically assumes that there is no node correspondence between snapshots, but then all of the real data experiments involve snapshots over time, which do have node correspondence. Methods that use node correspondence (e.g. incremental and evolutionary clustering) could possibly do better on these datasets.~~\n- No motivating application for the no node correspondence setting. Since there is no dataset targeting the proposed setting, a motivating application without data could also provide some justification as to why one should care about this setting. But no such application is present, so it feels more like the authors invented a problem to solve.\n- On real data sets, the number of clusters $K$ is not known, so the authors run the Louvain algorithm to choose $K$. But the Louvain algorithm also outputs a set of clusters, which appears to be discarded. ~~Furthermore, the computation time of the Louvain algorithm does not appear to be included, although I can't be sure because the presentation of the results is such a mess.~~\n\nTheorem 1 is trivial, and I'm not sure why it is highlighted as a theorem.\n\n*After discussion period:* I have added a strike through the incorrect portions of my review that have been clarified by the authors.", "summary_of_the_paper": "The authors consider the problem of inductive graph partitioning, which they formulate as clustering or partitioning multiple snapshots of a time-evolving graph for which we have no node correspondence. In other words, we cannot link the nodes in snapshot $t$ to those in snapshot $t-1$, which prevents incremental or evolutionary clustering algorithms from being applied. The propose a complicated dual graph neural network (GNN) architecture for this problem setting and demonstrate potentially good clustering accuracy with low computation time on simulated and real networks.", "summary_of_the_review": "The presentation of the results is extremely poor, making empirical results very hard to interpret. I also have concerns regarding the problem setting and evaluation, so I do not view this paper as ready for publication at this time.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L5FmdA0AwL", "reviewer": "Reviewer_CKG9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes an interesting framework which is resistant to permutations of the training set used by the IGP framework.  Specifically, the framework derives graph embeddings based on the input graph (as an adjacency matrix) and feature matrix which encodes neighbor similarity.  The embeddings are then used in the assignment of the node-disjoint cluster labels. \n\nThe ablation studies clearly show the effect of different aspects of the proposed architecture.\n\nThe reporting of the trade-off scores is slightly unclear.  What is the efficiency measure that is being traded-off?  Clarifying this in the main body of the results will make them clear.  Finally, there is literature - both in terms of discrete algorithms and learning representations - that addressed the problem of incremental partitioning of an evolving graph.  See, for example, https://rlgm.github.io/papers/41.pdf and https://www.vldb.org/pvldb/vol13/p1261-fan.pdf (and references within).  Comparison with the prior art in terms of the trade-off achievable will make the empirical analysis stronger. \n\nOther drawbacks of the work include the availability of training data that *already* computes an 'optimal' partition of a snapshot.  It's not clear how this can be achieved.  Secondly, the comparisons in the experiments are against other ML models whose performance cannot be verified in terms optimality loss, i.e., how far are those solutions from the optimal solution.   In this context, comparison to an algorithm with known approximation factors would help.", "summary_of_the_paper": "The authors propose an inductive graph partitioning (IGP) framework across multiple snapshots of a dynamic graph to produce an effective partitioning of the graph. IGP is based on training on the snapshots of the graph using a dual GNN architecture and is used to generalize to subsequent snapshots of the graph.  ", "summary_of_the_review": "I feel the paper in its current form can be significantly strengthened in terms of the presentation of the empirical results by clearly explaining the trade-off achieved as well comparing with more algorithms from the literature as baselines. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "F-uFrDEWNN", "reviewer": "Reviewer_FSan", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\nBoth the inductive graph partitioning problem which the paper attempts to solve and the dual GNN adversarial approach are interesting. The authors conduct comprehensive experiments and showcase the usefulness of their method. Even though there are a few notable limitations of the current work (which I will detail below), the authors explicitly state the assumptions and carry out a number of experiments that cover a reasonable range of inductive scenarios.\n\n**Weaknesses / Limitations**\n\n1. The paper does not provide a theoretical guarantee on the generalization to new unseen graphs. It would be nice if a guarantee on modularity or NCut is provided.\n\n2. The proposed framework does not work with attributed graphs. For graph partitioning this might be the usual setting, but the authors should comment on if incorporating node features could be helpful.\n\n3. The authors assume that the set of graphs, which includes both offline training and online testing graphs, follow similar distributions. This assumption easily breaks in practice for graphs that come from different domains. Table 21 in the appendix seems to indicate that, in general, the proposed inductive method may not generalize well due to distribution shifts. On the other hand, I appreciate the authors conduct additional transferring tests, even though the results are mixed, this is a plus since it provides the reader with additional information. For the experiments with LFR synthetic graphs in the main text, what would happen if we increase the range of N, e.g., from 500 to 10,000?\n\n4. The method requires knowing the number of ground-truth clusters K. It may not really be a limitation, as many graph partitioning methods also require K as a parameter.\n\n**Minor issues**\n\n1. In order for (1) and (2) to be equivalent, do we need to perform some rounding algorithm on an optimal solution H_t of (2)?\n\n2. Theorem 1 is trivial, it should be stated as a fact with detailed arguments left to the appendix.\n\n3. The font size in Figure 2 is too small. I cannot read it without zooming in on a screen.", "summary_of_the_paper": "This paper proposes an inductive GNN-based framework that partitions unattributed graphs with possibly different numbers of nodes and ground-truth clusters. Extensive empirical evaluations using both synthetic and real datasets demonstrate that the new method achieves a better trade-off between quality and efficiency when compared with 15 baselines from 4 categories.", "summary_of_the_review": "The paper proposes a new GNN-based framework for inductive graph partitioning. The authors conduct extensive experiments that cover a reasonable range of scenarios that showcase the usefulness of the proposed method. My concerns are (1) there is no generalization guarantee, and (2) the method may fail due to distribution shifts, as shown in the experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers an important problem, graph partitioning, from a transductive viewpoint: assuming that the graphs are generated by independent draws from an unknown distribution, learn some parameters in an ``offline” phase, and use these in the ``online” phase (much as in PAC learning). The authors have also answered many of the reviewer questions. In particular, the comparison with existing work is substantial. 

While I laud the positives of this work and the importance of the transductive approach, I see an issue: as a reviewer points out and as agreed by the authors, the paper does not provide a theoretical guarantee of the quality of the generalization to unseen graphs. It would have been useful, e.g., to consider this on Erdos-Renyi G(n,p) models, stochastic block models etc.
Decision: Reject