summaries: 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.

summaries: 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.

summaries: 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.

summaries: 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.

abstractText: 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 advanced machine learning techniques to obtain high-quality 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 a single graph, we propose an inductive graph partitioning (IGP) framework across multiple associated graphs of a system or scenario to alleviate the NP-hard challenge. IGP first conducts the offline training of a 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 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 over various state-of-the-art baselines.

title: Community detection and stochastic block models: recent developments

authors:
Vincent D Blondel
Jean-Loup Guillaume
Renaud Lambiotte
Etienne Lefebvre

title: Fast unfolding of communities in large networks. JSTAT

authors:
Jie Chen
Tengfei Ma
Cao Xiao

title: Fastgcn: fast learning with graph convolutional networks via importance sampling

venue: In Proc. of ICLR,

authors:
Petr Chunaev
Timofey Gradov
Klavdiya Bochenina

title: Community detection in node-attributed social networks: How structure-attributes correlation affects clustering quality

venue: Procedia Computer Science,

authors:
Peng Cui
Xiao Wang
Jian Pei
Wenwu Zhu

title: A survey on network embedding

venue: IEEE TKDE,

authors:
Lin Dai
Bo Bai

title: Optimal decomposition for large-scale infrastructure-based wireless networks

venue: IEEE TWC,

authors:
Inderjit S Dhillon
Yuqiang Guan
Brian Kulis

title: Weighted graph cuts without eigenvectors a multilevel approach

venue: IEEE TPAMI,

authors:
Michelle Girvan
Mark EJ Newman

title: Community structure in social and biological networks. PNAS

authors:
Aditya Grover
Jure Leskovec

title: node2vec: Scalable feature learning for networks

venue: In Proc. of ACM SIGKDD,

authors:
Will Hamilton
Zhitao Ying
Jure Leskovec

title: Inductive representation learning on large graphs

venue: In Proc. of NIPS,

authors:
Bruce Hendrickson
Robert W Leland

title: A multi-level algorithm for partitioning graphs

venue: Proceedings Supercomputing,

authors:
Weihua Hu
Bowen Liu
Joseph Gomes
Marinka Zitnik
Percy Liang
Vijay Pande
Jure Leskovec

title: Strategies for pre-training graph neural networks

authors:
Wenbing Huang
Tong Zhang
Yu Rong
Junzhou Huang

title: Adaptive sampling towards fast graph representation learning

authors:
Brian Karrer
Mark EJ Newman

title: Stochastic blockmodels and community structure in networks

venue: Physical Review E,

authors:
Andrea Lancichinetti
Santo Fortunato
Filippo Radicchi

title: Benchmark graphs for testing community detection algorithms

authors:
Jure Leskovec
Jon Kleinberg
Christos Faloutsos

title: Graphs over time: densification laws, shrinking diameters and possible explanations

authors:
Jiongqian Liang
Saket Gurukar
Srinivasan Parthasarathy

title: Mile: A multi-level framework for scalable graph embedding

venue: In Proc. of AAAI,

authors:
Azade Nazi
Will Hang
Anna Goldie
Sujith Ravi
Azalia Mirhoseini

title: Gap: Generalizable approximate graph partitioning framework

title: Modularity and community structure

venue: in networks. PNAS,

authors:
S Pan
R Hu
G Long
J Jiang
L Yao
C Zhang

title: Adversarially regularized graph autoencoder for graph embedding

venue: In Proc. of IJCAI,

authors:
Siddheshwar V Patil
Dinesh B Kulkarni

title: Graph partitioning using heuristic kernighan-lin algorithm for parallel computing

venue: In Next Generation Information Processing System,

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

authors:
Michal Piorkowski
Natasa Sarafijanovic
Matthias Grossglauser

title: A parsimonious model of mobile partitioned networks with clustering

venue: In Proc. of IEEE COMSNETS,

authors:
Meng Qin
Kai Lei

title: Dual-channel hybrid community detection in attributed networks

venue: Information Sciences,

authors:
Meng Qin
Di Jin
Kai Lei
Bogdan Gabrys
Katarzyna Musial-Gabrys

title: Adaptive community detection incorporating topology and content in social networks

venue: Knowledge-based systems,

authors:
Meng Qin
Kai Lei
Bo Bai
Gong Zhang

title: Towards a profiling view for unsupervised traffic classification by exploring the statistic features and link patterns

venue: In Proc. of ACM SIGCOMM Workshop on Network Meets AI & ML,

authors:
Jiezhong Qiu
Qibin Chen
Yuxiao Dong
Jing Zhang
Hongxia Yang
Ming Ding
Kuansan Wang
Jie Tang

title: Gcc: Graph contrastive coding for graph neural network pre-training

authors:
Ryan Rossi
Nesreen Ahmed

title: The network data repository with interactive graph analytics and visualization

authors:
Navaratnasothie Selvakkumaran
George Karypis

title: Multiobjective hypergraph-partitioning algorithms for cut and maximum subdomain-degree minimization

venue: IEEE TCAD,

authors:
Xing Su
Jianjun Cheng
Haijuan Yang
Mingwei Leng
Wenbo Zhang
Xiaoyun Chen

title: Incnsa: Detecting communities incrementally from time-evolving networks based on node similarity

venue: International Journal of Modern Physics C,

authors:
Jian Tang
Meng Qu
Mingzhe Wang
Ming Zhang
Jun Yan
Qiaozhu Mei

title: Line: Large-scale information network embedding

venue: In Proc. of WWW,

authors:
Anton Tsitsulin
Davide Mottin
Panagiotis Karras
Emmanuel Müller

title: Verse: Versatile graph embeddings from similarity measures

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio

title: Graph attention networks

title: A tutorial on spectral clustering

venue: Statistics & Computing,

authors:
Daixin Wang
Peng Cui
Wenwu Zhu

title: Structural deep network embedding

authors:
Fei Wang
Tao Li
Xin Wang
Shenghuo Zhu
Chris Ding

title: Community discovery using nonnegative matrix factorization

authors:
Klaus Wehrle
Mesut Günes
James Gross

title: Modeling and tools for network simulation

venue: Springer Science & Business Media,

authors:
Bryan Wilder
Eric Ewing
Bistra Dilkina
Milind Tambe

title: End to end learning and optimization on graphs

authors:
Keyulu Xu
Weihua Hu
Jure Leskovec
Stefanie Jegelka

title: How powerful are graph neural networks

authors:
Pinar Yanardag
SVN Vishwanathan

title: Deep graph kernels

authors:
Liang Yang
Xiaochun Cao
Dongxiao He
Chuan Wang
Xiao Wang
Weixiong Zhang

title: Modularity based community detection with deep learning

authors:
Renchi Yang
Jieming Shi
Xiaokui Xiao
Yin Yang
Sourav S. Bhowmick

title: Homogeneous network embedding for massive graphs via reweighted personalized pagerank

venue: VLDB Endow,

authors:
Hanqing Zeng
Hongkuan Zhou
Ajitesh Srivastava
Rajgopal Kannan
Viktor Prasanna

title: Graphsaint: Graph sampling based inductive learning method

authors:
Jie Zhang
Yuxiao Dong
Yan Wang
Jie Tang
Ming Ding

title: Prone: Fast and scalable network representation learning

authors:
Ziwei Zhang
Peng Cui
Haoyang Li
Xiao Wang
Wenwu Zhu

title: Billion-scale network embedding with iterative random projection

venue: In Proc. of ICDM,

authors:
Ziwei Zhang
Peng Cui
Jian Pei
Xiao Wang
Wenwu Zhu

title: Timers: Error-bounded svd restart on dynamic networks

authors:
Jing Zhu
Xingyu Lu
Mark Heimann
Danai Koutra

title: Node proximity is all you need: Unified structural and positional node and graph embedding

venue: In Proc. of SDM,

heading: 1 INTRODUCTION

text:
For various complex systems, e.g., communication networks, graph is a generic model to describe the entities and their relations using a set of nodes and edges. Graph partitioning (GP) is 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 a system, e.g., cells in wireless networks (Dai & Bai, 2017), many network applications are formulated as GP tasks (Qin et al., 2019; Patil & Kulkarni, 2021).
Mathematically, GP can be described as some NP-hard combinatorial optimization problems, e.g., modularity maximization (Newman, 2006) and normalized cut (NCut) minimization (Von Luxburg, 2007). Due to the NP-hardness, to balance the quality and efficiency of GP remains a challenge but some real applications have both requirements of high quality and low runtime, e.g., accurate GP on a 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 to 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 embedding emerges as a promising technique for GP in recent studies. These methods first learn lowdimensional node representations via random walk (Perozzi et al., 2014) or deep learning (Wang et al., 2016; Yang et al., 2016) to capture high-order proximities and nonlinear characteristics of a graph. The GP result is derived by feeding the learned embedding to a downstream clustering module (e.g, KMeans). 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 of some applications is another major focus. Some fast GP methods apply heuristic strategies to approximate conventional objectives, e.g., greedy modularity maximization (Blondel et al., 2008) and multi-level coarsening for graph-cut minimization (Dhillon et al., 2007). Several graph embedding approaches
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 independently optimize the model on 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 perspective across multiple associated graphs of a system or scenario. An inductive graph partitioning (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) independent (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 generalize 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-timeeffort only. Our focus is to achieve a better trade-off between quality and efficiency of online GP on new graphs after deploying the trained model to a 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 to new unseen nodes and graphs (Hamilton et al., 2017; Veličković 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 nodesN is non-fixed for multiple graphs. Although existing inductive GNNs can be applied to graphs with non-fixedN , 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., 2019)) to 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 can be assigned with different number of clusters K. Some inductive GNN based approaches adopt an end-to-end (E2E) framework to achieve a better approximation to 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 fullyconnected (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 time-consuming.
Although prior studies have demonstrated the ability of inductive GNNs to tackle (semi-)supervised tasks (e.g., node classification) on new unseen nodes and graphs (Hamilton et al., 2017; Veličković et 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 a better trade-off between quality and efficiency over conventional transductive 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 online GP with non-fixed N , we develop an efficient feature extraction module for inductive GNNs via graph coarsening. (ii) In contrast to 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 assignments (l1, l2, l3) = (1, 2, 2) and (l1, l2, l3) = (2, 1, 1) are the same in terms of GP with li as the
cluster label of node vi. 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 objectives (e.g., modularity maximization and NCut minimization) with a novel dual GNN structure which ensures strong robustness for the online GP on new graphs.

heading: 2 PROBLEM STATEMENTS AND PRELIMINARIES

text:
In this study, we consider GP on a set of graphs S = {G1,G2, · · · ,GT } from a common system or scenario. Each graph Gt ∈ S can be represented as Gt = (Vt, Et) with Vt = {vt1, . . . , vtNt} and Et = {(vti , vtj) ∣∣vti , vtj ∈ Vt } as the sets of nodes and edges. For each Gt, topology is the only available information source without graph attributes. We use an adjacency matrix At ∈ <Nt×Nt to describe its topology with Nt nodes, where (At)ij = (At)ji = 1 if (vti , v t j) ∈ Et and (At)ij = (At)ji = 0 otherwise. Since some systems allow addition and deletion of entities, we assume that different snapshots in S can have different node sets, i.e., ∃Gt,Gs ∈ S s.t. Vt 6= Vs. Since there may be no temporal dependency among {G1, · · · ,GT } in some cases (e.g., multiple ego-nets in social media), we do not consider the node correspondence among {V1, · · · ,VT }. 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 a common system or scenario.
Graph Partitioning. Given a graph Gt, GP aims to partition the node set Vt into Kt subsets (i.e., clusters) Ct = {Ct1, · · · , CtKt} so that (i) within each cluster the linkage is dense but (ii) between different clusters the linkage is relatively loose. The result Ct also satisfies Ctr ∩Cts = ∅ for ∀r 6= s. 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 Gt, NCut minimization aims to get the GP result Ct that minimizes the NCut metric:
arg minCt NCut(Ct) = 1
2 ∑Kt r=1 [cut(Ctr, C̄ t r)/vol(C t r)] (1)
where C̄tr = Vt − Ctr is the complementary set of Ctr; cut(Ctr, C̄tr) = ∑ vi∈Ctr,vj∈C̄tr
(At)ij is the cut between Ctr and C̄ t r; vol(C t r) = ∑ vi,vj∈Ctr (At)ij is the volume of C t r. The objective (1) can be equivalently expressed in the following matrix form:
arg minHt tr(H T t LtHt) s.t.H T t Ht = IKt , (2)
where Lt = INt − D−0.5t AtD−0.5t is the Laplacian matrix of At; Dt = diag(dt1, · · · , dtNt) is a diagonal matrix with dti = ∑ j (At)ij ; IN is anN -dimensional identity matrix. Ht ∈ <Nt×Kt is the membership indicator, where (Ht)ir = [dti · vol(Ctr)−1]0.5 if vti ∈ Ctr and (Ht)ir = 0 otherwise. Modularity maximization is another conventional NP-hard objective of GP. Given a graph Gt, it aims to find a partition Ct that maximizes the modularity metric:
arg minCt Mod(Ct) = 1
2e ∑ r ∑ vti ,v t j∈Ctr [(At)ij − d t id t j/(2e)], (3)
where e = ∑ i d t i/2 is the number of edges. The objective can also be rewritten in a matrix form:
argminHt − tr(HTt QtHt) s.t. tr(HTt Ht) = Nt, (4) where Qt ∈ <Nt×Nt is the modularity matrix with (Qt)ij = (At)ij − dtidtj/(2e). Ht ∈ <Nt×Kt is the membership indicator, where (Ht)ir = 1 if vti ∈ Ctr and (Ht)ir = 0 otherwise. Inductive Graph Embedding. Given a single graph Gt, conventional transductive graph embedding aims to learn a function f : {vti} 7→ {uti ∈ <1×k} that maps each node vti to a k-dimensional vector uti. The key characteristics of Gt (e.g., clustering structure) should be preserved in the embedding space, where a node pair (vti , v t j) with similar properties (e.g., in the same cluster) should have similar representations (uti,u t j) (e.g., with close distance in the embedding space). The learned representations {uti} are used as the input of several downstream tasks on Gt 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 a training set
Dual GNN Structure
Clustering
Module Model
Opt. (Param.
Fixed)Dual GNN Structure
Snapshots
New System
Historical GP Results
(e.g., ground-truth)
{ }t
{ } w.r.t. { }t tC
Historical System { }t    Snapshots
New GP Results
(a) Offline Training (b) Online fast
high-quality GP
' '{ }w.r.t.{ }t tC
Figure 1: IGP across multiple associated graphs.
1
2
3
4 5
6
7
8
Cluster 1 Cluster 2
1
2
3
4 5
6
7
8
Componet 1 Compoent 2
Feature Encoder
Aux. Label-
Induced Encoder
(Dual GNN w/ shared parameters)
{1, 2, 3, 4}
{5, 6, 7, 8}
Original Graph t
Aux. Label-Ind. Graph
Supergraph *
t
( )g t
(HEM Graph Coarsening)
Adjacency Matrix At
Red. Feat. Zt
Aux. Label-Ind. Adj. Matrix ( )g
tA
Emb. Ut
Aux. LabelInd. Emb. ( )g
tU
FC
Classifier
Discriminator
Generator
In n er
P ro d u ct
In Label-Ind. Encoder,
message passing only
occurs in each component
?tU
( )?gtU (i) Adv. Learning Obj.
Reconstru cted Feat. tX
(ii) Feature
Reconstruction Obj.
Neigh-Ind. Feature Xt
(min error)
(Regularizing)
GP Result Ct (ground-truth) of
t
(iii) Clustering
Reg. Obj.
1
2
3
4 5
6
7
8
1
2
3
4 5
6
7
8
In Feature Encoder,
message passing occurs in
the original topology
G
D
Figure 2: A running example of the offline training of our dual GNN structure.
Γ ⊂ S and a test set Γ′ = S − Γ, which represent the sets of historical known and newly generated graphs. We first train f on Γ in an offline way to fully capture structural properties of historical graphs. Although graph embedding and GP are unsupervised procedures, we assume the permutation invariant GP result Ct (i.e., label information) of each historical graph Gt ∈ Γ is available in the offline training, which can be used to enhance the offline embedding optimization. In general, the training label information {Ct|Gt ∈ Γ} 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 {ut′i } from f for each new graph Gt′ ∈ Γ′ with model parameters fixed. The online GP on a new graph Gt′ is the downstream task, where we assume the number of clusters Kt′ is given. The GP result of Gt′ is derived by applying a clustering algorithm (e.g., KMeans) to {ut ′ i }.

heading: 3 METHODOLOGY

text:
We propose an IGP framework with the overview shown in Fig. 1, including the (i) offline training of a dual GNN structure on historical graphs and (ii) online generalization to new graphs via an inductive graph embedding scheme. Fig. 2 gives 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 et 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 {Gt ∈ Γ} to the learned embedding via (i) a parameter sharing strategy and (ii) an adversarial process between {Gt} and auxiliary label-induced graphs {G(g)t }. Concretely, in the offline training, we assume the topology and GP result (used as the ‘ground-truth’) of each historical graph Gt are available, which are described by an adjacency matrix At ∈ <Nt×Nt and an indicator matrix Rt ∈ <Nt×Kt . We define (Rt)ir = 1 if node vti is in cluster Ctr by the ‘ground-truth’ and (Rt)ir = 0 otherwise. Due to the disjoint constraint of GP, only one entry in each row of Rt is 1 with other entries in the same row set to 0. In addition to the original graph Gt, an auxiliary label-induced graph G(g)t , with A (g) t = RtR T 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 Gt with Kt clusters, its auxiliary label-induced graph G(g)t has Kt fully connected components with each component corresponding to one unique cluster of Gt. Namely, there is an edge between nodes vti and v t j in G (g) t 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, 2, · · · , 8}, G(g)t has 2 fully connected components {1, 2, 3, 4} and {5, 6, 7, 8} w.r.t. the 2 clusters in the GP result (i.e., ‘ground-truth’) of Gt. The generator G includes a feature encoder and a label-induced encoder, forming a dual GNN structure with shared parameters δG. The feature encoder takes At and a feature matrix Xt as inputs, and derives graph embedding Ut, i.e., Ut = G(At,Xt; δG). The label-induced encoder takes A(g)t and Xt as inputs, and outputs auxiliary embedding U (g) t , i.e., U (g) t = G(A (g) t ,Xt; δG).
GNN is originally designed for attributed graphs, where each node vti must have a feature vector described by the i-th row of a feature matrix Xt. In this study, we consider GP without node attributes. Instead of using conventional settings of GNN for graphs without attributes (e.g., use a constant matrix for the input features), we extract additional structural feature Xt based on the neighbor similarity encoded in At. 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 as two examples, corresponding to two settings of Xt. For modularity maximization in (4), the modularity matrix Qt encodes the reweighted neighbor similarity based on At, so we let Xt = Qt. For NCut minimization in (2), the Laplacian matrix Lt gives the primary characteristics of graph structure, where Mt = D−0.5t AtD −0.5 t is the key component regarding neighbor similarity. Hence, we let Xt = Mt. Both Qt and Mt are the reweighting of At, where the pair of nodes (vti , v t j) with similar neighbor-induced features ((Xt)i,:, (Xt)j,:) are more likely to be partitioned into the same cluster. Our experiments further demonstrate that the extraction of Xt is essential to ensuring the high GP quality of IGP.
However, the feature dimensionality of Xt is Nt (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 Xt ∈ <Nt×Nt to a matrix Zt ∈ <Nt×L with fixed dimensionality L. For Nt > L, we extract reweighted edges E(w)t = {w(vti , vtj)|w(vti , vtj) = (Xt)ij , (At)ij = 1} and apply HEM to E(w)t . It merges the original graph Gt with Nt nodes into a supergraph G∗t with L supernodes via a greedy strategy of continuously merging the node pair with largest weight in E(w)t into a supernode, e.g., merging a graph with 8 nodes into 2 supernodes in Fig. 2. HEM outputs a coarsening matrix Ct ∈ <Nt×L, where (Ct)ij = |vt∗j |−0.5 if node vti is merged into supernode vt∗j and (Ct)ij = 0 otherwise. We then let Zt = XtCt be the reduced features. Since Ct is a sparse matrix, one can obtain Zt by setting its j-th column to (Zt):,j =∑ vi∈vt∗j
(Ct)ij(Xt):,i. ForNt < L, we let Zt = [Xt,0Nt×(L−Nt)]. In contrast to existing methods using HEM to reduce topology complexities (Dhillon et al., 2007), we are the first to extract feature input Zt for inductive GNNs (with non-fixed Nt) via HEM. It is more efficient than dimensionality reduction (e.g., PCA of At) in SOTA GNNs (Nazi et al., 2019), since HEM is widely used in fast GP methods (Liang et al., 2021). The derived Zt is also more informative than the input features in some classic settings of inductive GNNs (e.g., let Zt be a constant matrix (Xu et al., 2019)).
Let F(l−1)t and F (l) t be the input and output of the l-th layer of feature encoder or label-induced encoder in G with F(0)t = Zt. The l-th GNN encoder layer is defined as
F (l) t = tanh(D̂ −0.5 t ÂtD̂ −0.5 t F (l−1) t W (l−1) G ), (5)
where Ât = A′t + INt (A ′ t ∈ {At,A(g)t }) is the adjacency matrix with self-edges; D̂t = diag(d̂t1, · · · , d̂tNt) is the diagonal degree matrix; W (l−1) G is the trainable parameter matrix shared by the two encoders; (F(l)t )i,: is the latent feature vector of node v t i . In (5), (F (l) t )i,: is the nonlinear aggregation of the features of {vti} ∪ n(vti) in the previous layer, where n(vti) is the neighbor set of vti . It is also known as the message passing of GNN, where neighbors of v t i propagate their features to vti for aggregation. By Fact 1, A (g) t ensures that message passing of the label-induced encoder only occurs in each connected component w.r.t. 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 topology of Gt. The last layers of the feature and label-induced encoders output the graph embedding Ut ∈ <Nt×k and auxiliary label-induced embedding U(g)t ∈ <Nt×k, where U (g) t = G(A (g) t ,Xt) preserves more informative label-induced properties than Ut = G(At,Xt). We further use the non-linear inner product of Ut to reconstruct the neighbor-induced features Xt:
X̃t = tanh(UtUTt ). (6)
The discriminator D is an auxiliary classifier to distinguish U(g)t from Ut, while the generator G tries to generate plausible embedding Ut to fool D. Such an adversarial process helps G to generate embedding Ut close to U (g) t . We denote D as yt = D(St; δD), where St ∈ {Ut,U (g) t } and δD are the input and set of model parameters; yt ∈ <Nt is a column vector with (yt)i as the probability that (St)i,: = (U (g) t )i,: rather than (St)i,: = (Ut)i,:. Let P (l−1) t and P (l) t be the input and output of
the l-th layer in D with P(0)t = St. The l-th layer of D is defined as
P (l) t = ReLU(P (l−1) t W (l−1) D + b (l−1) D ), (7)
where {W(l−1)D ,b (l−1) D } are trainable model parameters. In particular, we use sigmoid as the activation function of the last layer instead of ReLU.
Model Optimization. As in Fig. 2, the offline training of IGP is based on three objectives: (i) 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 to distinguish U(g)t from Ut. The objective of D w.r.t. a graph Gt is
arg minδDLD(Gt) = − [∑
i log(1−D(Ut)i) + ∑ i logD(U (g) t )i ] /Nt. (8)
On the other hand, G tries to fool D by minimizing the following loss w.r.t. Gt: LAL(Gt) = − [∑
i logD(Ut)i
] /Nt. (9)
Such an adversarial process directsG to output the embedding Ut that is close to U (g) t , thus enabling G to capture the permutation invariant label information of historical training graphs.
The FR loss forces G to derive the embedding Ut that encodes the key properties of the neighborinduced features Xt w.r.t. Gt by minimizing the reconstruction error between Xt and X̃t:
LFR(Gt) = ||X̃t −Xt||2F . (10) In addition to 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 a graph Gt that minimizes the following loss:
LCR(Gt) = −tr(HTt X̃tHt), (11) where Ht is the membership indicator encoding the ‘ground-truth’ with the same definitions in (4) and (2). Since the constraints on Ht, e.g., tr(HTt Ht) = Nt and H T t Ht = IKt , are always satisfied for the given ‘ground-truth’, we do not need to consider the discrete constraints on Ht. To the best of our knowledge, we are the first to use the CR objective to incorporate the permutation invariant label information (encoded by Ht of historical training data) to the unsupervised embedding learning, whereas Ht 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. Gt by combining (9), (10), and (11): arg min δGLG(Gt) = LAL(Gt) + αLFR(Gt) + βLCR(Gt), (12)
where {α, β} are hyper-parameters to balance LFR and LCR. In the joint offline optimization ofD andG, we use the Xavier method to initialize model parameters {δD, δG}. The Adam optimizer is applied to iteratively update δD and δG based on the gradients of loss (8) and (12). In each epoch, we randomly sample a certain number of historical graphs p from the training set to update {δD, δG}. Finally, we save the model parameters {δ∗D, δ∗G} that result in the best average GP quality on the validation set within a certain number of epochs n.
After offline training, we generalize IGP to new graphs for fast online GP. As in Fig. 1, for each new graph Gt′ , we derive its embedding Ut′ by passing {At′ ,Xt′} forward the feature encoder of G with its parameters δG fixed. As we assume that the number of clusters Kt′ is given, we apply KMeans to Ut′ , which outputs the GP result w.r.t. the given Kt′ . Therefore, the runtime of online GP on Gt′ includes (i) the feature extraction of Zt, (ii) one feedforward propagation through the feature encoder, and (iii) the downstream clustering. Due to the space limit, we conclude the offline training and online generalization procedures of IGP in Appendix B.

heading: 4 EXPERIMENTS

text:
Datasets. We evaluate IGP on 2 synthetic benchmarks (with 7 settings) and 4 real datasets. Statistics of the datasets are depicted in Table 1, where T , N , |E|, and K are the number of graphs, nodes,
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-Net (Girvan & Newman, 2002) and LFRNet (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 pin and µ to control clustering structures of each graph. We denote the GN-Net with a setting of pin as GN-pin (pin ∈ {0.5, 0.4, 0.3}). The 3 datasets of GN-Net are with fixed N and K. We use L(c, µ) (c ∈ {f, n}, µ ∈ {0.3, 0.6}) to represent the LFR-Net with a setting of µ, where f and n denote cases with fixed and non-fixed N . As pin decreases and µ increases, the clustering structures become increasingly difficult to identify. Taxi (Piorkowski et al., 2009), Reddit (Yanardag & Vishwanathan, 2015), Enron (Rossi & Ahmed, 2015), and AS (Leskovec et al., 2005) are real datasets from a vehicle network, an email network, a social network, and an autonomous system. As the 4 real datasets do not provide ground-truth regardingK, to ensure the fairness of comparison, where each graph is with a common K for all the methods to be evaluated, we adopted a 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 C.2.
Baselines. We compared IGP over 15 baselines with 4 categories. (i) SNMF (Wang et al., 2011) and spectral clustering (SC) (Von Luxburg, 2007) are classic transductive GP methods. (ii) VERSE (Tsitsulin et al., 2018), MILE (Liang et al., 2021), and PhUSION (PhN) (Zhu et 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. (iii) Metis (Hendrickson & Leland, 1995), hMetis (Selvakkumaran & Karypis, 2006), and GraClus (Dhillon et al., 2007) are fast transductive GP baselines with heuristic approximation. (iv) GraSAGE (GSAGE) (Hamilton et al., 2017) and GAT (Veličković et al., 2018) are SOTA inductive GNNs, while GAP (Nazi et al., 2019) and ClusNet (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 (3) and (1). On datasets with 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 groundtruth. 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 illustrate such superiority of IGP beyond transductive baselines, for each dataset, we used the first 80% of the graphs as the training set ΓT with the remaining 10% and 10% deployed as the validation set ΓV and test set Γ′. In this setting, ΓT ∪ ΓV and Γ′ represent the sets of historical and newly generated graphs, respectively. We conducted the offline training of IGP on ΓT and generalized it to Γ′ for online GP. In the offline training, we save the model parameters of IGP with the best average quality on Γ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 Γ′, where we had to apply transductive baselines to each test graph in Γ′ 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.e., offline training on ΓT and online generalization to Γ′. Since we consider GP on graphs without attributes, we use a constant matrix 1Nt×L (with fixed feature dimensionality L), where each entry is set to 1, 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 ΓT, since most existing inductive GNNs (even with a supervised loss like crossentropy) cannot directly integrate the permutation invariant label information from ΓT.
Table 1: Statistics of the datasets.
T N |E| K
GN-0.5 2,000 5,000 48,065-49,314 250 GN-0.4 2,000 5,000 48,335-49,698 250 GN-0.3 2,000 5,000 48,488-49,981 250 L(f,0.3) 2,000 5,000 22,539-25,707 57-104 L(f,0.6) 2,000 5,000 22,585-25,639 58 - 107 L(n,0.3) 2,000 5,000-5,999 22,999-29,670 59-117 L(n,0.6) 2,000 5,000-6,000 22,680-29,931 61-118 Taxi 3,000 1,279 38,554-40,171 7-12 Reddit 1,870 501-3,648 525-4,780 14-121 Enron 410 502-3,261 554-5,097 10-31 AS 733 103-6,474 487-26,467 7-39
Table 2: Ablation study on L(n,.6).
NMI(%↑) AC(%↑) Mod(%↑) Ncut(↓)
IGP-M 56.48 53.42 34.22 82.76 w/o AL 52.13 49.30 33.35 84.05 w/o FR 11.19 6.28 10.08 1.01e3 w/o CR 49.97 46.70 32.70 86.08 w/o Zt 16.39 6.14 1.27 3.01e4 w/o GNN 1.14 3.92 0.01 1.08e4 IGP-C 52.71 47.47 31.95 92.40 w/o AL 35.12 26.15 26.70 113.10 w/o FR 15.46 5.46 0.45 2.08e4 w/o CR 35.16 26.22 26.78 111.62 w/o Zt 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 ClusNet), we could only conduct the offline training and fast online generalization on datasets with fixed K (i.e., on GN-Net), but we had to train them from scratch on the test set of other datasets with non-fixedK, 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 {At} 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-based methods (including the transductive embedding baselines, inductive GNNs, and IGP), we usedKMeans as the downstream clustering module. We ranKMeans 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 ClusNet), we directly derived the GP results from their outputs. Since Taxi, Reddit, Enron, and AS do not provide the GP ground-truth (in terms of the membership Ct) on each historical training snapshot of these datasets, we used the GP result of the baseline with best average modularity on ΓV to derive the membership indicator Ht for IGP, which is the second source of historical label information defined in Section 2. Note that we do not need to derive Ht in the evaluation phase when generalizing the trained model to test set Γ′.
We tuned parameters of all the methods on ΓV of each dataset to report best quality metrics. Both the mean and standard deviation of all the quality and efficiency metrics on Γ′ 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. In 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 Γ′, where other transductive baselines were fully trained. Surprisingly, IGP even has the best or 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 NP-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 Zt, and (v) GNN by respectively excluding the corresponding components from the original model. In case (iv), we used a constant matrix 1Nt×L with all entries set to 1 to replace Zt while we use an FC network that only takes Zt 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 2. According to Table 2, the FR loss, Zt, 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 applications. First, when the number of clusters K of a new graph is not given, IGP also has the potential
(j) AS (k) Enron
to estimate K, where we apply an auxiliary model selection method (e.g., XMeans) to the derived embedding Ut. Second, in contrast to 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 it to real datasets. The two extended applications are elaborated in Appendix D.

heading: 5 CONCLUSION

text: In this paper, we proposed a novel IGP framework to alleviate the NP-hard challenge of GP, obtaining 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 generated graphs for fast high-quality online GP. IGP is a 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 structure. Since we introduced an inductive graph embedding scheme and an efficient feature extraction module, IGP can also tackle online GP on 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.

heading: A PROOF OF FACT 1

text:
By the disjoint constraint of GP, i.e., Ctr ∩ Cts = ∅ for ∀r 6= s, each node can only belong to one unique cluster. For the membership indicator matrix Rt, only one entry in each row of Rt must be 1 with the rest entries in the same row set to 0. For the auxiliary adjacency matrix A(g)t = RtR T t ,
consider each entry (A(g)t )ij = ∑Kt r=1 [(Rt)ir(Rt)jr] with respect to the pair of nodes (v t i , v t j).
If nodes (vti , v t j) are in the same cluster C t s, i.e., v t i , v t j ∈ Cts, we have Ris = Rjs = 1. We can further derive (A(g)t )ij = (Rt)is(Rt)js = 1. It indicates that there is an edge between (v t i , v t j) with weight 1, when they are in the same cluster.
If nodes (vti , v t j) are not in the same cluster, i.e., v t i ∈ Ctr and vtj ∈ Cts (r 6= s), we have Rir = 1 and Rjs = 1, but (A (g) t )ij = 0. Namely, there is no edge between nodes (v t i , v t j) when they are in different clusters.
In summary, there is an edge between (vti , v t j) in the auxiliary label-induced graph G (g) t only if they are partitioned into the same cluster according to the given partitioning result Ct = {Ct1, · · · , CtKt} (used as the ‘ground-truth’). Especially, each node vti ∈ Ctr (i) must have edges connected to all the other nodes in the same cluster Ctr and (ii) do not have edges connected to nodes in different clusters Cts (r 6= s), thus forming a fully connected component with respect to cluster Ctr. Hence, for a graph Gt with Kt clusters, its corresponding auxiliary label-induced graph G(g)t has Kt fully connected components, with each component corresponding to one unique cluster of Gt.

heading: B DETAILED ALGORITHMS OF IGP

text:
In contrast to conventional transductive GP methods applied to a single static graph, IGP is an inductive framework that explores the structure properties across a set of graphs S = {G1, · · · ,GT }. In IGP, we first train a 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 a training set ΓT, a validation set ΓV, and a test set Γ′, where ΓT ∪ ΓV and Γ′ represent the set of historical and newly generated system snapshots, respectively. Namely, snapshots in ΓT ∪ ΓV should occur before those in Γ′.
Algorithm 1: HEM Graph Coarsening Input: input graph Gt; neighbor-induced features Xt; number of nodes Nt; reduced dimensionality L Output: coarsening matrix Ct
1 extract the node set V(0)t and reweighted edges E (w) t from Gt and Xt 2 E(0)t ← E (w) t //Initialize the edge set of the 1st coarsening level 3 k ← 0 //Initialize the level index 4 N ′t ← |V (0) t | //Initialize the number of (super)nodes 5 while N ′t > L do 6 V(k+1)t ← ∅ //Initialize the node set of next level 7 E(k+1)t ← ∅ //Initialize the edge set of next level 8 sort E(k)t based on weights in descending order 9 arrange the sorted result as a queue q(E(k)t )
10 while q(E(k)t ) 6= ∅ do 11 pop (v(k)i , v (k) j ) from q(E (k) t ) 12 if v(k)i ∈ V (k) t and v (k) j ∈ V (k) t then 13 delete v(k)i and v (k) j from V (k) t 14 merge v(k)i and v (k) j into supernode v (k+1) l 15 add v(k+1)l to V (k+1) t 16 adjust E(k)t and E (k+1) t w.r.t. V (k) t and V (k+1) t 17 N ′t ← N ′t − 1 //Update the number of supernodes 18 if N ′t = L then 19 V(k+1)t ← V (k+1) t ∪ V (k) t 20 return Ct based on the merging membership of V(k+1)t
21 V(k+1)t ← V (k+1) t ∪ V (k) t 22 E(k+1)t ← E (k+1) t ∪ E (k) t 23 k ← k + 1 //Update the level index k
24 return Ct based on the merging membership of V(k)t

heading: B.1 FEATURE EXTRACTION

text:
For a set of graph snapshots S = {G1, . . .GT } with non-fixed node set {V1, . . . ,VT } (i.e., with non-fixed number of nodes Nt), we introduce an efficient feature extraction strategy via HEM graph coarsening, which maps the neighbor-induced feature Xt ∈ <Nt×Nt (Xt = Qt or Xt = Mt) to a reduced feature matrix Zt ∈ <Nt×L with fixed dimensionality L. Algorithm 1 and Algorithm 2 summarize the procedures of HEM graph coarsening and the feature extraction module.
For each graph Gt ∈ S, if L < Nt, Algorithm 1 first merges Gt into a supergraph G∗t (with L supernodes) based on reweighted edges E(w)t = {w(vti , vtj)|w(vti , vtj) = (Xt)ij , (At)ij = 1} and outputs a coarsening matrix Ct ∈ <Nt×L that describes the merging membership. Concretely, (Ct)ij = |vt∗j |−0.5 if node vti is merged into supernode vt∗j (i.e., vti ∈ vt∗j ) and (Ct)ij = 0, otherwise. Based on Ct given by Algorithm 1, Algorithm 2 further derives a reduced feature matrix Zt via Zt = XtCt. By the sparsity of Ct, we can set its j-th column to (Zt):,j = ∑ vi∈vt∗j
(Ct)ij(Xt):,i. In contrast, when L > Nt, Algorithm 2 directly derives Zt = [Xt,0Nt×(L−Nt)] via a simple padding strategy.

heading: B.2 OFFLINE TRAINING ON HISTORICAL SYSTEM SNAPSHOTS

text:
In the offline training of IGP, we assume that the partitioning result Ct = {Ct1, · · · , CtKt} (i.e., ‘ground-truth’) of each historical graph Gt ∈ ΓT ∪ ΓV is available, which is permutation invariant in terms of cluster labels. For simplicity, we correlate each historical graph Gt ∈ ΓT ∪ ΓV with a 2-tuple (At, Ct). The offline training procedure of IGP is summarized in Algorithm 3, where L is fixed dimensionality for the reduced features Zt; {α, β} are hyper-parameters of the training loss
Algorithm 2: Feature Extraction of IGP Input: input graph Gt; neighbor-induced features Xt; number of nodes Nt; reduced dimensionality L Output: reduced features Zt
1 if L ≥ Nt then 2 let Zt = [Xt,0Nt×(L−Nt)] //Pad Zt with zeros
3 else if L < Nt then 4 derive the coarsening matrix Ct ∈ <Nt×L via Algorithm 1 5 derive the merging membership V∗t based on Ct 6 for each supernode v∗j ∈ V∗t do 7 (Zt):,j ← 0Nt×1//Initialize the j-th column of Zt 8 for each node vi ∈ v∗j do 9 (Zt):,j ← (Zt):,j + (Ct)ij(Xt):,i
Algorithm 3: Offline Training of IGP (on Historical System Snapshots) Input: training set ΓT; validation set ΓV; reduced feature dimensionality L; hyper-parameters of training
loss {α, β}; number of historical snapshots sampled in each epoch p; repetitions to update model parameters (w.r.t. each sampled snapshot in a epoch) m; learning rates {ηD, ηG}; maximum number of epochs n
Output: best model parameters {δ∗G, δ∗D} 1 initialize the variable q̄∗ that saves the best average quality metric 2 initialize model parameters {δG, δD} via the Xavier algorithm 3 for epoch from 1 to n do 4 for sample count from 1 to p do 5 randomly sample a graph Gt ∈ ΓT 6 get the associated 2-tuple (At, Ct) of Gt 7 derive the neighbor-induced features Xt based on adjacency matrix At 8 derive the reduced features Zt from {At,Xt} via Algorithm 2 9 derive the membership indicator Ht based on the ‘ground-truth’ Ct
10 for update count from 1 to m do 11 derive the loss function LD via equation (8) 12 update δD via δD ← Optimizer(ηD, δD, ∂LD∂δD ) with δG fixed 13 derive the loss function LG via equation (12) 14 update δG via δG ← Optimizer(ηG, δG, ∂LG∂δG ) with δD fixed
15 q̄ ← 0 //Initialize the variable that saves the average quality metric of current epoch 16 for each Gt′ ∈ ΓV do 17 get the associated 2-tuple (At′ , Ct′) of Gt′ 18 derive the neighbor-induced features Xt′ based on adjacency matrix At′ 19 derive the reduced features Zt′ from {At′ ,Xt′} via Algorithm 2 20 derive the graph embedding Ut′ from the feature encoder in G 21 apply KMeans to Ut′ to derive partitioning result C̃t′ 22 evaluate partitioning quality q based on C̃t′ (and Ct′ ) 23 q̄ ← q̄ + q //Update q̄ 24 q̄ ← q̄/|ΓV | //Compute the average quality metric 25 if q̄ better than q̄∗ then 26 {δ∗D, δ∗G} ← {δD, δG} //Update the best model parameters 27 q̄∗ ← q̄ //Update the best average partitioning quality
LG; p is the number of historical snapshots sampled in each epoch; {ηD, ηG} are learning rates of the optimizers updating {δD, δG}; n is the maximum number of epochs. For a selected training sample in each epoch, repeatedly updating model parameters m (m ≥ 1) times can sometimes lead to better partitioning quality (on the validation and test set). Algorithm 3 finally saves the model parameters {δ∗D, δ∗G} with the best quality metric on the validation set ΓV.
Algorithm 4: Online Generalization of IGP (to Newly Generated System Snapshots) Input: newly generated graph Gt′ ∈ Γ′, adjacency matrix At′ , reduced feature dimensionality L, number of clusters Kt′ (w.r.t. Gt′ ) Output: partitioning result C̃t′ w.r.t. Gt′
1 derive the neighbor-induced feature Xt′ based on adjacency matrix At′ 2 derive the reduced features Zt′ from {At′ ,Xt′} via Algorithm 2 3 derive the graph embedding Ut′ from the feature encoder in G 4 apply KMeans to Ut′ to derive the partitioning result C̃t′ with Kt′ clusters

heading: B.3 ONLINE GENERALIZATION TO NEWLY GENERATED SYSTEM SNAPSHOTS

text: In the online generalization of IGP, we fix the learned model parameters {δ∗D, δ∗G} and directly derive graph embedding Ut′ with respect to each newly generated graph Gt′ ∈ Γ′ from feature encoder of G. Since we assume that the number of clusters Kt′ of each graph Gt′ ∈ Γ′ is given in the online GP, we apply KMeans to Ut′ to derive the partitioning result C ′t′ with Kt′ clusters. In this case, the total runtime of online GP on each newly generated graph Gt′ ∈ Γ′ includes (i) the efficient feature extraction of Zt′ , (ii) one feedforward propagation of {At′ ,Zt′} through feature encoder, and (iii) the downstream (KMeans) clustering. In conclusion, we summarize the online generalization procedure of IGP in Algorithm 4.

heading: B.4 COMPLEXITY ANALYSIS

text:
For a given graph Gt, we use the efficient matrix multiplication to derive the neighbor-induced features Qt and Mt. Concretely, we set Qt = At − dTt dt / (2w) and Mt = D−1/2AtD−1/2, where dt = [dt1, · · · , dtNt ] and Dt = diag(d t 1, · · · , dtNt) are the degree vector and degree diagonal matrix of Gt. Although the complexities of computing Qt and Mt are both at mostO(N2t ), they can be easily paralleled via GPUs, which significantly reduces the runtime. Moreover, the complexity of the HEM graph coarsening (i.e., Algorithm 1) is no more than O(Nt|Et| log |Et|), with |Et| denoting the number of edges in Gt and |Et| N2t . The complexity to derive Zt via Xt and Ct (i.e., Algorithm 2) is no more than O(NtLn∗), where n∗ is the maximum number of nodes merged into a supernode; L is the number of supernodes (which is also the reduced feature dimensionality of Zt). Hence, the complexity to derive the reduced feature matrix Zt based on Xt is no more than O(Nt|Et| log |Et|+NtLn∗).
Let L(l−1) be the feature dimensionality of the l-th GNN layer of the feature encoder or auxiliary label-induced encoder in G, where we have L(0) = L. We used the efficient sparse-dense matrix multiplication to implement the graph convolutional operation described in equation (5), where the sparsity of At is considered. The complexity of one feedforward propagation through the feature encoder is no more than O(|Et|L(0)L(1) + |Et|L(1)L(2) + · · · ) = O(|Et|LL′), where L′ = L(1) and L(l) < L(l−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 Gt. Let k be the dimensionality of graph embedding. Usually, we have k Nt. For a graph with Kt clusters, the complexity of KMeans is no more than O(NtKtkI) for I iterations. In particular, the runtime of the downstream clustering (i.e., KMeans algorithm) can also be significantly reduced via parallel implementations.

heading: C EXPERIMENT DETAILS

heading: C.1 EVALUATION METRICS

text:
In our experiments, we 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 (3) and equation (1) (see Section 2).
For datasets with partitioning ground-truth (i.e., GN-Net and LFR-Net), we also used the metrics of normalized mutual information (NMI) and accuracy (AC) (Cui et al., 2018), which can measure the
correspondence between the partitioning result (given by the method to be evaluated) and groundtruth (given by the dataset). In general, better correspondence indicates better partitioning quality. For a graph Gt with Kt clusters, we use Ht = {Ht1, · · · , HtKt} and Ct = {C t 1, · · · , CtKt} to denote the ground-truth and partitioning result, where Htr ⊆ Vt and Ctr ⊆ Vt represent node member sets of the r-th cluster. Given Ht and Ct, the definition of NMI is as follow:
NMI(Ht, Ct) = −2 ∑ Htr∈Ht ∑ Cts∈Ct nr,s n log n×nr,s nr×ns∑
Htr∈Ht nr n log nr n + ∑ Cts∈Ct ns n log ns n , (13)
where nr = |Htr| is the number of nodes in the r-th cluster of ground-truth; ns = |Cts| is the number of nodes in the s-th cluster of partitioning result; nr,s = |Htr ∩ Cts| is the number of nodes that are simultaneously partitioned into the r-th cluster of ground-truth and the s-th cluster of partitioning result. Let Lt = (lt1, · · · , ltNt) and Rt = (r t 1, · · · , rtNt) be label sequences of the partitioning result and ground-truth with respect to node sequence (vt1, · · · , vtNt), where l t i and r t i are cluster labels of node vti . The definition of AC is as follow:
AC(Rt, Lt) =
∑Nt i=1 δ(r t i ,map(l t i))
Nt , (14)
where map(·) is the Kuhn-Munkres mapping function that gives the best membership map from Lt toRt; δ(a, b) is the Kronecker delta function with δ(a, b) = 1 when a = b and δ(a, b) = 0 otherwise. Usually, larger modularity, NMI, and AC, as well as smaller NCut indicate better partitioning quality of a given GP method.

heading: C.2 DATASET DETAILS

text:
The detailed statistics of the 11 datasets (with 7 synthetic benchmarks and 4 real datasets) used in our experiments are depicted in Table 3, where T ,N , |E|, andK are the number of snapshots, nodes, edges, and clusters, respectively.
GN-Net (Girvan & Newman, 2002) is a 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 vi and vj , if they’re assigned in the same cluster (i.e., vi, vj ∈ Cr), the probability to generate an edge (vi, vj) is pin. Otherwise (i.e., vi ∈ Cr and vj ∈ Cs (r 6= s)), the probability to generate an edge (vi, vj) is (1− pin)/(K − 1). In particular, we set pin ∈ {0.5, 0.4, 0.3} 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 between any two graphs in the dataset (as we defined in Section 2). Especially, with the decrease of pin, the clustering structures become increasingly difficult to identify. For simplicity, we denote the GN-Net with a specific setting of pin as GN-pin (e.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.
LFR-Net (Lancichinetti et al., 2008) is a more challenging synthetic benchmark that can simulate power-law properties of node degree and cluster size of real-world network systems. It uses (k, kmax, cmin, cmax, µ) to independently generate a single graph, where k and kmax are the average and maximum node degree; cmin and cmax are the minimum and maximum cluster size; µ is
the mixing ratio between the external degree and total degree of each node vi with respect to the cluster vi belongs to. In particular, we fixed (k, kmax, cmin, 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 a 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, µ) (c ∈ {f, n}) to represent the dataset with a specific setting of µ, where f and n denote the case with fixed and non-fixed N (e.g., L(f, 0.3), L(f, 0.6), L(n, 0.3), and L(n, 0.6)). Moreover, K is non-fixed in LFR-Net.
Taxi1 (Piorkowski et al., 2009) is 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.
Reddit2 (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, 870 graphs with N ≥ 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 to 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.
Enron3 (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 ≥ 500 from the records in chronological order, in which we treated each user as a unique node and constructed the topology based on 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-truth 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.
AS4 (Leskovec et al., 2005) is a real dataset extracted from the border gateway protocol (BGP) logs of a communication network, which describe the topology among a 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 to determine K for each snapshot. Therefore, it is with non-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.e., each snapshot shoule be assigned with a common K for all the methods to be evaluated.
1https://www.microsoft.com/en-us/research/publication/t-drive-driving-directions-based-on-taxitrajectories/
2https://github.com/weihua916/powerful-gnns/blob/master/dataset.zip 3http://networkrepository.com/ia-enron-email-dynamic.php 4http://snap.stanford.edu/data/as-733.html

heading: C.3 BASELINE METHODS

text:
In addition to the 15 baseline methods introduced in Section 4, we also evaluated partitioning quality and runtime of other 5 strong baselines, which include degree-corrected stochastic block model (DCSBM), IncSNA (Su et al., 2020), (Karrer & Newman, 2011), DeepWalk (Perozzi et al., 2014), node2vec (Grover & Leskovec, 2016), LINE (Tang et al., 2015), TIMERS (Zhang et al., 2018b) and GIN (Xu et al., 2019). 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, DeepWalk, 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 contrast, DeepWalk, node2vec, VERSE, MILE, and PhUSION are baselines that aim to derive high-quality representations (but may have high complexity) Besides, TIMERS is 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 particular, 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 a 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 Γ′) 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 ΓT and online generalization to test set Γ′). In particular, we can only use the inductive nature of E2E GNN methods (i.e., GAP and ClusNet) on datasets with fixed number of clusters K (i.e., on GN-Net). However, we have to use the same settings with transductive baselines (i.e., training GAP and ClusNet 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 4.
C.4 IMPLEMENTATION DETAILS
We used PyTorch to implement the dual GNN structure of IGP. The feature extraction module (i.e., Algorithm 1 and Algorithm 2) was implemented via NumPy and PyTorch, while we used the implementation of KMeans of scikit-learn as the downstream clustering module. All the experiments were conducted on a server with Intel Xeon CPU (E5-2650v4@2.20GHz, 48 cores), 1 Tesla V100 GPU, 61GB memory, as well as the Ubuntu Linux operating system. In this setting, modules implemented by PyTorch were speeded up via GPU.
For all the embedding based methods, including transductive embedding baselines (i.e., second type of the baseline), inductive GNNs (i.e., 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 KMeans 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 KMeans 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 KMeans) 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 simultaneously running on the test server.
On the validation set ΓV of each dataset, we tuned parameters and determine proper layer configurations for the two variants of IGP. Concretely, we adjusted α ∈ {1, 10} andm ∈ {1, 2, · · · 5} for both IGP-M and IGP-C, while we tuned β ∈ {0.1, 1, 2, · · · 5} and β ∈ {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 4, where dimensionality of the first and last layer of G are set to be L (i.e., dimensionality of reduced feature) and k (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 set the maximum number of epochs n = 100 for all the datasets.

heading: C.5 DETAILED EVALUATION RESULTS AND DISCUSSIONS

heading: C.5.1 QUANTITATIVE EVALUATION

text:
In addition to the visualization results of NMI, Modularity, and runtime in Fig. 3, we also visualized 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 to the fast transductive GP baselines.
In the experiments, we recorded the mean value µ and standard deviation σ of all the evaluation metrics and runtime for all the methods (on test set Γ′ of each dataset). In particular, we use format ‘µ (σ)’ to represent each evaluation result. The quantitative evaluation results on GN-Net and LFRNet in terms of NMI and AC are depicted in Table 5 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 11 and Table 12 give the runtime of all the methods. For both IGP-M and IGP-C, we also recorded the time of (i) feature extraction (i.e., Algorithm 2), (ii) one feedforward propagation (through the feature encoder of G), and (iii) downstream clustering (i.e., 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 6, Table 7, Table 8, Table 9, Table 10 Table 11, and Table 12, which are consistent with the visualization results in shown Fig. 3 (see Section 4), we have the following major observations.
(j) AS (k) Enron
• For all the datasets, IGP-M and IGP-C are in the top group with best quality metrics. Moreover, their runtime is also competitive to fast GP baselines (e.g., Metis, hMetis, GraClus, RandNE, etc.) and other inductive GNNs with fast online generalization (e.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 generated system snapshots. We further quantitatively evaluate the significant trade-off obtained by IGP via a novel trade-off score in Appendix C.5.2.
• Surprisingly, in some cases, IGP even has the best or second-best quality metrics. Note that IGP is a novel inductive framework, in which we do not conduct additional optimization on the test set of each dataset, but other conventional transductive baselines (e.g., SP, DeepWalk, 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 µ, 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.

heading: C.5.2 TRADE-OFF ANALYSIS

text:
In this paper, we focus on the trade-off between quality and efficiency of online GP on newly generated graphs from a system. To the best of our knowledge, to evaluate the trade-off between two aspects that conflict with each other using a comprehensive metric remains an open issue. We propose a trade-off score (TOS) to quantitatively evaluate the trade-off between quality and efficiency of a 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-efficiency visualization result (like Fig. 3). Fig. 5 gives two running examples regarding how to calculate TOS for a 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 as 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 a GP method to be evaluated. Given the tuple (E,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 as the quality metric Q, we further derive the normalized metric via
_ Q = Q/1, (15)
since the value range of NMI or AC is Q ∈ [0, 1] and larger NMI or AC indicate better partitioning quality. Furthermore, when we use modularity as the quality metric, the value range is Q ∈ [−1, 1], in which larger modularity indicates better quality. Hence, we derive the normalized metric as
_
Q = (Q+ 1)/2. (16) In contrast, smaller NCut metric implies better partitioning quality with value range Q ∈ [0,+∞). Therefore, when using NCut as the quality metric Q, we normalize it via
_ Q = (Qm −Q)/Qm (17)
with Qm as the maximum NCut value through all the methods to be evaluated. For efficiency metric E (i.e., runtime), smaller value of E indicates higher efficiency with value range E ∈ [0,+∞), so we further normalize E via
_ E = (Em − E)/Em, (18)
whereEm denotes the maximum runtime through all the methods to be evaluated. Finally, we define TOS with respect to the given quality and efficiency metrics (Q,E) as the (normalized) area covered by the induced rectangle illustrated in Fig. 5. Namely, we have
TOS(Q,E) = _ Q× _ E, (19)
in which larger TOS implies a 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 15, and Table 16, respectively. In our experiments, we saved model parameters of IGP with best metrics in 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 as 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. In summary, IGP can achieve a better trade-off between quality and efficiency of the online GP over various baseline methods.

heading: C.5.3 ROBUSTNESS ANALYSIS

text:
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.1 where fixed settings of (k, kmax,, cmin,cmax) and µ were used, we randomly set µ ∈ [0.3, 0.6], k ∈ [10, 20], kmax ∈ [100, 200], cmin ∈ [10, 20], cmax ∈ [100, 200], and N ∈ [500, 10000] to independently generate 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.5.1. We adopted the same experiment settings and evaluation protocols as in Appendix C.5.1 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 values between each quality metric (from the four metrics) and one efficiency metric are depicted in Table 17. 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
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.

heading: C.5.4 CONVERGENCE ANALYSIS

text:
We also analyzed the convergence of the offline training procedure of IGP (i.e., Algorithm 3). In each epoch of the offline training on a dataset, we recorded the average partitioning quality (in terms of NMI, AC, modularity, and NCut) with respect to the learned embedding {Ut} (i) on training set ΓT and validation set ΓV (i.e., historical system snapshots). Moreover, we also evaluated the average partitioning quality of the generalized embedding {Ut} on test set Γ′ (i.e., new snapshots) in each epoch. To further validate the effectiveness of auxiliary label-induced embedding {U(g)t },
the average partitioning quality of {U(g)t } on training set was also recorded in each epoch during the offline training. Note that we do not need to derive {U(g)t } for ΓV and Γ′. We use evaluation records on the challenging L(n, 0.6) dataset, whose clustering structures are difficult 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(g)t } on training set ΓT, (ii) {Ut} on training set ΓT, (iii) {Ut} on validation set ΓV, and (iv) {Ut} on test set Γ′ for IGP-M and IGP-C are illustrated in Fig. 6 and Fig. 7, respectively.
One can have similar observations in Fig. 6 and Fig. 7. Concretely, the partitioning quality (in terms of NMI, AC, modularity, and NCut) of {Ut} continuously improves in the first several epochs on the training, validation, and test set. More importantly, the average NMI and AC of {U(g)t } on training set ΓT 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(g)t } have perfect mapping to the ground-truth. For both IGP-M and IGP-C, the average modularity and NCut of {U(g)t } also keep at values that are much better than metrics of {Ut} on the training, validation, and test set. The convergence curves with respect to {U(g)t } further verify that the introduced label-induced embedding {U(g)t } can capture much more information regarding ‘ground-truth’ of the training set (i.e., historical system snapshots) than the learned embedding {Ut}, which enables IGP to capture the permutation invariant label information during the offline 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.

heading: C.5.5 ABLATION STUDY

text:
In addition to example results shown in Table 2, we conducted additional ablation studies on 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 σ of all the quality metrics (on test set Γ′) 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 Zt, 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.

heading: D EXTENDED APPLICATIONS

heading: D.1 MODEL SELECTION

text:
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, a model selection method, to the derived embedding {Ut} of both IGP-M and IGP-C to estimate K for each snapshot in the test sets of L(f, .3), L(f, .6), L(n, .3) and L(n, .6). In the 4 datasets, ground-truth regarding the K value is
given by the dataset andK is non-fixed for multiple test graphs. With the increase of µ, the clustering structures of L(f, µ) and L(n, µ) are increasingly difficult to identify. In particular, we use the same parameter settings and layer configurations with that in Table 4. The range ofK of XMeans for each dataset was set according to the maximum and minimum number of clusters as illustrated in Table 3. The model selection results and ground-truth with respect to the test sets of L(f, µ) and L(n, µ) are depicted in Fig. 8 and Fig 9, respectively.
The model selection results in Fig. 8 and Fig 9 are similar. When µ = 0.3 (with distinct clustering structures), the model selection results of both IGP-M and IGP-C fit well to ground-truth 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 L(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.

heading: D.2 TRANSFERRING TEST

text:
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 properties of real-world network systems. We adopt LFR-Net (see Appendix C.2) as the model to generate synthetic training graphs. In contrast to the parameter settings of LFR-Net in our quantitative evaluation (see Appendix C.2), we randomly set N ∈ [500, 6000], k ∈ [10, 100], kmax ∈ [50, 200], cmin ∈ [5, 100], cmax ∈ [50, 400], and µ ∈ [0.1, 0.7] to independently generate 2, 000 synthetic snapshots, where we ensure that kmax > k and cmax > cmin 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 configurations as in Table 4 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 as the results in Table 8 and
Table 10) and (ii) training on the aforementioned synthetic snapshots, respectively. According to Table 22, we have the following key observations.
• In some cases (e.g., on Taxi and Reddit), the quality metrics of training on synthetic graphs are close to those of 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 8 and Table 10. It preliminarily validates the potential of 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 Qt used in IGP-M is more informative than the normalized adjacency matrix Mt used in IGP-C.
Note that IGP has similar motivations with SOTA pre-training methods for graphs, e.g., PretrainGNN (Hu et al., 2020) and GCC (Qiu et al., 2020), in which we pre-train a GNN-based model on historical graphs (in an offline way) and generalize it to new snapshots. The major difference between IGP and SOTA pre-training methods is that a fine-tuning procedure with another optimization algorithm (based on a certain fine-tuning loss) on new test graphs is required for most pretraining 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 fine-tune the (pre-)trained model, which ensures the low runtime on new test graphs. In our future research, we intend to consider a promising application that we pre-train a high-quality GP model on completely synthetic graphs and fast fine-tune the (pre-)trained model on new graphs (via some efficient fine-tuning strategies), with the guarantee of high partitioning quality and low runtime.

heading: E POSSIBLE FUTURE WORK

text:
We summarize several promising future research directions as follows.
Further Reducing the Runtime. According to the results in Table 11 and Table 12, the downstream clustering module (i.e., KMeans 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 dimensionality) 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, we 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 efficiency of the online GP. The fine-tuning on new graphs of targeted scenarios can avoid the negative 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.
Scaling Up to Large Graphs. Scaling GNNs up to graphs with large number of nodes is a significant 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., 2018; 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 a 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-)supervised 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 a large graph into multiple small subgraphs via a sampling module and extract the neigh-induced features {Xt} for each sampled graph. IGP can then be applied to multiple sampled graphs and derive graph embedding {Ut} with respect to each subgraph. One possible challenge in this application is to ensure the consistency of embeddings {Ut} 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 an inductive GNN, but also related to the similarity between the training and test graphs. To give strict theoretical bound analysis of IGP (e.g., for modularity maximization and NCut minimization) is also a significant direction of in feature work.
We intend to extend the theoretical analysis of GP on one 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 on graph toplogy (e.g., NCut minimization and modularity maximization), our IGP method can be easily extended to include node attributes by concatenating the reduced neighbor-induced features Zt and the attribute matrix of an attributed graph. However, prior research (Qin et al., 2018; Chunaev et al., 2020; Qin & Lei, 2021) 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 mismatched characteristics, which result in unexpected quality declines, e.g., in terms of modularity and NCut for GP. In our feature work, we intend to consider an adaptive incorporation 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, we need to control the contribution of attributes to avoid unexpected quality decline for GP.