Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper tries to clarify some confounding concepts around graph/node representation learning by providing a unifying theoretical framework based on invariant theory. The authors define node embedding and structural graph representation based on a minimal number of requirements, which is, in turn, used to derive some useful properties and unify two seemly different concepts. Based on these, a new graph neural network framework is proposed. The experiments on multiple tasks with multiple datasets validate the main claim that a single node embedding is insufficient to capture the structural representation of a graph.

Overall, this paper tries to suggest a solution to a somewhat confusing and controversial problem that everyone recognises but hard to figure out a clear resolution. In that sense, this paper would serve as a good starting point by providing some theoretical baselines. I would like to see more discussion on this topic in future.

In many graph problems where each node is endowed with a certain feature set, we often observe the case where two subsets of nodes are isomorphic in terms of link structure but with different edge of node features. It would be good if there are some discussions on these cases.

Here's a minor comment on the representation of the paper. Although the concept of node embedding and structural representations get clearer as reading, the introduction, where I couldn't find any reference of these, seems unlikely to clarify the difference between these two concepts. The familiar representation in Section 3 might be the first part where the readers could get some intuition about their differences.


review_title: Official Blind Review #4

final_score: rating: 8: Accept
review_content: This paper proposes a unifield theoretical framework for node embeddings and structural graph representations, which bridgs methods like matrix factorization and graph neural networks.
The theoretical analysis is sufficient and experimental results are good. The theory alo shown that the concept of transductive and inductive learning is unrelated to node embeddings and graph representations, which clears another source of confusion in the literature.
In my opinion, this is a theory paper and the proof are sufficient.
review_title: Official Blind Review #3

final_score: rating: 8: Accept
review_content: The authors present mostly theoretical analysis indicating the equivalence of embeddings and structural graph representations. The authors argue that while most of the earlier work consider these to be different, they are actually the same and give theory and empirical results to back up this claim.

This is not an easy paper to read, as the authors immediately jump into heavy notation without much intuition or visual aid. It would be much better to include some figures to help the readers appreciate the work.
This continues throughout the experiments as well, where the authors are not very gentle when it comes to presentation.

I gave a weak accept as I do not want my (unfortunately) weak review (due to the paper topic not being my strong point) to have a great effect on the final decision. However, it is clear that the paper can and should be better written, and the paper ideas made closer to the readers. At the moment this is definitely not the case.


======= AFTER THE REBUTTAL ===========

Thank you for working on making the paper more accessible. I am perfectly fine with seeing this paper at the conference, and will change the vote to Accept simply to not block on my vote and to ensure the SPC makes sure to thoroughly consider this paper (in case they do some sort of ranking of paper reviews for deciding who gets accepted). However please note that my confidence remains as low as previously.
It is unfortunate that ICLR did not do any paper-reviewer matching like other conferences and that you are stuck with my weak review. But that is a different story that the organizers should make sure to address asap.
review_title: Official Blind Review #2

Meta-review: The paper shows the relationship between node embeddings and structural graph representations. By careful definition of what structural node representation means, and what node embedding means, using the permutation group, the authors show in Theorem 2 that node embeddings cannot represent any extra information that is not already in the structural representation. The paper then provide empirical experiments on three tasks, and show in a fourth task an illustration of the theoretical results.

The reviewers of the paper scored the paper highly, but with low confidence. I read the paper myself (unfortunately not with a lot of time), with the aim of increasing the confidence of the resulting decision. The main gap in the paper is between the phrases "structural node representation" and "node embedding", and their theoretical definitions. The analogy of distribution and its samples follows unsurprisingly from the definitions (8 and 12), but the interpretation of those definitions as the corresponding English phrases is not obvious by only looking at the definitions. There also seems to be a sleight of hand going on with the most expressive representations (Definitions 9 and 11), which is used to make the conditional independence statement of Theorem 2. The authors should clarify in the final version whether the existence of such a representation can be shown, or even better a constructive way to get it from data.

Given the significance of the theoretical results, the authors should improve the introduction of the two main concepts by:
- relating them to prior work (one way is to move Section 5 towards the front)
- explaining in greater detail why Definitions 8 and 12 correspond to the two concepts. For example expanding the part of the proof of Corollary 1 about SVD, to make clear what Definition 12 means.
- a corresponding simple example of Definition 8 to relate to a classical method.

The paper provides a nice connection between two disparate concepts. Unfortunately, the connection uses graph invariance and equivariance, which is unfamiliar to many of the ICLR audience. On balance, I believe that the authors can improve the presentation such that a reader can understand the implications of the connection without being an expert in graph isomorphism. As such, I am recommending an accept.


Decision: Accept (Poster)