Exploring Heterophily in Graph-level Tasks

• URL: http://arxiv.org/abs/2509.18893v1
• Date: Tue, 23 Sep 2025 11:07:16 GMT
• Title: Exploring Heterophily in Graph-level Tasks
• Authors: Qinhan Hou, Yilun Zheng, Xichun Zhang, Sitao Luan, Jing Tang,
• Abstract summary: We present the first analysis of heterophily in graph-level learning, combining theoretical insights with empirical validation.<n>We first introduce a taxonomy of graph-level labeling schemes, and focus on motif-based tasks within local structure labeling.<n>Using energy-based gradient flow analysis, we reveal a key insight: unlike frequency-dominated regimes in node-level tasks, motif detection requires mixed-frequency dynamics to remain flexible.
• Score: 9.539979711178416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: While heterophily has been widely studied in node-level tasks, its impact on graph-level tasks remains unclear. We present the first analysis of heterophily in graph-level learning, combining theoretical insights with empirical validation. We first introduce a taxonomy of graph-level labeling schemes, and focus on motif-based tasks within local structure labeling, which is a popular labeling scheme. Using energy-based gradient flow analysis, we reveal a key insight: unlike frequency-dominated regimes in node-level tasks, motif detection requires mixed-frequency dynamics to remain flexible across multiple spectral components. Our theory shows that motif objectives are inherently misaligned with global frequency dominance, demanding distinct architectural considerations. Experiments on synthetic datasets with controlled heterophily and real-world molecular property prediction support our findings, showing that frequency-adaptive model outperform frequency-dominated models. This work establishes a new theoretical understanding of heterophily in graph-level learning and offers guidance for designing effective GNN architectures.

Related papers

• Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks [2.6124895681424323]
  Graph Neural Networks (GNNs) often struggle to propagate information across long distances due to oversmoothing and oversquashing.<n>We introduce a Bakry-Emery graph Laplacian that integrates diffusion and advection through a learnable node-wise potential.<n>We develop mu-ChebNet, a spectral architecture that jointly learns the potential and Chebyshev filters.
  arXiv  Detail & Related papers  (2026-02-20T11:01:12Z)
• Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information [91.66597637613263]
  transformer-based models leveraging the attention mechanism have demonstrated strong empirical success in capturing complex dependencies within graphs.<n>We introduce a novel information-theoretic metric: the kernel-guided mutual information (KG-MI) based on the $f$-divergence.<n>We prove that, given sequences generated by a $K$-parent DAG, training a single-layer, multi-head transformer via a gradient ascent converges to the global optimum time.
  arXiv  Detail & Related papers  (2025-10-29T14:07:12Z)
• Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessing [1.1126342180866644]
  Graph Neural Networks have emerged as the most popular architecture for graph-level learning.<n>We show that good performance in practice requires careful model design.<n>We propose a selective approach, which only targets graphs whose individual performance benefits from rewiring.
  arXiv  Detail & Related papers  (2025-03-01T16:18:07Z)
• Perturbation Ontology based Graph Attention Networks [26.95077612390953]
  Ontology-based Graph Attention Networks (POGAT) is a novel methodology that combines ontology subgraphs with an advanced self-supervised learning paradigm to achieve a deep contextual understanding.<n>POGAT significantly outperforms state-of-the-art baselines, achieving a groundbreaking improvement of up to 10.78% in F1-score for the critical task of link prediction and 12.01% in Micro-F1 for the critical task of node classification.
  arXiv  Detail & Related papers  (2024-11-27T17:12:14Z)
• 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)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models [22.421702511126373]
  We leverage statistical inference on block models to guide the development of a spectral clustering algorithm for directed graphs.<n>We establish a theoretical upper bound on the misclustering error of its spectral relaxation, and based on this relaxation, introduce a novel, self-adaptive spectral clustering method for directed graphs.
  arXiv  Detail & Related papers  (2024-03-28T15:47:13Z)
• Shape-aware Graph Spectral Learning [36.63516222161871]
  Spectral Graph Neural Networks (GNNs) are gaining attention for their ability to surpass the limitations of message-passing GNNs. Some works empirically show that the preferred graph frequency is related to the graph homophily level. This relationship between graph frequency and graphs with homophily/heterophily has not been systematically analyzed and considered in existing spectral GNNs. We propose shape-aware regularization on a Newton Interpolation-based spectral filter that can learn an arbitrary spectral filter and incorporate prior knowledge about the desired shape of the corresponding homophily level.
  arXiv  Detail & Related papers  (2023-10-16T04:57:30Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexity [71.11795737362459]
  ViTs with self-attention modules have recently achieved great empirical success in many tasks. However, theoretical learning generalization analysis is mostly noisy and elusive. This paper provides the first theoretical analysis of a shallow ViT for a classification task.
  arXiv  Detail & Related papers  (2023-02-12T22:12:35Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57: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.