Learning Backbones: Sparsifying Graphs through Zero Forcing for Effective Graph-Based Learning
This paper introduces a novel framework for graph sparsification that preserves the essential learning attributes of original graphs, improving computational efficiency and reducing complexity in learning algorithms. We refer to these sparse graphs as "learning backbones". Our approach leverages the zero-forcing (ZF) phenomenon, a dynamic process on graphs with applications in network control. The key idea is to generate a tree from the original graph that retains critical dynamical properties. By correlating these properties with learning attributes, we construct effective learning backbones. We evaluate the performance of our ZF-based backbones in graph classification tasks across eight datasets and six baseline models. The results demonstrate that our method outperforms existing techniques. Additionally, we explore extensions using node distance metrics to further enhance the framework's utility.
Code (0)
등록된 구현이 없습니다.
Tasks
Computational EfficiencyGraph ClassificationSimilar Papers 제목 키워드 기반
Controllability Backbone in Networks
This paper studies the controllability backbone problem in dynamical networks defined over graphs. The main idea of the controllability backbone is to identify a small subset of edges in a given network such that any sub…
Deep Reinforcement Learning for Minimum Zero-Forcing Sets
This paper explores the problem of finding the minimum zero-forcing set on undirected graphs and proposes an adapted machine-learning framework to solve the problem. The minimum zero-forcing set problem is a graph colori…
Reinforcement LearningResilient Strong Structural Controllability in Networks using Leaky Forcing in Graphs
This paper studies the problem of selecting input nodes (leaders) to make networks strong structurally controllable despite misbehaving nodes and edges. We utilize a graph-based characterization of network strong structu…
Sparsifying Spiking Networks through Local Rhythms
It has been well-established that within conventional neural networks, many of the values produced at each layer are zero. In this work, I demonstrate that spiking neural networks can prevent the transmission of spikes r…
Distributed Design of Controllable and Robust Networks using Zero Forcing and Graph Grammars
This paper studies the problem of designing networks that are strong structurally controllable, and robust simultaneously. For given network specifications, including the number of nodes $N$, the number of leaders $N_L$,…