Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning

AI summary

Overview

Research area: Graph machine learning — specifically graph neural networks (GNNs) trained on heterophilic graphs, where connected nodes tend to have dissimilar features or labels.

Technical level: Intermediate. The paper assumes familiarity with GNN message passing, adjacency matrices, and homophily/heterophily metrics, but its core idea is a non-learning graph construction that can be understood without deep theoretical background.

Scope: The paper proposes GRAPHITE, a graph transformation that inserts "feature nodes" into a heterophilic graph to directly raise its homophily, together with theoretical guarantees and an evaluation against 27 baselines on six datasets.

What This Paper Is About

Most GNNs assume that connected nodes are similar, so they degrade on heterophilic graphs. Existing fixes focus on redesigning GNN architectures, yet the authors report that 23 recent GNNs still perform worse than a plain multi-layer perceptron (MLP) on the Actor dataset. GRAPHITE takes a different route: instead of changing the model, it changes the graph itself, adding auxiliary nodes so that nodes sharing features become close to each other and can exchange messages more easily.

Key Contributions

1. A new paradigm. The authors frame graph homophily improvement as a non-learning graph transformation problem, and state this is the first work to explicitly transform a graph to directly increase its homophily.
2. The GRAPHITE method. For each discrete feature in the feature set, a "feature node" is created; every graph node holding that feature is connected to it by a "feature edge." Feature nodes act as hubs that let similarly-featured nodes reach each other in two hops, instead of adding direct pairwise shortcut edges.
3. Theoretical guarantees. The paper proves that the transformed graph has higher homophily than the original while growing only modestly in size (|V*| ≤ O(|V|), |E*| ≤ O(|E|)), in contrast to the naive approach whose added edges can reach O(|V|²).
4. Empirical validation and a purpose-built architecture. GRAPHITE is evaluated on four heterophilic and two homophilic datasets, and a GNN architecture tailored to the transformed graph (different edge weights for graph edges, feature edges and self-loops, plus a self-gating aggregation and residual MLPs) is introduced.

Main Findings

• Heterophilic accuracy: GRAPHITE reaches 37.69 ± 1.57 on Actor, 43.06 ± 2.89 on Squirrel-F, 45.08 ± 4.04 on Chameleon-F, and 94.78 ± 0.41 (ROC-AUC) on Minesweeper. It outperforms the best baseline by 4.17%, 5.23%, 5.35% and 3.47% on Actor, Squirrel-F, Chameleon-F and Minesweeper respectively, with reported p-value < 0.1.
• Homophilic accuracy: On Cora GRAPHITE scores 88.23 ± 1.65 and on CiteSeer 76.41 ± 1.57, described as comparable to state-of-the-art methods rather than best.
• Homophily increase: Relative improvements are +179% feature homophily and +2767% adjusted homophily on Actor; +961% and +215% on Squirrel-F; +1739% and +402% on Chameleon-F; +41% and +1023% on Minesweeper.
• The transformation alone helps homophilic GNNs: Applying the transformed graph to off-the-shelf GNNs improves results on both Actor and Minesweeper. On Actor, GCN rises from 30.21 ± 0.86 to 34.83 ± 1.28, GAT from 28.86 ± 0.99 to 32.09 ± 1.35, GraphSAGE from 34.95 ± 1.06 to 35.09 ± 1.06, JKNet from 28.63 ± 0.94 to 35.96 ± 1.40, and GIN from 28.29 ± 1.45 to 33.75 ± 1.83. On Minesweeper, GCN rises from 72.32 ± 0.93 to 75.38 ± 1.56 and GIN from 75.89 ± 2.09 to 87.07 ± 1.71.
• Feature-node features: Averaging, learned embeddings, learned attention and majority voting all perform similarly (e.g., Actor 37.69, 37.46, 37.13, 37.59); averaging is chosen for simplicity and efficiency.
• Runtime: Adding the transformation raises running time from 1.9 to 2.3 minutes on Minesweeper, 1.5 to 2.0 on Actor, 0.7 to 1.1 on Squirrel-F and 0.5 to 0.7 on Chameleon-F, with the reported overhead being proportionally smaller on larger graphs.
• Hyperparameter robustness: On Minesweeper, GRAPHITE ranges from 93.48 to 94.78 across τ values in {0.1, 0.5, 1.0, 1.5, 2.0} and from 93.15 to 94.78 across w_X values in {0.1, 0.25, 0.5, 0.75, 1.0}, against a best baseline of 91.60.
• Why the naive alternative fails: Directly connecting every pair of nodes that share a feature (the "naive homophily booster," NHB) provably increases homophily but can add up to O(|V|²) edges. The paper illustrates this with a graph of only 2,000 nodes, where NHB could add as many as 1,999,000 shortcut edges.

Methodology in Plain English

The starting point is the definition of homophily itself: in a homophilic graph, nodes with similar features are more likely to be connected. So to make a heterophilic graph more homophilic, the authors want to create connections between nodes that share features — but without adding a link between every such pair, which would explode the edge count.

Their solution is indirection. Rather than linking similar nodes to each other, they introduce one extra "feature node" per discrete feature. A graph node is connected to the feature node for each feature it possesses. Two nodes sharing a feature are therefore two hops apart on the transformed graph, while the number of added edges stays proportional to the number of nonzero entries in the feature matrix. The adjacency matrix of the transformed graph is written as a block matrix with the original adjacency in the top-left, the feature matrix X in the top-right, its transpose in the bottom-left, and zeros in the bottom-right.

Feature nodes need their own input features, and the paper defines them as the average of the feature vectors of the graph nodes attached to them. Because the transformed graph mixes two kinds of nodes, the accompanying GNN architecture assigns different weights to graph edges, feature edges and self-loops, and uses a self-gating mechanism (inspired by FAGCN) with a temperature parameter τ to weight messages between nodes, followed by residual MLP layers with GELU activations. In the experiments, datasets are split into 10 random splits each: 48%/32%/20% train/validation/test for Actor, Chameleon-F and Squirrel-F, 60%/20%/20% for Cora and CiteSeer, and the 10 splits provided by the original paper for Minesweeper. Accuracy is reported for all datasets except Minesweeper, which uses ROC-AUC. Homophily is measured with the adjusted homophily metric from Platonov et al. (2024) and with feature homophily from Jin et al. (2022).

Why This Matters

The paper argues that architectural fixes alone have not solved heterophily, since many recent GNNs still lose to an MLP on Actor. If homophily can be raised by a preprocessing step rather than by a new model, that step can be dropped in front of existing GNNs — the ablation results show this working for GCN, GAT, GraphSAGE, JKNet and GIN. It also reframes discrete node features, normally treated as mere input attributes, as structural material for building new graph topology.

Real-world applications discussed in the paper:

• Protein function prediction, where GNNs model biological networks.
• Protein–protein interaction networks, where different protein types interact.
• Neuroscientific analysis of brain networks.
• Social network analysis, plus online marketplace networks where buyers connect with sellers rather than other buyers.

Industry relevance: Any setting where relational data is naturally heterophilic — recommendations, fraud and marketplace graphs, biological and chemical discovery pipelines — can use the transformation as a preprocessing layer without retraining a new architecture from scratch. The reported runtime overhead (0.2 to 0.6 minutes on the datasets tested) and the claim that the overhead shrinks proportionally on larger graphs suggest practical deployment costs are modest.

Future Directions

• The paper's conclusion section is truncated in the provided content, so its explicitly stated future work is not reported here.
• Extending the transformation to settings beyond discrete node features is an open question, since the construction depends on a binary feature matrix X ∈ {0,1}^{|V|×|X|}.
• The evaluation covers six datasets (four heterophilic, two homophilic); whether the homophily guarantees translate into the same accuracy gains on larger or differently structured graphs is not established by the reported experiments.
• Combining the transformation with graph transformers or with heterophilic-specific architectures, rather than only with homophilic GNNs in the ablation, is an untested direction.
• Since the paper reports homophilic accuracy as "comparable" rather than superior, understanding when the added feature nodes dilute homophilic signal remains open.

Target Audience

Researchers and practitioners in graph machine learning who work with heterophilic graphs and want a model-agnostic preprocessing step rather than yet another GNN architecture. It is most useful to readers comfortable with GNN message passing, adjacency matrix formulations and homophily metrics, and to engineers who want to improve existing GNN pipelines with limited changes to their models.

Authors’ abstract

Graph neural networks (GNNs) have emerged as a powerful tool for modeling graph-structured data. However, existing GNNs often struggle with heterophilic graphs, where connected nodes tend to have dissimilar features or labels. While numerous methods have been proposed to address this challenge, they primarily focus on architectural designs without directly targeting the root cause of the heterophily problem. These approaches still perform even worse than the simplest MLPs on challenging heterophilic datasets. For instance, our experiments show that 21 latest GNNs still fall behind the MLP on the Actor dataset. This critical challenge calls for an innovative approach to addressing graph heterophily beyond architectural designs. To bridge this gap, we propose and study a new and unexplored paradigm: directly increasing the graph homophily via a carefully designed graph transformation. In this work, we present a simple yet effective framework called GRAPHITE to address graph heterophily. To the best of our knowledge, this work is the first method that explicitly transforms the graph to directly improve the graph homophily. Stemmed from the exact definition of homophily, our proposed GRAPHITE creates feature nodes to facilitate homophilic message passing between nodes that share similar features. Furthermore, we both theoretically and empirically show that our proposed GRAPHITE significantly increases the homophily of originally heterophilic graphs, with only a slight increase in the graph size. Extensive experiments on challenging datasets demonstrate that our proposed GRAPHITE significantly outperforms state-of-the-art methods on heterophilic graphs while achieving comparable accuracy with state-of-the-art methods on homophilic graphs.