Second Order Neighborhoods for Learning in Heterophilous Graphs

This direction is merged into another direction: homophily assumption. Its last version stays readable and citable here.

Version 1 of 132 papers47 conceptsfrozen 2026-10-04

Most Graph Neural Networks (GNNs) operate on a simple assumption: "birds of a feather flock together." This principle, known as homophily, suggests that connected nodes likely share the same labels or features. However, many real-world networks are heterophilous, meaning "opposites attract." In a bipartite biological network, a protein might only connect to a chemical compound; in a social network, individuals might primarily interact with those of a different gender or political affiliation.

When homophily fails, standard GNNs—which smooth features across immediate neighbors—effectively wash away the signal, leading to poor performance. A growing body of research suggests that the solution lies not in the immediate neighborhood, but one step further: the "friend of a friend."

The Monophily Signal

The core intuition behind this research direction is that while your friends might not be like you, your friends' friends often are. Johan Ugander and Kristen M. Altenburger formalize this as monophily in Bias and variance in the social structure of gender. They demonstrate that even when direct connections show low similarity, extreme preferences in a network create hidden structural signals in second-order relationships.

In heterophilous graphs, the 1-hop neighborhood is a source of noise, but the 2-hop neighborhood often restores homophily. As Xiao Wang and Chuan Shi argue in A Generalized Neural Diffusion Framework on Graphs, this "monophily" property—the tendency for 2-hop neighbors to share labels—is a universal signal that can be exploited to make GNNs robust across diverse graph structures.

Restoring Similarity via Even-Step Propagation

The mathematical mechanism for capturing this signal often involves the square of the adjacency matrix ($A^2$). While $A$ represents direct links, $A^2$ represents paths of length two.

An early realization of this came from Brian Gallagher, Tina Eliassi-Rad, and colleagues in Using ghost edges for classification in sparsely labeled networks. They introduced "even-step" random walks to handle networks with negative autocorrelation. By focusing on nodes two steps away, they transformed a problem where neighbors were dissimilar back into a similarity-based propagation problem.

Modern architectures have refined this into explicit design principles. In Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs, Jiong Zhu and Leman Akoglu proposed H2GCN, which explicitly separates and aggregates information from 1-hop and 2-hop neighborhoods. This allows the model to learn that while the 1-hop neighbor might provide "negative" information (the node is not like this), the 2-hop neighbor provides "positive" information (the node is like this).

High-Order Diffusion and Skip Connections

The shift toward second-order signals has led to several specialized frameworks:

  • Skip-Graph Networks: In the realm of drug discovery, Kexin Huang and Jimeng Sun developed SkipGNN. They argue that in biological interactions, functional similarity is often found between nodes two steps apart. By fusing a standard graph with a "skip graph" (representing 2-hop connections), they bypass the dilution of signal that occurs in standard message passing.
  • Adaptive Propagation: Di Jin and Tao Wang introduced HOG-GCN in Powerful Graph Convolutional Networks with Adaptive Propagation Mechanism for Homophily and Heterophily. Their model adaptively determines the "homophily degree" of a neighborhood, allowing it to switch between 1-hop and 2-hop aggregation based on where the strongest similarity signal resides.
  • High-Order Diffusion: The HiD-Net framework, detailed by Yibo Li and Xiao Wang, treats graph learning as a continuous diffusion process. By incorporating high-order diffusion terms, the model naturally accounts for monophily, allowing information to flow effectively even when direct edges act as barriers.

Why It Works: The Paradox of Diversity

The effectiveness of second-order methods reveals a fundamental property of social and structural networks. As Anna Evtushenko notes in The paradox of second-order homophily in networks, social environments can be more diverse at the friend-of-friend level than immediate ties suggest, yet they often retain a predictable clustering of traits.

By looking two steps ahead, researchers are able to "see through" the local heterophily. Whether it is identifying super-spreaders via 2-hop redundancy (Dayong Zhang) or predicting gender through friend-of-friend preferences, the second-order neighborhood provides a stable inductive bias that first-order connections often lack. This shift from "who you know" to "who your friends know" has become the primary strategy for scaling GNNs to the complexity of real-world, non-assortative data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_second_order_neighborhoods_for_learning__2b28f8cf,
  title = {Second Order Neighborhoods for Learning in Heterophilous Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/second-order-neighborhoods-for-learning-in-heterophilous-graphs/rdr_2b28f8cf42b44c9396337af17f3d976f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_second_order_neighborhoods_for_learning__2b28f8cf_v1,
  title = {Second Order Neighborhoods for Learning in Heterophilous Graphs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/second-order-neighborhoods-for-learning-in-heterophilous-graphs/rdr_2b28f8cf42b44c9396337af17f3d976f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}