Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper presents an insightful analysis of the induced graph filters in GNNs. To accommodate the heterogeneity of graphs, the authors provide a family of novel GNNs for learning data-specific filter banks. Overall, the introduction part is well written, and the studied problem is novel and interesting. However, the technical part of this paper has some issues: (1) the contributions of this paper are over-claimed, (2) the theoretical analysis and algorithm are disconnected, (3) mistakes in the theoretical results. 
main_review: Here are the detailed comments:

[Problem] Very nice introduction and literature review. The problem is novel and interesting.

[Notation] The notation set shall be largely simplified. For example, y_i, c_m, r_i all refer to the node labels. 

[Typos] There are typos throughout this paper. For example, missing space in the 9th line of Sec 3.3; in Sec 3.4, graph frequency -> graph frequencies? For {\alpha_i = <u_i, x>}_i, why does the index i appear in both the inside and the outside of the parentheses?

[Theoretical Analysis] In sec 3.3, the authors claimed that \phi_i^k = \sum P_{i,j}^k is the probability that a random walker starting from v_i and stays in C_l. Based on my understanding, \phi_i^k does not exclude the case that the random walk traverse outside of C_l. Same in the Def. of interaction probability. Does the interaction probability also consider the case that random walk traverse to some other communities (different from l and m)? If so, please provide the justifications - what is the motivation and rationale of these formulations. 

[Proposition 3.1] There lack of insightful discussions about Proposition 3.1. What are the physical meanings of g(\Phi) and g[\Phi]? What does Proposition 3.1 tell us? And, what is the connection between Proposition 3.1 to the proposed algorithms?

[Confusiong Notions] In Def. 3.2, what do you mean about the distributional representation? The authors may want to provide further explanation. In Proposition 3.2, "f be the frequency of signal x" --> "f be the frequency distribution of signal x"?

[Over-calimed Contribution] (1) The low-pass/high-pass filters seem very similar to "Beyond Low-frequency Information in Graph Convolutional Networks". Moreover, the authors shall provide theoretical proofs to show why the g_b is a band-pass filter. (2) The authors claimed that this paper provides a "data-driven" mechanism for filter bank selection, which is not well described in the algorithm description. (3) the theoretical analysis and algorithm feel disconnected. 
summary_of_the_review: The studied problem of this paper is interesting, while there may exist some issues in the theoretical foundation of the proposed algorithm.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: It is observed that for Graph Neural Networks (GNNs), the correlation between the labels and the graph structure matters. The paper gives a theoretical analysis of this behavior via interaction probability and frequency distribution. The analysis shows why homophily is favorable for GNNs. Additionally, they are also able to identify some conditions when GNNs can do well. But the key point made is that it is not possible to cater to all possible scenarios with a single filter. The paper further goes to propose a model that builds multiple band-pass filters over the range of [-1, 1] and then aggregates information over these filters to give improved performance.
main_review: The paper is well-written and clear to understand.

## Strengths:
1. The theoretical analysis looks clean and simple. Equation 6, 7, 8, 9 and 10 provide a good indication of how the prediction error is dependent on pi_l. It also gives insight into the homophily requirements for good performance.
2. The proposed model is simple and gives good performance on datasets of varying homophily scores.

## Weaknesses:
1. The error analysis is done on MSE rather than Softmax (which I suspect is what is used in the experiments). However, this doesn't take away much from the presented work and the analysis still feels insightful enough.
2. The motivation for disentanglement block is unclear. The paper states *Theoretically, piling up sufficient numbers of graph filters to capture all the frequency components can improve prediction performance. However, it is very expensive. To avoid this problem, we consider feature disentanglement - essentially, it is to disentangle frequency distributions of features into different families. Features in the same family are expected to have similar spectral properties, that is, they have similar frequency distributions or have overlap on their main frequency bands.* While it is clear that it will be difficult to have large number of band-pass filters, it is unclear how disentanglement of features work to avoid this scenario.
3. Implementation of disentanglement seems to be just random masking. How does it satisfy the statement made *Features in the same family are expected to have similar spectral properties* ?
4. The motivation for P-DEMUF is pretty clear, but the T-DEMUF architecture motivation is not clear and there is no mention of it anywhere. Also, the equations of T-DEMUF are somewhat confusing. It feels like there might be a typo there, at least by looking at Figure 1.
5. GPRGNN by [Chien et. al] is missing from baseline comparison.

In light of the above, I am inclined to rate this paper marginally below threshold. 

There are few typos in the paper:
1. Var(f_l) in Section 3.4 and in other places it appears has a mistake.
2. Equations for T-DEMUF likely have a typo in there.

**References:**

Eli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. ICLR, 2021.
summary_of_the_review: The paper is well-written and clear to understand. Theoretical analysis is clean, simple and gives interesting insights. The results are also very strong with good improvements on several datasets. However, there are several weaknesses in the paper A] the motivation for the disentanglement block is unclear B] it is also unclear how simple random masking achieves disentaglement C] The motivation for T-DEMUF is unclear as well and D] a very related baseline by [Chien et. al] is missing from comparison.

In light of the above, I am inclined to rate this paper marginally below threshold. 

**References:**

Eli Chien, Jianhao Peng, Pan Li and Olgica Milenkovic. Adaptive Universal Generalized PageRank Graph Neural Network. ICLR, 2021.

---

Update post response phase:
Having gone through other reviews, it seems that there maybe a lack of clarity in the paper, particularly on the theoretical aspects. I admit it was a bit of an effort to keep up with all the notations and the paper will definitely strengthen by bringing in lot more clarity in notations. 

Having said that, I would like to add that although the conclusion of the work may not be new, but new perspectives for the same conclusion should not be discouraged. In mathematics, we have multiple proofs for a single statement like "There are infinite number of primes" [A], each of them brings a new perspective and has something to offer. I believe that we would be doing a disservice if we rejected papers simply on the basis that conclusion is not new, without really analyzing if the paper is offering a newer fresh perspective or not.

However, beyond these issues, I believe it is important to assess the actual model strengths as well. This is mostly where I find many things not so clear, for example, the feature disentanglement aspect is not clearly explained. Also, how does T-DEMUF work is not very well explained and what is the exact motivation for T-DEMUF is also quite lacking. 

In light of these, I am inclined to retain my current assessment of marginally below acceptance threshold.

[A] https://primes.utm.edu/notes/proofs/infinite/

---

Update post second response phase:

The authors have addressed all my issues. However, the outcome is the following:
1. The notations have to be improved in the paper
2. Explanation and motivation for disentanglement has to be added to the paper
3. Explanation and motivation for T-DEMUF has to be added to the paper.

However, I believe these should not be difficult changes to make and hence I am willing to change my rating to marginally above acceptance threshold, under the assumption that the authors would make these changes in the final revision.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the applications of graph filters in graph neural networks, and attempts to understand the links between graph spectral analysis, random walks, and homophily.
The authors introduce "interaction probability" as a metric for understanding homophily and its relationship to random walk transition matrices.
In this framework, the authors claim to understand a notion of graph information, as well as an understanding of how the performance of graph filters depends on both graph structure and input signals, with applications to graph neural networks.
main_review: This paper suffers on many fronts.
I wish I could give a more thorough review of this work, but the writing is so poor that assessing the merits of this work would be quite difficult.
The authors make many statements with very little explanation.
For instance, Proposition 3.1 is largely a jumble of symbols with very little surrounding discussion: it is not explained why I should remotely care about this result.
Section 3.4 states things that are largely obvious from a graph signal processing perspective.
Definition 4.1 is a strange way to look at prediction error: why are you using a Frobenius norm to evaluate the error of a node classificiation problem?
The conclusions reached in Section 4.1 are quite obvious and well-understood in the broad literature.
Of course filters should "match the true signal," this is the most basic fact from signal processing!

The conclusion that graph neural networks should use a filter bank rather than a single filter is nothing new.
See, for instance, the work "Stability Properties of Graph Neural Networks" from Gama et. al. (2020).

Overall, the contributions of this paper are extremely lacking.
And even if there was a notable contribution of this work, the writing quality obscures it so much for it to be at all useful.
I would also like to point out that the authors failed to cite even the most widely-known introductory papers for graph signal processing, such as that of Ortega et. al. (2018).
The failure of the authors to do so indicates a severe lack of familiarity with the graph signal processing literature, which this paper claims to contribute to.
summary_of_the_review: This paper does not live up to its claims, and is extremely poorly written.
The authors spent most of their effort on this work stating obvious things in convoluted ways, amounting to very limited statements regarding graph filters.
Despite their claims of reaching "deep understanding" of graph filters, this paper achieves very little.
Due to the poor writing and shallow application of this work, I strongly recommend this paper be rejected.
review_title: null

Meta-review: In this paper, in order to theoretically investigate the relationship between graph structure and labels in GNNs, interaction probabity and frequency indicators are introduced and analyzed, and a new family of GNNs with multiple filters is proposed based on the insights from the theoretical analysis,
In the discussion, there was an opinion that the theoretical analysis is interesting, but its novelty and clarity are limited. Although certain contributions are acknowledged, the impact is marginal and the audience for which this paper will matter is rather limited.
Decision: Reject