graph neural networks
49430686
Graph to Sequence Learning using Gated Graph Neural Networks
Many NLP applications can be framed as a graph to sequence learning problem. Previous work proposing neural architectures on graph to sequence obtained promising results compared to grammar based approaches but still rely on linearisation heuristics and/or standard recurrent networks to achieve the best performance. In this work propose a new model that encodes the full structural information contained in the graph. Our architecture couples the recently proposed Gated Graph Neural Networks with an input transformation that allows nodes and edges to have their own hidden representations, while tackling the parameter explosion problem present in previous work. Experimental results shows that our model outperforms strong baselines in generation from AMR graphs and syntax based neural machine translation.
ACL
Daniel Beck Gholamreza Haffari Trevor Cohn
147703905
Understanding attention in graph neural networks
We aim to better understand attention over nodes in graph neural networks and identify factors influencing its effectiveness. Motivated by insights from the work on Graph Isomorphism Networks (Xu et al. 2019) we design simple graph reasoning tasks that allow us to study attention in a controlled environment. We find that under typical conditions the effect of attention is negligible or even harmful, but under certain conditions it provides an exceptional gain in performance of more than 40% in some of our classification tasks. However, we have yet to satisfy these conditions in practice.
NeurIPS 2019
Boris Knyazev Graham W Taylor Mohamed R Amer
202888963
GraphMix: Regularized Training of Graph Neural Networks for Semi Supervised Learning
We present GraphMix, a regularization technique for Graph Neural Network based semi supervised object classification, leveraging the recent advances in the regularization of classical deep neural networks. Specifically, we propose a unified approach in which we train a fully connected network jointly with the graph neural network via parameter sharing, interpolation based regularization, and self predicted targets. Our proposed method is architecture agnostic in the sense that it can be applied to any variant of graph neural networks which applies a parametric transformation to the features of the graph nodes. Despite its simplicity, with GraphMix we can consistently improve results and achieve or closely match state of the art performance using even simpler architectures such as Graph Convolutional Networks, across three established graph benchmarks: the Cora, Citeseer and Pubmed citation network datasets, as well as three newly proposed datasets Cora Full, Co author CS and Co author Physics.
ArXiv
Vikas Verma Meng Qu Alex Lamb Yoshua Bengio Juho Kannala Jian Tang
196184169
Graph based Dependency Parsing with Graph Neural Networks
We investigate the problem of efficiently incorporating high order features into neural graph based dependency parsing. Instead of explicitly extracting high order features from intermediate parse trees, we develop a more powerful dependency tree node representation which captures high order information concisely and efficiently. We use graph neural networks (GNNs) to learn the representations and discuss several new configurations of GNN's updating and aggregation functions. Experiments on PTB show that our parser achieves the best UAS and LAS on PTB (96.0% 94.3% among systems without using any external resources.
ACL
Tao Ji Yuanbin Wu Man Lan
162168667
Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks
How can we estimate the importance of nodes in a knowledge graph (KG) A KG is a multi relational graph that has proven valuable for many tasks including question answering and semantic search. In this paper, we present GENI, a method for tackling the problem of estimating node importance in KGs, which enables several downstream applications such as item recommendation and resource allocation. While a number of approaches have been developed to address this problem for general graphs, they do not fully utilize information available in KGs, or lack flexibility needed to model complex relationship between entities and their importance. To address these limitations, we explore supervised machine learning algorithms. In particular, building upon recent advancement of graph neural networks (GNNs) we develop GENI, a GNN based method designed to deal with distinctive challenges involved with predicting node importance in KGs. Our method performs an aggregation of importance scores instead of aggregating node embeddings via predicate aware attention mechanism and flexible centrality adjustment. In our evaluation of GENI and existing methods on predicting node importance in real world KGs with different characteristics, GENI achieves 5 17% higher NDCG@100 than the state of the art.
KDD
Namyong Park Andrey Kan Xin Dong Tong Zhao Christos Faloutsos
65051725
NerveNet: Learning Structured Policy with Graph Neural Networks
We address the problem of learning structured policies for continuous control. In traditional reinforcement learning, policies of agents are learned by multi layer perceptrons (MLPs) which take the concatenation of all observations from the environment as input for predicting actions. In this work, we propose NerveNet to explicitly model the structure of an agent, which naturally takes the form of a graph. Specifically, serving as the agent's policy network, NerveNet first propagates information over the structure of the agent and then predict actions for different parts of the agent. In the experiments, we first show that our NerveNet is comparable to state of the art methods on standard MuJoCo environments. We further propose our customized reinforcement learning environments for benchmarking two types of structure transfer learning tasks, i.e. size and disability transfer, as well as multi task learning. We demonstrate that policies learned by NerveNet are significantly more transferable and generalizable than policies learned by other models and are able to transfer even in a zero shot setting.
ICLR
Tingwu Wang Renjie Liao Jimmy Ba Sanja Fidler
70349914
Graph Neural Networks for User Identity Linkage
The increasing popularity and diversity of social media sites has encouraged more and more people to participate in multiple online social networks to enjoy their services. Each user may create a user identity to represent his or her unique public figure in every social network. User identity linkage across online social networks is an emerging task and has attracted increasing attention, which could potentially impact various domains such as recommendations and link predictions. The majority of existing work focuses on mining network proximity or user profile data for discovering user identity linkages. With the recent advancements in graph neural networks (GNNs) it provides great potential to advance user identity linkage since users are connected in social graphs, and learning latent factors of users and items is the key. However, predicting user identity linkages based on GNNs faces challenges. For example, the user social graphs encode both \textit{local} structure such as users' neighborhood signals, and \textit{global} structure with community properties. To address these challenges simultaneously, in this paper, we present a novel graph neural network framework \m} for user identity linkage. In particular, we provide a principled approach to jointly capture local and global information in the user user social graph and propose the framework \m} which jointly learning user representations for user identity linkage. Extensive experiments on real world datasets demonstrate the effectiveness of the proposed framework.
ArXiv
Wen Zhang Kai Shu Huan Liu Yalin Wang
201058629
Experimental performance of graph neural networks on random instances of max cut
This note explores the applicability of unsupervised machine learning techniques towards hard optimization problems on random inputs. In particular we consider Graph Neural Networks (GNNs) a class of neural networks designed to learn functions on graphs and we apply them to the max cut problem on random regular graphs. We focus on the max cut problem on random regular graphs because it is a fundamental problem that has been widely studied. In particular, even though there is no known explicit solution to compare the output of our algorithm to, we can leverage the known asymptotics of the optimal max cut value in order to evaluate the performance of the GNNs. In order to put the performance of the GNNs in context, we compare it with the classical semidefinite relaxation approach by Goemans and Williamson (SDP) and with extremal optimization, which is a local optimization heuristic from the statistical physics literature. The numerical results we obtain indicate that, surprisingly, Graph Neural Networks attain comparable performance to the Goemans and Williamson SDP. We also observe that extremal optimization consistently outperforms the other two methods. Furthermore, the performances of the three methods present similar patterns, that is, for sparser, and for larger graphs, the size of the found cuts are closer to the asymptotic optimal max cut value.
Optical Engineering Applications
Weichi Yao Afonso S Bandeira Soledad Villar
209386433
Deep Iterative and Adaptive Learning for Graph Neural Networks
In this paper, we propose an end to end graph learning framework, namely Deep Iterative and Adaptive Learning for Graph Neural Networks (DIAL GNN) for jointly learning the graph structure and graph embeddings simultaneously. We first cast the graph structure learning problem as a similarity metric learning problem and leverage an adapted graph regularization for controlling smoothness, connectivity and sparsity of the generated graph. We further propose a novel iterative method for searching for a hidden graph structure that augments the initial graph structure. Our iterative method dynamically stops when the learned graph structure approaches close enough to the optimal graph. Our extensive experiments demonstrate that the proposed DIAL GNN model can consistently outperform or match state of the art baselines in terms of both downstream task performance and computational time. The proposed approach can cope with both transductive learning and inductive learning.
ArXiv
Yu Chen Lingfei Wu Mohammed J Zaki
202541059
Auto GNN: Neural Architecture Search of Graph Neural Networks
Graph neural networks (GNN) has been successfully applied to operate on the graph structured data. Given a specific scenario, rich human expertise and tremendous laborious trials are usually required to identify a suitable GNN architecture. It is because the performance of a GNN architecture is significantly affected by the choice of graph convolution components, such as aggregate function and hidden dimension. Neural architecture search (NAS) has shown its potential in discovering effective deep architectures for learning tasks in image and language modeling. However, existing NAS algorithms cannot be directly applied to the GNN search problem. First, the search space of GNN is different from the ones in existing NAS work. Second, the representation learning capacity of GNN architecture changes obviously with slight architecture modifications. It affects the search efficiency of traditional search methods. Third, widely used techniques in NAS such as parameter sharing might become unstable in GNN. To bridge the gap, we propose the automated graph neural networks (AGNN) framework, which aims to find an optimal GNN architecture within a predefined search space. A reinforcement learning based controller is designed to greedily validate architectures via small steps. AGNN has a novel parameter sharing strategy that enables homogeneous architectures to share parameters, based on a carefully designed homogeneity definition. Experiments on real world benchmark datasets demonstrate that the GNN architecture identified by AGNN achieves the best performance, comparing with existing handcrafted models and tradistional search methods.
ArXiv
Kaixiong Zhou Qingquan Song Xiao Huang Xia Hu