Query: graph node classification

title: Target Classification From SAR Imagery Based on the Pixel Grayscale Decline by Graph Convolutional Neural Network
abstract: The target classification from synthetic aperture radar (SAR) imagery is entering a bottleneck stage for the extensive use of a deep learning technology. Researchers have deployed various deep neural networks to extract the target features from the original SAR image in Euclidean space, which requires a large number of training data and cost lots of time to train the deep neural networks well generalized. Aiming at this problem, this letter introduces a novel method of target classification from SAR imagery based on the target pixel grayscale decline by a graph representation, which is different from the conventional deep learning methods so far. We separate the whole grayscale interval of one SAR image into several subintervals and assign a node to represent each pixel with the declined order of pixel grayscale in the subinterval. Then, a graph structure could be constructed to transform the raw SAR image from Euclidean data to graph structured data. Finally, we construct a graph convolutional neural network to extract the features of graph structured data we constructed previously and output the target classification result. The experiment result on the MSTAR dataset shows that our method achieved the average classification accuracy with 100% which surpasses all the state of the art methods for the first time in SAR automatic target recognition field.

title: Privacy Preserving Graph Neural Network for Node Classification
abstract: Recently, Graph Neural Network (GNN) has achieved remarkable progresses in various real world tasks on graph data, consisting of node features and the adjacent information between different nodes. High performance GNN models always depend on both rich features and complete edge information in graph. However, such information could possibly be isolated by different data holders in practice, which is the so called data isolation problem. To solve this problem, in this paper, we propose a Privacy Preserving GNN (PPGNN) learning paradigm for node classification task, which can be generalized to existing GNN models. Specifically, we split the computation graph into two parts. We leave the private data (i.e. features, edges, and labels) related computations on data holders, and delegate the rest of computations to a semi honest server. We conduct experiments on three benchmarks and the results demonstrate that PPGNN significantly outperforms the GNN models trained on the isolated data and has comparable performance with the traditional GNN trained on the mixed plaintext data.

title: Understanding Negative Sampling in Graph Representation Learning
abstract: Graph representation learning has been extensively studied in recent years, in which sampling is a critical point. Prior arts usually focus on sampling positive node pairs, while the strategy for negative sampling is left insufficiently explored. To bridge the gap, we systematically analyze the role of negative sampling from the perspectives of both objective and risk, theoretically demonstrating that negative sampling is as important as positive sampling in determining the optimization objective and the resulted variance. To the best of our knowledge, we are the first to derive the theory and quantify that a nice negative sampling distribution is pn(u|v) pd(u|v)a, 0 a 1. With the guidance of the theory, we propose MCNS, approximating the positive distribution with self contrast approximation and accelerating negative sampling by Metropolis Hastings. We evaluate our method on 5 datasets that cover extensive downstream graph learning tasks, including link prediction, node classification and recommendation, on a total of 19 experimental settings. These relatively comprehensive experimental results demonstrate its robustness and superiorities.

title: Adversarial Attacks on Graph Neural Networks via Node Injections: A Hierarchical Reinforcement Learning Approach
abstract: Graph Neural Networks (GNN) offer the powerful approach to node classification in complex networks across many domains including social media, E commerce, and FinTech. However, recent studies show that GNNs are vulnerable to attacks aimed at adversely impacting their node classification performance. Existing studies of adversarial attacks on GNN focus primarily on manipulating the connectivity between existing nodes, a task that requires greater effort on the part of the attacker in real world applications. In contrast, it is much more expedient on the part of the attacker to inject adversarial nodes, e.g. fake profiles with forged links, into existing graphs so as to reduce the performance of the GNN in classifying existing nodes. Hence, we consider a novel form of node injection poisoning attacks on graph data. We model the key steps of a node injection attack, e.g. establishing links between the injected adversarial nodes and other nodes, choosing the label of an injected node, etc. by a Markov Decision Process. We propose a novel reinforcement learning method for Node Injection Poisoning Attacks (NIPA) to sequentially modify the labels and links of the injected nodes, without changing the connectivity between existing nodes. Specifically, we introduce a hierarchical Q learning network to manipulate the labels of the adversarial nodes and their links with other nodes in the graph, and design an appropriate reward function to guide the reinforcement learning agent to reduce the node classification performance of GNN. The results of the experiments show that NIPA is consistently more effective than the baseline node injection attack methods for poisoning graph data on three benchmark datasets.

title: Unifying Graph Convolutional Neural Networks and Label Propagation
abstract: Label Propagation (LPA) and Graph Convolutional Neural Networks (GCN) are both message passing algorithms on graphs. Both solve the task of node classification but LPA propagates node label information across the edges of the graph, while GCN propagates and transforms node feature information. However, while conceptually similar, theoretical relation between LPA and GCN has not yet been investigated. Here we study the relationship between LPA and GCN in terms of two aspects: (1) feature/label smoothing where we analyze how the feature/label of one node is spread over its neighbors; And, (2) feature/label influence of how much the initial feature/label of one node influences the final feature/label of another node. Based on our theoretical analysis, we propose an end to end model that unifies GCN and LPA for node classification. In our unified model, edge weights are learnable, and the LPA serves as regularization to assist the GCN in learning proper edge weights that lead to improved classification performance. Our model can also be seen as learning attention weights based on node labels, which is more task oriented than existing feature based attention models. In a number of experiments on real world graphs, our model shows superiority over state of the art GCN based methods in terms of node classification accuracy.

title: Explain Graph Neural Networks to Understand Weighted Graph Features in Node Classification
abstract: Real data collected from different applications that have additional topological structures and connection information are amenable to be represented as a weighted graph. Considering the node labeling problem, Graph Neural Networks (GNNs) is a powerful tool, which can mimic experts' decision on node labeling. GNNs combine node features, connection patterns, and graph structure by using a neural network to embed node information and pass it through edges in the graph. We want to identify the patterns in the input data used by the GNN model to make a decision and examine if the model works as we desire. However, due to the complex data representation and non linear transformations, explaining decisions made by GNNs is challenging. In this work, we propose new graph features' explanation methods to identify the informative components and important node features. Besides, we propose a pipeline to identify the key factors used for node classification. We use four datasets (two synthetic and two real) to validate our methods. Our results demonstrate that our explanation approach can mimic data patterns used for node classification by human interpretation and disentangle different features in the graphs. Furthermore, our explanation methods can be used for understanding data, debugging GNN models, and examine model decisions.

title: Graph Inference Learning for Semi supervised Classification
abstract: In this work, we address the semi supervised classification of graph data, where the categories of those unlabeled nodes are inferred from labeled nodes as well as graph structures. Recent works often solve this problem with the advanced graph convolution in a conventional supervised manner, but the performance could be heavily affected when labeled data is scarce. Here we propose a Graph Inference Learning (GIL) framework to boost the performance of node classification by learning the inference of node labels on graph topology. To bridge the connection of two nodes, we formally define a structure relation by encapsulating node attributes, between node paths and local topological structures together, which can make inference conveniently deduced from one node to another node. For learning the inference process, we further introduce meta optimization on structure relations from training nodes to validation nodes, such that the learnt graph inference capability can be better self adapted into test nodes. Comprehensive evaluations on four benchmark datasets (including Cora, Citeseer, Pubmed and NELL) demonstrate the superiority of our GIL when compared with other state of the art methods in the semi supervised node classification task.

title: Benchmarking Graph Neural Networks
abstract: Graph neural networks (GNNs) have become the standard toolkit for analyzing and learning from data on graphs. As the field grows, it becomes critical to identify key architectures and validate new ideas that generalize to larger, more complex datasets. Unfortunately, it has been increasingly difficult to gauge the effectiveness of new models in the absence of a standardized benchmark with consistent experimental settings. In this paper, we introduce a reproducible GNN benchmarking framework, with the facility for researchers to add new models conveniently for arbitrary datasets. We demonstrate the usefulness of our framework by presenting a principled investigation into the recent Weisfeiler Lehman GNNs (WL GNNs) compared to message passing based graph convolutional networks (GCNs) for a variety of graph tasks, i.e. graph regression/classification and node/link prediction, with medium scale datasets.

title: Coloring graph neural networks for node disambiguation
abstract: In this paper, we show that a simple coloring scheme can improve, both theoretically and empirically, the expressive power of Message Passing Neural Networks(MPNNs) More specifically, we introduce a graph neural network called Colored Local Iterative Procedure (CLIP) that uses colors to disambiguate identical node attributes, and show that this representation is a universal approximator of continuous functions on graphs with node attributes. Our method relies on separability a key topological characteristic that allows to extend well chosen neural networks into universal representations. Finally, we show experimentally that CLIP is capable of capturing structural characteristics that traditional MPNNs fail to distinguish,while being state of the art on benchmark graph classification datasets.

title: Minimal Driver Nodes for Structural Controllability of Large Scale Dynamical Systems: Node Classification
abstract: This article considers the problem of minimal control inputs to affect the system states such that the resulting system is structurally controllable. This problem and the dual problem of minimal observability are claimed to have no polynomial order exact solution and, therefore, are NP hard. Here, adopting a graph theoretic approach, this problem is solved for general nonlinear (and also structure invariant) systems, and a P order solution is proposed. In this direction, the dynamical system is modeled as a directed graph, called system digraph, and two types of graph components are introduced, which are tightly related to structural controllability. Two types of nodes, which are required to be affected (or driven) by an input, called driver nodes, are defined, and minimal number of these driver nodes are obtained. Polynomial order complexity of the given algorithms to solve the problem ensures applicability of the solution for analysis of large scale dynamical systems. The structural results in this article are significant as compared with the existing literature, which offer approximate and computationally less efficient, e.g. Gramian based, solutions for the problem, while this article provides an exact solution with the lower computational complexity and applicable for controllability analysis of nonlinear systems.