DLS: Dual-Logic Graph Neural Networks with Chaos-Fuzzy Residuals for Robust Link Prediction

Mohammad Mehdi Keikha, Abolfazl NadiarXiv 2026 · arXiv

TL;DR

DLS (Dual-Logic SAGE) is a novel Graph Neural Network (GNN) framework that tackles the "over-smoothing" problem in link prediction by injecting "controlled instability" via chaos theory. By combining chaotic manifold expansion with fuzzy-logic noise filtering, DLS significantly outperforms state-of-the-art models on heterophilous graphs (where connected nodes are dissimilar) while maintaining high computational efficiency.

What Problem Does This Paper Address?

Most Graph Neural Networks rely on "message passing," a process where nodes aggregate information from their neighbors. Mathematically, this acts as a low-pass filter, which is great for finding patterns in "homophilous" graphs (where similar nodes connect, like a citation network). However, as GNNs get deeper, this leads to over-smoothing: node representations become nearly identical, making it impossible to distinguish between them.

This is a major hurdle for link prediction in "heterophilous" graphs—environments like transaction networks or protein interactions where connected nodes often have very different features. Standard GNNs inadvertently suppress the "high-frequency" signals needed to identify these distinct relationships. Existing solutions often rely on expensive subgraph mining, which doesn't scale well to large networks.

Methods

The authors introduce DLS (Dual-Logic SAGE), which uses a sequential residual pipeline to restore feature discriminability. The architecture consists of two main phases:

  1. Feature Engineering (Pre-processing):
    • Chaotic Dynamics Channel ($X_c$): The model uses the Logistic Map (a classic equation from chaos theory) to transform raw features. Because chaotic systems are highly sensitive to initial conditions, this "stretches" the feature manifold, forcing nodes that were artificially smoothed together to diverge and become distinguishable again.
  2. Fuzzy Logic Channel ($X_f$): To prevent the chaos from becoming pure noise, a fuzzy logic module uses a hyperbolic tangent function to model uncertainty. This acts as a "soft-thresholding" mechanism, filtering out stochastic noise while keeping the informative signals.
  3. Sequential Residual Architecture: Instead of just concatenating these features, DLS uses a GraphSAGE backbone and injects the chaotic and fuzzy signals as residual terms. This allows the model to "sharpen" the structural embeddings progressively.
Figure 1: The proposed DLS architecture. The framework consists of a GraphSAGE back- bone augmented by two residual streams: a Chaotic Injection path for feature expansion and a Fuzzy Logic path for noise gating. The final embedding Z integrates structural, chaotic, and fuzzy information sequentially.

Datasets

The model was evaluated on four diverse benchmarks representing different topological properties:

  • Cora: A standard homophilic citation network.
  • Squirrel & Chameleon: Wikipedia page networks characterized by high heterophily (dissimilar neighbors).
  • Actor: A movie-actor co-occurrence network known for its extreme sparsity and complex structural dependencies.

Key Insights and Ideas

  • The "Edge of Chaos": The authors found that performance peaks when the chaos control parameter ($r$) is set to 3.9. In dynamical systems, this is the "edge of chaos"—the point where the system has maximum complexity and entropy without collapsing into meaningless white noise.
  • Controlled Instability: Rather than trying to prevent instability, DLS embraces it. By injecting chaotic perturbations, the model recovers subtle signal variations that standard aggregation typically "washes out."
  • Fuzzy Logic as a Stabilizer: Link prediction is essentially a "Positive-Unlabeled" task (we know some edges exist, but a "missing" edge might just be an undiscovered one). Treating edge existence as a "degree of truth" via fuzzy logic helps the model handle this epistemic uncertainty better than binary logic.
  • Linear Scalability: Unlike many high-performing link prediction models (like SEAL or NCNC) that require expensive subgraph extraction, DLS maintains a complexity of $O(|E| + N)$, making it viable for very large graphs.

Key Results

  • Superiority in Heterophily: DLS achieved a remarkable 98.10% AUC on the Actor dataset, outperforming the nearest competitor (NCNC) by over 8%.
  • Robustness: While some baseline models performed well on homophilic graphs but failed on heterophilic ones (or vice versa), DLS remained a top performer across the entire spectrum.
  • Efficiency: On the Squirrel dataset, the popular "BUDDY" model failed due to memory exhaustion (OOM), while DLS processed it efficiently while achieving state-of-the-art results.

Limitations and Future Work

The authors acknowledge that the current version of DLS uses a fixed chaos control parameter across the entire graph. They suggest that a natural next step is developing Adaptive Dynamical GNNs, where the "chaos rate" is a learnable, node-specific variable that adjusts based on local graph entropy. Additionally, they aim to extend this framework to continuous-time dynamic graphs to predict how interactions evolve over time.

Summary updated

Abstract

Link prediction is a fundamental task in graph mining, critical for applications ranging from biological interaction discovery to recommender systems. While Message Passing Neural Networks (MPNNs) have achieved state-of-the-art results, they are fundamentally limited by the inadvertent suppression of high-frequency signals, as the recursive aggregation that stabilizes structural learning inherently leads to over-smoothing, rendering node representations indistinguishable in deep layers. This limitation is particularly severe in heterophilous graphs, where structural proximity does not imply feature similarity. In this paper, we propose DLS (Dual-Logic SAGE), a novel inductive framework designed to break the over-smoothing barrier via a "controlled instability" mechanism. Unlike conventional methods relying on static structural heuristics, DLS introduces a dynamic residual pipeline. First, a Chaotic Injection Module utilizes the Logistic Map to diversify the feature manifold, exploiting sensitivity to initial conditions to separate topologically similar but semantically distinct nodes. Second, to mitigate the aleatoric uncertainty introduced by chaotic dynamics, a Fuzzy-Logic Gating Mechanism applies soft-thresholding to filter noise and retain only high-confidence signals. Experimental results on diverse benchmarks demonstrate that DLS effectively balances feature discrimination with robustness, significantly outperforming state-of-the-art baselines in heterophilous settings while maintaining competitive efficiency on standard homophilous graphs.
BibTeX
@misc{keikha2026dls,
  author = {Mohammad Mehdi Keikha and Abolfazl Nadi},
  title = {{DLS: Dual-Logic Graph Neural Networks with Chaos-Fuzzy Residuals for Robust Link Prediction}},
  year = {2026},
  eprint = {2611.22607},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22607},
}
Figure