Learning Propagation Geometry from Message-Passing Feedback

1 INTRODUCTION

• Neighborhood means can conceal cross-feature joint variation, causing identical target features and means to yield the same estimated geometry for different neighborhoods.The introduction identifies this as a limitation of ARGNN’s metric estimation.Source: §1 · p. 2
• GeoF jointly evolves node features and node-wise symmetric positive-definite geometry, using triangular frame transport and weighted second-order residuals to form geometry targets.The residuals compare aligned individual messages with the transformed target state.Source: §1 · p. 2
• A shared controller learns task-supervised corrections that bounded log-triangular updates combine with geometry targets and prior states while preserving positive definiteness.The updated geometry governs neighborhood weights and frame transformations in subsequent propagation steps.Source: §1 · p. 2
• GeoF reports consistent gains over general, manifold-based, and adaptive GNN baselines on node classification, link prediction, and graph classification.The recurrent mechanism uses shared parameters across steps and task-specific readouts.Source: §1 · p. 2

Operator and Structure Adaptation in GNNs

• Operator and structure adaptation includes higher-order mixing, adaptive propagation scales, meta-path graphs, refined adjacency matrices, and latent edges.These approaches adapt aggregation or which nodes communicate.Source: §2 · p. 2

Geometric Modeling and Adaptive Propagation Spaces

• Geometric GNNs use hyperbolic spaces for hierarchical structure and sheaf-based local maps, and may learn graph-dependent curvature or select spaces per node.The passage also describes node-wise anisotropic metrics learned from node features and neighborhood means.Source: §2 · pp. 2–3
• Unlike metrics estimated from features and neighborhood means, GeoF maintains local geometry across propagation steps and updates it using aligned-message residual statistics and task-guided corrections.This makes propagation geometry a persistent node-wise state.Source: §2 · p. 3

3.1 GEOMETRIC STATES AND INITIALIZATION

• Block log-triangular coordinates and a shared prototype atlas initialize bounded, positive-definite node geometries from structural signatures while retaining within-block interactions.The representation uses d(m + 1)/2 geometric coordinates per node.Source: §3.1 · pp. 3–4

3.2 TRIANGULAR FRAME TRANSPORT

• Current geometries determine neighborhood weights and transport transformed source messages through a shared environment into each target node’s local frame before aggregation and feature updates.This couples neighbor weighting with alignment, giving messages a consistent reference for residual computation.Source: §3 · p. 3, §3.2 · p. 4

3.3 SECOND-ORDER RESIDUAL FEEDBACK

• Weighted outer products of aligned-message residuals capture directional variation and within-block dependence, including variation that cancels in the mean and is missed by mean-based estimators.The second-order target registers such variation for almost every configuration, whereas first-order updates cannot; it is nevertheless not an injective aggregator.Source: §3.3 · pp. 5–6

3.4 TASK-GUIDED GEOMETRY EVOLUTION

• Task supervision supplies a learned correction that combines with the residual target and previous state in a bounded log-triangular update; convergence is guaranteed under stated contraction conditions.The one-step Lipschitz bound does not depend on node degrees.Source: §3.4 · pp. 6–7

3.5 LEARNING OBJECTIVES

• Task objectives jointly train the geometry controller, propagation parameters, and readouts through geometry’s effects on subsequent propagation for node, link, and graph prediction.Node classification uses a shared linear classifier, while graph classification mean-pools final environment representations and applies a shared MLP.Source: §3 · p. 3, §3.5 · p. 7
• A shared MLP decodes the symmetric pair representation formed from the final environment representations into a predicted edge probability.The probability is the sigmoid of the link decoder output.Source: §3.5 · p. 7
• The link objective applies binary cross-entropy to positive training edges and sampled negative pairs, labeled 1 and 0, respectively.The training set is the union of positive training edges and sampled negative pairs.Source: §3.5 · p. 7

4.1 EXPERIMENTAL SETTINGS

• The evaluation covers node classification and link prediction on six datasets and graph classification on six datasets, comparing GeoF with general, manifold-based, and adaptive GNNs.Node and graph classification use accuracy, while link prediction uses ROC-AUC.Source: §4.1 · pp. 7–8

4.2 PERFORMANCE COMPARISONS

• Table 1 compares baselines with GeoF for node classification and link prediction, while Table 2 covers graph classification.Both captions describe performance comparisons in percent.Source: Table 1 · p. 8, Table 2 · p. 8

4.3 ABLATION STUDY

• Freezing geometry costs the most accuracy, while removing second-order feedback costs the second most on Mutagenicity and NCI1.The full model attains the highest accuracy on both datasets; removing frame transport also lowers accuracy.Source: §4.3 · p. 9

4.4 SENSITIVITY ANALYSIS

• On NCI1, accuracy is stable for B ∈{8, 16, 32} and changes little for K ∈{4, 8, 16}; on PubMed, accuracy is stable for L from 1 to 8.Accuracy drops at B = 64 and slightly at K = 32 and 64; geometric change decreases with depth and plateaus between L = 2 and 5.Source: §4.4 · p. 9
• As perturbation magnitude rises from σ = 0.01 to 0.5, one-step sensitivity decreases by 7.6% and accuracy drops by only 1.1%.The reported sensitivity is nearly constant at small σ.Source: §4.4 · p. 9

4.5 ANALYSIS OF SECOND-ORDER FEEDBACK

• Mean-only and diagonal residual targets both lower accuracy on all four datasets, with the diagonal target losing most on NCI1 and Mutag.The restricted variants rank differently across datasets, suggesting that mean and marginal second moments capture different aspects of local variation.Source: §4.5 · p. 9
• GeoF exceeds the strongest second-order-augmented baseline by 0.7 to 3.3 points in every reported setting.The comparison uses matched parameter counts within 0.5%; GeoF uses the statistics as feedback that changes subsequent geometry, while the baselines use them as features.Source: Table 3 · p. 9, §4.5 · p. 9
• Updating geometry only once after the first step lowers accuracy on Photo, CS, Mutag, and NCI1.The respective drops are 1.4, 1.0, 1.8, and 3.2 points.Source: §4.5 · p. 10

5 CONCLUSION

• GeoF jointly evolves node features and propagation geometry through recurrent message-passing feedback.The geometry governs neighborhood weighting and frame-aligned propagation, while second-order residual statistics and task-supervised corrections drive updates that preserve positive definiteness.Source: §5 · p. 10
• Experiments on node, link, and graph prediction show consistent gains over competitive baselines.The conclusion frames these results as support for learning propagation geometry from the interactions it induces.Source: §5 · p. 10
• The paper identifies adaptive-depth inference and evolving graphs as directions for future work.Source: §5 · p. 10

A NOTATION SUMMARY

• Table 5 summarizes the paper's key notations.Source: A NOTATION SUMMARY · p. 13, Table 5 · p. 13

B PROOF OF LEMMA 1

• The frame L(z) is lower triangular with positive diagonal entries e^ℓt, making it invertible and g(z) = L(z)⊤L(z) symmetric positive definite.The proof uses the resulting frame bounds to bound the eigenvalues of the metric.Source: B PROOF OF LEMMA 1 · p. 14
• Bounds on the triangular coordinates yield upper and lower spectral bounds for L(z) and corresponding metric bounds.The constants depend on m, amax, ℓmin, and ℓmax; the inverse-frame bound uses forward substitution and a Neumann-series argument.Source: B PROOF OF LEMMA 1 · pp. 13–14
• The reconstruction map from log-triangular coordinates to frames is Lipschitz, with the result extending to block-diagonal frames.The proof separates changes in the strictly lower entries from changes in the diagonal factors.Source: B PROOF OF LEMMA 1 · pp. 13–15

C PROOF OF PROPOSITION 1

• Composing frame transports along a walk reduces to a transformation determined by the endpoint frames; a closed walk gives the identity.Source: C PROOF OF PROPOSITION 1 · p. 15
• Admissible geometric states make neighborhood weights positive and finite, and invertible target frames ensure transport returns a unique message.The transport operator is bounded using the frame spectral bounds.Source: C PROOF OF PROPOSITION 1 · p. 15
• In environment coordinates, the proof expresses both the aggregate and message residuals using the aligned transport construction.Source: C PROOF OF PROPOSITION 1 · pp. 15–16

• First-order updates return identical outputs for configurations with the same first moment, while the second-order target is injective in the second-moment statistic.The stated first-order updates include the controller and feature update.Source: D PROOF OF PROPOSITION 2 · p. 16
• With at least two neighbors, equal-first-moment configurations with differing second-order statistics are generic, since the exceptional set has Lebesgue measure zero.The proof establishes this genericity result for each block.Source: D PROOF OF PROPOSITION 2 · pp. 16–17
• For m = 1, distinct three-point residual sets can share equal weights, first moments, and second moments, so the second-order target does not distinguish them.The proof compares such a set with {−1, 0, 1}.Source: D PROOF OF PROPOSITION 2 · pp. 16–18
• For m ≥ 2, the configurations {0, ±v} and {0, ±w} have the same diagonal statistics but different full second moments, unlike the mean-only target.Their off-diagonal (1, 2) entries differ in sign.Source: D PROOF OF PROPOSITION 2 · p. 18

E PROOF OF PROPOSITION 3

• The geometry update's projection is Euclidean projection onto the admissible coordinate set and is non-expansive.The proof treats the projected update as a proximal step.Source: E PROOF OF PROPOSITION 3 · p. 18
• The recurrent map is Lipschitz with constant K independent of node degrees, under the stated bounded-feature and parameter conditions.The bound depends on model and update constants, but not on graph degree.Source: E PROOF OF PROPOSITION 3 · pp. 18, 20
• An unclipped fixed point is locally attracting when its Jacobian has spectral radius below one; a stricter contraction condition gives a unique global fixed point.The global condition is ρ = (1 − λ) + λL̂z + γLΔ < 1.Source: E PROOF OF PROPOSITION 3 · p. 18

F.1 STRICTLY LOWER-TRIANGULAR VECTORIZATION

• The numerical operators vectorize and reconstruct strictly lower-triangular entries in row-major order, preserving their Frobenius norm.Svecsl extracts the entries and matsl inverts that ordering.Source: §F.1 · p. 21

F.2 STABILIZED CHOLESKY FACTORIZATION

• Stabilized Cholesky retries with increasing diagonal jitter after numerical failure; the resulting target frame maps the local unit ball to the residual second-moment ellipsoid.The jitter is a numerical safeguard, separate from statistic regularization.Source: §F.2 · p. 21, §F.3 · p. 22

F.3 CONSTRUCTION OF THE COORDINATE TARGET

• The target frame's singular values are square roots of the regularized residual-statistic eigenvalues, stretching high-energy directions more strongly in the environment.Neighborhood weights are computed in that environment.Source: §F.3 · p. 22

G.1 DATASET DESCRIPTION

• The benchmarks include citation, co-authorship, and Amazon co-purchase networks for node classification and link prediction, alongside bioinformatics and molecular graphs for graph classification.Examples include CiteSeer, PubMed, CS, Physics, Photo, Computers, PROTEINS, NCI1, BBBP, and ogbg-molhiv.Source: §G.1 · p. 22, §G.2 · p. 24

G.2 DATA PROCESSING

• Node and link-prediction graphs are made undirected and row-normalized; degree and random-walk structural signatures inform the prototype gate and geometric controller.Link prediction uses the standard random edge-split protocol.Source: §G.2 · p. 24

H.1 BASELINE DESCRIPTION

• Compared baselines include general GNNs such as GIN and WaveGC, manifold-based HGCN, D-GCN, and SPDGNN, and adaptive methods.The adaptive family includes ACE-HGNN, BEC-GNN, GNRF, and ARGNN.Source: §H.1 · pp. 24–25

H.2 IMPLEMENTATION DETAILS

• GeoF uses two shared-parameter recurrent steps, eight geometric blocks, four prototypes, and a rank-four controller.Training uses Adam with learning rate 1 × 10^-3 and weight decay 5 × 10^-4.Source: §H.2 · p. 25
• Evaluation reports accuracy for node classification and most graph classification datasets, and ROC-AUC for link prediction, BBBP, and ogbg-molhiv.Node classification and link prediction use ten random splits; graph classification uses ten-fold cross-validation.Source: §H.2 · p. 25

I ALGORITHM

• Algorithm 1 presents the overall training and inference process for GeoF.Source: I ALGORITHM · p. 25

J COMPLEXITY ANALYSIS

• The overall cost is O(L · d · m · |E| + L · d · (d + m2) · n), linear in the numbers of nodes and edges.The expression combines edge-level propagation with node-level geometry and feature operations.Source: J COMPLEXITY ANALYSIS · p. 26
• Block-diagonal parameterization reduces node-wise geometric operations from O(d3) to O(d · m2).The feature dimension is partitioned into B blocks of size m, with d = Bm.Source: J COMPLEXITY ANALYSIS · pp. 25–26
• Atlas initialization costs O(n · K · d · m), while each recurrent step adds edge-level, geometry-update, and shared feature-transformation costs.Per-step costs are O(|E| · d · m), O(n · d · m2), and O(n · d2), respectively.Source: J COMPLEXITY ANALYSIS · pp. 25–26

K.1 CROSS-TASK AGGREGATE ANALYSIS

• GeoF has the strongest average in every task category and overall, ranks first in all 18 settings, and has positive gains with all 14 pairwise comparisons significant after Holm correction.Gains are distributed across tasks and datasets rather than concentrated in a few favorable settings.Source: §K.1 · pp. 26–27

K.4 EFFICIENCY AND RESOURCE CONSUMPTION ANALYSIS

• On node-classification datasets, GeoF trains faster than ARGNN; on graph-classification datasets, it takes more time and generally uses more memory than compared baselines.Its overhead relative to ARGNN remains a moderate constant factor rather than growing with graph size.Source: Table 8 · p. 27, Table 9 · p. 27, §K.4 · pp. 27–28

K.2 MORE ABLATION STUDY

• Across PubMed, Computers, BBBP, and ogbg-molhiv, freezing geometry causes the largest ablation drop, while removing second-order feedback usually causes the next largest.Frame transport, structural signatures, and atlas initialization yield smaller, dataset-dependent decreases.Source: §K.2 · p. 27

K.3 MORE SENSITIVITY STUDY

• Performance stays within a relatively narrow range across moderate block counts and prototype numbers, with mild declines at excessive capacity.The sensitivity tests cover PubMed and Mutagenicity; increasing geometric granularity or atlas size produces no systematic improvement.Source: §K.3 · p. 27

L VISUALIZATION

• On CiteSeer, GeoF’s highlighted class cluster is more compact than ARGNN’s, while enabling geometric correction yields clearer grouping in the highlighted region.The correction comparison uses a shared 3D t-SNE projection.Source: L VISUALIZATION · p. 28, Figure 3 · p. 28