Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering

2022-06-06 · Shouheng Li, Dongwoo Kim, Qing Wang

While a growing body of literature has been studying new Graph Neural Networks (GNNs) that work on both homophilic and heterophilic graphs, little has been done on adapting classical GNNs to less-homophilic graphs. Although the ability to handle less-homophilic graphs is restricted, classical GNNs still stand out in several nice properties such as efficiency, simplicity, and explainability. In this work, we propose a novel graph restructuring method that can be integrated into any type of GNNs, including classical GNNs, to leverage the benefits of existing GNNs while alleviating their limitations. Our contribution is threefold: a) learning the weight of pseudo-eigenvectors for an adaptive spectral clustering that aligns well with known node labels, b) proposing a new density-aware homophilic metric that is robust to label imbalance, and c) reconstructing the adjacency matrix based on the result of adaptive spectral clustering to maximize the homophilic scores. The experimental results show that our graph restructuring method can significantly boost the performance of six classical GNNs by an average of 25% on less-homophilic graphs. The boosted performance is comparable to state-of-the-art methods.

📄 PDF Abstract BibTeX arXiv:2206.02386

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringNode Classification

Methods 이 논문이 사용한 방법론

Spectral Clustering Spectral clustering has attracted increasing attention due to the promising ability in dealing with nonlinearly separable datasets [15], [16]. In spectral clustering, the…

Global Node Attentions via Adaptive Spectral Filters

2021-01-01 · Shouheng Li, Dongwoo Kim, Qing Wang

Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in local neighborhoods. This assumption limits the generalizability o…

Node Classification

Adaptive Homophily Clustering: Structure Homophily Graph Learning with Adaptive Filter for Hyperspectral Image

2025-01-03 · Yao Ding, Weijie Kang, Aitao Yang, Zhili Zhang 외

Hyperspectral image (HSI) clustering has been a fundamental but challenging task with zero training labels. Currently, some deep graph clustering methods have been successfully explored for HSI due to their outstanding p…

Clustering Graph Clustering Graph Embedding Graph Learning+1

Can Large Language Models Improve Spectral Graph Neural Networks?

2025-06-17 · Kangkang Lu, Yanhua Yu, Zhiyong Huang, Tat-Seng Chua

Spectral Graph Neural Networks (SGNNs) have attracted significant attention due to their ability to approximate arbitrary filters. They typically rely on supervision from downstream tasks to adaptively learn appropriate …

Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs

2021-03-26 · Sean Li, Dongwoo Kim, Qing Wang

Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. As pointed out by recent studies, most GNNs assume local homophily, i.e., strong similarities in local neighborhoods. This assump…