ECG outperforms graph clustering algorithms using ensemble method.
problem Graph clustering challenges.
method ECG combines Louvain algorithm and consensus clustering.
result ECG outperforms leading algorithms on artificial networks.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,291 papers · 148 categories
Trend · papers per month
48 results for “graph clustering algorithms”
Benchmarked over 70 graph clustering algorithms.
problem Lack of comprehensive performance comparison for graph clustering algorithms.
method Evaluated 70+ graph clustering programs for runtime and quality on weighted and unweighted graphs, analyzed ground truth characteristics.
result Supply a start point for engineers and viewpoint for researchers.
New algorithm speeds up spectral clustering for dynamic graphs.
problem Prohibitive complexity of spectral clustering for dynamic graphs.
method Reuse past cluster assignments and use fast Chebyshev graph filtering.
result Achieves clustering quality approximating spectral clustering with significant complexity benefits.
Graph clustering uses multiscale community detection for improved performance.
problem Improving data clustering accuracy and robustness.
method Graph-theoretical approach combining multiscale community detection.
result Multiscale graph-based clustering achieves better performance than traditional methods.
AMOS automates model order selection for spectral graph clustering.
problem Automated selection of the correct number of clusters in spectral graph clustering.
method Incrementally increases the number of clusters, estimates cluster quality, and provides reliability tests.
result AMOS outputs clusters of minimal model order with statistical guarantees.
ECG improves graph clustering and resolves resolution limit issues.
problem Graph clustering resolution limit issue.
method ECG uses consensus clustering to improve graph clustering.
result ECG alleviates the resolution limit issue and improves partition stability.
Improved spectral clustering algorithm for better performance.
problem Improving the performance of spectral clustering algorithms.
method Developed a new performance guarantee under a weaker assumption and evaluated using a different spectral embedding map.
result Better performance guarantee under a weaker assumption and evaluation of a new spectral embedding map.
Interpolates mean shift and spectral clustering on graphs.
problem Data clustering algorithms.
method Fokker-Planck equations on data graphs.
result New theoretical insights on diffusion maps and mean shift dynamics.
PASCO speeds up graph clustering for large graphs.
problem Efficiently clustering large graphs with many communities.
method Overlay method combining coarsening and parallel clustering.
result PASCO accelerates clustering with improved efficiency and quality.
KCoreMotif clusters large networks efficiently by exploiting k-core decomposition and motifs.
problem Efficiently clustering large networks for trust evaluation.
method Exploits k-core decomposition and motifs to perform motif-based spectral clustering on k-core subgraphs.
result The proposed algorithm is accurate and efficient for large networks.
This paper analyzes various graph clustering methods and their applications.
problem Dividing graphs into homogeneous groups for diverse applications.
method Traditional and deep learning-based clustering methods are compared.
result Deep learning techniques improve clustering accuracy.
Enhanced spectral clustering for geometric graphs improves clustering accuracy.
problem Ineffective standard spectral clustering for geometric graphs.
method Higher-order spectral clustering using higher-order eigenvectors.
result Established weak and strong consistency for Soft Geometric Block Model.
A new spectral clustering algorithm uses convex programming for better cluster identification.
problem Improving spectral clustering for better cluster identification in well-clustered graphs.
method Uses convex programming in the grouping stage of spectral clustering.
result The algorithm can find clusters of nodes with minimal conductance for well-clustered graphs.
Two spectral algorithms detect clusters in directed graphs with cyclic or acyclic patterns.
problem Detecting clusters in directed graphs with cyclic or acyclic patterns.
method Computation of extremal eigenvalues of the transition matrix associated with the directed graph.
result The proposed methods outperform state-of-the-art methods on synthetic datasets and real-world networks.
A scalable framework for clustering large graphs using randomized sketching.
problem Clustering large partially observed graphs efficiently.
method Randomized graph sketching, correlation-based retrieval, uniform and degree-based node sampling.
result Improved phase transitions for clustering with reduced computational complexity and minimum cluster size.
New methods for clustering graphs using spectral analysis.
problem Graph clustering for complex systems.
method Transfer operators and spectral properties.
result Spectral clustering can be interpreted using Koopman operators.
StruClus clusters large graph datasets efficiently and interpretably.
problem Clustering large-scale graph databases efficiently and interpretably.
method Frequent subgraph sampling, projection-based clustering, parallelization.
result StruClus achieves high quality clusterings with linear runtime growth and interpretability.
New method clusters directed graphs using Koopman operators.
problem Challenges in clustering directed graphs, especially complex eigenvalues and lack of cluster definition.
method Relate graph Laplacians to transfer operators and metastable sets in stochastic systems, derive clustering algorithms for directed and time-evolving graphs.
result Clusters can be interpreted as coherent sets, useful for analyzing transport and mixing processes.
Proposes a deep learning approach for attributed graph clustering.
problem Suboptimal performance in graph clustering due to two-step frameworks.
method Goal-directed deep learning approach using attention networks and inner product decoders.
result Superior performance compared to state-of-the-art algorithms.
We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one first has to construct a graph on the data points and then apply a graph clustering algorithm to find a suitable partition of the graph. Our main question is if and how the construction of the graph (…
MARCO-GE selects clustering algorithms using graph embeddings.
problem Automated selection of clustering algorithms for unseen datasets.
method Transform datasets into graphs, extract latent representations, train a ranking meta-model.
result MARCO-GE outperforms state-of-the-art approaches in algorithm recommendation.
This paper develops a multilayer spectral clustering method for heterogeneous data.
problem Clustering in multilayer graphs with varying layer weights and structures.
method Convex layer aggregation for multilayer spectral graph clustering (SGC).
result Phase transition analysis and automated cluster assignment with statistical guarantees.
New clustering method avoids problematic properties of existing algorithms.
problem Existing clustering algorithms cannot satisfy all natural clustering properties.
method Developed Morse Clustering using Morse Theory to satisfy Kleinberg's axioms with a new property, Monotonic Consistency.
result Morse Clustering satisfies Kleinberg's original axioms with Consistency replaced by Monotonic Consistency.
A novel multi-view spectral clustering model fuses and clusters data views.
problem Fusing and clustering multi-view data effectively.
method Simultaneously fuses and clusters views into a single graph.
result The proposed method outperforms existing techniques.
New spectral clustering for directed graphs reveals socio-economic patterns.
problem Spectral clustering for directed graphs is unsatisfactory due to edge directionality.
method Proposes a complex-valued matrix representation and analysis for directed graphs.
result Our approach reveals socio-economic patterns in internal migration data.
Paper analyzes spectral clustering for large graphs using random signals.
problem Complex eigen decomposition for large graphs.
method Graph filtering of random signals for approximate spectral embedding.
result Consistency of spectral clustering in stochastic block model.
Algorithm predicts graph label changes online with cluster specialists.
problem Online prediction of graph label changes with changing data.
method Specialist approach with cluster specialists, focusing on probabilistic cluster structure.
result Algorithm achieves time complexity, significantly faster than existing methods.
Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: an algorithm that serially clusters neighborhoods of vertices, and obtains a 3-approximation ratio. Unfortunately, KwikCluster in practice re…
This paper proposes an organized generalization of Newman and Girvan's modularity measure for graph clustering. Optimized via a deterministic annealing scheme, this measure produces topologically ordered graph clusterings that lead to faithful and readable graph representations based on clustering induced graphs. Topog…
New algorithms detect outliers in high-dimensional data with arbitrary shapes.
problem Challenges of high dimensionality and varying cluster shapes in traditional outlier detection methods.
method Cluster Catch Digraphs (CCDs) and their variants (U-MCCD, UN-MCCD, SU-MCCD, SUN-MCCD).
result U-MCCD efficiently identifies outliers with high true negative rates, and SU-MCCD improves handling of non-uniform clusters.
A new clustering algorithm inspired by Wittgenstein's philosophy.
problem Clustering data without assuming predefined cluster shapes or sizes.
method Wittgenstein's family resemblance concept applied to machine learning.
result WFR clustering algorithm effectively identifies clusters in data.
Cluster-GCN efficiently trains deep GCNs on large graphs without memory or computational constraints.
problem Training large-scale GCNs is computationally and memory-intensive.
method Cluster-GCN exploits graph clustering to restrict neighborhood search to dense subgraphs, reducing memory and computational requirements.
result Cluster-GCN achieves comparable test accuracy to previous algorithms while being faster and using less memory.
The paper introduces curvature-based clustering algorithms for graph analysis.
problem Identifying densely connected substructures in graphs for community detection.
method Discrete Ricci curvatures and geometric flows to reveal community structure.
result The curvature-based approach can identify overlapping communities in graphs.
New algorithms for clustering and dimension reduction using relative von Neumann entropy.
problem Clustering and dimension reduction for complex data sets.
method Construct graphs from data points, select graph maximizing relative von Neumann entropy, use eigenvectors for dimension reduction.
result Outperforms existing methods on non-trivial data sets.
Generalizes k-means to graphs using PageRank.
problem Clustering nodes in directed and undirected graphs.
method Utilizes PageRank to compute node centrality in graphs.
result Robustly computes centrality in graphs and metric spaces.
New approach for fair graph clustering using semidefinite relaxation.
problem Ensuring equitable representation in network analysis.
method Semidefinite relaxation approach for NP-hard optimization problem.
result Optimal accuracy-fairness trade-off achieved.
This paper proposes a simple but effective graph-based agglomerative algorithm, for clustering high-dimensional data. We explore the different roles of two fundamental concepts in graph theory, indegree and outdegree, in the context of clustering. The average indegree reflects the density near a sample, and the average…
New methods cluster and test graphs without vertex correspondence.
problem Clustering and testing of networks without vertex correspondence.
method Inspired by graphon estimation, propose a novel graph distance and clustering algorithms.
result Prove statistical consistency of clustering algorithms under Lipschitz assumptions on graph degrees.
A new clustering algorithm GDT improves on HDBSCAN for uneven data.
problem Data clustering with uneven distribution and high noise.
method GDT combines local and global structures, forming local clusters and estimating a global topological graph based on connectivity between clusters.
result GDT achieves SOTA performance on various datasets with low time complexity.
A new algorithm PD improves stock-correlation network clustering and robustness.
problem Improving clustering and robustness of stock-correlation networks.
method Proposes a new proportional degree algorithm to filter information on a complete graph of normalised mutual information.
result The PD algorithm produces a network with better homogeneity and robustness compared to PMFG.
New algorithms ensure fair clustering in graph data.
problem Achieving fair clustering in graph data partitions.
method Developed variants of constrained spectral clustering.
result Proved algorithms can recover fair clusterings with high probability.
EAP clusters evolving data, promoting temporal smoothness and automatic cluster tracking.
problem Clustering time-evolving data with temporal smoothness and automatic cluster identification.
method Evolutionary Affinity Propagation (EAP) on a factor graph exchanging messages between adjacent data snapshots.
result EAP clusters data with temporal smoothness and automatically tracks clusters, outperforming existing methods.
Spectral clustering (SC) and graph-based semi-supervised learning (SSL) algorithms are sensitive to how graphs are constructed from data. In particular if the data has proximal and unbalanced clusters these algorithms can lead to poor performance on well-known graphs such as -NN, full-RBF, -graphs. This is becaus…
Graph clustering improved using Boltzmann machine heuristics.
problem Graph clustering to form densely connected clusters.
method Two mathematical programming formulations, two variations of Boltzmann machine heuristic.
result Boltzmann machine provides superior solutions and faster computation times.
In this work we develop a theory of hierarchical clustering for graphs. Our modeling assumption is that graphs are sampled from a graphon, which is a powerful and general model for generating graphs and analyzing large networks. Graphons are a far richer class of graph models than stochastic blockmodels, the primary se…
Polynomial-time algorithm for c-planarity and thickenability.
problem Testing clustered planarity and thickenability of graphs.
method Combines graph theory and topological graph theory.
result First polynomial-time algorithm for c-planarity.
New algorithm for multiway spectral clustering on Grassmann manifolds.
problem Efficiently computing multiple eigenvectors of a nonlinear graph Laplacian.
method Direct multiway spectral clustering in -norm, reformulated as minimization on Grassmann manifold.
result Monotonic decrease of balanced graph cuts leads to optimal solutions.
LMVSC clusters large datasets in linear time, overcoming scalability issues.
problem Efficiency in clustering large-scale multi-view data.
method Learn smaller graphs for each view, integrate them, and apply spectral clustering.
result LMVSC achieves linear complexity for clustering large datasets.