Imbalanced Node Classification Beyond Homophilic Assumption

• URL: http://arxiv.org/abs/2304.14635v1
• Date: Fri, 28 Apr 2023 05:33:19 GMT
• Title: Imbalanced Node Classification Beyond Homophilic Assumption
• Abstract summary: We propose a novel GraphSANN for imbalanced node classification on both homophilic and heterophilic graphs. Firstly, we propose a unified feature mixer to generate synthetic nodes with both homophilic and heterophilic in a unified way. Next, by randomly sampling edges between synthetic nodes and existing nodes as candidate edges, we design an adaptive subgraph extractor.
• Score: 39.94226626445198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Imbalanced node classification widely exists in real-world networks where graph neural networks (GNNs) are usually highly inclined to majority classes and suffer from severe performance degradation on classifying minority class nodes. Various imbalanced node classification methods have been proposed recently which construct synthetic nodes and edges w.r.t. minority classes to balance the label and topology distribution. However, they are all based on the homophilic assumption that nodes of the same label tend to connect despite the wide existence of heterophilic edges in real-world graphs. Thus, they uniformly aggregate features from both homophilic and heterophilic neighbors and rely on feature similarity to generate synthetic edges, which cannot be applied to imbalanced graphs in high heterophily. To address this problem, we propose a novel GraphSANN for imbalanced node classification on both homophilic and heterophilic graphs. Firstly, we propose a unified feature mixer to generate synthetic nodes with both homophilic and heterophilic interpolation in a unified way. Next, by randomly sampling edges between synthetic nodes and existing nodes as candidate edges, we design an adaptive subgraph extractor to adaptively extract the contextual subgraphs of candidate edges with flexible ranges. Finally, we develop a multi-filter subgraph encoder that constructs different filter channels to discriminatively aggregate neighbor's information along the homophilic and heterophilic edges. Extensive experiments on eight datasets demonstrate the superiority of our model for imbalanced node classification on both homophilic and heterophilic graphs.

Related papers

• Addressing Graph Heterogeneity and Heterophily from A Spectral Perspective [46.37860909753809]
  Heterogeneity refers to a graph with multiple types of nodes or edges, while heterophily refers to the fact that connected nodes are more likely to have dissimilar attributes or labels. We propose a Heterogeneous Heterophilic Spectral Graph Neural Network (H2SGNN), which employs two modules: local independent filtering and global hybrid filtering. Extensive experiments are conducted on four datasets to validate the effectiveness of the proposed H2SGNN.
  arXiv  Detail & Related papers  (2024-10-17T09:23:53Z)
• The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges [101.83124435649358]
  Homophily principle, ie nodes with the same labels or similar attributes are more likely to be connected. Recent work has identified a non-trivial set of datasets where GNN's performance compared to the NN's is not satisfactory.
  arXiv  Detail & Related papers  (2024-07-12T18:04:32Z)
• 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)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? [61.35457647107439]
  Most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns. We provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity.
  arXiv  Detail & Related papers  (2023-06-02T07:46:20Z)
• Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering [15.764819403555512]
  It is impossible to first identify a graph as homophilic or heterophilic before a suitable GNN model can be found. We propose a novel graph clustering method, which contains three key components: graph reconstruction, a mixed filter, and dual graph clustering network. Our method dominates others on heterophilic graphs.
  arXiv  Detail & Related papers  (2023-05-03T01:49:01Z)
• Neighborhood Homophily-based Graph Convolutional Network [4.511171093050241]
  Graph neural networks (GNNs) have been proved powerful in graph-oriented tasks. Many real-world graphs are heterophilous, challenging the homophily assumption of classical GNNs. Recent studies propose new metrics to characterize the homophily, but rarely consider the correlation of the proposed metrics and models. In this paper, we first design a new metric, Neighborhood Homophily (textitNH), to measure the label complexity or purity in node neighborhoods.
  arXiv  Detail & Related papers  (2023-01-24T07:56:44Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  We show that a well-known graph algorithm, Label Propagation, combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities.
  arXiv  Detail & Related papers  (2022-05-19T08:34:34Z)
• 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)
• Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs [20.470934944907608]
  We investigate a novel framework that performs well on graphs with either homophily or heterophily. In label-wise message-passing, neighbors with similar pseudo labels will be aggregated together. We also propose a bi-level optimization method to automatically select the model for graphs with homophily/heterophily.
  arXiv  Detail & Related papers  (2021-10-15T14:49:45Z)
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs [6.018995094882323]
  Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. Most GNNs assume local homophily, i.e., strong similarities in localneighborhoods. We propose a flexible GNN model, which is capable of handling any graphs without beingrestricted by their underlying homophily.
  arXiv  Detail & Related papers  (2021-03-26T00:35:36Z)

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.