Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose an inductive graph partitioning (IGP) framework across multiple snapshots of a dynamic graph to produce an effective partitioning of the graph. IGP is based on training on the snapshots of the graph using a dual GNN architecture and is used to generalize to subsequent snapshots of the graph.  
main_review: The paper proposes an interesting framework which is resistant to permutations of the training set used by the IGP framework.  Specifically, the framework derives graph embeddings based on the input graph (as an adjacency matrix) and feature matrix which encodes neighbor similarity.  The embeddings are then used in the assignment of the node-disjoint cluster labels. 

The ablation studies clearly show the effect of different aspects of the proposed architecture.

The reporting of the trade-off scores is slightly unclear.  What is the efficiency measure that is being traded-off?  Clarifying this in the main body of the results will make them clear.  Finally, there is literature - both in terms of discrete algorithms and learning representations - that addressed the problem of incremental partitioning of an evolving graph.  See, for example, https://rlgm.github.io/papers/41.pdf and https://www.vldb.org/pvldb/vol13/p1261-fan.pdf (and references within).  Comparison with the prior art in terms of the trade-off achievable will make the empirical analysis stronger. 

Other drawbacks of the work include the availability of training data that *already* computes an 'optimal' partition of a snapshot.  It's not clear how this can be achieved.  Secondly, the comparisons in the experiments are against other ML models whose performance cannot be verified in terms optimality loss, i.e., how far are those solutions from the optimal solution.   In this context, comparison to an algorithm with known approximation factors would help.
summary_of_the_review: I feel the paper in its current form can be significantly strengthened in terms of the presentation of the empirical results by clearly explaining the trade-off achieved as well comparing with more algorithms from the literature as baselines.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose an inductive graph partitioning framework across multiple evolving graph snapshots to alleviate the NP-hard challenge. It first conducts the offline training of a dual graph neural network on historical snapshots to capture the structural properties of a system. The trained model is then generalized to newly generated snapshots for fast high-quality online GP without additional optimization, where a better trade-off between quality and efficiency is achieved. 
main_review: Strong points:

Overall, the paper is well written and the experimental part seems comprehensive. 

A few comments.

1) Theorem 1 is stated in a very informal way. It seems not good to add discussion on one concrete example in Figure 2 in a statement of a theorem. I would suggest that please move that outside and discuss the potential meanings and implications of theorem 1 on examples separately. 

2) Figures 1 and 2 both are too small and it is hard to read details there.




summary_of_the_review: The paper seems well written. Here are a few typos.

1) The first line on the first paragraph of section 2: $S=...$, a comma is missing after the symbol $\mathcal{G}_2$.

2) On page 6, in the sentence just above equation (12), *we drive* should be *we derive*...
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of solving the graph partitioning problem repeatedly over many different graphs. Graphs are sampled i.i.d. from an unknown but fixed distribution and the goal of the algorithm is to solve the GP problem on each of the graphs. There are two quantities that are opposing; efficiency (on one hand we can solve an NP-hard problem each time but would be prohibitively time consuming) and quality (on the other hand we can generalize from the learnings on the other graph since they are related via the i.i.d. distribution). This paper proposes a NN architecture that uses a subset of the graphs in the family to learn an embedding, and then derives the solution to the other instances by using this embedding via a matrix multiplication. Using a number of simulated and real-world datasets they show that this method works well empirically.
main_review: The strengths of this paper are as follows.

+ The problem consider is important and practical. Graph partitioning is an important pre-processing step in many applications. Moreover the model of being sampled i.i.d. has practical relevance and also considered in many prominent works in the graph networks literature.

+ For the most part, the paper is written well, with detailed explanantion of the methodology and the results. The experiments are also exhaustive and sound. They considered an exhaustive list of baselines, and show that they perform nearly well or better than most methods on the range of tasks considered.

+ They use publicly available datasets and the results can largely be reproduced.

The weakness of this paper is as follows.

- The paper does not do a good job of crisply characterizing how their methods differ from prior works. The reasons why their method is better, that the authors state, seem somewhat shallow/arbitrary. They claim that computing gradients etc are expensive/time-consuming. Yet their method is based on adversarial auto-encoders, which need to be trained via gradient based optimization methods. So it seems like this is not a real difference. The only difference I can see is that, this paper considers a different NN architecture and training method compared to some of the other GNN based methods (e.g., Hamilton et al.,). I would like the author's to be a bit more precise and scientific & also credit prior works better.

- Along the lines of (1) it is not entirely clear to me why this method works. Adding intuition about some of the choices would make it much better. At the moment it seems like, they created a new method, threw it at the datasets, and it happened to work. Some more principled study on why it works would greatly help the paper.

- The paper does not report CIs in the experiment. Some of the points are so close to each other, that without CIs its unclear if its real improvement or just noise. This is important, since the thrust of the claims made by this paper is in the experiments, and having rigoros statistical analysis gives more confidence in the results.
summary_of_the_review: My main review is based on the weaknesses I stated above. I am not totally confident about the importance/merit of the approach provided in this paper. Thus, I am giving a weak reject.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work the authors focus on an important problem, building an inductive framework for graph partitioning. This is a major problem with the potential of improving the performance of various classic transductive  algorithms for graph partitioning, both in terms of output quality, but also in terms of speed when a new snapshot  of a system needs to be partitioned into communities. This is a recent line of research, see, e.g., Nazi et al. 2019 "GAP: Generalizable Approximate Graph Partitioning Framework".  The proposed framework can address snapshots with differing number of nodes, by projecting them down to coarsened versions of the network. There are two versions of the framework, based on normalized cut and modularity objectives respectively. The framework can be potentially used with other measures as well. A nice idea is to leverage the unsupervised communities extracted from modularity optimization, or spectral algorithms through a dual GNN structure, that can then be used to partition fast unseen instances.  
main_review: The paper has various strong points, including an extensive experimental evaluation with numerous other baselines, 

- What is the advantage that the dual GNN offers over other choices in prior work (Pan et al. 2018, Nazi et al. 2019)?  

- Under what conditions on the training dataset does the framework work well? Is it easy to test those conditions? E.g., from equation (11) that encodes a "k-cut size" it seems that you implicitly assume small changes from snapshot to snapshot?  Is this what you mean by saying that the graphs are snapshots of a given complex system?

- Can you please elaborate on how the uncoarsening is done to get the actual community participation of the query graph G?
 
- Having an axis with >T secs is not very informative for the proposed method. Can you please be more specific about the runtimes? 

- Can you test your method on communities with community groundtruth? 

- For the synthetic experiments using the stochastic blockmodel, it would have been nice to see a comparison with the paper  "Supervised community detection with line graph neural networks" by Chen et al. that provides state-of-the-art results.   


summary_of_the_review: The paper has various strong points, but the write-up can be improved. I found overall the paper hard to read; e.g., the choice of the dual GNN is not well justified (what issues is it resolving from GAP), reading the theorem 1 was kind of confusing, as the statement feels more as an observation derived from the definition of a partition etc.  I also found the term of permutation invariant for labels (0,1,1) vs (1,0,0) a bit confusing, as up to that point, I was expecting labels to be indicator vectors of which community a node participates in.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors consider the problem of inductive graph partitioning, which they formulate as clustering or partitioning multiple snapshots of a time-evolving graph for which we have no node correspondence. In other words, we cannot link the nodes in snapshot $t$ to those in snapshot $t-1$, which prevents incremental or evolutionary clustering algorithms from being applied. The propose a complicated dual graph neural network (GNN) architecture for this problem setting and demonstrate potentially good clustering accuracy with low computation time on simulated and real networks.
main_review: Strengths:

- Performs graph partitioning on multiple graph snapshots while not requiring any form of correspondence of nodes between snapshots.
- Proposed architecture includes a few novel elements.

Weaknesses:

- Presentation of results is extremely poor. Figure 3 is trying to show way too much! It took me several minutes of staring at the figure, zooming in and out, and examining multiple legends to understand what is being shown. Be selective in the results that you show in the main body, and provide the rest in the supplementary. Text in figures and tables is too small.
- ~~Proposed problem setting specifically assumes that there is no node correspondence between snapshots, but then all of the real data experiments involve snapshots over time, which do have node correspondence. Methods that use node correspondence (e.g. incremental and evolutionary clustering) could possibly do better on these datasets.~~
- No motivating application for the no node correspondence setting. Since there is no dataset targeting the proposed setting, a motivating application without data could also provide some justification as to why one should care about this setting. But no such application is present, so it feels more like the authors invented a problem to solve.
- On real data sets, the number of clusters $K$ is not known, so the authors run the Louvain algorithm to choose $K$. But the Louvain algorithm also outputs a set of clusters, which appears to be discarded. ~~Furthermore, the computation time of the Louvain algorithm does not appear to be included, although I can't be sure because the presentation of the results is such a mess.~~

Theorem 1 is trivial, and I'm not sure why it is highlighted as a theorem.

*After discussion period:* I have added a strike through the incorrect portions of my review that have been clarified by the authors.
summary_of_the_review: The presentation of the results is extremely poor, making empirical results very hard to interpret. I also have concerns regarding the problem setting and evaluation, so I do not view this paper as ready for publication at this time.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an inductive GNN-based framework that partitions unattributed graphs with possibly different numbers of nodes and ground-truth clusters. Extensive empirical evaluations using both synthetic and real datasets demonstrate that the new method achieves a better trade-off between quality and efficiency when compared with 15 baselines from 4 categories.
main_review: **Strengths**

Both the inductive graph partitioning problem which the paper attempts to solve and the dual GNN adversarial approach are interesting. The authors conduct comprehensive experiments and showcase the usefulness of their method. Even though there are a few notable limitations of the current work (which I will detail below), the authors explicitly state the assumptions and carry out a number of experiments that cover a reasonable range of inductive scenarios.

**Weaknesses / Limitations**

1. The paper does not provide a theoretical guarantee on the generalization to new unseen graphs. It would be nice if a guarantee on modularity or NCut is provided.

2. The proposed framework does not work with attributed graphs. For graph partitioning this might be the usual setting, but the authors should comment on if incorporating node features could be helpful.

3. The authors assume that the set of graphs, which includes both offline training and online testing graphs, follow similar distributions. This assumption easily breaks in practice for graphs that come from different domains. Table 21 in the appendix seems to indicate that, in general, the proposed inductive method may not generalize well due to distribution shifts. On the other hand, I appreciate the authors conduct additional transferring tests, even though the results are mixed, this is a plus since it provides the reader with additional information. For the experiments with LFR synthetic graphs in the main text, what would happen if we increase the range of N, e.g., from 500 to 10,000?

4. The method requires knowing the number of ground-truth clusters K. It may not really be a limitation, as many graph partitioning methods also require K as a parameter.

**Minor issues**

1. In order for (1) and (2) to be equivalent, do we need to perform some rounding algorithm on an optimal solution H_t of (2)?

2. Theorem 1 is trivial, it should be stated as a fact with detailed arguments left to the appendix.

3. The font size in Figure 2 is too small. I cannot read it without zooming in on a screen.
summary_of_the_review: The paper proposes a new GNN-based framework for inductive graph partitioning. The authors conduct extensive experiments that cover a reasonable range of scenarios that showcase the usefulness of the proposed method. My concerns are (1) there is no generalization guarantee, and (2) the method may fail due to distribution shifts, as shown in the experiments.
review_title: null

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

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