Node Classification via Simplicial Interaction with Augmented Maximal Clique Selection

• URL: http://arxiv.org/abs/2509.23568v1
• Date: Sun, 28 Sep 2025 01:57:01 GMT
• Title: Node Classification via Simplicial Interaction with Augmented Maximal Clique Selection
• Abstract summary: We propose an augmented maximal clique strategy to handle higher-order interactions in a network.<n>Using only maximal cliques can reduce unnecessary overlap and provide a concise representation of the network.<n>Our strategy offers a computationally efficient and effective solution for higher-order network learning.
• Score: 1.9336815376402718
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Considering higher-order interactions allows for a more comprehensive understanding of network structures beyond simple pairwise connections. While leveraging all cliques in a network to handle higher-order interactions is intuitive, it often leads to computational inefficiencies due to overlapping information between higher-order and lower-order cliques. To address this issue, we propose an augmented maximal clique strategy. Although using only maximal cliques can reduce unnecessary overlap and provide a concise representation of the network, certain nodes may still appear in multiple maximal cliques, resulting in imbalanced training data. Therefore, our augmented maximal clique approach selectively includes some non-maximal cliques to mitigate the overrepresentation of specific nodes and promote more balanced learning across the network. Comparative analyses on synthetic networks and real-world citation datasets demonstrate that our method outperforms approaches based on pairwise interactions, all cliques, or only maximal cliques. Finally, by integrating this strategy into GNN-based semi-supervised learning, we establish a link between maximal clique-based methods and GNNs, showing that incorporating higher-order structures improves predictive accuracy. As a result, the augmented maximal clique strategy offers a computationally efficient and effective solution for higher-order network learning.

Related papers

• Differentiable Lifting for Topological Neural Networks [49.208571794040374]
  Topological neural networks (TNNs) enable leveraging high-order structures on graphs.<n>DiffLift is a framework for learning graph liftings to hypergraphs and cellular- and simplicial complexes.<n>Our approach leads to gains of up to 45% over static liftings, including both connectivity- and feature-based ones.
  arXiv  Detail & Related papers  (2026-08-02T11:30:09Z)
• Scaling Higher-Order Graph Learning with Maximal Clique Complexes [12.285621964183854]
  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.
  arXiv  Detail & Related papers  (2026-05-29T14:42:40Z)
• 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)
• Unsupervised Ordering for Maximum Clique [30.652280460904375]
  We transform the constraints into geometric relationships such that the ordering of vertices aligns with the clique structures.<n>By integrating this clique-oriented ordering into branch-and-bound search, we improve search efficiency and reduce the number of computational steps.
  arXiv  Detail & Related papers  (2025-03-25T18:28:49Z)
• Structured Click Control in Transformer-based Interactive Segmentation [36.49641677493008]
  We propose a structured click intent model based on graph neural networks. The graph nodes will be aggregated to obtain structured interaction features. The dual cross-attention will be used to inject structured interaction features into vision Transformer features.
  arXiv  Detail & Related papers  (2024-05-07T04:57:25Z)
• Unified Off-Policy Learning to Rank: a Reinforcement Learning Perspective [61.4025671743675]
  Off-policy learning to rank methods often make strong assumptions about how users generate the click data. We show that offline reinforcement learning can adapt to various click models without complex debiasing techniques and prior knowledge of the model. Results on various large-scale datasets demonstrate that CUOLR consistently outperforms the state-of-the-art off-policy learning to rank algorithms.
  arXiv  Detail & Related papers  (2023-06-13T03:46:22Z)
• Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphs [59.96266198512243]
  We propose a decentralized and federated learning algorithm for tasks that are positively and negatively correlated. Our algorithm uses gradients to calculate the correlations among tasks automatically, and dynamically adjusts the communication graph to connect mutually beneficial tasks and isolate those that may negatively impact each other. We conduct experiments on a synthetic Gaussian dataset and a large-scale celebrity attributes (CelebA) dataset.
  arXiv  Detail & Related papers  (2022-12-21T18:58:24Z)
• Cell Attention Networks [25.72671436731666]
  We introduce Cell Attention Networks (CANs), a neural architecture operating on data defined over the vertices of a graph. CANs exploit the lower and upper neighborhoods, as encoded in the cell complex, to design two independent masked self-attention mechanisms. The experimental results show that CAN is a low complexity strategy that compares favorably with state of the art results on graph-based learning tasks.
  arXiv  Detail & Related papers  (2022-09-16T21:57:39Z)
• Bandit Sampling for Multiplex Networks [8.771092194928674]
  We propose an algorithm for scalable learning on multiplex networks with a large number of layers. Online learning algorithm learns how to sample relevant neighboring layers so that only the layers with relevant information are aggregated during training. We present experimental results on both synthetic and real-world scenarios.
  arXiv  Detail & Related papers  (2022-02-08T03:26:34Z)
• Coordinated Reinforcement Learning for Optimizing Mobile Networks [6.924083445159127]
  We show how to use coordination graphs and reinforcement learning in a complex application involving hundreds of cooperating agents. We show empirically that coordinated reinforcement learning outperforms other methods.
  arXiv  Detail & Related papers  (2021-09-30T14:46:18Z)
• Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks [68.9026534589483]
  RioGNN is a novel Reinforced, recursive and flexible neighborhood selection guided multi-relational Graph Neural Network architecture. RioGNN can learn more discriminative node embedding with enhanced explainability due to the recognition of individual importance of each relation.
  arXiv  Detail & Related papers  (2021-04-16T04:30:06Z)
• Dynamic Graph: Learning Instance-aware Connectivity for Neural Networks [78.65792427542672]
  Dynamic Graph Network (DG-Net) is a complete directed acyclic graph, where the nodes represent convolutional blocks and the edges represent connection paths. Instead of using the same path of the network, DG-Net aggregates features dynamically in each node, which allows the network to have more representation ability.
  arXiv  Detail & Related papers  (2020-10-02T16:50:26Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors. It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features. We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
  arXiv  Detail & Related papers  (2020-06-26T17:03:06Z)

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.