In recent years, graph-partition-based clustering algorithms have attracted increasing attention. These algorithms first construct a graph over the data points and then partition this graph, regarding each connected subgraph in the partitioned graph as a cluster. However, traditional graph-partition-based clustering algorithms face challenges when clustering datasets with highly imbalanced density distributions. This is because, during the process of graph partitioning, they mainly rely on edge lengths and largely ignore local density variations. To address this issue, we propose the Adaptive Graph Partitioning (AGP) clustering algorithm. AGP integrates local density information into the partitioning process and adaptively normalizes the magnitudes of edge weights in both sparse and dense regions. This enhancement allows AGP to avoid the over-partitioning of dense clusters, effectively addressing a common problem in traditional graph-partition-based clustering algorithms. Additionally, the mechanism of connectivity domain differences is introduced into AGP, further enhancing the algorithm’s ability to discriminate between neighboring clusters that are difficult to separate. Extensive experiments on 13 benchmark datasets show that AGP achieves the best clustering performance on 7 datasets and performs competitively on the others, especially when density imbalance is severe. Moreover, scalability experiments on datasets with up to 100,000 data points, together with complexity analysis, demonstrate that AGP enjoys favorable time and memory efficiency compared with representative baselines.

Discovering causal relationships among observed variables is an important research focus in data mining. Existing causal discovery approaches are mainly based on constraint-based methods and functional causal models (FCMs). However, the constraint-based method cannot identify the Markov equivalence class and the functional causal models cannot identify the complex interrelationships when multiple variables affect one variable. To address the two aforementioned problems, we propose a new graph structure Causal Star Graph (CSG) and a corresponding framework Causal Discovery via Causal Star Graphs (CD-CSG) to divide a causal directed acyclic graph into multiple CSGs for causal discovery. In this framework, we also propose a generalized learning in CSGs based on a variational approach to learn the representative intermediate variable of CSG’s non-central variables. Through the generalized learning in CSGs, the asymmetry in the forward and backward model of CD-CSG can be found to identify the causal directions in the directed acyclic graphs. We further divide the CSGs into three categories and provide the causal identification principle under each category in our proposed framework. Experiments using synthetic data show that the causal relationships between variables can be effectively identified with CD-CSG and the accuracy of CD-CSG is higher than the best existing model. By applying CD-CSG to real-world data, our proposed method can greatly augment the applicability and effectiveness of causal discovery.

Discovering causal relationships among observed variables is a new research focus in the area of data mining. Methods based on the additive noise model have been proved to be efficient in the identification of cause-effect pairs. However, when trying to determine many-to-one causality, additive noise models often fail to identify the causal direction due to the complex interrelationships and interactions even though the generation of each causal relation follows the additive noise model, and become unreliable in practical applications. In this work, to identify the causal direction, we propose a Hierarchical Additive Noise Model (HANM) to convert many-to-one causality into an approximate one-to-one causality by generalizing multiple factors into an intermediate variable with a variational approach, and use asymmetry in the forward model and backward model of HANM to identify causal direction. Experiments using synthetic data show that many-to-one causality can be effectively identified through asymmetry with our proposed HANM and the accuracy of HANM is higher than the best existing model. By applying the model to real-world data, it can be seen that HANM can greatly augment the application scope of functional causal models for causal discovery.