Loading...
Send to Friend
 Bookmark
 Review List
  1. Explainable graph clustering via expanders in the massively parallel computation model (Property)
  2. Simple search
  3. Search result

Explainable graph clustering via expanders in the massively parallel computation model

Aghamolaei, S ; Sharif University of Technology | 2024

88 Viewed
  1. Type of Document: Article
  2. DOI: 10.1016/j.ins.2024.120897
  3. Publisher: 2024
  4. Abstract:
  5. Explainable clustering provides human-understandable reasons for decisions in black-box learning models. In a previous work, a decision tree built on the set of dimensions was used to define ranges of values for k-means clusters. For explainable graph clustering, we use expander graphs instead of dense subgraphs since powering an expander graph is guaranteed to result in a clique after at most a logarithmic number of steps. Consider a set of multi-dimensional points labeled with k labels. We introduce the heat map sorting problem as reordering the rows and columns of an input matrix (each point is a column and each row is a dimension) such that the labels of the entries of the matrix form connected components (clusters). A cluster is preserved if it remains connected, i.e., if it is not split into several clusters and no two clusters are merged. In the massively parallel computation model (MPC), each machine has a sublinear memory and the total memory of the machines is linear. We prove the problem is NP-hard. We give a fixed-parameter algorithm in MPC and an approximation algorithm based on expander decomposition. We empirically compare our algorithm with explainable k-means on several graphs of email and computer networks. © 2024 Elsevier Inc
  6. Keywords:
  7. Computation theory ; Decision trees ; K-means clustering ; Matrix algebra ; Parameter estimation ; Clusterings ; DBSCAN ; Expander graphs ; Explainable clustering ; Fixed-parameter algorithms ; Graph clustering ; Massively parallel computation ; Massively parallels ; Parallel Computation ; Parallel computation model ; Approximation algorithms
  8. Source: Information Sciences ; Volume 677 , 2024 ; 00200255 (ISSN)
  9. URL: https://www.sciencedirect.com/science/article/abs/pii/S0020025524008119