Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

• URL: http://arxiv.org/abs/2603.28151v1
• Date: Mon, 30 Mar 2026 08:14:53 GMT
• Title: Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra
• Abstract summary: We present a novel evolutionary approach to evolve graphs based on the Laplacian graph spectra descriptor.<n>Our experimental results show that our approach is successful for different classes of graphs and a wide range of Laplacian graph spectra.
• Score: 6.164863213336097
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graphs with diverse structural characteristics play a central role in modelling and optimization tasks. The ability to generate different types of graphs that exhibit shared properties is likewise essential for algorithm selection and configuration. However, constructing graphs that preserve high-level properties across a broad range of graph classes remains a challenging problem. We present a novel evolutionary approach to evolve graphs based on the Laplacian graph spectra descriptor. This descriptor can be used as part of a fitness function to evaluate graphs according to their desired high-level properties. Our evolutionary algorithm evolves graphs towards this descriptor in order to obtain graphs having properties that are consistent with it but are different from each other in terms of non-spectral graph metrics, such as path length, clustering coefficient and betweenness centrality. Our experimental results show that our approach is successful for different classes of graphs and a wide range of Laplacian graph spectra.

Related papers

• Diversity Curves for Graph Representation Learning [21.35846278198515]
  We show how to track the structural diversity of a graph across coarsening levels.<n>The resulting graph embeddings are interpretable by construction, efficient, and directly comparable.<n>We demonstrate their utility over a range of baseline methods in practice.
  arXiv  Detail & Related papers  (2026-05-07T15:55:20Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Training A Foundation Model to Represent Graphs as Vectors [24.592499205332413]
  This paper aims to train a graph foundation model that is able to represent any graph as a vector preserving semantic information.<n>We provide a theoretical generalization bound to support the effectiveness of the proposed model.<n>The experimental results of few-shot graph classification and graph clustering show that our model outperforms strong baselines.
  arXiv  Detail & Related papers  (2026-02-04T06:06:28Z)
• Graph Classification Gaussian Processes via Spectral Features [7.474662887810221]
  Graph classification aims to categorise graphs based on their structure and node attributes. In this work, we propose to tackle this task using tools from graph signal processing by deriving spectral features. We show that even such a simple approach, having no learned parameters, can yield competitive performance compared to strong neural network and graph kernel baselines.
  arXiv  Detail & Related papers  (2023-06-06T15:31:05Z)
• Renormalized Graph Representations for Node Classification [21.589472270424405]
  We analyze the effect of using different coarse-grained graph resolutions on node classification tasks.<n>We specifically experiment using representations at the characteristic scale of the graph's mesoscopic structures.<n>Our results showed that models with access to both the original graph and the characteristic scale graph can achieve statistically significant improvements in test accuracy.
  arXiv  Detail & Related papers  (2023-06-01T14:16:43Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Demystifying Graph Convolution with a Simple Concatenation [6.542119695695405]
  We quantify the information overlap between graph topology, node features, and labels. We show that graph concatenation is a simple but more flexible alternative to graph convolution.
  arXiv  Detail & Related papers  (2022-07-18T16:39:33Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  We propose a multi-level graph matching network (MGMN) framework for computing the graph similarity between any pair of graph-structured objects. To compensate for the lack of standard benchmark datasets, we have created and collected a set of datasets for both the graph-graph classification and graph-graph regression tasks. Comprehensive experiments demonstrate that MGMN consistently outperforms state-of-the-art baseline models on both the graph-graph classification and graph-graph regression tasks.
  arXiv  Detail & Related papers  (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

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.