Properties and Performance of the ABCDe Random Graph Model with Community Structure

• URL: http://arxiv.org/abs/2203.14899v1
• Date: Mon, 28 Mar 2022 17:03:24 GMT
• Title: Properties and Performance of the ABCDe Random Graph Model with Community Structure
• Authors: Bogumi{\l} Kami\'nski, Tomasz Olczak, Bartosz Pankratz, Pawe{\l} Pra{\l}at, Fran\c{c}ois Th\'eberge
• Abstract summary: We propose a new implementation of the ABCD graph generator, ABCDe, that uses multiple-threading. We show that ABCDe is more than ten times faster and scales better than the parallel implementation of LFR provided in NetworKit.
• Score: 4.724825031148412
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we investigate properties and performance of synthetic random graph models with a built-in community structure. Such models are important for evaluating and tuning community detection algorithms that are unsupervised by nature. We propose a new implementation of the ABCD graph generator, ABCDe, that uses multiple-threading. We discuss the implementation details of the algorithm as well as compare it with both the previously available sequential version of the ABCD model and with the parallel implementation of the standard and extensively used LFR generator. We show that ABCDe is more than ten times faster and scales better than the parallel implementation of LFR provided in NetworKit. Moreover, the algorithm is not only faster but random graphs generated by ABCD have similar properties to the ones generated by the original LFR algorithm, while the parallelized NetworKit implementation of LFR produces graphs that have noticeably different characteristics.

Related papers

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP) We propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursion call. Annotating comparisons of different graphs concerning their MIS size leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa.
  arXiv  Detail & Related papers  (2023-10-28T10:58:25Z)
• Challenging the Myth of Graph Collaborative Filtering: a Reasoned and Reproducibility-driven Analysis [50.972595036856035]
  We present a code that successfully replicates results from six popular and recent graph recommendation models. We compare these graph models with traditional collaborative filtering models that historically performed well in offline evaluations. By investigating the information flow from users' neighborhoods, we aim to identify which models are influenced by intrinsic features in the dataset structure.
  arXiv  Detail & Related papers  (2023-08-01T09:31:44Z)
• Artificial Benchmark for Community Detection with Outliers (ABCD+o) [5.8010446129208155]
  We extend the ABCD model to include potential outliers. We perform some exploratory experiments on both the new ABCD+o model as well as a real-world network to show that outliers possess some desired, distinguishable properties.
  arXiv  Detail & Related papers  (2023-01-13T20:14:44Z)
• NVDiff: Graph Generation through the Diffusion of Node Vectors [20.424372965054832]
  We propose NVDiff, which takes the VGAE structure and uses a score-based generative model (SGM) as a flexible prior to sample node vectors. Built on the NVDiff framework, we introduce an attention-based score network capable of capturing both local and global contexts of graphs.
  arXiv  Detail & Related papers  (2022-11-19T20:43:39Z)
• Modularity of the ABCD Random Graph Model with Community Structure [2.580765958706854]
  The ABCD graph is a random graph model with community structure and power-law distribution for both degrees and community sizes. We analyze the modularity function, arguably the most important graph property of networks in the context of community detection. It is also used as a quality function in many community detection algorithms, including the widely used Louvain algorithm.
  arXiv  Detail & Related papers  (2022-03-03T01:49:46Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Ramanujan Bipartite Graph Products for Efficient Block Sparse Neural Networks [2.4235475271758076]
  We propose framework for generating structured multi level block sparse neural networks by using the theory of Graph products. We also propose to use products of Ramanujan graphs which gives the best connectivity for a given level of sparsity. We benchmark our approach by experimenting on image classification task over CIFAR dataset using VGG19 and WideResnet-40-4 networks.
  arXiv  Detail & Related papers  (2020-06-24T05:08:17Z)
• Revisiting Graph based Collaborative Filtering: A Linear Residual Graph Convolutional Network Approach [55.44107800525776]
  Graph Convolutional Networks (GCNs) are state-of-the-art graph based representation learning models. In this paper, we revisit GCN based Collaborative Filtering (CF) based Recommender Systems (RS) We show that removing non-linearities would enhance recommendation performance, consistent with the theories in simple graph convolutional networks. We propose a residual network structure that is specifically designed for CF with user-item interaction modeling.
  arXiv  Detail & Related papers  (2020-01-28T04:41:25Z)
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure [5.8010446129208155]
  We provide an alternative random graph model with community structure and power-law distribution for both degrees and community sizes, the Artificial Benchmark for Community Detection (ABCD) ABCD is fast, simple, and can be easily tuned to allow the user to make a smooth transition between the two extremes: pure (independent) communities and random graph with no community structure.
  arXiv  Detail & Related papers  (2020-01-14T17:20:27Z)

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.