DuoGNN: Topology-aware Graph Neural Network with Homophily and Heterophily Interaction-Decoupling

Technical Summary of DuoGNN

Problem Statement
Graph Neural Networks (GNNs) have demonstrated efficacy in various domains, including medical imaging, by leveraging local neighborhood aggregation to capture short-range spatial interactions. However, this paradigm suffers from two fundamental limitations that hinder model expressiveness and prevent the effective use of deep architectures:

1. Over-smoothing: In heterophilic node aggregation, node embeddings become indistinguishable as the number of layers increases, causing features of nodes from distinct classes to converge.
2. Over-squashing: Graph bottlenecks inhibit message passing, causing the exponential growth of a node's receptive field and forcing substantial information to collapse into fixed-sized feature vectors.

Existing solutions, such as transformer-based attention mechanisms, multi-scale architectures, and topological graph rewiring, face significant drawbacks. Attention mechanisms suffer from quadratic time complexity ($O(|V|^2)$) and lack topological awareness. Multi-scale models often rely on clustering algorithms that are computationally expensive and topology-specific. Rewiring algorithms, while effective at alleviating bottlenecks, can excessively perturb graph structures or fail to resolve issues in very large or chain-like graphs. Consequently, there is a lack of a scalable, generalizable approach capable of simultaneously capturing short-range and long-range interactions (LRIs) across diverse graph topologies.

Methodology: DuoGNN Architecture
The authors propose DuoGNN, a topology-aware architecture designed to decouple homophilic and heterophilic interactions to process them independently. The model operates through a three-stage pipeline:

1. Interaction-Decoupling Stage:

   • Topological Edge Filtering: The model computes a topological measure (e.g., centrality or curvature) over the input graph's edges. It removes the $\kappa$ edges with the highest value of the metric (e.g., the highest centrality), as these edges are likely closest to graph bottlenecks. This effectively breaks the graph into homophilic connected components. This produces a homophilic graph ($G_{ho}$) that preserves short-range interactions while mitigating over-smoothing risks.
   • Heterophilic Graph Condensation: To recover the long-range interactions lost during edge filtering, the model identifies the $\mu$ most populated clusters in $G_{ho}$. For each cluster, it selects the most connected node (assumed to have the most reliable representation) and constructs a distinct, fully-connected graph ($G_{he}$). This condensation ensures scalability by drastically reducing the number of nodes while preserving heterophilic interactions and LRIs.

2. Parallel Transformation Stage:

   • The model processes $G_{ho}$ and $G_{he}$ through independent GNN modules.
   • Homophilic Module: Uses standard aggregation ($X^{(i+1)}_{ho} = \phi_{ho}(\hat{A}_{ho}X^{(i)}_{ho}W^{(i)}_{ho})$) to aggregate embeddings of nodes within the same class.
   • Heterophilic Module: Employs a modified aggregation strategy to prevent over-smoothing. It avoids aggregating features in the first layer to preserve original features and concatenates outputs from all layers into a linear layer. This allows the model to learn distinctions between dissimilar neighbors at multiple levels of smoothness.

3. Prediction Stage:

   • The outputs from both modules are concatenated and passed through a final linear layer to generate the final node representations for classification.

Key Contributions
The paper outlines three core contributions:

1. Topological Edge-Filtering Algorithm: An algorithm that extracts homophilic interactions by removing bottleneck edges, enabling the model to generalize across any graph topology.
2. Heterophilic Graph Condensation: A technique that extracts heterophilic interactions by condensing clusters into a smaller, fully-connected graph, ensuring scalability.
3. Dual Aggregation Pipeline: A mechanism that prevents over-smoothing and over-squashing by processing homophilic and heterophilic interactions independently, rather than relying on a single aggregation paradigm.

Results and Evaluation
DuoGNN was benchmarked against standard baselines (GCN, GIN, GAT) and their variants with topological filtering on both medical and non-medical datasets:

• Datasets: MedMNIST (Organ-C and Organ-S, involving liver tumor classification from CT scans) and Cora (scientific publication classification).
• Performance: DuoGNN variants consistently outperformed baselines across all tasks. The curvature-enhanced variant (using discrete Olivier's Ricci curvature) achieved the highest performance, likely due to its theoretical ability to detect areas affected by over-smoothing or over-squashing.
• Scalability: While DuoGNN showed a higher GPU memory footprint on small graphs due to its dual aggregation paradigm, it demonstrated superior scalability on large graphs compared to attention-based models (like GAT), which failed to run (OOM) on the MedMNIST datasets. The heterophilic condensation reduced the computational load of analyzing LRIs.
• Ablation: Simple pre-processing techniques (filtering applied to baselines) showed only marginal improvements, suggesting that the full architecture is necessary to effectively capture LRIs.

Significance and Claims
The authors claim that DuoGNN offers a scalable and generalizable solution to the long-standing challenges of over-smoothing and over-squashing in GNNs. By leveraging topological properties to decouple interaction types, the model expands the applicability of GNNs in medical imaging and other fields involving large datasets with complex, long-range dependencies. The paper emphasizes that unlike previous methods that either fail to generalize across topologies or incur prohibitive computational costs, DuoGNN provides a refined aggregation protocol that adapts to graph density and structure without requiring deep networks that inevitably lead to performance degradation.