Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Motivated by the sort-and-smooth graphon estimator of Chan and Airoldi, 2014, this paper proposes two new clustering algorithms (graph distance based spectral clustering and similarity based semidefinite programming) for multiple graphs observed without vertex correspondence. The idea is to use the graphon approximation method to obtain a histogram estimator with the same number of bins for each graph and subsequently apply an existing spectral clustering approach on the graphon based distance matrix.
Theoretical properties of their approach are studied (under reasonable smoothness assumptions on the generating process i.e. graphon) and consistency is established. The graph distance metric is applied to test for similarity of two collections of graphs. 

main_review: Strengths:
- Deals with the issue of vertex correspondence for clustering of a population of graphs. A large proportion of existing methods developed for clustering assume vertex matched collection of graphs. Thus the idea is to first employ graph matching algorithms and subsequently use these techniques. As a consequence, these existing works do not provide clarity on the actual performance of clustering methods which may vary depending on the choice of graph matching algorithm used in the first step. This paper studied the clustering problem exactly as encountered in practice.

- Theoretical guarantees are provided for the proposed clustering algorithms and testing framework

Weaknesses:
- The Bernoulli exchangeable model for graph only allows dense graphs (as the probability of edges does not depend on the number of nodes n). Most real world networks are sparse and thus I find this model restrictive. 
- Assumption of strict degree monotonicity is a restrictive one which is not satisfied in many real data examples. It appears that other existing histogram methods for graphon estimation such as by Airoldi, Costa and Chan, 2013 or Olhede and Wolfe, 2014 might be better suited for the clustering task given this practical concern. 
- Number of clusters K is assumed to be known for the numerical experiments whereas in practice this must be suitably determined from the data itself
-Simulation study does not report performance for the case of sparse networks
- Not clear how robust the techniques are to the assumption on strict monotonicity of the degree not being satisfied and to the choice of metric used to define the graph distance
- A discussion on the consequences of Assumptions 2 and 3 specifically wrt clustering (the main objective of the paper) would have been helpful 

Other minor comments:
- From reading the introduction it was not clear what 'clustering' meant exactly : in general for a  population of graphs, it could mean clustering of nodes in each graph or clustering across graphs or both. 
 .- What sort of graphs are considered? Directed/self-loops? Not mentioned in the paper. 
- What exactly is Assumption 3? Is it assuming that each w_i is an element of an equivalence class unrelated to the equivalence class of w_j? How is the equivalence class defined?
summary_of_the_review: Overall, the proposed idea combines existing approaches on graphon estimation and spectral clustering to lead to the proposed clustering and testing approach. It is a neat idea and comes with theoretical guarantees, however, I find the setting of dense networks and the strict assumptions on degree sequence as required for graphon estimation, restrictive. The performance of the clustering algorithms and the testing approach when these assumptions fail and when the number of clusters is unknown, is not clear from the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a graph distance based on graphons that can operate on the small sample size regime; this is possible by exploiting a large number of nodes.
The proposed paper is meant to address two shortcomings that the authors have found in the literature: 
- a lack of study of current graph processing methods beyond graph-level classification, and 
- a lack of theoretically sound methods.  

The paper also shows theoretical guarantees associated with two existing clustering methods and a two-sample statistical tests when operating with the proposed distance.


main_review: __Strengths__:

The paper is easy to read and follow, well-grounded, and theoretically sound in most of its parts. 
The authors also try to give intuition about the choices they made.
The developed method is applicable and effective to small samples of graphs and it appears novel to me.

__Weaknesses__:
1. The authors claim there are no studies beyond network classification and a lack of theoretical support for the available methods. In my opinion, the claim is not correct. Many papers include different graph-level tasks in their experiments and several of them provide also theoretical support about the proposed architecture; I can refer the authors to some of them below. The authors also claim "the efficacy of these methods [on graph matching] in learning from network-valued data remains unexplored". The authors should be more precise about what remains unexplored. Nevertheless, I may agree that extra studies and theoretical analyses can positively contribute to the research in this field, and I recognize the value of considering the small sample size setting.
    * https://ogb.stanford.edu/
    * Dwivedi, Vijay Prakash, et al. 2020. Benchmarking graph neural networks
    * Bouritsas, Giorgos, et al. 2020. Improving graph neural network expressivity via subgraph isomorphism counting.
    * Zambon, D., Alippi, C., & Livi, L. 2020. Graph Random Neural Features for Distance-Preserving Graph Representations.
    * Sato, Ryoma. 2020. A survey on the expressive power of graph neural networks. 
    * Maron, Haggai, Heli Ben-Hamu, and Yaron Lipman. 2019. Open problems: Approximation power of invariant graph networks.
    * Loukas, Andreas. 2019. What graph neural networks cannot learn: depth vs width.
    * Kriege, Nils M., et al. 2018. A Property Testing Framework for the Theoretical Expressivity of Graph Kernels.
    * Chen, Hao, and Jerome H. Friedman. 2017. A new graph-based two-sample test for multivariate and object data.
2. The graph transformation of G to G^\sigma seems to be ill-defined. Although the graphon can have unique node degrees, graphs sampled from it can result in nodes with the same degree, so 1) there might not exist a monotonically _increasing_ permutation but only _non-decreasing_, and 2) the permutation is not unique, in general. 
3. The claim "NCLM is the only known clustering strategy for graphs of different sizes" is incorrect. Basically, any kernel-based and distance-based clustering method that does not require explicit vector embeddings can be applied to graphs. It is customary to choose the most appropriate distance or kernel that better fits the problem at hand; a simple example is k-means. The claims seem unjustified to me also because, as far as I can tell, NCLM constructs vector representations of graphs.
4. The methods chosen for the comparison can give only limited insights. The considered methods appear to be more or less arbitrarily chosen combinations of graph functions with clustering methods. For example, this approach does not allow us to understand whether it is the proposed distance or the considering clustering method that brings the most advantages. I might be wrong, but it seems to me that there is no limitation in performing experiments with the proposed graphon-based distance with other clustering methods, and the considered clustering methods with other distances/kernels.
5. Regarding the two-sample hypothesis test, it is unclear how a critical region of a given significance level can be constructed without having knowledge about the underlying graphons. From what I see, in the paper, the critical region is computed by sampling from the original graphons. I would to have some clarifications in this respect.


Questions and unclear parts:
- The sorting-and-smoothing estimator is mentioned even in the abstract, but never introduced in the paper. Why is it the only one that can meet the above requirements? Moreover, the above requirements (I guess the authors refer to Assumptions 1-3) are about the graphons, not their estimators.
- Theorem 1. It is counterintuitive for me that for a bounded number of nodes, the more graphs we have, the larger the _rate_ of erroneous clustered graph increases. I would expect that for m -> infinity, the rate of misclustered graphs converges to the optimal value (which is not necessarily zero), and the variance of such observed rate decreases. Could you comment on that? 
- It is not clear to me to what extent the discussed clustering methods had to be adapted to work with the proposed distance. It is also unclear whether or not these clustering methods would be consistent regardless of the specific graph distance, provided that the graph distance is sufficiently expressive (eg, it is metric).
- Because the considered method is based on edge histograms, I wonder if there are known limitations or important differences when considering sparse graphs instead of denser ones. Are there different best practices to operate in the two regimes? 

__Other comments and suggestions__:
- Say explicitly that graphs are symmetric and without node or edge attributes (if this is the case).
- Expand the comment about indistinguishable inhomogeneous random graph models. What is the argument to show that although different, they are indistinguishable? What are we losing by ignoring such graphs, in what cases are we interested in considering also them?
- Prop 1. Please, expand the discussion about the variable n which seems to be undefined.
- Cor 1. Shouldn't it be: given m, n_0 and |w-w'|, we need to find a _small_ enough constant C?

summary_of_the_review: Overall the paper is well written. The proposed solutions are novel to me and address an extremely challenging problem related to the small sample size regime. However, a few negative aspects are present: there seem to be incorrect claims, the graph transformation appears not well-defined, and the experimental setup does not bring decisive conclusions.
Given the points raised in the main review section and unless it turns out I misunderstood those parts of the paper, I am afraid to say that the paper is ready for publication in its current state. However, I encourage the authors to carry on the research in this direction, because it appears promising and only few (yet, important) aspects need to be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 
This paper presents an interesting approach to clustering of graphs sampled from graphons.  The papers presents a number of guarantees for the quality of obtained clusterings and a few preliminary experiments.

main_review: 
The paper is very interesting, well written and understandable.

The proposed heory only works when graphs are sampled from graphons and the vertices are kept in the same order.  On the one hand, I understand that anything involving graph isomrophisms (and hence vertex permutations) will be untractable.  On the other hand, in practical applications we don't know the order of the vertices, hence there is a lot of work on graph isomorphism, graphon cut norms, and other tools to deal with that issue.  Assuming instead 'ordered' graph sampling with L2 graphon norms is interesting from a theory point of view but is quite far from practical applications where clustering and testing becomes relevant.

The experimental section could devote more attention to the runtime of the algorithms and experiments.

Nevertheless, the paper has some original ideas which could form a first step into more mature results.


Some details:
* Assumption 2: I dislike the term "degree distribution" in this context.  Usually, "degree distribution" is used for a probability distribution f which gives for a input degree d the probability f(d) that a randomly selected vertex has degree d.

* In Equation (1), it seems the index i of A_{i,j} starts from 0 until n_0-1 rather than from 1 to n_0 as usual.  Alos, vertices with index larger than n_0*\lfloor n/n_0 \rfloor aren't taken into account.

at some places articles are missing, e.g.,
* page 5 first line: Davis-Kuhan theorem -> the Davis-Kuhan theorem
* Sec 3.2 second line: Gaussian kernel -> the Gaussian kernel




summary_of_the_review: 

The paper is interesting and sound, while the result on itself is not yet very practical it could form a good first step.
review_title: null

Meta-review: This paper presents a new method for clustering multiple graphs, without vertex correspondence, by combing existing approaches on graphon estimation and spectral clustering. All reviewers agree that this is a neat paper with new theoretical and empirical results. The main concerns were also properly addressed during rebutal. Overall, it is a good paper.
Decision: Accept (Poster)