Simple Truncated SVD based Model for Node Classification on Heterophilic Graphs

2021/06/24 by Vijay Lingam, Rahul Ragesh, Lingam, Vijay +5
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Recommender Systems and Techniques

paper · pdf · doi:10.48550/arxiv.2106.12807

openalex publication_date 2021/06/24 · openalex created_date 2021/07/05 · openalex updated_date 2026/07/28

Abstract

Graph Neural Networks (GNNs) have shown excellent performance on graphs that exhibit strong homophily with respect to the node labels i.e. connected nodes have same labels. However, they perform poorly on heterophilic graphs. Recent approaches have typically modified aggregation schemes, designed adaptive graph filters, etc. to address this limitation. In spite of this, the performance on heterophilic graphs can still be poor. We propose a simple alternative method that exploits Truncated Singular Value Decomposition (TSVD) of topological structure and node features. Our approach achieves up to ~30% improvement in performance over state-of-the-art methods on heterophilic graphs. This work is an early investigation into methods that differ from aggregation based approaches. Our experimental results suggest that it might be important to explore other alternatives to aggregation methods for heterophilic setting.

Citations

• Birds of a Feather: Homophily in Social Networks
• Inductive Representation Learning on Large Graphs
• Simplifying Graph Convolutional Networks
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• Geom-GCN: Geometric Graph Convolutional Networks
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs
• Beyond Low-frequency Information in Graph Convolutional Networks

Related

• Incorporating Heterophily into Graph Neural Networks for Graph Classification
• Label-Wise Graph Convolutional Network for Heterophilic Graphs
• Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?
• A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
• Graph Neural Networks for Graphs with Heterophily: A Survey