Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition

• URL: http://arxiv.org/abs/2108.06094v1
• Date: Fri, 13 Aug 2021 07:06:32 GMT
• Title: Multi-Stage Graph Peeling Algorithm for Probabilistic Core Decomposition
• Authors: Yang Guo, Xuekui Zhang, Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, Li Xing
• Abstract summary: Recently, Esfahani et al. presented a probabilistic core decomposition algorithm based on graph peeling and Central Limit Theorem (CLT) We propose a multi-stage graph peeling algorithm (M-PA) that has a two-stage data screening procedure added before the previous PA. We show that M-PA is more efficient than the previous PA and with the properly set filtering threshold, can produce very similar dense subgraphs to the previous PA.
• Score: 3.004067332389205
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mining dense subgraphs where vertices connect closely with each other is a common task when analyzing graphs. A very popular notion in subgraph analysis is core decomposition. Recently, Esfahani et al. presented a probabilistic core decomposition algorithm based on graph peeling and Central Limit Theorem (CLT) that is capable of handling very large graphs. Their proposed peeling algorithm (PA) starts from the lowest degree vertices and recursively deletes these vertices, assigning core numbers, and updating the degree of neighbour vertices until it reached the maximum core. However, in many applications, particularly in biology, more valuable information can be obtained from dense sub-communities and we are not interested in small cores where vertices do not interact much with others. To make the previous PA focus more on dense subgraphs, we propose a multi-stage graph peeling algorithm (M-PA) that has a two-stage data screening procedure added before the previous PA. After removing vertices from the graph based on the user-defined thresholds, we can reduce the graph complexity largely and without affecting the vertices in subgraphs that we are interested in. We show that M-PA is more efficient than the previous PA and with the properly set filtering threshold, can produce very similar if not identical dense subgraphs to the previous PA (in terms of graph density and clustering coefficient).

Related papers

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  We introduce an algorithm for graph matching based on the proximal operator, referred to as differentiable proximal graph matching (DPGM) The whole algorithm can be considered as a differentiable map from the graph affinity matrix to the prediction of node correspondence. Numerical experiments show that PGM outperforms existing graph matching algorithms on diverse datasets.
  arXiv  Detail & Related papers  (2024-05-26T08:17:13Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  Cluster deletion is an NP-hard graph clustering objective with applications in computational and social network analysis. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. We show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a maximum degree in an auxiliary graph and forming a cluster around it.
  arXiv  Detail & Related papers  (2024-04-24T18:39:18Z)
• An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem [9.400610985728441]
  The Maximum s-Bundle Problem (MBP) addresses the task of identifying a maximum s-bundle in a given graph. We introduce a novel Partition-based Upper Bound (PUB) that leverages the graph partitioning technique to achieve a tighter upper bound. We also propose a new BnB algorithm that uses the initial lower bound and PUB in preprocessing for graph reduction.
  arXiv  Detail & Related papers  (2024-02-06T06:05:11Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
  We consider the problem of correlation clustering for dynamic complete signed graphs. Online approximation algorithm in [CALM+21] for correlation clustering is used. This is the first online algorithm for dynamic graphs which allows a full set of graph editing operations.
  arXiv  Detail & Related papers  (2022-11-13T19:36:38Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  We introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$. Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases. A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice.
  arXiv  Detail & Related papers  (2021-06-02T02:58:35Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.