Loading...
Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening
Li, Guoming Yang, Jian Chen, Yifan
Li, Guoming
Yang, Jian
Chen, Yifan
Author
Supervisor
Department
Machine Learning
Embargo End Date
Type
Conference proceeding
Date
2025
License
Language
English
Collections
Research Projects
Organizational Units
Journal Issue
Abstract
Filtering-based graph neural networks (GNNs) constitute a distinct class of GNNs that employ graph filters to handle graph-structured data, achieving notable success in various graph-related tasks. Conventional methods adopt a graph-wise filtering paradigm, imposing a uniform filter across all nodes, yet recent findings suggest that this rigid paradigm struggles with heterophilic graphs. To overcome this, recent works have introduced node-wise filtering, which assigns distinct filters to individual nodes, offering enhanced adaptability. However, a fundamental gap remains: a comprehensive framework unifying these two strategies is still absent, limiting theoretical insights into the filtering paradigms. Moreover, through the lens of Contextual Stochastic Block Model, we reveal that a synthesis of graph-wise and node-wise filtering provides a sufficient solution for classification on graphs exhibiting both homophily and heterophily, suggesting the risk of excessive parameterization and potential overfitting with node-wise filtering. To address the limitations, this paper introduces Coarsening-guided Partition-wise Filtering (CPF). CPF innovates by performing filtering on node partitions. The method begins with structure-aware partition-wise filtering, which filters node partitions obtained via graph coarsening algorithms, and then performs feature-aware partition-wise filtering, refining node embeddings via filtering on clusters produced by k-means clustering over features. In-depth analysis is conducted for each phase of CPF, showing its superiority over other paradigms. Finally, benchmark node classification experiments, along with a real-world graph anomaly detection application, validate CPF's efficacy and practical utility. Code is available with the Github repository: https://github.com/vasile-paskardlgm/CPF.
Citation
G. Li, J. Yang, and Y. Chen, “Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening,” pp. 1353–1364, Aug. 2025, doi: 10.1145/3711896.3737075/SUPPL_FILE/RTFB0781-VIDEO.MP4
Source
Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Conference
2025 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Keywords
Graph Coarsening, Graph Filtering, Heterophily, Node Classification, Benchmarking, Clustering Algorithms, Graph Algorithms, Graph Embeddings, Graph Neural Networks, Graph Structures, Graphic Methods, Ostwald Ripening, Stochastic Models, Stochastic Systems, Coarsenings, Conventional Methods, Graph Coarsening, Graph Filtering, Graph Structured Data, Heterophily, Node Classification, Node Partition, Through The Lens, Coarsening
Subjects
Source
2025 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Publisher
Association for Computing Machinery