acceptodds
Under review as a conference paper at ICLR 2027

Restoring Component Locality in Spectral Positional Encodings

Abstract

Spectral positional encodings should preserve the representation of a component when an unrelated component is added. A fixed-rank prefix of a merged Laplacian spectrum can violate this principle: the added component competes for the same eigenvector slots. We formalize Component Locality, prove that a global prefix cannot guarantee it, and provide a sufficient direct-sum criterion. Component- local selection restores the identity by assigning each component its own spectral quota. We test this mechanism with shared checkpoints and a component-local downstream path on real graphs placed in controlled disjoint unions. CL-SPE restores encoding, hidden-state, and prediction locality in an independent holdout across all seven main cells; six cells show practically significant prediction-drift reductions. BudgetMatched and ClusterComplete separate total budget, allocation, and exact-eigenspace effects. An additional USPTO study establishes the mechanism on natural reaction graphs: 49.17% of nonboundary primary training reactions exhibit displacement under BudgetMatched. Component-local selection reduces reaction-macro kernel error from 0.206 under BudgetMatched to numerical zero and restores coverage to 1. Reaction-center prediction meets the overall noninferiority criterion on all 3,512 primary test reactions. Together, controlled interventions and natural reaction graphs establish component-wise allocation as a concrete design principle for spectral positional encodings.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph representation learning, spectral positional encodings, Laplacian eigenvectors, graph transformers, component locality, disconnected graphs

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_s4WrOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the component locality problem in spectral positional encodings (PEs). The authors show that global top-k eigenvector selection can change the representation of a component when an unrelated component is added. They formalize this problem and provide theoretical analysis. To address it, they propose CL-SPE, which selects eigenvectors independently for each connected component. Experiments on synthetic and real graphs show that CL-SPE can restore spectral and prediction locality. Further experiments on USPTO reaction graphs confirm that this problem exists in real applications. However, CL-SPE does not show significant improvement in downstream task performance.

Critical strengths
  1. Clear problem formulation and theoretical analysis. The paper identifies a component locality issue caused by global top-k spectral selection. It provides a formal definition, theoretical counterexamples, and sufficient conditions for restoring locality. This gives a clear explanation of a limitation in existing spectral positional encodings and provides a useful perspective for designing component-local representations.
Critical weaknesses
  1. Unclear and disorganized presentation. The overall presentation is somewhat confusing and needs careful polishing. The motivation and main problem are not explained clearly enough, and many technical terms are introduced without sufficient explanation. For example, the terms such as "GlobalSelect-LocalSPE", "BudgetMatched", "ClusterComplete", and "contextual-SPE" in introduction without clearly explaining what they mean or how they differ. This makes the paper difficult to understand. The authors should better organize the presentation, explain the terminology more clearly, and improve the overall readability.

  2. Limited methodological novelty and practical benefits. The proposed method mainly replaces global top-k selection with component-wise selection, which is quite straightforward. A simple method is not necessarily a weakness if it brings meaningful practical benefits. However, most experiments focus on KLE and prediction drift, where the improvements are largely expected from the experiment design. More importantly, the method does not show significant improvements in downstream task performance, which makes its overall contribution less convincing.

Questions for authors
  1. What is the main novelty of the proposed method? The idea of selecting eigenvectors separately for each connected component seems quite straightforward, especially given the block-diagonal structure of the Laplacian. Could the authors explain more clearly how CL-SPE differs from existing component-wise spectral processing methods, and what new insights or advantages it provides beyond this simple change?

  2. Why does restoring component locality matter in practice? The experiments show that CL-SPE can reduce KLE and prediction drift to nearly zero, but these improvements are largely expected from the experiment design. Moreover, the USPTO experiments do not show significant improvements in downstream prediction performance. Could the authors explain why component locality is important for practical graph learning tasks, and what benefits it brings beyond improving these locality metrics?

Reviewer_FVc2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors study a problem with spectral positional encodings: when choosing bottom-k laplacian eigenvectors of a graph C for node positional encoding, the addition of a separate disjoint graph D could introduce additional eigenvectors, that end up displacing the eigenvectors that would be chosen for C. This is intuitively wrong because D and C are disconnected and thus should not affect each other's structural coordinates. The authors give a rigorous proof-by-construction that when D is a sufficiently long path, it can displace every target mode from a finite global prefix. The authors then propose KLE, a metric for measuring how many modes of a component gets lost when adding a disjoint graph. The authors propose a simple solution (CL-SPE): compute the k eigenvectors separately for each component, independently of the other components, and each component gets its own quota. Theorem 1 shows that this preserves locality. Empirical results show that CL-SPE improves locality, as well as downstream task loss in some cases.

Critical strengths
  1. The key issue is clearly stated, the proof and the construction are clean and easy to understand.
  2. The experiments support the theory that CL-SPE preserves locality.
Critical weaknesses
  1. The USPTO experiment does not establish a clear downstream advantage over alternatives.
  2. Table 2 does show an advantage of CL-SPE, demonstrating that CL-SPE makes the model more dobust against artificially adding unrelated components at test-time. However, this does not show that CL-SPE improves downstream performance without this train-test-mismatch. Additionally, we really need to see the inclusion of BudgetMatched in Table 2, since I think it is an informative baseline that controls for the (likely beneficial) effect of increased spectral budget.
  3. The theory is somewhat basic, and seems to follow from the block-diagonal laplacian structure of disconnected graphs.
Questions for authors

see weaknesses.

Reviewer_E6rROpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the component locality of spectral positional encodings, that is, given a graph component, whether the spectral positional encodings restricted on this component stay the same when another unrelated disconnected component is added. It identifies that the top-K eigenvector selection approach does not satisfy component locality and propose a CL-SPE, that applies Stable Positional Encodings to each component individually and then aggreate the representations. Experiments on synthetic and real-world graphs demonstrate the proposed approach is stable under disconnected component addition.

Critical strengths
  • The paper identifies an interesting consistency problem of spectral positional encodings when applied to multi-component graphs.
  • The main theorem 1 establishes sufficient conditions for an eigenvector selection policy to satisfy component locality, and a simple algorithm CL-SPE is proposed to satisfy such conditions.
Critical weaknesses
  • Novelty concern: most other theoretical results follow directly from standard properties of block-diagonal matrices and orthogonal projections. For instance, Proposition 3 simply applies a standard identity for orthogonal projectors onto subspaces. Besides, the proposed CL-SPE essentially applies existing SPE techiqnues to individual components.
  • The evaluation on downstream tasks are mainly on the representation robustness to component addition, not the actual performance metrics (except for Table 3 comparing prediction accuracy, but it seems the difference across different methods are minor). It is unclear if the proposed method is indeed improving the baselines.
Questions for authors
  • Are there real-world tasks that requires num-of-component generalization and CL-SPE can thereby show actual performance improvement consistently?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.