# A Foundational Perspective for Partitional Clustering on Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 27 Jul 2026.

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)

## Abstract (arXiv)

This study presents a theoretical analysis of partitional clustering on networks, analyzing both hard and soft assignment schemes with different objective functions. Cluster centers are not restricted to vertices but can also be located along the edges. We examine four key models: P-Median (PMP) and Sum of Squares Clustering (SSC) under hard assignment, and Probabilistic Distance Clustering (PDC) and Fuzzy C-Means (FCM) under soft assignment. Through mathematical analysis, we uncover structural properties that differentiate these models, such as the significance of assignment bottleneck points and the role of vertex-restricted solutions in determining optimal cluster centers. Our findings reveal that, while SSC and FCM can yield optimal centers along edges, PMP and PDC inherently favor vertex placement, leading to insights into clustering behavior on networks. These insights offer new directions for designing efficient algorithms and have implications ranging from facility location and network design to clustering on the embedding graphs that power similarity search in modern retrieval systems.