More Like this

1. The orbit-polynomial: a novel measure of symmetry in networks

   https://doi.org/10.1109/ACCESS.2020.2970059  

   Dehmer, M.; Chen, Z.; Emmert-Streib, F.; Mowshowitz, A.; Varmuza, K.; Feng, L.; Jodlbauer, H.; Shi, Y.; and Tao, J. (January 2020, IEEE access)

   Research on the structural complexity of networks has produced many useful results in graph theory and applied disciplines such as engineering and data analysis. This paper is intended as a further contribution to this area of research. Here we focus on measures designed to compare graphs with respect to symmetry. We do this by means of a novel characteristic of a graph G, namely an ``orbit polynomial.'' A typical term of this univariate polynomial is of the form czn, where c is the number of orbits of size n of the automorphism group of G. Subtracting the orbit polynomial from 1 results in another polynomial that has a unique positive root, which can serve as a relative measure of the symmetry of a graph. The magnitude of this root is indicative of symmetry and can thus be used to compare graphs with respect to that property. In what follows, we will prove several inequalities on the unique positive roots of orbit polynomials corresponding to different graphs, thus showing differences in symmetry. In addition, we present numerical results relating to several classes of graphs for the purpose of comparing the new symmetry measure with existing ones. Finally, it is applied to a set of isomers of the chemical compound adamantane C10H16. We believe that the measure can be quite useful for tackling applications in chemistry, bioinformatics, and structure-oriented drug design. 

   more » « less
2. Optimization complexity and resource minimization of emitter-based photonic graph state generation protocols

   https://doi.org/10.1038/s41534-025-01056-3  

   Takou, Evangelia; Barnes, Edwin; Economou, Sophia E (July 2025, npj Quantum Information)

   Abstract Photonic graph states are important for measurement- and fusion-based quantum computing, quantum networks, and sensing. They can in principle be generated deterministically by using emitters to create the requisite entanglement. Finding ways to minimize the number of entangling gates between emitters and understanding the overall optimization complexity of such protocols is crucial for practical implementations. Here, we address these issues using graph theory concepts. We develop optimizers that minimize the number of entangling gates, reducing them by up to 75% compared to naive schemes for moderately sized random graphs. While the complexity of optimizing emitter-emitter CNOT counts is likely NP-hard, we are able to develop heuristics based on strong connections between graph transformations and the optimization of stabilizer circuits. These patterns allow us to process large graphs and still achieve a reduction of up to 66% in emitter CNOTs, without relying on subtle metrics such as edge density. We find the optimal emission orderings and circuits to prepare unencoded and encoded repeater graph states of any size, achieving global minimization of emitter and CNOT resources despite the average NP-hardness of both optimization problems. We further study the locally equivalent orbit of graphs. Although enumerating orbits is#P complete for arbitrary graphs, we analytically calculate the size of the orbit of repeater graphs and find a procedure to generate the orbit for any repeater size. Finally, we inspect the entangling gate cost of preparing any graph from a given orbit and show that we can achieve the same optimal CNOT count across the orbit. 

   more » « less
3. A parallel algorithm for generating a random graph with a prescribed degree sequence

   https://doi.org/10.1109/BigData.2017.8258316  

   Bhuiyan, Hasanuzzaman; Khan, Maleq; Marathe, Madhav (December 2017, 2017 IEEE International Conference on Big Data (Big Data))

   Random graphs (or networks) have gained a significant increase of interest due to its popularity in modeling and simulating many complex real-world systems. Degree sequence is one of the most important aspects of these systems. Random graphs with a given degree sequence can capture many characteristics like dependent edges and non-binomial degree distribution that are absent in many classical random graph models such as the Erdöos-Rényi graph model. In addition, they have important applications in uniform sampling of random graphs, counting the number of graphs having the same degree sequence, as well as in string theory, random matrix theory, and matching theory. In this paper, we present an OpenMP-based shared-memory parallel algorithm for generating a random graph with a prescribed degree sequence, which achieves a speedup of 20.4 with 32 cores. We also present a comparative study of several structural properties of the random graphs generated by our algorithm with that of the real-world graphs and random graphs generated by other popular methods. One of the steps in our parallel algorithm requires checking the Erdöos-Gallai characterization, i.e., whether there exists a graph obeying the given degree sequence, in parallel. This paper presents a non-trivial parallel algorithm for checking the Erdöos-Gallai characterization, which achieves a speedup of 23 with 32 cores. 

   more » « less
4. GraphS: A Graph Processing Accelerator Leveraging SOT-MRAM

   Angizi, Shaahin; Sun, Jiao; Zhang, Wei; Fan, Deliang (March 2019, 23rd Design Automation and Test in Europe)

   In this work, we present GraphS architecture, which transforms current Spin Orbit Torque Magnetic Random Access Memory (SOT-MRAM) to massively parallel computational units capable of accelerating graph processing applications. GraphS can be leveraged to greatly reduce energy consumption dealing with underlying adjacency matrix computations, eliminating unnecessary off-chip accesses and providing ultra-high internal bandwidth. The device-to-architecture co-simulation for three social network data-sets indicate roughly 3.6X higher energy efficiency and 5.3X speed-up over recent ReRAM crossbar. It achieves ~4X higher energy-efficiency and 5.1X speed-up over recent processing-in-DRAM acceleration methods. 

   more » « less
5. Learning Similarity-Preserving Representations of Brain Structure-Function Coupling

   https://doi.org/10.23919/EUSIPCO55093.2022.9909566  

   Li, Yang; Mateos, Gonzalo (August 2022, 2022 30th European Signal Processing Conference (EUSIPCO))

   Advances in graph signal processing for network neuroscience offer a unique pathway to integrate brain structure and function, with the goal of revealing some of the brain's organizing principles at the system level. In this direction, we develop a supervised graph representation learning framework to model the relationship between brain structural connectivity (SC) and functional connectivity (FC) via a graph encoder-decoder system. Specifically, we propose a Siamese network architecture equipped with graph convolutional encoders to learn graph (i.e., subject)-level embeddings that preserve application-dependent similarity measures between brain networks. This way, we effectively increase the number of training samples and bring in the flexibility to incorporate additional prior information via the prescribed target graph-level distance. While information on the brain structure-function coupling is implicitly distilled via reconstruction of brain FC from SC, our model also manages to learn representations that preserve the similarity between input graphs. The superior discriminative power of the learnt representations is demonstrated in downstream tasks including subject classification and visualization. All in all, this work advocates the prospect of leveraging learnt graph-level, similarity-preserving embeddings for brain network analysis, by bringing to bear standard tools of metric data analysis. 

   more » « less