HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity

• URL: http://arxiv.org/abs/2405.17050v2
• Date: Tue, 24 Jun 2025 10:34:05 GMT
• Title: HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity
• Authors: Sonny Achten, Zander Op de Beeck, Francesco Tonin, Volkan Cevher, Johan A. K. Suykens,
• Abstract summary: HeNCler learns a similarity graph by optimizing a clustering-specific objective based on weighted kernel singular value decomposition.<n>Our approach enables spectral clustering on an asymmetric similarity graph, providing flexibility for both directed and undirected graphs.
• Score: 48.62389920549271
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Reliable Node Similarity Matrix Guided Contrastive Graph Clustering [51.23437296378319]
  We introduce a new framework, Reliable Node Similarity Matrix Guided Contrastive Graph Clustering (NS4GC) Our method introduces node-neighbor alignment and semantic-aware sparsification, ensuring the node similarity matrix is both accurate and efficiently sparse.
  arXiv  Detail & Related papers  (2024-08-07T13:36:03Z)
• Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
  Multi-view clustering methods based on anchor graph factorization lack adequate cluster interpretability for the decomposed matrix. We address this limitation by using non-negative tensor factorization to decompose an anchor graph tensor that combines anchor graphs from multiple views.
  arXiv  Detail & Related papers  (2024-04-01T03:23:55Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability. We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition. The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
  arXiv  Detail & Related papers  (2023-12-07T06:19:39Z)
• 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)
• 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)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Simplifying Clustering with Graph Neural Networks [5.571369922847262]
  This paper shows that a graph neural network, equipped with suitable message passing layers, can generate good cluster assignments by optimizing only a balancing term. Results on attributed graph datasets show the effectiveness of the proposed approach in terms of clustering performance and time.
  arXiv  Detail & Related papers  (2022-07-18T17:36:54Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  Cut-based directed graph (digraph) clustering often focuses on finding dense within-cluster or sparse between-cluster connections. For flow-based clusterings the edges between clusters tend to be oriented in one direction and have been found in migration data, food webs, and trade data.
  arXiv  Detail & Related papers  (2022-03-02T20:07:04Z)
• Robust Correlation Clustering with Asymmetric Noise [3.8073142980733]
  Correlation Clustering is a graph clustering formulation which: (1) takes as input a signed graph with edge weights representing a similarity/dissimilarity measure between the nodes, and (2) requires no prior estimate of the number of clusters in the input graph. We propose a novel graph generative model, called the Node Factors Model (NFM), which is based on generating feature vectors/embeddings for the graph nodes.
  arXiv  Detail & Related papers  (2021-10-15T21:47:27Z)
• 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)
• Interpretable Clustering on Dynamic Graphs with Recurrent Graph Neural Networks [24.017988997693262]
  We study the problem of clustering nodes in a dynamic graph, where the connections between nodes and nodes' cluster memberships may change over time. We first propose a simple decay-based clustering algorithm that clusters nodes based on weighted connections between them, where the weight decreases at a fixed rate over time. We characterize the optimal decay rate for each cluster and propose a clustering method that achieves almost exact recovery of the true clusters.
  arXiv  Detail & Related papers  (2020-12-16T04:31:19Z)
• Smoothness Sensor: Adaptive Smoothness-Transition Graph Convolutions for Attributed Graph Clustering [10.905770964670191]
  We propose a smoothness sensor for attributed graph clustering based on adaptive smoothness-transition graph convolutions. As an alternative to graph-level smoothness, a novel fine-gained node-wise level assessment of smoothness is proposed. Experiments show that the proposed methods significantly outperform 12 other state-of-the-art baselines in terms of three different metrics.
  arXiv  Detail & Related papers  (2020-09-12T08:12:27Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)

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.