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.
- In Representation Learning: Le Yu et al. developed R-HGNN (Heterogeneous Graph Representation Learning With Relation Awareness), which decomposes graphs into subgraphs based on edge types to run independent graph convolutions for each relation. Similarly, Lijie Wen et al. proposed GAHNE (GAHNE: Graph-Aggregated Heterogeneous Network Embedding) to extract features from relation-specific sub-networks, bypassing the need for manual path engineering.
- In Natural Language Processing: Rajat Agarwal et al. designed MitiGaTe (Multi-Relational Graph Transformer for Automatic Short Answer Grading), which decomposes sentence-meaning graphs into semantic subgraphs (like agent-action versus patient-action links) to grade short answers based on structural logic rather than simple word matching.
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.
- Multi-Behavior Systems: Shuyun Gu et al. developed S-MBRec (Self-supervised Graph Neural Networks for Multi-behavior Recommendation), which splits a global interaction graph into behavior-specific subgraphs (e.g., clicking, adding to cart, purchasing) to capture hidden commonalities when target data like purchases are scarce.
- Role-Based Systems: For group-buying e-commerce, Liangwei Yang et al. created MVPRec (Multi-view Graph Convolution for Participant Recommendation), decomposing historical data into initiator-item and participant-item subgraphs to capture how user behavior shifts depending on whether they are leading or joining a collective purchase.
- Outcome-Based Systems: In intelligent education, Pengyang Shao et al. designed ISG-CD (Exploring Heterogeneity and Uncertainty for Graph-based Cognitive Diagnosis Models in Intelligent Education), partitioning student-exercise graphs based on correct versus incorrect answers to preserve the unique semantic meaning of success and failure.
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.