Let Your Features Tell The Differences: Understanding Graph Convolution By Feature Splitting

Authors: Yilun Zheng, Xiang Li, Sitao Luan, Xiaojiang Peng, Lihui Chen
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Graph Homophily, Topological Feature Selection

Abstract:
Graph Neural Networks (GNNs) have demonstrated strong capabilities in processing structured data. While traditional GNNs typically treat each feature dimension equally important during graph convolution, we raise an important question: **Is the graph convolution operation equally beneficial for each feature?** If not, the convolution operation on certain feature dimensions can possibly lead to harmful effects, even worse than convolution-free models. Therefore, it is required to distinguish convolution-favored and convolution-disfavored features. Traditional feature selection methods mainly focus on identifying informative features or reducing redundancy, but they are not suitable for structured data as they overlook graph structures. In graph community, some studies have investigated the performance of GNN with respect to node features using feature homophily metrics, which assess feature consistency across graph topology. Unfortunately, these metrics do not effectively align with GNN performance and cannot be reliably used for feature selection in GNNs. To address these limitations, we introduce a novel metric, Topological Feature Informativeness (TFI), to distinguish GNN-favored and GNN-disfavored features, where its effectiveness is validated through both theoretical analysis and empirical observations. Based on TFI, we propose a simple yet effective Graph Feature Selection (GFS) method, which processes GNN-favored and GNN-disfavored features with GNNs and non-GNN models separately. Compared to original GNNs, GFS significantly improves the extraction of useful topological information from each feature with comparable computational costs. Extensive experiments show that after applying GFS to $\textbf{8}$ baseline and state-of-the-art (SOTA) GNN architectures across $\textbf{10}$ datasets, $\textbf{90\%}$ of the GFS-augmented cases show significant performance boosts. Furthermore, our proposed TFI metric outperforms other feature selection methods for GFS. These results verify the effectiveness of both GFS and TFI. Additionally, we demonstrate that GFS's improvements are robust to hyperparameter tuning, highlighting its potential as a universally valid method for enhancing various GNN architectures. To facilitate reproducibility and further research, we have made our code publicly available at https://github.com/KTTRCDL/graph-feature-selection.

Decision: accept (poster)
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730292547217

thread_type:
official_review

<thread_object>
creator: reviewer_v9jq

<content>
summary:
The paper explores the varying impact of graph convolution across different feature dimensions in GNNs. It introduces a novel metric called Topological Feature Informativeness (TFI), designed to identify features that are either favored or disfavored by GNNs. The authors propose a Graph Feature Selection (GFS) method that leverages TFI to process GNN-favored features with GNNs and GNN-disfavored features with MLPs, enhancing overall performance. The experimental results across multiple GNN architectures and datasets demonstrate that GFS improves accuracy with minimal computational overhead. The work emphasizes the importance of feature-aware processing in GNNs, showing that graph convolution is not uniformly beneficial for all feature dimensions.

strengths:
S1: The concept of distinguishing between GNN-favored and GNN-disfavored features is interesting and novel. 

S2: The paper is well-written and structured, easy for readers to follow the methodology and findings. 

S3:  The experimental results consistently demonstrate the effectiveness of the proposed GFS trick.

weaknesses:
W1: As far as I am concerned, the theoretical analysis of the proposed strategy is incomplete. The paper does not clearly explain the specific conditions under which distinguishing between GNN-favored and GNN-disfavored features is most effective. 

W2: The proposed TFI metric, while beneficial, appears similar to existing mutual information-based methods. The authors need to provide more clarification on how TFI uniquely contributes to feature selection in graph learning, emphasizing its distinct advantages over prior approaches.

W3: Although the experimental results demonstrate strong performance of the GFS-augmented models, I remain somewhat unconvinced. To strengthen the validity of the findings, it would be helpful to include experiments on synthetic datasets, such as those generated by the SBM model with varying levels of heterophily and homophily. Such experiments could offer more reliable insights into the potential advantages of the proposed methodology.

questions:
Q1: I am still unclear about how TFI fundamentally differs from other mutual information-based metrics for feature selection in graph learning. Could the authors provide a clearer explanation of its unique contributions and advantages?

Q2: How does the proposed method handle extremely sparse features, which are common in real-world graphs? Are there specific challenges or limitations in this context?

Q3: It appears that the proposed method offers limited advantages on homophilous graphs compared to its performance on heterophilous graphs. Could the authors provide insights to clarify this discrepancy and explain why the method may be less effective in homophilous settings?

Q4: I am curious about the robustness of the proposed method when applied to noisy graphs, where certain features may contain varying levels of noise. Could the authors provide insights or results on its performance in these scenarios?"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730345308336

thread_type:
official_review

<thread_object>
creator: reviewer_port

<content>
summary:
GNNs have strong graph learning capabilities. However, GNNs are not effective at learning all graph data features. In previous work, many metrics based on graph topology and features have been proposed to describe feature homogeneity in order to assess the effectiveness of GNNs. However, there has been no metric that can directly and effectively guide which features GNNs should learn. To fill this gap, this paper proposes an evaluation metric, Topological Feature Informative (TFI), to compute the learnability of features for GNNs. Subsequently, a dual-channel embedding architecture combining GNNs and MLPs is used to embed these features separately.

strengths:
1. The writing of the paper is clear and easy to understand, with a well-defined theme.
2. The paper provides a theoretical foundation for using TFI to guide feature selection through simple proofs.
3. The experimental results on node classification tasks are impressively good.

weaknesses:
The paper does not provide any statistical analysis of the selected features, which raises some questions.

questions:
1. How is the decomposition of node features in the graph executed? 
2. What impact does the dimension of the initial node features have?
3. Can this method only be applied to node features, or can it also be used on edge features, and what would be the effect?
4. Is it possible to measure what a "good heterophily" feature looks like? Can other metrics be used for supplementary description, such as Label Homophily, Feature Homophily, Mutual Information, and so on?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730584737396

thread_type:
official_review

<thread_object>
creator: reviewer_isuk

<content>
summary:
The paper introduces a new method to identify features that are favored and disfavored by GNNs. It uses topological feature selection to integrate these features into GNNs, leading to significant improvements in their performance.

strengths:
1. The paper is well-motivated and presents a novel approach to distinguish between GNN-favored and GNN-disfavored features, treating them separately to learn with different methods.
2. The paper is clearly presented and includes solid theoretical guarantees, making it easy to follow.
3. The authors provide sufficient empirical analysis, including ablation studies and comparisons with state-of-the-art methods.

weaknesses:
The evaluation method is not fair enough. The performance results in Table 1 should be presented with only the difference of with or without GPS, while keeping the model architecture the same (e.g., number of layers and hidden dimension).

questions:
1. As shown in Figure 2, the performance gap for the Roman dataset between GCN and MLP in regions with low TFI is minimal. How is the improvement over GCN in Figure 4 so significant regardless of $r$?
2. Since features are updated in each GNN/MLP layer, is the TFI computed at each layer to get (dis)favored features, or is it only computed at the beginning? This point does not seem clearly explained in the paper.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644662674

thread_type:
official_review

<thread_object>
creator: reviewer_jpab

<content>
summary:
This paper investigates the problem of feature selection for graph Convolution Networks (GCNs). It begins by introducing TFI, a metric designed to guide the selection of relevant features. Following that, it introduces GFS, a plug-in method that distinguishes between features that benefit graph convolution and those that do not contribute positively or may even have a negative impact. Then, the two sets of features are processed separately using GCN and Multi-Layer Perceptrons (MLP), respectively. Evaluations on node classification tasks demonstrate the effectiveness of the proposed TFI and GFS.

strengths:
1 This paper is well-organized and easy to follow. 

2 The figures regarding the design motivation and the proposed framework (Figures 1 and 3) are clear.

3 The theoretical proofs are detailed.

weaknesses:
1 The proposed feature selection metric TFI, which leverages mutual information between features and labels, is not novel. This is a conventional approach for feature selection, as outlined in [1]. Although the TFI utilizes the features derived from the neighborhood average (AX), the approach is incremental. 

2 This paper lacks a comparative analysis of classic feature selection methods, such as [2]. 

3 The GPS exhibits limited robustness to the selection of the hyperparameter r.

4 It is unclear how the high-pass filters of FAGCN and ACMGNN, as presented in Table 1, align with the TFI metric with low-pass AX.

5 A significant concern is the applicability of the proposed GFS. The paper asserts that TFI is computed on training nodes. Thus, I am concerned that the unusual dataset division of 50/25/25 for training/validation/testing employed in this paper is crucial for the effectiveness of GFS. The question then becomes: how would the results be affected if a public splitting, such as 20 per class for training in GCN, SGC, GAT, and APPNP, were applied?

[1] Feature Selection: A Data Perspective. ACM Comput. Surv. 50(6).

[2] Multi-label Feature Selection via Global Relevance and Redundancy Optimization. IJCAI 2020.

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

</thread>
<thread>
creation date:
1732554770131

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to extend our sincere gratitude to all the reviewers for their valuable feedback. In response to the question, "Is Graph Convolution Always Beneficial for Every Feature?", we introduce a new metric, TFI, designed to assess whether specific features benefit from graph-aware models. This is supported by both our empirical observations and theoretical justifications. Following the principle of "feeding the right feature to the right model," we propose GFS, a method that directs GNN-favored features to graph-aware models and GNN-disfavored features to graph-agnostic models. Our experiments demonstrate that this approach can be easily integrated into various GNN backbones, **enhancing model performance without the need of hyperparameter tuning.**

Below is a summary of our additional findings from the rebuttal:

1. **Impact of Label Homophily:** We utilize the CSBM to manipulate label homophily in synthetic graphs. As shown in Table 16, GFS consistently outperforms both MLP and GCN across varying levels of label homophily.

2. **Additional Settings:**
(1) By varying the number of node features in synthetic datasets, we find that GFS is significantly more effective in datasets with a higher number of features, demonstrating greater fault tolerance during feature selection.
(2) Introducing sparsity in node features shows that GFS maintains effectiveness across different levels of sparsity.
(3) When random noises are added to real-world datasets, GFS continuously outperforms baseline GNNs on noisy graphs.

3. **Statistical Analysis of Selected Features:** As illustrated in Table 21, we found that:
(1) Datasets encoded by Pretrained Language Models (PLMs) exhibit similar feature values; notably, a higher average TFI across features correlates with improved GFS performance.
(2) GFS is less effective on datasets with higher sparsity, such as Minesweeper and Tolokers.
(3) Datasets with lower homophily tend to classify more features as GNN-disfavored, while those with higher homophily identify more features as GNN-favored.

Thank you once again to all the reviewers. **We look forward to your response.**
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a novel technique called e Graph Feature Selection (GFS) to enhance the performance of GCNs. The method leverages a Topological Feature Informativeness (TFI) to distinguish GNN-favored features and GNN-disfavored features. The proposed method is justified by theories and experiments.   

The paper is well written. The motivation is clearly presented and the results nicely supports the hypothesis that the authors made. The theoretical analysis is solid and detailed. The numerical experiments well support that the proposed method enhances performances of GCNs. Thus, I recommend acceptance of the paper.