Pith. sign in

REVIEW 98 references

Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening

T0 review · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A partition-wise graph filtering method, CPF, unifies graph-wise and node-wise filtering and achieves state-of-the-art node classification on 13 benchmark graphs and anomaly detection on 3 datasets.

arxiv 2505.14033 v2 pith:SO2AO57L submitted 2025-05-20 cs.LG cs.NAeess.SPmath.NA

Guoming Li , Jian Yang , Yifan Chen This is my paper
classification cs.LGcs.NAeess.SPmath.NA
keywords filteringgraphnodepartition-wisefiltersnode-wiseclassificationcoarsening
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph neural networks that use filters have two standard setups. Graph-wise filtering applies the same filter to every node, which is simple but can underperform when the graph is heterophilic, meaning connected nodes often have different labels. Node-wise filtering gives each node its own filter, which is flexible but uses many parameters. This paper proposes a middle ground: partition-wise filtering, where groups of nodes share a filter.\n\nThe method, CPF, forms the groups in two ways. First, it uses graph coarsening, a technique that merges nodes into supernodes while trying to keep the graph spectrum similar. Each supernode becomes a partition, and all nodes in it share a filter. Second, it runs k-means clustering on the resulting node embeddings, with one cluster per class, and applies a separate linear transformation to each cluster.\n\nThe authors support the approach with theory. They show that under a contextual stochastic block model, a hybrid of graph-wise and node-wise filtering is enough for linear separation of classes, motivating the partition-wise design. They also argue that propagation on the coarsened graph approximates propagation on the original graph when coarsening preserves the spectrum. Experiments on 13 node classification datasets and 3 anomaly detection datasets report consistent gains over 18 baselines.\n\nThe theory, however, rests on idealized assumptions. The main theorem requires the coarsening error to go to zero, but the experiments fix the coarsening ratio at 0.5 without measuring that error. One proof step also uses a spectral bound that is not generally valid. These gaps do not necessarily invalidate the empirical method, but they weaken the theoretical claims.
Extended reading notes

Core claim

The paper claims that message propagation across nodes in a graph is structurally equivalent to propagation between coarsening-based clusters when the RSA constant is small (Theorem 3.2), and that CPF unifies graph-wise and node-wise filtering as extreme cases (Proposition 3.3). The empirical claim is that CPF (coarsening ratio 0.5, polynomial degree 10) outperforms 18 baselines on 13 node classification datasets and 3 graph anomaly detection datasets, with improvements up to 6.87 percentage points on Snap-patents over the nearest competitor.

Load-bearing premise

The theory of structure-aware filtering assumes the coarsening matrix has RSA constant epsilon approaching zero (Theorem 3.2), so that propagation on the original graph is approximated by propagation on the coarsened graph. The experiments set the coarsening ratio to r=0.5 for all datasets without measuring epsilon, and the proof of Theorem 3.2 additionally relies on an unproven spectral norm bound (Appendix B, Eq. 20). If real coarsenings at r=0.5 do not have small epsilon, the structural equivalence justifying shared filters within partitions is unsupported.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central method rests on a set of assumptions borrowed from prior work (CSBM theorem, RSA inequality) and a few paper-specific choices (r=0.5, K=10, cluster count equal to class count). The most fragile are the idealized epsilon-to-zero approximation and an unproven norm bound in the main theorem's proof.

free parameters (3)
  • coarsening ratio r = 0.5
    Fixed across all experiments (Section 4.1.2, Appendix F.1). The method interpolates between graph-wise (r=n-1/n) and node-wise (r=0); the chosen midpoint value is not derived from theory or tuned per dataset.
  • polynomial degree K = 10
    Set to 10 to match prior filtering methods; ablation shows performance varies with K (Table 6), so this choice affects results.
  • number of feature clusters c = number of classes per dataset
    Used for k-means in feature-aware filtering; the number of clusters equals the number of node classes (Section 3.4.1).
assumptions (5)
  • domain assumption Theorem 1 of [28]: in binary-class CSBM graphs, a uniform filter achieves linear separability for homophilic graphs, and node-specific filters do so for heterophilic graphs.
    Used as the starting point for Proposition 3.1's hybrid solution (Appendix A).
  • domain assumption The RSA inequality ||Delta x - Pi Delta Pi x||_L <= epsilon ||x||_L (||Delta||_L + ||Pi Delta||_L) from [39] holds for the coarsening matrix used.
    Fundamental bound in the proof of Theorem 3.2 (Appendix B, Eq. 17).
  • ad hoc to paper Coarsening at ratio r=0.5 yields an RSA constant close enough to zero for the approximation in Theorem 3.2 to hold.
    The theorem assumes epsilon to 0, but the experiments fix r=0.5 without measuring epsilon or justifying the limit.
  • ad hoc to paper The L-induced operator norm satisfies ||Delta^{k-1}x||_L <= lambda_max ||x||_L with lambda_max <= 1.
    Invoked in Appendix B (Eq. 20) to bound ||Delta^{k-1}x||_L; this inequality is not generally true for the L-induced norm and is not proven.
  • domain assumption k-means clustering of the structure-filtered embeddings into c clusters recovers groups whose class-wise linear transforms can correct misclassifications.
    Heuristic basis for feature-aware filtering (Section 3.4); no guarantee that clusters align with classes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening." pith.science (2026). https://pith.science/paper/SO2AO57L

@misc{pith2026250514033,
  author       = {Pith},
  title        = {Pith review of: Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SO2AO57L}},
  note         = {Machine review of arXiv:2505.14033}
}
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.

Figures

Figures reproduced from arXiv: 2505.14033 by the authors.

Figure 1
Figure 1. Overview of CPF’s filtering procedure. It employs the partition-wise graph filtering in two aspects: structure, where [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The impact of coarsening ratio. Here, “Graph-” and [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Additional ablation studies of coarsening ratio [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

98 extracted references · 37 canonical work pages

  1. [1]

    Shai Ben-David, Dávid Pál, and Hans Ulrich Simon. 2007. Stability of k-Means Clustering. InLearning Theory, Nader H. Bshouty and Claudio Gentile (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 20–34

    2007

  2. [2]

    Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. 2020. Graph Neural Networks With Convolutional ARMA Filters.IEEE Transactions on Pattern Analysis and Machine Intelligence44, 7 (2020), 3496–3507. doi:10.1109/ TPAMI.2021.3054830

    arXiv 2020

  3. [3]

    Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. 2023. Specformer: Spectral Graph Neural Networks Meet Transformers. InThe Eleventh International Confer- ence on Learning Representations. https://openreview.net/forum?id=0pdSt3oyJa1

    2023

  4. [4]

    Fedor Borisyuk, Shihai He, Yunbo Ouyang, Morteza Ramezani, Peng Du, Xiaochen Hou, Chengming Jiang, Nitin Pasumarthy, Priya Bannur, Birjodh Tiwana, Ping Liu, Siddharth Dangi, Daqi Sun, Zhoutao Pei, Xiao Shi, Sirou Zhu, Qianqi Shen, Kuang-Hsuan Lee, David Stein, Baolei Li, Haichao Wei, Amol Ghoting, and Souvik Ghosh. 2024. LiGNN: Graph Neural Networks at Li...

    doi:10.1145/3637528 2024

  5. [5]

    Jie Chen, Yousef Saad, and Zechen Zhang. 2022. Graph coarsening: from scientific computing to machine learning.SeMA Journal79, 1 (2022), 187–223

    2022

  6. [6]

    Jie Chen and Ilya Safro. 2011. Algebraic Distance on Graphs.SIAM Jour- nal on Scientific Computing33, 6 (2011), 3468–3490. doi:10.1137/090775087 arXiv:https://doi.org/10.1137/090775087

    work page doi:10.1137/090775087 2011

  7. [7]

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Sim- ple and Deep Graph Convolutional Networks. InProceedings of the 37th Interna- tional Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119). PMLR, 1725–1735. https://proceedings.mlr.press/v119/chen20v.html

    2020

  8. [8]

    Yifan Chen, Rentian Yao, Yun Yang, and Jie Chen. 2023. A Gromov-Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening. InProceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarle...

    2023

Show all 98 references
  1. [9]

    Zhengdao Chen, Lisha Li, and Joan Bruna. 2019. Supervised Community Detec- tion with Line Graph Neural Networks. InInternational Conference on Learning Representations. https://openreview.net/forum?id=H1g0Z3A9Fm

    2019

  2. [10]

    Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021. Adaptive Universal Generalized PageRank Graph Neural Network. InInternational Conference on Learning Representations. https://openreview.net/forum?id=n6jl7fLxrP

    2021

  3. [11]

    1997.Spectral Graph Theory

    Fan Chung. 1997.Spectral Graph Theory. Vol. 92. CBMS Regional Conference Series in Mathematics. doi:/10.1090/cbms/092

    1997 doi

  4. [12]

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolu- tional Neural Networks on Graphs with Fast Localized Spectral Filtering. InAd- vances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.), Vol. 2...

    2016

  5. [13]

    Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng

  6. [14]

    Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. 2018. Contextual Stochastic Block Models. InAdvances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Assoc...

    2018

  7. [15]

    Charles Dickens, Edward Huang, Aishwarya Reganti, Jiong Zhu, Karthik Subbian, and Danai Koutra. 2024. Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training. InCompanion Proceedings of the ACM Web Conference 2024(Singapore, Singapore)(WWW ’24). As...

    2024

  8. [16]

    Xiaowen Dong, Dorina Thanou, Laura Toni, Michael Bronstein, and Pascal Frossard. 2020. Graph Signal Processing for Machine Learning: A Review and New Perspectives.IEEE Signal Processing Magazine37, 6 (2020), 117–127. doi:10.1109/MSP.2020.3014591

    2020

  9. [17]

    Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S. Yu. 2020. Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsters. InProceedings of the 29th ACM International Confer- ence on Information & Knowledge Management(Virtual Event, I...

    2020

  10. [18]

    Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. 2022. GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily. InProceedings of the ACM Web Conference

    2022

  11. [19]

    Cody Dunne and Ben Shneiderman. 2013. Motif simplification: improving net- work visualization readability with fan, connector, and clique glyphs. InProceed- ings of the SIGCHI Conference on Human Factors in Computing Systems(Paris, France)(CHI ’13). Association for Computing M...

    2013

  12. [20]

    Moshe Eliasof, Eldad Haber, and Eran Treister. 2021. PDE-GCN: Novel Architec- tures for Graph Neural Networks Motivated by Partial Differential Equations. In Advances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (Eds.)....

    2021

  13. [21]

    Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar. 2014. Vertex Sparsifiers: New Results from Old Techniques.SIAM J. Comput.43, 4 (2014), 1239–1262. doi:10.1137/130908440 arXiv:https://doi.org/10.1137/130908440

    2014 doi

  14. [22]

    Matthias Fey and Jan Eric Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. doi:10.48550/ARXIV.1903.02428

    2019 doi arXiv

  15. [23]

    Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yong- dong Zhang. 2023. Addressing Heterophily in Graph Anomaly Detection: A Perspective of Graph Spectrum. InProceedings of the ACM Web Conference 2023 (Austin, TX, USA)(WWW ’23). Association for Computing Mac...

    2023

  16. [24]

    Yuan Gao, Xiang Wang, Xiangnan He, Zhenguang Liu, Huamin Feng, and Yong- dong Zhang. 2023. Alleviating Structural Distribution Shift in Graph Anomaly Detection. InProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining(Singapore, Singapore)(WSDM...

    2023

  17. [25]

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2019. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In International Conference on Learning Representations. https://openreview.net/ forum?id=H1gL-2A9Ym

    2019

  18. [26]

    Chenghua Gong, Yao Cheng, Xiang Li, Caihua Shan, and Siqiang Luo. 2024. Learn- ing from Graphs with Heterophily: Progress and Future. arXiv:2401.09769 [cs.SI] https://arxiv.org/abs/2401.09769

    2024 arXiv

  19. [27]

    Yuhe Guo and Zhewei Wei. 2023. Graph Neural Networks with Learnable and Optimal Polynomial Bases. InProceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara...

    2023

  20. [28]

    Haoyu Han, Juanhui Li, Wei Huang, Xianfeng Tang, Hanqing Lu, Chen Luo, Hui Liu, and Jiliang Tang. 2024. Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach. arXiv:2406.03464 [cs.LG] https://arxiv.org/abs/ 2406.03464

    2024 arXiv

  21. [29]

    Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. 2021. BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation. InAd- vances in Neural Information Processing Systems, A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (Eds.). https://op...

    2021

  22. [30]

    Mingguo He, Zhewei Wei, and Ji-Rong Wen. 2022. Convolutional Neural Net- works on Graphs with Chebyshev Approximation, Revisited. InAdvances in Neu- ral Information Processing Systems, Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.). https://openreview....

    2022

  23. [31]

    Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. doi:10.48550/ARXIV.2002.02126

    2020 doi arXiv

  24. [32]

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. InAdvances in Neural Information Processing Systems, Vol. 33. 22118–22133. https://proceedings....

    2020

  25. [33]

    Keke Huang, Wencai Cao, Hoang Ta, Xiaokui Xiao, and Pietro Liò. 2024. Opti- mizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach. InProceedings of the ACM Web Conference 2024(Singapore, Singapore)(WWW ’24). Association for Computing Machinery, New York, N...

    2024

  26. [34]

    Keke Huang, Jing Tang, Juncheng Liu, Renchi Yang, and Xiaokui Xiao. 2023. Node-wise Diffusion for Scalable Graph Learning. InProceedings of the ACM Web Conference 2023(Austin, TX, USA)(WWW ’23). Association for Computing Machinery, New York, NY, USA, 1723–1733. doi:10.1145/354...

    2023

  27. [35]

    Keke Huang, Yu Guang Wang, Ming Li, and Pietro Lio. 2024. How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over- smoothing, and Over-squashing. InForty-first International Conference on Machine Learning. https://openreview.net/forum?id=Z2LH6Va7L2

    2024

  28. [36]

    Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. 2021. Scaling Up Graph Neural Networks Via Graph Coarsening. InProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining(Virtual Event, Singapore)(KDD ’21). Association for Computing M...

    2021

  29. [37]

    A. K. Jain, M. N. Murty, and P. J. Flynn. 1999. Data clustering: a review.ACM Comput. Surv.31, 3 (Sept. 1999), 264–323. doi:10.1145/331499.331504

    1999

  30. [38]

    Yu Jin, Andreas Loukas, and Joseph JaJa. 2020. Graph Coarsening with Preserved Spectral Properties. InProceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research, KDD ’25, August 3–7, 2025, Toront...

    2020

  31. [39]

    Antonin Joly and Nicolas Keriven. 2024. Graph Coarsening with Message-Passing Guarantees. arXiv:2405.18127 [cs.LG] https://arxiv.org/abs/2405.18127

    2024 arXiv

  32. [40]

    Kingma and Jimmy Ba

    Diederik P. Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Opti- mization. doi:10.48550/ARXIV.1412.6980

    2014 doi arXiv

  33. [41]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. InInternational Conference on Learning Repre- sentations. https://openreview.net/forum?id=SJU4ayYgl

    2017

  34. [42]

    Manoj Kumar, Anurag Sharma, and Sandeep Kumar. 2023. A Unified Framework for Optimization-Based Graph Coarsening.Journal of Machine Learning Research 24, 118 (2023), 1–50. http://jmlr.org/papers/v24/22-1085.html

    2023

  35. [43]

    Manoj Kumar, Anurag Sharma, Shashwat Saxena, and Sandeep Kumar. 2023. Featured Graph Coarsening with Similarity Guarantees. InProceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunski...

    2023

  36. [44]

    Bingheng Li, Erlin Pan, and Zhao Kang. 2024. PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering.Proceedings of the AAAI Conference on Artificial Intelligence38, 12 (Mar. 2024), 13437–13445. doi:10.1609/aaai.v38i12. 29246

    2024 doi

  37. [45]

    Guoming Li, Jian Yang, and Shangsong Liang. 2025. ERGNN: Spectral Graph Neural Network With Explicitly-Optimized Rational Graph Filters. InICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 1–5. doi:10.1109/ICASSP49660.2025.10888930

    2025

  38. [46]

    Guoming Li, Jian Yang, Shangsong Liang, and Dongsheng Luo. 2024. Spectral GNN via Two-dimensional (2-D) Graph Convolution. arXiv:2404.04559 [cs.LG]

    2024 arXiv

  39. [47]

    Guoming Li, Jian Yang, Shangsong Liang, and Dongsheng Luo. 2025. Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach. InProceedings of the ACM on Web Conference 2025(Sydney NSW, Australia)(WWW ’25). Association for Computing Machine...

    2025

  40. [48]

    Xunkai Li, Jingyuan Ma, Zhengyu Wu, Daohan Su, Wentao Zhang, Rong-Hua Li, and Guoren Wang. 2024. Rethinking Node-wise Propagation for Large-scale Graph Learning. InProceedings of the ACM Web Conference 2024(Singapore, Singapore)(WWW ’24). Association for Computing Machinery, N...

    2024

  41. [49]

    Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. InProceedings of the 39th International Conference on Machine Learning (Proceedings of Machine Learning R...

    2022

  42. [50]

    Langzhang Liang, Xiangjing Hu, Zenglin Xu, Zixing Song, and Irwin King. 2023. Predicting Global Label Relationship Matrix for Graph Neural Networks under Heterophily. InAdvances in Neural Information Processing Systems, A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, a...

    2023

  43. [51]

    Ningyi Liao, Siqiang Luo, Xiang Li, and Jieming Shi. 2023. LD2: Scalable Het- erophilous Graph Neural Network with Decoupled Embeddings. InThirty-seventh Conference on Neural Information Processing Systems. https://openreview.net/ forum?id=7zkFc9TGKz

    2023

  44. [52]

    Ningyi Liao, Dingheng Mo, Siqiang Luo, Xiang Li, and Pengcheng Yin. 2024. Scalable decoupling graph neural network with feature-oriented optimization. The VLDB Journal33, 3 (2024), 667–683

    2024

  45. [53]

    Derek Lim, Felix Matthew Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Prasad Bhalerao, and Ser-Nam Lim. 2021. Large Scale Learning on Non- Homophilous Graphs: New Benchmarks and Strong Simple Methods. InAdvances in Neural Information Processing Systems, A. Beygel...

    2021

  46. [54]

    Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He

  47. [55]

    Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph Summa- rization Methods and Applications: A Survey.ACM Comput. Surv.51, 3, Article 62 (jun 2018), 34 pages. doi:10.1145/3186727

    2018 doi

  48. [56]

    Andreas Loukas. 2019. Graph Reduction with Spectral and Cut Guarantees. Journal of Machine Learning Research20, 116 (2019), 1–42. http://jmlr.org/papers/ v20/18-680.html

    2019

  49. [57]

    Andreas Loukas and Pierre Vandergheynst. 2018. Spectrally Approximating Large Graphs with Smaller Graphs. InProceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, 32...

    2018

  50. [58]

    Li, Jian Tang, Guy Wolf, and Stefanie Jegelka

    Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Chang, Doina Precup, Rex Ying, Stan Z. Li, Jian Tang, Guy Wolf, and Stefanie Jegelka. 2024. The Heterophilic Graph Learning Hand- book: Benchmarks, Models, Theoretical Analysis, Applic...

    2024 arXiv

  51. [59]

    Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2022. Revisiting Heterophily For Graph Neural Networks. InAdvances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, ...

    2022

  52. [60]

    Sheng, Hui Xiong, and Leman Akoglu

    Xiaoxiao Ma, Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z. Sheng, Hui Xiong, and Leman Akoglu. 2023. A Comprehensive Survey on Graph Anom- aly Detection With Deep Learning.IEEE Transactions on Knowledge and Data Engineering35, 12 (2023), 12012–12038. doi:10.1109/TKDE.2021.3118815

    2023

  53. [61]

    James MacQueen et al. 1967. Some methods for classification and analysis of multivariate observations. InProceedings of the fifth Berkeley symposium on mathematical statistics and probability, Vol. 1. Oakland, CA, USA, 281–297

    1967

  54. [62]

    2009.An introduction to information retrieval

    Christopher D Manning. 2009.An introduction to information retrieval

    2009

  55. [63]

    Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. 2023. A Fractional Graph Laplacian Approach to Oversmoothing. InAdvances in Neural Information Processing Systems, A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36. Curran Associ...

    2023

  56. [64]

    Naoto Ohsaka, Tomohiro Sonobe, Sumio Fujita, and Ken-ichi Kawarabayashi

  57. [65]

    Antonio Ortega, Pascal Frossard, Jelena Kovačević, José M. F. Moura, and Pierre Vandergheynst. 2018. Graph Signal Processing: Overview, Challenges, and Ap- plications.Proc. IEEE106, 5 (2018), 808–828. doi:10.1109/JPROC.2018.2820126

    2018

  58. [66]

    Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-GCN: Geometric Graph Convolutional Networks. InInternational Confer- ence on Learning Representations. https://openreview.net/forum?id=S1e2agrFvS

    2020

  59. [67]

    2003.Interpolation and approximation by polynomials

    George M Phillips. 2003.Interpolation and approximation by polynomials. Vol. 14. Springer New York. doi:10.1007/b97417

    2003 doi

  60. [68]

    Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. 2023. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. InThe Eleventh International Conference on Learning Representations. https://openrevie...

    2023

  61. [69]

    Aditya Prakash, Chanhyun Kang, Yao Zhang, and V.S

    Manish Purohit, B. Aditya Prakash, Chanhyun Kang, Yao Zhang, and V.S. Sub- rahmanian. 2014. Fast influence-based coarsening for large networks(KDD ’14). Association for Computing Machinery, New York, NY, USA, 1296–1305. doi:10.1145/2623330.2623701

    2014

  62. [70]

    Hezhe Qiao, Hanghang Tong, Bo An, Irwin King, Charu Aggarwal, and Guansong Pang. 2024. Deep Graph Anomaly Detection: A Survey and New Perspectives. arXiv:2409.09957 [cs.LG] https://arxiv.org/abs/2409.09957

    2024 arXiv

  63. [71]

    2020.Chebyshev polynomials

    Theodore J Rivlin. 2020.Chebyshev polynomials. Courier Dover Publications

    2020

  64. [72]

    Aliaksei Sandryhaila and José M. F. Moura. 2013. Discrete Signal Processing on Graphs.IEEE Transactions on Signal Processing61, 7 (2013), 1644–1656. doi:10. 1109/TSP.2013.2238935

    2013

  65. [73]

    Aliaksei Sandryhaila and José M. F. Moura. 2013. Discrete signal processing on graphs: Graph filters. In2013 IEEE International Conference on Acoustics, Speech and Signal Processing. 6163–6166. doi:10.1109/ICASSP.2013.6638849

    2013

  66. [74]

    Aliaksei Sandryhaila and José M. F. Moura. 2013. Discrete signal processing on graphs: Graph fourier transform. In2013 IEEE International Conference on Acoustics, Speech and Signal Processing. 6167–6170. doi:10.1109/ICASSP.2013. 6638850

    2013 doi

  67. [75]

    Gordon K Smyth. 1998. Polynomial approximation.Encyclopedia of Biostatistics 13 (1998)

    1998

  68. [76]

    Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. 2023. Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. InThe Eleventh International Conference on Learning Representations. https: //openreview.net/forum?id=wKPmPBHSnT6

    2023

  69. [77]

    2006.Linear algebra and its applications.Belmont, CA: Thomson, Brooks/Cole

    Gilbert Strang. 2006.Linear algebra and its applications.Belmont, CA: Thomson, Brooks/Cole

    2006

  70. [78]

    Jiaqi Sun, Lin Zhang, Guangyi Chen, Peng Xu, Kun Zhang, and Yujiu Yang

  71. [79]

    Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. 2022. Rethinking Graph Neural Networks for Anomaly Detection. InProceedings of the 39th International Confer- ence on Machine Learning (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le...

    2022

  72. [80]

    Xiyuan Wang and Muhan Zhang. 2022. How Powerful are Spectral Graph Neural Networks. InProceedings of the 39th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 162), Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gan...

    2022

  73. [81]

    Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. InProceedings of the 36th International Conference on Machine Learning, Vol. 97. PMLR, 6861–6871. https://proceedings.mlr.press/v97/wu19e.html

    2019

  74. [82]

    Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. 2022. Node- Former: A Scalable Graph Structure Learning Transformer for Node Classification. InAdvances in Neural Information Processing Systems, Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho (E...

    2022

  75. [83]

    Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks.IEEE Transactions on Neural Networks and Learning Systems32, 1 (2021), 4–24. doi:10. 1109/TNNLS.2020.2978386

    2021

  76. [84]

    Lianghao Xia, Yong Xu, Chao Huang, Peng Dai, and Liefeng Bo. 2021. Graph Meta Network for Multi-Behavior Recommendation. InThe 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. 757–766. doi:10.1145/3404835.3462972

    2021

  77. [85]

    Cohen, and Ruslan Salakhutdinov

    Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. 2016. Revisiting Semi- Supervised Learning with Graph Embeddings. doi:10.48550/ARXIV.1603.08861

    2016 doi arXiv

  78. [86]

    Yuan Zhang, Dong Wang, and Yan Zhang. 2019. Neural IR Meets Graph Embed- ding: A Ranking Model for Product Search. InThe World Wide Web Conference (San Francisco, CA, USA)(WWW ’19). Association for Computing Machinery, New York, NY, USA, 2390–2400. doi:10.1145/3308558.3313468

    2019

  79. [87]

    Da Zheng, Xiang Song, Chengru Yang, Dominique LaSalle, and George Karypis

  80. [88]

    Shuai Zheng, Zhenfeng Zhu, Zhizhe Liu, Youru Li, and Yao Zhao. 2023. Node- Oriented Spectral Filtering for Graph Neural Networks.IEEE Transactions on Pattern Analysis and Machine Intelligence46, 1 (2023), 388–402. doi:10.1109/ TPAMI.2023.3324937

    2023

  81. [89]

    Yu, and Shirui Pan

    Xin Zheng, Yi Wang, Yixin Liu, Ming Li, Miao Zhang, Di Jin, Philip S. Yu, and Shirui Pan. 2024. Graph Neural Networks for Graphs with Heterophily: A Survey. arXiv:2202.07082 [cs.LG] https://arxiv.org/abs/2202.07082

    2024 arXiv

  82. [90]

    Yu Zhou, Haixia Zheng, Xin Huang, Shufeng Hao, Dengao Li, and Jumin Zhao

  83. [91]

    mixture-wise

    Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. InAdvances in Neural Information Processing Systems, Vol. 33. Curran Associates, Inc., 7793–7804. http...

    2020

  84. [93]

    InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(Washington DC, USA) (KDD ’22)

    Distributed Hybrid CPU and GPU training for Graph Neural Networks on Billion-Scale Heterogeneous Graphs. InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(Washington DC, USA) (KDD ’22). Association for Computing Machinery, New York, NY, USA...

  85. [97]

    doi:10.1145/3495161

    Graph Neural Networks: Taxonomy, Advances, and Trends.ACM Transac- tions on Intelligent Systems and Technology13, 1, Article 15 (jan 2022), 54 pages. doi:10.1145/3495161

    2022 doi

  86. [2017]

    InProceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA)(SIGMOD ’17)

    Coarsening Massive Influence Networks for Scalable Diffusion Analysis. InProceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA)(SIGMOD ’17). Association for Computing Machinery, New York, NY, USA, 635–650. doi:10.1145/3035918.3064045

    2017

  87. [2020]

    InInternational Conference on Learning Representations

    GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding. InInternational Conference on Learning Representations. https: //openreview.net/forum?id=r1lGO0EKDH

  88. [2021]

    InProceedings of the Web Conference 2021(Ljubljana, Slovenia)(WWW ’21)

    Pick and Choose: A GNN-based Imbalanced Learning Approach for Fraud Detection. InProceedings of the Web Conference 2021(Ljubljana, Slovenia)(WWW ’21). Association for Computing Machinery, New York, NY, USA, 3168–3177. doi:10.1145/3442381.3449989

    2021

  89. [2022]

    https://doi.org/10.1145/3485447.3512201

    1550–1558. https://doi.org/10.1145/3485447.3512201

  90. [2023]

    InProceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol

    Feature Expansion for Graph Neural Networks. InProceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202). PMLR, 33156–33176

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.