SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation

• URL: http://arxiv.org/abs/2305.09958v4
• Date: Wed, 09 Apr 2025 07:19:32 GMT
• Title: SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation
• Authors: Haoyu Liu, Ningyi Liao, Siqiang Luo,
• Abstract summary: Graph neural networks (GNNs) realize great success in graph learning but suffer from performance loss when meeting heterophily.<n>We propose SIGMA, an efficient global heterophilous GNN aggregation integrating the structural similarity measurement SimRank.
• Score: 12.302311645194775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) realize great success in graph learning but suffer from performance loss when meeting heterophily, i.e. neighboring nodes are dissimilar, due to their local and uniform aggregation. Existing attempts of heterophilous GNNs incorporate long-range or global aggregations to distinguish nodes in the graph. However, these aggregations usually require iteratively maintaining and updating full-graph information, which limits their efficiency when applying to large-scale graphs. In this paper, we propose SIGMA, an efficient global heterophilous GNN aggregation integrating the structural similarity measurement SimRank. Our theoretical analysis illustrates that SIGMA inherently captures distant global similarity even under heterophily, that conventional approaches can only achieve after iterative aggregations. Furthermore, it enjoys efficient one-time computation with a complexity only linear to the node set size $\mathcal{O}(n)$. Comprehensive evaluation demonstrates that SIGMA achieves state-of-the-art performance with superior aggregation and overall efficiency. Notably, it obtains $5\times$ acceleration on the large-scale heterophily dataset pokec with over 30 million edges compared to the best baseline aggregation.

Related papers

• GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs [11.458759345322832]
  Granular and Implicit Graph Network (GRAIN) is a novel GNN model specifically designed for heterophilous graphs. GRAIN enhances node embeddings by aggregating multi-view information at various levels and incorporating implicit data from distant, non-neighboring nodes. We also introduce an adaptive graph information aggregator that efficiently combines multi-granularity and implicit data, significantly improving node representation quality.
  arXiv  Detail & Related papers  (2025-04-09T07:36:44Z)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  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)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• 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)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  Heterogeneous graph neural networks (HGNNs) have powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) over homogeneous graphs, especially the attention mechanism and the multi-layer structure. This paper conducts an in-depth and detailed study of these mechanisms and proposes Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN)
  arXiv  Detail & Related papers  (2022-07-06T10:01:46Z)
• 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)
• 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)
• Higher-Order Attribute-Enhancing Heterogeneous Graph Neural Networks [67.25782890241496]
  We propose a higher-order Attribute-Enhancing Graph Neural Network (HAEGNN) for heterogeneous network representation learning. HAEGNN simultaneously incorporates meta-paths and meta-graphs for rich, heterogeneous semantics. It shows superior performance against the state-of-the-art methods in node classification, node clustering, and visualization.
  arXiv  Detail & Related papers  (2021-04-16T04:56:38Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  Graph Neural Networks (GNNs) explore the graph structure and node features by aggregating and transforming information within node neighborhoods. We propose SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs.
  arXiv  Detail & Related papers  (2020-11-19T04:18:01Z)
• Adaptive Universal Generalized PageRank Graph Neural Network [36.850433364139924]
  Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility. We introduce a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights. GPR-GNN offers significant performance improvement compared to existing techniques on both synthetic and benchmark data.
  arXiv  Detail & Related papers  (2020-06-14T19:27:39Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  Graph Neural Networks (GNNs) provide a data-driven solution for this task. Existing GNN-based methods, which either respectively embeds two graphs or deploy cross-graph interactions for whole graph pairs, are still not able to achieve competitive results. We propose the "embedding-coarsening-matching" framework CoSimGNN, which first embeds and coarsens large graphs with adaptive pooling operation and then deploys fine-grained interactions on the coarsened graphs for final similarity scores.
  arXiv  Detail & Related papers  (2020-05-14T16:33:13Z)
• Permutohedral-GCN: Graph Convolutional Networks with Global Attention [7.873191259466302]
  Graph convolutional networks (GCNs) update a node's feature vector by aggregating features from its neighbors in the graph. We introduce a global attention mechanism where a node can selectively attend to, and aggregate features from, any other node in the graph. We show that the resulting attention-based global aggregation scheme is analogous to high-dimensional Gaussian filtering.
  arXiv  Detail & Related papers  (2020-03-02T02:44:52Z)

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.