Graph Neural Networks with Feature and Structure Aware Random Walk

• URL: http://arxiv.org/abs/2111.10102v2
• Date: Mon, 28 Oct 2024 12:59:37 GMT
• Title: Graph Neural Networks with Feature and Structure Aware Random Walk
• Authors: Wei Zhuo, Guang Tan,
• Abstract summary: We show that in typical heterphilous graphs, the edges may be directed, and whether to treat the edges as is or simply make them undirected greatly affects the performance of the GNN models. We develop a model that adaptively learns the directionality of the graph, and exploits the underlying long-distance correlations between nodes.
• Score: 7.143879014059894
• License:
• Abstract: Graph Neural Networks (GNNs) have received increasing attention for representation learning in various machine learning tasks. However, most existing GNNs applying neighborhood aggregation usually perform poorly on the graph with heterophily where adjacent nodes belong to different classes. In this paper, we show that in typical heterphilous graphs, the edges may be directed, and whether to treat the edges as is or simply make them undirected greatly affects the performance of the GNN models. Furthermore, due to the limitation of heterophily, it is highly beneficial for the nodes to aggregate messages from similar nodes beyond local neighborhood.These motivate us to develop a model that adaptively learns the directionality of the graph, and exploits the underlying long-distance correlations between nodes. We first generalize the graph Laplacian to digraph based on the proposed Feature-Aware PageRank algorithm, which simultaneously considers the graph directionality and long-distance feature similarity between nodes. Then digraph Laplacian defines a graph propagation matrix that leads to a model called {\em DiglacianGCN}. Based on this, we further leverage the node proximity measured by commute times between nodes, in order to preserve the nodes' long-distance correlation on the topology level. Extensive experiments on ten datasets with different levels of homophily demonstrate the effectiveness of our method over existing solutions in the task of node classification.

Related papers

• Improving Graph Neural Networks by Learning Continuous Edge Directions [0.0]
  Graph Neural Networks (GNNs) traditionally employ a message-passing mechanism that resembles diffusion over undirected graphs. Our key insight is to assign fuzzy edge directions to the edges of a graph so that features can preferentially flow in one direction between nodes. We propose a general framework, called Continuous Edge Direction (CoED) GNN, for learning on graphs with fuzzy edges.
  arXiv  Detail & Related papers  (2024-10-18T01:34:35Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• GraphRARE: Reinforcement Learning Enhanced Graph Neural Network with Relative Entropy [21.553180564868306]
  GraphRARE is a framework built upon node relative entropy and deep reinforcement learning. An innovative node relative entropy is used to measure mutual information between node pairs. A deep reinforcement learning-based algorithm is developed to optimize the graph topology.
  arXiv  Detail & Related papers  (2023-12-15T11:30:18Z)
• 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)
• 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)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
  arXiv  Detail & Related papers  (2023-05-14T19:42:31Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• Incorporating Heterophily into Graph Neural Networks for Graph Classification [6.709862924279403]
  Graph Neural Networks (GNNs) often assume strong homophily for graph classification, seldom considering heterophily. We develop a novel GNN architecture called IHGNN (short for Incorporating Heterophily into Graph Neural Networks) We empirically validate IHGNN on various graph datasets and demonstrate that it outperforms the state-of-the-art GNNs for graph classification.
  arXiv  Detail & Related papers  (2022-03-15T06:48:35Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• On Local Aggregation in Heterophilic Graphs [11.100606980915144]
  We show that properly tuned classical GNNs and multi-layer perceptrons match or exceed the accuracy of recent long-range aggregation methods on heterophilic graphs. We propose the Neighborhood Information Content(NIC) metric, which is a novel information-theoretic graph metric.
  arXiv  Detail & Related papers  (2021-06-06T19:12:31Z)
• Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
  Graph Neural Network (GNN) is a powerful model to learn representations and make predictions on graph data. We propose a new graph convolution operator, which augments the weighted sum with pairwise interactions of the representations of neighbor nodes. We term this framework as Bilinear Graph Neural Network (BGNN), which improves GNN representation ability with bilinear interactions between neighbor nodes.
  arXiv  Detail & Related papers  (2020-02-10T06:43:38Z)

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.