Structural Controllability of Large-Scale Hypergraphs

Joshua Pickard; Xin Mao; Can Chen

math.OCMar 20, 2026

Structural Controllability of Large-Scale Hypergraphs

Authors: Joshua Pickard, Xin Mao, Can Chen

Organizations: Eric and Wendy Schmidt Center, Broad Institute of MIT and Harvard, Cambridge, MA 02142, USA · School of Data Science and Society, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, USA · Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, USA · Department of Biostatistics, University of North Carolina at Chapel Hill, Chapel Hill, NC 27599, USA

Abstract

Controlling real-world networked systems, including ecological, biomedical, and engineered networks that exhibit higher-order interactions, remains challenging due to inherent nonlinearities and large system scales. Despite extensive studies on graph controllability, the controllability properties of hypergraphs remain largely underdeveloped. Existing results focus primarily on exact controllability, which is often impractical for large-scale hypergraphs. In this article, we develop a structural controllability framework for hypergraphs by modeling hypergraph dynamics as polynomial dynamical systems. In particular, we extend classical notions of accessibility and dilation from linear graph-based systems to polynomial hypergraph dynamics and establish a hypergraph-based criterion under which the topology guarantees satisfaction of classical Lie-algebraic and Kalman-type rank conditions for almost all parameter choices. We further derive a topology-based lower bound on the minimum number of driver nodes required for structural controllability and leverage this bound to design a scalable driver node selection algorithm combining dilation-aware initialization via maximum matching with greedy accessibility expansion. We demonstrate the effectiveness and scalability of the proposed framework through numerical experiments on hypergraphs with tens to thousands of nodes and higher-order interactions.

Figures & tables

Fig. 1: Examples of hypergraph walk, accessibility, and dilation. This hypergraph is not structurally controllable. Hyperedges are uniquely colored, and nodes are shaded to match the color of their incident hyperedge head. Hyperedges are numbered according to the order they may appear in a walk originating at the control node. The black and dark purple nodes are inaccessible, and the light purple nodes form a dilation. The black node is inaccessible as it is not an input node and lacks an incident hyperedge head. Consequently, the dark purple node is also inaccessible; its incident hyperedge head cannot be traversed because the black node is inaccessible. The light purple nodes form a dilation since there is only a single hyperedge head for two nodes.

\mathcal{D}_{\mathrm{dil}}=\{v\in\mathcal{V}\mid v\text{ is uncovered by }\mathcal{M}\}

Algorithm 1 Matching-Augmented Greedy (MaG) Driver Node Selection

$k=6$
$\alpha$	$n$	Matching	MaG	Greedy	Optimal
0.5	10	5.200 $\pm$ 0.447	7.200 $\pm$ 0.837	9.667 $\pm$ 0.577	6.800 $\pm$ 0.837
	15	8.200 $\pm$ 0.447	10.200 $\pm$ 1.304	11.667 $\pm$ 0.577	9.200 $\pm$ 0.837
	20	10.800 $\pm$ 0.837	13.200 $\pm$ 1.304	16.333 $\pm$ 1.528	12.400 $\pm$ 0.548
1.0	10	1.400 $\pm$ 0.894	7.400 $\pm$ 0.894	7.500 $\pm$ 0.577	6.000 $\pm$ 0.000
	15	1.600 $\pm$ 0.548	10.000 $\pm$ 1.000	9.400 $\pm$ 0.548	7.000 $\pm$ 0.707

TABLE I: Driver node selection for small-scale hypergraphs (mean

\pm

std with 5 trials).

Fig. 2: Driver node selection on small-scale hypergraphs. Comparison of four methods for selecting driver nodes in 4-uniform hypergraphs of varying size

n

and density

\alpha

. Our proposed method (MaG), pure greedy selection, linear matching, and brute force search (optimal).

Fig. 3: Scaling of MaG, matching, and greedy based control node selection for large-scale hypergraphs. Runtime is averaged over three trials per hypergraph size.

Fig. 4: Structural properties of driver nodes in structured hypergraph topologies. Comparison of driver node characteristics across scale-free (red), clustered (green), and small-world (orange) hypergraph networks with

n=100

varying densities. Solid lines show means over 10 independent realizations; shaded regions indicate standard deviations. Points represent individual trials.

Dynamical Systems

Dynamical systems studies how states evolve over time, including stability, feedback, chaos, and transitions in physical, biological, and engineered systems.

See all 474 papers

High-order Knowledge Based Network Controllability Robustness Prediction: A Hypergraph Neural Network Approach
Feb 28, 2026Shibing Mo, Jiarui Zhang, Jiayu Xie +2Graph Robustness
School of Artifcial Intelligence, Xidian University, Xian 710126, China. · School of Computer Science and Technology, Xidian University, Xian 710126, China. · Guangzhou Institute of Technology, Xidian University, Guangzhou 510555, China.
Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment
Aug 30, 2026Lutz Oettershagen, Honglian Wang, Aristides GionisGraph Matching Hypergraph Learning
University of Liverpool · Liverpool, UK · KTH Royal Institute of Technology +2
Trajectory-Aware Node Contributions and the Limits of Static Controllability
Jun 2, 2026Valentina Kuskova, Dmitry Zaytsev, Michael Coppedge
Lucy Family Institute for Data & Society · University of Notre Dame · Notre Dame, IN, USA +1

Feb 28, 2026J/K move · Enter open · S save

High-order Knowledge Based Network Controllability Robustness Prediction: A Hypergraph Neural Network Approach

Shibing Mo, Jiarui Zhang, Jiayu Xie, Xiangyi Teng+1

School of Artifcial Intelligence, Xidian University, Xian 710126, China. · School of Computer Science and Technology, Xidian University, Xian 710126, China. · Guangzhou Institute of Technology, Xidian University, Guangzhou 510555, China.

Graph Robustness

Open paper AskPDF arXiv

In order to evaluate the invulnerability of networks against various types of attacks and provide guidance for potential performance enhancement as well as controllability maintenance, network controllability robustness (NCR) has attracted increasing attention in recent years. Traditionally, controllability robustness is determined by attack simulations, which are computationally time-consuming and only applicable to small-scale networks. Although some machine learning-based methods for predicting network controllability robustness have been proposed, they mainly focus on pairwise interactions in complex networks, and the underlying relationships between high-order structural information and controllability robustness have not been explored. In this paper, a dual hypergraph attention neural network model based on high-order knowledge (NCR-HoK) is proposed to accomplish robustness learning and controllability robustness curve prediction. Through a node feature encoder, hypergraph construction with high-order relations, and a dedicated dual hypergraph attention module, the proposed method can effectively learn three types of network information simultaneously: explicit structural information in the original graph, high-order connection information in local neighborhoods, and hidden features in the embedding space. Notably, we explore for the first time the impact of high-order knowledge on network controllability robustness. Compared with state-of-the-art methods for network robustness learning, the proposed method achieves superior performance on both synthetic and real-world networks with low computational overhead.

Abstract

Dynamical Systems

Explore similar work

High-order Knowledge Based Network Controllability Robustness Prediction: A Hypergraph Neural Network Approach

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

Trajectory-Aware Node Contributions and the Limits of Static Controllability