.png){kind=icon}
.png){kind=icon}
Return
Solving the non-submodular network collapse problems via Decision Transformer
.png){kind=icon}
PRE
AI
DOI：10.1016/j.neunet.2024.106328.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Given a graph G , the network collapse problem (NCP) selects a vertex subset S of minimum cardinality from G such that the difference in the values of a given measure function f ( G ) - f ( G \ S ) is greater than a predefined collapse threshold. Many graph analytic applications can be formulated as NCPs with different measure functions, which often pose a significant challenge due to their NP -hard nature. As a result, traditional greedy algorithms, which select the vertex with the highest reward at each step, may not effectively find the optimal solution. In addition, existing learning -based algorithms do not have the ability to model the sequence of actions taken during the decision -making process, making it difficult to capture the combinatorial effect of selected vertices on the final solution. This limits the performance of learning -based approaches in non-submodular NCPs. To address these limitations, we propose a unified framework called DT -NC, which adapts the D ecision T ransformer to the N etwork C ollapse problems. DT -NC takes into account the historical actions taken during the decision -making process and effectively captures the combinatorial effect of selected vertices. The ability of DT -NC to model the dependency among selected vertices allows it to address the difficulties caused by the non-submodular property of measure functions in some NCPs effectively. Through extensive experiments on various NCPs and graphs of different sizes, we demonstrate that DT -NC outperforms the state-of-the-art methods and exhibits excellent transferability and generalizability.
Keywords:
Graph neural network
Decision Transformer
Network collapse
Network dismantling
Collapsed k-core
Journal
IF:
6.3
Papers:
7.8K
Citations:
3.0W
Organization
View more organizations