Introduction
Graph Neural Networks (GNNs) are the standard tool for relational learning [4 ] . Several of the most widely used families rest on a geometric prior rooted in Riemannian manifolds, typically Euclidean space, in which the metric tensor is strictly positive definite and connected nodes are therefore “close” and expected to share representations. The prior is explicit in three places. Graph convolution read as heat diffusion requires a positive semi-definite operator [5 ] ; hyperbolic architectures such as HGCN [6 ] and HAT [47 ] embed features on positive-definite Riemannian manifolds; and dot-product [38 ] and GAT-style [39 ] attention use Euclidean inner products of projected features, which admit no negative squared distance. The assumption is not universal. Signed attention [1 ] and sheaf models [2 ] are natural counterexamples, and precisely because they work, the geometry deserves to be treated as a modeling choice rather than a default.
While this Riemannian inductive bias serves well for homophilic graphs, it creates a fundamental geometric mismatch when applied to heterophilic graphs, where edges often denote dissimilarity or structural repulsion [27 ] [49]. Heterophily-adapted GNNs address this architecturally with high-frequency spectral filters [11 , 7 , 14 ] or signed aggregation weights [1 , 44 , 41 ] . These are empirically effective, but the space they act in stays positive definite, so repulsion is expressed by distorting an embedding built for attraction [36 ] .
We read heterophily geometrically, whereas the prevailing view is statistical. Non-Euclidean GNNs [6 , 42 ] adapt curvature to hierarchical structure. We argue that some heterophilic graphs call instead for an indefinite metric, which admits negative squared distances [17 ] and so can sharpen across one class pair while smoothing across another. We diagnose the geometry the labels induce and then learn the metric inside it. The diagnostic is the Graph Signature Index (s G s_G s G ), a spectral invariant of the label topology. The model is the Pseudo-Riemannian Attention Network (PRAT), whose attention logit is a signed squared pseudo-distance under a diagonal metric initialized from s G s_G s G and learned thereafter.
Theoretical Framework: The Geometry of Heterophily
Graph Signature Index
Previous studies proposed measures of graph homophily, including the node homophily index h V h_V h V [27 ] and edge homophily index h E h_E h E [50] described in Appendix § 8 .5. Their values, ranging between 0 and 1, quantify the likelihood that nodes with identical labels are connected by edges (see Appendix § 8 .§ 24 ). The graph signature index refines these indices by recording the signature of the eigenvalues of a real symmetric matrix constructed from a graph with node labels.
Definition 2.1. Let G : = ( V , E ) \mathcal{G} := (\mathcal{V}, \mathcal{E}) G := ( V , E ) be an undirected graph without self-loops. Let l : V → L = { 1 , 2 , ⋯ , ∣ L ∣ } l : \mathcal{V} \to L = \{1, 2, \cdots, |L|\} l : V → L = { 1 , 2 , ⋯ , ∣ L ∣ } be the ground-truth node label function assigning each node to one of ∣ L ∣ |L| ∣ L ∣ classes. The graph signature matrix S G S_G S G is the ∣ L ∣ × ∣ L ∣ |L| \times|L| ∣ L ∣ × ∣ L ∣ real symmetric matrix whose ( i , j ) (i,j) ( i , j ) -th entry is given as
s i , j : = ∣ { ( v , w ) ∈ E ∣ l ( v ) = i , l ( w ) = j } ∣ ∣ { v ∈ V ∣ l ( v ) = i } ∣ ⋅ ∣ { v ∈ V ∣ l ( v ) = j } ∣ (1) s_{i,j} := \frac{|\{(v,w) \in\mathcal{E} \mid l(v) = i,l(w) = j\}|}{|\{v \in\mathcal{V} \mid l(v) = i\}| \cdot|\{v \in\mathcal{V} \mid l(v) = j\}|} \tag*{(1)} s i , j := ∣ { v ∈ V ∣ l ( v ) = i } ∣ ⋅ ∣ { v ∈ V ∣ l ( v ) = j } ∣ ∣ {( v , w ) ∈ E ∣ l ( v ) = i , l ( w ) = j } ∣ (1) The graph signature index of G \mathcal{G} G , denoted as s G s_G s G , is the 3-tuple consisting of the number of positive, zero, and negative eigenvalues of S G S_G S G .
Because S G S_G S G is a real symmetric matrix, every eigenvalue of S G S_G S G is real. Sylvester’s law of inertia shows that the graph signature index is invariant under any invertible linear change of coordinates on R ∣ L ∣ \mathbb{R}^{|L|} R ∣ L ∣ .
Theorem 2.2 ([34 ] ). Let S ∈ R n × n S \in\mathbb{R}^{n \times n} S ∈ R n × n be a real symmetric matrix. Then there exists a diagonal matrix D ∈ R n × n D \in\mathbb{R}^{n \times n} D ∈ R n × n and an invertible matrix W ∈ R n × n W \in\mathbb{R}^{n \times n} W ∈ R n × n such that S = W T D W S = W^{T} D W S = W T D W , where ( ⋅ ) T (\cdot)^T ( ⋅ ) T denotes the transpose of a square matrix. The numbers of positive, zero, and negative eigenvalues of S S S are invariant under the change of coordinates.
Each ( i , j ) (i,j) ( i , j ) -th entry of S G S_G S G is the expected probability that a node with a preassigned label j j j lies in the depth 1 unfolding tree rooted at a node with label i i i ; see Appendix § 8 .2. The signature of the eigenvalues of S G S_G S G can be used to determine whether graphs with discrete labels are heterophilic or homophilic. For example, graphs with two discrete node labels and E ≠ ∅ \mathcal{E} \ne\varnothing E = ∅ have three types of s G s_G s G ; see Appendix § 8 .3. Appendix § 8 .4 provides heuristics on the density of these three graph types.
The following theorem relates the edge homophily level h E h_E h E to the graph signature index s G s_G s G .
Theorem 2.3 (Critical Homophily Threshold). Assume class i i i contains n i n_i n i nodes and N = ∑ i = 1 ∣ L ∣ n i N = \sum_{i=1}^{|L|} n_i N = ∑ i = 1 ∣ L ∣ n i . Under a proportional allocation model, the expected graph signature matrix S G S_G S G has eigenvalues:
λ 1 > 0 , λ 2 = ⋯ = λ ∣ L ∣ = 2 ∣ E ∣ ( h E N 2 − ∑ k = 1 ∣ L ∣ n k 2 ) ∑ k = 1 ∣ L ∣ n k 2 ⋅ ( N 2 − ∑ k = 1 ∣ L ∣ n k 2 ) . (2) \lambda_1 > 0,\qquad\lambda_2 = \cdots= \lambda_{|L|} = \frac{2|\mathcal{E}|\left(h_E N^2 - \sum_{k=1}^{|L|} n_k^2\right)}{\sum_{k=1}^{|L|} n_k^2 \cdot\left(N^2 - \sum_{k=1}^{|L|} n_k^2\right)}. \tag*{(2)} λ 1 > 0 , λ 2 = ⋯ = λ ∣ L ∣ = ∑ k = 1 ∣ L ∣ n k 2 ⋅ ( N 2 − ∑ k = 1 ∣ L ∣ n k 2 ) 2∣ E ∣ ( h E N 2 − ∑ k = 1 ∣ L ∣ n k 2 ) . (2) The critical homophily threshold is given by: h E ∗ = ∑ k = 1 ∣ L ∣ n k 2 N 2 h_E^* = \frac{\sum_{k=1}^{|L|} n_k^2}{N^2} h E ∗ = N 2 ∑ k = 1 ∣ L ∣ n k 2 . For balanced classes where n i = n n_i = n n i = n for all i i i , this reduces to h E ∗ = 1 / ∣ L ∣ h_E^* = 1/|L| h E ∗ = 1/∣ L ∣ .
While Theorem 2.3 reveals a correlation between edge homophily and graph signature under idealized conditions, homophily indices cannot fully characterize the spectral properties of S G S_{\mathcal{G}} S G . We formalize this limitation by showing that no value of h E h_E h E or h V h_V h V in ( 0 , 1 ) (0,1) ( 0 , 1 ) rules out a negative eigenvalue of S G S_{\mathcal{G}} S G .
Theorem 2.4 (Limitation of Homophily Indices). For every rational h ∈ ( 0 , 1 ) h \in(0,1) h ∈ ( 0 , 1 ) , there exists a graph G : = ( V , E ) \mathcal{G} := (\mathcal{V},\mathcal{E}) G := ( V , E ) with discrete node labels such that h E = h V = h h_E = h_V = h h E = h V = h and S G S_{\mathcal{G}} S G has a negative eigenvalue.
Limitations of Riemannian GNNs
We reformulate the problem of analyzing heterophilic graphs using pseudo-Riemannian manifolds. A pseudo-Riemannian manifold ( M , g ) (\mathcal{M},g) ( M , g ) is a smooth manifold endowed with a metric tensor g p : T p M × T p M → R g_p : T_p\mathcal{M} \times T_p\mathcal{M} \to\mathbb{R} g p : T p M × T p M → R which defines a non-degenerate symmetric bilinear form over the tangent space T p M T_p\mathcal{M} T p M at each point p ∈ M p \in\mathcal{M} p ∈ M . A pseudo-Riemannian manifold is Riemannian if the tensor g p g_p g p is positive-definite for every point p ∈ M p \in\mathcal{M} p ∈ M . We keep this terminology for a symmetric bilinear form that is allowed to be degenerate. This is deliberate: the form on the hidden space is a pullback of rank at most ∣ L ∣ |L| ∣ L ∣ , hence degenerate whenever the hidden width exceeds the number of classes, and it depends on a hidden vector only through its image in L \mathcal{L} L . Non-degeneracy returns on L \mathcal{L} L itself whenever s G s_{\mathcal{G}} s G has no zero eigenvalue, and Theorem 2.5 counts only negative eigenvalues, so degeneracy does not affect it. We focus on the h h h -dimensional manifold M \mathcal{M} M endowed with a metric tensor g p : = S ∈ R h × h g_p := S \in\mathbb{R}^{h \times h} g p := S ∈ R h × h for some fixed real symmetric matrix S S S at every point p ∈ M p \in\mathcal{M} p ∈ M , which defines the following quadratic form on tangent vectors w 1 , w 2 ∈ T p M w_1,w_2 \in T_p\mathcal{M} w 1 , w 2 ∈ T p M : g p ( w 1 , w 2 ) : = w 1 T S w 2 g_p(w_1,w_2) := w_1^{\mathsf{T}} S w_2 g p ( w 1 , w 2 ) := w 1 T S w 2 [24 , 37 ] .
Let G : = ( V , E ) \mathcal{G} := (\mathcal{V},\mathcal{E}) G := ( V , E ) be a graph with continuous node attributes X : V → R h X : \mathcal{V} \to\mathbb{R}^h X : V → R h and embedded node labels l : V → R ∣ L ∣ l : \mathcal{V} \to\mathbb{R}^{|L|} l : V → R ∣ L ∣ . We set the metric tensor over R ∣ L ∣ \mathbb{R}^{|L|} R ∣ L ∣ to be the graph signature matrix S G S_{\mathcal{G}} S G of the given graph G \mathcal{G} G . By doing so, we regard the graph G \mathcal{G} G as a subspace of some smooth manifold M \mathcal{M} M admitting a smooth function f : M → L ≅ R ∣ L ∣ f : \mathcal{M} \to\mathcal{L} \cong\mathbb{R}^{|L|} f : M → L ≅ R ∣ L ∣ , whose metric tensor is the pullback of metric tensor f ∗ S G f^*S_{\mathcal{G}} f ∗ S G . Given a metric tensor g g g on L \mathcal{L} L , its pullback f ∗ g f^*g f ∗ g on M \mathcal{M} M is defined as
( f ∗ g ) p ( v , w ) : = g f ( p ) ( T p f ( v ) , T p f ( w ) ) . (f^*g)_p(v,w) := g_{f(p)}(T_p f(v),T_p f(w)). ( f ∗ g ) p ( v , w ) := g f ( p ) ( T p f ( v ) , T p f ( w )) .
Because S G S_{\mathcal{G}} S G can have negative eigenvalues, M \mathcal{M} M is a pseudo-Riemannian manifold, thereby covering a class of manifolds which are not Riemannian. The theorem below, proved in Appendix § 8 .§ 25 , makes this observation explicit.
Theorem 2.5 (Geometric Mismatch). Let M \mathcal{M} M and L \mathcal{L} L be differentiable manifolds and f : M → L f : \mathcal{M} \to\mathcal{L} f : M → L be a smooth map. If S G S_{\mathcal{G}} S G defined on L \mathcal{L} L is indefinite and the pushforward T p f : T p M → T f ( p ) L T_p f : T_p\mathcal{M} \to T_{f(p)}\mathcal{L} T p f : T p M → T f ( p ) L is surjective for every p ∈ M p \in\mathcal{M} p ∈ M , then there exists a diffeomorphism ϕ : L → L \phi: \mathcal{L} \to\mathcal{L} ϕ : L → L such that the pullback of the Euclidean metric I I I , the identity form, satisfies ( ϕ ∘ f ) ∗ I = f ∗ S G (\phi\circ f)^*I = f^*S_{\mathcal{G}} ( ϕ ∘ f ) ∗ I = f ∗ S G .
Theorem 2.5 establishes a geometric mismatch between the Riemannian prior and graphs whose S G S_{\mathcal{G}} S G is indefinite. It proves that this geometric mismatch is intrinsic and cannot be bridged by any smooth transformation of the Riemannian space. Surjectivity of the pushforward is what carries the indefiniteness through to the pullback: the image of T p f T_p f T p f is then all of T f ( p ) L T_{f(p)}\mathcal{L} T f ( p ) L , so a negative direction of S G S_{\mathcal{G}} S G has a preimage. Injectivity alone would not suffice, since an injective map can pull an indefinite form back to a degenerate one. In our architecture T p f T_p f T p f is the projection W W W of Equation (4) , surjective exactly when rank W = ∣ L ∣ \operatorname{rank} W = |L| rank W = ∣ L ∣ . Every configuration we report has h ′ > ∣ L ∣ h' > |L| h ′ > ∣ L ∣ , so the hypothesis holds for almost every W W W . Appendix A.8 discusses further implications for heterophilic graphs.
Method: Pseudo-Riemannian Attention Network (PRAT)
Pseudo-Riemannian Edge Attention using continuous features
We define the tangent attention scores of a finite graph G \mathcal{G} G , which generalize the notion of attention scores used in graph attention networks (GAT) and attention-transformers. The geometric structure endowed by the pseudo-metric tensor g g g allows us to compute the numerical relation between two edges of a finite directed graph G \mathcal{G} G by comparing their derivatives. Given a curve γ : [ 0 , 1 ] → M \gamma: [0,1] \to\mathcal{M} γ : [ 0 , 1 ] → M , the derivative of the curve at time t = t 0 t=t_0 t = t 0 , denoted as γ ′ ( t 0 ) \gamma'(t_0) γ ′ ( t 0 ) , is an element of the tangent space T γ ( t 0 ) M T_{\gamma(t_0)}\mathcal{M} T γ ( t 0 ) M . Given two curves γ 1 , γ 2 : [ 0 , 1 ] → M \gamma_1,\gamma_2 : [0,1] \to\mathcal{M} γ 1 , γ 2 : [ 0 , 1 ] → M , the two derivatives γ 1 ′ ( t 0 ) \gamma_1'(t_0) γ 1 ′ ( t 0 ) and γ 2 ′ ( t 0 ) \gamma_2'(t_0) γ 2 ′ ( t 0 ) may not lie in the same tangent space. To overcome this, we define a function γ 12 : [ 0 , 1 ] × [ 0 , 1 ] → M \gamma_{12} : [0,1] \times[0,1] \to\mathcal{M} γ 12 : [ 0 , 1 ] × [ 0 , 1 ] → M which satisfies γ 12 ( t , 0 ) = γ 2 ( t ) \gamma_{12}(t,0)=\gamma_2(t) γ 12 ( t , 0 ) = γ 2 ( t ) and γ 12 ( t , 1 ) = γ 1 ( t ) \gamma_{12}(t,1)=\gamma_1(t) γ 12 ( t , 1 ) = γ 1 ( t ) . For each time t = t 0 t=t_0 t = t 0 , the parallel transport operator Γ γ 12 ( t 0 , 1 ) : T γ 2 ( t 0 ) M → T γ 1 ( t 0 ) M \Gamma_{\gamma_{12}(t_0,1)} : T_{\gamma_2(t_0)}\mathcal{M} \to T_{\gamma_1(t_0)}\mathcal{M} Γ γ 12 ( t 0 , 1 ) : T γ 2 ( t 0 ) M → T γ 1 ( t 0 ) M moves any tangent vector w 2 ∈ T γ 2 ( t 0 ) M w_2 \in T_{\gamma_2(t_0)}\mathcal{M} w 2 ∈ T γ 2 ( t 0 ) M to the tangent vector Γ γ 12 ( t 0 , 1 ) ( w 2 ) ∈ T γ 1 ( t 0 ) M \Gamma_{\gamma_{12}(t_0,1)}(w_2) \in T_{\gamma_1(t_0)}\mathcal{M} Γ γ 12 ( t 0 , 1 ) ( w 2 ) ∈ T γ 1 ( t 0 ) M along the curve γ 12 ( t 0 , s ) : { t 0 } × [ 0 , 1 ] → M \gamma_{12}(t_0,s): \{t_0\}\times[0,1]\to\mathcal{M} γ 12 ( t 0 , s ) : { t 0 } × [ 0 , 1 ] → M . After performing parallel transport, we define the tangent attention score between γ 1 \gamma_1 γ 1 and γ 2 \gamma_2 γ 2 . fig:1b illustrates how to compute a tangent attention score.
Definition 3.1. The tangent attention score between two curves γ 1 , γ 2 : [ 0 , 1 ] → M \gamma_1,\gamma_2:[0,1]\to\mathcal{M} γ 1 , γ 2 : [ 0 , 1 ] → M with a choice of a function γ 12 : [ 0 , 1 ] × [ 0 , 1 ] → M \gamma_{12}:[0,1]\times[0,1]\to\mathcal{M} γ 12 : [ 0 , 1 ] × [ 0 , 1 ] → M is
e γ 12 ( γ 1 , γ 2 ) : = ∫ 0 1 g γ 1 ( t ) ( γ 1 ′ ( t ) , Γ γ 12 ( t , 1 ) ( γ 2 ′ ( t ) ) ) d t . e_{\gamma_{12}}(\gamma_1,\gamma_2) := \int_0^1 g_{\gamma_1(t)}\left(\gamma_1'(t),\Gamma_{\gamma_{12}(t,1)}\left(\gamma_2'(t)\right)\right)\,\mathrm{d}t. e γ 12 ( γ 1 , γ 2 ) := ∫ 0 1 g γ 1 ( t ) ( γ 1 ′ ( t ) , Γ γ 12 ( t , 1 ) ( γ 2 ′ ( t ) ) ) d t .
By imposing suitable topological structures on finite directed graphs, we can compute a tangent attention score between two edges of a directed graph G : = ( V , E ) \mathcal{G}:=(\mathcal{V},\mathcal{E}) G := ( V , E ) (including self-loops) as a function of node features X : V → R h X:\mathcal{V}\to\mathbb{R}^h X : V → R h . See Appendix § 8 .§ 26 for details. We also choose a continuous function X γ : G → M X_\gamma:\mathcal{G}\to\mathcal{M} X γ : G → M which extends the node feature function X X X . Given two edges e 1 , e 2 ∈ E e_1,e_2\in\mathcal{E} e 1 , e 2 ∈ E with the corresponding paths γ e 1 , γ e 2 : [ 0 , 1 ] → R h \gamma_{e_1},\gamma_{e_2}:[0,1]\to\mathbb{R}^h γ e 1 , γ e 2 : [ 0 , 1 ] → R h , we define γ e 1 , e 2 ( t , s ) : = s ⋅ γ e 1 ( t ) + ( 1 − s ) ⋅ γ e 2 ( t ) \gamma_{e_1,e_2}(t,s):=s\cdot\gamma_{e_1}(t)+(1-s)\cdot\gamma_{e_2}(t) γ e 1 , e 2 ( t , s ) := s ⋅ γ e 1 ( t ) + ( 1 − s ) ⋅ γ e 2 ( t ) . Tangent attention scores are symmetric in their two edges. Section A.9 gives the argument. We can quantify the differences among node features of G \mathcal{G} G using these scores.
Definition 3.2. The tangent attention score matrix of G \mathcal{G} G , denoted as e G , γ e_{\mathcal{G},\gamma} e G , γ , is the ∣ E ∣ × ∣ E ∣ |\mathcal{E}|\times|\mathcal{E}| ∣ E ∣ × ∣ E ∣ real symmetric matrix whose ( e 1 , e 2 ) (e_1,e_2) ( e 1 , e 2 ) -th entry for e 1 , e 2 ∈ E e_1,e_2\in\mathcal{E} e 1 , e 2 ∈ E is the tangent attention score e γ e 1 , e 2 ( γ e 1 , γ e 2 ) e_{\gamma_{e_1,e_2}}(\gamma_{e_1},\gamma_{e_2}) e γ e 1 , e 2 ( γ e 1 , γ e 2 ) .
Using e G , γ e_{\mathcal{G},\gamma} e G , γ , we recover several classes of previously studied attention functions. The detailed version of the theorem stated below can be found in Appendix § 8 .§ 27 .
Theorem 3.3. There exist continuous extensions X γ : G → M X_\gamma:\mathcal{G}\to\mathcal{M} X γ : G → M such that e G , γ e_{\mathcal{G},\gamma} e G , γ respectively recovers dot-product attention, single-layer feedforward linear layer, and dynamic graph attention [38 , 39 , 3 ] .
Learnable Indefinite Metric
Because tangent attention scores encompass various types of previously studied attention scores, a wide class of novel graph attention networks can be constructed by carefully choosing the curves representing the edges of G \mathcal{G} G , choosing the symmetric matrix S S S , and choosing which subsets of entries of the tangent attention score matrix to use.
Building on this, our proposed Pseudo-Riemannian Attention Network (PRAT) architecture reformulates classical attention networks with tangent attention scores defined from the curve γ e [ 1 ] : [ 0 , 1 ] → M \gamma_e^{[1]}:[0,1]\to\mathcal{M} γ e [ 1 ] : [ 0 , 1 ] → M as shown in Theorem 3.3 and Appendix A.10. The following equation governs the PRAT algorithm.
h v ( i + 1 ) : = ⨁ k = 1 K σ ( ∑ w ∈ N v ∪ { v } α v , w [ i , k ] W v [ i , k ] h w ( i ) ) , h v ( 0 ) : = ψ e n c ( X ( v ) ) (3) h_v^{(i+1)} := \bigoplus_{k=1}^{K}\sigma\left(\sum_{w\in\mathcal{N}_v\cup\{v\}}\alpha_{v,w}^{[i,k]}W_v^{[i,k]}h_w^{(i)}\right),\qquad h_v^{(0)}:=\psi_{\mathrm{enc}}(X(v)) \tag*{(3)} h v ( i + 1 ) := k = 1 ⨁ K σ w ∈ N v ∪ { v } ∑ α v , w [ i , k ] W v [ i , k ] h w ( i ) , h v ( 0 ) := ψ enc ( X ( v )) (3)
For each 1 ≤ k ≤ K 1 \leq k \leq K 1 ≤ k ≤ K ,
α v , w [ i , k ] : = exp ( e ( h v ( i ) , h w ( i ) ) [ k ] ) ∑ u ∈ N v ∪ { v } exp ( e ( h v ( i ) , h u ( i ) ) [ k ] ) , e ( h v ( i ) , h u ( i ) ) [ k ] : = { Δ ( h v , u ( i ) ) T D [ i , k ] Δ ( h v , u ( i ) ) if u ∈ N v a [ i , k ] ( h v ( i ) ) T D [ i , k ] ( h v ( i ) ) if v = u \alpha_{v,w}^{[i,k]} := \frac{\exp(e(h_v^{(i)},h_w^{(i)})[k])}{\sum_{u \in\mathcal{N}_v \cup\{v\}} \exp(e(h_v^{(i)},h_u^{(i)})[k])}, \quad e(h_v^{(i)},h_u^{(i)})[k] := \begin{cases} \Delta(h_{v,u}^{(i)})^{\mathsf{T}}\mathbf{D}^{[i,k]}\Delta(h_{v,u}^{(i)}) & \text{if } u \in\mathcal{N}_v \\ a^{[i,k]}(h_v^{(i)})^{\mathsf{T}}\mathbf{D}^{[i,k]}(h_v^{(i)}) & \text{if } v=u \end{cases} α v , w [ i , k ] := ∑ u ∈ N v ∪ { v } exp ( e ( h v ( i ) , h u ( i ) ) [ k ]) exp ( e ( h v ( i ) , h w ( i ) ) [ k ]) , e ( h v ( i ) , h u ( i ) ) [ k ] := { Δ ( h v , u ( i ) ) T D [ i , k ] Δ ( h v , u ( i ) ) a [ i , k ] ( h v ( i ) ) T D [ i , k ] ( h v ( i ) ) if u ∈ N v if v = u
where N v \mathcal{N}_v N v is the set of nodes adjacent to the node v v v , Δ ( h v , u ( i ) ) \Delta(h_{v,u}^{(i)}) Δ ( h v , u ( i ) ) is equal to h v ( i ) − h u ( i ) h_v^{(i)} - h_u^{(i)} h v ( i ) − h u ( i ) given u ∈ N v u \in\mathcal{N}_v u ∈ N v , and σ \sigma σ is the nonlinear activation function. ψ e n c : R h → R h ′ \psi_{enc} : \mathbb{R}^{h} \to\mathbb{R}^{h'} ψ e n c : R h → R h ′ is a learnable function (e.g., multilayer perceptron) that maps node features to hidden states of dimension h ′ h' h ′ . The a [ i , k ] a^{[i,k]} a [ i , k ] are learnable self-loop weights playing the role of a 2 v a_2^v a 2 v in (40) , calibrated in Appendix F.3, and D [ i , k ] ∈ R h ′ × h ′ \mathbf{D}^{[i,k]} \in\mathbb{R}^{h' \times h'} D [ i , k ] ∈ R h ′ × h ′ are symmetric matrices that serve as the metric tensor.
In Appendix B, we conceptualize the learning process of PRAT as a sequence of geometric transformations, from which we derive D [ l , k ] \mathbf{D}^{[l,k]} D [ l , k ] for the k k k -th head at layer l l l as follows, where W [ l , k ] ∈ R ∣ L ∣ × h ′ \mathbf{W}^{[l,k]} \in\mathbb{R}^{|L| \times h'} W [ l , k ] ∈ R ∣ L ∣ × h ′ is a learnable weight matrix, and S ∣ L ∣ ∈ R ∣ L ∣ × ∣ L ∣ \mathbf{S}^{|L|} \in\mathbb{R}^{|L| \times|L|} S ∣ L ∣ ∈ R ∣ L ∣ × ∣ L ∣ is a pseudo-metric on the latent manifold.
D [ l , k ] = ( W [ l , k ] ) T S ∣ L ∣ W [ l , k ] . (4) \mathbf{D}^{[l,k]} = \left(\mathbf{W}^{[l,k]}\right)^{\mathsf{T}}\mathbf{S}^{|L|}\mathbf{W}^{[l,k]}. \tag*{(4)} D [ l , k ] = ( W [ l , k ] ) T S ∣ L ∣ W [ l , k ] . (4)
Following the theoretical motivation in § 2.2 , we instantiate the pseudo-metric S ∣ L ∣ \mathbf{S}^{|L|} S ∣ L ∣ as the graph signature matrix S G \mathbf{S}_G S G . The pullback then carries the label topology into the attention score. Substituting S ∣ L ∣ = S G \mathbf{S}^{|L|} = \mathbf{S}_G S ∣ L ∣ = S G into Equation (4) and performing the eigendecomposition S G = Q T Λ G Q \mathbf{S}_G = \mathbf{Q}^{\mathsf{T}}\mathbf{\Lambda}_G\mathbf{Q} S G = Q T Λ G Q , we can reformulate the induced metric tensor. By absorbing the orthogonal eigenvector matrix Q \mathbf{Q} Q into the learnable weight matrix, i.e., defining W ′ [ l , k ] : = Q W [ l , k ] \mathbf{W'}^{[l,k]} := \mathbf{Q}\mathbf{W}^{[l,k]} W ′ [ l , k ] := Q W [ l , k ] , we arrive at:
D [ l , k ] = ( W [ l , k ] ) T ( Q T Λ G Q ) W [ l , k ] = ( Q W [ l , k ] ) T Λ G ( Q W [ l , k ] ) = ( W ′ [ l , k ] ) T Λ G W ′ [ l , k ] . (5) \mathbf{D}^{[l,k]} = \left(\mathbf{W}^{[l,k]}\right)^{\mathsf{T}}\left(\mathbf{Q}^{\mathsf{T}}\mathbf{\Lambda}_G\mathbf{Q}\right)\mathbf{W}^{[l,k]} = \left(\mathbf{Q}\mathbf{W}^{[l,k]}\right)^{\mathsf{T}}\mathbf{\Lambda}_G\left(\mathbf{Q}\mathbf{W}^{[l,k]}\right) = \left(\mathbf{W'}^{[l,k]}\right)^{\mathsf{T}}\mathbf{\Lambda}_G\mathbf{W'}^{[l,k]}. \tag*{(5)} D [ l , k ] = ( W [ l , k ] ) T ( Q T Λ G Q ) W [ l , k ] = ( Q W [ l , k ] ) T Λ G ( Q W [ l , k ] ) = ( W ′ [ l , k ] ) T Λ G W ′ [ l , k ] . (5)
In Equation (5), Λ G \mathbf{\Lambda}_G Λ G is a diagonalized graph signature matrix which directly encodes the homophilic or heterophilic character of the graph. In practical semi-supervised settings, however, the ground-truth labels for the entire graph are inaccessible, so we compute the empirical graph signature S G , t r a i n \mathbf{S}_{G,\mathrm{train}} S G , train and its eigenvalues Λ G , t r a i n \mathbf{\Lambda}_{G,\mathrm{train}} Λ G , train on the subgraph induced by the training nodes. We initialize the diagonal matrix Λ \mathbf{\Lambda} Λ using a normalized version of Λ G , t r a i n \mathbf{\Lambda}_{G,\mathrm{train}} Λ G , train , i.e. Λ i n i t = Λ G , t r a i n std ( Λ G , t r a i n ) ⋅ 1 ∣ L ∣ \mathbf{\Lambda}_{\mathrm{init}} = \frac{\mathbf{\Lambda}_{G,\mathrm{train}}}{\operatorname{std}(\mathbf{\Lambda}_{G,\mathrm{train}})} \cdot\frac{1}{\sqrt{|L|}} Λ init = std ( Λ G , train ) Λ G , train ⋅ ∣ L ∣ 1 , where std ( ⋅ ) \operatorname{std}(\cdot) std ( ⋅ ) is the standard deviation, set to 1 if zero. We leave these values free and treat the diagonal matrix Λ \mathbf{\Lambda} Λ as a learnable parameter. This design allows the model to fine-tune the geometric prior derived from the training set and generalize it to the unseen test nodes. Labels enter only here, and the forward pass never reads one. What the initialization has to supply is an informed indefinite prior, not ground truth: Section J.2 shows that a signature estimated from k k k -means pseudo-labels on node features recovers the label-based accuracy on both indefinite benchmarks, and Section K shows how far the estimate and the accuracy survive when the training labels are few or wrong.
Experiments
Datasets and Baselines
Standard Benchmark Datasets. We first evaluate PRAT on node classification across eight standard benchmarks covering a broad spectrum of homophily levels. We use Texas and Cornell from WebKB3 , Chameleon and Squirrel [30 ] , and Actor [35 ] as heterophilic datasets, and Cora, Citeseer, and PubMed [32 , 45 ] as homophilic counterparts. Detailed statistics, including edge homophily levels (h E h_E h E ) and graph signature indices (s G s_G s G ), are summarized in Table 1 . The homophilic graphs here carry strictly positive signatures and the heterophilic ones other than Actor carry negative components. That association only motivates the design; the ablation in Table 5 , not this correlation, shows that the sign structure produces the gain.
Table 1. Standard benchmark statistics (h E h_E h E , s G s_G s G ).
Table 5. Ablation study results.
Platonov Benchmark Datasets. We additionally evaluate PRAT on seven datasets curated by Platonov et al. [28 ] : (i) the filtered versions of Chameleon and Squirrel, in which duplicate nodes causing severe train–test leakage in the original benchmarks are removed; and (ii) five large-scale heterophilic datasets, roman-empire , amazon-ratings , minesweeper , tolokers and questions , spanning 10K to 49K nodes They test PRAT at scale without the data-quality artifacts of the original Wikipedia networks. Statistics are in Table 2 and descriptions in Appendix § 10 .
Table 2. Platonov benchmark statistics [28 ] .
Baselines on Standard Benchmarks. We compare PRAT against a diverse set of architectures spanning multiple paradigms: (1) Standard GNNs: GCN [16 ] , GIN [43 ] , and GraphSAGE [12 ] ; (2) Attention-based models: GAT [39 ] , GATv2 [3 ] , Scaled Dot-Product (SDP) Attention [38 , 33 ] , and Graph Transformer with and without ego-neighbor separation (GT, GT-sep) [33 ] [49]; (3) Heterophily-adapted GNNs: CPGNN [50], FAGCN [1 ] , Geom-GCN [27 ] , GPR-GNN [7 ] , BernNet [14 ] , and H2GCN [49]; (4) Geometric models: Q-GCN [42 ] on a pseudo-hyperboloid and HAT [47 ] on the Poincaré ball.
Baselines on Platonov Benchmarks. On the Platonov benchmarks, we compare PRAT against the best of three ResNet variants and the 14 GNN baselines reported in Platonov et al. [28 ] . (1) Standard GNNs: GCN [16 ] and GraphSAGE [12 ] ; (2) Attention-based models: GAT [39 ] , GAT-sep [49], Graph Transformer (GT) [33 ] , and GT-sep [49], where the “-sep” suffix denotes the ego- and neighbor-embedding separation trick of Zhu et al. [49]; (3) Heterophily-adapted GNNs: H2GCN [49], CPGNN [50], GPR-GNN [7 ] , FSGNN [23 ] , GloGNN [19 ] , FAGCN [1 ] , GBK-GNN [10 ] , and JacobiConv [40 ] .
Experimental Setup
Standard Benchmarks. We evaluate performance using 10 splits. For heterophilic datasets, we adopt the fixed 48%/32%/20% train/validation/test splits provided by Pei et al. [27 ] . For homophilic datasets, we generate random 60%/20%/20% splits, avoiding the selection bias of a fixed set. All graphs are undirected with self-loops added, and the seed is fixed across splits. Baselines and PRAT share one sweep over a predefined range (hidden dimension, learning rate, dropout), and we report mean test accuracy with standard deviation at the best-validation step.4 Detailed configurations are provided in Appendix § 13 .1.
Platonov Benchmarks. For the seven Platonov benchmarks, we use the official training pipeline of Platonov et al. [28 ] 5 as our experimental harness, where PRAT is implemented as a drop-in attention replacement inside the Platonov backbone. Data loading, the ten predefined splits, validation-based model selection and 10-split mean ± std reporting all follow Platonov et al. [28 ] exactly, so every deviation we report is across splits at a fixed seed. Section G.2 adds three seeds and finds seed variance the smaller of the two. PRAT is hyperparameter-tuned inside the same harness published by Platonov et al. [28 ] . Detailed configurations are provided in Appendix § 13 .1.
Cost. A PRAT layer has GAT’s asymptotic cost, since the metric it adds is diagonal and acts on a latent space whose dimension is the number of classes (Section E gives the expressions). Measured on the two largest graphs at equal backbone, width and depth, a training step takes 88.7 ms on questions against 91.2 for GAT and 175.2 for GT, and 26.7 ms on tolokers against 22.8 and 32.9 (Section E.3). At this scale, PRAT costs as much as GAT.
Main Results
Table 3 reports node classification accuracy on the eight standard benchmarks. PRAT is best on Actor and Texas, second on Squirrel, third on Chameleon and fourth on Cornell, and among the homophilic datasets it is best on Citeseer and third on PubMed; Section G.1 reports the pairwise tests, four of which are ties. PRAT attends over ℓ \ell ℓ -hop neighborhoods only, yet it exceeds the multi-hop spectral filters BernNet and GPR-GNN on Texas, Squirrel and Actor, so the margin there does not come from a larger receptive field. Section H reads the GT and geometric rows.
Table 3. Performance of PRAT and baselines on benchmark datasets. The top 3 performances are highlighted in First, Second, and Third.
Table 4 extends the comparison to Platonov et al. [28 ] benchmarks. PRAT is best or statistically tied on four of the seven datasets (Cham.-filt., roman-empire, amazon-ratings, tolokers), ranks 2nd on Sq.-filt., and sits 0.05pp below the third-placed model on minesweeper and 0.01pp below GT-sep at rank 3 on questions. Only two of those four are wins; the other two are ties: against SAGE on amazon-ratings a Welch test gives p = 0.55 p = 0.55 p = 0.55 , and against FAGCN on filtered Chameleon p = 0.52 p = 0.52 p = 0.52 (Section G.1). Across the seven benchmarks PRAT therefore outperforms or remains competitive with all standard and heterophily-adapted GNNs reported by Platonov et al. [28 ] . The ResNet row is graph-aware on every dataset (ResNet+SGC or ResNet+adj) and outscores GCN on filtered Chameleon, yet PRAT leads it on all seven, by 1.23 to 21.36 points. On filtered Chameleon, where the duplicate nodes responsible for train–test leakage in the original benchmark are removed, the gain survives; removing that leakage shows the gain is not an artifact of it, though it does not by itself rule out memorization of other kinds. These results support our central thesis: the geometry of the latent space, not the depth of aggregation, is the dominant factor for learning under heterophily.
Validation of Geometric Hypothesis Based on Synthetic Data
Generated graphs let us vary one structural property at a time. Nodes, edges, features and classes are held fixed across all of them, and every cell is five random 60/20/20 splits. Section D gives the generator.
Varying Homophily level We generated synthetic graphs with edge homophily h E ∈ { 0 , 0.05 , … , 1.0 } h_E \in\{0, 0.05, \ldots, 1.0\} h E ∈ { 0 , 0.05 , … , 1.0 } and evaluated classification accuracy. The comparison stays inside the attention family, so the receptive field is fixed and only the metric differs: GAT and GATv2 keep it positive definite, FAGCN signs the aggregation weights without touching the geometry, and PRAT makes the metric itself indefinite. In Figure 2 , PRAT holds its accuracy across the sweep while the other three fall away together below h E = 0.5 h_E = 0.5 h E = 0.5 . The gap to FAGCN averages 40.6 points over the nine levels at h E ≤ 0.4 h_E \le0.4 h E ≤ 0.4 . The curves converge above h E = 0.8 h_E = 0.8 h E = 0.8 , where a positive-definite metric is no longer a mismatch. Signed weights alone do not substitute for an indefinite metric.
Figure 2. Accuracy across edge homophily levels, within the attention family.
Figure 3 tracks the ratio of positive eigenvalues in the learned metric: as homophily falls the negative share rises, so the signature the model settles on is not imposed but follows the data. On real graphs the learned Λ \Lambda Λ instead keeps the initial sign of every entry with ∣ λ ∣ > 10 − 4 \lvert\lambda\rvert> 10^{-4} ∣ λ ∣ > 1 0 − 4 in Λ G , t r a i n \Lambda_{G,\mathrm{train}} Λ G , train , which Section J.1 reports.
Figure 3. Ratio of positive eigenvalues of the learned metric in PRAT across varying homophily levels.
Figure 4 visualizes the attention scores of PRAT and GAT, aggregated by source-target label pairs across all edges. Unlike GAT, PRAT concentrates attention on same-class connections (the diagonal) at h E = 0.1 h_E = 0.1 h E = 0.1 , suppressing dissimilar neighbors while keeping the node’s own signal, but does not do so at h E = 0.9 h_E = 0.9 h E = 0.9 . The metric changes how attention uses the same neighborhood.
Figure 4. Attention score distributions of PRAT and GAT. Each heatmap gives mean attention from source class (row) to target class (column).
Varying Graph Signature Index To investigate the influence of higher-order structural patterns beyond simple homophily, we generated synthetic graphs with a fixed homophily level (h E = 0.5 h_E = 0.5 h E = 0.5 ) but varying graph signature indices s G ∈ { ( 5 , 0 , 0 ) , ( 4 , 0 , 1 ) , ( 3 , 0 , 2 ) } s_{\mathcal{G}} \in\{(5, 0, 0), (4, 0, 1), (3, 0, 2)\} s G ∈ {( 5 , 0 , 0 ) , ( 4 , 0 , 1 ) , ( 3 , 0 , 2 )} .
In Figure 5 , baseline performance fluctuates significantly with the graph signature index. Specifically, the standard deviation of accuracy across different signatures is 3.99 for GAT and 3.42 for GATv2. PRAT varies by 0.68. Two readings follow: PRAT is the less sensitive of the three to latent structure, and s G s_{\mathcal{G}} s G separates graphs that a scalar h E h_E h E cannot, since these three share an h E h_E h E and behave differently.
Figure 5. Performance comparison under fixed h E = 0.5 h_E = 0.5 h E = 0.5 across different graph signature indices.
Ablation Study
To evaluate the effectiveness of graph-aware metric initialization in PRAT, we ran an ablation with two variants: (1) PRATp o s _{\mathrm{pos}} pos , whose learnable Λ \Lambda Λ is constrained to be positive definite, and (2) PRATf i x e d _{\mathrm{fixed}} fixed , whose Λ \Lambda Λ is frozen at its signature initialization.
In Table 5 the gap between PRAT and PRATp o s _{\mathrm{pos}} pos falls on the graphs whose signature has negative eigenvalues: Chameleon, Squirrel, Cornell and Texas all lose under the constraint, while Cora, PubMed and Citeseer, whose signatures are strictly positive, are unchanged. § 16 .1 repeats the comparison on the Platonov suite with an exact paired test: both significant losses are on indefinite graphs and no graph without a negative eigenvalue changes significantly, while filtered Squirrel, whose negative eigenvalues sit near zero, ties. A negative signature is therefore necessary for a significant loss, and § 16 .2 finds no significant rank correlation between n − n_{-} n − and what signed or high-pass baselines gain, so we offer s G s_G s G as a diagnostic and not as a predictor.
The two variants isolate different things. PRATp o s _{\mathrm{pos}} pos removes the freedom to be indefinite and starts Λ \Lambda Λ at a scaled identity, so it measures the sign structure. PRATf i x e d _{\mathrm{fixed}} fixed freezes Λ \Lambda Λ but not the metric, since D = ( W ′ ) ⊤ Λ W ′ D = (\mathbf{W}')^{\top}\Lambda\mathbf{W}' D = ( W ′ ) ⊤ Λ W ′ keeps adapting through the projection, so it measures whether the inertia has to be supplied at initialization. Its drop sits on the small graphs, 16.7 points on Cornell and 9.4 on Texas, where the training-split signature varies most; on the large Platonov graphs the two are within noise. Learning Λ \Lambda Λ earns its place where the signature is noisy, not where it is clean.
Which part of the signature carries the effect differs by graph. In Section J.1 the only control that loses decisively on roman-empire deletes the negative directions and keeps the magnitudes, 2.26 points at p = 0.002 p = 0.002 p = 0.002 , while sign-only, sign-flipped and three random draws stay within 0.7. On filtered Chameleon the magnitudes matter too, since every random draw loses 1.63 to 2.62 points.
GNNs for Heterophily. Standard GNNs assume homophily, acting as low-pass filters that smooth features across edges. Heterophily-adapted models answer this architecturally: Geom-GCN [27 ] and H 2 H_2 H 2 GCN [49] separate aggregation from the immediate neighborhood, spectral methods such as GPR-GNN [7 ] and BernNet [14 ] learn polynomial filters that mix high- and low-frequency signals, and attention-based models use signed edge weights [1 , 44 ] to represent repulsion. All of these operate within a Euclidean space.
Pseudo-Riemannian graph models. We are not the first to bring an indefinite geometry to graphs. Q-GCN [42 ] embeds node features on a pseudo-hyperboloid Q β s , t \mathcal{Q}_{\beta}^{s,t} Q β s , t , and convolves there through diffeomorphic exponential and logarithmic maps; Q-GT [18 ] carries the same ambient space into a transformer with linear attention. Three differences separate them from PRAT. First, where the indefinite form lives: in both it is the canonical scalar product of the manifold the nodes are embedded on, whereas in PRAT it is the attention logit itself, a signed squared pseudo-distance Δ ⊤ Δ \Delta^{\top}\Delta Δ ⊤ Δ . Q-GT’s attention weights come from a positive-definite kernel, so its indefinite product never reaches a score. Second, how the signature is chosen: Q-GCN picks the number of time dimensions by a curvature heuristic and a sweep, which its own conclusion names as an open limitation, and Q-GT selects its own signature ( p , q ) (p, q) ( p , q ) , the counts of positive and negative dimensions, offline by matching a sectional-curvature distribution. Neither criterion reads the label topology, so neither can see heterophily, while s G s_G s G is built from that topology and Λ \Lambda Λ is learned from the spectrum of S G , t r a i n S_{G,\mathrm{train}} S G , train . Third, coverage: Q-GCN’s labeled evaluation is citation networks and Airport, Q-GT adds two non-homophilous social graphs, and neither reports the WebKB, Wikipedia or Platonov suites used here. We claim a learnable label-initialized indefinite metric inside attention together with a diagnostic for when it should help, not priority for pseudo-Riemannian geometry on graphs. ACM-GCN [21 ] is closest on the channel side, mixing aggregation, diversification and identity channels node-wise, which puts the sign in the channel domain rather than in a metric. Its published numbers use different splits, so we cite it as a counterpart, not a comparable row.
Geometric Graph Learning. Hyperbolic GNNs [6 , 47 ] use constant negative curvature for hierarchical structure, and ARGNN [41 ] makes the metric node-wise and learnable. Both stay Riemannian (g > 0 g > 0 g > 0 ); only an indefinite metric admits a negative squared distance [17 ] .
Graph Attention. Standard L 2 L_2 L 2 attention can be reformulated as an SDP and is biased accordingly [22 ] . DGAT [20 ] uses spectral distances for rewiring in a separate preprocessing step, and global Graph Transformers [46 , 29 , 9 ] reach long range at quadratic cost while remaining Euclidean. PRAT instead reads attention as a tangent-space interaction on a learnable manifold.
Statistical Foundations. The Generalised Random Dot Product Graph (GRDPG) [31 ] shows statistically that indefinite inner products are needed to model disassortative networks. Theorem 2.5 reaches a complementary conclusion from the geometric side. GRDPG gives a fixed spectral embedding. PRAT learns the indefinite metric end-to-end, so attention moves with it at every layer.
Conclusion
We examined the positive-definite geometric prior carried by diffusion, hyperbolic and dot-product attention models, and asked what it costs when the labels induce an indefinite form. Theorem 2.5 answers in one direction: where S G S_G S G is indefinite and the pushforward is surjective, no diffeomorphism of the target turns the Riemannian pullback into f ∗ S G f^*S_G f ∗ S G . That is a statement about those model families and about graphs with a negative signature, not about heterophily as a whole.
The empirical picture matches that scope. The Graph Signature Index says which graphs carry a negative signature. In the paired Platonov ablation every significant loss from constraining the metric falls on such a graph, and no other graph changes significantly. The condition is necessary for a detectable loss. Several of our heterophilic benchmarks do not meet it, so the diagnosis, not heterophily as such, is a precondition of the indefinite metric’s advantage.
Limitations and future work. The signature is an initialization prior rather than an architectural requirement, since the forward pass never reads labels and Λ \Lambda Λ is an ordinary learnable parameter. Even so, four limits are worth stating. It is computed from training-node labels, which ties the scheme as presented to (semi-)supervised node classification. Section J.2 weakens that, but a full self-supervised treatment, objective as well as initialization, is outside our scope. Inductive use needs no recomputation in the forward pass, yet signature shift between training and test graphs is open. Graph-level tasks are out of reach as the method stands, since S G S_G S G is undefined without node labels. Finally, rank ( D ) ≤ ∣ L ∣ \operatorname{rank}(\mathbf{D}) \le|L| rank ( D ) ≤ ∣ L ∣ bounds the structure the metric can carry when classes are few, and on the binary benchmarks the inertia reduces to a single bit. Dynamic curvature and directed graphs are natural next steps.
Acknowledgments and Disclosure of Funding
This research was supported by the “Advanced GPU Utilization Support Program” funded by the Government of the Republic of Korea (Ministry of Science and ICT). Sun Woo Park would like to sincerely thank Max Planck Institute for Mathematics for its kind and generous support. The authors declare no competing interests.
Theoretical analysis and proofs
Normalization of the Graph Signature Matrix
The ( i , j ) (i,j) ( i , j ) -th entry of S G S_G S G is defined as s i j = ∣ E i j ∣ / ( n i ⋅ n j ) s_{ij} = \lvert E_{ij}\rvert/(n_i \cdot n_j) s ij = ∣ E ij ∣ / ( n i ⋅ n j ) , where ∣ E i j ∣ \lvert E_{ij}\rvert ∣ E ij ∣ is the number of ordered pairs ( v , w ) (v,w) ( v , w ) of adjacent nodes with l ( v ) = i l(v)=i l ( v ) = i and l ( w ) = j l(w)=j l ( w ) = j (so an edge inside class i i i is counted twice, which is the factor 2 of the diagonal entries in Appendix § 8 .§ 23 ), and n i , n j n_i,n_j n i , n j are the class sizes. This quantity is the edge density between classes i i i and j j j : the probability that a randomly chosen pair ( v , w ) (v,w) ( v , w ) with l ( v ) = i , l ( w ) = j l(v)=i,l(w)=j l ( v ) = i , l ( w ) = j is connected. This normalization is standard in stochastic block models (SBMs) and carries a clear physical interpretation: positive eigenvalues correspond to over-connected class pairs (homophilic tendency), while negative eigenvalues indicate under-connected pairs (heterophilic tendency).
The signature does not depend on the normalization by n i ⋅ n j n_i \cdot n_j n i ⋅ n j . Write C C C for the matrix of raw counts ∣ E i j ∣ \lvert E_{ij}\rvert ∣ E ij ∣ and N L : = diag ( n 1 , … , n ∣ L ∣ ) N_L := \operatorname{diag}(n_1,\ldots,n_{\lvert L\rvert}) N L := diag ( n 1 , … , n ∣ L ∣ ) . Since every class is nonempty, N L N_L N L is invertible, so
S G = N L − 1 C N L − 1 S_G = N_L^{-1} C N_L^{-1} S G = N L − 1 C N L − 1
is congruent to C C C and has the same inertia by Theorem 2.2. The normalization acts on the eigenvalues instead. Those of C C C scale with class sizes, so class imbalance enters their magnitudes, while those of S G S_G S G are the spectrum of the connection-probability matrix above. Rescaled, they initialize Λ \Lambda Λ (Equation (5) ), and Section J.1 shows that on filtered Chameleon their magnitudes matter beyond their signs. The critical homophily threshold in Theorem 2.3 is derived under this normalization, where the expected matrix takes the form a I + b ( J − I ) aI+b(J-I) a I + b ( J − I ) with eigenvalues in closed form, and the resulting h E ∗ = ∑ n k 2 / N 2 h_E^* = \sum n_k^2/N^2 h E ∗ = ∑ n k 2 / N 2 explicitly accounts for class imbalance.
A different characterization of S G S_G S G
Using the unfolding-tree perspective on local graph structure [25 ] , we interpret entries of the graph signature matrix through depth 1 unfolding trees rooted at each node of G \mathcal{G} G .
Definition A.1. For any node v ∈ V v \in\mathcal{V} v ∈ V , we define the probability that a node with a given node label j j j is connected to a directed edge starting from node v v v as
p v , j : = P [ ( v , w ) ∈ E | w ∈ V , l ( w ) = j ] = ∣ { w ∈ V ∣ l ( w ) = j , ( v , w ) ∈ E } ∣ ∣ { w ∈ V ∣ l ( w ) = j } ∣ (6) p_{v,j} := \mathbb{P}\left[(v,w) \in\mathcal{E} \,\middle|\, w \in\mathcal{V},\ l(w)=j\right]
= \frac{\lvert\{w \in\mathcal{V} \mid l(w)=j,\ (v,w) \in\mathcal{E}\}\rvert}{\lvert\{w \in\mathcal{V} \mid l(w)=j\}\rvert} \tag*{(6)} p v , j := P [ ( v , w ) ∈ E ∣ w ∈ V , l ( w ) = j ] = ∣{ w ∈ V ∣ l ( w ) = j }∣ ∣{ w ∈ V ∣ l ( w ) = j , ( v , w ) ∈ E }∣ (6)
Lemma A.2. Given a graph G \mathcal{G} G , each matrix entry of S G S_G S G satisfies
p i , j = 1 ∣ { v ∈ V ∣ l ( v ) = i } ∣ ∑ v ∈ V l ( v ) = i p v , j (7) p_{i,j} = \frac{1}{\lvert\{v \in\mathcal{V} \mid l(v)=i\}\rvert} \sum_{\substack{v \in\mathcal{V} \\ l(v)=i}} p_{v,j} \tag*{(7)} p i , j = ∣{ v ∈ V ∣ l ( v ) = i }∣ 1 v ∈ V l ( v ) = i ∑ p v , j (7)
Proof. We note that
p i , j : = 1 ∣ { v ∈ V ∣ l ( v ) = i } ∣ ∣ { ( v , w ) ∈ E ∣ l ( v ) = i , l ( w ) = j } ∣ ∣ { v ∈ V ∣ l ( v ) = j } ∣ = 1 ∣ { v ∈ V ∣ l ( v ) = i } ∣ ∑ v ∈ V l ( v ) = i ∣ { ( v , w ) ∈ E ∣ l ( w ) = j } ∣ ∣ { w ∈ V ∣ l ( w ) = j } ∣ = 1 ∣ { v ∈ V ∣ l ( v ) = i } ∣ ∑ v ∈ V l ( v ) = i p v , j . (8) \begin{aligned}
p_{i,j} &:= \frac{1}{\lvert\{v \in\mathcal{V}\mid l(v)=i\}\rvert}\frac{\lvert\{(v,w)\in\mathcal{E}\mid l(v)=i,l(w)=j\}\rvert}{\lvert\{v\in\mathcal{V}\mid l(v)=j\}\rvert}\\
&= \frac{1}{\lvert\{v\in\mathcal{V}\mid l(v)=i\}\rvert}\frac{\sum_{\substack{v\in\mathcal{V}\\l(v)=i}}\lvert\{(v,w)\in\mathcal{E}\mid l(w)=j\}\rvert}{\lvert\{w\in\mathcal{V}\mid l(w)=j\}\rvert}\\
&= \frac{1}{\lvert\{v\in\mathcal{V}\mid l(v)=i\}\rvert}\sum_{\substack{v\in\mathcal{V}\\l(v)=i}}p_{v,j}. \tag*{(8)}
\end{aligned} p i , j := ∣{ v ∈ V ∣ l ( v ) = i }∣ 1 ∣{ v ∈ V ∣ l ( v ) = j }∣ ∣{( v , w ) ∈ E ∣ l ( v ) = i , l ( w ) = j }∣ = ∣{ v ∈ V ∣ l ( v ) = i }∣ 1 ∣{ w ∈ V ∣ l ( w ) = j }∣ ∑ v ∈ V l ( v ) = i ∣{( v , w ) ∈ E ∣ l ( w ) = j }∣ = ∣{ v ∈ V ∣ l ( v ) = i }∣ 1 v ∈ V l ( v ) = i ∑ p v , j . (8)
In other words, each ( i , j ) (i,j) ( i , j ) -th entry of S G S_{\mathcal{G}} S G is the expected value of the probability that a node with a preassigned label j j j lies in the depth 1 unfolding tree rooted at a node with label i i i .
An example of graph signature index for graphs with two discrete node labels
Theorem A.3 (2 Discrete Node Labels). Let G : = ( V , E ) \mathcal{G}:=(\mathcal{V},\mathcal{E}) G := ( V , E ) be an undirected graph without self-loops and with E ≠ ∅ \mathcal{E}\ne\varnothing E = ∅ . Let l : V → { 1 , 2 } l:\mathcal{V}\to\{1,2\} l : V → { 1 , 2 } be the discrete node label function over the set of nodes of G \mathcal{G} G . Then the following correspondence holds between s G s_{\mathcal{G}} s G and entries of S G : = ( p i , j ) 1 ≤ i , j ≤ 2 S_{\mathcal{G}}:=(p_{i,j})_{1\le i,j\le2} S G := ( p i , j ) 1 ≤ i , j ≤ 2 :
s G = ( 2 , 0 , 0 ) ⟺ p 1 , 2 < p 1 , 1 p 2 , 2 s G = ( 1 , 1 , 0 ) ⟺ p 1 , 2 = p 1 , 1 p 2 , 2 s G = ( 1 , 0 , 1 ) ⟺ p 1 , 2 > p 1 , 1 p 2 , 2 (9) \begin{aligned}
s_{\mathcal{G}}=(2,0,0)&\Longleftrightarrow p_{1,2}<\sqrt{p_{1,1}p_{2,2}}\\
s_{\mathcal{G}}=(1,1,0)&\Longleftrightarrow p_{1,2}=\sqrt{p_{1,1}p_{2,2}}\\
s_{\mathcal{G}}=(1,0,1)&\Longleftrightarrow p_{1,2}>\sqrt{p_{1,1}p_{2,2}} \tag*{(9)}
\end{aligned} s G = ( 2 , 0 , 0 ) s G = ( 1 , 1 , 0 ) s G = ( 1 , 0 , 1 ) ⟺ p 1 , 2 < p 1 , 1 p 2 , 2 ⟺ p 1 , 2 = p 1 , 1 p 2 , 2 ⟺ p 1 , 2 > p 1 , 1 p 2 , 2 (9)
Proof. Let S G S_{\mathcal{G}} S G be the graph signature matrix of G \mathcal{G} G . Its explicit form is given as
S G : = ( p 1 , 1 p 1 , 2 p 2 , 1 p 2 , 2 ) (10) S_{\mathcal{G}}:=\begin{pmatrix}p_{1,1}&p_{1,2}\\p_{2,1}&p_{2,2}\end{pmatrix} \tag*{(10)} S G := ( p 1 , 1 p 2 , 1 p 1 , 2 p 2 , 2 ) (10)
The characteristic polynomial of S G S_{\mathcal{G}} S G is given by
( λ − p 1 , 1 ) ( λ − p 2 , 2 ) − p 1 , 2 2 = 0 (11) (\lambda-p_{1,1})(\lambda-p_{2,2})-p_{1,2}^{2}=0 \tag*{(11)} ( λ − p 1 , 1 ) ( λ − p 2 , 2 ) − p 1 , 2 2 = 0 (11)
The eigenvalues of S G S_{\mathcal{G}} S G are given by
λ = ( p 1 , 1 + p 2 , 2 ) ± ( p 1 , 1 + p 2 , 2 ) 2 − 4 ( p 1 , 1 p 2 , 2 − p 1 , 2 2 ) 2 (12) \lambda=\frac{(p_{1,1}+p_{2,2})\pm\sqrt{(p_{1,1}+p_{2,2})^{2}-4(p_{1,1}p_{2,2}-p_{1,2}^{2})}}{2} \tag*{(12)} λ = 2 ( p 1 , 1 + p 2 , 2 ) ± ( p 1 , 1 + p 2 , 2 ) 2 − 4 ( p 1 , 1 p 2 , 2 − p 1 , 2 2 ) (12)
Since E ≠ ∅ \mathcal{E}\ne\varnothing E = ∅ , the trace p 1 , 1 + p 2 , 2 p_{1,1}+p_{2,2} p 1 , 1 + p 2 , 2 is positive whenever p 1 , 1 p 2 , 2 ≥ p 1 , 2 2 p_{1,1}p_{2,2}\ge p_{1,2}^{2} p 1 , 1 p 2 , 2 ≥ p 1 , 2 2 , as otherwise all three entries vanish. Hence, the graph signature s G s_{\mathcal{G}} s G is determined by the sign of the term p 1 , 1 p 2 , 2 − p 1 , 2 2 p_{1,1}p_{2,2}-p_{1,2}^{2} p 1 , 1 p 2 , 2 − p 1 , 2 2 .
Heuristics on heterophilic and homophilic graphs with two discrete node labels
The phase diagram for the graph F : p 1 , 2 − p 1 , 1 p 2 , 2 = 0 F:p_{1,2}-\sqrt{p_{1,1}p_{2,2}}=0 F : p 1 , 2 − p 1 , 1 p 2 , 2 = 0 is shown in Figure 6 , where the region below F F F characterizes graphs whose nodes with identical labels are more likely to be connected than those with distinct labels (i.e. homophilic graphs), whereas the region above F F F contains heterophilic graphs. A third region, defined by F F F , contains graphs whose nodes with identical labels are as likely to be connected as those with distinct labels. Note that the volume of the region below F F F over 0 ≤ p 1 , 1 ≤ 1 0\le p_{1,1}\le1 0 ≤ p 1 , 1 ≤ 1 and 0 ≤ p 2 , 2 ≤ 1 0\le p_{2,2}\le1 0 ≤ p 2 , 2 ≤ 1 is given by
Figure 6. A phase diagram of graph signature index with two types of discrete node labels. The blue surface denotes the region where F : p 1 , 2 = p 1 , 1 p 2 , 2 F : p_{1,2} = \sqrt{p_{1,1}p_{2,2}} F : p 1 , 2 = p 1 , 1 p 2 , 2 .
∫ 0 1 ∫ 0 1 p 1 , 1 p 2 , 2 d p 1 , 1 d p 2 , 2 = 4 9 . (13) \int_{0}^{1}\int_{0}^{1}\sqrt{p_{1,1}p_{2,2}}\,dp_{1,1}dp_{2,2}=\frac{4}{9}. \tag*{(13)} ∫ 0 1 ∫ 0 1 p 1 , 1 p 2 , 2 d p 1 , 1 d p 2 , 2 = 9 4 . (13)
Consider the idealized model with 2 discrete node labels whose connectivity parameters ( p 1 , 1 , p 1 , 2 , p 2 , 2 ) (p_{1,1},p_{1,2},p_{2,2}) ( p 1 , 1 , p 1 , 2 , p 2 , 2 ) are uniformly distributed on [ 0 , 1 ] 3 [0,1]^3 [ 0 , 1 ] 3 , and let P = ( p i , j ) P=(p_{i,j}) P = ( p i , j ) be the symmetric 2 × 2 2\times2 2 × 2 connectivity matrix, with inertia In ( P ) \operatorname{In}(P) In ( P ) . The integral computed above shows that
P [ In ( P ) = ( i , j , k ) ] = { 5 9 if ( i , j , k ) = ( 1 , 0 , 1 ) 0 if ( i , j , k ) = ( 1 , 1 , 0 ) 4 9 if ( i , j , k ) = ( 2 , 0 , 0 ) (14) \mathbb{P}[\operatorname{In}(P)=(i,j,k)]=
\begin{cases}
\frac{5}{9} & \text{if }(i,j,k)=(1,0,1)\\
0 & \text{if }(i,j,k)=(1,1,0)\\
\frac{4}{9} & \text{if }(i,j,k)=(2,0,0)
\end{cases} \tag*{(14)} P [ In ( P ) = ( i , j , k )] = ⎩ ⎨ ⎧ 9 5 0 9 4 if ( i , j , k ) = ( 1 , 0 , 1 ) if ( i , j , k ) = ( 1 , 1 , 0 ) if ( i , j , k ) = ( 2 , 0 , 0 ) (14)
Notion of homophily indices
Proof of Theorem 2.3
Setup and Notation. Consider an undirected graph G : = ( V , E ) \mathcal{G} := (\mathcal{V},\mathcal{E}) G := ( V , E ) with ∣ L ∣ ≥ 2 |L| \ge2 ∣ L ∣ ≥ 2 class labels, where class i i i contains n i ≥ 1 n_i \ge1 n i ≥ 1 nodes. Let N = ∑ i = 1 ∣ L ∣ n i N = \sum_{i=1}^{|L|} n_i N = ∑ i = 1 ∣ L ∣ n i denote the total number of nodes. The graph has ∣ E ∣ > 0 |\mathcal{E}| > 0 ∣ E ∣ > 0 edges with edge homophily level h E ∈ [ 0 , 1 ] h_E \in[0,1] h E ∈ [ 0 , 1 ] , partitioned into h E ∣ E ∣ h_E|\mathcal{E}| h E ∣ E ∣ intra-class edges and ( 1 − h E ) ∣ E ∣ (1-h_E)|\mathcal{E}| ( 1 − h E ) ∣ E ∣ inter-class edges.
We adopt a proportional allocation model :
Intra-class edges are distributed among classes proportionally to n i 2 n_i^2 n i 2 (the denominator of s i , i s_{i,i} s i , i in Definition 2.1).
Inter-class edges are distributed among class pairs ( i , j ) (i,j) ( i , j ) with i ≠ j i\ne j i = j proportionally to n i n j n_i n_j n i n j .
Define the following quantities for notational convenience:
Σ 2 : = ∑ k = 1 ∣ L ∣ n k 2 , Σ × : = ∑ i < j n i n j = N 2 − Σ 2 2 . (17) \Sigma_2 := \sum_{k=1}^{|L|} n_k^2,\qquad\Sigma_{\times} := \sum_{i<j} n_i n_j = \frac{N^2-\Sigma_2}{2}. \tag*{(17)} Σ 2 := k = 1 ∑ ∣ L ∣ n k 2 , Σ × := i < j ∑ n i n j = 2 N 2 − Σ 2 . (17)
Expected Edge Counts. Under the proportional allocation model, the expected number of intra-class edges in class i i i is
E [ X i ] = h E ∣ E ∣ ⋅ n i 2 Σ 2 . (18) \mathbb{E}[X_i] = h_E|\mathcal{E}|\cdot\frac{n_i^2}{\Sigma_2}. \tag*{(18)} E [ X i ] = h E ∣ E ∣ ⋅ Σ 2 n i 2 . (18)
and the expected number of inter-class edges between classes i i i and j j j (where i ≠ j i \ne j i = j ) is
E [ Y i j ] = ( 1 − h E ) ∣ E ∣ ⋅ n i n j Σ × = 2 ( 1 − h E ) ∣ E ∣ ⋅ n i n j N 2 − Σ 2 . (19) \mathbb{E}[Y_{ij}] = (1-h_E)|\mathcal{E}| \cdot\frac{n_i n_j}{\Sigma_{\times}} = \frac{2(1-h_E)|\mathcal{E}| \cdot n_i n_j}{N^2-\Sigma_2}. \tag*{(19)} E [ Y ij ] = ( 1 − h E ) ∣ E ∣ ⋅ Σ × n i n j = N 2 − Σ 2 2 ( 1 − h E ) ∣ E ∣ ⋅ n i n j . (19)
Expected Signature Matrix Entries. The expected signature matrix S G = E [ S ^ G ] S_{\mathcal{G}} = \mathbb{E}[\widehat{S}_{\mathcal{G}}] S G = E [ S G ] has entries given by Definition 2.1. For diagonal entries:
( S G ) i i = 2 E [ X i ] n i 2 = 2 h E ∣ E ∣ ⋅ n i 2 / Σ 2 n i 2 = 2 h E ∣ E ∣ Σ 2 = : a . (20) (S_{\mathcal{G}})_{ii} = \frac{2\mathbb{E}[X_i]}{n_i^2} = \frac{2h_E|\mathcal{E}| \cdot n_i^2/\Sigma_2}{n_i^2} = \frac{2h_E|\mathcal{E}|}{\Sigma_2} =: a. \tag*{(20)} ( S G ) ii = n i 2 2 E [ X i ] = n i 2 2 h E ∣ E ∣ ⋅ n i 2 / Σ 2 = Σ 2 2 h E ∣ E ∣ =: a . (20)
For off-diagonal entries:
( S G ) i j = E [ Y i j ] n i n j = 2 ( 1 − h E ) ∣ E ∣ ⋅ n i n j / ( N 2 − Σ 2 ) n i n j = 2 ( 1 − h E ) ∣ E ∣ N 2 − Σ 2 = : b . (21) (S_{\mathcal{G}})_{ij} = \frac{\mathbb{E}[Y_{ij}]}{n_i n_j} = \frac{2(1-h_E)|\mathcal{E}| \cdot n_i n_j/(N^2-\Sigma_2)}{n_i n_j} = \frac{2(1-h_E)|\mathcal{E}|}{N^2-\Sigma_2} =: b. \tag*{(21)} ( S G ) ij = n i n j E [ Y ij ] = n i n j 2 ( 1 − h E ) ∣ E ∣ ⋅ n i n j / ( N 2 − Σ 2 ) = N 2 − Σ 2 2 ( 1 − h E ) ∣ E ∣ =: b . (21)
Both diagonal and off-diagonal entries are constant across all indices, yielding the matrix structure:
S G = a ⋅ I ∣ L ∣ + b ⋅ ( J ∣ L ∣ − I ∣ L ∣ ) = ( a − b ) I ∣ L ∣ + b J ∣ L ∣ , (22) S_{\mathcal{G}} = a \cdot I_{|\mathcal{L}|} + b \cdot(J_{|\mathcal{L}|} - I_{|\mathcal{L}|}) = (a-b)I_{|\mathcal{L}|} + bJ_{|\mathcal{L}|}, \tag*{(22)} S G = a ⋅ I ∣ L ∣ + b ⋅ ( J ∣ L ∣ − I ∣ L ∣ ) = ( a − b ) I ∣ L ∣ + b J ∣ L ∣ , (22)
where I ∣ L ∣ I_{|\mathcal{L}|} I ∣ L ∣ is the ∣ L ∣ × ∣ L ∣ |\mathcal{L}| \times|\mathcal{L}| ∣ L ∣ × ∣ L ∣ identity matrix and J ∣ L ∣ J_{|\mathcal{L}|} J ∣ L ∣ is the ∣ L ∣ × ∣ L ∣ |\mathcal{L}| \times|\mathcal{L}| ∣ L ∣ × ∣ L ∣ all-ones matrix.
Eigenvalue Computation. The all-ones matrix J ∣ L ∣ J_{|\mathcal{L}|} J ∣ L ∣ has eigenvalue ∣ L ∣ |\mathcal{L}| ∣ L ∣ with eigenvector 1 ∣ L ∣ = ( 1 , … , 1 ) ⊤ \mathbf{1}_{|\mathcal{L}|} = (1,\ldots,1)^{\top} 1 ∣ L ∣ = ( 1 , … , 1 ) ⊤ , and eigenvalue 0 0 0 with multiplicity ∣ L ∣ − 1 |\mathcal{L}|-1 ∣ L ∣ − 1 for eigenvectors orthogonal to 1 ∣ L ∣ \mathbf{1}_{|\mathcal{L}|} 1 ∣ L ∣ . Therefore, the first eigenvalue (with eigenvector 1 ∣ L ∣ \mathbf{1}_{|\mathcal{L}|} 1 ∣ L ∣ ) is
λ 1 = ( a − b ) + ∣ L ∣ b = a + ( ∣ L ∣ − 1 ) b , (23) \lambda_1 = (a-b) + |\mathcal{L}|b = a + (|\mathcal{L}|-1)b, \tag*{(23)} λ 1 = ( a − b ) + ∣ L ∣ b = a + ( ∣ L ∣ − 1 ) b , (23)
and the remaining eigenvalues (with eigenvectors in 1 ∣ L ∣ ⊥ \mathbf{1}_{|\mathcal{L}|}^{\perp} 1 ∣ L ∣ ⊥ , multiplicity ∣ L ∣ − 1 |\mathcal{L}|-1 ∣ L ∣ − 1 ) are
λ 2 = ⋯ = λ ∣ L ∣ = a − b . (24) \lambda_2 = \cdots= \lambda_{|\mathcal{L}|} = a-b. \tag*{(24)} λ 2 = ⋯ = λ ∣ L ∣ = a − b . (24)
Substituting the definitions of a a a and b b b :
a − b = 2 h E ∣ E ∣ Σ 2 − 2 ( 1 − h E ) ∣ E ∣ N 2 − Σ 2 = 2 ∣ E ∣ ( h E Σ 2 − 1 − h E N 2 − Σ 2 ) = 2 ∣ E ∣ ⋅ h E ( N 2 − Σ 2 ) − ( 1 − h E ) Σ 2 Σ 2 ( N 2 − Σ 2 ) . (25) \begin{aligned}
a-b &= \frac{2h_E|\mathcal{E}|}{\Sigma_2} - \frac{2(1-h_E)|\mathcal{E}|}{N^2-\Sigma_2} = 2|\mathcal{E}|\left(\frac{h_E}{\Sigma_2} - \frac{1-h_E}{N^2-\Sigma_2}\right) \\
&= 2|\mathcal{E}| \cdot\frac{h_E(N^2-\Sigma_2) - (1-h_E)\Sigma_2}{\Sigma_2(N^2-\Sigma_2)}. \tag*{(25)}
\end{aligned} a − b = Σ 2 2 h E ∣ E ∣ − N 2 − Σ 2 2 ( 1 − h E ) ∣ E ∣ = 2∣ E ∣ ( Σ 2 h E − N 2 − Σ 2 1 − h E ) = 2∣ E ∣ ⋅ Σ 2 ( N 2 − Σ 2 ) h E ( N 2 − Σ 2 ) − ( 1 − h E ) Σ 2 . (25)
Expanding the numerator:
h E ( N 2 − Σ 2 ) − ( 1 − h E ) Σ 2 = h E N 2 − h E Σ 2 − Σ 2 + h E Σ 2 = h E N 2 − Σ 2 . (26) h_E(N^2-\Sigma_2) - (1-h_E)\Sigma_2 = h_E N^2 - h_E\Sigma_2 - \Sigma_2 + h_E\Sigma_2 = h_E N^2 - \Sigma_2. \tag*{(26)} h E ( N 2 − Σ 2 ) − ( 1 − h E ) Σ 2 = h E N 2 − h E Σ 2 − Σ 2 + h E Σ 2 = h E N 2 − Σ 2 . (26)
Therefore:
λ 2 = ⋯ = λ ∣ L ∣ = 2 ∣ E ∣ ( h E N 2 − Σ 2 ) Σ 2 ( N 2 − Σ 2 ) . (27) \lambda_2 = \cdots= \lambda_{|\mathcal{L}|} = \frac{2|\mathcal{E}|(h_E N^2-\Sigma_2)}{\Sigma_2(N^2-\Sigma_2)}. \tag*{(27)} λ 2 = ⋯ = λ ∣ L ∣ = Σ 2 ( N 2 − Σ 2 ) 2∣ E ∣ ( h E N 2 − Σ 2 ) . (27)
Critical Threshold. The sign of λ 2 , … , λ ∣ L ∣ \lambda_2,\ldots,\lambda_{|\mathcal{L}|} λ 2 , … , λ ∣ L ∣ is determined by the numerator ( h E N 2 − Σ 2 ) (h_E N^2-\Sigma_2) ( h E N 2 − Σ 2 ) :
h E N 2 − Σ 2 ⋛ 0 ⟺ h E ⋛ Σ 2 N 2 = ∑ k = 1 ∣ L ∣ n k 2 N 2 . (28) h_E N^2-\Sigma_2 \gtreqless0 \Longleftrightarrow h_E \gtreqless\frac{\Sigma_2}{N^2} = \frac{\sum_{k=1}^{|\mathcal{L}|} n_k^2}{N^2}. \tag*{(28)} h E N 2 − Σ 2 ⋛ 0 ⟺ h E ⋛ N 2 Σ 2 = N 2 ∑ k = 1 ∣ L ∣ n k 2 . (28)
Thus, the critical threshold is:
h E ∗ = ∑ k = 1 ∣ L ∣ n k 2 N 2 = ∑ k = 1 ∣ L ∣ ( n k N ) 2 . (29) h_E^* = \frac{\sum_{k=1}^{|\mathcal{L}|} n_k^2}{N^2} = \sum_{k=1}^{|\mathcal{L}|}\left(\frac{n_k}{N}\right)^2. \tag*{(29)} h E ∗ = N 2 ∑ k = 1 ∣ L ∣ n k 2 = k = 1 ∑ ∣ L ∣ ( N n k ) 2 . (29)
Positivity of λ 1 \lambda_1 λ 1 . We verify that λ 1 > 0 \lambda_1 > 0 λ 1 > 0 for all valid parameter ranges:
λ 1 = a + ( ∣ L ∣ − 1 ) b = 2 h E ∣ E ∣ Σ 2 + 2 ( ∣ L ∣ − 1 ) ( 1 − h E ) ∣ E ∣ N 2 − Σ 2 . (30) \lambda_1 = a + (|\mathcal{L}|-1)b = \frac{2h_E|\mathcal{E}|}{\Sigma_2} + \frac{2(|\mathcal{L}|-1)(1-h_E)|\mathcal{E}|}{N^2-\Sigma_2}. \tag*{(30)} λ 1 = a + ( ∣ L ∣ − 1 ) b = Σ 2 2 h E ∣ E ∣ + N 2 − Σ 2 2 ( ∣ L ∣ − 1 ) ( 1 − h E ) ∣ E ∣ . (30)
Since h E ∈ [ 0 , 1 ] h_E \in[0,1] h E ∈ [ 0 , 1 ] , ∣ E ∣ > 0 |\mathcal{E}| > 0 ∣ E ∣ > 0 , Σ 2 > 0 \Sigma_2 > 0 Σ 2 > 0 , and N 2 − Σ 2 = 2 ∑ i < j n i n j > 0 N^2-\Sigma_2 = 2\sum_{i<j}n_i n_j > 0 N 2 − Σ 2 = 2 ∑ i < j n i n j > 0 for ∣ L ∣ ≥ 2 |\mathcal{L}| \ge2 ∣ L ∣ ≥ 2 , we have λ 1 > 0 \lambda_1 > 0 λ 1 > 0 always.
Signature Classification. Combining the above results:
If h E > h E ∗ h_E > h_E^* h E > h E ∗ : λ 1 > 0 \lambda_1 > 0 λ 1 > 0 and λ 2 = ⋯ = λ ∣ L ∣ > 0 \lambda_2 = \cdots= \lambda_{|L|} > 0 λ 2 = ⋯ = λ ∣ L ∣ > 0 , so s G = ( ∣ L ∣ , 0 , 0 ) s_G = (|L|, 0, 0) s G = ( ∣ L ∣ , 0 , 0 ) .
If h E = h E ∗ h_E = h_E^* h E = h E ∗ : λ 1 > 0 \lambda_1 > 0 λ 1 > 0 and λ 2 = ⋯ = λ ∣ L ∣ = 0 \lambda_2 = \cdots= \lambda_{|L|} = 0 λ 2 = ⋯ = λ ∣ L ∣ = 0 , so s G = ( 1 , ∣ L ∣ − 1 , 0 ) s_G = (1, |L| - 1, 0) s G = ( 1 , ∣ L ∣ − 1 , 0 ) .
If h E < h E ∗ h_E < h_E^* h E < h E ∗ : λ 1 > 0 \lambda_1 > 0 λ 1 > 0 and λ 2 = ⋯ = λ ∣ L ∣ < 0 \lambda_2 = \cdots= \lambda_{|L|} < 0 λ 2 = ⋯ = λ ∣ L ∣ < 0 , so s G = ( 1 , 0 , ∣ L ∣ − 1 ) s_G = (1, 0, |L| - 1) s G = ( 1 , 0 , ∣ L ∣ − 1 ) .
Reduction to Balanced Case. For balanced classes where n i = n n_i = n n i = n for all i ∈ { 1 , … , ∣ L ∣ } i \in\{1, \ldots, |L|\} i ∈ { 1 , … , ∣ L ∣ } :
h E ∗ = ∑ k = 1 ∣ L ∣ n 2 ( ∣ L ∣ n ) 2 = ∣ L ∣ n 2 ∣ L ∣ 2 n 2 = 1 ∣ L ∣ . (31) h_E^* = \frac{\sum_{k=1}^{|L|} n^2}{(|L|n)^2} = \frac{|L|n^2}{|L|^2n^2} = \frac{1}{|L|}. \tag*{(31)} h E ∗ = ( ∣ L ∣ n ) 2 ∑ k = 1 ∣ L ∣ n 2 = ∣ L ∣ 2 n 2 ∣ L ∣ n 2 = ∣ L ∣ 1 . (31)
Probabilistic Interpretation. The critical threshold h E ∗ = ∑ k = 1 ∣ L ∣ ( n k / N ) 2 h_E^* = \sum_{k=1}^{|L|}(n_k/N)^2 h E ∗ = ∑ k = 1 ∣ L ∣ ( n k / N ) 2 equals the probability that two nodes chosen uniformly at random (with replacement) belong to the same class. This quantity provides a natural baseline:
h E > h E ∗ h_E > h_E^* h E > h E ∗ : Edges preferentially connect intra-class nodes relative to random chance (homophilic ).
h E < h E ∗ h_E < h_E^* h E < h E ∗ : Edges preferentially connect inter-class nodes relative to random chance (heterophilic ).
Proof of Theorem 2.4
Both homophily indices of a finite graph are rational: h E h_E h E is a ratio of edge counts and h V h_V h V is an average of ratios of integers. The construction below attains every rational number in ( 0 , 1 ) (0, 1) ( 0 , 1 ) , so Theorem 2.4 covers every value that h E h_E h E or h V h_V h V takes in ( 0 , 1 ) (0, 1) ( 0 , 1 ) . We prove it in the following stronger form, which also prescribes the number of classes.
Theorem A.5. For every rational h ∈ ( 0 , 1 ) h \in(0, 1) h ∈ ( 0 , 1 ) and every number of classes ∣ L ∣ ≥ 2 |L| \ge2 ∣ L ∣ ≥ 2 , there exists a graph G : = ( V , E ) \mathcal{G} := (\mathcal{V}, \mathcal{E}) G := ( V , E ) with node labels l : V → L l : \mathcal{V} \to L l : V → L such that h E = h V = h h_E = h_V = h h E = h V = h and S G S_{\mathcal{G}} S G has a negative eigenvalue.
Proof. We first record a sufficient condition that involves neither h E h_E h E nor h V h_V h V . Suppose that some class j j j has no intra-class edge and at least one edge to a class i ≠ j i \ne j i = j , so that s j , j = 0 s_{j,j} = 0 s j , j = 0 and s i , j = s j , i > 0 s_{i,j} = s_{j,i} > 0 s i , j = s j , i > 0 . For the standard basis vectors e i , e j ∈ R ∣ L ∣ e_i, e_j \in\mathbb{R}^{|L|} e i , e j ∈ R ∣ L ∣ and x = t e i − e j x = t e_i - e_j x = t e i − e j with $t > 0,
x T S G x = t 2 s i , i − 2 t s i , j + s j , j = t ( t s i , i − 2 s i , j ) , (32) x^T S_{\mathcal{G}} x = t^2s_{i,i} - 2ts_{i,j} + s_{j,j} = t(ts_{i,i} - 2s_{i,j}), \tag*{(32)} x T S G x = t 2 s i , i − 2 t s i , j + s j , j = t ( t s i , i − 2 s i , j ) , (32)
which is negative for every sufficiently small t > 0 t > 0 t > 0 . The smallest eigenvalue of S G S_{\mathcal{G}} S G is at most the Rayleigh quotient x T S G x / x T x x^T S_{\mathcal{G}}x/x^T x x T S G x / x T x , hence negative.
Write h = p / q h = p/q h = p / q with integers 1 ≤ p < q 1 \le p < q 1 ≤ p < q , and let k = ∣ L ∣ k = |L| k = ∣ L ∣ and m = k − 1 m = k - 1 m = k − 1 . Let G \mathcal{G} G be the disjoint union of m q mq m q edges: m p mp m p of them join two nodes of class 1, and each of the other m ( q − p ) ≥ k − 1 m(q-p) \ge k-1 m ( q − p ) ≥ k − 1 edges joins a node of class 1 to a node of a class j ∈ { 2 , … , k } j \in\{2, \ldots, k\} j ∈ { 2 , … , k } , with every such j j j used at least once. Every class is nonempty, so S G S_{\mathcal{G}} S G is well defined, and h E = m p / ( m q ) = h h_E = mp/(mq) = h h E = m p / ( m q ) = h . Every node has degree 1: each of the 2 m p 2mp 2 m p endpoints of an intra-class edge has its only neighbor in its own class, and each of the other 2 m ( q − p ) 2m(q-p) 2 m ( q − p ) nodes has its only neighbor in another class, so h V = 2 m p / ( 2 m q ) = h h_V = 2mp/(2mq) = h h V = 2 m p / ( 2 m q ) = h . Class 2 has no intra-class edge and an edge to class 1, so S G S_{\mathcal{G}} S G has a negative eigenvalue by the sufficient condition.
The signature is explicit. Class 1 has n 1 = m ( q + p ) n_1 = m(q + p) n 1 = m ( q + p ) nodes and m p ≥ 1 mp \ge1 m p ≥ 1 intra-class edges, so s 1 , 1 > 0 s_{1,1} > 0 s 1 , 1 > 0 . Each node of a class j ≥ 2 j \ge2 j ≥ 2 has its single edge to class 1, so s j , 1 = 1 / n 1 s_{j,1} = 1/n_1 s j , 1 = 1/ n 1 and s j , j ′ = 0 s_{j,j'} = 0 s j , j ′ = 0 for all j , j ′ ≥ 2 j,j' \ge2 j , j ′ ≥ 2 . Rows $2, \ldots, k$ of S G S_{\mathcal{G}} S G therefore all equal ( 1 / n 1 , 0 , … , 0 ) (1/n_1,0,\ldots,0) ( 1/ n 1 , 0 , … , 0 ) , while row 1 has the entry 1 / n 1 1/n_1 1/ n 1 in columns 2 , … , k 2,\ldots,k 2 , … , k , so S G S_{\mathcal{G}} S G has rank 2. One of its two nonzero eigenvalues is negative and their sum is tr S G = s 1 , 1 > 0 \operatorname{tr} S_{\mathcal{G}} = s_{1,1} > 0 tr S G = s 1 , 1 > 0 , so s G = ( 1 , ∣ L ∣ − 2 , 1 ) s_{\mathcal{G}} = (1, |L| - 2, 1) s G = ( 1 , ∣ L ∣ − 2 , 1 ) . For $|L| = 2,
S G = ( s 1 , 1 1 q + p 1 q + p 0 ) , s 1 , 1 > 0 , det S G = − 1 ( q + p ) 2 < 0. (33) S_{\mathcal{G}} =
\begin{pmatrix}
s_{1,1} & \frac{1}{q+p} \\
\frac{1}{q+p} & 0
\end{pmatrix},
\qquad s_{1,1} > 0,\qquad\det S_{\mathcal{G}} = -\frac{1}{(q+p)^2} < 0. \tag*{(33)} S G = ( s 1 , 1 q + p 1 q + p 1 0 ) , s 1 , 1 > 0 , det S G = − ( q + p ) 2 1 < 0. (33)
Proof and interpretations of Theorem 2.5
For a smooth map f : M → L f:\mathcal{M}\to\mathcal{L} f : M → L between differentiable manifolds M \mathcal{M} M and L \mathcal{L} L , the signature of the metric g g g over L \mathcal{L} L and that of the pullback f ∗ g f^*g f ∗ g over M \mathcal{M} M satisfy the following conditions:
Number of positive eigenvalues of ( f ∗ g ) p ≤ Number of positive eigenvalues of g f ( p ) \text{Number of positive eigenvalues of }(f^*g)_p \leq\text{Number of positive eigenvalues of }g_{f(p)} Number of positive eigenvalues of ( f ∗ g ) p ≤ Number of positive eigenvalues of g f ( p )
Number of negative eigenvalues of ( f ∗ g ) p ≤ Number of negative eigenvalues of g f ( p ) \text{Number of negative eigenvalues of }(f^*g)_p \leq\text{Number of negative eigenvalues of }g_{f(p)} Number of negative eigenvalues of ( f ∗ g ) p ≤ Number of negative eigenvalues of g f ( p )
Number of zero eigenvalues of ( f ∗ g ) p = dim R Ker ( T p f ) + dim R ( Im ( T p f ) ∩ Im ( T p f ) ⊥ g ) (34) \text{Number of zero eigenvalues of }(f^*g)_p = \dim_{\mathbb{R}}\operatorname{Ker}(T_pf) + \dim_{\mathbb{R}}\left(\operatorname{Im}(T_pf)\cap\operatorname{Im}(T_pf)^{\perp_g}\right) \tag*{(34)} Number of zero eigenvalues of ( f ∗ g ) p = dim R Ker ( T p f ) + dim R ( Im ( T p f ) ∩ Im ( T p f ) ⊥ g ) (34)
The second term in the last line is needed whenever g g g is indefinite. A linear map can be injective and still pull an indefinite form back to a degenerate one: for A = ( 1 , 1 ) T : R → R 1 , 1 A=(1,1)^{\mathsf{T}}:\mathbb{R}\to\mathbb{R}^{1,1} A = ( 1 , 1 ) T : R → R 1 , 1 with g = diag ( 1 , − 1 ) g=\operatorname{diag}(1,-1) g = diag ( 1 , − 1 ) we have ker A = 0 \operatorname{ker}A=0 ker A = 0 yet A T g A = 0 A^{\mathsf{T}}gA=0 A T g A = 0 , so the nullity is 1. The image of A A A is a null line, contained in its own g g g -orthogonal complement, which is exactly what the second term counts. When g g g is positive definite that intersection is trivial and the identity reduces to the familiar dim ker \dim\operatorname{ker} dim ker . The two inequalities on the positive and negative counts hold regardless.
By Sylvester’s law of inertia (Theorem 2.2), ϕ ∗ I \phi^*I ϕ ∗ I is positive-definite. Hence, for any pushforward T p f : T p M → T f ( p ) L T_pf:T_p\mathcal{M}\to T_{f(p)}\mathcal{L} T p f : T p M → T f ( p ) L , the eigenvalues of the pullback f ∗ ( ϕ ∗ I ) f^*(\phi^*I) f ∗ ( ϕ ∗ I ) satisfy:
Number of negative eigenvalues of ( f ∗ ( ϕ ∗ I ) ) p = 0 (35) \text{Number of negative eigenvalues of }\left(f^*(\phi^*I)\right)_p=0 \tag*{(35)} Number of negative eigenvalues of ( f ∗ ( ϕ ∗ I ) ) p = 0 (35)
On the other hand, if T p f T_pf T p f is surjective then Im ( T p f ) = T f ( p ) L \operatorname{Im}(T_pf)=T_{f(p)}\mathcal{L} Im ( T p f ) = T f ( p ) L , so a negative direction of S G S_{\mathcal{G}} S G has a preimage and the eigenvalues of the pullback f ∗ S G f^*S_{\mathcal{G}} f ∗ S G satisfy:
Number of negative eigenvalues of ( f ∗ S G ) p > 0 (36) \text{Number of negative eigenvalues of }(f^*S_{\mathcal{G}})_p>0 \tag*{(36)} Number of negative eigenvalues of ( f ∗ S G ) p > 0 (36)
Surjectivity is what this step needs, and it is strictly stronger than full rank when dim M < dim L \dim\mathcal{M}<\dim\mathcal{L} dim M < dim L : an injective map into a higher-dimensional indefinite space can miss every negative direction, as the example above shows. A linear map is surjective exactly when its rank equals dim L \dim\mathcal{L} dim L , which requires dim M ≥ dim L \dim\mathcal{M}\geq\dim\mathcal{L} dim M ≥ dim L and is not implied by it. In our setting T p f T_pf T p f is the projection W ∈ R ∣ L ∣ × h ′ W\in\mathbb{R}^{|\mathcal{L}|\times h'} W ∈ R ∣ L ∣ × h ′ of Equation (4) , and every configuration we report has h ′ > ∣ L ∣ h'>|\mathcal{L}| h ′ > ∣ L ∣ . The matrices of rank below ∣ L ∣ |\mathcal{L}| ∣ L ∣ are the common zero set of the ∣ L ∣ × ∣ L ∣ |\mathcal{L}|\times|\mathcal{L}| ∣ L ∣ × ∣ L ∣ minors, a proper algebraic subset of R ∣ L ∣ × h ′ \mathbb{R}^{|\mathcal{L}|\times h'} R ∣ L ∣ × h ′ of measure zero, so the hypothesis holds for almost every W W W , and almost surely at the random initialization. Therefore, there does not exist a diffeomorphism ϕ : L → L \phi:\mathcal{L}\to\mathcal{L} ϕ : L → L which induces ( ϕ ∘ f ) ∗ I = f ∗ S G (\phi\circ f)^*I=f^*S_{\mathcal{G}} ( ϕ ∘ f ) ∗ I = f ∗ S G . This concludes the proof of Theorem 2.5 .
We can also deduce the following three observations from Theorem 2.5 .
Discretization of graph diffusion processes [5 ] , which inherently assumes that the underlying topological space with graphs as subspaces is a Riemannian manifold, may have limited capabilities in analyzing relations among nodes of graphs whose S G S_{\mathcal{G}} S G has a negative eigenvalue.
Continuous node attributes of graphs may not be beneficial in classifying node labels of heterophilic graph data sets, implying that utilizing only the connectivity structure between node labels could be advantageous. Empirical evidence also supports this observation, as shown in [50].
Using adjacency matrices other than positive-definite symmetric matrices, such as graph laplacians, may boost results in classifying node labels of heterophilic graph data sets. Examples include using adjacency matrices multiplied with cosine similarities of node labels [44 ] or using sheaf graph laplacian operator, a type of block matrix which is not necessarily positive-definite (but positive-definite as a block matrix) [2 ] .
Topological structure on directed finite graphs in preparation for Definition 3.2
The parallel transport Γ γ e 1 , γ e 2 ( t 0 , s ) \Gamma_{\gamma_{e_1},\gamma_{e_2}}(t_0,s) Γ γ e 1 , γ e 2 ( t 0 , s ) for each t = t 0 t=t_0 t = t 0 is taken with respect to the flat connection of R h \mathbb{R}^h R h , so it translates vectors, preserving both their directions and lengths. Because the metric g = S g=S g = S is constant, this connection is compatible with g g g even when S S S is degenerate, and it is the Levi-Civita connection of g g g when S S S is non-degenerate. Since Γ \Gamma Γ acts as the identity on R h \mathbb{R}^h R h and S S S is symmetric, e γ e 1 , γ e 2 ( γ e 1 , γ e 2 ) = e γ e 2 , γ e 1 ( γ e 2 , γ e 1 ) e_{\gamma_{e_1},\gamma_{e_2}}(\gamma_{e_1},\gamma_{e_2})=e_{\gamma_{e_2},\gamma_{e_1}}(\gamma_{e_2},\gamma_{e_1}) e γ e 1 , γ e 2 ( γ e 1 , γ e 2 ) = e γ e 2 , γ e 1 ( γ e 2 , γ e 1 ) , which proves the commutative property of tangent attention scores.
This subsection describes suitable topological structures to impose on directed finite graphs so that we can rigorously define the tangent attention score matrix of a graph. We treat graphs with h h h -dimensional node features as subspaces of an h h h -dimensional connected pseudo-Riemannian manifold.
Without loss of generality, let G : = ( V , E ) \mathcal{G} := (\mathcal{V},\mathcal{E}) G := ( V , E ) be a finite directed graph with a node feature function X : V → R h X : \mathcal{V} \to\mathbb{R}^{h} X : V → R h . We may view undirected graphs as directed graphs by regarding each undirected edge between the node v v v and w w w as two reciprocal directed edges between them. Any graph G \mathcal{G} G can be viewed as a 1-dimensional topological space with nodes as discrete points and edges as unit intervals [ 0 , 1 ] [0,1] [ 0 , 1 ] [26 , 8 ] ; see Chapter 0 of [13 ] for further discussion. This presupposition allows us to extend a function of node features X : V → R h X : \mathcal{V} \to\mathbb{R}^{h} X : V → R h to a continuous function X γ : G → M X_{\gamma} : \mathcal{G} \to\mathcal{M} X γ : G → M for some h h h -dimensional pseudo-Riemannian manifold ( M , g ) (\mathcal{M},g) ( M , g ) , where each directed edge e e e from the source node v v v to the target node w w w , denoted as e : = ( v , w ) e := (v,w) e := ( v , w ) , is represented by a smooth curve of our choice γ e : [ 0 , 1 ] → M \gamma_{e} : [0,1] \to\mathcal{M} γ e : [ 0 , 1 ] → M satisfying the constraint that γ e ( 0 ) = X ( v ) \gamma_{e}(0) = X(v) γ e ( 0 ) = X ( v ) and γ e ( 1 ) = X ( w ) \gamma_{e}(1) = X(w) γ e ( 1 ) = X ( w ) . Figure 1 a illustrates how one may regard a directed graph G \mathcal{G} G as a subspace of M \mathcal{M} M .
Figure 1. Figure 1(a) illustrates how one can map a directed graph G \mathcal{G} G to a subspace of a pseudo-Riemannian manifold ( M , g ) (\mathcal{M},g) ( M , g ) . The nodes of G \mathcal{G} G correspond to points on M \mathcal{M} M , whereas the edges of G \mathcal{G} G correspond to curves on M \mathcal{M} M . Figure 1(b) demonstrates how one may compute tangent attention scores between two edges of G \mathcal{G} G using the pseudo-Riemannian metric g g g defined over the tangent space T γ 1 ( t ) M T_{\gamma_1(t)}\mathcal{M} T γ 1 ( t ) M at each point of the curve representing an edge.
Detailed description and proof of Theorem 3.3
This subsection shows, with proof, which choice of extension X γ X_{\gamma} X γ allows us to reconstruct a wide class of attention functions, including the dot-product attention from [38 ] , the single-layer feedforward linear layer from GAT [39 ] , and the dynamic graph attention from GATv2 [3 ] . Provided below is a detailed description of Theorem 3.3.
Theorem A.6. Let G : = ( V , E ) \mathcal{G} := (\mathcal{V},\mathcal{E}) G := ( V , E ) be a finite directed complete graph with self-loops, along with an h h h -dimensional node feature function X : V → R h X : \mathcal{V} \to\mathbb{R}^{h} X : V → R h . Fix a symmetric matrix S ∈ R h × h S \in\mathbb{R}^{h \times h} S ∈ R h × h which endows R h \mathbb{R}^{h} R h a pseudo-metric structure.
Suppose that for each edge e : = ( v , w ) ∈ E e := (v,w) \in\mathcal{E} e := ( v , w ) ∈ E , the curves γ e [ i ] : [ 0 , 1 ] → M ≅ R h \gamma_{e}^{[i]} : [0,1] \to\mathcal{M} \cong\mathbb{R}^{h} γ e [ i ] : [ 0 , 1 ] → M ≅ R h are given by:
γ e [ 1 ] ( t ) : = { ( 1 − t ) ⋅ X ( v ) + t ⋅ X ( w ) if v ≠ w ( 3 a v t ( t − 1 ) + 1 3 ) ⋅ X ( v ) if v = w (37) \gamma_{e}^{[1]}(t) := \begin{cases} (1-t)\cdot X(v)+t\cdot X(w) & \text{if }v\ne w \\ \left(\sqrt{3}\,a_{v}t(t-1)+\frac{1}{\sqrt{3}}\right)\cdot X(v) & \text{if }v=w \end{cases} \tag*{(37)} γ e [ 1 ] ( t ) := { ( 1 − t ) ⋅ X ( v ) + t ⋅ X ( w ) ( 3 a v t ( t − 1 ) + 3 1 ) ⋅ X ( v ) if v = w if v = w (37) γ e [ 2 ] ( t ) : = { ( 1 − t 2 ) ⋅ X ( v ) + t 3 ⋅ X ( w ) if v ≠ w X ( v ) + 6 t ( t − 1 ) ( 5 t − 3 ) ⋅ a v , 1 + 10 t ( t − 1 ) ( 2 t − 1 ) ⋅ a v , 2 if v = w (38) \gamma_{e}^{[2]}(t) := \begin{cases} (1-t^{2})\cdot X(v)+t^{3}\cdot X(w) & \text{if }v\ne w \\ X(v)+6t(t-1)(5t-3)\cdot a_{v,1}+10t(t-1)(2t-1)\cdot a_{v,2} & \text{if }v=w \end{cases} \tag*{(38)} γ e [ 2 ] ( t ) := { ( 1 − t 2 ) ⋅ X ( v ) + t 3 ⋅ X ( w ) X ( v ) + 6 t ( t − 1 ) ( 5 t − 3 ) ⋅ a v , 1 + 10 t ( t − 1 ) ( 2 t − 1 ) ⋅ a v , 2 if v = w if v = w (38) γ e [ 3 ] ( t ) : = { ( 1 − t ) ⋅ X ( v ) + t ⋅ X ( w ) + t ( t − 1 ) ⋅ a e if v ≠ w X ( v ) + 3 t ( t − 1 ) ⋅ a v , 3 if v = w (39) \gamma_{e}^{[3]}(t) := \begin{cases} (1-t)\cdot X(v)+t\cdot X(w)+t(t-1)\cdot a_{e} & \text{if }v\ne w \\ X(v)+3t(t-1)\cdot a_{v,3} & \text{if }v=w \end{cases} \tag*{(39)} γ e [ 3 ] ( t ) := { ( 1 − t ) ⋅ X ( v ) + t ⋅ X ( w ) + t ( t − 1 ) ⋅ a e X ( v ) + 3 t ( t − 1 ) ⋅ a v , 3 if v = w if v = w (39) for some fixed choices of set of scalars { a v } v ∈ V \{a_{v}\}_{v\in\mathcal{V}} { a v } v ∈ V and h h h -dimensional real vectors { a e } e ∈ E \{a_{e}\}_{e\in\mathcal{E}} { a e } e ∈ E , { a v , i } v ∈ V ⊂ R h \{a_{v,i}\}_{v\in\mathcal{V}}\subset\mathbb{R}^{h} { a v , i } v ∈ V ⊂ R h . Then given a pair of edges e 1 : = ( v 1 , w 1 ) e_{1}:=(v_{1},w_{1}) e 1 := ( v 1 , w 1 ) , e 2 : = ( v 2 , w 2 ) e_{2}:=(v_{2},w_{2}) e 2 := ( v 2 , w 2 ) , the ( e 1 , e 2 ) (e_{1},e_{2}) ( e 1 , e 2 ) -th entries of the tangent attention score matrices e G , γ [ i ] e_{\mathcal{G},\gamma^{[i]}} e G , γ [ i ] are equal to:
( e G , γ [ 1 ] ) e 1 , e 2 : = { ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) if v 1 ≠ w 1 , v 2 ≠ w 2 0 if v 1 ≠ w 1 , v 2 = w 2 0 if v 1 = w 1 , v 2 ≠ w 2 a v 1 a v 2 X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) if v 1 = w 1 , v 2 = w 2 (40) \left(e_{\mathcal{G},\gamma^{[1]}}\right)_{e_{1},e_{2}} := \begin{cases} \left(X(w_{1})-X(v_{1})\right)^{\mathsf{T}}\cdot S\cdot\left(X(w_{2})-X(v_{2})\right) & \text{if }v_{1}\ne w_{1},\ v_{2}\ne w_{2} \\ 0 & \text{if }v_{1}\ne w_{1},\ v_{2}=w_{2} \\ 0 & \text{if }v_{1}=w_{1},\ v_{2}\ne w_{2} \\ a_{v_{1}}a_{v_{2}}X(v_{1})^{\mathsf{T}}\cdot S\cdot X(v_{2}) & \text{if }v_{1}=w_{1},\ v_{2}=w_{2} \end{cases} \tag*{(40)} ( e G , γ [ 1 ] ) e 1 , e 2 := ⎩ ⎨ ⎧ ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) 0 0 a v 1 a v 2 X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 (40) ( e G , γ [ 2 ] ) e 1 , e 2 : = { ( 4 3 X ( v 1 ) − 3 2 X ( w 1 ) ) T ⋅ S ⋅ X ( v 2 ) if v 1 ≠ w 1 , v 2 ≠ w 2 ( 3 2 X ( v 1 ) − 3 5 X ( w 1 ) ) T ⋅ S ⋅ X ( w 2 ) if v 1 ≠ w 1 , v 2 = w 2 X ( v 1 ) T ⋅ S ⋅ ( a v 2 , 1 X ( v 1 ) + a v 2 , 2 ) if v 1 = w 1 , v 2 ≠ w 2 a v 1 , 1 T ⋅ S ⋅ X ( v 2 ) + a v 1 , 2 T ⋅ S ⋅ X ( w 2 ) if v 1 = w 1 , v 2 ≠ w 2 48 a v 1 , 1 T ⋅ S ⋅ a v 2 , 1 + 30 a v 1 , 1 T ⋅ S ⋅ a v 2 , 2 + 30 a v 1 , 2 T ⋅ S ⋅ a v 2 , 1 + 20 a v 1 , 2 T ⋅ S ⋅ a v 2 , 2 if v 1 = w 1 , v 2 = w 2 (41) \left(e_{\mathcal{G},\gamma^{[2]}}\right)_{e_{1},e_{2}} := \begin{cases} \left(\frac{4}{3}X(v_{1})-\frac{3}{2}X(w_{1})\right)^{\mathsf{T}}\cdot S\cdot X(v_{2}) & \text{if }v_{1}\ne w_{1},\ v_{2}\ne w_{2} \\ \left(\frac{3}{2}X(v_{1})-\frac{3}{5}X(w_{1})\right)^{\mathsf{T}}\cdot S\cdot X(w_{2}) & \text{if }v_{1}\ne w_{1},\ v_{2}=w_{2} \\ X(v_{1})^{\mathsf{T}}\cdot S\cdot\left(a_{v_{2},1}X(v_{1})+a_{v_{2},2}\right) & \text{if }v_{1}=w_{1},\ v_{2}\ne w_{2} \\ a_{v_{1},1}^{\mathsf{T}}\cdot S\cdot X(v_{2})+a_{v_{1},2}^{\mathsf{T}}\cdot S\cdot X(w_{2}) & \text{if }v_{1}=w_{1},\ v_{2}\ne w_{2} \\ 48a_{v_{1},1}^{\mathsf{T}}\cdot S\cdot a_{v_{2},1}+30a_{v_{1},1}^{\mathsf{T}}\cdot S\cdot a_{v_{2},2}+30a_{v_{1},2}^{\mathsf{T}}\cdot S\cdot a_{v_{2},1}+20a_{v_{1},2}^{\mathsf{T}}\cdot S\cdot a_{v_{2},2} & \text{if }v_{1}=w_{1},\ v_{2}=w_{2} \end{cases} \tag*{(41)} ( e G , γ [ 2 ] ) e 1 , e 2 := ⎩ ⎨ ⎧ ( 3 4 X ( v 1 ) − 2 3 X ( w 1 ) ) T ⋅ S ⋅ X ( v 2 ) ( 2 3 X ( v 1 ) − 5 3 X ( w 1 ) ) T ⋅ S ⋅ X ( w 2 ) X ( v 1 ) T ⋅ S ⋅ ( a v 2 , 1 X ( v 1 ) + a v 2 , 2 ) a v 1 , 1 T ⋅ S ⋅ X ( v 2 ) + a v 1 , 2 T ⋅ S ⋅ X ( w 2 ) 48 a v 1 , 1 T ⋅ S ⋅ a v 2 , 1 + 30 a v 1 , 1 T ⋅ S ⋅ a v 2 , 2 + 30 a v 1 , 2 T ⋅ S ⋅ a v 2 , 1 + 20 a v 1 , 2 T ⋅ S ⋅ a v 2 , 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 (41) ( e G , γ [ 3 ] ) e 1 , e 2 : = { ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) + 1 3 a e 1 T ⋅ S ⋅ a e 2 if v 1 ≠ w 1 , v 2 ≠ w 2 a e 1 T ⋅ S ⋅ a v 2 , 3 if v 1 ≠ w 1 , v 2 = w 2 a v 1 , 3 T ⋅ S ⋅ a e 2 if v 1 = w 1 , v 2 ≠ w 2 3 a v 1 , 3 T ⋅ S ⋅ a v 2 , 3 if v 1 = w 1 , v 2 = w 2 (42) \left(e_{\mathcal{G},\gamma^{[3]}}\right)_{e_{1},e_{2}} := \begin{cases} \left(X(w_{1})-X(v_{1})\right)^{\mathsf{T}}\cdot S\cdot\left(X(w_{2})-X(v_{2})\right)+\frac{1}{3}a_{e_{1}}^{\mathsf{T}}\cdot S\cdot a_{e_{2}} & \text{if }v_{1}\ne w_{1},\ v_{2}\ne w_{2} \\ a_{e_{1}}^{\mathsf{T}}\cdot S\cdot a_{v_{2},3} & \text{if }v_{1}\ne w_{1},\ v_{2}=w_{2} \\ a_{v_{1},3}^{\mathsf{T}}\cdot S\cdot a_{e_{2}} & \text{if }v_{1}=w_{1},\ v_{2}\ne w_{2} \\ 3a_{v_{1},3}^{\mathsf{T}}\cdot S\cdot a_{v_{2},3} & \text{if }v_{1}=w_{1},\ v_{2}=w_{2} \end{cases} \tag*{(42)} ( e G , γ [ 3 ] ) e 1 , e 2 := ⎩ ⎨ ⎧ ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) + 3 1 a e 1 T ⋅ S ⋅ a e 2 a e 1 T ⋅ S ⋅ a v 2 , 3 a v 1 , 3 T ⋅ S ⋅ a e 2 3 a v 1 , 3 T ⋅ S ⋅ a v 2 , 3 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 if v 1 = w 1 , v 2 = w 2 (42)
Proof. We prove the statement of the theorem for the curve γ e [ 1 ] : [ 0 , 1 ] → M \gamma_e^{[1]} : [0,1] \to\mathcal{M} γ e [ 1 ] : [ 0 , 1 ] → M . The remaining cases follow analogously. Let e 1 = ( v 1 , w 1 ) e_1=(v_1,w_1) e 1 = ( v 1 , w 1 ) , e 2 = ( v 2 , w 2 ) e_2=(v_2,w_2) e 2 = ( v 2 , w 2 ) be a pair of directed edges of a finite directed complete graph G G G .
Suppose v 1 ≠ w 1 v_1 \ne w_1 v 1 = w 1 and v 2 ≠ w 2 v_2 \ne w_2 v 2 = w 2 . Then we obtain that
γ ˙ e 1 [ 1 ] ( t ) = X ( w 1 ) − X ( v 1 ) γ ˙ e 2 [ 1 ] ( t ) = X ( w 2 ) − X ( v 2 ) (43) \begin{aligned}
\dot{\gamma}_{e_1}^{[1]}(t) &= X(w_1)-X(v_1) \\
\dot{\gamma}_{e_2}^{[1]}(t) &= X(w_2)-X(v_2) \tag*{(43)}
\end{aligned} γ ˙ e 1 [ 1 ] ( t ) γ ˙ e 2 [ 1 ] ( t ) = X ( w 1 ) − X ( v 1 ) = X ( w 2 ) − X ( v 2 ) (43)
Because both derivatives are constant functions with respect to the variable t t t ,
e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) . (44) e_{\gamma_{e_1},\gamma_{e_2}}\left(\dot{\gamma}_{e_1}^{[1]},\dot{\gamma}_{e_2}^{[1]}\right)
= \left(X(w_1)-X(v_1)\right)^T \cdot S \cdot\left(X(w_2)-X(v_2)\right). \tag*{(44)} e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( X ( w 1 ) − X ( v 1 ) ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) . (44)
If v 1 = w 1 v_1=w_1 v 1 = w 1 whereas v 2 ≠ w 2 v_2 \ne w_2 v 2 = w 2 , then
γ ˙ e 1 [ 1 ] ( t ) = 3 a v 1 ( 2 t − 1 ) ⋅ X ( v 1 ) γ ˙ e 2 [ 1 ] ( t ) = X ( w 2 ) − X ( v 2 ) (45) \begin{aligned}
\dot{\gamma}_{e_1}^{[1]}(t) &= \sqrt{3}a_{v_1}(2t-1)\cdot X(v_1) \\
\dot{\gamma}_{e_2}^{[1]}(t) &= X(w_2)-X(v_2) \tag*{(45)}
\end{aligned} γ ˙ e 1 [ 1 ] ( t ) γ ˙ e 2 [ 1 ] ( t ) = 3 a v 1 ( 2 t − 1 ) ⋅ X ( v 1 ) = X ( w 2 ) − X ( v 2 ) (45)
which leads to
e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( ∫ 0 1 3 a v 1 ( 2 t − 1 ) d t ) ⋅ ( X ( v 1 ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) ) = 0. (46) e_{\gamma_{e_1},\gamma_{e_2}}\left(\dot{\gamma}_{e_1}^{[1]},\dot{\gamma}_{e_2}^{[1]}\right)
= \left(\int_0^1 \sqrt{3}a_{v_1}(2t-1)\,dt\right)\cdot\left(X(v_1)^T\cdot S\cdot\left(X(w_2)-X(v_2)\right)\right)=0. \tag*{(46)} e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( ∫ 0 1 3 a v 1 ( 2 t − 1 ) d t ) ⋅ ( X ( v 1 ) T ⋅ S ⋅ ( X ( w 2 ) − X ( v 2 ) ) ) = 0. (46)
Lastly, if v 1 = w 1 v_1=w_1 v 1 = w 1 and v 2 = w 2 v_2=w_2 v 2 = w 2 , then
γ ˙ e 1 [ 1 ] ( t ) = 3 a v 1 ( 2 t − 1 ) ⋅ X ( v 1 ) γ ˙ e 2 [ 1 ] ( t ) = 3 a v 2 ( 2 t − 1 ) ⋅ X ( v 2 ) (47) \begin{aligned}
\dot{\gamma}_{e_1}^{[1]}(t) &= \sqrt{3}a_{v_1}(2t-1)\cdot X(v_1) \\
\dot{\gamma}_{e_2}^{[1]}(t) &= \sqrt{3}a_{v_2}(2t-1)\cdot X(v_2) \tag*{(47)}
\end{aligned} γ ˙ e 1 [ 1 ] ( t ) γ ˙ e 2 [ 1 ] ( t ) = 3 a v 1 ( 2 t − 1 ) ⋅ X ( v 1 ) = 3 a v 2 ( 2 t − 1 ) ⋅ X ( v 2 ) (47)
which gives
e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( ∫ 0 1 3 a v 1 a v 2 ( 2 t − 1 ) 2 d t ) ⋅ ( X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) ) = a v 1 a v 2 X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) . (48) \begin{aligned}
e_{\gamma_{e_1},\gamma_{e_2}}\left(\dot{\gamma}_{e_1}^{[1]},\dot{\gamma}_{e_2}^{[1]}\right)
&= \left(\int_0^1 3a_{v_1}a_{v_2}(2t-1)^2\,dt\right)\cdot\left(X(v_1)^T\cdot S\cdot X(v_2)\right) \\
&= a_{v_1}a_{v_2}X(v_1)^T\cdot S\cdot X(v_2). \tag*{(48)}
\end{aligned} e γ e 1 , γ e 2 ( γ ˙ e 1 [ 1 ] , γ ˙ e 2 [ 1 ] ) = ( ∫ 0 1 3 a v 1 a v 2 ( 2 t − 1 ) 2 d t ) ⋅ ( X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) ) = a v 1 a v 2 X ( v 1 ) T ⋅ S ⋅ X ( v 2 ) . (48)
Theorem 3.3 demonstrates that previously researched attention scores correspond to computing the tangent attention score between two directed edges where at least one of them is a self-loop at each node of G G G . The dot product attention score from the encoder layer of attention-transformers [38 ] with identical query and key weight matrices is equal to the tangent attention score between two self-loops represented by γ e [ 1 ] \gamma_e^{[1]} γ e [ 1 ] , with S = W T W S=W^TW S = W T W a symmetric matrix obtained from a product of invertible square weight matrix W ∈ R h × h W\in\mathbb{R}^{h\times h} W ∈ R h × h . With the same symmetric matrix S S S , the attention score of the single-layer feedforward linear layer in [39 ] can be obtained from the tangent attention score between a self-loop and a directed edge represented by γ e [ 2 ] \gamma_e^{[2]} γ e [ 2 ] . Lastly, by setting S S S to be the identity matrix I I I , and by choosing the fixed vector a e a_e a e as a e = LeakyRelu ( W [ X ( v ) ∣ ∣ X ( w ) ] ) a_e=\operatorname{LeakyRelu}(W[X(v)||X(w)]) a e = LeakyRelu ( W [ X ( v ) ∣∣ X ( w )]) for each edge e = ( v , w ) ∈ E e=(v,w)\in\mathcal{E} e = ( v , w ) ∈ E and every a v , 3 a_{v,3} a v , 3 as the shared attention vector a ∈ R h a\in\mathbb{R}^h a ∈ R h of GATv2, where [ X ( v ) ∣ ∣ X ( w ) ] ∈ R 2 h [X(v)||X(w)]\in\mathbb{R}^{2h} [ X ( v ) ∣∣ X ( w )] ∈ R 2 h is a concatenation of two node feature vectors, and W ∈ R h × 2 h W\in\mathbb{R}^{h\times2h} W ∈ R h × 2 h is a weight matrix, the tangent attention score between a self-loop and a directed edge represented by γ e [ 3 ] \gamma_e^{[3]} γ e [ 3 ] is equal to the dynamic graph attention score constructed from [3 ] .
Geometric Framework of PRAT
In Figure 7 , H ( l ) ≅ R h ′ \mathcal{H}^{(l)}\cong\mathbb{R}^{h'} H ( l ) ≅ R h ′ denotes the hidden manifold at layer l l l , and L ≅ R ∣ L ∣ \mathcal{L}\cong\mathbb{R}^{|L|} L ≅ R ∣ L ∣ is the common latent manifold corresponding to the node labels. The encoder ψ e n c : M → H ( 0 ) \psi_{\mathrm{enc}}:\mathcal{M}\to\mathcal{H}^{(0)} ψ enc : M → H ( 0 ) calibrates node features to the initial hidden feature.
Figure 7. Geometric interpretation of PRAT. Each hidden manifold H ( l ) \mathcal{H}^{(l)} H ( l ) is mapped to the common latent manifold L \mathcal{L} L via φ ( l ) \varphi^{(l)} φ ( l ) .
For each layer l l l , we posit the existence of a linear map φ ( l ) : H ( l ) → L \varphi^{(l)}:\mathcal{H}^{(l)}\to\mathcal{L} φ ( l ) : H ( l ) → L , which projects the hidden representation to the label space. While the final layer’s map φ ( l max ) \varphi^{(l_{\max})} φ ( l m a x ) acts as the explicit readout function for classification, the intermediate maps φ ( l ) \varphi^{(l)} φ ( l ) (for l < l max l<l_{\max} l < l m a x ) provide a critical geometric link: they allow us to transport the intrinsic geometric structure of the latent manifold back to the hidden manifolds.
Let g L g_{\mathcal{L}} g L be the pseudo-metric tensor defined on L \mathcal{L} L , represented by a symmetric matrix S ∣ L ∣ S^{\lvert L\rvert} S ∣ L ∣ . To ensure that the hidden representations at layer l l l respect the global structural prior of the latent space, we set the metric on H ( l ) \mathcal{H}^{(l)} H ( l ) to the pullback metric induced by φ ( l ) \varphi^{(l)} φ ( l ) . Hence, the pseudo-metric on H ( l ) \mathcal{H}^{(l)} H ( l ) is determined by pulling back g L g_{\mathcal{L}} g L via φ ( l ) \varphi^{(l)} φ ( l ) :
g H ( l ) = ( φ ( l ) ) ∗ g L . (49) g_{\mathcal{H}^{(l)}} = \left(\varphi^{(l)}\right)^{*}g_{\mathcal{L}}. \tag*{(49)} g H ( l ) = ( φ ( l ) ) ∗ g L . (49)
Considering the multi-head attention mechanism where k k k denotes the head index, the projection φ ( l ) \varphi^{(l)} φ ( l ) is parameterized by a weight matrix W φ [ l , k ] \mathbf{W}_{\varphi}^{[l,k]} W φ [ l , k ] . The induced metric tensor D [ l , k ] \mathbf{D}^{[l,k]} D [ l , k ] for the k k k -th head at layer l l l is then derived as:
D [ l , k ] = ( W φ [ l , k ] ) ⊤ S ∣ L ∣ W φ [ l , k ] , (50) \mathbf{D}^{[l,k]} = \left(\mathbf{W}_{\varphi}^{[l,k]}\right)^{\top} S^{\lvert L\rvert}\mathbf{W}_{\varphi}^{[l,k]}, \tag*{(50)} D [ l , k ] = ( W φ [ l , k ] ) ⊤ S ∣ L ∣ W φ [ l , k ] , (50)
which is identical to the expression for D [ l , k ] \mathbf{D}^{[l,k]} D [ l , k ] in Equation (4) .
Benchmark Datasets
We use fifteen real-world benchmarks in two groups: (i) eight standard benchmarks spanning homophilic and heterophilic regimes, and (ii) seven Platonov benchmarks [28 ] consisting of filtered Wikipedia networks and five large-scale heterophilic datasets.
Standard benchmarks.
Citation Networks (Cora, Citeseer, PubMed) Standard benchmark datasets representing citation relationships between scientific publications [32 , 45 ] . Nodes correspond to documents, and edges denote citation links. For each node, the features are typically sparse bag-of-words vectors derived from the document text, and the label indicates the subject category of the paper.
Wikipedia Networks (Chameleon, Squirrel) These are page-page networks derived from Wikipedia [30 ] . Nodes represent Wikipedia articles, and edges indicate mutual hyperlinks between them. Node features are informative nouns extracted from the corresponding article, and the node label represents the average monthly traffic of the webpage.
Actor Co-occurrence Network (Actor) The Actor dataset (often referred to as Film) [35 ] is a subgraph of a film-director-actor-writer network. Nodes represent actors, and edges signify co-occurrence on the same Wikipedia page. Node features are derived from keywords on the actor’s Wikipedia page, and node labels are determined by the words found on the webpage.
Webpage Networks (Texas, Cornell) Subsets of the WebKB dataset6 . Nodes represent university webpages, and edges represent hyperlinks between them. For each node, the features are bag-of-words representations of the webpage content, and the node label denotes the category of the webpage.
Platonov benchmarks [28 ] .
Filtered Wikipedia networks (Chameleon-filtered, Squirrel-filtered) Platonov et al. [28 ] identified that 57–61% of nodes in the original Chameleon and Squirrel datasets are exact duplicates with identical neighborhoods and labels, causing severe train–test leakage. The filtered versions remove these duplicate nodes, yielding 890 and 2,223 nodes respectively. Node features and class definitions follow the original Rozemberczki et al. [30 ] construction. These filtered benchmarks are widely adopted in subsequent heterophily research as a more reliable proxy for the underlying task.
roman-empire Each node corresponds to a non-unique word in the English Wikipedia article “Roman Empire,” and edges connect words that are syntactically dependent or sequential in the article. Node features are GloVe-300 embeddings of the word, and the 18-class label is the syntactic role assigned by spaCy. With h E = 0.05 h_E = 0.05 h E = 0.05 , this is the most extreme heterophilic dataset in the suite.
amazon-ratings A product co-purchase network from Amazon, where nodes are products (books, music CDs, DVDs, VHS tapes) and edges connect frequently co-purchased products. Node features are the mean of fastText embeddings of the product description, and the 5-class label is the average rating, binned into five ranges.
minesweeper A synthetic 100 × 100 100 \times100 100 × 100 grid graph from the Minesweeper game: nodes are cells, edges connect each cell to its eight surrounding neighbors, and 20% of cells are randomly designated as mines (the binary class). Node features are 7-dimensional one-hot encodings of the number of neighboring mines for non-mine cells (with mine cells masked); the resulting graph has very low-dimensional node features and a regular topological structure.
tolokers A worker-collaboration network from the Toloka crowdsourcing platform, where nodes are workers and edges connect workers who co-completed at least one task. Node features include task performance and profile statistics, and the binary label indicates whether a worker was banned. With over 519K edges over 11.8K nodes, tolokers is the densest graph in the suite.
questions A user-interaction network on the Yandex.Q question-answering site, where nodes are users and edges connect users who answered each other’s questions during a one-year window. Node features are FastText embeddings of the user description, and the binary label indicates account activity at the end of the window. With 48,921 nodes, this is the largest graph in the suite.
Analysis on Graph Signature Index. Figure 8 illustrates the eigenvalue distributions of the graph signature matrices for all benchmark datasets, revealing distinct structural characteristics. Among the standard benchmarks, the Actor dataset stands out for its many zero eigenvalues. Its signature s G = ( 1 , 4 , 0 ) s_G = (1, 4, 0) s G = ( 1 , 4 , 0 ) indicates connectivity of numerical rank one at the 10 − 4 10^{-4} 1 0 − 4 threshold, where all 5 classes share nearly identical edge density patterns, with 4 out of 5 label-space dimensions carrying negligible discriminative signal. PRAT leverages this by learning Λ \Lambda Λ values near zero for the corresponding dimensions during training, effectively projecting out uninformative directions and concentrating the metric on the single informative one. This “feature selection via metric learning” explains why PRAT achieves the best accuracy on Actor despite the absence of negative eigenvalues: the pseudo-Riemannian framework naturally accommodates zero eigenvalues, providing a mechanism to suppress noise that other methods aggregate indiscriminately.
Figure 8. Eigenvalue distributions of the graph signature matrix of the full labeled graph (Definition 2.1) for all fifteen benchmark datasets (eight standard + seven Platonov), which give the signatures of Table 1 and Table 2. Eigenvalues with ∣ λ ∣ < 1.0 × 10 − 4 |\lambda| < 1.0 \times10^{-4} ∣ λ ∣ < 1.0 × 1 0 − 4 are rounded to zero for reporting.
Synthetic Data Generation
Synthetic datasets are generated based on Model 1 proposed in Appendix B of [15 ] . According to this model, each node feature is initially sampled from a Bernoulli distribution, yielding binary values of 0 or 1. However, we observed that this formulation results in class labels being trivially predictable by GNNs, leading to near-perfect accuracy even in highly heterophilic regimes.
To address this limitation and make classification harder, we modify the original model’s features. We add class-independent Gaussian noise of standard deviation 0.4 to each node feature, thereby transforming the discrete binary features into continuous values and increasing the difficulty of class discrimination. The added noise prevents perfect predictions while preserving the synthetic dataset’s underlying structure.
For graph construction, given a target number of edges, a desired homophily level h E ∈ [ 0 , 1 ] h_E \in[0, 1] h E ∈ [ 0 , 1 ] , and a target graph signature index, we first compute the number of homophilic edges as ∣ E h o m o ∣ = h E ⋅ ∣ E ∣ |E_{homo}| = h_E \cdot|E| ∣ E h o m o ∣ = h E ⋅ ∣ E ∣ and heterophilic edges as ∣ E h e t e r o ∣ = ∣ E ∣ − ∣ E h o m o ∣ |E_{hetero}| = |E| - |E_{homo}| ∣ E h e t er o ∣ = ∣ E ∣ − ∣ E h o m o ∣ . To ensure the resulting graph matches the specified signature index, these edge counts are strategically distributed across valid intra-class and inter-class pairs by a random search over at most 2,000 symmetric candidates for a class-connectivity matrix that satisfies both the homophily and signature constraints. Homophilic edges are then generated by randomly sampling node pairs within the same class, while heterophilic edges are created by connecting nodes from different classes according to the determined connectivity matrix. Certain combinations of homophily levels and signature indices are mathematically incompatible; in such cases, synthetic data generation is restricted. This procedure precisely controls both the graph’s homophily ratio and signature index, enabling systematic evaluation of model performance across diverse structural scenarios. Every graph is generated with seed 42, the five random splits use seeds 42 to 46, and every model is trained with seed 42.
Eigenvalue Evolution. Figure 9 illustrates the evolution of eigenvalues in the graph signature matrix across synthetic datasets generated with varying homophily levels. At the heterophilic extreme (h E = 0 h_E = 0 h E = 0 ), the graph signature index is ( 1 , 0 , 4 ) (1, 0, 4) ( 1 , 0 , 4 ) , indicating a predominance of negative eigenvalues. As h E h_E h E increases, these eigenvalues exhibit a continuous upward trend, eventually transitioning to a strictly positive regime. This trajectory closely mirrors the sign evolution of the learned metric observed in Figure 3 . These findings provide empirical evidence that PRAT successfully leverages the underlying topological information regarding graph homophily.
Figure 9. Evolution of eigenvalues of graph signature matrix across varying homophily levels. As homophily increases, eigenvalues change from mixed signs to positive values, indicating a shift from pseudo-Riemannian to Riemannian geometry.
Computational Complexity Analysis
We analyze the computational complexity of PRAT compared to other attention-based models. Let N N N denote nodes, E E E edges, H H H hidden dimension, C C C classes, K K K attention heads, and L L L layers. H / K H/K H / K is the per-head dimension.
Time Complexity
Theorem E.1 (PRAT Layer Complexity). The time complexity of a single PRAT layer is O ( N H ( H + K C ) + E ( H + K C ) ) \mathcal{O}\left(NH(H + KC) + E(H + KC)\right) O ( N H ( H + K C ) + E ( H + K C ) ) .
Proof. PRAT has operations:
Latent space projection (X W XW X W , W ∈ R H × K C W \in\mathbb{R}^{H \times KC} W ∈ R H × K C ): O ( N H K C ) \mathcal{O}(NHKC) O ( N H K C )
Value projection (X W V XW_V X W V , W V ∈ R H × H W_V \in\mathbb{R}^{H \times H} W V ∈ R H × H ): O ( N H 2 ) \mathcal{O}(NH^2) O ( N H 2 )
Attention scores (difference, square, weighted sum per edge): O ( E K C ) \mathcal{O}(EKC) O ( E K C )
Softmax and aggregation: O ( E K + E H ) \mathcal{O}(EK + EH) O ( E K + E H )
Theorem E.2 (GAT/GATv2 Layer Complexity). The time complexity of GAT and GATv2 layers is O ( N H 2 + E H ) \mathcal{O}(NH^2 + EH) O ( N H 2 + E H ) .
Proof. GAT computes e i j = LeakyReLU ( a ⊤ [ W h i ∥ W h j ] ) e_{ij} = \operatorname{LeakyReLU}(\mathbf{a}^{\top}[\mathbf{W}\mathbf{h}_i \Vert\mathbf{W}\mathbf{h}_j]) e ij = LeakyReLU ( a ⊤ [ W h i ∥ W h j ]) :
Feature transform (X W XW X W ): O ( N H 2 ) \mathcal{O}(NH^2) O ( N H 2 )
Attention computation (concatenation + linear per edge): O ( E K ( H / K ) ) = O ( E H ) \mathcal{O}(EK(H/K)) = \mathcal{O}(EH) O ( E K ( H / K )) = O ( E H )
Softmax and aggregation: O ( E K + E H ) \mathcal{O}(EK + EH) O ( E K + E H )
GATv2 applies LeakyReLU before the attention vector but has identical complexity.
Theorem E.3 (SDP Layer Complexity). The time complexity of Scaled Dot-Product attention is O ( 3 N H 2 + E H ) \mathcal{O}(3NH^2 + EH) O ( 3 N H 2 + E H ) .
Proof. SDP computes e i j = ( Q i ⋅ K j ) / d k e_{ij} = (\mathbf{Q}_i \cdot\mathbf{K}_j)/\sqrt{d_k} e ij = ( Q i ⋅ K j ) / d k with three projections:
Query, key, and value projections: O ( 3 N H 2 ) \mathcal{O}(3NH^2) O ( 3 N H 2 )
Dot product per edge: O ( E K ( H / K ) ) = O ( E H ) \mathcal{O}(EK(H/K)) = \mathcal{O}(EH) O ( E K ( H / K )) = O ( E H )
Softmax and aggregation: O ( E K + E H ) \mathcal{O}(EK + EH) O ( E K + E H )
Table 6 summarizes the time complexity of PRAT and attention-based models. PRAT shares asymptotic complexity O ( N H 2 + E H ) \mathcal{O}(NH^2 + EH) O ( N H 2 + E H ) with GAT and GATv2 since K C KC K C is typically small relative to H H H (e.g., K = 4 K=4 K = 4 , C = 5 C=5 C = 5 , H = 64 H=64 H = 64 gives K C = 20 < 64 KC=20 < 64 K C = 20 < 64 ).
Table 6. Time complexity comparison per layer.
Parameter Count
For a model with encoder, L L L attention layers, and decoder:
Theorem E.4 (Parameter Counts). The total parameters for each model are:
P P R A T = ( F + 1 ) H + L ( H 2 + H K C + H + K C + K ) + ( H + 1 ) C (51) P_{PRAT}=(F+1)H+L(H^2+HKC+H+KC+K)+(H+1)C \tag*{(51)} P P R A T = ( F + 1 ) H + L ( H 2 + H K C + H + K C + K ) + ( H + 1 ) C (51) P G A T = ( F + 1 ) H + L ( H 2 + 3 H ) + ( H + 1 ) C (52) P_{GAT}=(F+1)H+L(H^2+3H)+(H+1)C \tag*{(52)} P G A T = ( F + 1 ) H + L ( H 2 + 3 H ) + ( H + 1 ) C (52) P G A T v 2 = ( F + 1 ) H + L ( H 2 + 3 H ) + ( H + 1 ) C (53) P_{GATv2}=(F+1)H+L(H^2+3H)+(H+1)C \tag*{(53)} P G A T v 2 = ( F + 1 ) H + L ( H 2 + 3 H ) + ( H + 1 ) C (53) P S D P = ( F + 1 ) H + L ( 3 H 2 + 3 H ) + ( H + 1 ) C (54) P_{SDP}=(F+1)H+L(3H^2+3H)+(H+1)C \tag*{(54)} P S D P = ( F + 1 ) H + L ( 3 H 2 + 3 H ) + ( H + 1 ) C (54)
Proof. Per-layer parameters:
PRAT: W ∈ R H × K C \mathbf{W}\in\mathbb{R}^{H\times KC} W ∈ R H × K C without bias, W V ∈ R H × H \mathbf{W}_{V}\in\mathbb{R}^{H\times H} W V ∈ R H × H with bias, the C C C diagonal entries of the learnable metric held for each of the K K K heads, Λ ∈ R K × C \Lambda\in\mathbb{R}^{K\times C} Λ ∈ R K × C , self-loop scaling parameters { a } ∈ R K \{a\}\in\mathbb{R}^{K} { a } ∈ R K . Total: H K C + H 2 + H + K C + K HKC+H^2+H+KC+K H K C + H 2 + H + K C + K .
GAT/GATv2: W ∈ R H × H \mathbf{W}\in\mathbb{R}^{H\times H} W ∈ R H × H and an output bias, with a ∈ R 2 H a\in\mathbb{R}^{2H} a ∈ R 2 H for GAT; GATv2 shares W \mathbf{W} W between source and target and adds a bias to it, with a ∈ R H a\in\mathbb{R}^{H} a ∈ R H . Total: H 2 + 3 H H^2+3H H 2 + 3 H .
SDP: W Q , W K , W V ∈ R H × H \mathbf{W}_{Q},\mathbf{W}_{K},\mathbf{W}_{V}\in\mathbb{R}^{H\times H} W Q , W K , W V ∈ R H × H each with bias. Total: 3 H 2 + 3 H 3H^2+3H 3 H 2 + 3 H .
Single layer MLP encoder and decoder contribute ( F + 1 ) H (F+1)H ( F + 1 ) H and ( H + 1 ) C (H+1)C ( H + 1 ) C , respectively, for all models.
Table 7 shows that PRAT has modestly more parameters than GAT and GATv2 because of its learnable metric components. Since K C < H KC < H K C < H in practice, this overhead remains negligible. Moreover, PRAT is substantially more parameter-efficient than SDP attention, which requires separate query, key, and value projections.
Table 7. Parameter count per layer (H = 64 H=64 H = 64 , C = 5 C=5 C = 5 , K = 4 K=4 K = 4 ).
Measured cost
The asymptotics above say that PRAT and GAT are in the same class. Table 8 shows what that means in practice, measured on the two largest graphs with the same backbone, width, depth and number of steps, so that the only difference is the attention module.
Table 8. Training cost per step and peak memory, measured on one A100 80GB with identical backbone, width and depth.
PRAT adds 80 parameters over GAT on questions, out of 2.83 million, and 32 on tolokers. The step time is 0.97 times GAT’s on questions and 1.17 on tolokers, and peak memory is 1.03 and 1.20 times GAT’s. On questions, PRAT and GAT are indistinguishable at that scale: single-step timing has run-to-run spread of the same order, so their timings do not establish that PRAT is faster. GT, whose attention is also restricted to graph neighbors, costs 1.92 times GAT on questions and needs 2.4 times the parameters.
Experimental Details
Signature estimation. S G , t r a i n \mathcal{S}_{G,\mathrm{train}} S G , train is Definition 2.1 applied to the subgraph induced by the training nodes, with self-loops removed: an edge counts only when both endpoints are training nodes, the class sizes in the denominator are training-node counts, and a class with no training node contributes a zero row and column. Λ i n i t \Lambda_{\mathrm{init}} Λ init is computed from the unrounded eigenvalues, with std ( ⋅ ) \operatorname{std}(\cdot) std ( ⋅ ) the population standard deviation over the ∣ L ∣ |L| ∣ L ∣ eigenvalues. When all eigenvalues are equal, so that this deviation is zero, the division is skipped and Λ i n i t = Λ G , t r a i n / ∣ L ∣ \Lambda_{\mathrm{init}} = \Lambda_{G,\mathrm{train}}/\sqrt{|L|} Λ init = Λ G , train / ∣ L ∣ ; the identity initialization of Table 15 takes this path. The 10 − 4 10^{-4} 1 0 − 4 rounding of Figure 8 is applied to the unnormalized eigenvalues and only for reported inertias.
Table 15. Label-free initialization. The inertia is that of the eigenvalue vector each initialization is built from, before normalization, at the 10 − 4 10^{-4} 1 0 − 4 rounding convention of Figure 8; the two signature estimates use the training nodes.
Hyperparameters
Standard Benchmark Experiments. For experiments on the eight standard benchmarks, the hyperparameters of every model (PRAT and baselines) were selected via a hyperparameter sweep over the search ranges and distributions listed in Table 9 , with the best configuration chosen by validation accuracy.
Table 9. Hyperparameter search ranges used for the standard benchmark experiments.
Platonov Benchmark Experiments. For experiments on the seven Platonov et al. [28 ] benchmarks (filtered Chameleon/Squirrel and the five large-scale heterophilic datasets), PRAT’s hyperparameters were selected via a sweep starting from the official PRAT-compatible defaults of Platonov et al. [28 ] (hidden channels 512, layers ∈ { 1 , 2 , 3 , 4 , 5 } \in\{1, 2, 3, 4, 5\} ∈ { 1 , 2 , 3 , 4 , 5 } , lr 3 × 10 − 5 3 \times10^{-5} 3 × 1 0 − 5 , dropout 0.2, 1,000 training steps), and we report 10-split mean ± \pm ± std on the official predefined splits. Table 10 lists the selected configurations.
Table 10: Selected PRAT configurations on the Platonov benchmarks, shared by Table 4 and the matched run of Section I.1. Every configuration uses LayerNorm, AdamW and training seed 42; warmup is a fraction of the training steps.
Table 10.
Synthetic Data Experiments. When training models on synthetic data, we employed a fixed set of hyperparameters shown in Table 11 across all synthetic datasets and models. This controlled setup ensures that any observed performance fluctuations are solely attributable to changes in the homophily level or graph signature index, thus facilitating a clear analysis of the behavioral trends and stability of each method.
Table 11: Configuration for synthetic data experiments.
Table 11.
Computing Resources
All experiments we conducted for this paper were run on a single NVIDIA A100 80GB GPU. The baseline rows of Table 4 are quoted from Platonov et al. [28 ] , and the Geom-GCN results from Yan et al. [44 ] . No multi-GPU or multi-node training was used. One full hyperparameter sweep per dataset takes between 0.5 and 8 GPU-hours depending on dataset size, after which the selected configuration is rerun across multiple splits for the reported test mean / standard deviation. Final 10-split evaluations on the Platonov benchmarks (Table 4 ) require an additional ∼ 0.5 \sim0.5 ∼ 0.5 –2 GPU-hours per dataset. The total compute budget across the project, including preliminary and discarded configurations not reported in the paper, is conservatively estimated at ∼ 200 \sim200 ∼ 200 A100-hours.
Table 4. Performance on Platonov et al. [28 ] benchmarks. Accuracy (↑ \uparrow ↑ ) is reported for roman-empire, amazon-ratings, Cham.-filt., Sq.-filt.; ROC AUC (↑ \uparrow ↑ ) for minesweeper, tolokers, questions. † ^{\dagger} † Best per dataset of the graph-agnostic ResNet of Platonov et al. [28 ] and its graph-aware variants ResNet+SGC and ResNet+adj.
Calibration of the Self-Loop Scaling Parameter
From the tangent attention framework in Appendix § 8 .§ 27 , self-loop scores involve a scaling coefficient applied to the quadratic form h v T D h v h_v^{\mathsf{T}}\mathbf{D}h_v h v T D h v . We derive a principled initialization for the self-loop scaling parameter a a a by matching expected attention scores.
Pseudo-Label Representation. Assume hidden features encode noisy pseudo-labels in the latent space L \mathcal{L} L :
W h v = e ℓ ( v ) + ϵ v , ϵ v ∼ N ( 0 , σ 2 I ∣ L ∣ ) , (55) \mathbf{W}h_v=e_{\ell(v)}+\epsilon_v,\qquad\epsilon_v\sim\mathcal{N}(0,\sigma^2 I_{|\mathcal{L}|}), \tag*{(55)} W h v = e ℓ ( v ) + ϵ v , ϵ v ∼ N ( 0 , σ 2 I ∣ L ∣ ) , (55)
where W is the weight matrix from Equation (4) . e i ∈ R ∣ L ∣ e_i \in\mathbb{R}^{|\mathcal{L}|} e i ∈ R ∣ L ∣ is the one-hot encoding of label i i i and σ 2 \sigma^2 σ 2 quantifies the noise level in the representation.
Matching Condition. Using the graph signature matrix S G \mathbf{S}_{\mathcal{G}} S G as the metric tensor and the proportional allocation model introduced in Appendix § 8 .§ 23 , matching the expected self-loop and edge scores yields, for h E > 0 h_E > 0 h E > 0 :
a ( 1 + σ 2 ∣ L ∣ ) = 2 ( 1 − h E ) ( h E − h E ∗ ) h E ( 1 − h E ∗ ) + 2 σ 2 ∣ L ∣ , (56) a(1+\sigma^2|\mathcal{L}|)=\frac{2(1-h_E)(h_E-h_E^*)}{h_E(1-h_E^*)}+2\sigma^2|\mathcal{L}|, \tag*{(56)} a ( 1 + σ 2 ∣ L ∣ ) = h E ( 1 − h E ∗ ) 2 ( 1 − h E ) ( h E − h E ∗ ) + 2 σ 2 ∣ L ∣ , (56)
where h E ∗ = ∑ k = 1 ∣ L ∣ ( n k / N ) 2 h_E^* = \sum_{k=1}^{|L|} (n_k/N)^2 h E ∗ = ∑ k = 1 ∣ L ∣ ( n k / N ) 2 is the critical homophily threshold from Theorem 2.3 , with n k n_k n k denoting the number of nodes in class k k k . Solving for a a a :
a = 2 ( 1 − h E ) ( h E − h E ∗ ) h E ( 1 − h E ∗ ) + 2 σ 2 ∣ L ∣ 1 + σ 2 ∣ L ∣ . (57) a = \frac{\frac{2(1-h_E)(h_E-h_E^*)}{h_E(1-h_E^*)}+2\sigma^2|L|}{1+\sigma^2|L|}. \tag*{(57)} a = 1 + σ 2 ∣ L ∣ h E ( 1 − h E ∗ ) 2 ( 1 − h E ) ( h E − h E ∗ ) + 2 σ 2 ∣ L ∣ . (57)
Noise-Dominated Initialization. At the onset of training, before the network has learned label-discriminative representations, the hidden features are approximately uninformative about class labels, corresponding to the high-noise regime. In this regime, the structure-dependent term 2 ( 1 − h E ) ( h E − h E ∗ ) h E ( 1 − h E ∗ ) \frac{2(1-h_E)(h_E-h_E^*)}{h_E(1-h_E^*)} h E ( 1 − h E ∗ ) 2 ( 1 − h E ) ( h E − h E ∗ ) contributes negligibly compared to the noise-driven term 2 σ 2 ∣ L ∣ 2\sigma^2|L| 2 σ 2 ∣ L ∣ . Consequently, Equation (57) simplifies to:
a i n i t ≃ 2 σ 2 ∣ L ∣ σ 2 ∣ L ∣ = 2. (58) a_{\mathrm{init}} \simeq\frac{2\sigma^2|L|}{\sigma^2|L|}=2. \tag*{(58)} a init ≃ σ 2 ∣ L ∣ 2 σ 2 ∣ L ∣ = 2. (58)
This initial value is independent of both the homophily level h E h_E h E and the class distribution { n k } \{n_k\} { n k } , providing a universal, structure-agnostic initialization.
Separation of Concerns. This derivation reveals a principled division of roles between PRAT’s two learnable components:
Metric tensor Λ \Lambda Λ : Encodes the geometric structure of the graph. Initialized from the graph signature eigenvalues Λ G , t r a i n \Lambda_{G,\mathrm{train}} Λ G , train , it captures whether the underlying manifold is Riemannian or pseudo-Riemannian, directly reflecting the homophilic or heterophilic nature of the graph.
Self-loop scaling a a a : Controls the signal-to-noise balance in attention computation. Initialized at 2 corresponding to uninformative representations, it adapts during training as the network learns discriminative features.
Statistical reliability
How the reported margins are tested, and how the spread divides between seeds and splits.
Statistical significance
Several margins in Table 3 and Table 4 are small relative to the split deviation, so we test them at two levels.
A Friedman test over all models of each table rejects equality of mean ranks on both suites, and PRAT holds the best mean rank on each: 2.63 against 2.88 for BernNet on the standard suite, with χ 2 = 54.46 \chi^2 = 54.46 χ 2 = 54.46 , p = 4.4 × 10 − 6 p = 4.4 \times10^{-6} p = 4.4 × 1 0 − 6 , and 1.86 against 4.57 for GT-sep on the Platonov suite, with χ 2 = 67.59 \chi^2 = 67.59 χ 2 = 67.59 , p = 1.2 × 10 − 8 p = 1.2 \times10^{-8} p = 1.2 × 1 0 − 8 . With eight and seven datasets the Nemenyi critical difference is 8.73 and 8.72 rank units at α = 0.05 \alpha= 0.05 α = 0.05 , so this post-hoc test separates PRAT from the four and five lowest-ranked models, and the per-dataset tests carry the comparison with the strongest baselines.
Per dataset we use Welch’s t t t where only a mean and a standard deviation are available, and an exact paired Wilcoxon signed-rank test where per-split values exist on both sides. PRAT beats GAT-sep on roman-empire at p = 3.9 × 10 − 5 p = 3.9 \times10^{-5} p = 3.9 × 1 0 − 5 and on tolokers at p = 8.2 × 10 − 6 p = 8.2 \times10^{-6} p = 8.2 × 1 0 − 6 . We re-ran GAT-sep, the strongest baseline on roman-empire, in the identical pipeline, reproducing its 88.75 there, which allows a paired test on the shared splits that PRAT wins on all ten at p = 0.002 p = 0.002 p = 0.002 .
In four comparisons PRAT has the higher mean but the difference is not significant at α = 0.05 \alpha= 0.05 α = 0.05 , and we count these as ties: amazon-ratings against SAGE at p = 0.55 p = 0.55 p = 0.55 , Citeseer against Geom-GCN at p = 0.94 p = 0.94 p = 0.94 , filtered Chameleon against FAGCN at p = 0.52 p = 0.52 p = 0.52 , and Actor against FAGCN at p = 0.20 p = 0.20 p = 0.20 . The paired tests behind the ablation are given with Table 13 and Table 14 .
Table 13. Three-way ablation on the Platonov benchmarks, grouped as in Table 4, with the graph signature index of each dataset. p p p is an exact paired Wilcoxon signed-rank test of PRAT against P R A T p o s \mathrm{PRAT}_{\mathrm{pos}} PRAT pos over the ten shared splits; bold p p p marks significance at α = 0.05 \alpha= 0.05 α = 0.05 . Among the three variants the best mean is in bold , and where means tie the smaller deviation takes it.
Table 14. Initialization controls on the two indefinite benchmarks. The signature row is the reference: Δ \Delta Δ is the loss against it and p p p an exact paired Wilcoxon over ten shared splits, with bold p p p marking significance at α = 0.05 \alpha= 0.05 α = 0.05 . abs_pos keeps the magnitudes and deletes the negative directions; sign keeps the signs at a uniform magnitude; flip keeps the magnitudes and inverts the signs; random draws an indefinite diagonal of the same inertia at the signature’s scale.
Variation across training seeds
The tables vary data splits with the training seed fixed, so that a split is reproducible. To check that fixing the seed hides no variance, we reran the ten-split evaluation on the five large Platonov datasets with three training seeds, in one matched run that reproduces Table 4 to within 0.11 points.
In Table 12 each ten-split mean moves by under one point across the three seeds. On a fixed split, the deviation across the three seeds, pooled over the ten splits, is 0.25, 0.40, 0.50, 0.37 and 0.47 points in the order of the table, below the split-to-split deviation of a single run on every dataset, so the error bars we report capture the dominant source of variability.
Table 12. Ten-split mean under three training seeds, against the split-to-split deviation of the reported run.
Graph Transformer and geometric baselines
Four rows of Table 3 answer two further questions: how the neighbor-only Graph Transformer used by Platonov et al. [28 ] behaves on these splits (GT and GT-sep), and how PRAT compares against models that already carry an indefinite or curved geometry (Q-GCN on a pseudo-hyperboloid, HAT on the Poincaré ball).
Two readings follow. First, GT is close on the two Wikipedia graphs, at 68.71 against 68.73 on Chameleon and 56.83 against 56.96 on Squirrel, and an exact paired test on the shared splits finds no significant difference (p = 0.16 p = 0.16 p = 0.16 and p = 0.70 p = 0.70 p = 0.70 ). GT differs from PRAT in its projections and layer architecture as well as in the metric, so it is not a geometry-matched control; the causal claim in this paper rests on the paired ablation of § 16 .1, not on this table.
Second, among the geometric models the pattern is cleaner. On the three homophilic graphs, where no negative direction can be exploited, everything sits within two points. On the heterophilic half Q-GCN trails by 7.61 to 26.21 points and HAT, curved but positive definite, trails on every dataset here. Q-GCN also trails PRAT by 3.87 and 4.48 points on filtered Chameleon and filtered Squirrel, at 38.82 ± 2.28 38.82 \pm2.28 38.82 ± 2.28 and 35.12 ± 1.36 35.12 \pm1.36 35.12 ± 1.36 .
The sign-conditional ablation
What happens when the metric is forbidden to be indefinite, and what that does and does not license.
Three-way ablation on the Platonov suite
Table 5 runs the three-way ablation on the standard benchmarks. Table 13 repeats it on the Platonov suite and the filtered pair, inside one matched run whose PRAT rows reproduce Table 4 to within 0.24 points. Because the three variants share every split, an exact paired Wilcoxon signed-rank test over the ten splits is available, which a comparison of means alone is not.
The gap between PRAT and PRATp o s ^{\mathrm{pos}} pos appears only where the signature has negative eigenvalues, and there it is significant: +2.60 points on roman-empire on all ten splits, and +2.06 on filtered Chameleon on eight of ten. On the four datasets with n − = 0 n_{-}=0 n − = 0 the two variants differ by at most 0.14 points at p ≥ 0.13 p \ge0.13 p ≥ 0.13 , and the single nominal win for the constraint is minesweeper by 0.03 points at p = 0.85 p = 0.85 p = 0.85 . Filtered Squirrel is the boundary case. Its training-split spectrum is nearly flat beyond λ 1 = 0.1375 \lambda_{1}=0.1375 λ 1 = 0.1375 , the next three eigenvalues carrying 3.2%, 0.2% and −0.7% of it, so what the initialization supplies there is near-zero suppression rather than sign, and the positive-definite constraint costs 0.19 points at p = 0.77 p = 0.77 p = 0.77 . A constraint that mattered for generic reasons would not localize this way.
PRATf i x e d ^{\mathrm{fixed}} fixed matches PRAT on six of the seven, the exception being minesweeper by 0.16 points at p = 0.002 p = 0.002 p = 0.002 . Freezing Λ \Lambda Λ freezes the inertia and not the metric, since D = ( W ′ ) ⊤ Λ W ′ D = (W^{\prime})^{\top}\Lambda W^{\prime} D = ( W ′ ) ⊤ Λ W ′ keeps adapting through W ′ W^{\prime} W ′ , so these rows say that on large graphs the initialization is what has to supply the spectrum while the pullback is still learned. Where the training-split signature is noisy, on the small graphs of Table 5 , learning Λ \Lambda Λ as well is what recovers 16.7 points on Cornell.
The signature as a diagnostic rather than a predictor
It is natural to ask whether n − n_{-} n − predicts how much a signed or high-pass model gains. Rank-correlating n − n_{-} n − from Table 1 against what each such baseline of Table 3 gains over GCN is positive throughout, at ρ = + 0.23 \rho= +0.23 ρ = + 0.23 for FAGCN, + 0.33 +0.33 + 0.33 for GPR-GNN, + 0.60 +0.60 + 0.60 for BernNet and + 0.33 +0.33 + 0.33 for their mean gain; none is significant at eight datasets, and Squirrel is the exception, where the three models lose 2.82 points on average despite n − = 1 n_{-}=1 n − = 1 .
We therefore present s G s_G s G as a diagnostic of the condition under which an indefinite mechanism should pay, not as a predictor of accuracy. The direct evidence for the diagnostic reading is the sign-conditional ablation of Section I.1, which manipulates the admissible sign structure with everything else held fixed and finds the effect exactly where the condition holds. Predicting the gain is hard for measures of this kind in general: Zheng et al. [48 ] report their own composite homophily score correlating with the graph-aware advantage at p ≥ 0.11 p \ge0.11 p ≥ 0.11 over thirty-one graphs.
What the initialization has to supply
Which part of the signature carries the effect, and whether ground-truth labels are needed to obtain it.
What the initialization has to supply
The ablation above shows that the freedom to be indefinite is worth something. It does not say which part of the signature carries it, the sign pattern or the magnitudes. Table 14 separates the two with four controls that keep the architecture fixed and change the initial diagonal; abs_pos also holds Λ \Lambda Λ positive definite during training, as PRATp o s ^{\mathrm{pos}} pos does.
The controls give different results on the two graphs, and the difference is informative. On roman-empire the only variant that loses decisively is abs_pos, which keeps the magnitude profile and removes the negative directions: it costs 2.26 points on all ten splits. Everything that retains negative directions, including sign-only, sign-flipped and all three random draws of matching inertia, stays within 0.7 points. The reason is visible in the spectrum: eleven of roman-empire’s eighteen training-split eigenvalues are below a sixth of λ 1 \lambda_1 λ 1 in magnitude, so the profile is close to flat and the only information the signature carries there is that negative directions exist. On filtered Chameleon the spectrum is not flat, its second eigenvalue carrying 10.8% of the first against 3.2% on filtered Squirrel, and there the specific values matter: every random draw of matching inertia loses 1.63 to 2.62 points and sign-only loses 2.55.
An uninformed initialization is the other end of the scale. An identity initialization that is free to become indefinite but carries no signature information reaches 87.61 on roman-empire, level with the positive-definite variant at 87.56. Freedom alone therefore buys nothing; what has to be supplied is the negative directions and, where the spectrum is informative, their relative sizes as well.
The initialization also survives training. Figure 3 reports the converged positive-eigenvalue ratio on synthetic graphs. On real graphs we logged Λ \Lambda Λ throughout training. Between 97.2% and 100% of its entries keep their initial sign at convergence, the cosine to the initialization stays above 0.985, and roman-empire’s negative-entry fraction holds between 0.38 and 0.42 while the magnitudes adapt. Every sign change falls on an entry initialized from a training-split eigenvalue within 10 − 4 10^{-4} 1 0 − 4 of zero, which the convention of Figure 8 rounds to zero, so every entry whose training-split eigenvalue counts as positive or negative keeps its sign. On tolokers, whose signature is strictly positive, no entry becomes negative. The model does not drift back to a Riemannian solution when it is free to, which is what the diagnose-then-learn reading predicts.
Estimating the signature without labels
The signature is computed from training-node labels, but nothing in the forward pass reads a label. To test whether the labels are the essential ingredient or merely a convenient one, we re-estimate the signature from k k k -means pseudo-labels on node features, with the number of clusters set to the number of classes and no ground-truth label used in the estimate, and train as usual.
In Table 15 recovery is complete on both indefinite benchmarks, while the uninformed initialization loses 2.55 and 2.27 points. The feature-only estimate is not a reconstruction of the label signature: its inertia is (7,4,7) against (8,4,6) on roman-empire and (1,3,1) against (3,0,2) on filtered Chameleon, and it still recovers the accuracy. Taken with Section J.1, the picture is that what has to be supplied is the presence of negative directions together with near-zero suppression, not a faithful copy of the label spectrum, and that node features alone can supply it. A complete self-supervised treatment, the training objective as well as the initialization, is outside the scope of this paper.
Behavior under sparse and noisy labels
How far the signature and the accuracy survive when training labels are few or wrong.
Stability of the signature under label sparsity and noise
Table 17 varies how many labels the model trains on. A separate question is how quickly the signature estimate itself degrades. We keep a random fraction p p p of the training nodes, or flip a fraction η \eta η of the training labels to a random other class, recompute the signature and report the mean sign agreement of its eigenvalues against the full-training-label estimate over 100 repeats.
Table 17.
Table 16 : Mean eigenvalue sign agreement of the estimated signature against the full-training-label signature, over 100 repeats.
Table 16.
Table 16 reports the agreement. Large graphs are stable at modest label fractions. Actor’s low agreement sits in near-zero eigenvalues at the rounding threshold, where the dominant directions keep their sign, and the 183-node WebKB graphs lose the signature below a quarter of an already small training set. That is exactly where Table 17 shows Cornell losing its lead, with all three models inside 0.6 points at 10%, and it is why the learnable Λ \Lambda Λ matters most on small graphs.
What matters in the end is accuracy. Training PRAT from the corrupted initialization, with training labels left clean and only the initialization degraded, costs at most 0.11 points on roman-empire (90.16 → \to → 90.05 at η = 10 % \eta=10\% η = 10% ) and 1.46 on filtered Chameleon (42.45 → \to → 40.99 at p = 25 % p=25\% p = 25% ), both inside the split deviation, and every corrupted variant stays at or above the positive-definite ablation.
Training Fraction Sensitivity
We evaluate how PRAT’s advantage depends on label availability by training on 10%, 20%, 40%, 60%, and 100% of the original training split on Cornell, Texas, Actor, and Cora, using each model’s best hyperparameters and 10 data splits.
Table 17 : Accuracy (%) at varying training fractions. Bold indicates the best model per dataset and fraction.
On heterophilic datasets, PRAT consistently outperforms GAT and GATv2, but the gap narrows with fewer labels (Texas: +1.97pp at 100% → \to → +2.7pp at 10%). This reveals the mechanism behind PRAT’s advantage: as S G S_{\mathcal{G}} S G becomes noisier with fewer labels, initialization quality degrades and performance approaches that of standard attention.
On homophilic Cora, all models perform comparably at fractions ≥ 20 % \geq20\% ≥ 20% , as expected, since the positive-definite structure of Cora’s S G S_{\mathcal{G}} S G initializes PRAT’s metric as positive semi-definite, offering no additional geometric advantage over GAT/GATv2. At 10%, PRAT shows higher variance (74.24± \pm ± 14.97%) due to one split where S G S_{\mathcal{G}} S G computed from ∼ \sim ∼ 163 training nodes across 7 classes produces a severely noisy initialization. This is consistent with our analysis: the S G S_{\mathcal{G}} S G quality degrades when training labels are extremely sparse relative to the number of classes, but performance recovers rapidly at 20% (83.09 ± 2.12 % 83.09 \pm2.12\% 83.09 ± 2.12% ).
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
Answer: [Yes]
Justification: The main claims in the abstract and introduction are supported by the theoretical analysis in Section 2, the proposed PRAT method in Section 3, and empirical results in Section 4. The scope is limited to node classification on homophilic and heterophilic graph benchmarks.
Guidelines:
The answer [N/A] means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A [No] or [N/A] answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The Limitations paragraph after the conclusion states four: the signature is initialized from training-node labels, which ties the method as presented to (semi-)supervised node classification; signature shift between training and test graphs is not studied; graph-level tasks are out of reach because SG is undefined without node labels; and rank ( D ) ≤ ∣ L ∣ \operatorname{rank}(D) \leq|L| rank ( D ) ≤ ∣ L ∣ bounds the structure the metric can carry when classes are few. Appendix J.2 reports the label-free variant that weakens the first of these.
Guidelines:
The answer [N/A] means that the paper has no limitation while the answer [No] means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate “Limitations” section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best
judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper states the assumptions and formal results in Section 2, including Theorems 2.2–2.5 , and provides detailed proofs in Appendix § 8 .
Guidelines:
The answer [N/A] means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: § 4.2 specifies the train/validation/test split, use of fixed and random splits, self-loop preprocessing, random seed control, and hyperparameter tuning protocol. Detailed configurations are provided in Appendix § 13 .1.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
If the paper includes experiments, a [No] answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general, releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example: (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide a repository at https://github.com/voltwin-dev/PRAT_NeurIPS_2026, containing the implementation of PRAT, scripts for reproducing the experiments, configuration files, license information, and instructions for the reported benchmarks. The released code is provided for research and non-commercial use only due to patent-related restrictions, while the datasets used in this work are publicly available benchmark datasets and cited in § 4.1 .
Guidelines:
The answer [N/A] means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so [No] is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies dataset splits, preprocessing, random seeds, hyperparameter tuning, and evaluation metrics in § 4.2 , with additional configuration details in Appendix § 13 .1.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All benchmark, ablation and appendix tables report the mean over the ten fixed evaluation splits with the standard deviation across those splits, so the error bars capture split variability at a fixed seed. Appendix G.1 adds a Friedman test across models on each suite and, per dataset, Welch’s t t t -test and the exact paired Wilcoxon signed-rank test over the ten splits, and reports which comparisons are ties. Appendix G.2 separates seed variability from split variability by repeating the ten-split evaluation under three training seeds.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The authors should answer [Yes] if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).
If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All experiments we conducted were run on a single NVIDIA A100 80GB GPU; the used computing resources are reported in Appendix F.2.
Guidelines:
The answer [N/A] means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?
Answer: [Yes] Justification: The research appears to conform to the NeurIPS Code of Ethics and does not involve human subjects, private data, or high-risk deployment.
Guidelines:
The answer [N/A] means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer [No], they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The paper does not include a separate discussion of societal impacts. PRAT is a foundational method for node classification on graphs and is not tied to a particular application or deployment, and we do not see a direct path from it to negative applications.
Guidelines:
The answer [N/A] means that there is no societal impact of the work performed.
If the authors answer [N/A] or [No], they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?
Answer: [N/A]
Justification: The paper does not release a high-risk pretrained model, scraped dataset, or system with a clear high-risk misuse scenario requiring special safeguards.
Guidelines:
The answer [N/A] means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The paper cites the original sources of the benchmark datasets and baseline methods used in the experiments. The repository documents the licenses and terms of use for the datasets and baseline code assets, and states that the released PRAT implementation is provided under a research-only, non-commercial license due to patent-related restrictions.
Guidelines:
The answer [N/A] means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset’s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We release an implementation of PRAT with documentation, experiment scripts, configuration files, license information, and instructions for reproducing the reported results. The released PRAT code is made available for research and non-commercial use only due to patent-related restrictions.
Guidelines:
The answer [N/A] means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing experiments or research with human subjects.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [N/A]
Justification: The paper does not involve crowdsourcing experiments or research with human subjects, so IRB approval or equivalent review is not applicable.
Guidelines:
The answer [N/A] means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.
Answer: [N/A]
Justification: LLMs are not used as an important, original, or non-standard component of the core method, experiments, or scientific contributions of this work.
Guidelines:
The answer [N/A] means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.