Scaling Higher-Order Graph Learning with Maximal Clique Complexes

• URL: http://arxiv.org/abs/2605.31373v1
• Date: Fri, 29 May 2026 14:42:40 GMT
• Title: Scaling Higher-Order Graph Learning with Maximal Clique Complexes
• Abstract summary: Graph neural networks (GNNs) are limited to modeling pairwise interactions, while higher-order models based on cell complexes achieve greater expressivity but often suffer from poor scalability.<n>We introduce simplified and factored cellular Weisfeiler Leman tests (sCWL and fCWL), which preserve the expressivity of the CWL test while improving computational efficiency.<n>We further introduce the maximal clique complex, enabling scalable CWNs with reduced time and memory complexity while retaining strong empirical performance.
• Score: 12.285621964183854
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) are limited to modeling pairwise interactions, while higher-order models based on cell complexes achieve greater expressivity but often suffer from poor scalability. We introduce simplified and factored cellular Weisfeiler Leman tests (sCWL and fCWL), which preserve the expressivity of the CWL test while improving computational efficiency. We further introduce the maximal clique complex, enabling scalable CWNs with reduced time and memory complexity while retaining strong empirical performance. To avoid explicit clique enumeration, we propose CliqueWalk, a biased random walk that samples maximal cliques and scales linearly with graph size. These contributions yield a scalable topological learning framework for higher-order graph representation.

Related papers

• A Distributed Training Architecture For Combinatorial Optimization [0.0]
  We propose a distributed graph neural network (GNN)-based training framework for optimization.<n>Experiments are conducted on both real large-scale social network datasets and synthetically generated high-complexity graphs.<n>Our framework outperforms state-of-the-art approaches in both solution quality and computational efficiency.
  arXiv  Detail & Related papers  (2025-11-12T12:22:10Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale graph reasoning abilities.<n>With RL on Erdos, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size)<n>Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks.
  arXiv  Detail & Related papers  (2025-05-24T04:33:41Z)
• 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)
• Tensor-Fused Multi-View Graph Contrastive Learning [12.412040359604163]
  Graph contrastive learning (GCL) has emerged as a promising approach to enhance graph neural networks' (GNNs) ability to learn rich representations from unlabeled graph-structured data.<n>Current GCL models face challenges with computational demands and limited feature utilization.<n>We propose TensorMV-GCL, a novel framework that integrates extended persistent homology with GCL representations and facilitates multi-scale feature extraction.
  arXiv  Detail & Related papers  (2024-10-20T01:40:12Z)
• Higher Order Structures For Graph Explanations [9.164945693135959]
  We present Framework For Higher-Order Representations In Graph Explanations (FORGE)<n>FORGE enables graph explainers to capture higher-order, multi-node interactions.<n>It improves average explanation accuracy by 1.9x and 2.25x, respectively.
  arXiv  Detail & Related papers  (2024-06-05T13:31:30Z)
• Learning From Simplicial Data Based on Random Walks and 1D Convolutions [6.629765271909503]
  simplicial complex neural network learning architecture based on random walks and fast 1D convolutions. We empirically evaluate SCRaWl on real-world datasets and show that it outperforms other simplicial neural networks.
  arXiv  Detail & Related papers  (2024-04-04T13:27:22Z)
• Sparse Training of Discrete Diffusion Models for Graph Generation [45.103518022696996]
  We introduce SparseDiff, a novel diffusion model based on the observation that almost all large graphs are sparse. By selecting a subset of edges, SparseDiff effectively leverages sparse graph representations both during the noising process and within the denoising network. Our model demonstrates state-of-the-art performance across multiple metrics on both small and large datasets.
  arXiv  Detail & Related papers  (2023-11-03T16:50:26Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Weisfeiler and Lehman Go Cellular: CW Networks [3.0017241250121383]
  Graph Neural Networks (GNNs) are limited in their expressive power, struggle with long-range interactions and lack a principled way to model higher-order structures. We extend recent theoretical results on SCs to regular Cell Complexes, topological objects that flexibly subsume SCs and graphs. We show that this generalisation provides a powerful set of graph lifting'' transformations, each leading to a unique message passing procedure.
  arXiv  Detail & Related papers  (2021-06-23T17:59:16Z)
• Graph Contrastive Learning Automated [94.41860307845812]
  Graph contrastive learning (GraphCL) has emerged with promising representation learning performance. The effectiveness of GraphCL hinges on ad-hoc data augmentations, which have to be manually picked per dataset. This paper proposes a unified bi-level optimization framework to automatically, adaptively and dynamically select data augmentations when performing GraphCL on specific graph data.
  arXiv  Detail & Related papers  (2021-06-10T16:35:27Z)
• Parameterized Hypercomplex Graph Neural Networks for Graph Classification [1.1852406625172216]
  We develop graph neural networks that leverage the properties of hypercomplex feature transformation. In particular, in our proposed class of models, the multiplication rule specifying the algebra itself is inferred from the data during training. We test our proposed hypercomplex GNN on several open graph benchmark datasets and show that our models reach state-of-the-art performance.
  arXiv  Detail & Related papers  (2021-03-30T18:01:06Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

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.