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
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.
TABLE I: Driver node selection for small-scale hypergraphs (mean ± 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 α . 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 studies how states evolve over time, including stability, feedback, chaos, and transitions in physical, biological, and engineered systems.
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.
Shibing Mo, Jiarui Zhang, Jiayu Xie +2
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.
We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.
A recurring data mining task in complex networks is to determine how individual nodes contribute to system behavior. Existing approaches rely on either static-graph centralities or control-theoretic quantities such as controllability Gramians, which assume linear, time-invariant dynamics. Estimated systems, however, are typically nonlinear and time-varying. We define "emergent contribution (EC)," a finite-horizon measure of a node's dynamical leverage: the metric-weighted energy of its impulse response accumulated along the system trajectory. Computed from the Jacobians of any differentiable model, EC is estimator-agnostic and reduces exactly to average controllability in the linear, time-invariant limit. Our contribution is a characterization of when the two measures agree and diverge. Using a controlled synthetic family with known ground-truth contribution, we construct a phase diagram spanning nonlinearity, regime structure, persistence, and perturbation amplitude. EC and average controllability agree under static or smoothly drifting dynamics and both track ground truth. Divergence emerges under persistent regime switching, is strongest under persistent sign reversal, and disappears when the sign reversal is removed. At extreme perturbation amplitudes, both measures degrade, identifying the limits of local linearization. We place five estimated real systems from several domains within this phase space. Their placement serves as a diagnostic of when EC provides information beyond static controllability and therefore justifies its additional computational cost. On one panel examined in depth, a twenty-seed retraining ensemble reveals a robust variance--leverage dissociation: nodes whose perturbations propagate widely despite low within-system variance, which is not recovered by static centralities nor variance-based summaries.
Valentina Kuskova, Dmitry Zaytsev, Michael Coppedge
Lucy Family Institute for Data & Society · University of Notre Dame · Notre Dame, IN, USA +1