Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

Xiang LiRenyu ZhuYao ChengCaihua ShanSiqiang LuoDongsheng LiWeining Qian

article2022ICML309 citations

Proposes GloGNN and GloGNN++, two scalable graph neural network architectures that overcome the limitations of local heterophily by aggregating information from globally correlated nodes in linear time using a closed-form coefficient matrix with theoretical grouping guarantees.

Listen

Graph-based machine learning models are widely used to analyze connected data across domains such as social networks, biology, and cybersecurity. Standard graph neural networks rely on the assumption of homophily, where connected entities share similar characteristics or labels. However, real-world networks frequently exhibit heterophily, where linked entities are dissimilar while similar entities may be situated far apart. Existing methods that expand local neighborhoods or apply fixed filters struggle to capture distant similar entities and often become computationally prohibitive on large datasets.

The article introduces and evaluates two new graph neural network models, GloGNN and GloGNN++, designed to address this limitation. The primary objective is to demonstrate that aggregating information across all entities globally rather than restricting aggregation to local connections significantly improves learning accuracy and computational scalability on heterophilous networks.

The researchers developed a mathematical framework that characterizes entity relationships across the entire graph using an optimized coefficient matrix incorporating both feature similarities and network structures. To eliminate the standard quadratic or cubic computational bottlenecks associated with global operations, they reformulated the aggregation steps to achieve linear processing time relative to network size. The approach was evaluated against 11 baseline algorithms across 15 benchmark datasets varying in scale, domain, and level of heterophily, ranging from small citation networks to large-scale platforms with millions of entities.

The evaluation produced four key findings. First, GloGNN++ achieved the top overall performance rank across all 15 benchmark datasets, while GloGNN achieved the second-highest average rank, outperforming existing baselines across diverse domains. Second, the proposed framework maintained linear computational scaling, enabling successful execution on datasets with millions of nodes where advanced competitors failed due to out-of-memory errors. Third, the models achieved substantial operational speedups over competitive alternatives, such as operating twice as fast as H2GCN on social graph data and nearly eight times faster than ACM-GCN on web user data. Fourth, mathematical analysis and empirical tests confirmed the grouping effect, verifying that the models consistently assign similar representations to entities sharing equivalent features and structures regardless of network distance.

These findings indicate that network-based learning systems do not need to rely on restrictive local neighborhood assumptions. By efficiently incorporating global graph context, organizations can deploy high-performing graph models in complex domains such as fraud detection, spam identification, and multi-relational social analysis without incurring prohibitive compute or memory costs. This directly addresses the historical trade-off between structural expressiveness and scalability.

Organizations implementing graph representation systems for non-homophilous or large-scale data should transition from purely local message-passing architectures to global aggregation frameworks like GloGNN and GloGNN++. While the models demonstrated robust empirical gains and theoretical guarantees across all tested benchmarks, practitioners should conduct validation on their specific domain topologies, tune key structural weighting hyper-parameters, and assess feature sparsity constraints prior to production deployment.

East China Normal University Microsoft Nanyang Technological University closed-form solution graph neural networks intermediate node heterophilous graphs graph neural networks global homophily

arXiv: 2205.07308

Paper: Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs, Jiong Zhu et al. (2020). It identifies the breakdown of standard graph neural networks under heterophily and proposes architectural designs like multi-hop neighborhood aggregation that GloGNN seeks to advance.
Paper: Geom-GCN: Geometric Graph Convolutional Networks, Hongbin Pei et al. (2020). It introduces continuous geometric mapping and structural neighborhoods to handle disassortative graphs, establishing key baselines and concepts for learning under heterophily.
Paper: Predict then Propagate: Graph Neural Networks meet Personalized PageRank, Johannes Gasteiger et al. (2019). It separates neural feature transformations from global propagation via personalized PageRank, motivating GloGNN's use of broader graph-level context.
Paper: Simple and Deep Graph Convolutional Networks, Ming Chen et al. (2020). It provides deep GCN formulations using residual connections to combat over-smoothing, a fundamental challenge when expanding neighborhood aggregation across graphs.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). It introduces the localized first-order spectral convolution framework that serves as the baseline architecture generalized by GloGNN.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). It details attention-based aggregation mechanisms for weighting neighbor importance, which GloGNN extends to global, signed correlation matrices.

Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). It provides a standardized, parameter-controlled benchmarking framework to evaluate the empirical advances of modern expressive graph architectures like GloGNN.
Paper: Label-free Node Classification on Graphs with Large Language Models (LLMs), Zhikai Chen et al. (2024). It builds on modern node classification pipelines by incorporating large language models for active label generation before applying expressive GNN architectures.

Cover for Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

Abstract

We investigate graph neural networks on graphs with heterophily. Some existing methods amplify a node’s neighborhood with multi-hop neighbors to include more nodes with homophily. However, it is a significant challenge to set personalized neighborhood sizes for different nodes. Further, for other homophilous nodes excluded in the neighborhood, they are ignored for information aggregation. To address these problems, we propose two models GloGNN and GloGNN++, which generate a node’s embedding by aggregating information from global nodes in the graph. In each layer, both models learn a coefficient matrix to capture the correlations between nodes, based on which neighborhood aggregation is performed. The coefficient matrix allows signed values and is derived from an optimization problem that has a closed-form solution. We further accelerate neighborhood aggregation and derive a linear time complexity. We theoretically explain the models’ effectiveness by proving that both the coefficient matrix and the generated node embedding matrix have the desired grouping effect. We conduct extensive experiments to compare our models against 11 other competitors on 15 benchmark datasets in a wide range of domains, scales and graph heterophilies. Experimental results show that our methods achieve superior performance and are also very efficient.

Topics

closed-form solution graph neural networks intermediate node multihop optimization optimization problems bipartite graphs directed graphs weighted graph destination nodes

Keywords

heterophilous graphs graph neural networks global homophily node neighborhood aggregation node classification homophilous neighbors multi-hop neighbors local graph structures

1. Introduction
2. Related Work
3. Preliminaries
4. Algorithm
4.1. Coefficient matrix
4.2. Aggregation acceleration
4.3. Grouping effect
4.4. GloGNN++
4.5. Discussion
5. Experiments
5.1. Datasets
5.2. Algorithms for comparison
5.3. Performance results
5.4. Efficiency study
5.5. Grouping effect
5.6. Global homophily
6. Conclusions
Acknowledgements
References
A. Pseudocodes
B. Datasets
C. Aggregation acceleration
D. Proof
E. Ablation study
F. Experimental setup

Knowls

Knowl 1 — GloGNN Framework and Closed-Form Global Coefficient Matrix
model/method
GloGNN is a graph neural network designed for graphs with heterophily (where linked nodes frequently possess dissimilar features or distinct class labels). Rather than aggregating only from local or multi-hop neighbors, GloGNN characterizes each node using all nodes in the graph via a learned coefficient matrix $Z^{(l)} \in \mathbb{R}^{n \times n}$ .

Given an undirected graph $G=(V, E)$ with $n$ nodes, initial node feature matrix $X \in \mathbb{R}^{n \times d}$ , adjacency matrix $A \in \mathbb{R}^{n \times n}$ , and $c$ classification labels, GloGNN first decouples feature transformation and neighborhood aggregation to prevent over-smoothing. Initial node representations $H^{(0)} \in \mathbb{R}^{n \times c}$ are computed via multilayer perceptrons (MLPs): $H_X^{(0)} = \text{MLP}_1(X), \quad H_A^{(0)} = \text{MLP}_2(A)$ $H^{(0)} = (1 - \alpha) H_X^{(0)} + \alpha H_A^{(0)}$ where $\alpha \in [0, 1]$ balances feature and topological connectivity information.

In the $l$ -th layer with node embedding matrix $H^{(l)} \in \mathbb{R}^{n \times c}$ , GloGNN determines the signed coefficient matrix $Z^{(l)} \in \mathbb{R}^{n \times n}$ by solving the optimization problem: $\min_{Z^{(l)}} \left\| H^{(l)} - (1 - \gamma) Z^{(l)} H^{(l)} - \gamma H^{(0)} \right\|_F^2 + \beta_1 \|Z^{(l)}\|_F^2 + \beta_2 \left\| Z^{(l)} - \sum_{k=1}^K \lambda_k \hat{A}^k \right\|_F^2$ where $\gamma \in [0, 1]$ governs a skip connection to the initial embedding $H^{(0)}$ , $\beta_1, \beta_2 > 0$ are regularization hyperparameters, $K$ is the maximum hop count, $\lambda_k$ is a learnable importance weight for $k$ -hop connectivity, and $\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ is the normalized adjacency matrix with self-loops ( $ilde{A} = A + I_n$ and $ilde{D}_{ii} = \sum_{j=1}^n \tilde{A}_{ij}$ ).

The optimization problem admits a closed-form solution $Z^{(l)*}$ : $Z^{(l)*} = \left[ (1 - \gamma) H^{(l)} (H^{(l)})^T + \beta_2 \sum_{k=1}^K \lambda_k \hat{A}^k - \gamma (1 - \gamma) H^{(0)} (H^{(l)})^T \right] \left[ (1 - \gamma)^2 H^{(l)} (H^{(l)})^T + (\beta_1 + \beta_2) I_n \right]^{-1}$

The node representations are then updated by: $H^{(l+1)} = (1 - \gamma) Z^{(l)*} H^{(l)} + \gamma H^{(0)}$ Because $Z^{(l)*}$ can take negative and positive values, this aggregation implicitly combines low-pass and high-pass filtering.
Knowl 2 — GloGNN++ Feature Attention and Coefficient Formulation
model/method
GloGNN++ extends the GloGNN framework by introducing dimension-wise ("horizontal") attention across hidden feature channels, complementing the node-wise ("longitudinal") attention captured by the coefficient matrix $Z^{(l)}$ . This addresses label imbalance and varying feature channel importance in node classification.

Let $\Sigma \in \mathbb{R}^{c \times c}$ be a diagonal weight matrix where $\Sigma_{ii}$ represents the learned importance factor for the $i$ -th dimension of the hidden representation matrix $H^{(l)} \in \mathbb{R}^{n \times c}$ , where $n$ is the number of nodes and $c$ is the number of classes. In each layer $l$ , the coefficient matrix $Z^{(l)} \in \mathbb{R}^{n \times n}$ is obtained by solving: $\min_{Z^{(l)}} \left\| H^{(l)} - (1 - \gamma) Z^{(l)} H^{(l)} \Sigma - \gamma H^{(0)} \right\|_F^2 + \beta_1 \|Z^{(l)}\|_F^2 + \beta_2 \left\| Z^{(l)} - \sum_{k=1}^K \lambda_k \hat{A}^k \right\|_F^2$ where $H^{(0)} \in \mathbb{R}^{n \times c}$ is the initial node embedding, $\gamma \in [0, 1]$ is the skip-connection weight, $\beta_1, \beta_2 > 0$ are regularizer weights, $\hat{A}$ is the normalized graph adjacency matrix with self-loops, and $\lambda_k$ is the learnable weight for the $k$ -hop normalized adjacency $\hat{A}^k$ up to maximum hop $K$ .

The closed-form optimal coefficient matrix for GloGNN++ is: $Z^{(l)*} = \left[ (1 - \gamma) H^{(l)} \Sigma (H^{(l)})^T + \beta_2 \sum_{k=1}^K \lambda_k \hat{A}^k - \gamma (1 - \gamma) H^{(0)} \Sigma (H^{(l)})^T \right] \left[ (1 - \gamma)^2 H^{(l)} \Sigma \Sigma (H^{(l)})^T + (\beta_1 + \beta_2) I_n \right]^{-1}$

Node embeddings are subsequently updated using $H^{(l+1)} = (1 - \gamma) Z^{(l)*} H^{(l)} + \gamma H^{(0)}$ via linear-time reordering.
Knowl 3 — Accelerated Linear-Time Global Aggregation via Woodbury Identity
model/method
Directly computing the closed-form global coefficient matrix $Z^{(l)*} \in \mathbb{R}^{n \times n}$ and evaluating the global neighborhood aggregation $H^{(l+1)} = (1 - \gamma) Z^{(l)*} H^{(l)} + \gamma H^{(0)}$ requires $O(n^3)$ operations due to matrix inversion of an $n \times n$ matrix and $O(n^2 c)$ for matrix multiplication, which is computationally prohibitive for large graphs.

Applying the Woodbury matrix identity to the inversion term $[(1 - \gamma)^2 H^{(l)} (H^{(l)})^T + (\beta_1 + \beta_2) I_n]^{-1}$ yields: $\left[ (1 - \gamma)^2 H^{(l)} (H^{(l)})^T + (\beta_1 + \beta_2) I_n \right]^{-1} = \frac{1}{\beta_1 + \beta_2} I_n - \frac{1}{(\beta_1 + \beta_2)^2} H^{(l)} \left[ \frac{1}{(1 - \gamma)^2} I_c + \frac{1}{\beta_1 + \beta_2} (H^{(l)})^T H^{(l)} \right]^{-1} (H^{(l)})^T$ where $I_n \in \mathbb{R}^{n \times n}$ and $I_c \in \mathbb{R}^{c \times c}$ are identity matrices, and $c$ is the number of classes.

Substituting this identity into the aggregation formula reformulates the layer update as: $H^{(l+1)} = (1 - \gamma) H^{(l)} (H^{(l)})^T Q^{(l+1)} + \beta_2 \sum_{k=1}^K \lambda_k \hat{A}^k Q^{(l+1)} - \gamma (1 - \gamma) H^{(0)} (H^{(l)})^T Q^{(l+1)} + \gamma H^{(0)}$ where $Q^{(l+1)} \in \mathbb{R}^{n \times c}$ is defined as: $Q^{(l+1)} = \frac{1 - \gamma}{\beta_1 + \beta_2} H^{(l)} - \frac{1 - \gamma}{(\beta_1 + \beta_2)^2} H^{(l)} \left[ \frac{1}{(1 - \gamma)^2} I_c + \frac{1}{\beta_1 + \beta_2} (H^{(l)})^T H^{(l)} \right]^{-1} (H^{(l)})^T H^{(l)}$

Computation is accelerated by reordering matrix multiplications:
1. Calculating $Q^{(l+1)}$ requires inverting a $c \times c$ matrix in $O(c^3)$ time and computing multiplications right-to-left in $O(n c^2)$ time.
2. The terms $H^{(l)} ((H^{(l)})^T Q^{(l+1)})$ and $H^{(0)} ((H^{(l)})^T Q^{(l+1)})$ are evaluated right-to-left in $O(n c^2)$ time.
3. The term $\sum_{k=1}^K \lambda_k \hat{A}^k Q^{(l+1)}$ is evaluated sequentially by computing $\hat{A} Q^{(l+1)}$ , then $\hat{A}(\hat{A} Q^{(l+1)})$ , taking $O(k_1 c n)$ per hop where $k_1$ is the average number of non-zero entries per row of the sparse normalized adjacency $\hat{A}$ .
Since $c \ll n$ , the total time complexity per layer is reduced to $O(k_2 n)$ , which is strictly linear in the number of nodes $n$ .
Knowl 4 — Grouping Effect of GloGNN Coefficient and Representation Matrices
theoretical result
Let $V = \{v_1, \dots, v_n\}$ be the set of nodes, $x_i \in \mathbb{R}^d$ denote the feature vector of node $v_i$ , and $\hat{a}_i^k \in \mathbb{R}^n$ denote the $i$ -th row of the $k$ -hop normalized adjacency matrix $\hat{A}^k$ (representing the $k$ -hop reachability of $v_i$ ). Let $v_i \to v_j$ denote the asymptotic condition where both feature and structural differences vanish: $\|x_i - x_j\|_2 \to 0$ and $\|\hat{a}_i^k - \hat{a}_j^k\|_2 \to 0$ for all $k \in \{1, \dots, K\}$ .

A matrix $Z \in \mathbb{R}^{n \times n}$ satisfies the grouping effect if: $v_i \to v_j \implies |Z_{ip} - Z_{jp}| \to 0 \quad \text{for all } 1 \le p \le n$

Under the GloGNN framework, the following properties hold:
1. The optimal coefficient matrix $Z^{(l)*}$ satisfies the grouping effect: for any node $v_p$ , $|Z^{(l)*}_{ip} - Z^{(l)*}_{jp}| \to 0$ as $v_i \to v_j$ .
2. The transpose $(Z^{(l)*})^T$ satisfies the grouping effect: for any node $v_p$ , $|Z^{(l)*}_{pi} - Z^{(l)*}_{pj}| \to 0$ as $v_i \to v_j$ .
3. The updated embedding matrix $H^{(l+1)}$ satisfies the grouping effect: $\|h^{(l+1)}_i - h^{(l+1)}_j\|_2 \to 0$ as $v_i \to v_j$ .
Consequently, any two nodes with similar features and similar multi-hop neighborhood topologies receive nearly identical characterization coefficients from and toward all other graph nodes, and converge to similar embedding vectors, irrespective of their geodesic distance in the graph topology.
Knowl 5 — GloGNN Node Classification Algorithm
algorithm
GloGNN performs node classification on an undirected graph $G=(V,E)$ where $V = \mathcal{L} \cup \mathcal{U}$ , with $\mathcal{L}$ denoting labeled nodes and $\mathcal{U}$ denoting unlabeled nodes. It decouples feature extraction from global message aggregation and updates node representations in linear time per layer.
Input: Graph $G = (V, E)$ with adjacency matrix $A \in \mathbb{R}^{n \times n}$ , node features $X \in \mathbb{R}^{n \times d}$ , number of layers $L$ , number of classes $c$ , labeled set $\mathcal{L}$ with one-hot labels $Y_\mathcal{L}$ , hyperparameters $\alpha, \gamma, \beta_1, \beta_2, K$
Output: Predicted labels $Y_\mathcal{U}$ for unlabeled nodes
$H_X^{(0)} \leftarrow \text{MLP}_1(X)$
$H_A^{(0)} \leftarrow \text{MLP}_2(A)$
$H^{(0)} \leftarrow (1 - \alpha) H_X^{(0)} + \alpha H_A^{(0)}$
for $l \leftarrow 0$ to $L - 1$ do
     $M \leftarrow \left( \frac{1}{(1 - \gamma)^2} I_c + \frac{1}{\beta_1 + \beta_2} (H^{(l)})^T H^{(l)} \right)^{-1}$
     $Q^{(l+1)} \leftarrow \frac{1 - \gamma}{\beta_1 + \beta_2} H^{(l)} - \frac{1 - \gamma}{(\beta_1 + \beta_2)^2} H^{(l)} \left( M ( (H^{(l)})^T H^{(l)} ) \right)$
     $T_1 \leftarrow (1 - \gamma) H^{(l)} ( (H^{(l)})^T Q^{(l+1)} )$
     $T_2 \leftarrow \beta_2 \sum_{k=1}^K \lambda_k \hat{A}^k Q^{(l+1)}$
     $T_3 \leftarrow \gamma (1 - \gamma) H^{(0)} ( (H^{(l)})^T Q^{(l+1)} )$
     $H^{(l+1)} \leftarrow T_1 + T_2 - T_3 + \gamma H^{(0)}$
end for
$\hat{Y} \leftarrow \text{Softmax}(H^{(L)})$
Update model parameters by minimizing cross-entropy loss over $\mathcal{L}$
return $Y_\mathcal{U} \leftarrow \arg\max \hat{Y}_\mathcal{U}$
The time complexity of this algorithm is $O(L \cdot (k_1 c n + n c^2 + c^3))$ per epoch, where $k_1$ is the average degree of the graph, $n = |V|$ is the number of nodes, and $c$ is the number of classes.

Knowl 6 — Node Classification Performance on Small-Scale Benchmark Graphs

data/table

The table compares classification accuracy (%) across 9 small-scale benchmark datasets (mean $\pm$ standard deviation over 10 splits). Datasets are characterized by edge homophily (the fraction of edges connecting nodes with the same label): WebKB graphs (Texas, Wisconsin, Cornell), Actor, and Wikipedia graphs (Squirrel, Chameleon) exhibit high heterophily (edge homophily between 0.11 and 0.30), while Cora, Citeseer, and Pubmed exhibit high homophily (0.74 to 0.81).

Dataset	Texas	Wisconsin	Cornell	Actor	Squirrel	Chameleon	Cora	Citeseer	Pubmed	Avg. Rank
Edge Hom.	0.11	0.21	0.30	0.22	0.22	0.23	0.81	0.74	0.80	-
MLP	80.81 $\pm$ 4.75	85.29 $\pm$ 3.31	81.89 $\pm$ 6.40	36.53 $\pm$ 0.70	28.77 $\pm$ 1.56	46.21 $\pm$ 2.99	75.69 $\pm$ 2.00	74.02 $\pm$ 1.90	87.16 $\pm$ 0.37	9.72
GCN	55.14 $\pm$ 5.16	51.76 $\pm$ 3.06	60.54 $\pm$ 5.30	27.32 $\pm$ 1.10	53.43 $\pm$ 2.01	64.82 $\pm$ 2.24	86.98 $\pm$ 1.27	76.50 $\pm$ 1.36	88.42 $\pm$ 0.50	10.22
GAT	52.16 $\pm$ 6.63	49.41 $\pm$ 4.09	61.89 $\pm$ 5.05	27.44 $\pm$ 0.89	40.72 $\pm$ 1.55	60.26 $\pm$ 2.50	87.30 $\pm$ 1.10	76.55 $\pm$ 1.23	86.33 $\pm$ 0.48	11.11
MixHop	77.84 $\pm$ 7.73	75.88 $\pm$ 4.90	73.51 $\pm$ 6.34	32.22 $\pm$ 2.34	43.80 $\pm$ 1.48	60.50 $\pm$ 2.53	87.61 $\pm$ 0.85	76.26 $\pm$ 1.33	85.31 $\pm$ 0.61	10.11
GCNII	77.57 $\pm$ 3.83	80.39 $\pm$ 3.40	77.86 $\pm$ 3.79	37.44 $\pm$ 1.30	38.47 $\pm$ 1.58	63.86 $\pm$ 3.04	88.37 $\pm$ 1.25	77.33 $\pm$ 1.48	90.15 $\pm$ 0.43	5.89
H2GCN	84.86 $\pm$ 7.23	87.65 $\pm$ 4.98	82.70 $\pm$ 5.28	35.70 $\pm$ 1.00	36.48 $\pm$ 1.86	60.11 $\pm$ 2.15	87.87 $\pm$ 1.20	77.11 $\pm$ 1.57	89.49 $\pm$ 0.38	6.72
WRGAT	83.62 $\pm$ 5.50	86.98 $\pm$ 3.78	81.62 $\pm$ 3.90	36.53 $\pm$ 0.77	48.85 $\pm$ 0.78	65.24 $\pm$ 0.87	88.20 $\pm$ 2.26	76.81 $\pm$ 1.89	88.52 $\pm$ 0.92	6.17
GPR-GNN	78.38 $\pm$ 4.36	82.94 $\pm$ 4.21	80.27 $\pm$ 8.11	34.63 $\pm$ 1.22	31.61 $\pm$ 1.24	46.58 $\pm$ 1.71	87.95 $\pm$ 1.18	77.13 $\pm$ 1.67	87.54 $\pm$ 0.38	8.83
GGCN	84.86 $\pm$ 4.55	86.86 $\pm$ 3.29	85.68 $\pm$ 6.63	37.54 $\pm$ 1.56	55.17 $\pm$ 1.58	71.14 $\pm$ 1.84	87.95 $\pm$ 1.05	77.14 $\pm$ 1.45	89.15 $\pm$ 0.37	3.89
ACM-GCN	87.84 $\pm$ 4.40	88.43 $\pm$ 3.22	85.14 $\pm$ 6.07	36.28 $\pm$ 1.09	54.40 $\pm$ 1.88	66.93 $\pm$ 1.85	87.91 $\pm$ 0.95	77.32 $\pm$ 1.70	90.00 $\pm$ 0.52	3.78
LINKX	74.60 $\pm$ 8.37	75.49 $\pm$ 5.72	77.84 $\pm$ 5.81	36.10 $\pm$ 1.55	61.81 $\pm$ 1.80	68.42 $\pm$ 1.38	84.64 $\pm$ 1.13	73.19 $\pm$ 0.99	87.86 $\pm$ 0.77	8.78
GloGNN	84.32 $\pm$ 4.15	87.06 $\pm$ 3.53	83.51 $\pm$ 4.26	37.35 $\pm$ 1.30	57.54 $\pm$ 1.39	69.78 $\pm$ 2.42	88.31 $\pm$ 1.13	77.41 $\pm$ 1.65	89.62 $\pm$ 0.35	3.22
GloGNN++	84.05 $\pm$ 4.90	88.04 $\pm$ 3.22	85.95 $\pm$ 5.10	37.70 $\pm$ 1.40	57.88 $\pm$ 1.76	71.21 $\pm$ 1.84	88.33 $\pm$ 1.09	77.22 $\pm$ 1.78	89.24 $\pm$ 0.39	2.56

GloGNN++ achieves the lowest average rank across all datasets (2.56), and GloGNN achieves the second-lowest average rank (3.22). On heterophilous datasets (e.g., Chameleon and Actor), GloGNN and GloGNN++ outperform standard baselines like GCN and GAT by large margins, while remaining competitive on homophilous citation datasets (Cora, Citeseer, Pubmed).

Knowl 7 — Scalability and Performance on Large-Scale Non-Homophilous Benchmarks

data/table

The table compares performance (accuracy % or AUC % on genius, mean $\pm$ standard deviation over 5 trials) across 6 large-scale benchmark datasets ranging from 41K to 2.9M nodes. Several heterophily-specific baselines (H2GCN, WRGAT, GGCN) fail to execute on large datasets due to out-of-memory (OOM) errors.

Dataset	Penn94	pokec	arXiv-year	snap-patents	genius	twitch-gamers	Avg. Rank
Edge Hom.	0.47	0.44	0.22	0.07	0.61	0.54	-
#Nodes	41,554	1,632,803	169,343	2,923,922	421,961	168,114	-
#Edges	1,362,229	30,622,564	1,166,243	13,975,788	984,979	6,797,557	-
#Features	5	65	128	269	12	7	-
#Classes	2	2	5	5	2	2	-
MLP	73.61 $\pm$ 0.40	62.37 $\pm$ 0.02	36.70 $\pm$ 0.21	31.34 $\pm$ 0.05	86.68 $\pm$ 0.09	60.92 $\pm$ 0.07	10.00
GCN	82.47 $\pm$ 0.27	75.45 $\pm$ 0.17	46.02 $\pm$ 0.26	45.65 $\pm$ 0.04	87.42 $\pm$ 0.37	62.18 $\pm$ 0.26	7.00
GAT	81.53 $\pm$ 0.55	71.77 $\pm$ 6.18	46.05 $\pm$ 0.51	45.37 $\pm$ 0.44	55.80 $\pm$ 0.87	59.89 $\pm$ 4.12	8.50
MixHop	83.47 $\pm$ 0.71	81.07 $\pm$ 0.16	51.81 $\pm$ 0.17	52.16 $\pm$ 0.09	90.58 $\pm$ 0.16	65.64 $\pm$ 0.27	4.17
GCNII	82.92 $\pm$ 0.59	78.94 $\pm$ 0.11	47.21 $\pm$ 0.28	37.88 $\pm$ 0.69	90.24 $\pm$ 0.09	63.39 $\pm$ 0.61	6.00
H2GCN	81.31 $\pm$ 0.60	OOM	49.09 $\pm$ 0.10	OOM	OOM	OOM	10.50
WRGAT	74.32 $\pm$ 0.53	OOM	OOM	OOM	OOM	OOM	11.92
GPR-GNN	81.38 $\pm$ 0.16	78.83 $\pm$ 0.05	45.07 $\pm$ 0.21	40.19 $\pm$ 0.03	90.05 $\pm$ 0.31	61.89 $\pm$ 0.29	7.83
GGCN	OOM	OOM	OOM	OOM	OOM	OOM	12.25
ACM-GCN	82.52 $\pm$ 0.96	63.81 $\pm$ 5.20	47.37 $\pm$ 0.59	55.14 $\pm$ 0.16	80.33 $\pm$ 3.91	62.01 $\pm$ 0.73	6.83
LINKX	84.71 $\pm$ 0.52	82.04 $\pm$ 0.07	56.00 $\pm$ 1.34	61.95 $\pm$ 0.12	90.77 $\pm$ 0.27	66.06 $\pm$ 0.19	2.50
GloGNN	85.57 $\pm$ 0.35	83.00 $\pm$ 0.10	54.68 $\pm$ 0.34	62.09 $\pm$ 0.27	90.66 $\pm$ 0.11	66.19 $\pm$ 0.29	2.17
GloGNN++	85.74 $\pm$ 0.42	83.05 $\pm$ 0.07	54.79 $\pm$ 0.25	62.03 $\pm$ 0.21	90.91 $\pm$ 0.13	66.34 $\pm$ 0.29	1.33

GloGNN++ achieves the lowest average rank (1.33) across large-scale datasets, followed by GloGNN (2.17). GloGNN++ trains approximately $8\times$ faster than ACM-GCN on genius and $2\times$ faster than H2GCN on Penn94 while successfully scaling to graphs with millions of nodes.

Knowl 8 — Ablation Study on Graph Signals, Feature Transformation, and Local Regularization
empirical result
An ablation study evaluating the individual components of GloGNN examines three specific variants:
1. GloGNN-na (No Adjacency Embedding): Sets $\alpha = 0$ , constructing the initial representation solely from node features ( $H^{(0)} = H_X^{(0)}$ ).
2. GloGNN-nf (No Feature Embedding): Sets $\alpha = 1$ , constructing the initial representation solely from graph adjacency structure ( $H^{(0)} = H_A^{(0)}$ ).
3. GloGNN-nl (No Local Regularization): Removes the multi-hop adjacency regularization term by setting $\beta_2 = 0$ , optimizing the coefficient matrix $Z^{(l)}$ without the penalty term $\beta_2 \|Z^{(l)} - \sum_{k=1}^K \lambda_k \hat{A}^k\|_F^2$ .
Experimental findings across the 15 benchmark datasets demonstrate:
- GloGNN significantly outperforms GloGNN-na and GloGNN-nf on datasets where both modalities provide complementary signals, showing the necessity of adaptively learning $\alpha$ to fuse feature and connectivity spaces.
- GloGNN consistently outperforms GloGNN-nl. Without the multi-hop topology regularization constraint ( $\beta_2 = 0$ ), the model fails to capture homophilous node pairs that share structural roles but have dissimilar raw features, confirming the importance of local structural regularizers in guiding global attention.
Knowl 9 — Global Homophily Distribution Across Distant Neighborhoods
empirical result
On heterophilous graphs (including Texas, Wisconsin, Cornell, Actor, Squirrel, and Chameleon), analysis of graph topology and GloGNN's learned optimal coefficient matrix $Z^*$ establishes two key observations:
1. For each node in these datasets, the average number of 1-hop adjacent neighbors in the same class is substantially smaller than the count of homophilous neighbors located in multi-hop neighborhoods (2-hop to 6-hop) and distant regions (>6 hops).
2. The number of positive entries in the learned coefficient matrix ( $Z^*_{ij} > 0$ ) closely tracks the true distribution of same-class nodes across both local and multi-hop neighborhoods.
This validates that GloGNN accurately identifies and assigns positive weights to globally distributed homophilous nodes beyond local graph neighborhoods.

Coverage note — None was omitted; all primary contributions, models (GloGNN and GloGNN++), acceleration equations, theoretical grouping effects, algorithm pseudocode, and benchmark results are covered.

References

1.Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Galstyan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, pp. 21–29. PMLR, 2019.
2.Bo, D., Wang, X., Shi, C., and Shen, H. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00797, 2021.
3.Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203, 2013.
4.Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Y. Simple and deep graph convolutional networks. In ICML, pp. 1725–1735. PMLR, 2020.
5.Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
6.Ciotti, V., Bonaventura, M., Nicosia, V., Panzarasa, P., and Latora, V. Homophily and missing links in citation networks. EPJ Data Science, 5:1–14, 2016.
7.Dai, H., Li, H., Tian, T., Huang, X., Wang, L., Zhu, J., and Song, L. Adversarial attack on graph structured data. In ICML, pp. 1115–1124. PMLR, 2018.
8.Defferrard, M., Bresson, X., and Vandergheynst, P. Convolutional neural networks on graphs with fast localized spectral filtering. NeurIPS, 29:3844–3852, 2016.
9.Dong, Y., Ding, K., Jalaian, B., Ji, S., and Li, J. Graph neural networks with adaptive frequency response filter. arXiv preprint arXiv:2104.12840, 2021.
10.Gerber, E. R., Henry, A. D., and Lubell, M. Political homophily and collaboration in regional planning networks. American Journal of Political Science, 57(3):598–610, 2013.
11.Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs. In NeurIPS, pp. 1025–1035, 2017.
12.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
13.Klicpera, J., Bojchevski, A., and Günnemann, S. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
14.Li, X., Kao, B., Shan, C., Yin, D., and Ester, M. Cast: A correlation-based adaptive spectral clustering algorithm on multi-scale data. In KDD, pp. 439–449, 2020.
15.Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. NeurIPS, 34, 2021.
16.Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., and Ma, Y. Robust recovery of subspace structures by low-rank representation. TPAMI, 35(1):171–184, 2012.
17.Liu, M., Gao, H., and Ji, S. Towards deeper graph neural networks. In KDD, pp. 338–348, 2020.
18.Liu, M., Wang, Z., and Ji, S. Non-local graph neural networks. TPAMI, 2021.
19.Lu, C.-Y., Min, H., Zhao, Z.-Q., Zhu, L., Huang, D.-S., and Yan, S. Robust and efficient subspace segmentation via least squares regression. In ECCV, pp. 347–360, 2012.
20.Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup, D. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.05641, 2021.
21.Max, A. W. Inverting modified matrices. In Memorandum Rept. 42, Statistical Research Group, pp. 4. Princeton Univ., 1950.
22.McPherson, M., Smith-Lovin, L., and Cook, J. M. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415–444, 2001.
23.Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
24.Rong, Y., Huang, W., Xu, T., and Huang, J. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903, 2019.
25.Shan, C., Shen, Y., Zhang, Y., Li, X., and Li, D. Reinforcement learning enhanced explainer for graph neural networks. NeurIPS, 34, 2021.
26.Suresh, S., Budde, V., Neville, J., Li, P., and Ma, J. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD, pp. 1541–1551, 2021.
27.Tang, J., Sun, J., Wang, C., and Yang, Z. Social influence analysis in large-scale networks. In KDD, pp. 807–816, 2009.
28.Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
29.Vu, M. N. and Thai, M. T. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. arXiv preprint arXiv:2010.05788, 2020.
30.Yan, Y., Hashemi, M., Swersky, K., Yang, Y., and Koutra, D. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
31.Yang, Y., Liu, T., Wang, Y., Zhou, J., Gan, Q., Wei, Z., Zhang, Z., Huang, Z., and Wipf, D. Graph neural networks inspired by classical iterative algorithms. arXiv preprint arXiv:2103.06064, 2021.
32.Zhao, L. and Akoglu, L. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv:1909.12223, 2019.
33.Zhu, D., Zhang, Z., Cui, P., and Zhu, W. Robust graph convolutional networks against adversarial attacks. In KDD, pp. 1399–1407, 2019.
34.Zhu, J., Rossi, R. A., Rao, A., Mai, T., Lipka, N., Ahmed, N. K., and Koutra, D. Graph neural networks with heterophily. arXiv preprint arXiv:2009.13566, 2020a.
35.Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. arXiv preprint arXiv:2006.11468, 2020b.

Citation

MLA

Li, X., et al. “Finding Global Homophily in Graph Neural Networks When Meeting Heterophily”. International Conference on Machine Learning, vol. 162, 2022, pp. 13242–56, https://proceedings.mlr.press/v162/li22ad.html.

APA

Li, X., Zhu, R., Cheng, Y., Shan, C., Luo, S., Li, D., & Qian, W. (2022). Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. International Conference on Machine Learning, 162, 13242–13256. https://proceedings.mlr.press/v162/li22ad.html

Chicago

Li, X., R. Zhu, Y. Cheng, et al. 2022. “Finding Global Homophily in Graph Neural Networks When Meeting Heterophily”. International Conference on Machine Learning 162: 13242–56. https://proceedings.mlr.press/v162/li22ad.html.

Harvard

Li, X. et al. (2022) “Finding Global Homophily in Graph Neural Networks When Meeting Heterophily”, International Conference on Machine Learning. PMLR, pp. 13242–13256. Available at: https://proceedings.mlr.press/v162/li22ad.html.

Vancouver

1. Li X, Zhu R, Cheng Y, Shan C, Luo S, Li D, Qian W (2022) Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. In: International Conference on Machine Learning. PMLR, pp 13242–13256

BibTeX

@InProceedings{pmlr-v162-li22ad,
  title = 	 {Finding Global Homophily in Graph Neural Networks When Meeting Heterophily},
  author =       {Li, Xiang and Zhu, Renyu and Cheng, Yao and Shan, Caihua and Luo, Siqiang and Li, Dongsheng and Qian, Weining},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {13242--13256},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/li22ad/li22ad.pdf},
  url = 	 {https://proceedings.mlr.press/v162/li22ad.html},
  abstract = 	 {We investigate graph neural networks on graphs with heterophily. Some existing methods amplify a node’s neighborhood with multi-hop neighbors to include more nodes with homophily. However, it is a significant challenge to set personalized neighborhood sizes for different nodes. Further, for other homophilous nodes excluded in the neighborhood, they are ignored for information aggregation. To address these problems, we propose two models GloGNN and GloGNN++, which generate a node’s embedding by aggregating information from global nodes in the graph. In each layer, both models learn a coefficient matrix to capture the correlations between nodes, based on which neighborhood aggregation is performed. The coefficient matrix allows signed values and is derived from an optimization problem that has a closed-form solution. We further accelerate neighborhood aggregation and derive a linear time complexity. We theoretically explain the models’ effectiveness by proving that both the coefficient matrix and the generated node embedding matrix have the desired grouping effect. We conduct extensive experiments to compare our models against 11 other competitors on 15 benchmark datasets in a wide range of domains, scales and graph heterophilies. Experimental results show that our methods achieve superior performance and are also very efficient.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Finding Global Homophily in Graph Neural Networks When Meeting Heterophily

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — GloGNN Framework and Closed-Form Global Coefficient Matrix

Knowl 2 — GloGNN++ Feature Attention and Coefficient Formulation

Knowl 3 — Accelerated Linear-Time Global Aggregation via Woodbury Identity

Knowl 4 — Grouping Effect of GloGNN Coefficient and Representation Matrices

Knowl 5 — GloGNN Node Classification Algorithm