Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a method for summarising graphs in such a way that they are compressed into a smaller representation while retaining the information required for the downstream task. The authors extend an optimum transport-based framework method for graph summarization (Garg & Jaakkola (2019)) to a supervised graph summarization method which also preserves information for the class label by maximising their mutual information. The effectiveness of the proposed method was demonstrated on several datasets such as MNIST outperforming the baseline that is based on optimum transport.
strength_and_weaknesses: Strengths
- This work is well-motivated in terms of how employing supervised graph summarization might help enhance the model in downstream tasks. 

- I like how this work presents the limitations of existing work on OT and then attempts to address them with a new method.

- Showing that supervised graph summarization is NP-hard is good information because it encourages researchers to think of fast ways to estimate the solution, which the authors attempted to do.

Weaknesses
- The colors in Table 1 are confusing as colors are usually used to identify which results are state-of-the-art and second place. Also, I found it difficult to associate each result with its corresponding method. I would find it a lot easier to read if there was a column "model" that shows the model for each row of results.
- It is not clear what is meant by OT since most methods are Optimal Transport based. It would be easier to parse the results if a citation is provided next to the method's name such as OT. Is this one by Garg & Jaakkola (2019)?
- Results on larger-scale datasets like ImageNet are missing. Having large scale datasets as part of the benchmark is important since this method's main strength is to compress large graphs while maintaining information that helps in the downstream task. 
- It would be useful to know concrete numbers on how many gigabytes of size would be reduced with compression and speed-up in seconds to identify the practical aspect of this work.
- The 100% accuracy on MNIST is a bit suspicious because as far as I know there are few images there that are ambiguous to humans even. Can you elaborate more on how the proposed method got 100% accuracy?
- The results in many cases do not seem significant between the baseline and the proposed method, except on MNIST, can you clarify why that is happening? Also, it seems strange that the compressed graph allows the classifier to train better than the uncompressed version, how did that happen?

Overall this work brings interesting insights and methodology to the table, and I am curious about clarifications on the points I mentioned in the Weaknesses. 
clarity,_quality,_novelty_and_reproducibility: Please see the Strengths and Weaknesses.
summary_of_the_review: Please see the Strengths and Weaknesses.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this work the authors address the problem of graph summarization using optimal transport with class labels in mind. In doing so the author proposes to formulate the problem as an optimal transport that mutual information about a class label is maximized. Empirically the author conducts several experiments to show the improvement over the previous work.
strength_and_weaknesses: Overall this is a neat extension of Garg & Jaakkola (2019) which proposed to address graph summarization from optimal transport point of view. The formation of mutual information under the existing optimal transportation is novel.

While the work overall is a good one, this works' contribution, however,  is limited in that it mostly extends Garg & Jaakkola (2019). Although the theoretically information NON-monotonicity is pointed out, it's not sure how this empirically affects the summarization. Furthermore the experiments would be better improvised with further datasets (e.g. several standard graph datasets in  Garg & Jaakkola (2019)) and visualizations.

clarity,_quality,_novelty_and_reproducibility: Overall this is a neat, original work well written, however it's limited in the scope as mostly an extension of a previous work.
summary_of_the_review: Based on the strengths and weaknesses, I would recommend 6: marginally above the acceptance threshold
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper seems to work on graph summarization problem taking into account node attribute and class label, hence, supervised graph summarization. 
strength_and_weaknesses: +The problem motivation is valid (if the solution is available)
- The paper's writing is too unclear and erroneous to the level that I could not follow. 
clarity,_quality,_novelty_and_reproducibility: - The paper's writing and presentation is unclear and confusing. I could not understand its description of previous work, and more seriously, it's problem setting. 
- Section 2 and the early part of Section 3 are repetitive, even with that, I could not understand its content. There are things like "D" without any connections to the already confusing text. 
- Objective function (1) 3) are unclear.
summary_of_the_review: The paper didn't have a proper presentation that allows readers to follow, let alone judging its quality.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a variant over the OT-based graph summarization technique introduced in (Garg & Jaakola, 2019). The improvement relies on taking supervised information into account (when it exists) through the use of Mutual Information.
strength_and_weaknesses: * Strengths
    * The use of supervised information to guide the summarization process makes sense
    * Relying on Information-theoretic measures for that seems like a reasonable choice
    * The study of the inherent limitations of OT-based approaches for graph summarization is interesting
* Weaknesses
    * The contribution in terms of method is rather limited
    * The paper is presented in such a way that it makes it hard to grasp the repercussions of the findings

In more details:

* Regarding the limited contribution
    * The contribution focuses on setting node weights $\rho_0$ and cost based on an information-theoretic criterion, rather than based on vertex / edge importance, as done in the OT baseline, which is reasonable yet not ground-breaking.
    * In terms of performance, the average gain seems rather limited when compared to the reported standard deviations, except on the Synthetic dataset, which is build on purpose to match the method's specificities. This is rather disappointing given that the OT baseline uses no information for the graph summarization step.
* Regarding the lack of clarity
    * In general, the paper lacks both structure and discussions about the potential impacts of the findings. The paper should be largely rewritten to improve on understandability.
        * Regarding Structure, as an example, Section 5 is interesting but it misses an important point which is to discuss whether the proposed method (Section 4.2) suffers from the limitations presented in Theorem 2 or not
            * This is discussed in the experimental section (6.2) but it would be nice to provide insights on this question in Section 5
        * Regarding discussions, here are a few examples:
            * In Section 4.3, the assumption "that the random node attributes are independent" seems rather strong and not sufficiently motivated. Also, I do not understand the formulation in Equation (13): could the authors detail their derivation for $P(G_V | X_V, C)$ and the underlying assumptions if there are any?
            * In Section 5, the counter-example should be better discussed so as to convey the important message about why this specific example is a counter example, rather than focusing on calculations. Maybe starting with the Theorem + proof and then using the example could avoid redundancy in the text and help focus the counter-example on its illustrative power
            

* Minor issues
    * Strange that authors do not cite anything related to Gromov-Wasserstein for graphs in their literature about the use of Optimal Transport on graphs
    * Section 2 is a copy-paste of the beginning of Section 3!
    * Theorem 2: $X_G$ => $X_V$?
    * I do not understand what the authors mean by "we tag best out of XX% of nodes as sensitive using ..."
clarity,_quality,_novelty_and_reproducibility: The clarity of the paper could be improved by a large margin by giving more insights on intuitions behind the exposed claims / theorems and reorganizing the paper structure such that the whole message is more clearly conveyed.
summary_of_the_review: The paper proposes a method to use supervised information for graph summarization using Optimal Transport.
The proposed method is of limited scope (even experiments do not clearly illustrate its interest) and the presentation is not sufficiently clear to convey the overall message.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a creative use of optimal transport for the goal of graph summarization. The reviewers were somewhat divided about this paper, and perhaps the paper needs a bit more work before it is published.

Regarding Theorem 1: I am not sure if the proof of Theorem 1 completely is clear to me. C seems to be sampled once from Bernoulli, and could be either 0 or 1 with probability 1/2 (if I understand correctly the notation C ~ Bernoulli(1/2)), what if it is sampled to be 0, doesn't that mean that p=0 and therefore, there will be no edges at all in G' (both cases three lines above Eq. 4 will lead to no-edge?). This means that overall there is probabiility 1/2 in the reduction that there will be just no edges in G'? Also, what is E_{v,w}, is it $e$ that is referred to a few words before? Also, what is the meaning of the reduction itself being probabilistic in the standard reduction to an NP-hard problem world? Also, what does it mean in the statement "with the knowledge of data distribution?" How can you query the distribution (I assume with an oracle) with this knowledge, and what could be computed? In addition, NP-hardness refers to decision problems, what is the decision problem here you are reducing to? It seems to be a maximization problem. I feel the details and rigor are just a bit fuzzy with this theorem statement and proof. Some of these concerns are echoed in reviewer comments.

All in all, I think the work is in great direction, but given the reviews, discussions with the SAC, and some of the caveats above and others mentioned in the discussion, I feel there needs to be a bit more work done with respect to clarity of notation and logic and related work.
justification_for_why_not_higher_score: I believe there is lack of knowledge of a substantial amount of older work.
justification_for_why_not_lower_score: The paper presents a reasonable and interesting contribution, but there are some caveats.
Decision: Reject