Unifying Homophily and Heterophily Network Transformation via Motifs

Li Zhang, Yan Ge, Jun Ma, Li Zhang 0131, Haiping LuarXiv 2020 · arXiv

Introduction

In the field of network embedding, researchers often struggle to balance two competing graph principles: homophily and heterophily. Homophily assumes that "birds of a feather flock together," meaning connected nodes (like friends in a social circle) should be close in embedding space. Heterophily, conversely, suggests that nodes playing similar structural roles (like department heads in different universities) should be close, even if they are far apart in the actual graph.

Comparison of Homophily, Heterophily, and the proposed Hybrid approach.

Most current algorithms are "one-size-fits-all," failing to capture the hybrid nature of real-world networks that contain both tight-knit communities and cross-community structural roles. The $H^2NT$ framework addresses this by bridging the gap between these conflicting principles.

The H²NT Framework

The authors propose $H^2NT$ (Homophily and Heterophily preserving Network Transformation). Rather than a new embedding algorithm, $H^2NT$ is a transformation layer applied before standard algorithms like DeepWalk, AROPE, or GCN to enhance their performance.

Methodology

The framework utilizes triangular motifs—groups of three interconnected nodes—to define proximity. These motifs act as a denoise filter, focusing on significant structural patterns rather than raw edges. The transformation follows a structured workflow:

  1. Homophily Proximity ($A_M$): Captures local community structures using motif-based representations.
  2. Heterophily Proximity (H): Encourages "macro-level" walks that jump across communities to identify global structural similarities.
  3. Unified Proximity (Q): Merges these properties into a single matrix $Q = A_M + \lambda H$, where $\lambda$ tunes the balance between the two.
The H²NT framework workflow.

Key Insights and Results

One of the framework's most significant advantages is intelligent sparsification. By focusing on motif-rich structures, $H^2NT$ thins out the graph, removing "noisy" edges that do not contribute to a node's core identity. This leads to two major benefits:

  • Improved Accuracy: $H^2NT$-DeepWalk showed a 24% improvement in precision for motif prediction and consistently outperformed baselines in node classification on Facebook social network datasets.
  • Computational Efficiency: Because the transformed network is sparser, downstream algorithms have less work to do. $H^2NT$ reduced the computational time of DeepWalk by 46% and AROPE by 35%.

Conclusion and Future Work

$H^2NT$ successfully bridges the gap between homophily and heterophily. While currently focused on triangular motifs and linear unification, future iterations may explore higher-order motifs (like 4-vertex cliques) and non-linear operators to further refine how these fundamental network properties are merged.

Summary updated

BibTeX
@misc{zhang2020unifying,
  author = {Li Zhang and Yan Ge and Jun Ma and Li Zhang and Haiping Lu},
  title = {{Unifying Homophily and Heterophily Network Transformation via Motifs}},
  year = {2020},
  eprint = {2012.11400},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.11400},
}
Figure