On the Unreasonable Effectiveness of Feature propagation in Learning on
Graphs with Missing Node Features
- URL: http://arxiv.org/abs/2111.12128v1
- Date: Tue, 23 Nov 2021 19:50:46 GMT
- Title: On the Unreasonable Effectiveness of Feature propagation in Learning on
Graphs with Missing Node Features
- Authors: Emanuele Rossi, Henry Kenlay, Maria I. Gorinova, Benjamin Paul
Chamberlain, Xiaowen Dong, Michael Bronstein
- Abstract summary: We present a general approach for handling missing features in graph machine learning applications.
We experimentally show that the proposed approach outperforms previous methods on seven common node-classification benchmarks.
It takes only 10 seconds to run on a graph with $sim$2.5M nodes and $sim$123M edges on a single GPU.
- Score: 7.421573539569853
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While Graph Neural Networks (GNNs) have recently become the de facto standard
for modeling relational data, they impose a strong assumption on the
availability of the node or edge features of the graph. In many real-world
applications, however, features are only partially available; for example, in
social networks, age and gender are available only for a small subset of users.
We present a general approach for handling missing features in graph machine
learning applications that is based on minimization of the Dirichlet energy and
leads to a diffusion-type differential equation on the graph. The
discretization of this equation produces a simple, fast and scalable algorithm
which we call Feature Propagation. We experimentally show that the proposed
approach outperforms previous methods on seven common node-classification
benchmarks and can withstand surprisingly high rates of missing features: on
average we observe only around 4% relative accuracy drop when 99% of the
features are missing. Moreover, it takes only 10 seconds to run on a graph with
$\sim$2.5M nodes and $\sim$123M edges on a single GPU.
Related papers
- Graph Sparsification via Mixture of Graphs [70.78196524207466]
We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node.
MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node.
Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
arXiv Detail & Related papers (2024-05-23T07:40:21Z) - 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) - A Simple and Scalable Graph Neural Network for Large Directed Graphs [11.792826520370774]
We investigate various combinations of node representations and edge direction awareness within an input graph.
In response, we propose a simple yet holistic classification method A2DUG.
We demonstrate that A2DUG stably performs well on various datasets and improves the accuracy up to 11.29 compared with the state-of-the-art methods.
arXiv Detail & Related papers (2023-06-14T06:24:58Z) - SGAT: Simplicial Graph Attention Network [38.7842803074593]
Heterogeneous graphs have multiple node and edge types and are semantically richer than homogeneous graphs.
Many graph neural network approaches for heterogeneous graphs use metapaths to capture multi-hop interactions between nodes.
We present Simplicial Graph Attention Network (SGAT), a simplicial complex approach to represent such high-order interactions.
arXiv Detail & Related papers (2022-07-24T15:20:41Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
We propose a bi-level optimization approach for learning the optimal graph structure.
We also explore a low-rank approximation model for further reducing the time complexity.
arXiv Detail & Related papers (2022-05-06T03:37:00Z) - DOTIN: Dropping Task-Irrelevant Nodes for GNNs [119.17997089267124]
Recent graph learning approaches have introduced the pooling strategy to reduce the size of graphs for learning.
We design a new approach called DOTIN (underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes) to reduce the size of graphs.
Our method speeds up GAT by about 50% on graph-level tasks including graph classification and graph edit distance.
arXiv Detail & Related papers (2022-04-28T12:00:39Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data.
We present a novel Graph Matching based GNN Pre-Training framework, called GMPT.
The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
arXiv Detail & Related papers (2022-03-03T09:53:53Z) - Node Feature Extraction by Self-Supervised Multi-scale Neighborhood
Prediction [123.20238648121445]
We propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT)
GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information.
We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets.
arXiv Detail & Related papers (2021-10-29T19:55:12Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data.
Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks.
In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
arXiv Detail & Related papers (2020-11-19T06:03:35Z) - Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
Graph embedding is a way to transform and encode the data structure in high dimensional and non-Euclidean feature space.
CensNet is a general graph embedding framework, which embeds both nodes and edges to a latent feature space.
Our approach achieves or matches the state-of-the-art performance in four graph learning tasks.
arXiv Detail & Related papers (2020-10-25T22:39:31Z) - Meta-path Free Semi-supervised Learning for Heterogeneous Networks [16.641434334366227]
Graph neural networks (GNNs) have been widely used in representation learning on graphs and achieved superior performance in tasks such as node classification.
In this paper, we propose simple and effective graph neural networks for heterogeneous graph, excluding the use of meta-paths.
arXiv Detail & Related papers (2020-10-18T06:01:58Z)
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.