Long-Cycle Topological Graph Pooling

Integrate this at the input graph-construction stage of a graph neural network, before message passing or graph pooling. Given node features x_i and coordinates or an embedding z_i, choose a radius r so the average degree is bounded but above the percolation threshold; in practice estimate r from the desired degree k by r approximately (k/n)^(1/d), then build edges (i,j) whenever the distance is at most r. Work over F_2. First compute a spanning forest T. For every non-tree edge e=(u,v), form its fundamental cycle c_e consisting of e plus the unique T-path from u to v; these cycles provide a basis of Z_1(G). Estimate the graph-diameter cutoff L_G=alpha*log(1/r), with alpha initially 2 to 6. Classify each fundamental cycle as local when its maximum pairwise shortest-path distance is at most L_G. To approximate Z_1^{L_G}, collect local cycles and run binary Gaussian elimination on their edge-incidence vectors; calculate rank_long=rank(all cycle basis)-rank(local-cycle span). A scalable alternative is a sparse XOR basis for local cycle vectors. Append rank_long, the surviving quotient coordinates, or a learned projection of the quotient basis to the pooled graph representation. The theorem supplies the scale separation and expected O(n) edge budget; estimate the percolation threshold, cycle ranks, and alpha empirically. Start with 2D Swiss-roll, torus, and circle-versus-line graph classification using 1,000 to 10,000 points. Compare a GCN or GraphSAGE on a kNN graph, a radius graph without topology features, and a persistent-homology baseline. Measure accuracy at fixed edges, memory, and wall-clock time. The expected signal is improved classification of manifolds with different global loops at equal edge count, with long-cycle rank stable under node subsampling and coordinate noise. Sweep alpha to test for a transition near the logarithmic cutoff.