Invariant Layers for Graphs with Nodes of Different Types

• URL: http://arxiv.org/abs/2302.13551v1
• Date: Mon, 27 Feb 2023 07:10:33 GMT
• Title: Invariant Layers for Graphs with Nodes of Different Types
• Authors: Dmitry Rybin, Ruoyu Sun, Zhi-Quan Luo
• Abstract summary: We show that implementing linear layers invariant to input permutations allows learning important node interactions more effectively than existing techniques. Our findings suggest that function approximation on a graph with $n$ nodes can be done with tensors of sizes $leq n$, which is tighter than the best-known bound $leq n(n-1)/2$.
• Score: 27.530546740444077
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Neural networks that satisfy invariance with respect to input permutations have been widely studied in machine learning literature. However, in many applications, only a subset of all input permutations is of interest. For heterogeneous graph data, one can focus on permutations that preserve node types. We fully characterize linear layers invariant to such permutations. We verify experimentally that implementing these layers in graph neural network architectures allows learning important node interactions more effectively than existing techniques. We show that the dimension of space of these layers is given by a generalization of Bell numbers, extending the work (Maron et al., 2019). We further narrow the invariant network design space by addressing a question about the sizes of tensor layers necessary for function approximation on graph data. Our findings suggest that function approximation on a graph with $n$ nodes can be done with tensors of sizes $\leq n$, which is tighter than the best-known bound $\leq n(n-1)/2$. For $d \times d$ image data with translation symmetry, our methods give a tight upper bound $2d - 1$ (instead of $d^{4}$) on sizes of invariant tensor generators via a surprising connection to Davenport constants.

Related papers

• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• On the Expressive Power of Sparse Geometric MPNNs [3.396731589928944]
  We study the expressive power of message-passing neural networks for geometric graphs. We show that generic pairs of non-isomorphic geometric graphs can be separated by message-passing networks.
  arXiv  Detail & Related papers  (2024-07-02T07:48:22Z)
• Learning to Approximate Adaptive Kernel Convolution on Graphs [4.434835769977399]
  We propose a diffusion learning framework, where the range of feature aggregation is controlled by the scale of a diffusion kernel. Our model is tested on various standard for node-wise classification for the state-of-the-art datasets performance. It is also validated on a real-world brain network data for graph classifications to demonstrate its practicality for Alzheimer classification.
  arXiv  Detail & Related papers  (2024-01-22T10:57:11Z)
• 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)
• Node Embedding from Neural Hamiltonian Orbits in Graph Neural Networks [33.88288279902204]
  In this paper, we model the embedding update of a node feature as a Hamiltonian orbit over time. Our proposed node embedding strategy can automatically learn, without extensive tuning, the underlying geometry of any given graph dataset. Numerical experiments demonstrate that our approach adapts better to different types of graph datasets than popular state-of-the-art graph node embedding GNNs.
  arXiv  Detail & Related papers  (2023-05-30T11:53:40Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  We propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into a sequence. We evaluate our method on a massive graph with more than 111 million nodes and 1.6 billion edges. Results show that our proposed method is scalable to massive graphs and achieves superior performance across massive and medium-scale graphs.
  arXiv  Detail & Related papers  (2022-02-07T16:38:36Z)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  A major issue with arbitrary graphs is the absence of canonical positional information of nodes. We introduce Positional nodes (PE) of nodes, and inject it into the input layer, like in Transformers. We observe a performance increase for molecular datasets, from 2.87% up to 64.14% when considering learnable PE for both GNN classes.
  arXiv  Detail & Related papers  (2021-10-15T05:59:15Z)
• RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
  Graph neural networks (GNNs) have gained increasing popularity and have shown very promising results for data that are represented by graphs. We propose a random walk data processing of the graphs based on three selected lengths. Namely, (regular) walks of length 1 and 2, and a fractional walk of length $gamma in (0,1)$, in order to capture the different local and global dynamics on the graphs. We test our method on various molecular datasets by passing the processed node features to the network in order to perform several classification and regression tasks.
  arXiv  Detail & Related papers  (2021-09-15T20:04:01Z)

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.