Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Collective Learning Framework to Boost GNN Expressiveness
125
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success, but GNNs model dependencies among the attributes of nearby neighboring nodes rather than dependencies among observed node labels. In this work, we consider the task of inductive node classification using GNNs in supervised and semi-supervised settings, with the goal of incorporating label dependencies. Because current GNNs are not universal (i.e., most-expressive) graph representations, we propose a general collective learning approach to increase the representation power of any existing GNN. Our framework combines ideas from collective classification with self-supervised learning, and uses a Monte Carlo approach to sampling embeddings for inductive learning across graphs. We evaluate performance on five real-world network datasets and demonstrate consistent, significant improvement in node classification accuracy, for a variety of state-of-the-art GNNs.
rate research
Read More
The expressiveness of deep neural network (DNN) is a perspective to understandthe surprising performance of DNN. The number of linear regions, i.e. pieces thata piece-wise-linear function represented by a DNN, is generally used to measurethe expressiveness. And the upper bound of regions number partitioned by a rec-tifier network, instead of the number itself, is a more practical measurement ofexpressiveness of a rectifier DNN. In this work, we propose a new and tighter up-per bound of regions number. Inspired by the proof of this upper bound and theframework of matrix computation in Hinz & Van de Geer (2019), we propose ageneral computational approach to compute a tight upper bound of regions numberfor theoretically any network structures (e.g. DNN with all kind of skip connec-tions and residual structures). Our experiments show our upper bound is tighterthan existing ones, and explain why skip connections and residual structures canimprove network performance.
Humans can learn a variety of concepts and skills incrementally over the course of their lives while exhibiting many desirable properties, such as continual learning without forgetting, forward transfer and backward transfer of knowledge, and learning a new concept or task with only a few examples. Several lines of machine learning research, such as lifelong learning, few-shot learning, and transfer learning, attempt to capture these properties. However, most previous approaches can only demonstrate subsets of these properties, often by different complex mechanisms. In this work, we propose a simple yet powerful unified framework that supports almost all of these properties and approaches through one central mechanism. We also draw connections between many peculiarities of human learning (such as memory loss and rain man) and our framework. While we do not present any state-of-the-art results, we hope that this conceptual framework provides a novel perspective on existing work and proposes many new research directions.
In this paper, we proposed a general framework for data poisoning attacks to graph-based semi-supervised learning (G-SSL). In this framework, we first unify different tasks, goals, and constraints into a single formula for data poisoning attack in G-SSL, then we propose two specialized algorithms to efficiently solve two important cases --- poisoning regression tasks under $ell_2$-norm constraint and classification tasks under $ell_0$-norm constraint. In the former case, we transform it into a non-convex trust region problem and show that our gradient-based algorithm with delicate initialization and update scheme finds the (globally) optimal perturbation. For the latter case, although it is an NP-hard integer programming problem, we propose a probabilistic solver that works much better than the classical greedy method. Lastly, we test our framework on real datasets and evaluate the robustness of G-SSL algorithms. For instance, on the MNIST binary classification problem (50000 training data with 50 labeled), flipping two labeled data is enough to make the model perform like random guess (around 50% error).
A basic question in learning theory is to identify if two distributions are identical when we have access only to examples sampled from the distributions. This basic task is considered, for example, in the context of Generative Adversarial Networks (GANs), where a discriminator is trained to distinguish between a real-life distribution and a synthetic distribution. % Classically, we use a hypothesis class $H$ and claim that the two distributions are distinct if for some $hin H$ the expected value on the two distributions is (significantly) different. Our starting point is the following fundamental problem: is having the hypothesis dependent on more than a single random example beneficial. To address this challenge we define $k$-ary based discriminators, which have a family of Boolean $k$-ary functions $mathcal{G}$. Each function $gin mathcal{G}$ naturally defines a hyper-graph, indicating whether a given hyper-edge exists. A function $gin mathcal{G}$ distinguishes between two distributions, if the expected value of $g$, on a $k$-tuple of i.i.d examples, on the two distributions is (significantly) different. We study the expressiveness of families of $k$-ary functions, compared to the classical hypothesis class $H$, which is $k=1$. We show a separation in expressiveness of $k+1$-ary versus $k$-ary functions. This demonstrate the great benefit of having $kgeq 2$ as distinguishers. For $kgeq 2$ we introduce a notion similar to the VC-dimension, and show that it controls the sample complexity. We proceed and provide upper and lower bounds as a function of our extended notion of VC-dimension.
Graph Neural Networks(GNNs) are useful deep learning models to deal with the non-Euclid data. However, recent works show that GNNs are vulnerable to adversarial attacks. Small perturbations can lead to poor performance in many GNNs, such as Graph attention networks(GATs). Therefore, enhancing the robustness of GNNs is a critical problem. Robust GAT(RoGAT) is proposed to improve the robustness of GNNs in this paper, . Note that the original GAT uses the attention mechanism for different edges but is still sensitive to the perturbation, RoGAT adjusts the edges weight to adjust the attention scores progressively. Firstly, RoGAT tunes the edges weight based on the assumption that the adjacent nodes should have similar nodes. Secondly, RoGAT further tunes the features to eliminate features noises since even for the clean graph, there exists some unreasonable data. Then, we trained the adjusted GAT model to defense the adversarial attacks. Different experiments against targeted and untargeted attacks demonstrate that RoGAT outperforms significantly than most the state-of-the-art defense methods. The implementation of RoGAT based on the DeepRobust repository for adversarial attacks.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
