🤖 machine learning

Graph Neural Network leveraging Higher-order Class Label Connectivity for Heterophilous Graphs

This paper proposes the Label Context Classifier (LCC), a novel method that captures higher-order class label connectivity through four types of walks in directed heterophilous graphs, which can be adaptively integrated with existing GNNs to significantly outperform state-of-the-art node classification methods.

Original authors: Takuto Takahashi, Itsuki Nakayama, Takahiro Mitani, Ryosuke Kikuchi, Yuya Sasaki, Makoto Onizuka

Published 2026-06-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Takuto Takahashi, Itsuki Nakayama, Takahiro Mitani, Ryosuke Kikuchi, Yuya Sasaki, Makoto Onizuka

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Like-Me" Bias

Imagine you are trying to guess someone's job title just by looking at their friends.

In a "Homophilous" world (where people with similar jobs hang out): If you see a person surrounded by other doctors, you can safely guess they are a doctor. This is how most current AI (Graph Neural Networks or GNNs) works. It assumes "birds of a feather flock together."
In a "Heterophilous" world (where opposites attract): This is where real life gets messy. Think of a university website. A Student is connected to a Professor, who is connected to a Department, which is connected to a Course.
- If you only look at a Student's immediate friends, you see Professors.
- If you look at the Professors' friends, you see Students and Departments.
- The current AI gets confused here. It sees a Student surrounded by Professors and thinks, "Maybe this student is a Professor?" because it only looks at the immediate neighborhood. It misses the bigger picture of how these different roles connect in a chain.

The Solution: The "Label Context Classifier" (LCC)

The authors propose a new tool called LCC (Label Context Classifier). Instead of just looking at who is standing next to whom, LCC looks at the story of how labels connect over several steps.

Think of LCC as a detective who doesn't just ask, "Who is your neighbor?" but instead asks, "Who did your neighbor talk to, and who did they talk to?"

To do this, LCC uses four specific "walking" strategies (called Label Walks) to trace paths through the network:

Forward Walk: Walking with the flow of the arrows. (e.g., Student $\to$ Professor $\to$ Department).
Backward Walk: Walking against the flow. (e.g., Department $\leftarrow$ Professor $\leftarrow$ Student).
Sibling Walk: Going up to a parent and then down to a cousin. (e.g., Student $\to$ Professor $\to$ Another Student). This helps find people who share the same boss.
Guardian Walk: The reverse of the sibling walk. (e.g., Department $\leftarrow$ Professor $\leftarrow$ Another Department). This helps find groups that share the same subordinate.

How It Works (The "Word2Vec" Analogy)

The paper mentions an idea inspired by word2vec (a famous AI that learns words by looking at the words around them).

The Old Way: The AI tries to guess a label based on the raw data of the node itself.
The LCC Way: The AI treats the sequence of labels (like "Student $\to$ Professor $\to$ Department") like a sentence. It learns that "Student" often appears in the context of "Professor," and "Professor" appears in the context of "Department."
By turning these walking paths into "embeddings" (mathematical summaries of the context), the AI creates a map of higher-order connectivity. It understands that even if a Student isn't directly connected to a Department, they are indirectly connected through a Professor.

The Team-Up: LCC + GNN

The authors realized that LCC is great at seeing the "big picture" of label connections, but traditional GNNs are still good at looking at the "fine details" of the node's own features.

So, they created a Team-Up Strategy:

They train the traditional GNN and the new LCC separately.
They use a "smart referee" (based on validation data) to decide how much to trust each team member.
- If the GNN is doing a better job on a specific dataset, the referee gives it more weight.
- If LCC is doing better, it gets more say.
They combine the two predictions to get the final answer.

Crucially, this doesn't require retraining the whole system. It's like hiring two experts, asking them for their opinions, and then averaging their answers based on who has been more accurate recently.

What They Found

The team tested this on real-world datasets like university web pages (Texas, Cornell, Wisconsin) and Wikipedia networks (Roman Empire, Chameleon).

The Result: In almost every case, the Team-Up (GNN + LCC) was more accurate than using either method alone.
The "Magic": The LCC part was especially good at fixing the mistakes the traditional GNNs made in "heterophilous" graphs (where opposites connect).
The Walk Length: They found that looking further ahead (taking longer walks) usually helped, but the "best" walk length depended on the specific dataset.

Summary

The paper argues that current AI is too focused on "who is my neighbor?" and misses the complex chains of relationships in real-world networks. By adding a new tool (LCC) that traces four types of walking paths to understand how different labels connect, and then smartly combining it with existing AI, they achieved better accuracy in classifying nodes in messy, real-world graphs.

Technical Summary: Graph Neural Network leveraging Higher-order Class Label Connectivity for Heterophilous Graphs

Problem Statement

Node classification in Graph Neural Networks (GNNs) has achieved high accuracy in homophilous graphs, where nodes with similar class labels tend to connect. However, performance degrades significantly in heterophilous graphs, where nodes with different class labels are more likely to be connected.

The authors identify a specific limitation in current GNNs (including those derived from Graph Convolutional Networks like GCN, GAT, and advanced heterophilous models like H2GCN and LINKX): they transform the node classification problem into a simple mapping from embedding space to class label space. Consequently, these models fail to capture higher-order class label connectivity—the structural relationships between class labels that span multiple hops via directed edges. While some methods utilize a class compatibility matrix to capture 1st-order connectivity, they do not account for complex, multi-hop label interactions frequently observed in real-world directed graphs (e.g., the Texas dataset, where "Student" nodes connect to "Department" nodes, which in turn connect to "Staff" nodes).

Methodology

The proposed approach introduces a novel classifier, the Label Context Classifier (LCC), and a framework to integrate it with existing GNNs.

1. Label Context Classifier (LCC)

LCC is designed to capture higher-order class label connectivity by treating sequences of class labels along graph walks as context, inspired by the word2vec Skip-gram model. The process involves three main steps:

Label Walk Extraction: From a target node, four distinct types of label walks are extracted. A label walk is a sequence of class labels where nodes are replaced by their labels. If a node is not in the training set, a null label is used.
- Forward Walk: A depth-first search following the direction of edges (Target $\to$ Child $\to$ Grandchild).
- Backward Walk: A depth-first search following the reverse direction of edges (Target $\to$ Parent $\to$ Grandparent).
- Sibling Walk: Traverses backward to a parent node and then forward to its other children (Target $\to$ Parent $\to$ Sibling). This captures connectivity between nodes sharing a common parent.
- Guardian Walk: Traverses forward to a child node and then backward to its other parents (Target $\to$ Child $\to$ Co-parent). This captures connectivity between nodes sharing a common child.
Label Context Embedding Generation: Using the extracted walks, the model learns embeddings that represent the "label context." A simple two-layer Multi-Layer Perceptron (MLP) is trained to predict the context labels (the subsequent labels in the walk) given the target node's label as input. The hidden layer produces the label context embeddings ( $Z$ ).
Classifier Training: The final LCC classifier is an MLP trained on the concatenation of the original node features and the label context embeddings derived from the four walk types.

2. Integration with GNNs

To leverage the strengths of both traditional GNNs (which capture feature and local structural information) and LCC (which captures higher-order label connectivity), the authors propose an adaptive integration scheme:

Independent Training: Both the GNN and the LCC are trained independently on the training set.
Adaptive Weighting: The importance of each model is determined using the validation loss. The weights ( $w_{LCC}$ and $w_{GNN}$ ) are calculated as the reciprocal of the validation loss, adjusted by a temperature parameter ( $T$ ).
Ensemble Prediction: The final prediction is a weighted average of the outputs from the GNN and the LCC. This integration requires no additional model training, only the calculation of weights based on validation performance.

Key Contributions

Proposal of LCC: A novel classifier that estimates node labels by capturing higher-order class label connectivity through four direction-aware label walks (Forward, Backward, Sibling, Guardian).
Adaptive Integration Framework: A method to integrate LCC with any existing GNN by adaptively learning importance weights based on validation loss, without requiring additional training costs.
Empirical Validation: Experimental results demonstrating that the integration of LCC with GNNs outperforms State-of-the-Art (SOTA) methods on heterophilous directed graphs.

Experimental Results

The authors evaluated their method on seven heterophilous directed graph datasets: Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire, and Amazon-Ratings.

Performance Improvement: The integrated models (e.g., H2GCN+LCC, LINKX+LCC, GloGNN+LCC) achieved the highest node classification accuracy across all datasets compared to standalone GNNs, MLPs, and LCC alone.
Complementarity: The results indicate that LCC and GNNs capture different graph properties. In most cases, the integration improved accuracy over the individual components.
Effectiveness of Label Walks: LCC significantly outperformed a vanilla MLP (which uses only node features), confirming that label context embeddings effectively capture class label connectivity. Notably, accuracy gains exceeded 10% on datasets like Chameleon, Squirrel, Roman-Empire, and Amazon-Ratings.
Walk Type Importance: The importance of specific walk types varied by dataset. For instance, Guardian walks were most critical for Chameleon, Squirrel, and Amazon-Ratings, while Sibling walks were most effective for Roman-Empire.
Walk Length: Increasing the walk length (for forward/backward walks) or utilizing 2-hop walks (sibling/guardian) generally improved performance, highlighting the necessity of capturing higher-order connectivity.

Significance and Claims

The paper claims that the primary weakness of current GNNs in heterophilous settings is their inability to model how class labels connect through multiple hops in directed graphs. By explicitly modeling these higher-order relationships via label walks, LCC provides a complementary signal to feature-based GNNs.

The authors emphasize that their approach does not require complex architectural changes to existing GNNs; rather, it offers a modular classifier that can be adaptively combined with any GNN to enhance performance. The results suggest that leveraging structural information between class labels, rather than just node features or immediate neighbors, is crucial for accurate classification in heterophilous directed graphs. The work is supported by JSPS KAKENHI and JST ASPIRE grants.