Neural Trees for Learning on Graphs

• URL: http://arxiv.org/abs/2105.07264v1
• Date: Sat, 15 May 2021 17:08:20 GMT
• Title: Neural Trees for Learning on Graphs
• Authors: Rajat Talak, Siyi Hu, Lisa Peng, and Luca Carlone
• Abstract summary: Graph Neural Networks (GNNs) have emerged as a flexible and powerful approach for learning over graphs. We propose a new GNN architecture -- the Neural Tree. We show that the neural tree architecture can approximate any smooth probability distribution function over an undirected graph.
• Score: 19.05038106825347
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have emerged as a flexible and powerful approach for learning over graphs. Despite this success, existing GNNs are constrained by their local message-passing architecture and are provably limited in their expressive power. In this work, we propose a new GNN architecture -- the Neural Tree. The neural tree architecture does not perform message passing on the input graph but on a tree-structured graph, called the H-tree, that is constructed from the input graph. Nodes in the H-tree correspond to subgraphs in the input graph, and they are reorganized in a hierarchical manner such that a parent-node of a node in the H-tree always corresponds to a larger subgraph in the input graph. We show that the neural tree architecture can approximate any smooth probability distribution function over an undirected graph, as well as emulate the junction tree algorithm. We also prove that the number of parameters needed to achieve an $\epsilon$-approximation of the distribution function is exponential in the treewidth of the input graph, but linear in its size. We apply the neural tree to semi-supervised node classification in 3D scene graphs, and show that these theoretical properties translate into significant gains in prediction accuracy, over the more traditional GNN architectures.

Related papers

• Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
  Shapley Interactions (SIs) quantify node contributions and interactions among multiple nodes. By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction. We introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly.
  arXiv  Detail & Related papers  (2025-01-28T13:37:44Z)
• Graph Spring Neural ODEs for Link Sign Prediction [49.71046810937725]
  We propose a novel message-passing layer architecture called Graph Spring Network (GSN) modeled after spring forces. We show that our method achieves accuracy close to the state-of-the-art methods with node generation time speedup factors of up to 28,000 on large graphs.
  arXiv  Detail & Related papers  (2024-12-17T13:50:20Z)
• 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)
• TREE-G: Decision Trees Contesting Graph Neural Networks [33.364191419692105]
  TREE-G modifies standard decision trees, by introducing a novel split function that is specialized for graph data. We show that TREE-G consistently outperforms other tree-based models and often outperforms other graph-learning algorithms such as Graph Neural Networks (GNNs) and Graph Kernels.
  arXiv  Detail & Related papers  (2022-07-06T15:53:17Z)
• GTNet: A Tree-Based Deep Graph Learning Architecture [8.50892442127182]
  We propose a deep graph learning architecture with a new general message passing scheme that originates from the tree representation of graphs. Two graph representation learning models are proposed within this GTNet architecture - Graph Tree Attention Network (GTAN) and Graph Tree Convolution Network (GTCN)
  arXiv  Detail & Related papers  (2022-04-27T09:43:14Z)
• Graph Tree Neural Networks [0.43012765978447565]
  Graph tree neural networks (GTNNs) are designed to solve the problems of existing networks by analyzing the structure of human neural networks. In GTNNs, information units are related to the form of a graph and then they become a bigger unit of information again and have a relationship with other information units.
  arXiv  Detail & Related papers  (2021-10-31T07:58:00Z)
• Hierarchical graph neural nets can capture long-range interactions [8.067880298298185]
  We study hierarchical message passing models that leverage a multi-resolution representation of a given graph. This facilitates learning of features that span large receptive fields without loss of local information. We introduce Hierarchical Graph Net (HGNet), which for any two connected nodes guarantees existence of message-passing paths of at most logarithmic length.
  arXiv  Detail & Related papers  (2021-07-15T16:24:22Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• GraphSVX: Shapley Value Explanations for Graph Neural Networks [81.83769974301995]
  Graph Neural Networks (GNNs) achieve significant performance for various learning tasks on geometric data. In this paper, we propose a unified framework satisfied by most existing GNN explainers. We introduce GraphSVX, a post hoc local model-agnostic explanation method specifically designed for GNNs.
  arXiv  Detail & Related papers  (2021-04-18T10:40:37Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• TreeRNN: Topology-Preserving Deep GraphEmbedding and Learning [24.04035265351755]
  We study the methods to transfer the graphs into trees so that explicit orders are learned to direct the feature integration from local to global. To best learn the patterns from the graph-tree-images, we propose TreeRNN, a 2D RNN architecture that recurrently integrates the image pixels by rows and columns to help classify the graph categories.
  arXiv  Detail & Related papers  (2020-06-21T15:22:24Z)

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.