Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering

• URL: http://arxiv.org/abs/2512.09810v1
• Date: Wed, 10 Dec 2025 16:25:24 GMT
• Title: Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering
• Authors: Adithya K Moorthy, V Vijaya Saradhi, Bhanu Prasad,
• Abstract summary: This research introduces novel approaches for constructing fair k-nearest neighbor (kNN) and fair epsilon-neighborhood graphs.<n>Our approaches incorporate proportional representation of sensitive features into the local graph structure while maintaining geometric consistency.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph clustering plays a pivotal role in unsupervised learning methods like spectral clustering, yet traditional methods for graph clustering often perpetuate bias through unfair graph constructions that may underrepresent some groups. The current research introduces novel approaches for constructing fair k-nearest neighbor (kNN) and fair epsilon-neighborhood graphs that proactively enforce demographic parity during graph formation. By incorporating fairness constraints at the earliest stage of neighborhood selection steps, our approaches incorporate proportional representation of sensitive features into the local graph structure while maintaining geometric consistency.Our work addresses a critical gap in pre-processing for fair spectral clustering, demonstrating that topological fairness in graph construction is essential for achieving equitable clustering outcomes. Widely used graph construction methods like kNN and epsilon-neighborhood graphs propagate edge based disparate impact on sensitive groups, leading to biased clustering results. Providing representation of each sensitive group in the neighborhood of every node leads to fairer spectral clustering results because the topological features of the graph naturally reflect equitable group ratios. This research fills an essential shortcoming in fair unsupervised learning, by illustrating how topological fairness in graph construction inherently facilitates fairer spectral clustering results without the need for changes to the clustering algorithm itself. Thorough experiments on three synthetic datasets, seven real-world tabular datasets, and three real-world image datasets prove that our fair graph construction methods surpass the current baselines in graph clustering tasks.

Related papers

• FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance [1.2516203168932827]
  Fair graph clustering aims to partition a set of nodes in a graph into $k$ disjoint clusters.<n>It is, however, computationally challenging to incorporate fairness constraints into existing graph clustering algorithms.<n>We propose FairAD, a computationally efficient fair graph clustering method.<n>Experiment results show that FairAD can achieve fair clustering while being up to 40 times faster than state-of-the-art fair graph clustering algorithms.
  arXiv  Detail & Related papers  (2025-10-31T03:20:48Z)
• GLANCE: Graph Logic Attention Network with Cluster Enhancement for Heterophilous Graph Representation Learning [47.674647127050186]
  Graph Neural Networks (GNNs) have demonstrated significant success in learning from graph-structured data but often struggle on heterophilous graphs.<n>We propose GLANCE, a novel framework that integrates logic-guided reasoning, dynamic graph refinement, and adaptive clustering to enhance graph representation learning.
  arXiv  Detail & Related papers  (2025-07-24T15:45:26Z)
• Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models [22.421702511126373]
  We leverage statistical inference on block models to guide the development of a spectral clustering algorithm for directed graphs.<n>We establish a theoretical upper bound on the misclustering error of its spectral relaxation, and based on this relaxation, introduce a novel, self-adaptive spectral clustering method for directed graphs.
  arXiv  Detail & Related papers  (2024-03-28T15:47:13Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• A Unified Framework for Fair Spectral Clustering With Effective Graph Learning [12.343382413705394]
  We consider the problem of spectral clustering under group fairness constraints. In practice, the graph is usually unknown, and we need to construct the underlying graph from potentially noisy data. We propose a novel graph construction method with a node-adaptive graph filter to learn graphs from noisy data.
  arXiv  Detail & Related papers  (2023-11-23T01:43:00Z)
• Homophily-enhanced Structure Learning for Graph Clustering [19.586401211161846]
  Graph structure learning allows refining the input graph by adding missing links and removing spurious connections. Previous endeavors in graph structure learning have predominantly centered around supervised settings. We propose a novel method called textbfhomophily-enhanced structure textbflearning for graph clustering (HoLe)
  arXiv  Detail & Related papers  (2023-08-10T02:53:30Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  This paper proposes a novel self-supervised learning method, termed as Geometry Contrastive Learning (GCL) GCL views a heterogeneous graph from Euclidean and hyperbolic perspective simultaneously, aiming to make a strong merger of the ability of modeling rich semantics and complex structures. Extensive experiments on four benchmarks data sets show that the proposed approach outperforms the strong baselines.
  arXiv  Detail & Related papers  (2022-06-25T03:54:53Z)
• Koopman-based spectral clustering of directed and time-evolving graphs [0.3655021726150368]
  spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems. However, clustering directed graphs remains notoriously difficult and there is no universally accepted definition of clusters in directed graphs. We derive clustering algorithms for directed and time-evolving graphs using relationships between Laplacians and transfer operators. The resulting clusters can be interpreted as coherent sets, which play an important role in the analysis of transport and mixing processes in fluid flows.
  arXiv  Detail & Related papers  (2022-04-06T17:33:24Z)
• Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
  We propose a novel unsupervised graph representation model by contrasting cluster assignments, called as GRCCA. It is motivated to make good use of local and global information synthetically through combining clustering algorithms and contrastive learning. GRCCA has strong competitiveness in most tasks.
  arXiv  Detail & Related papers  (2021-12-15T07:28:58Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.