Exploring Heterophily in Graph-level Tasks

Qinhan Hou 1,2 , Yilun Zheng 3 , Xichun Zhang 2 , Sitao Luan 4,5,∗ , Jing Tang 2,∗ 1 Doctoral Program of Computer Science, University of Helsinki, Helsinki, Finland 2 Research Program in Systems Oncology, Faculty of Medicine, University of Helsinki, Helsinki, Finland 3 Centre for Information Science · 2025

Read Exploring Heterophily in Graph-level Tasks by Qinhan Hou 1,2 , Yilun Zheng 3 , Xichun Zhang 2 , Sitao Luan 4,5,∗ , Jing Tang 2,∗ 1 Doctoral Program of Computer Science, University of Helsinki, Helsinki, Finland 2 Research Program in Systems Oncology, Faculty of Medicine, University of Helsinki, Helsinki, Finland 3 Centre for Information Science (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18893.txt.

Introduction

In graph learning, linked nodes often share labels, but sometimes neighbors differ on purpose. Qinhan Hou, Yilun Zheng, Xichun Zhang, Sitao Luan, and Jing Tang study that mismatch, called heterophily, at the whole-graph level in this 2025 paper. Node-level heterophily is well studied. Its graph-level cousin, where the label describes the whole structure, was not.

The team sorts graph labeling schemes into a taxonomy and focuses on motif-based tasks. Motifs are small recurring patterns whose presence sets the label. An energy-based flow analysis yields the key insight: motif detection needs mixed-frequency dynamics, not one dominant band. Objectives based on motifs clash with global frequency dominance by design. Tests on synthetic graphs with tuned heterophily and on molecular data back the theory. Frequency-adaptive models beat frequency-dominated ones. The paper offers design guidance for graph-level networks.

Catalog record

CREATORQinhan Hou 1,2 , Yilun Zheng 3 , Xichun Zhang 2 , Sitao Luan 4,5,∗ , Jing Tang 2,∗ 1 Doctoral Program of Computer Science, University of Helsinki, Helsinki, Finland 2 Research Program in Systems Oncology, Faculty of Medicine, University of Helsinki, Helsinki, Finland 3 Centre for Information Science
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-18893

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exploring Heterophily in Graph-level Tasks Qinhan Hou 1,2 , Yilun Zheng 3 , Xichun Zhang 2 , Sitao Luan 4,5,∗ , Jing Tang 2,∗ 1 Doctoral Program of Computer Science, University of Helsinki, Helsinki, Finland 2 Research Program in Systems Oncology, Faculty of Medicine, University of Helsinki, Helsinki, Finland 3 Centre for Information Sciences and Systems, Nanyang Technological University, Singapore 4 University of Montreal, Canada 5 Mila, Quebec Artificial Intelligence Institute, Canada ∗ Corresponding author, main supervision 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. \workshoptitle New Perspectives in Graph Machine Learning 1 Introduction Graph Neural Networks (GNNs) have achieved success in learning from graph-structured data, demonstrating strong performance across diverse domains including social networks [ 19 , 26 ] and molecular property prediction [ 41 , 45 ] . Many popular GNN architectures, such as Graph Convolutional Networks (GCNs) [ 11 ] , are designed under the homophily assumption, i.e., connected nodes tend to share similar features or labels [ 29 , 14 , 25 ] . However, many real-world graphs exhibit heterophily, where neighboring nodes have dissimilar characteristics [ 47 , 24 ] . While the challenges posed by heterophily have been extensively studied on node-level tasks [ 23 , 21 , 22 , 44 , 43 , 42 ] , its impact on graph-level tasks remains poorly understood. This work is the first to study heterophily in graph-level tasks. We introduce a taxonomy that classifies such tasks into three types by their labeling mechanisms, focusing on motif-based tasks where labels depend on discriminative subgraphs ( motifs ). From an energy and gradient flow perspective [ 12 ] , our analysis shows that graph-level tasks have distinct frequency preferences from node-level tasks, as motif detection misaligns with the global nature of low- and high-frequency dominant regimes. This misalignment challenges the effectiveness of GNN under heterophily settings. We provide both theoretical and empirical evidence, offering new insights into heterophily’s role in graph-level prediction and guiding the design of more adaptive GNNs. 2 Task Taxonomy, Notations and Background 2.1 Task Taxonomy Compared to node-level tasks, the labeling schemes of graph-level tasks make it challenging to establish a simple and general relation between graph labels and certain graph properties. To enable a simplified and systematic discussion, we categorize the labeling schemes into three main types based on the following criterion derived from practical applications. Aggregated Node Features. In this scenario, graph labels are primarily determined by aggregated node features. For instance, a graph may be assigned to a particular class if the average value of a specific node feature across all nodes exceeds a given threshold, or if a certain proportion of nodes belong to a particular latent class, e.g., online community detection based on aggregated user demographics [ 30 , 9 , 5 ] . Local Structure. Labels depend on local structural patterns and node-level features. For example, a label may be assigned based on the presence of a specified number of particular motifs ( e.g., triangles) within the graph. These motifs may predominantly consist of either homophilic or heterophilic nodes, e.g., molecular classification based on the presence of specific pharmacophores or toxic substructures [ 7 , 40 , 18 , 36 ] . Global Structure. In this case, labels are determined by global structural properties of the graph, such as its diameter or overall connectivity. The label thus reflects a purely structural characteristic of the graph, e.g., metabolic network categorization of different organisms based on global connectivity patterns, such as scale-free vs. random network topologies [ 46 , 28 , 33 ] . To give a more intuitive understanding, we list some real-world applications according to these three types of tasks in the Appendix A . Note that the above three categories are not exclusive, and a graph can be classified by mixture criteria. To simplify the discussion, we focus on the local structure labeling in this work, which is common in real world. 2.2 Energy-Based Framework for Understanding GNN Dynamics Recent work by Di Giovanni et al. [ 12 ] provides a rigorous framework for analyzing GNNs as dynamical systems that minimize a generalized energy functional. This framework reveals that under certain conditions, the training dynamic of GNN will lead to a global frequency-dominated regime, leading to a bipolar convergence of node features. We review this framework briefly. GNN Dynamics as Gradient Flow Consider an undirected and connected graph G=(V,E) , where nodes v=\{v_{1},v_{2},\dots,v_{n}\}\in V have features \{\textbf{f}_{i}\in\mathbb{R}^{d}:v_{i}\in V\} , and edge set denotes E\subset V\times V . The feature matrix \textbf{F}\in\mathbb{R}^{n\times d} consists of \textbf{f}_{i} as its rows. According to [ 3 ] , Message Passing Neural Networks (MPNNs) [ 11 ] update the layer t+1 via: \dot{\textbf{F}}=\textbf{F}(t+1)-\textbf{F}(t)=\sigma(-\textbf{F}(t)\mathbf{\Omega}_{t}+\textbf{A}\textbf{F}(t)\textbf{W}_{t}-\textbf{F}(0)\tilde{\textbf{W}}_{t}) (1) where \Omega_{t} , \textbf{W}_{t} , and \tilde{\textbf{W}}_{t} are learnable matrices performing feature transformations, \sigma is the non-linear activation function, and A is the adjacency matrix which aggregates neighbor information. A gradient flow is a special dynamical system which is defined by an ordinary differential equation \dot{\textbf{F}}(t)=-\nabla\mathcal{E}(\textbf{F}(t)) . The dynamic in Eq. 1 corresponds to a gradient flow of the energy functional: \mathcal{E}_{\mathbf{\theta}}(\mathbf{F})\;=\;\sum_{i}\langle\mathbf{f}_{i},\mathbf{\Omega}\mathbf{f}_{i}\rangle\vphantom{\sum_{i,j}}\;-\;\sum_{i,j}A_{ij}\langle\mathbf{f}_{i},\mathbf{W}\mathbf{f}_{j}\rangle\vphantom{\sum_{i,j}}\;+\;\varphi^{0}(\mathbf{F},\mathbf{F}(0))\vphantom{\sum_{i,j}} (2) given the conditions that the weight matrices \mathbf{\Omega} and \mathbf{W} are symmetric [ 12 ] , and \varphi^{0} is a pre-defined function to calculate the distance between F and the source \textbf{F}(0) . Note that the Dirichlet energy \mathcal{E}^{Dir}(\textbf{F}(t)):=\frac{1}{2}\sum_{(i,j)\in E}\|\nabla\textbf{F}(t)\|^{2} is a special case of \mathcal{E}_{\mathbf{\Theta}} when \mathbf{\Omega}=\textbf{W}=\textbf{I}_{d} and {\varphi^{0}}=0 . Asymptotic Frequency-Dominated Regimes This energy framework reveals that linear GNNs converge to one of two asymptotic behaviors, characterized by the relationship between the graph Laplacian spectrum and the eigenvalues of the weight matrix W . Let \mathbf{\Delta}=\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2} be the normalized Laplacian with ordered eigenvalues 0=\boldsymbol{\lambda}_{0}\leq\dots\leq\boldsymbol{\lambda}_{n-1} and corresponding eigenvectors \{\boldsymbol{\phi}_{0},\dots,\boldsymbol{\phi}_{n-1}\} . We give the symmetric definition for the frequency-dominated dynamics and a theorem to decide the dynamics in a simplified version of MPNN. Definition 1 (Frequency-Dominated Dynamics) . The dynamics of a GNN depends on the limiting behavior of the normalized Dirichlet energy \mathcal{E}^{Dir}(\mathbf{F}(t))/\|\mathbf{F}(t)\|^{2} . If it converges to the eigenvalue \boldsymbol{\lambda}_{0} , we call the dynamic Low-Frequency-Dominant (LFD). Conversely, if it converges to the eigenvalue \boldsymbol{\lambda}_{n-1} , we call it High-Frequency-Dominant (HFD). We refer a lemma to illustrate the condition to decide whether the MPNN is HFD or LFD. Lemma 1 (Theorem 4.3 in [ 12 ] ) . Given a continuous MPNN of the form \dot{\textbf{F}}(t)=\textbf{A}\textbf{F}(t)\textbf{W} , let \boldsymbol{\mu}_{0}\leq\boldsymbol{\mu}_{1}\leq\dots\leq\boldsymbol{\mu}_{d-1} be the eigenvalues of W . If |\boldsymbol{\mu}_{0}|(\boldsymbol{\lambda}_{n-1}-1)>\boldsymbol{\mu}_{d-1}

Read the complete text