Identifying critical nodes in complex networks by graph representation learning

• URL: http://arxiv.org/abs/2201.07988v1
• Date: Thu, 20 Jan 2022 03:41:22 GMT
• Title: Identifying critical nodes in complex networks by graph representation learning
• Authors: Enyu Yu, Duanbing Chen, Yan Fu, Yuanyuan Xu
• Abstract summary: Influence is one of the main problems in critical nodes mining. IMGNN is a graph learning framework that takes centralities of nodes in a network as input and the probability that nodes in the optimal initial spreaders as output. IMGNN is more efficient than human-based algorithms in minimizing the size of initial spreaders under the fixed infection scale.
• Score: 2.304938062591095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Because of its wide application, critical nodes identification has become an important research topic at the micro level of network science. Influence maximization is one of the main problems in critical nodes mining and is usually handled with heuristics. In this paper, a deep graph learning framework IMGNN is proposed and the corresponding training sample generation scheme is designed. The framework takes centralities of nodes in a network as input and the probability that nodes in the optimal initial spreaders as output. By training on a large number of small synthetic networks, IMGNN is more efficient than human-based heuristics in minimizing the size of initial spreaders under the fixed infection scale. The experimental results on one synthetic and five real networks show that, compared with traditional non-iterative node ranking algorithms, IMGNN has the smallest proportion of initial spreaders under different infection probabilities when the final infection scale is fixed. And the reordered version of IMGNN outperforms all the latest critical nodes mining algorithms.

Related papers

• Reducing Oversmoothing through Informed Weight Initialization in Graph Neural Networks [16.745718346575202]
  We propose a new scheme (G-Init) that reduces oversmoothing, leading to very good results in node and graph classification tasks. Our results indicate that the new method (G-Init) reduces oversmoothing in deep GNNs, facilitating their effective use.
  arXiv  Detail & Related papers  (2024-10-31T11:21:20Z)
• Improving Critical Node Detection Using Neural Network-based Initialization in a Genetic Algorithm [3.5877750256097465]
  The primary objective of CNP-1a is to minimize the pair-wise connectivity in the remaining network after deleting a limited number of nodes from a network. To improve the efficiency of solving CNP-1a, a knowledge-guided genetic algorithm named K2GA has been proposed. The effectiveness of the proposed knowledgeguided genetic algorithm is verified by experiments on 26 realworld instances of complex networks.
  arXiv  Detail & Related papers  (2024-02-01T07:53:25Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  This paper focuses on improving the performance of GNNs via normalization. By studying the long-tailed distribution of node degrees in the graph, we propose a novel normalization method for GNNs. The $scale$ operation of ResNorm reshapes the node-wise standard deviation (NStd) distribution so as to improve the accuracy of tail nodes.
  arXiv  Detail & Related papers  (2022-06-16T13:49:09Z)
• Edge Graph Neural Networks for Massive MIMO Detection [15.970981766599035]
  Massive Multiple-Input Multiple-Out (MIMO) detection is an important problem in modern wireless communication systems. While traditional Belief Propagation (BP) detectors perform poorly on loopy graphs, the recent Graph Neural Networks (GNNs)-based method can overcome the drawbacks of BP and achieve superior performance.
  arXiv  Detail & Related papers  (2022-05-22T08:01:47Z)
• BScNets: Block Simplicial Complex Neural Networks [79.81654213581977]
  Simplicial neural networks (SNN) have recently emerged as the newest direction in graph learning. We present Block Simplicial Complex Neural Networks (BScNets) model for link prediction. BScNets outperforms state-of-the-art models by a significant margin while maintaining low costs.
  arXiv  Detail & Related papers  (2021-12-13T17:35:54Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph Networks [19.45752945234785]
  Imbalanced classification on graphs is ubiquitous yet challenging in many real-world applications, such as fraudulent node detection. We present a generative adversarial graph network model, called ImGAGN, to address the imbalanced classification problem on graphs. We show that the proposed method ImGAGN outperforms state-of-the-art algorithms for semi-supervised imbalanced node classification task.
  arXiv  Detail & Related papers  (2021-06-05T06:56:37Z)
• Graph neural network based approximation of Node Resiliency in complex networks [1.629817296011086]
  We propose a graph neural network (GNN) based framework for approximating node resilience in large complex networks. The proposed framework defines a GNN model that learns the node rank on a small representative subset of nodes. The scalability of the framework is demonstrated through the prediction of node ranks in real-world graphs.
  arXiv  Detail & Related papers  (2020-12-26T05:37:18Z)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  We propose a graph meta-learning framework -- Graph Prototypical Networks (GPN) GPN is able to perform textitmeta-learning on an attributed network and derive a highly generalizable model for handling the target classification task.
  arXiv  Detail & Related papers  (2020-06-23T04:13:23Z)
• MSE-Optimal Neural Network Initialization via Layer Fusion [68.72356718879428]
  Deep neural networks achieve state-of-the-art performance for a range of classification and inference tasks. The use of gradient combined nonvolutionity renders learning susceptible to novel problems. We propose fusing neighboring layers of deeper networks that are trained with random variables.
  arXiv  Detail & Related papers  (2020-01-28T18:25:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.