Node Classification in the Heterophilic Regime via Diffusion-Jump GNNs

Q6. Jumps $J^k = (V,E_k)$ are graphs, we should indicate that at the end of the first sentence of the paragraph Exploration by parallel Jumping. Filters $\mathbf{J}^k = (V,E_k,C_k)$ are just attributed graphs. Thank you again for making this point more clear in the new version.

Q7. In section 4.1, we state that: In Appendix B1, we also give practical evidence of the need to solve Trace-Ratio problems in an SGD context, instead of solving the original Trace problem in Eq.2. We also justify the convenience of conditioning $\mathbf{U}$ to $\mathbf{A}$, $\mathbf{U}=f_{\theta}(\mathbf{A})$. Actually, this setting is inspired by how the LINKX method exploits the graph topology.

We clarify this point in a pdf in the supplementary Rebuttal_PDF.pdf

Q8. This claim is referred to the fact that we are outperformed by FSGNN using 8 hops. Please, note that our method is shallow. We want to emphasize that certain types of graphs require a higher number of labels in order to obtain a more precise classification with a single layer. The discussion of multiple-layered Diffusion-Jump GNNs is in progress.

Thank you so much for your constructive and encouraging comments. Below, we address your recommendations. Please do not hesitate to ask more questions during the discussion period.

W1. In the paper, we used a couple of figures (Fig. 1 and Fig. 2) to illustrate respectively the concepts of structural heterophily and jumps hierarchy. These two elements summarize the key contributions of the approach.

W2. The $\mathbf{J}^k = (V, E_k, C_k)$ are referred to as "filters" by following MixHop [Abu-El-Haija et al. (2019)]. In MixHop, the filters (which are actually powers of the transition matrix) are not learnable. However, we explicitly use $\mathbf{J}^k = (V, E_k, C_k)$ to emphasize that each edge of the so-called "Structural Filter" is endowed with a learnable weight (see Fig.3 where the tridimensional functions illustrate what extent these coefficients define the support of a filter).

In addition, there is a relationship with graph signal processing: we learn the Fourier Transform of the graph. We are not learning the eigenvectors of the adjacency matrix but those of the normalized Laplacian which are equivalent in reverse order to those of the transition matrix.

W3. Concerning the novelty, we are aware that the idea of learning a filter bank is in the literature: see for instance MixHop. However, the value of our approach is a technique for learning the shape of these filters, i.e. the coefficients $C_k$. To sum up, note that in this paper the term "Structural Filter" refers to a learnable attributed graph.

Regarding structural heterophily, please see the answer to the Q3.

W4. Due to the limitations of space, we decided to introduce the concepts of structural heterophily and Jumps vs Hops to motivate our approach.

Q1. Yes, you are right, the correct formula is: $\ell^{\ast}=\arg\min_{\ell\neq\mathbf{0},\ell\perp\mathbf{1}} \ell^T\triangle\ell$, as in the beginning page 4.

Q2. The hidden graph $G'= (V,E')$ encodes the ideal/hidden rewiring of the original graph $G=(V,E)$ where the edges $E'$ mostly link homophilic nodes. Since this is an ideal representation, we only show it in Fig. 3 (Embeddings) as a means of visualizing the homophiliation process.

The relationship between this hidden rewiring and the jumps is as follows. Each jump is a graph, i.e. one of the $K + 1$ versions of $G'= (V,E')$. In this regard, Diffusion-Jump GNNs work as a non-linear combination of parallel rewiring. However, we do not originally mention this interpretation for the sake of clarity.

Q3. As you noted in W3, structural heterophily is related to edge homophily. However, this relationship is not as straight as you suggest. Edge homophily simply counts the number of homophilic edges, independently of how they are located in the graph. For instance, intra-class heterophilic edges are quite structurally different from those in the bottleneck: the first ones are more difficult to bypass than the natural heterophily arising from the bottleneck. Bottleneck heterophily can not be avoided, but edge heterophily counts these edges and overestimates the difficulty of the problem.

Our proposed metric focuses on those intra-class edges and discards bottleneck edges (see Fig.1 A, where structural heterophily is one). The denominator in our metric is the Fiedler value, whereas the numerator is close to one of the eigenvalues of the Laplacian. As a result, our measure approximates the ratio between two structural variabilities. Which is quite different from counting edges.

Q4. To begin with, $\bar{A}$ is a partition, not an adjacency matrix: $\bar{A} \cap A = \emptyset$. Actually, the white node in Fig.2 belongs to $\bar{A}$. Then, the notation $\bar{A}$: $\bar{A}\subseteq \bar{A}_1\subseteq \bar{A}_2\subseteq\ldots$ indicates the level sets depicted in Fig.2 bottom.

Answering your question, $\mathbf{u}_1,\mathbf{u}_2,\ldots$ lead to energies $\mathbf{u}_1^T\triangle\mathbf{u}_1$, $\mathbf{u}_2^T\triangle\mathbf{u}_2,\ldots$

In addition, we are aware that the Fiedler is independent of any labeling. And this is why it is the denominator of our proposed measure. Homophilic graphs tend to have the same energy (numerator) as the Fiedler vector: labeling meets optimal structural partition. In the heterophilic regime, however, it is very likely to have energies (denominator) larger than the Fiedler value.

Concerning the sharpness of the Fiedler vector, it is well known that the smaller the bottleneck, the sharper the partition. But you are right: the sentence "the new Fiedler vector" should be "the new vector" and it is corrected in the new version, thank you for your awareness.

Q5. We wanted to discriminate between the parameters of the MLP $f_{\theta}(\mathbf{A})$ and the parameter $\Theta$ of the full model.

I thank the authors for the detailed rebuttal. I acknowledge your efforts in the rebuttal phase and here is my response and some further suggestions.

1. Incorporating review comments into the revised version should be very helpful. In my personal evaluation, the current version is still not ready to be published in one of the top machine learning conferences so I will keep my score.
2. Avoid using too much jargon/terms, e.g., "hidden graphs", which are distracting. Try to introduce your core ideas and techniques with minimal but sufficient terms/jargon, in my view. Also, for the term "jump" matrices, I still believe that they cannot be termed as filters. In graph signal processing, filters have a clear definition (an analogy from the classic Fourier analysis). A possibly better term is propagation matrix (if I understand correctly).
3. Ask your colleagues/collaborators who are not familiar with your work to proofread and check if all the terms/notations are clearly defined and introduced.

General response . We are deeply discouraged because the review is not very constructive in order to start a discussion. The summary has one line, the paper is judged to be written in a hurry and the decision is "binary" (seems irrevocable). The review seems more a subjective proofreading than a objective scientific judgement.

However, we politely ask the reviewer to engage in a constructive discusion on the ligth of the responses to his/her questions beyond bold format statemets such as "This is not how an abstract should be written".

W1. Paper poorly written. What exactly you don't like from the paper? How can we improve it?

W2. In a hurry. Well, from the abstract to the supplementary stuff there is a formal construction flowing from intuition to inspiring methods and stopping at the contribution. We ask the following scientific question: Could a GNN learn the eigenvectors of a graph and use them for node classification? This is not a minor question (no work in the literature does this: eigenvectors are usually pre-computed). As this is not a minor question it deserves a motivation (measuring heterophily in a different way) and the use of the eigenvectors in a node distance. Having the distance to hand we explore in parallel different level-sets to solve the semi-supervised node-classification task.

Q1. Abstract is within the limits of the template. The abstract has 3 stages: motivation (heterophily), technique (related to the state of the art) and optimization problem (trace-ratio) with experimental results.

Q2. Difference between $f_{\Theta}$ and $f_{\theta}$. $\Theta$ refers to the whole parameters of the GNN whereas $\theta$ refers to the MLP parameters. What other confusios do you see?, please let us know.

Q3. What is $\ell$? $\ell$ is defined in the first paragraph of section 2; it is a labeling. After that, we define $\ell^{\ast}$. as the optimal (minimal energy) labeling.

Q4. Jump Hierarchy and expansions (page 4). $\bar{A}$ is a partition of the vertex set: $\bar{A} \cap A = \emptyset$. Actually, the white node in Fig.2 belongs to $\bar{A}$. Then, the notation $\bar{A}$: $\bar{A}\subseteq \bar{A}_1\subseteq \bar{A}_2\subseteq\ldots$ indicates the level sets depicted in Fig.2 bottom. This is a refinement. Then, $\mathbf{u}_1,\mathbf{u}_2,\ldots$ lead to energies $\mathbf{u}_1^T\triangle\mathbf{u}_1$, $\mathbf{u}_2^T\triangle\mathbf{u}_2,\ldots$ and they are unstable because their energies are lower bounded by the optimal one (the ground energy). $\mathbf{u}^T\triangle\mathbf{u}$ defined by the Fiedler vector $\mathbf{u}$.

Q5. Structural filters are weighted graphs, i,e, tuples $\mathbf{J}^k=(V,E_k,C_k)$ where $E_k\subseteq E$ and $C_k$ are the learnable coefficients of these edges. By the way, the concept of structural filter is introduced in the abstract.

There are $K+1$ filters because the last one is the original graph to capture the full homophilic case (Homophilic branch: see in the last paragraph of section 4),

Q6. Actually the filters are rewirings.

We hope that these clarifications engage the reviews in a discussion.

Answer 1, It would be good if the authors can clearly summarize the novelty and contributions of this paper.

We learn the smallest eigenvectors of the Laplacian and estimate diffusion distances for node classification. This is a unique method in the literature: from a point of view of "algorithmic reasoning", we compute eigenvectors using GNNs. By doing so, we bridge spatial and spectral GNNs.

Answer 2. There are efficient ways to compute the Fiedler vector.

What methods? Krylov/Power method cannot deal with large graphs. This is why we "learn" them. Please, try to pre-compute these quantities using the current algorithm for a graph of 170,000 nodes such as arxiv-year. In addition, these graphs are not connected and a standard algorithm will fail. Moreover, having the learned eigenvectors to hand we can estimate the diffusion distances.

Answer 3 I urge the authors to write professionally to avoid any misunderstandings.

I am professional enough to answer this question.

Answer 4 Reviewer q3r3 has similar concerns as mine. As a lot more work is required of this paper, I am keeping my score.

Thank you. I politely protest against this type of reviews: destructive, uninformative and not helpful at all. Congratulations for your successful blockage. It is a huge damage to the conference.

Thank you so much for appreciating our proposed method and our experimental results. Below we try to respond to your questions. Please, do not hesitate to add more comments during the discussion period.

W1. We are aware of that and due to space limitations, we have explained the methods inspiring our approach in the Appendix. We also include some experiments with SBMs.

W2. Sure. See answers to Q1 and Q3.

W3. We have split the basic maths (in the paper) from the more difficult maths (in the appendix). Regarding the interpretability of the approach for wide use: (1) diffusion distances are approximated by distances between eigenfunctions), (2) our approach can be seen as a learnable directional network where the number of eigenfunctions is the number of classes. However, this number can be changed (reduced or extended) to envision how the diffusion pump captures the structure of the graph. (3) Another source of interpretability is that, in addition, to show how many jumps we need and how important they are, the structural filters become rewirings of the input graph where we show the decisions taken by the GNN to homophiliate the graph (i.e. to construct the latent space. Note the process shown at the bottom of Fig.3).

W4. Concerning the stability, it is important to note here that the diffusion pump has a double role: (a) it generates eigenfunctions, and (b) it reduces the structural energies (if needed) of the modifications proposed by the classification loss (regularization). We implement a shallow network where gradients are under control. However, the interference between the Dirichlet loss and the classification loss is important during the initial epochs. Then, the Dirichlet loss converges to a basic set of eigenfunctions, and finally, after the stabilization of the Dirichlet loss, the classification loss fluctuates until convergence. We agree that we have to delve into this point, and we will do that in future papers since we honestly believe that diffusion pumps can be useful modules in other GNNs.

Q1. Dealing with huge graphs is still a challenge that new GNN layers or architectures have to deal with today. In our case, creating a dense diffusion matrix forces us to use an $O(n^2)$ memory space, just as a Transformer or HO-GNNs would do. That said, in the paper we have tried to include large graphs to show that our performance is still competitive and we leave the window open so that in future work, we do not need all the distances but a selection of them. Making our method sparse and consuming less memory. Part of this sparsification effort relies on computing the eigenfunctions of the transition matrix (which involves the sparse adjacency in the trace-ratio problem instead of the Laplacian).

Q2. We believe that when Diffusion-Jump GNN can deal with graphs that have multiple nodes or edges. One possible way is to follow the "role2vec" approach (https://arxiv.org/pdf/1802.02896.pdf): compute the transition matrix between types of nodes (for instance) and then rely on this transition matrix. A similar approach can be applied to the line graph of the original graph if there are multiple types of edges. Finally, for a multigraph, we should create a diffusion pump for each particular type of edge.

Q3. Yes of course, as we said in Q1, we left the window open so that in the future we can work in a more sparse way and also improve the performance. As to the question of whether we are planning on expanding it for other tasks, the answer is yes, we are currently looking at how these eigenfunctions behave and the distances they generate in link prediction. Since we are observing that they do not react in the same way as in node classification task, because these functions have to capture the nature of the graph, instead of changing it as we do in this work in order to connect distant nodes of the same class. Our preliminary experiments in link prediction show that we can replace the diffusion distance matrix by the concatenation of the matrix of features with the eigenfunctions. This allows us to deal with graphs with $0(10^6)$ edges. What we want to emphasize here is the power of empirical eigenfunctions.

Overall, we are happy to answer more questions during this discussion process.