Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture
Updated 2 h ago · first seen 11 Sept 2026
paper_01M294GPKX71QD49DS4BZN7CTB
- Published
- 11 Sept 2026
- T1 · 2 h ago
- arXiv
- 2508.08005
- T1 · 2 h ago
- Category
- cs.LG
- T1 · 2 h ago
Abstract
-cross Abstract: Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.
Authors 3
Xiang Li, Shanshan Wang, Chenglong Xiao
Specification
- Official page
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
- Arxiv announce type
- replace
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
- arXiv id
- 2508.08005
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
- Categories
- cs.LG, cs.AI
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
- Primary category
- cs.LG
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
- Published
- 11 Sept 2026
Source:arXiv (Atom API + RSS)T1observed 2 h agohigh
Each value shows its source, tier and observation time. Conflicting claims are kept side by side and flagged — never averaged. How AI Atlas records facts →
Provenance
Attributed facts
9
Source tiers
T19
Freshest observation
2 h ago
Conflicts
None
No models linked to this paper yet.
- Authors
- Xiang Li, Shanshan Wang, Chenglong Xiao
As of
Rewind the record: see this entity's attributes exactly as AI Atlas knew them on a given day.
Claim history
Official pageofficial_url1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| https://arxiv.org/abs/2508.08005 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Abstractabstract1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| -cross Abstract: Although the Maximum Clique Problem (MCP) has been extensively studied and features a rich ecosystem of exact solvers, empirical evidence shows that solver performance varies substantially across graph families. Consequently, selecting an appropriate algorithm for a given instance remains an open and practically important challenge that has received little systematic attention. We address this gap by developing an instance-aware selection framework that systematically combines global statistical descriptors with learned topological representations. We construct a comprehensive benchmark by evaluating four state-of-the-art exact solvers on a diverse collection of graph instances and deriving both global statistical and local structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Motivated by these observations, we introduce a dual-channel architecture that jointly leverages a Graph Attention Network for capturing local neighborhood patterns and a Multilayer Perceptron for modeling global statistical features. Extensive experiments show that the proposed dual-channel model consistently surpasses classical baselines and the single-best solver, achieving 90.43% test accuracy. These findings demonstrate the value of integrating local topological encoding with global statistical cues for combinatorial algorithm selection. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F. | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Arxiv announce typearxiv_announce_type1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| replace | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
arXiv idarxiv_id1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 2508.08005 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Categoriescategories1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| cs.LG, cs.AI | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
PDFpdf_url1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| https://arxiv.org/pdf/2508.08005 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Primary categoryprimary_category1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| cs.LG | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Publishedpublished_at1
| Value | Valid from → to | Status | Source | Confidence | Extractor |
|---|---|---|---|---|---|
| 11 Sept 2026 | → current | current | arXiv (Atom API + RSS)T1 | high | deterministic |
Claims are temporal and append-only: a new observation closes the previous claim (valid_to) instead of overwriting it. Conflicting claims from different sources are kept side by side and flagged — never averaged. Methodology →
- New paperPaperInstance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture
New paper: Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecture
arxiv
| Source | Document | Type | Tier | Last observed | Snapshots |
|---|---|---|---|---|---|
| arXiv (Atom API + RSS) | rss.arxiv.org/rss/cs.AI | feed | T1· Official | 2 h ago | 1 |
Tier 1 = official/primary, 2 = quality secondary, 3 = community, 4 = unverified. Every snapshot is archived; see all sources and the methodology.