# HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity

arXiv: https://arxiv.org/abs/2405.17050 · HTML: https://mlsanity.com/paper/2405.17050/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 27 May 2024.

## Builds on (most cited first, 16 of 16)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Learning Graph Embedding with Adversarial Training Methods](https://mlsanity.com/paper/1901.01250/) (2019)
- [Disentangled Representation Learning and Generation with Manifold Optimization](https://mlsanity.com/paper/2006.07046/) (2020)
- [MUSE: Multi-View Contrastive Learning for Heterophilic Graphs](https://mlsanity.com/paper/2307.16026/) (2023)
- [Learning with Asymmetric Kernels: Least Squares and Feature Interpretation](https://mlsanity.com/paper/2202.01397/) (2022)
- [Homophily-enhanced Structure Learning for Graph Clustering](https://mlsanity.com/paper/2308.05309/) (2023)
- [Unsupervised Neighborhood Propagation Kernel Layers for Semi-supervised Node Classification](https://mlsanity.com/paper/2301.13764/) (2023)

## Built on by (most cited first, 2 of 2)

- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [When Connected Does Not Mean Similar: Charting the Homophily Boundary of SNAP-KG for Streaming Entity Integration](https://mlsanity.com/paper/2609.12356/) (2026)

## Abstract (arXiv)

Clustering nodes in heterophilous graphs is challenging as traditional methods assume that effective clustering is characterized by high intra-cluster and low inter-cluster connectivity. To address this, we introduce HeNCler-a novel approach for Heterophilous Node Clustering. HeNCler learns a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition. Our approach enables spectral clustering on an asymmetric similarity graph, providing flexibility for both directed and undirected graphs. By solving the primal problem directly, our method overcomes the computational difficulties of traditional adjacency partitioning-based approaches. Experimental results show that HeNCler significantly improves node clustering performance in heterophilous graph settings, highlighting the advantage of its asymmetric graph-learning framework.