Learning Personalized Scoping for Graph Neural Networks under Heterophily

• URL: http://arxiv.org/abs/2409.06998v2
• Date: Mon, 21 Oct 2024 03:07:06 GMT
• Title: Learning Personalized Scoping for Graph Neural Networks under Heterophily
• Authors: Gangda Deng, Hongkuan Zhou, Rajgopal Kannan, Viktor Prasanna,
• Abstract summary: Heterophilous graphs, where dissimilar nodes tend to connect, pose a challenge for graph neural networks (GNNs) We formalize personalized scoping as a separate scope classification problem that overcomes GNN overfitting in node classification. We propose Adaptive Scope (AS), a lightweight approach that only participates in GNN inference.
• Score: 3.475704621679017
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heterophilous graphs, where dissimilar nodes tend to connect, pose a challenge for graph neural networks (GNNs) as their superior performance typically comes from aggregating homophilous information. Increasing the GNN depth can expand the scope (i.e., receptive field), potentially finding homophily from the higher-order neighborhoods. However, uniformly expanding the scope results in subpar performance since real-world web graphs often exhibit homophily disparity between nodes. An ideal way is personalized scopes, allowing nodes to have varying scope sizes. Existing methods typically add node-adaptive weights for each hop. Although expressive, they inevitably suffer from severe overfitting. To address this issue, we formalize personalized scoping as a separate scope classification problem that overcomes GNN overfitting in node classification. Specifically, we predict the optimal GNN depth for each node. Our theoretical and empirical analysis suggests that accurately predicting the depth can significantly enhance generalization. We further propose Adaptive Scope (AS), a lightweight approach that only participates in GNN inference. AS encodes structural patterns and predicts the depth to select the best model for each node's prediction. Experimental results show that AS is highly flexible with various GNN architectures across a wide range of datasets while significantly improving accuracy.

Related papers

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  We introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth.
  arXiv  Detail & Related papers  (2024-06-18T12:16:00Z)
• 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)
• When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability [92.8279562472538]
  Homophily principle has been believed to be the main reason for the performance superiority of Graph Networks (GNNs) over Neural Networks on node classification tasks. Recent research suggests that, even in the absence of homophily, the advantage of GNNs still exists as long as nodes from the same class share similar neighborhood patterns.
  arXiv  Detail & Related papers  (2023-04-25T09:40:47Z)
• GNN-Ensemble: Towards Random Decision Graph Neural Networks [3.7620848582312405]
  Graph Neural Networks (GNNs) have enjoyed wide spread applications in graph-structured data. GNNs are required to learn latent patterns from a limited amount of training data to perform inferences on a vast amount of test data. In this paper, we push one step forward on the ensemble learning of GNNs with improved accuracy, robustness, and adversarial attacks.
  arXiv  Detail & Related papers  (2023-03-20T18:24:01Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  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.
  arXiv  Detail & Related papers  (2021-11-19T08:54:21Z)
• Graph Pointer Neural Networks [11.656981519694218]
  We present Graph Pointer Neural Networks (GPNN) to tackle the challenges mentioned above. We leverage a pointer network to select the most relevant nodes from a large amount of multi-hop neighborhoods. The GPNN significantly improves the classification performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-10-03T10:18:25Z)
• Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification? [44.71818395535755]
  Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using the graph structures based on the inductive bias (homophily assumption) Performance advantages of GNNs over graph-agnostic NNs seem not generally satisfactory. Heterophily has been considered as a main cause and numerous works have been put forward to address it.
  arXiv  Detail & Related papers  (2021-09-12T23:57:05Z)
• 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)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  Graph neural networks (GNNs) learn the representation of a node by aggregating its neighbors. Over-smoothing is one of the key issues which limit the performance of GNNs as the number of layers increases. We introduce two over-smoothing metrics and a novel technique, i.e., differentiable group normalization (DGN)
  arXiv  Detail & Related papers  (2020-06-12T07:18:02Z)

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.