- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The authors of the paper propose a differentiable graph lifting framework for constructing higher-order structures based on sheaf-inspired local relational inconsistency. The method introduces learnable edge-dependent transformations to compare node representations in shared spaces, moving beyond conventional connectivity- and similarity-based lifting criteria. Edge-level inconsistencies are aggregated over candidate cycles, which are subsequently weighted through a differentiable gating mechanism to construct higher-order structures. The framework is evaluated on homophilic and heterophilic graphs using several topological neural network architectures and graph lifting baselines.
Critical strengths
- The authors address a limitation of existing graph lifting approaches, which often rely on connectivity or feature similarity to construct higher-order structures. The proposed use of sheaf-inspired local relational inconsistency, modeled through edge-dependent transformations, provides an alternative criterion for identifying meaningful higher-order interactions, particularly in heterophilic settings
- The proposed framework achieves consistent performance improvements across different topological neural network architectures, with particularly strong results on heterophilic datasets. These findings provide empirical evidence of the effectiveness of the proposed lifting strategy across different backbones
Critical weaknesses
- Although the authors provide a theoretical complexity analysis, the paper lacks an empirical comparison of computational costs with existing lifting approaches. In particular, the additional training time and memory consumption introduced by the proposed framework are not evaluated. This limitation is particularly relevant given that the experiments focus on relatively small graphs, leaving the scalability of the proposed approach to larger graphs unclear and making it difficult to assess whether the reported performance improvements justify the additional computational overhead
- The proposed cycle-level inconsistency is computed as the average of edge-level disagreement scores. However, different cycles with distinct relational patterns may have the same average inconsistency, resulting in identical gating weights. This may limit the ability of the proposed lifting criterion to distinguish different higher-order structures
Questions for authors
- What is the computational cost of the proposed framework compared with other lifting approaches? It would be useful to provide a comparison of training time and memory requirements
- Since the proposed inconsistency measure averages edge-level scores, different cycles with distinct relational patterns may receive identical gating weights. How does this limitation affect the ability of the framework to distinguish different higher-order structures?
- The experimental evaluation focuses on established undirected graph learning approaches. Recent methods, such as [1], have explored directional higher-order representations. How do the authors position their framework with respect to these approaches? Could the proposed lifting mechanism be extended to directed higher-order structures?
[1] Lecha, Manuel, et al. "Directed semi-simplicial learning with applications to brain activity decoding." International Conference on Learning Representations. Vol. 2026. 2026.
5 comments
W2 & Q2) Expressivity of cycle-level inconsistency aggregation
A) Mean aggregation is not injective: cycles with different distributions or orders of edge inconsistencies may have the same mean and therefore the same gate. It summarizes length-normalized disagreement; it is not a complete description of within-cycle relational patterns.
Importantly, identical gating weights do not necessarily imply identical higher-order representations. As defined in Eqs. (9)–(10), each candidate retains its own edge–cell incidence structure and aggregated edge features. Consequently, cycles assigned the same scalar weight can still contribute differently to higher-order message passing through their distinct constituent edges and cell representations. Nevertheless, the gating criterion itself cannot distinguish cycles based solely on differences in the distribution or ordering of edge inconsistencies when their means coincide.
Aggregation ablation. We compared mean, max, and mean + std on Cora, Texas, Cornell, and Actor using CWN and EDGNN:
\delta_c^{\mathrm{max}} &= \max_{e\in c}\delta_e,\\\\ \delta_c^{\mathrm{mean+std}} &= \operatorname{mean}_{e\in c}\delta_e + \operatorname{std}_{e\in c}\delta_e. \end{aligned}$$ All variants were retrained using identical candidate structures, backbone architectures, model capacities, data splits, and optimization settings. **Table 1. Corrected node classification accuracy (%) for cycle aggregation variants.** | Backbone | Dataset | Mean | Max | Mean + Std | |:---|:---|---:|---:|---:| | CWN | Cora | **87.50** | 86.72 | 86.36 | | CWN | Texas | **80.80** | 78.72 | 76.41 | | CWN | Cornell | **73.70** | 73.21 | 73.15 | | CWN | Actor | **38.30** | 37.91 | 38.01 | | CWN | Avg. | **70.08** | 69.14 | 68.48 | | EDGNN | Cora | 87.50 | **88.09** | 87.46 | | EDGNN | Texas | 78.60 | **79.71** | 79.15 | | EDGNN | Cornell | **71.60** | 66.60 | 68.86 | | EDGNN | Actor | 37.80 | **38.39** | 38.07 | | EDGNN | Avg. | **68.88** | 68.20 | 68.39 | *Avg. denotes the unweighted average across Cora, Texas, Cornell, and Actor. Full results will be reported in the revised Appendix.* **Distributional analysis.** On Actor/CWN, 8,555 of 12,278 cycle pairs (70%) with mean inconsistencies differing by less than $10^{-3}$ have a standard-deviation difference greater than 0.05. Thus mean aggregation loses distributional detail, even though distinct cycles still retain different incidence and feature information. Incorporating standard deviation did not consistently improve downstream accuracy in the evaluated settings. **Interpretation.** Mean aggregation provides a simple, differentiable, and length-normalized summary of relational disagreement, achieving the highest average accuracy across the evaluated aggregation rules for both backbones. --- **Q3) Relationship to directed semi-simplicial learning and applicability to directed graphs.** **A)** Lecha et al. [4] study directed higher-order representation through semi-simplicial structures and face-map-based message passing. Our focus is complementary: learning relation-aware weights for candidate higher-order structures. **Distinction.** SSNs specify direction-aware higher-order cells and message-passing operators; SheafLifting specifies a learnable edge-conditioned criterion for candidate weighting. A full integration would require suitable directed candidates, incidence/face maps, and a direction-aware backbone rather than assuming our current undirected construction is already semi-simplicial. **Directional information.** Our two endpoint restriction maps depend on oppositely ordered inputs $[h_u\|h_v]$ and $[h_v\|h_u]$, allowing distinct endpoint-conditioned transformations. The ordered edge-feature concatenation $h_e=\psi_\theta([h_u\|h_v\|\lvert h_u-h_v\rvert])$ can preserve source/target roles in a directed extension, together with direction-aware candidate construction and message passing. **Revision plan.** We will clarify in the revised discussion how the learned relational criterion could complement directed semi-simplicial representations and specify the directed candidates, face maps, and backbone operators required for such an extension. The present experiments focus on undirected graphs.I thank the authors for their detailed responses and additional experiments, which address several of my concerns and help clarify the proposed approach. However, my concern regarding scalability remains unresolved. The evaluation is still limited to six relatively small datasets (the largest being Actor, with only 7,600 nodes), and the substantial preprocessing time reported for Actor raises concerns about applicability to larger graphs. I would encourage a more extensive evaluation on larger datasets, potentially including Yelp and Trivago from DHG-Bench [1], to better assess both the scalability and the benefits of the proposed method in more challenging settings. While I appreciate the improvements made during the rebuttal, I maintain my original rating.
[1] DHG-Bench: A Comprehensive Benchmark for Deep Hypergraph Learning.
W1 & Q1) Empirical computational cost and scalability.
A) We thank the reviewer for highlighting the need to evaluate computational overhead beyond theoretical complexity. To address this concern, we conducted additional runtime and memory profiling across six datasets and four TNN backbones (EDGNN, SCN, CWN, and CCXN), comparing SheafLifting against static cycle lifting and the official ∂lift implementation.
Importantly, static cycle lifting uses exactly the same candidate structures and backbone architecture as SheafLifting, with uniform cycle weights (wc=1). This controlled comparison directly isolates the additional computational cost of our restriction-map-based scoring and adaptive cycle weighting. We measured complete training steps, including forward computation, loss, backward computation, and optimizer updates. All measurements were performed sequentially with GPU-process monitoring, warm-up, and repeated synchronized trials.
Table 1. Training-step latency (ms) and peak CUDA allocated memory (MB).
Across all 24 dataset–backbone configurations, SheafLifting incurs approximately 1.42–1.66× training-step overhead relative to static cycle lifting. On smaller graphs such as Texas, the additional GPU memory is negligible (at most 1 MB across the four backbones). On Actor, the memory overhead is more pronounced; for example, CWN increases from 342 MB to 603 MB. These results quantify the practical cost of differentiable relational scoring rather than assuming negligible overhead.
CPU candidate preprocessing was profiled separately. On Actor, the NetworkX
cycle_basisalternative yields 3,596 candidates in 0.466 s, whereas the mainminimum_cycle_basisconstruction yields 19,004 candidates in 175.4 s. These differ in candidate pool and should not be interpreted as a matched-candidate timing comparison.Our shared-basis parameterization avoids learning independent dense restriction maps for individual edges, reducing the number of learnable transformation parameters. Nevertheless, we agree that this parameter efficiency does not establish end-to-end scalability. While the present profiling provides empirical evidence of the computational trade-offs across the evaluated datasets, performance and efficiency on substantially larger graphs remain to be established.
We will include the complete results for all six datasets and four backbones, including inference latency, preprocessing time, and peak GPU memory, in the revised Appendix. For the full profiling comparison, refer to Q4 of Reviewer 7RUG.