Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper provides a spectral analysis perspective on the expressivity of GNNs. The analysis is done under the assumption that graphs differ in at least one eigen value. The paper claims GNNs can achieve separation power greater than 1-WL by augmenting the node feature with appropriate choices and demonstrate the disadvantages of using an all-1 input vector. The authors suggest augmenting the input to the GNN with the diagonal of powers of the adjacency matrix to improve expressive power.
strength_and_weaknesses: ### 1. Strengths

- The paper provides expressivity analysis from a spectral perspective. 
- The authors show that using random input features and a covariance operator yields a GNN model that is more expressive than 1-WL and show equivalence to a model that sidesteps the need to use random features. This result bridges betweenthe role of random features and substructure input features in increasing expressivity of GNNs.

### 2. Weaknesses

1. **Novelty**

   The paper suggests to augment the node features with the diagonal of adjacency powers, which are, the k-cycle couts (with repeatitions) for each node in the graph. This idea has appeared before e.g., in [1] that generally proposed to add information on subgraph isomorphism counts including cycles. Altough the proposed model was derived from a different thoretical perspective, I believe the novelty of the proposed model is quite limited.  The authos do not cite [1]. Can the authors provide a discussion upon relations of their work to [1]?

2. **Model complexity**

   Theorem 2.2 implies that in order to distinguish between two graphs the filter length should be at least $q$, the size of the set of all unique eigen values in the union of both graphs’ eigen values. This number grows with the number of nodes in the graph and could impose high complexity for large graphs. 

3. **Too strong claims**

   The authors repeatedly state that the analysis of the expressive power of GNNs is limited to the case of an all 1 input vector. However, lots of works extended this result and the authors overview them in the related woprk section. I would suggest that the authors soften their claims dismissing other works that have already been done. 

4. **Experimental Evaluation**

   Experimental evaluation is not convincing enough. The proposed method shows comperable performence to GIN where the improvement is insignificant. The results on the CSL dataset are not surprising, again since properties of the cycle counts features has already been analysed in [1]. Furthermore, [1] outperforms the current model across all social and biological datasets.

   

[1] Bouritsas, G.; Frasca, F.; Zafeiriou, S.; Bronstein, M. M. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. arXiv July 5, 2021.

### 
clarity,_quality,_novelty_and_reproducibility: 1. **Clarity of proof of Theorem 2.2**

   Theorem 2.2 is fundamental in the paper and I find its proof a little confusing. I suggest the authors add an explicit statement saying that the constructed filter distinguishing two graphs is required to be of length $q$. Adding an example would also be nice. 

2. **Novelty**

   See above. 
summary_of_the_review: I think this work provides an interesting view on the analysis of GNN expressivity. However, the final proposed model lacks novelty and the experimental evaluation is not convincing enough. 

I therefore think this paper is below the bar for ICLR but will consider raising my score upon addressing my concerns.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper uses the spectral decomposition perspective to study the expressive power of GNNs. It argues that the 1-WL is not the real limit of GNN expressiveness. Instead, it only serves as the limit when we use all-one vectors as input features. Further, this paper proposes a new model, which uses features derived from powers of matrix representations and can be more expressive than regular GNNs.
strength_and_weaknesses: Strengths:

1. The motivation of analyzing GNNs from the spectral decomposition view is good.

2. The analysis of using random input features can help improve expressiveness is great.

Weakness:

1. The fundamental assumption that 1-WL only serves as the limit when using all-one vectors as input features is not clearly correct to me. Specifically, to prove that 1-WL is the limit of GNNs in the GIN paper, the only assumption is that the input feature space is countable. In other words, the input features do not have to be all-one vectors to achieve the proof. Hence, it is unclear to me why this fundament assumption hold in this paper.

2. The proposed new model uses features obtained from powers of matrix representations. However, the similar idea has been investigated in exiting work, such as SIGN [1]. Hence, the proposed model is not novel from this view.

[1] Rossi, Emanuele, et al. "Sign: Scalable inception graph neural networks." arXiv preprint arXiv:2004.11198 7 (2020): 15.

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The novelty of the proposed model is limited but the analysis is good. Some assumptions are not well supported.
summary_of_the_review: Overall, I think this work has merits in terms of the motivation and the analysis. However, the technical assumption and contribution have not met the standard of ICLR.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: GNNs are known to have a discriminative power of at most 1-WL algorithm in the graph isomorphism problem. This paper pointed out that this result assumed that inputs are the all-one vectors and analyzed the expressive power of GNNs in the graph isomorphism problem when inputs are not necessarily all-one.
First, this paper gave sufficient conditions on the spectrum of the adjacency matrices and the input vectors for a GNN to discriminate between two non-isomorphic graphs (Theorem 2.2). In particular, it was shown that this condition held when inputs were an appropriate number of Gaussian random noise (Proposition 4.1). Also, the condition is achieved when inputs are numbers of cycles of appropriate length in the graphs (Theorem 5.1. Theorem 6.1). 
strength_and_weaknesses: Strengths
- Sufficient conditions (Assumption 2.1) are general and have broad applicability.

Weaknesses
- Mathematical arguments are somewhat informal, and the description has room for improvement.
- Experiments on real data have not shown that the proposed methods (in terms of both architectures and input features) are practically effective on prediction tasks on graphs.
clarity,_quality,_novelty_and_reproducibility: Clarity

I think there is room for improvement in the architecture description and mathematical claims.
In several theorems (Theorem 4.1, Proposition 4.1, Proposition 6.1, Corollary 6.2), the architecture is explained only schematically using figures. For example, there is no explanation in the main text corresponding to the type-1 architecture in Figure 4. While figures enable us to understand concepts smoothly, they are auxiliary tools and unsuitable for accurate discussions. The architecture should be explained in the text to exclude ambiguity.

I would suggest writing about how a GNN determines whether two graphs are isomorphic based on the output signals obtained from an input pair of graphs (e.g., in Theorem 2.2). Judging from the proof, the GNN decides two graphs are isomorphic if and only if there exists a permutation matrix $\Pi$ such that $Y'=\Pi Y$, where $Y$ and $Y'$ are the outputs of input graphs $G$ and $G'$, respectively (this is efficiently computable by sorting the value of $Y$ and $Y'$)

Theorem 4.1 and 6.1 claimed that two GNNs are "equivalent" but did not define "equivalent" mathematically. Therefore I would suggest writing its formal definition.

(minor comments) Contribution (C2) claimed that "the WL algorithm is a limit [...] only when we use the all-one vectors as an input". Strictly speaking, this is not strictly true. It is true that the WL algorithm is upper bound when we use the all-one vector. However, it is not shown that the converse holds, i.e., there is the possibility that inputs are not all-one and the expressive power is lower than the WL algorithm. 


Quality
Contribution (C3) claimed that GNNs have a higher discriminative ability when "node features are initialized with random white noise." However, I think this is a slightly confusing expression. In my understanding, white random noise input means that we draw a sample from a Gaussian distribution and feed the sample to the GNN. However, the GNN in Figure 3(a) takes the expectation of the input variable. This operation is impossible from a single realization of a random variable $x$. It requires the information of the random variable $x$ (e.g., distribution of $x$).

Experiment results (Table 4) showed that the proposed method was not superior to the baseline when all-one vectors were used. Since this study has a theoretical nature, I do not think this result does not solely incur the significance of this study significantly. On the other hand, I believe we can obtain many implications from this result. For example, there is a gap between the theoretical graph homomorphism identification capability and the practical prediction accuracy on graphs. I would suggest discussing what we can learn from the numerical evaluations.


Novelty

Several studies theoretically and experimentally enhanced the representational capability of GNNs by enriching the graph input (e.g., [You et al., 21], [Ishiguro et al., 20] and reference therein). Moreover, some of them have theoretically shown that GNNs they proposed have better discriminative power than the 1-WL algorithm in the graph isomorphism problem. Therefore, I think the novelty of this study concerning the strategy of improvement is limited. On the other hand, focusing on graph spectra is an good approach because, as far as I know, few studies pay attention to it. In addition, Assumption 2.1 for the identification is general in the sense that many graph pairs satisfy this condition.

[You et al., 21] https://ojs.aaai.org/index.php/AAAI/article/view/17283
[Ishiguro et al., 20] https://arxiv.org/abs/2006.06909


Reproducibility

This paper provides the references and specifications of the datasets. Also, the code URL and hyperparaemters are available in the appendix. Therefore, although there is no guarantee of perfect reproduction, I think we can implement the code to reproduce the experiments to some degree.


Questions

Looking at theoretical analyses (e.g., Theorem 4.1, 5.2, and 6.1), I am wondering whether they imply that we can increase the discriminative power of the WL algorithm by adopting the numbers of cycles of length $k$ ($1\leq k\leq K$) for an appropriate $K$ as the initial colors?
summary_of_the_review: The sufficient conditions derived in this paper for a GNN to discriminate a pair of non-isomorphic graphs are flexible. On the other hand, enriching the input of GNNs may not be a novel approach in the theoretical analysis of the expressive power of GNNs. In addition, the statements and architectural descriptions are somewhat informal, and there is room for improvement.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper obtained low scores from the reviewers, even after a long discussion where the authors had time to argue their case. After reading the paper and reviews, I want to first encourage the authors to continue to pursue this line of work. Indeed, mainstream expressivity papers make assumptions that are strong and which are often not met in practice. Hence, the author's research is important. However, as rightfully criticized by the reviewers, the authors did not succeed in placing their work in the context of prior work that did not only consider all 1 vectors. There is also generally room for improvement in motivating the method and a lack of clarity in describing the method. Finally, the experiments are not very convincing in that there is only a minor, potentially insignificant improvement of their model compared to the state of the art. I don't believe, however, that this is a fundamental problem as long as the motivation, related work, and formal analysis of the method are improved. 
justification_for_why_not_higher_score: All reviewers tended towards rejecting the paper. Two reviewers have a strong opinion about the paper having to get rejected. Especially one of these reviewers participated actively in discussions.
Decision: Reject