CS Paper Radar

Theory-Driven Network Backbones for Bipartite Projections

Nikos Salamanos, Paula Gheorghiade, Tom Brughmans, Michele Coscia

cs.SI cs.DB ·submitted 2026-11-12 12:08 UTC · v1

Abstract

Collecting data, including network data, is subject to measurement error. Network backboning is the process of statistically validating each edge in a network to estimate the probability that the edge is born of noisy measurements. The current backboning literature provides approaches in two classes: structural and statistical. The classes differ in many respects, but they share one commonality: the test used to determine whether to filter out noisy edges is data-agnostic; it does not take into account what the network is representing. However, the nodes and edges of all non-synthetic networks correspond to specific real-world entities, whose dynamics determine how the edge-generating process operates. In this paper, we propose the first in a new class of network backboning algorithms: a theory-driven backboning approach that allows us to encode known dynamics into the backboning process. The resulting backbone embeds the encoded theory and produces a network compatible with it, rather than one that obeys a data-agnostic network process, as in the structural and statistical backboning classes. We specifically focus on the case of projecting and backboning a bipartite structure. We do so by allowing users to specify an Agent-Based Model for the two types of agents (nodes) in the network and by performing Simulation-Based Inference to fit the observed bipartite structure and, as a result, reconstruct the true relationships between the two classes of agents. We test our framework both on synthetic data -- where we have perfect information about the edge-generating process -- and in a case study using archaeological data on amphorae retrieved from different archaeological sites. Our approach improves latent-edge recovery over conventional backboning methods in synthetic experiments and reveals interpretable archaeological patterns despite imperfect model fit.

Comment
13 pages, 10 figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

A graph decomposition approach for the synthesis of EMPs in directed acyclic networks

eess.SY ·2026-10-22 ·Eduardo Mapurunga, Michel Gevers, Alexandre Bazanella
unusual similarity 0.58
Abstract · Paper submitted to Automatica

This paper considers the identifiability of dynamical networks whose topology is a Directed Acyclic Graph (DAG), in the context where not all nodes are excited and not all nodes are measured. The objective is to construct a valid and parsimonious Excitation and Measurement Pattern (EMP), i.e. a selection of excited and measured nodes, that allows to identify the whole network with a small number of excitations and measurements. We show first that a DAG can be decomposed into a set of trees and parallel paths networks. We propose an algorithm that achieves this decomposition and computes an EMP that combines EMPs for the individual trees and parallel paths networks. We formally show that this algorithm yields an EMP capable of identifying the whole network.

0.34

Scalable detection of higher-order interactions in network data

cs.SI ·2026-09-27 ·Yingbang Zang, Yanting Zhang, Alec Kirkley
similarity 0.57
Abstract · 27 pages, 5 figures, 6 tables

Complex systems are routinely measured and represented through pairwise networks, even when the underlying interactions involve more than two units at once. Recovering this latent hypergraph structure from pairwise measurements is a fundamental inverse problem, but as the space of candidate hyperedges grows exponentially with system size, scalable hypergraph reconstruction at arbitrary interaction orders is out of reach for existing methods. Here we cast hypergraph reconstruction as a local signal-to-noise discrimination problem and use this locality to build a fast algorithm that reconstructs hypergraphs up to any interaction order. Across diverse synthetic and real-world systems our method achieves a high recovery accuracy of latent hypergraph structure while reconstructing hypergraphs up to orders of magnitude more quickly than current approaches. Our approach also yields an information-theoretic detectability boundary that sharply predicts which latent hyperedges are recoverable from pairwise measurements.

0.31

Efficiently Estimating Cycle Statistics on Graphs via Spanning Trees

cs.SI stat.CO ·2026-11-05 ·Josef Hoppe, Michael T. Schaub
code/data similarity 0.56
Abstract · 15 pages, 8 figures, plus appendix

Simple cycles encode feedback and alternative routes in networks and are important for routing problems, the convergence of dynamical processes on networks, message passing and belief propagation, or even static network characterizations such as structural balance in signed networks. Being able to assess and sample from the cycle structure of a graph is thus of interest in many analysis contexts. However, due to the combinatorial growth of the cycle space with graph size, the computational cost for such sampling is high. Therefore, we here introduce a sampling framework that enables us to sample from the cycle structure without enumerating all cycles. Specifically, the method draws uniform spanning trees and collects the fundamental cycles created by their non-tree edges, such that each tree provides an informative subset of simple cycles. Because cycles are included with unequal probabilities and are dependent within each subset, we formulate an inclusion-probability-based Horvitz-Thompson estimator, which we average over random subsets, a procedure we call Monte Carlo Horvitz-Thompson. For this, we sample multiple Horvitz-Thompson estimators and introduce a method to further subsample the individual estimators for increased computational performance. For sampling cycles, the estimator is unbiased if exact cycle inclusion probabilities are known. To extend the method to larger networks, we derive an efficient mean-field approximation for the inclusion probabilities and characterize the graph regimes in which it remains accurate. Experiments on synthetic and real-world networks demonstrate the computational scaling and statistical performance of the framework. We then illustrate the utility of Monte Carlo Horvitz-Thompson estimation by estimating cycle counts and cycle-level frustration statistics in signed spin systems. An implementation is available in the py-raccoon package.

0.68

From topology learning to graph generation: A unifying perspective

cs.LG stat.MLeess.SP ·2026-09-02 ·Xiaowen Dong, Hoi-To Wai, Siheng Chen, Laura Toni, Dorina Thanou
similarity 0.56
Abstract

Learning graph structures from data is a fundamental problem that spans a wide range of signal processing and machine learning tasks. While significant effort has been made to tackle the problem, existing research has largely evolved along two parallel directions. The first seeks to infer the topology of an individual graph from observations supported on it, whereas the second seeks to learn a generative distribution from observed graph instances, enabling the sampling of new graphs. This review presents a unified framework that connects these formulations by viewing them as inverse problems of a common generation process for graph data. We review the major methodologies within this framework, highlight their relationships, strengths, and limitations, and identify opportunities for integrating ideas across paradigms. By bridging graph topology learning and graph generation, this review provides a broader cross-disciplinary perspective on the field and outlines promising directions for future research.

0.27

Pipelining vs. Combining in Aggregation Tasks

cs.DC cs.DS ·2026-10-22 ·Gabriel Marques Domingues, Claire Mathieu, Boaz Patt-Shamir
similarity 0.55
Abstract · 22 pages; 7 figures

We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two values has the same length as each of the input values. Since values do not fit in a message, they are transferred in a ``train'' of pipelined messages, which must be terminated whenever we want to aggregate values. The goal is to minimize the makespan time of aggregating all values. We present general lower bounds on the problem and optimal algorithms for several prevalent parallel computing architectures, including the hypercube and complete bipartite graphs, under both the splittable and unsplittable flows models. We also present an $O(\log n)$ approximation for general graphs in the unsplittable flows model.

0.40

Exact Bayesian Tracking of Dynamic Network Topologies

eess.SP ·2026-09-10 ·Victor M. Tenorio, Elvin Isufi, Geert Leus, Antonio G. Marques
similarity 0.55
Abstract · Under review

Tracking the temporal evolution of network topologies is a fundamental challenge in social networks, epidemiology, and sensor systems, among others. This paper develops an exact Bayesian tracker for unweighted, directed graphs using nodal signal observations. This framework yields the full posterior probability distribution over network states at each time step, naturally enabling uncertainty quantification, prediction, and principled decision-making. We model the network dynamics as a Markov process on the Boolean hypercube, where edges transition independently according to a flip probability. For efficient computation, we cast the prediction step as a dyadic convolution, and leverage the Fast Walsh-Hadamard Transform to reduce the computational cost from $\mathcal{O} (4^k)$ to $\mathcal{O} (k 2^k)$, where $k$ is the maximum node degree. When the network transition probabilities are unknown, we develop an Expectation-Maximization framework to learn them from the observed signals. Comprehensive experiments on synthetic and six real-world datasets validate the proposed method and demonstrate its superior tracking accuracy, faster recovery from topological changes, and meaningful uncertainty estimates compared to state-of-the-art and classical baselines.

0.29

Similarity-Guided Optimization Strategies for Approximate Network Symmetry Detection

cs.NE cs.LGq-bio.NC ·2026-11-12 ·David Hartman, Jaroslav Hlinka, Dominik Klepl, Anna Pidnebesna, Petra Vidnerová
similarity 0.55
Abstract · 90 pages, 15 figures and 2 tables in the main text; supplementary material with 64 figures and 7 tables included

Symmetry in complex networks is a structural property with broad implications for network function, dynamics, and robustness. While classical approaches rely on exact automorphisms and thus remain highly sensitive to small perturbations, recent work of Liu has introduced approximate formulations that relax the strict invariance condition and recast symmetry detection as an optimization problem over permutations. We investigate how node-level similarity information can be used to bias the search toward structurally plausible vertex correspondences, with network centralities serving as one interpretable instance. Building on this perspective, we adapt simulated annealing, genetic algorithms, tabu search, particle swarm optimization, differential evolution and the quadratic symmetry approximator to this problem, add similarity guidance to each, and introduce Bilinear Approximate Symmetry Inference (BASIN), which learns a soft assignment matrix via bilinear embeddings. Using a unified evaluation pipeline, we compare their guided and unguided variants, BASIN and a random baseline on four synthetic graph families, structural brain connectomes, and three empirical networks with known automorphism groups. Node-similarity guidance is decisive where a planted orbit exists that the unguided search misses, and algorithm-dependent elsewhere, on synthetic and empirical networks alike. Overall, tabu search achieves the strongest performance; its guided variant (SGTS) has the lowest median score among the guided variants in all 44 synthetic conditions, while BASIN is the better of the continuous relaxations on rewired lateral graphs. The effect of node-similarity guidance is therefore regime-dependent rather than uniformly positive.

0.30

An Incremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets

cs.GT cs.DS ·2026-09-21 ·Dario Fiorenza, Daniele Gorla, Ivano Salvo
published similarity 0.55
Abstract

Braess paradox is a well-known phenomenon that originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The possibility of having the paradox was called vulnerability by Roughgarden in 2006 and was characterized later on by graph-theoretical notions, both for undirected and for directed graphs. In this paper we provide an algorithm for the incremental case of checking vulnerability for dynamically evolving graphs. The crucial idea to keep the amortized cost linear for every edge addition is that we do not need to run the vulnerability algorithm on the whole graph, but only on a well-identified subgraph, determined by the edge that we are adding. Overall, to add m edges, we pay a cost of O(m2); this aligns with the O(m2) cost of the state-of-the-art static algorithm for vulnerability.

0.64