Relational Decomposition of Heterogeneous Graphs

41 concepts34 papers1 proposal

Real-world networks are rarely uniform. They are typically heterogeneous graphs, containing a rich mix of different node types (e.g., users, items, attributes) and edge types (e.g., clicks, purchases, social ties).

When we apply standard Graph Neural Networks (GNNs) to these complex networks, we run into a fundamental bottleneck. Forcing a single message-passing mechanism to digest every type of node and edge simultaneously leads to semantic dilution—where distinct types of relationships interfere with each other—and over-smoothing, where highly connected "hub nodes" cause all node representations to collapse into indistinguishable vectors.

To solve this, researchers use a divide-and-conquer strategy: relational decomposition. Instead of processing a complex heterogeneous graph as a monolithic structure, the graph is broken down into multiple simpler, specialized subgraphs or "views." Each view isolates a specific relational context, allowing specialized encoders to extract clean features independently before fusing them back together.


How We Slice a Graph: Decomposition Strategies

Depending on the domain and the nature of the data, graphs can be decomposed along several different dimensions.

1. Edge-Type and Relation-Specific Partitioning

The most direct way to decompose a graph is to separate it by its explicit edge relations. This allows the model to learn distinct node representations for every specific role a node plays in the network.

2. Meta-Paths and Semantic Granularity

Sometimes, single edges are too fine-grained. Decomposition can instead occur across meta-paths (sequences of node types that capture high-order relationships) or across different levels of semantic abstraction.

  • Meta-Path Views: Shaowei Wei et al. demonstrated in NetMCs (Multiple clusterings of heterogeneous information networks) that isolating different meta-paths allows a model to discover multiple distinct, high-quality clusterings of the same entities (such as grouping organizations by geographic location versus professional domain). For online courses, Lu Jiang et al. used meta-path decomposition in IaGRL (Multi-View MOOC Quality Evaluation via Information-Aware Graph Representation Learning) to evaluate course quality by viewing a course independently through the lens of its instructor versus its subject matter.
  • Granularity Views: Zhiwei Hu et al. introduced MCLET (Multi-view Contrastive Learning for Entity Typing over Knowledge Graphs), which decomposes a graph into homogeneous views representing different levels of semantic granularity, such as entity-to-type, entity-to-cluster, and cluster-to-type relationships.

3. Behavioral, Role, and Outcome-Based Splitting

In user-centric systems, interactions carry different intents, roles, or outcomes. Decomposing the graph based on these behavioral nuances prevents conflicting signals from muddying the embeddings.

4. Structural Disentanglement (Homophily vs. Heterophily)

Graphs can also be decomposed by their underlying connectivity patterns rather than explicit labels. Zhaochen Guo et al. introduced DMGC (Disentangling Homophily and Heterophily in Multimodal Graph Clustering), which decomposes a graph into a homophilic view (where similar nodes connect) and a heterophilic view (where dissimilar nodes connect). The homophilic view captures broad semantic consensus, while the heterophilic view preserves fine-grained distinctions necessary to resolve overlaps between clusters.


Why It Works: The Core Intuition

Decomposing a graph provides several mathematical and structural advantages that make representation learning more robust.

Mitigating Over-Smoothing and Information Interference

In a standard GNN, passing messages across a highly connected heterogeneous network causes the features of different node types to blend together until they become uniform.

To combat this, Zheng Liu et al. developed HSGNN (Heterogeneous Similarity Graph Neural Network on Electronic Health Records), which splits electronic health record graphs into similarity-based subgraphs. This prevents highly connected "hub nodes" (like common diagnostic codes) from dominating the network and over-smoothing patient representations.

Similarly, Linli Xu et al. proposed HVHMC (Hierarchical Multi-label Text Classification with Horizontal and Vertical Category Correlations), partitioning text classification graphs into word-category and document-word subgraphs to eliminate cross-tier information interference.

In the realm of pre-training, Xiaohan Li et al. introduced RAM-GNN (Pre-training Recommender Systems via Reinforced Attentive Multi-relational Graph Neural Network), which pre-trains user and item embeddings on isolated multi-relational subgraphs to capture intrinsic features before exposing them to the noise of the full interaction space.

Preventing Parameter Explosion

When a knowledge graph contains hundreds of distinct relation types, assigning a unique parameter matrix to every single relation causes the model's parameter size to skyrocket.

Liying Cheng et al. addressed this in ENT-DESC (ENT-DESC: Entity Description Generation by Exploring Knowledge Graph) by decomposing complex knowledge graphs into structural primitives: self-loops, directional entity-relation links, and direct entity-to-entity connections. This structural decomposition maintains rich relational context while preventing parameter explosion.

Enabling Specialized Modality Processing

Not all relationships should be computed using the same mathematical operations. Decomposing a graph allows us to apply specialized logic to different data modalities.

For example, Zhiyuan Liu et al. developed AttrGNN (Exploring and Evaluating Attributes, Values, and Structures for Entity Alignment), which partitions knowledge graphs into subgraphs based on data types—literal strings, numerical values, and relational structures. This allows the model to apply string-matching algorithms to text attributes and numerical distance metrics to values, rather than forcing a one-size-fits-all GNN message-passing step.

Similarly, Xia Chen et al. showed in ActiveHNE (ActiveHNE: Active Heterogeneous Network Embedding) that breaking a heterogeneous network into distinct homogeneous and bipartite sub-networks allows for specialized spectral convolutions tailored to each specific mathematical structure.


Recombining the Views

Decomposition is only half the battle; the isolated views must eventually be woven back together into a unified representation. The modern standard for this recombination is self-supervised contrastive learning. By maximizing mutual information across different views, the model learns to retain the core identity of a node while respecting its multi-faceted behavioral contexts.

                  ┌───► View A (Collaborative) ───► Encoder A ──┐
                  │                                             ▼
Heterogeneous ────┼───► View B (Semantic)      ───► Encoder B ──┼───► Cross-View Fusion
   Graph          │                                             ▲     & Contrastive Loss
                  └───► View C (Structural)    ───► Encoder C ──┘

For instance, Ding Zou et al. introduced MCCLK (Multi-level Cross-view Contrastive Learning for Knowledge-aware Recommender System), which contrasts a global structural view, a local collaborative view, and a local semantic view. This self-supervision forces the recommender system to extract highly discriminative features that are robust to data sparsity.

To make this fusion more flexible, Mengru Chen et al. developed HGCL (Heterogeneous Graph Contrastive Learning for Recommendation), utilizing a cross-view meta-network to dynamically personalize how side information (like social ties or item categories) influences individual user-item interactions.

By breaking graphs apart to protect semantic purity and using contrastive frameworks to bring them together, relational decomposition allows models to navigate the complexity of real-world networks without losing their way.

Key Foundational Work

GPSP: Graph Partition and Space Projection based Approach for Heterogeneous Network Embedding (2018) — contributed 2 concept elements to this direction.
SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction (2018) — contributed 1 concept elements to this direction.
DevRank: Mining Influential Developers In Github (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_heterogeneous_graph_decomposition_fbdf3ba4,
  title = {heterogeneous graph decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/heterogeneous-graph-decomposition/rdr_fbdf3ba4485a4a7db51ffe41f5dea322},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_heterogeneous_graph_decomposition_fbdf3ba4_v1,
  title = {heterogeneous graph decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/heterogeneous-graph-decomposition/rdr_fbdf3ba4485a4a7db51ffe41f5dea322/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake