Complex-Weighted Convolutional Networks: Provable Expressiveness via Complex Diffusion

• URL: http://arxiv.org/abs/2511.13937v1
• Date: Mon, 17 Nov 2025 21:45:27 GMT
• Title: Complex-Weighted Convolutional Networks: Provable Expressiveness via Complex Diffusion
• Abstract summary: Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain limited by oversmoothing and poor performance on heterophilic graphs.<n>We introduce a novel framework that equips graphs with a complex-weighted structure, assigning each edge a complex number to drive a diffusion process that extends random walks into the complex domain.<n>We propose the Complex-Weighted Convolutional Network (CWCN), which learns suitable complex-weighted structures directly from data.
• Score: 5.766027446111051
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) have achieved remarkable success across diverse applications, yet they remain limited by oversmoothing and poor performance on heterophilic graphs. To address these challenges, we introduce a novel framework that equips graphs with a complex-weighted structure, assigning each edge a complex number to drive a diffusion process that extends random walks into the complex domain. We prove that this diffusion is highly expressive: with appropriately chosen complex weights, any node-classification task can be solved in the steady state of a complex random walk. Building on this insight, we propose the Complex-Weighted Convolutional Network (CWCN), which learns suitable complex-weighted structures directly from data while enriching diffusion with learnable matrices and nonlinear activations. CWCN is simple to implement, requires no additional hyperparameters beyond those of standard GNNs, and achieves competitive performance on benchmark datasets. Our results demonstrate that complex-weighted diffusion provides a principled and general mechanism for enhancing GNN expressiveness, opening new avenues for models that are both theoretically grounded and practically effective.

Related papers

• Score Approximation for Diffusion Models on Arbitrary Low-Dimensional Structures [23.118804869806898]
  This work establishes a universal score approximation theorem that works for any distribution supported on any compact set of upper Minkowski dimension $d$.<n>Using a novel discrete-mixture formulation, we prove that the score function can be approximated with a ReLU network whose complexity grows exponentially only with $d$.
  arXiv  Detail & Related papers  (2026-06-18T07:51:33Z)
• Generalization Bounds of Spiking Neural Networks via Rademacher Complexity [58.338455812259724]
  Spiking Neural Networks (SNNs) have garnered increasing attention as one of bio-inspired models due to their great potential in neuromorphic computing and computation.<n>Recent advances disclosed an excitation-dependent and architecture-related generalization bound such that the Rademacher complexity of SNNs with firing can be upper bounded by an exponential function.<n>We theoretically investigate the generalization bounds of SNNs with several integration-and-fire schemes via Rademacher complexity.
  arXiv  Detail & Related papers  (2026-04-26T14:24:48Z)
• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  We introduce a novel generative framework called textitGuided Topology Diffusion (GTD)<n>Inspired by conditional discrete graph diffusion models, GTD formulates topology synthesis as an iterative construction process.<n>At each step, the generation is steered by a lightweight proxy model that predicts multi-objective rewards.<n>Experiments show that GTD can generate highly task-adaptive, sparse, and efficient communication topologies.
  arXiv  Detail & Related papers  (2025-10-09T05:28:28Z)
• High-Fidelity Scientific Simulation Surrogates via Adaptive Implicit Neural Representations [51.90920900332569]
  Implicit neural representations (INRs) offer a compact and continuous framework for modeling spatially structured data.<n>Recent approaches address this by introducing additional features along rigid geometric structures.<n>We propose a simple yet effective alternative: Feature-Adaptive INR (FA-INR)
  arXiv  Detail & Related papers  (2025-06-07T16:45:17Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• Continuous Simplicial Neural Networks [14.60720265850122]
  We introduce continuous simplicial neural network (COSIMO)<n>COSIMO is a novel SNN architecture derived from partial differential equations (PDEs) on simplicial complexes.<n>We show that COSIMO achieves competitive performance compared to state-of-the-art SNNs in complex and noisy environments.
  arXiv  Detail & Related papers  (2025-03-17T08:31:25Z)
• Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes [5.838832985156104]
  We present a higher-order Flower-Petals (FP) model, incorporating FP Laplacians into simplicial complexes (SCs) We also introduce a Higher-order Graph Convolutional Network (HiGCN) grounded in FP Laplacians, capable of discerning intrinsic features across varying topological scales. HiGCN accomplishes state-of-the-art performance on a range of graph tasks and provides a scalable and flexible solution to explore higher-order interactions in graphs.
  arXiv  Detail & Related papers  (2023-09-22T16:11:17Z)
• SC-MAD: Mixtures of Higher-order Networks for Data Augmentation [36.33265644447091]
  The simplicial complex has inspired generalizations of graph neural networks (GNNs) to simplicial complex-based models. We propose data augmentation of simplicial complexes through both linear and nonlinear mixup mechanisms. We theoretically demonstrate that the resultant synthetic simplicial complexes interpolate among existing data with respect to homomorphism densities.
  arXiv  Detail & Related papers  (2023-09-14T06:25:39Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Simple and Efficient Heterogeneous Graph Neural Network [55.56564522532328]
  Heterogeneous graph neural networks (HGNNs) have powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) over homogeneous graphs, especially the attention mechanism and the multi-layer structure. This paper conducts an in-depth and detailed study of these mechanisms and proposes Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN)
  arXiv  Detail & Related papers  (2022-07-06T10:01:46Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Simplicial Attention Networks [4.401427499962144]
  Simplicial Neural Networks (SNNs) naturally model interactions by performing message passing on simplicial complexes. We propose Simplicial Attention Networks (SAT), a new type of simplicial network that dynamically weighs the interactions between neighbouring simplicies. We demonstrate that SAT outperforms existent convolutional SNNs and GNNs in two image and trajectory classification tasks.
  arXiv  Detail & Related papers  (2022-04-20T13:41:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.