Spectral Highways: Injecting Homophily into Heterophilic Graphs

Authors: Karan Goyal, Saankhya Samanta, Vikram Goyal, Mukesh Mohania
Primary area: learning on graphs and other geometries & topologies
Keywords: Data augmentation, Graph representation learning, GNNs, Homophily, Heterophily

Abstract:
It is widely assumed that standard GNNs perform better on graphs with high homophily, leading to the development of specialised algorithms for heterophilic datasets in recent years. In this work, we both challenge and leverage this assumption. Rather than creating new algorithms, we emphasise the importance of understanding and enriching the data. We introduce a novel data engineering technique, \textit{Spectral Highways}, that enhances the performance of both heterophilic and non-heterophilic GNNs on heterophilic datasets. Our method augments a given heterophilic graph by adding supernodes, thereby creating a network of highways connecting spectral clusters in the graph. It facilitates additional paths to bring similar nodes closer than dissimilar ones by reducing the average shortest path lengths. We draw both intuitive and empirical connections between the relative decreases in intraclass and interclass average shortest path lengths and shifts in the graph's homophily levels, providing a novel perspective that extends beyond traditional homophily measures. We conduct extensive experiments on seven heterophilic datasets using various GNN architectures and also compare with data-centric techniques, demonstrating significant improvements in node classification performance. Furthermore, our empirical findings highlight the strong sensitivity of several recent GNNs to the random seed used for data splitting, underscoring the importance of this often-overlooked factor in GNN evaluation.

Decision: reject
Reviewer scores: 3, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730593674317

thread_type:
official_review

<thread_object>
creator: reviewer_dhkq

<content>
summary:
This paper aims to propose a technique for better performance on heterophilic graphs.
The authors introduce additional virtual nodes to the graph that improve the connectivity of the nodes within clusters.
The experiments are conducted on seven heterophilic graphs.

strengths:
1. The idea is simple and works well.

weaknesses:
1. This paper is written poorly.
2. There is not enough justification for the design of the proposed method.
3. There is no ablation study in the experiments.

questions:
1. The introduction is written poorly. There is no paragraph pointing out the existing challenges of node classification on heterophilic graphs. This makes the last paragraph of contribution very abrupt and lacks motivation. I would recommend adding a paragraph pointing out the current challenges.
2. Again, the related works provide little context or motivation with respect to the proposed method. As this is not a survey paper, these paragraphs are not helpful. This section should serve as a motivation for proposing your work.
3. In line 158, in heterophilic networks, vertices with high similarity are usually 2 steps away. “Far away” is an ambiguous description.
4. Figure 1 does not look like a heterophilic graph, as most edges are connected by the nodes with the same label.
5. The connectivity between the spectral nodes seems redundant. It would be helpful to have an ablation study of removing all the edges between the spectral nodes. Moreover, there is no ablation study at all.
6. In Table 2, most baselines have different base GNN models and make the results not comparable. Dir-SAGE and SH (Dir-SAGE) seem to be comparable, but the results are statistically tied.
7. Section 6 should be moved forward to be right after the proposed method section, to justify the design of the proposed method. However, most analyses are indirect to the reason for performance improvement, and do not help understand why the method works. A theoretical analysis would largely improve the completeness of the paper.
8. In Table 7, using SH hurts the performance in the homophilic graphs most times. In real-world, given a graph with limited labels, knowing whether it is homophilic or heterophilic is not an easy problem. This is important but also not discussed in the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730669380292

thread_type:
official_review

<thread_object>
creator: reviewer_br69

<content>
summary:
This paper proposes a new technique called Spectral Highways that is designed to improve the performance of GNNs on heterophilic datasets. Namely, supernodes are added to the graph, each supernode is linked to a particular cluster and supernodes are linked to each other. This allows better information exchange between different regions of the graph.

strengths:
The idea proposed in the paper is reasonable and improves on the concept of virtual nodes.

weaknesses:
- Most of the datasets used in the experiments are small and have certain flows. Namely, Cornell, Texas and Wisconsin are extremely small and are unbalanced (so, accuracy should not be used as a performance metric). Then, Squirrel Filtered and Chameleon Filtered are used by Platonov et al. (2023) to illustrate the flows of the original Squirrel and Chameleon and are not advised for further usage. The new datasets proposed by Platonov et al. (2023) are not used in this paper. Similarly, only one dataset from Lim et al. (2021) is used. The authors write that "We could not take other datasets like pokec, genius, wiki, etc., as their experiments ran out of memory, and twitch-gamers due to resource constraint." Does this apply to all models? For instance, Platonov et al. (2023) use several simple models that show good results on their datasets. The absence of experiments on realistic datasets reduces the reliability of conclusions made in the paper.
- From the description of the proposed approach it is not clear why one would expect it to work on heterophilic datasets. In particular, it is not obvious why it should improve homophily. As I understand, new edges are added independently of whether they are homophilic. Thus, it seems that edges with neutral homophily are added which agrees with the results reported in Table 3: adding neutral edges to heterophilic graphs makes them more homophilous (adjusted homophily, in most cases, becomes closer to zero), and adding neutral edges to homophilic graphs makes them more heterophilous (again, adjusted homophily becomes closer to zero).
- In lines 208-232 the authors discuss several options for their algorithm and write that it is not always the case that the intuitive option works and thus all the options need to be tried on a particular dataset. Thus, the proposed approach is not so well supported by the intuition described in the text.
- Equation (1) is claimed to be a formal mathematical description of the proposed algorithm, but it is not a valid mathematical expression and thus complicates the reading.
- If I am not mistaken, code for reproducing the results is not provided.
- Some of the ideas of the proposed approach are related to the concept of virtual nodes, so I suggest discussing related work on this topic (e.g., Hwang et al., 2022; Qian et al., 2024). For instance, similarly to the proposed approach, Hwang et al. (2022) cluster the initial graph and assign a virtual node to each cluster (however, there are no edges between the virtual nodes).

Hwang, EunJeong, et al. "An analysis of virtual nodes in graph neural networks for link prediction." The First Learning on Graphs Conference. 2022.

Qian, Chendi, et al. "Probabilistic Graph Rewiring via Virtual Nodes." arXiv preprint arXiv:2405.17311, 2024.

Minor comments:
- The range of indices in equation (8) can be fixed: $p$ and $q$ range from 1 to $C$, $p \neq q$ should be inside the formula, the comment about $i$ and $j$ also should not be outside the formula (since these are indices inside the sum).
- Table 1: For better readability, I suggest highlighting the best result not only in cases when the proposed solution outperforms the baseline.
- Table 7: I suggest highlighting the best algorithms in this table too.
 
Typos:
- L43: "updation" -> "updates"
- L52: "labels. e.g. In"
- L428: Should be \citet here
- L484: "denotes" -> "denote"

questions:
Q1. What is the main intuition on why the method is expected to work well on heterophilic graphs?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730909818684

thread_type:
official_review

<thread_object>
creator: reviewer_e6x4

<content>
summary:
The paper proposes Spectral Highways, a technique that enhances the performance of Graph Neural Networks on heterophilic graphs with additional nodes and connections forming highways over the original graph.

strengths:
1. The story is interesting.
2. It tested on rich datasets.

weaknesses:
1. The addition of nodes and connections is a common approach in graph augmentation. For example, methods such as [1] use similar upsampling approaches. To better showcase the novelty, I suggest that the authors emphasize these unique aspects more explicitly and explore how these modifications lead to improvements over [1] and similar methods.
2. While enriching the graph can enhance performance, it may also introduce considerable computational overhead, especially on large-scale datasets. I recommend that the authors include a detailed analysis of time and space complexity. Specifically, it would be beneficial to compare the construction time of Spectral Highways relative to the original graph size, as well as its impact on downstream GNN runtime.
3. Since datasets are already introduced in Section 2.1, Section 2.2 could be streamlined to focus primarily on algorithmic contributions without redundancies. In table 2, The analysis could be expanded to include comparisons that consider performance gains across dataset characteristics, such as homophily levels, graph sizes, and class distributions. This additional detail would make the results more informative and enable better comparisons across datasets.

[1] Azabou, Mehdi, et al. "Half-Hop: A graph upsampling approach for slowing down message passing." International Conference on Machine Learning. PMLR, 2023.

questions:
See Weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731243873482

thread_type:
official_review

<thread_object>
creator: reviewer_buwu

<content>
summary:
This paper presents a graph data augmentation method called Spectral Highway (SH). It involves dividing existing nodes into clusters using spectral clustering and then adding a layer of nodes on top of them. Each new node corresponds to a spectral cluster in the original graph. The new nodes form a fully connected subgraph, and they are connected to the original nodes belonging to their respective clusters in a principled way.

**Experiments.**
The authors tested the improvement in node classification performance on several classic *small-scale* datasets, showing *significant* results on ChameleonF and SquirrelF. They also compared SH with several rewiring and data-centric methods, demonstrating the advantages of SH as a graph augmentation method.

**Analysis.**
The authors mainly considered the impact of SH on homophily *intuitively and through experiments*, as well as the effect on intra-class and inter-class average shortest path lengths.

strengths:
1. The method and illustrations in the paper are clear.
2. The approach is very simple, but it shows significant results on ChameleonF and SquirrelF.
3. The paper organizes existing motivations for heterophilic graphs and addresses them in the analysis section.

weaknesses:
1. The algorithm is difficult to run on larger datasets. The paper emphasizes the impact of random seeds, which is reflected in the large variance of results. This is largely due to the small size of the datasets involved (Cornell, Texas, Wisconsin). Because of this, the authors should conduct experiments on larger datasets. However, the algorithm depends on spectral clustering, which seems to prevent it from scaling to larger datasets.

2. Few rewiring, data-centric/graph-augmentation methods are compared in the paper. 

3. The paper empirically discusses SH’s impact on homophily across various metrics. However, aside from the decrease in Aggregated Homophily on many datasets, the observed improvements are *not significant* in terms of numerical values.

questions:
Please check weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732308157095

thread_type:
public_comment

<thread_object>
creator: ~arshdeep_singla1

<content>
title:
A few queries

comment:
Hi, I stumbled upon this work while looking for specialized algos for heterophilic graphs. I work with financial data on asset management here at Berkeley and continuously look for the latest models for my leverage. I thoroughly enjoyed reading this paper smoothly, especially the sensitivity of many of the latest GNNs to random seed, and the uncovering of shortest path length phenomena and its relationship to the various homophily measures and model performance. It was pretty insightful that I could thoughtfully perturb my existing data using spectral clustering and probabilistic modeling to achieve better predictions. I currently use state of the art 'Dirsage' model for my data, and you have shown significant improvements over it through extensive detailed experimentation, which intrigued me. I have a few queries.

Since this perturbation is an augmentation methodology, can you please let me know the average number of additional nodes and edges it introduces?

Also, can you tell me which ranking algorithm you prefer to choose the nodes for spectral connections?

And do you plan to release your code in the near future? I would greatly appreciate that.

Thanks in advance.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732534749712

thread_type:
public_comment

<thread_object>
creator: ~samyak_jain3

<content>
title:
Impact of spectral clustering

comment:
Dear Authors,\
I am quite fascinated by your approach of employing traditional ML concepts of Spectral clustering for graph node prediction in a heterophilic setting. It is extremely interesting that you play with the notion of path lengths to bring dissimilar vertices closer to inject homophily. I see its applicability in many real-life industrial challenges that we face. Though I really liked your analysis and discussion segment, however, I couldn’t find any discussion where we see the impact of spectral clustering on downstream prediction. If you plan to rebut, can you please show these results if possible? Also, for the purpose of utilizing your work do you also plan to open source the code?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732889803470

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final and revised manuscript has been uploaded

comment:
Dear Reviewers,

We have tried our best to address your concerns and revised the paper. We have uploaded the final version of our paper. Compared to the previous version, we made the following major changes:


**Addition of more baselines:** We have added 2 additional baselines as suggested by Reviewers bUwU, e6x4 and bR69. We discussed and compared the results in the revised manuscript.

**Conducting ablation studies:** We have conducted 3 ablation studies following the request of Reviewer dhKQ and the public commentator. The studies highlight the importance of each step of our proposed algorithm.

**Revising Introduction:** We have revised the introduction following the suggestion from Reviewer dhKQ to make it more coherent.

**Adding large dataset:** Following the suggestion of Reviewers bUwU and bR69, we ran experiments on one large dataset and showed results in the discussion forum.

**Time and Space Analysis:** We have added the relevant sections covering the time and space aspects of our proposed method in the revised manuscript. We thank Reviewer e6x4 and the public commentator for this feedback.

**Minor fixes:** We have corrected the typos and the suggested minor fixes as suggested by Reviewer bR69.


We will be grateful if you can kindly take a look at our revised manuscript and the rebuttal responses. **We have tried our best to produce a lucid and thorough rebuttal**. We also fully understand that you probably need to prioritise your own submissions at this moment. We wish all of you good luck at this extended discussion stage.

Sincere Regards.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a graph augmentation method called Spectral Highway (SH) to improve the performance of Graph Neural Networks (GNNs) on heterophilic graphs by adding supernodes that represent spectral clusters. The method is evaluated on several small-scale datasets, showing promising results, particularly on ChameleonF and SquirrelF. The paper also explores the impact of SH on homophily and node classification performance, though its broader applicability and the significance of the improvements are not fully explored.

While the proposed model shows promising results, the reviewers have identified several weaknesses that need to be addressed:

1. The paper lacks a clear theoretical explanation for why the method is effective on heterophilic graphs, with empirical results sometimes showing mixed or insignificant improvements.
2. The method struggles to scale to larger datasets due to its reliance on spectral clustering, which limits its applicability to bigger graphs.
3.  The paper only compares SH to a few rewiring and graph augmentation methods, missing a broader range of relevant approaches in the literature.

Based on these weaknesses, we recommend rejecting this paper. We hope this feedback helps the authors improve their paper.