CS Paper Radar

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

Eduardo Mapurunga, Michel Gevers, Alexandre Bazanella

eess.SY ·submitted 2026-10-22 18:52 UTC · v1
unusual

Abstract

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.

Comment
Paper submitted to Automatica

Closest papers

Nearest neighbours by meaning across the whole index.

Stable Set Reconfiguration in Dense Digraphs

cs.DM cs.CCmath.CO ·2026-10-23 ·Sarah Houdaigoui, Nacim Oijid, Matthieu Petiteau, Alexandre Vigny
similarity 0.58
Abstract

In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.

0.28

Theory-Driven Network Backbones for Bipartite Projections

cs.SI cs.DB ·2026-11-12 ·Nikos Salamanos, Paula Gheorghiade, Tom Brughmans, Michele Coscia
similarity 0.58
Abstract · 13 pages, 10 figures, 3 tables

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.

0.44

Revealing Pathway Interactions in Network Computations with Complete Path Contribution

cs.LG q-bio.NC ·2026-11-19 ·Shenghua Liu, Youssef Faragalla, Surya Ganguli, Stephen A. Baccus
benchmark similarity 0.56
Abstract · 40 pages, 24 figures

Networks pass signals through many layers of interconnected units, so explaining what they compute means tracing how information travels from input to output and how pathways interact. Most existing approaches analyze only pairwise interactions between components such as units, layers or attention heads. Even when these measurements are combined post hoc into a circuit, they do not capture higher-order interactions along full causal chains (paths) from input to output, and so cannot address how exponentially many paths interact to construct network computation. This leaves a large set of mechanistic questions unanswerable, for example whether inhibitory pathways veto excitatory ones, and how the two combine to yield network decisions. To address this gap, we introduce Complete Path Contribution, a method to decompose the network output into mathematically complete contributions of individual paths to study path-level interactions directly and at scale. Partial summation then induces definitions of contributions for any circuit at any granularity level, with completeness guaranteed at every level. We further present an efficient algorithm that identifies the $k$ strongest paths without examining all of them, with runtime empirically linear in $k$ rather than exponential in depth. By applying Path Contribution to benchmark image classification networks, we quantify excitatory-inhibitory interactions and show how they collectively construct network decisions at a level of detail previously unmeasurable. Furthermore, in an interpretable model of the mouse retina, it reveals how dynamic receptive fields emerge from excitatory-inhibitory interaction motifs among pathways between different cell types in response to time-varying natural stimuli. Overall, Path Contribution reveals how a network's causal pathways interact at scale to transform input to output.

0.22

Estimating the number of nodes and paths in a DAG by following a random path

cs.DS math.CO ·2026-10-28 ·Günter Rote
similarity 0.55
Abstract · 28 pages, 5 figures, 10 tables, 4 appendices

We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.

0.52

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.52
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

A Decremental Algorithm for Checking the Possibility of Braess Paradox in Dynamic Nets

cs.GT cs.DS ·2026-10-05 ·Dario Fiorenza, Daniele Gorla, Ivano Salvo
similarity 0.52
Abstract

Braess paradox originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The graph-theoretic property of networks suffering from the Braess paradox was called vulnerability by Roughgarden in 2006; it was then characterized and algorithmically checked both for undirected and for directed nets. In this paper, we provide a decremental algorithm of linear amortized complexity to check vulnerability for dynamically evolving networks. The basic idea of our dynamic algorithm is to use a static algorithm that marks some edges as irrelevant for the vulnerability of the graph and ignore those edges for all subsequent runs of the decremental procedure. To get a linear amortized cost for every edge remotion, we also provide a new version of such a static algorithm that improves its complexity from O(n m^2) to O(m^2), that is in turn aligned with the cost of the best state-of-the-art static algorithm for vulnerability.

0.29

Faster Algorithms for Finding Small Induced Patterns in Sparse Host Graphs

cs.DS ·2026-09-30 ·Priyanshi Agrawal, Balagopal Komarath
similarity 0.51
Abstract · 38 pages, 70 figures

We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs. We show that at least five of the 21 connected graphs on five vertices can be detected in time roughly the product of the number of vertices and the number of edges, and that at least 65 of the 112 connected graphs on six vertices can be detected in time nearly quadratic in the number of edges. We also give algorithms for detecting induced paths and cycles on seven vertices, running in time roughly the number of vertices times the square of the number of edges. Our main technical tool is a generalized notion of tree decomposition width, called (p, q)-width. It yields algorithms whose running times depend on both the number of vertices and the number of edges, and are never worse than existing bounds. Whenever the host graph has fewer than roughly quadratically many edges in its number of vertices, our bounds are strictly faster. For some patterns, including the seven-vertex cycle, our algorithms are optimal under standard complexity-theoretic assumptions. We further develop this approach using pattern-based polynomials that exploit the structure of tree decompositions, not just their width. This gives algorithms for detecting induced paths and cycles on an even number of vertices in bipartite graphs, running in time roughly the (k-1)-th power of the number of edges for paths on 2k vertices, and that same bound times the number of vertices for cycles on 2k vertices. These are faster than the best known algorithms for general graphs.

0.16

Ollivier's Ricci Curvature on Complex-weighted Graphs

cs.SI math.MGphysics.soc-ph ·2026-08-10 ·Yu Tian, Eleanor Wiesler, Melanie Weber
similarity 0.51
Abstract · 32 pages, 11 figures

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

0.10