FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance

• URL: http://arxiv.org/abs/2510.27136v1
• Date: Fri, 31 Oct 2025 03:20:48 GMT
• Title: FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance
• Authors: Minh Phu Vuong, Young-Ju Lee, Iván Ojeda-Ruiz, Chul-Ho Lee,
• Abstract summary: 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.
• Score: 1.2516203168932827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the growing concern about unsavory behaviors of machine learning models toward certain demographic groups, the notion of 'fairness' has recently drawn much attention from the community, thereby motivating the study of fairness in graph clustering. Fair graph clustering aims to partition the set of nodes in a graph into $k$ disjoint clusters such that the proportion of each protected group within each cluster is consistent with the proportion of that group in the entire dataset. It is, however, computationally challenging to incorporate fairness constraints into existing graph clustering algorithms, particularly for large graphs. To address this problem, we propose FairAD, a computationally efficient fair graph clustering method. It first constructs a new affinity matrix based on the notion of algebraic distance such that fairness constraints are imposed. A graph coarsening process is then performed on this affinity matrix to find representative nodes that correspond to $k$ clusters. Finally, a constrained minimization problem is solved to obtain the solution of fair clustering. Experiment results on the modified stochastic block model and six public datasets show that FairAD can achieve fair clustering while being up to 40 times faster compared to state-of-the-art fair graph clustering algorithms.

Related papers

• Incorporating Fairness in Neighborhood Graphs for Fair Spectral Clustering [0.0]
  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.
  arXiv  Detail & Related papers  (2025-12-10T16:25:24Z)
• Deep Cut-informed Graph Embedding and Clustering [36.17182061654739]
  We propose an innovative and non-GNN-based Deep Cut-informed Graph embedding and Clustering framework, namely DCGC.<n>For the encoding module, we derive a cut-informed graph embedding objective to fuse graph structure and attributes by minimizing their joint normalized cut.<n>For the clustering module, we utilize the optimal transport theory to obtain the clustering assignments.
  arXiv  Detail & Related papers  (2025-03-09T14:24:09Z)
• A Semidefinite Relaxation Approach for Fair Graph Clustering [1.03590082373586]
  This study introduces fair graph clustering within the framework of the disparate impact doctrine. We employ a semidefinite relaxation approach to approximate the underlying optimization problem.
  arXiv  Detail & Related papers  (2024-10-19T22:51:24Z)
• Fair Clustering with Minimum Representation Constraints [2.707154152696381]
  We study the k-means and k-medians clustering problems under the additional fairness constraint that each group must attain a minimum level of representation in at least a specified number of clusters.<n>We present several strategies that make the approach practical even for large datasets.
  arXiv  Detail & Related papers  (2024-09-04T00:13:40Z)
• Learning Uniform Clusters on Hypersphere for Deep Graph-level Clustering [25.350054742471816]
  We propose a novel deep graph-level clustering method called Uniform Deep Graph Clustering (UDGC) UDGC assigns instances evenly to different clusters and then scatters those clusters on unit hypersphere, leading to a more uniform cluster-level distribution and a slighter cluster collapse. Our empirical study on eight well-known datasets demonstrates that UDGC significantly outperforms the state-of-the-art models.
  arXiv  Detail & Related papers  (2023-11-23T12:08:20Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  A deep graph clustering method (Dink-Net) is proposed with the idea of dilation and shrink. By discriminating nodes, whether being corrupted by augmentations, representations are learned in a self-supervised manner. The clustering distribution is optimized by minimizing the proposed cluster dilation loss and cluster shrink loss. Compared to the runner-up, Dink-Net 9.62% achieves NMI improvement on the ogbn-papers100M dataset with 111 million nodes and 1.6 billion edges.
  arXiv  Detail & Related papers  (2023-05-28T15:33:24Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• 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)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  We propose a novel attributed graph clustering network, namely Self-supervised Contrastive Attributed Graph Clustering (SCAGC) In SCAGC, by leveraging inaccurate clustering labels, a self-supervised contrastive loss, are designed for node representation learning. For the OOS nodes, SCAGC can directly calculate their clustering labels.
  arXiv  Detail & Related papers  (2021-10-15T03:25:28Z)
• 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)

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.