Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: Below constitutes the Official Review for Paper2605.

Summary of the paper:

This paper explores the problem of constructing invariant representations to certain new environments. Specifically, they constrain the problem to a so-called single-environment graph classification or regression task. Authors define a notion of counterfactual coupling, and consider a notion of invariance different from (though not well-justified) the standard literature. Based on the authors' own definition, they consider a few example tasks on random graphs. Under strong assumptions, authors show a couple generalization error bounds. Their bounds appear to be algorithm agnostic and do not take into account the neural network or optimizer properties. On the modeling side, authors propose a model: the model is to simply replace a one-hot vector with a GNN. Small-scale experiments are conducted on two toy datasets to show the proposed model slightly improves four vanilla baselines, on these two toy datasets.

Evaluation:

While it is clear that papers like Paper2605 have much to offer, the official recommendation is rejection. 

Overall, it is unclear what contribution this paper has. The problem setting is contrived, over-complicated, and not well-defined. It is hard for one to find the theorems meaningful: they assume strong assumptions and contrived settings, and are not applicable to real problems. What conclusion one can draw from the theorems are also quite unclear. The technical proofs are unimpressive either as they appear to be maneuvering the already contrived definitions with basic inequalities. 

The proposed model is unclear, unmotivated, and has logical gaps.  No clear algorithm process or code is given. Reproducibility is impossible. No motivation or theoretical guarantee is given, neither were we given evidence how it may compare to other invariant/causal models such as IRM or domain adaptation techniques.

Because the theoretical and modeling contributions were unclear, one would expect to see strong experimental results. Yet, the experiments are particularly unconvincing, in that the proposed one had only been evaluated on two toy datasets,  and compared to four baselines. State-of-the-art models such as IRM, REx, domain invariant models are are missing from the comparison. Putting aside the unconvincing execution,  the experiments do not seem to corroborate the theorems (which are ambiguous and unclear anyways) either, making the theoretical/modeling contribution even weaker and more unclear. 

Additionally, one must complain about the poor writing. This paper suffers from the lack of logic and mathematical rigor; it is full of jargons that are unexplained and undefined. For example, after reading the entire paper, one still can't find a definition of GNN or GNN+, which constitute the main part of the proposed model. It is impossible to imagine the ICLR community will appreciate this paper. Based on the evaluation, a rejection is recommended. 

$\textbf{Unclear contribution and contrived/trivial theorems}$ 

One cannot draw any clear conclusion from the theorems. Problem setting and theorems are contrived, over-complicated and not rigorously defined. The technical proofs are unimpressive either as they appear to be maneuvering the already contrived definitions with basic inequalities. 

''Definition 1 (Counterfactual coupling (CFC)).'' This definition is simply confusing and contrived. How can you even evaluate over all permutations? This is NP-hard?  The independence assumption is also strong? How is this different from standard definitions? Never explained?

''Proposition 1. Let P(Y |G(obs) N(obs) = G (obs) n(obs)) and P(Y |G(cf) N(cf) = G (cf) n(cf)) be the conditional target distributions ''  Proposition 1 seems to be only stating definitions (generalization error etc), how is this even a proposition? 

''Proposition 1. a link function ρ(·, ·) such that'' link function p is never defined. 

''assume Y ∈ Y is discrete'' What about regression?


'E ∈ Z+ that describes the graph-processing environment''.  Graph-processing environment is never defined. What is that?

''supervised task over a graph input Gn(n ≥ 2) and its corresponding output Y''. Problem is undefined. What is graph classification or regression?  Is the response variable over graph, edge, vertex? Is input one graph or many graphs?

'' Consider a permutation-invariant graph representation Γ : ∪∞ n=1Ω n×n → R d''  How is this even possible?  Permutation-invariant graph representation is such a strong assumption?

''Proposition 1 shows that an E-invariant representation will perform no worse on the counterfactual
test data (extrapolation samples from (Y, G (cf) N(cf))) than on a test dataset having the same environment distribution as the training data (samples from (Y, G (obs) N(obs))).''  Well, this is apparently wrong? Evidence? 

''Other notions of E-invariant representations are possible (Arjovsky et al., 2019; Scholkopf, 2019), but ours —through coupling— provides a direct relationship with how we learn graph representations from a single training environment.''  Not convincing? Evidence? Well, Arjovsky et al., 2019; Scholkopf, 2019 can be applied to graphs too? You are also missing a great amount of literature on invariant models and domain adaptation techniques.

''Theorem 1. Assume our graph-processing heuristic'' What does graph-processing heuristic even mean?

''Theorem1.   the outputs of ge1 and ge2 of Equation (1) can only differ in their attributes ∀e1, e2'' What does this even mean? Seems too contrived?

''Theorem 1. Deleting a random vertex n from G (obs)n |W, and the distribution of the trimmed graph is the same as the distribution of G (obs)n−1|W, with G (obs) 1|W as a trivial graph with a single vertex for all W'' Over-complicated?

''For every 1 < k < n, the subgraphs of G (obs) n |W induced by {1, . . . , k} and {k + 1, . . . , n} are independent random variables'' Why does this hold? Evidence?

''Then, the variable W can be equivalently defined as W = (W0, C0E), where W0 is a random variable defined over the family of symmetric measurable functions W0
: [0, 1]2 → [0, 1], i.e., W0 is a random graphon function, and, if the graph has attributes, C0 E is an environment-dependent random
variable that defines vertex and edge attributes, otherwise, C0E = Ø is defined as the constant null.'' Unclear what conclusion one can draw from Theorem. Doesn't seem to have useful implications. 

''It is possible to guarantee that a graph representation is E-invariant even when the training data contains just one environment.'' This reads apparently wrong? Evidence? 

''inj(F, G) be the number of injective homomorphisms of F into a larger unattributed graph G'' Expensive to evaluate? Justification?

''1one-hot{Fk0 , F≤k} be the one-hot vector with a one at the index of Fk0 in F≤k and zeros elsewhere'' How do you construct this? Not well motivated? 

$\textbf{Trivial and unmotivated modeling}$

The proposed method (Section 3.2) is not well-motivated and is ambiguous. No clear algorithm is described either, making it impossible to reproduce.

''Hence, our proposal replaces the one-hot vector 1one-hot{Fk0 , F≤k} with a GNN applied to Fk0 : ''  What is this one-hot vector? What is GNN? Never defined? Replacing one hot by GNN seems trivial? 

''ta-inj(Fk0 , Gn)'' Not well-defined? Algorithm to compute this?

''Unfortunately, GNNs are not most-expressive representations of graphs (Morris et al., 2019; Murphy et al., 2019b; Xu et al., 2018a) and thus ΓGNN(·) is less expressive than Γ1-hot(·) for unattributed graphs.'' What does this even mean? Then why do you use GNN (which is not defined anyways)?


$\textbf{Unconvincing experiments}$

The proposed model is only evaluated on two toy datasets.

A large amount of baselines on invariant models, causal models, domain adaptation techniques are missing. Just to name a few,

https://arxiv.org/abs/1907.02893

https://arxiv.org/abs/2003.00688

https://arxiv.org/abs/2002.04692

https://arxiv.org/abs/1505.07818

https://arxiv.org/abs/1911.00804

https://arxiv.org/abs/2006.07500

https://arxiv.org/abs/2010.07922v1


The proposed model only slightly improves upon four basic baselines on the toy datasets. 

The experiments do not corroborate the theorems (which are inconclusive anyways). 


$\textbf{Poor writing and mathematical rigor}$

The paper is full of jargons that are unexplained and undefined.  Many claims are stated without evidence.

''graphs are simply representations of a natural process rather than the true state''. What does this even mean? Evidence?

'E ∈ Z+ that describes the graph-processing environment''.  Graph-processing environment is never defined. What is that?

''supervised task over a graph input Gn(n ≥ 2) and its corresponding output Y''. Problem is undefined. What is graph classification or regression?  Is the response variable over graph, edge, vertex? Is input one graph or many graphs?

''graph generation function g : Z+ × D × D → Ω n×n'' D is never defined. What is D?

''in some canonical order'' what is the canonical order?

''graphs are simple, meaning all pairs of vertices have at most one edge'' This is a wrong definition of simple graphs?

''Erdos-Renyi example (part 1)''  The problem setting is described by an example. A rigorous definition of problem setting is expected. 

''Figure 1: (a) The DAG of the structural causal model (SCM) of our graph extrapolation tasks where hashed (white) vertices'' Hashed (white) vertices do not exist in Figure 1 (a)? What is sampled permutation?

''Illustrates the relationship between expressive model families and most-expressive extrapolation families'' How is this even related?

SCM is never defined? While I know what a SCM is, this presents yet another example of poor writing.

''Single-environment graph extrapolation task''. What does this even mean?  Can you formally define it? Isn't the paper studying invariant models?  https://en.wikipedia.org/wiki/Extrapolation  extrapolation is used in a confusing way, different from wikipedia? 

''the value Y = W in Equation (3), which is also the edge probability p'' Well, isn't this too contrived?

''Hence, traditional (interpolation) methods can pick-up this correlation, which prevents the learnt model from extrapolating over environments different than the. ones provided in the training data (or even over different P(E) distributions).'' Well, this is not your contribution, so you need to properly add citation.

''we need a backdoor adjustment'' What is backdoor adjustment? Undefined? Well, although I know what it is, it shows yet another example of lack of mathematical rigor.

''Definition 1 (Counterfactual coupling (CFC)).'' This definition is simply confusing and contrived. How can you even evaluate over all permutations? This is NP-hard?  The independence assumption is also strong? How is this different from standard definitions? Never explained?  

''Proposition 1. Let P(Y |G(obs)
N(obs) = G
(obs)
n(obs)) and P(Y |G(cf)
N(cf) = G
(cf)
n(cf)) be the conditional target distributions ''  Proposition 1 seems to be only stating definitions, how is this a proposition? What do you even mean?  

''Proposition 1. a link function ρ(·, ·) such that'' link function p is never defined?

''Theorem 1. Assume our graph-processing heuristic'' What does graph-processing heuristic even mean?

'' the outputs of ge1 and ge2 of Equation (1) can only differ in their attributes ∀e1, e2'' What does this even mean? 
review_title: Official Review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper explores the problem of extrapolation in graph classification tasks and by leveraging Lovasz’s graph limit theory, provides graph representations and related theoretical guarantees on graph size extrapolation in the context of unattributed graphs. Specifically, it is shown that the graph representations characterized by induced homomorphism densities are size-invariant under certain conditions. The theoretical claims are validated by empirical evaluation of classifiers trained on the proposed graph representations. 

Overall, I find the contributions of the paper solid and of interest to many researchers. 

Pros: The paper is well written with an appropriate focus on motivating the problem at hand. The experiments seem convincing enough to establish the implications of theoretical guarantees. 

Cons: I don't see any major issues in the paper. 

Elaborating on a few points will help improve the readability:

1. I recommend elaborating on the graphon function $W'$ defined in Theorem 1 and its relation to graph topology. 

2. Are the conditions of Theorem 1 violated by any large class of graph models, such as MRFs?



review_title: Interesting contribution to graph size extrapolation 

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper formulates a theoretical model for testing extrapolation abilities of graph learning tasks, and suggests some practical feature maps to achieve good extrapolation properties empirically. In more detail, this paper introduces a model, a so-called structural causal model, for graphs where the graph creation process is modeled as a random variable that depends on different independent factors:  environment $E$, which is used to model the graph size $n$; graph property $W$, which is used for example to model the probability of edge existence; and random seed $Z_X$. The created graph is also scrambled by a random permutation to yield the observed graph $G^{\text{obs}}$. The ground truth labels of the graph $Y$ are functions of two factors $W$, the graph property, and $Z_Y$ random seed. 

The authors claim that a problem with learning data of the form $(G^{\text{obs}},Y)$ is that $Y$ is not independent of $E$ given that we see $G^{\text{obs}}$ and therefore standard learning techniques can overfit certain environments and fail to extrapolate. These dependencies are referred to as backdoor paths. Then the authors move to define counterfactual coupling of $G^{\text{obs}}$ and $Y$. They actually mention equation 1 but i assume this is a mistake and they mean equation 2. Also, why $\tilde{E}$ is used as regular variable inside $g$? The definition is confusing to me since the event the indicator defines does not necessarily mean $G^{\text{obs}}=G^{\text{cf}}$. Anyway, I could not really understand what is the object that is defined here. My best guess was that there is a new random variable $G^{\text{cf}}$ defined with a new environment $\tilde{E}$, and the counterfactual coupling is their joint probability function.  
In Proposition 1, if I understand correctly, the main point is that given a function $\Gamma$ that is (almost everywhere) invariant to the environment parameter then good generalization error of this function would also imply good extrapolation error. This feels natural, however, if this is indeed the case, I find it hard to understand the formulation of the difference equations in Prop 1. In particular the equalities between the different $G$, and what is a link function? The definition of E-invariant should be defined properly; e.g. , what does "can be sampled" mean? 

The authors then turn to look for $E$-invariant graph functions $\Gamma$. Theorem 1 then introduces certain assumptions under which it is possible. I could not understand the conclusions in this theorem. The assumptions basically mean that subgraphs of $G^{\text{obs}}$ can be seen as sampled from smaller $n$. Does that mean different $E$ is already available by just sampling subgraphs of the observed data? Using these assumptions the authors prove in Theorem 2 that a certain version of subgraph counting provides such an $E$-invariant function. Again the definitions in this Section (3.1) were unclear. They also discuss an extension to graphs with features using some common GNN architectures in Section 3.2. I found this section also hard to follow. The paper concludes with experiments using these feature maps to demonstrate extrapolation properties.

I think this paper presents a potentially interesting model and some initial results as to what kind of conditions allow extrapolation. However, this paper suffers from what I find as a bad exposition. It assumes familiarity with causality theory, and lacks clear definitions, statements, claims and explanations. I really struggled understanding the different parts and cannot say I fully understand them. I needed to guess many details and I am not sure i got it right. I think that to make this paper useful for the community a rather complete rewrite should be done. 

A more concrete concern I had is that I was under the impression that the type of assumption required (in Theorem 1) for building $E$-invariant representations basically means that we have access to different size graphs (through the sub-graph assumptions)  and therefore extrapolation to smaller sizes is possible. I would be interested to know if we can extrapolate to larger graphs in this case. 
Lastly, subgraph counting is computationally and memory demanding. Maybe empirically quantifying the cost ($k$?)-extrapolation tradeoff could be useful. 

review_title: Interesting paper, rough exposition 

Meta-review: The paper introduces a new extrapolation problem for graph representation learning (they refer to it as ' counterfactual modeling').
While the problem set-up is intriguing and the work likely has merit,  two reviewers (R2 and R4),  found the writing highly problematic and we share their opinion.  Even though some of the concerns they raised, as followed from the rebuttal, were not correct, this confusion, in our view, is largely due to the exposition.  Both these reviewers are experts in geometric deep learning. Their lack of understanding even of relatively central points of the paper, despite clearly investing a large amount of time in reading the paper, indicates that extra work is needed.  The only positive reviewer marked his confidence as very low, provided a rather short review, and did not choose to champion the paper.

While the authors tried to address the reviewers' concerns both in rebuttal and by revising the manuscript, we still feel that much more work is needed before it can be presented at a conference. We understand that this is a challenge to present this work in a conference format; it builds on the diverse background (e.g., in graph representation learning and in causal modeling) and considers a novel setting. However, we still feel that it could have been done much more successfully. In principle, this work may benefit from being presented in a journal paper (e.g., jmlr).
Decision: Reject