Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a new framework of GNN which can deal with undirected and directed graphs in a unified way. The authors argue that the size of the symbol space for a message passing path with length n is 2^n, while previous architectures only have constant size. Motivated by this observation, the authors borrow ideas from Iterated Function System to augment the symbol space. 

Roughly speaking, the main idea is to use 2 linear mappings f_0 and f_1 which correspond to the two directions. For the given input vector x, in each of the n iterations, we apply one of the two linear mappings randomly (the probability of applying each mapping is a learnable parameter), and we use the expectation of the resulting vector as the representation. The authors argue that the resulting symbol space could have sufficient size if n is sufficiently large. 

The main idea looks reasonable and interesting. My major concern is about the experiment part (and thus my recommendation would just be weak acceptance) . The authors only perform experiments on three datasets, and it is unclear if the same approach will be effective on other datasets/settings. Moreover, although we see performance improvement on two of the three datasets, necessary discussion about the experimental results is missing. It would be great if the authors could explain why the proposed method improves the performance on Cora and Citeseer, and achieves worse performance compared to some of the baselines on Pubmed, to give the readers a better idea when this new framework would be effective. 

***Post Rebuttal***
I have read authors' response and other reviewers' reviews. After reading it is still unclear to me why sparsity of the networks could affect the performance of the proposed framework. Therefore I would like to keep my original score. 
review_title: Review for Iterated graph neural network system 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This work proposes a new graph neural network architecture with modified rules for message passing, Iterated Graph Neural Network System (IGNNS). The paper then provides a theoretical analysis of the proposed architecture by connecting it with Iterated Function System (IFS), an important research field in fractal geometry. This paper further demonstrates empirically that the proposed architecture outperforms related models on citation network datasets.

Pros:

1.The proposed architecture achieves empirical improvement on citation network datasets.

2.This work also provides some theoretical analysis for the proposed architecture: it analyzes the geometric properties of IGNNS from the perspective of dynamical system.


Cons:
1.It seems unclear to me how the theoretical analysis via IFS could be used to explain the empirical performance gain on citation networks.

2.According to the formulas in equation (3) and above on page 4, it seems that the mathematical expectation $E_n$ is still linear (affine) w.r.t. to the input $X^{\text{int}}$. Then if we use a learnable matrix to learn such combinations of matrices $A_i$ and probability vector $p_i$, would this be equivalent to applying an MLP to for each the message passing iteration (the adjacency information in $A_i$  is accessible to update the MLP via backpropagation)?

3.In Figure 1, how would the message passing in d) be different compared to the message passing in c) after two iterations?

4.It would be nice for the authors to provide a theoretical analysis on the computational complexity for the proposed architecture IGNNS.

5.It would be nice for the authors to provide discussions with relevant works [1-3] on graph neural networks. [1] proposes a generalized aggregation function that allows successful and reliable training of very deep GCNs and how the proposed theorems in work could unify the mixed results (as Thm 4.1 and 4.2 state that the characterization ability of IGNNS would decrease with the increase of IFS iterations). [2] proposes a method for directional message passing as well. [3] proposes a theoretical framework for analyzing which type of GNN would achieve better generalization performance on the given task, which is also related to this paper for explaining the performance gain by IGNNS.

6.The quality of the writing could be much more improved. It would be nice for the authors to provide:
a) better intuitions on its analysis using IFS (e.g. what is the physical meaning of the fractal set in IFS and why is it important). 
b) more connections between its proposed architecture and the empirical experiment section (e.g. how the proposed theorem could explain the performance gain connections)
There are also grammar mistakes in the paper which may hinder the understanding of the readers (e.g. last sentence in the abstract).

[1] Li, Guohao, et al. "Deepergcn: All you need to train deeper gcns." arXiv preprint arXiv:2006.07739 (2020).

[2] Klicpera, Johannes, Janek Groß, and Stephan Günnemann. "Directional message passing for molecular graphs." arXiv preprint arXiv:2003.03123 (2020).

[3] Xu, Keyulu, et al. "What Can Neural Networks Reason About?." arXiv preprint arXiv:1905.13211 (2019).

review_title: A new graph neural networks architecture with modified rules for message passing

final_score: rating: 4: Ok but not good enough - rejection
review_content: Overall, this paper proposes Iterated Graph Neural Network System, which provides a novel way for computing GNN messages.

However, there lack enough discussions with existing multi-layer GNNs. 
The paper mentions that "the message passing in the two directions is independent and lacks of interaction". While this is true for a single layer GNN, when the GNN is multi-layer, the messages sent in deeper layers contains fused information from multiple directions. 
Furthermore, if skip connections are used, the messages sent in deeper layers can have even richer information.
These discussions are lacking in the current paper.

Moreover, the evaluation is very insufficient.
Firstly, the paper mentions a General Framework in Section 5, including a new model R-IGNNS. However, no evaluation is made at all. I would regard the experiments as incomplete.
Additionally, there is no further analysis or ablation study provided. While the performance improvement seems to be hugel, without those analysis, it is really hard to understand where the improvement comes from.

More comments:
1 "Therefore, the above architectures can not deal with directed graph directly". I believe this is not the case: existing GNNs can naively work with directed graphs by doing message passing following the edge direction.

2 The paper mentions after Eq (3) that H^(n) has H x 2^n elements. Will it be a scalability concern?
review_title: An interesting method with insufficient discussion and evaluation

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a new definition of GNNs designed to cope with bi-directional message-passing processes.  To do so, a new symbols space, different from the one adopted by Bidirectional GCN,  is considered, together with an iterated function system. These lead to an architecture composed of 4 steps: an input layer that acts as a classic FC layer; an IFS layer that applies the iterated function system considering the adjacency matrix; a layer to concatenate or sum the expected values of each iteration; and an output layer that combines the results using the functions of the IFS and a new learnable weight matrix.
Experiments on citations datasets show significantly better results than those obtained by many different related works.

The paper proposes an interesting approach, but personally, I found the document a bit foggy in some parts. On page 2, iterated function systems are introduced, but the definition does not explain what the f_i functions are, how many functions there may be and how the probabilities are related to the functions. This detail can be assumed in section 3.2 when the expected values are computed using the probabilities from the p set. However, in this section there are undefined symbols, such as p_{00}, p_{01}, etc., which make it difficult to follow the explanation of the step.

In section 3.2, a short discussion of the value of n (the number of iteration) should be added to say whether this value depends on the input graph, on the values of the H matrices in each iteration or something else.

In section 3.3, to compute the global representation R one can decide between two different definitions. These two definitions are very different and combine the results of each iteration. However, it is not clear to me how I should decide which one to use. I would like to see in the paper an explanation of what they represent and why it is more useful to calculate an average or a concatenation of the results of each iteration instead of considering only the results of the last iteration (which should depend on all the previous one).

As regards the experiments, the results seem promising, but information on trining time should be added.
Unfortunately, however,  the description of the datasets used is too simplified.  It should explain how the nodes are extracted from those available in the datasets and why only 20 nodes per class are extracted. It seems that only very few nodes are considered despite the availability of a large number of them. In addition, details about the edges connecting the nodes and the features can also be useful, as not all the edges/features will be considered since only 20 nodes per class are used. It is necessary to explain if these nodes belong to only one class or to several classes because there could be unbalance problems. Also, it is not specified which function is used in the representation layer.
It would be interesting to understand what happened for the Pubmed dataset. Probably the result depends on the small percentage of nodes considered.

Pros
- The results seem interesting

Cons
- Overall the proposal seems interesting, but its description lacks important definitions.
- Code and datasets are not available. Unfortunately, this does not help to evaluate the proposal.

Typos
The second line of section 3.4: labels instead of lebels
In theorem 4.2 furthermore instead of further more
In the references, arXiv URLs are not well-formed.
review_title: The description of the proposal could be improved

Meta-review: Reviewers found the new framework interesting. However, reviewers are unsatisfied with empirical evaluations. More experiments and discussion are needed.
Decision: Reject