Dissecting graph measure performance for node clustering in LFR parameter space

• URL: http://arxiv.org/abs/2202.09827v1
• Date: Sun, 20 Feb 2022 14:52:52 GMT
• Title: Dissecting graph measure performance for node clustering in LFR parameter space
• Authors: Vladimir Ivashkin, Pavel Chebotarev
• Abstract summary: We study the performance of 25 graph measures on generated graphs with different parameters. We create a dataset of 11780 graphs covering the whole LFR parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best.
• Score: 2.445911003610726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph measures that express closeness or distance between nodes can be employed for graph nodes clustering using metric clustering algorithms. There are numerous measures applicable to this task, and which one performs better is an open question. We study the performance of 25 graph measures on generated graphs with different parameters. While usually measure comparisons are limited to general measure ranking on a particular dataset, we aim to explore the performance of various measures depending on graph features. Using an LFR graph generator, we create a dataset of 11780 graphs covering the whole LFR parameter space. For each graph, we assess the quality of clustering with k-means algorithm for each considered measure. Based on this, we determine the best measure for each area of the parameter space. We find that the parameter space consists of distinct zones where one particular measure is the best. We analyze the geometry of the resulting zones and describe it with simple criteria. Given particular graph parameters, this allows us to recommend a particular measure to use for clustering.

Related papers

• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node. MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
  arXiv  Detail & Related papers  (2024-05-23T07:40:21Z)
• Cluster-based Graph Collaborative Filtering [55.929052969825825]
  Graph Convolution Networks (GCNs) have succeeded in learning user and item representations for recommendation systems. Most existing GCN-based methods overlook the multiple interests of users while performing high-order graph convolution. We propose a novel GCN-based recommendation model, termed Cluster-based Graph Collaborative Filtering (ClusterGCF)
  arXiv  Detail & Related papers  (2024-04-16T07:05:16Z)
• Graph Parsing Networks [64.5041886737007]
  We propose an efficient graph parsing algorithm to infer the pooling structure, which then drives graph pooling. The resulting Graph Parsing Network (GPN) adaptively learns personalized pooling structure for each individual graph.
  arXiv  Detail & Related papers  (2024-02-22T09:08:36Z)
• DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization [5.329981192545312]
  We propose a novel method, DGCluster, which primarily optimize the modularity objective using graph neural networks and scales linearly with the graph size. We extensively test DGCluster on several real-world datasets of varying sizes, across multiple popular cluster quality metrics. Our approach consistently outperforms the state-of-the-art methods, demonstrating significant performance gains in almost all settings.
  arXiv  Detail & Related papers  (2023-12-20T01:43: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)
• Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes [3.8823562292981393]
  This paper proposes a metric to measure the dissimilarity between graphs that may have a different number of nodes. The proposed graph GOSPA metric includes costs associated with node attribute errors for properly assigned nodes, missed and false nodes and edge mismatches between graphs.
  arXiv  Detail & Related papers  (2023-11-10T11:40:24Z)
• G-Mapper: Learning a Cover in the Mapper Construction [0.7528462379265576]
  The Mapper algorithm is a visualization technique in topological data analysis (TDA) that outputs a graph reflecting the structure of a given dataset. We present an algorithm that optimize the cover of a Mapper graph by splitting a cover repeatedly according to a statistical test for normality. Our algorithm is based on G-means clustering which searches for the optimal number of clusters in $k$-means by iteratively applying the Anderson-Darling test.
  arXiv  Detail & Related papers  (2023-09-12T22:51:16Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• A parameter-free graph reduction for spectral clustering and SpectralNet [1.5469452301122175]
  We introduce a graph reduction method that does not require any parameters. First, distances from every point $p$ to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. The edges that survive two steps form the constructed graph that was passed to spectral clustering SpectralNet.
  arXiv  Detail & Related papers  (2023-02-25T21:19:30Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Measuring inter-cluster similarities with Alpha Shape TRIangulation in loCal Subspaces (ASTRICS) facilitates visualization and clustering of high-dimensional data [0.0]
  Clustering and visualizing high-dimensional (HD) data are important tasks in a variety of fields. Some of the most effective algorithms for clustering HD data are based on representing the data by nodes in a graph. I propose a new method called ASTRICS to measure similarity between clusters of HD data points.
  arXiv  Detail & Related papers  (2021-07-15T20:51:06Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)

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.