Dominance-Fold Graph Pooling
Source paper: The Homotopy Types of the Independence and Perfect Matching Complex of Möbius Ladder Graph arXiv:2608.30601 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Before message passing, repeatedly detect a pair of vertices with nested open neighborhoods and fold away the dominated vertex while preserving its information in the surviving vertex's feature state. The graph reduction is justified by homotopy invariance of the independence complex, while the feature merge prevents task-relevant attributes from being lost. Add a topology-aware ablation comparing this exact fold against random node pooling and standard learned pooling.
Formulas
Mathematical statement
The paper uses the domination reduction: if vertices u and w satisfy N(u) \subseteq N(w), where N(x) is the open neighborhood of x, then removing w preserves the independence complex up to homotopy, \operatorname{Ind}(G) \simeq \operatorname{Ind}(G\setminus w). The proof applies this rule repeatedly to Möbius-ladder subgraphs. The second structural identity is \operatorname{Ind}(G\sqcup H) = \operatorname{Ind}(G) \star \operatorname{Ind}(H), where \sqcup is disjoint union and \star is simplicial join. In the paper's auxiliary graph H_n, the reduction gives H_n\setminus b_{n-2}=H_{n-2}\sqcup P_3, hence \operatorname{Ind}(H_n)\simeq \operatorname{Ind}(H_{n-2})\star\operatorname{Ind}(P_3). Since \operatorname{Ind}(P_3)\simeq \mathbb{S}^0, iterating yields \operatorname{Ind}(H_n)\simeq \mathbb{S}^{(n-2)/2} for even n and a contractible complex for odd n. The ML adaptation exploits the exact local fold as a graph coarsening certificate: the independence-complex homotopy type is unchanged, although arbitrary node-level graph tasks are not guaranteed to be unchanged.
Implementation notes
Integrate this at the input graph-pooling stage, before the first GNN layer or between message-passing blocks. For every current graph, maintain adjacency sets and node features h_v. Repeatedly search for an ordered pair (u,w) with N(u) contained in N(w); use sorted-neighbor lists, bitsets, or hash-set inclusion tests. When found, remove w from the adjacency structure, but do not discard its feature: update the surviving representative using h_u <- MLP([h_u, h_w, degree(u), degree(w), |N(u)|]) or the simpler normalized merge h_u <- (h_u+h_w)/2. Record a fold map assigning w to u so that a later graph readout can optionally unpool or concatenate the accumulated cluster size and feature moments. Continue until no domination pair remains or a prescribed compression ratio is reached. Pseudocode is: while nodes_removed < budget: find (u,w) with N[u] subset N[w]; if none: break; h[u] = Merge(h[u],h[w]); cluster[u] += cluster[w]; delete w and incident edges; record fold(w->u). Compute the neighborhood criterion exactly from the graph; estimate no mathematical quantities. For disconnected components, optionally process each component independently, since the paper's join identity identifies their independence complexes compositionally. First test on synthetic graphs where labels are independence number, maximal independent-set count, or parity of the independence-complex sphere dimension, then on MUTAG or ogbn-arxiv with a 3-layer GIN baseline. Compare exact folds with random pooling and TopK pooling at equal node counts. Success means lower memory and runtime at matched accuracy, or improved accuracy at the same retained-node budget; specifically measure whether independence-structure tasks degrade less than under random deletion.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.