Contextualized Messages Boost Graph Representations

## Abstract

Abstract Graph neural networks (GNNs) have gained significant attention in recent years for their ability to process data that may be represented as graphs. This has prompted several studies to explore their representational capability based on the graph isomorphism task. These works inherently assume a countable node feature representation, potentially limiting their applicability. Interestingly, only a few study GNNs with uncountable node feature representation. In the paper, a novel perspective on the representational capability of GNNs is investigated across all levels—node-level, neighborhood-level, and graph-level—when the space of node feature representation is uncountable. More specifically, the strict injective and metric requirements are softly relaxed by employing a pseudometric distance on the space of input to create a soft-injective function such that distinct inputs may produce similar outputs if and only if the pseudometric deems the inputs to be sufficiently similar on some representation. As a consequence, a simple and computationally efficient soft-isomorphic relational graph convolution network (SIR-GCN) that emphasizes the contextualized transformation of neighborhood feature representations via anisotropic and dynamic message functions is proposed. A mathematical discussion on the relationship between SIR-GCN and widely used GNNs is then laid out to put the contribution into context, establishing SIR-GCN as a generalization of classical GNN methodologies. Experiments on synthetic and benchmark datasets then demonstrate the relative superiority of SIR-GCN, outperforming comparable models in node and graph property prediction tasks.

## 1 Introduction

Graph neural networks (GNNs) constitute a class of deep learning models designed to process data that may be represented as graphs. These models are well-suited for node, edge, and graph property prediction tasks across various domains including social networks, molecular graphs, and biological networks, among others (Dwivedi et al., ; Hu et al., ). GNNs predominantly follow the message-passing scheme wherein each node aggregates the feature representation of its neighbors and combines them to create an updated node feature representation (Gilmer et al., ; Xu et al., ; ). This allows the model to encapsulate both the network structure and the broader node contexts. Moreover, a graph readout function is employed to pool the individual node feature representation and create a representation for the entire graph (Li et al., ; Murphy et al., ; Xu et al., ; Ying et al., ).

Among the most widely used GNNs in literature include the graph convolution network (GCN) (Kipf & Welling, ), graph sample and aggregate (GraphSAGE) (Hamilton et al., ), graph attention network (GAT) (Brody et al., ; Veličković et al., ), and graph isomorphism network (GIN) (Xu et al., ) which largely fall under the message-passing neural network (MPNN) (Gilmer et al., ) framework. These models have gained popularity due to their simplicity and remarkable performance across various applications (Dwivedi et al., ; Hsu et al., ; Hu et al., ; Jiang et al., ; Kim & Ye, ; Liu et al., ). Improvements are also constantly being proposed to achieve state-of-the-art performance (Bodnar et al., ; Bouritsas et al., ; Ishiguro et al., ; Miao et al., ; Sun et al., ; Wang et al., ; Ying et al., ).

Notably, these advances are mainly driven by heuristics and empirical results. Nonetheless, several studies have also begun exploring the representational capability of GNNs (Azizian & Lelarge, ; Bodnar et al., ; Böker et al., ; Corso et al., ; Garg et al., ; Sato et al., ). Most of these works analyzed GNNs in relation to the graph isomorphism task. Xu et al. () was among the first to lay the foundations for creating a maximally expressive GNN based on the Weisfeiler-Leman (WL) graph isomorphism test (Weisfeiler & Leman, ). Subsequent works build upon their results by considering extensions to the original 1-WL test. However, these results only hold with countable node feature representation which potentially limits their applicability. Meanwhile, Corso et al. () proposed using multiple aggregators to create powerful GNNs when the space of node feature representation is uncountable. Interestingly, there has been no significant theoretical progress since this work.

This paper presents a novel perspective on the representational capability of GNNs when the space of node feature representation is uncountable. The key idea is to define a pseudometric distance on the space of input to create a soft-injective function such that distinct inputs may produce similar outputs if and only if the distance between the inputs is sufficiently small on some representation. This idea is investigated across all levels—node-level, neighborhood-level, and graph-level. From the theoretical results, a simple and computationally efficient soft-isomorphic relational graph convolution network (SIR-GCN) which emphasizes the contextualized transformation of neighborhood feature representations using anisotropic and dynamic message functions is proposed. The mathematical relationship between SIR-GCN and popular GNNs in literature is also presented to underscore the novelty and advantages of the proposed model. Experiments on synthetic and benchmark datasets in node and graph property prediction tasks then highlight the expressivity of SIR-GCN, positioning the proposed model as the best-performing MPNN instance.

## 2 Graph neural networks

Let $\mathcal{G}=\left(\mathcal{V}_{\mathcal{G}},\mathcal{E}_{\mathcal{G}}\right)$ be a graph and $\mathcal{N}_{\mathcal{G}}(u)\subseteq\mathcal{V}_{\mathcal{G}}$ the set of nodes adjacent to node $u\in\mathcal{V}_{\mathcal{G}}$. The subscript $\mathcal{G}$ will be omitted whenever the context is clear. Suppose $\mathcal{H}$ is the space of node feature representation, henceforth feature, and $\bm{h_{u}}\in\mathcal{H}$ is the feature of node $u$. A GNN following the message-passing scheme can be expressed mathematically as

$$ $\displaystyle\bm{H_{u}}$ $\displaystyle=\left\{\!\!\left\{\bm{h_{v}}:v\in\mathcal{N}_{\mathcal{G}}(u) \right\}\!\!\right\}$ $\displaystyle\bm{a_{u}}$ $\displaystyle=\textsc{AGG}\left(\bm{H_{u}}\right)$ (1) $\displaystyle\bm{h^{*}_{u}}$ $\displaystyle=\textsc{COMB}\left(\bm{h_{u}},\bm{a_{u}}\right),$ $$

where AGG and COMB are some aggregation and combination strategies, respectively, $\bm{H_{u}}$ is the multiset (Xu et al., ) of neighborhood features for node $u$, $\bm{a_{u}}$ is the aggregated neighborhood features for node $u$, and $\bm{h^{*}_{u}}$ is the updated feature for node $u$. Since AGG takes arbitrary-sized multisets of neighborhood features as input and transforms them into a single feature, it may be considered a hash function. Hence, aggregation and hash functions shall be used interchangeably throughout the paper.

##### Related works

When $\mathcal{H}$ is countable, Xu et al. () showed that there exists a function $f:\mathcal{H}\rightarrow\mathcal{S}$ such that the aggregation or hash function

$$ $F\left(\bm{H}\right)=\sum_{\bm{h}\in\bm{H}}f\left(\bm{h}\right)$ (2) $$

is injective or unique for each multiset of neighborhood features $\bm{H}$ of bounded size in the embedded feature space $\mathcal{S}$. This result forms the theoretical basis of GIN.

Meanwhile, the result above no longer holds when $\mathcal{H}$ is uncountable. In this setting, Corso et al. () proved that if $\bigoplus$ comprises multiple aggregators (e.g., mean, standard deviation, max, and min), the hash function

$$ $M\left(\bm{H}\right)=\bigoplus_{\bm{h}\in\bm{H}}m\left(\bm{h}\right)$ (3) $$

produces a unique output for every $\bm{H}$ of bounded size. This finding provides the foundation for the principal neighborhood aggregation (PNA) (Corso et al., ). Notably, for this result to hold, the number of aggregators in $\bigoplus$ must also scale with the size of the multiset of neighborhood features $\bm{H}$, which may be infeasible for large and dense graphs.

## 3 Soft-injective functions

While injective functions and metrics are necessary for tasks requiring strict isomorphism, many practical applications of GNNs often do not require such strict constraints. For instance, in node classification tasks, the model must produce identical outputs for some distinct nodes. Thus, this paper softly relaxes these constraints by employing pseudometrics and soft-injective functions.

###### Definition 1 (Pseudometric) .

Let $\mathcal{H}$ be a non-empty set. A function $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ is a pseudometric on $\mathcal{H}$ if the following holds for all $\bm{h}^{(1)},\bm{h}^{(2)},\bm{h}^{(3)}\in\mathcal{H}$:

- •
$d\left(\bm{h}^{(1)},\bm{h}^{(1)}\right)=0$;
- •
$d\left(\bm{h}^{(1)},\bm{h}^{(2)}\right)=d\left(\bm{h}^{(2)},\bm{h}^{(1)}\right)$; and
- •
$d\left(\bm{h}^{(1)},\bm{h}^{(3)}\right)\leq d\left(\bm{h}^{(1)},\bm{h}^{(2)}
\right)+d\left(\bm{h}^{(2)},\bm{h}^{(3)}\right)$.

Note that unlike a metric, $d\left(\bm{h}^{(1)},\bm{h}^{(2)}\right)=0\centernot\implies\bm{h}^{(1)}=\bm{h}
^{(2)}$ for a pseudometric $d$. The following assumption is then imposed on the psuedometric $d$, leveraging results from kernel theory.

###### Assumption 1 .

Let $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ be a pseudometric on $\mathcal{H}$ such that $-d^{2}$ is a conditionally positive definite kernel on $\mathcal{H}$.

The Euclidean distance is an example of a pseudometric satisfying Assumption 1. A class of pseudometrics satisfying this assumption is provided below, see Berg et al. () and Schölkopf () for more.

###### Remark 1 .

Consider the pseudometrics $d_{1}$ and $d_{2}$ on $\mathcal{H}$ satisfying Assumption 1. For $a>0$ and $0<p<1$, the pseudometrics $a\cdot d_{1}$, $\sqrt{d_{1}^{2}+d_{2}^{2}}$, and $d_{1}^{p}$ also satisfy Assumption 1.

Assumption 1 thus offers considerable flexibility in the choice of pseudometric $d$. The following theorem then softly relaxes the injective and metric requirements in previous works.

###### Theorem 1 .

Let $\mathcal{H}$ be a non-empty set with a pseudometric $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ satisfying Assumption 1. There exists a feature map $g:\mathcal{H}\rightarrow\mathcal{S}$ such that for every $\bm{h}^{(1)},\bm{h}^{(2)}\in\mathcal{H}$ and $\varepsilon_{1}>\varepsilon_{2}>0$,

$$ $\varepsilon_{2}<\left\lVert g\left(\bm{h}^{(1)}\right)-g\left(\bm{h}^{(2)} \right)\right\rVert<\varepsilon_{1}\iff\varepsilon_{2}<d\left(\bm{h}^{(1)},\bm {h}^{(2)}\right)<\varepsilon_{1}.$ (4) $$

Figure: (a) Input feature space $\mathcal{H}$.

Theorem 1 shows that, for each node $u\in\mathcal{V}$, given a pseudometric distance $d_{u}$ that represents a dissimilarity function on $\mathcal{H}$, possibly encoded with prior knowledge, there exists a corresponding feature map $g_{u}$ that maps distinct inputs $\bm{h_{u}}^{(1)},\bm{h_{u}}^{(2)}\in\mathcal{H}$ close in the embedded feature space $\mathcal{S}$ if and only if $d_{u}$ determines $\bm{h_{u}}^{(1)},\bm{h_{u}}^{(2)}$ to be sufficiently similar on some representation. The lower bound $\varepsilon_{2}$ asserts the ability of $g_{u}$ to separate elements of $\mathcal{H}$ in the embedded feature space $\mathcal{S}$ while the upper bound $\varepsilon_{1}$ ensures $g_{u}$ maintains the relationship between elements of $\mathcal{H}$ with respect to $d_{u}$. The feature map $g_{u}$ may then be described as soft-injective.(^1^11The pseudometric $d$ induces the equivalence class $\left[\bm{h}\right]_{d}\coloneqq\left\{\bm{h^{\prime}}\in\mathcal{H}:d\left( \bm{h},\bm{h^{\prime}}\right)=0\right\}$ with the quotient space $\mathcal{H}_{d}\coloneqq\mathcal{H}\setminus d=\left\{\left[\bm{h}\right]_{d}: \bm{h}\in\mathcal{H}\right\}$ such that $d$ becomes metric and the corresponding feature map $g$ becomes injective on $\mathcal{H}_{d}$ (Schoenberg, ). Hence, $g$ may be described as soft-injective.) Corollary 1 extends this result for multisets.

###### Definition 1 (Pseudometric) .

###### Assumption 1 .

###### Remark 1 .

###### Theorem 1 .

### 3.1 Soft-isomorphic relational graph convolution network

###### Corollary 1 .

Let $\mathcal{H}$ be a non-empty set with a pseudometric $D$ on bounded, equinumerous multisets of $\mathcal{H}$ defined as

$$ $D^{2}\left(\bm{H}^{(1)},\bm{H}^{(2)}\right)=\sum_{\begin{subarray}{c}\bm{h}\in \bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})- \dfrac{1}{2}\sum_{\begin{subarray}{c}\bm{h}\in\bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(1)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})- \dfrac{1}{2}\sum_{\begin{subarray}{c}\bm{h}\in\bm{H}^{(2)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})$ (5) $$

for some pseudometric $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ satisfying Assumption 1 and bounded, equinumerous multisets $\bm{H}^{(1)},\bm{H}^{(2)}$. There exists a feature map $g:\mathcal{H}\rightarrow\mathcal{S}$ such that for every $\bm{H}^{(1)},\bm{H}^{(2)}$ and $\varepsilon_{1}>\varepsilon_{2}>0$,

$$ $\varepsilon_{2}<\left\lVert G\left(\bm{H}^{(1)}\right)-G\left(\bm{H}^{(2)} \right)\right\rVert<\varepsilon_{1}\iff\varepsilon_{2}<D\left(\bm{H}^{(1)},\bm {H}^{(2)}\right)<\varepsilon_{1},$ (6) $$

where

$$ $G(\bm{H})=\sum_{\bm{h}\in\bm{H}}g(\bm{h}).$ (7) $$

Similarly, Corollary 1 shows that, for each node $u\in\mathcal{V}$, given a pseudometric distance $D_{u}$ on multisets of $\mathcal{H}$ defined in Eqn. 5 with a corresponding pseudometric distance $d_{u}$ on $\mathcal{H}$, there exists a corresponding feature map $g_{u}$ and soft-injective hash function $G_{u}$ defined in Eqn. 7 that produces similar outputs for distinct multisets of neighborhood features $\bm{H_{u}}^{(1)},\bm{H_{u}}^{(2)}$ if and only if $D_{u}$ deems $\bm{H_{u}}^{(1)},\bm{H_{u}}^{(2)}$ to be sufficiently similar on some representation. Likewise, the lower and upper bounds guarantee the ability of $G_{u}$ to separate equinumerous multisets of $\mathcal{H}$ in the embedded feature space $\mathcal{S}$ while maintaining the relationship with respect to $D_{u}$. In this setting, the feature map $g_{u}$ may be interpreted as the message function (Gilmer et al., ) of the aggregation strategy that transforms the individual neighborhood features. Meanwhile, the psuedometric $D_{u}$ corresponds to the kernel distance (Joshi et al., ) which intuitively represents the difference between the cross-distance and self-distance between two multisets.

###### Corollary 1 .

##### Dynamic transformation

To illustrate the role of pseudometrics, consider anomaly detection on node features representing zero-mean scores, with node $u$ having two neighbors $v_{1}$ and $v_{2}$. If $d_{u}$ simply corresponds to the Euclidean distance, then the corresponding hash function $G_{u}$ becomes linear as presented in Fig. 2(a). The contour plot highlights collisions—instances where distinct inputs produce identical outputs (i.e., the equivalence class $\left[\bm{H}\right]_{D}$)—between dissimilar multisets of neighborhood features, resulting in aggregated neighborhood features that are less useful for the task.

Figure: (a) $g_{u}(\bm{h})=\bm{h}$.
Refer to caption: extracted/5889568/images/contour_linear.png

Nevertheless, other choices of pseudometrics, possibly incorporating prior knowledge, would correspond to more complex message functions $g_{u}$. This leads to non-trivial hash functions $G_{u}$ and contour plots where only the regions determined by $D_{u}$ to be similar may produce similar aggregated neighborhood features, making collisions more informative and controlled. This also highlights the significance of dynamic (Brody et al., ) or non-linear message functions $g_{u}$ in MPNNs.

As further illustration, if $d_{u}$ instead corresponds to the Euclidean distance of the squared score, then the corresponding hash function $G_{u}$ has the contour plot in Fig. 2(b). The resulting hash collisions and equivalence classes then become more useful and meaningful for detecting anomalous scores.

##### Anisotropic messages

It is also worth noting that Corollary 1 holds for each node $u\in\mathcal{V}$ independently. Hence, different nodes may correspond to different $D_{u}$, $d_{u}$, $g_{u}$, and $G_{u}$. For simplicity, especially in inductive learning contexts, consider a single pseudometric instead, defined as

$$ $D^{2}\left(\bm{H_{u}}^{(1)},\bm{H_{u}}^{(2)};\bm{h_{u}}\right)=\sum_{\begin{ subarray}{c}\bm{h}\in\bm{H_{u}}^{(1)}\\ \bm{h^{\prime}}\in\bm{H_{u}}^{(2)}\end{subarray}}\!\!d^{2}(\bm{h},\bm{h^{ \prime}};\bm{h_{u}})-\dfrac{1}{2}\!\!\sum_{\begin{subarray}{c}\bm{h}\in\bm{H_{ u}}^{(1)}\\ \bm{h^{\prime}}\in\bm{H_{u}}^{(1)}\end{subarray}}\!\!d^{2}(\bm{h},\bm{h^{ \prime}};\bm{h_{u}})-\dfrac{1}{2}\!\!\sum_{\begin{subarray}{c}\bm{h}\in\bm{H_{ u}}^{(2)}\\ \bm{h^{\prime}}\in\bm{H_{u}}^{(2)}\end{subarray}}\!\!d^{2}(\bm{h},\bm{h^{ \prime}};\bm{h_{u}}),$ (8) $$

with a single hash function, defined as

$$ $G\left(\bm{H_{u}};\bm{h_{u}}\right)=\sum_{\bm{h}\in\bm{H_{u}}}g\left(\bm{h}; \bm{h_{u}}\right),$ (9) $$

for every node $u\in\mathcal{V}$. This approach makes $D$, $d$, $g$, and $G$ anisotropic (Dwivedi et al., ) (i.e., a function of both the features of the query (center) node $\bm{h_{u}}$ and key (neighboring) nodes $\bm{h}\in\bm{H_{u}}$). Moreover, contextualized on the features of the query node, $D$ may still be interpreted as a pseudometric controlling hash collisions with a corresponding soft-injective hash function $G$.

Furthermore, the integration of $\bm{h_{u}}$ also allows for the interpretation of $g$ as a relational message function, guiding how features of the key nodes are to be embedded and transformed based on the features of the query node. Figs. 2(c) and 2(d) provide intuition for this idea where the introduction of a bias term, assuming a function of the features of the query node, shifts the contour plot to produce distinct aggregated neighborhood features $\bm{a_{u}}\neq\bm{a_{u^{\prime}}}$ for nodes $u$ and $u^{\prime}$ with identical neighborhood features $\bm{H_{u}}=\bm{H_{u^{\prime}}}$ but distinct features $\bm{h_{u}}\neq\bm{h_{u^{\prime}}}$. Nevertheless, one may also inject stochasticity into the node features to distinguish between nodes $u$ and $u^{\prime}$ with identical features $\bm{h_{u}}=\bm{h_{u^{\prime}}}$ and neighborhood features $\bm{H_{u}}=\bm{H_{u^{\prime}}}$ with high probability (Sato et al., ) and to imitate having distinct $D_{u}$, $d_{u}$, $g_{u}$, and $G_{u}$ for each node $u\in\mathcal{V}$.

##### Proposed model

For a graph representation learning problem, one may directly model the anisotropic and dynamic relational message function $g$ as a two-layer multi-layer perceptron (MLP), with implicitly learned pseudometrics, following the universal approximation theorem (Hornik et al., ) to obtain the soft-isomorphic relational graph convolution network (SIR-GCN)

$$ $\bm{h_{u}^{*}}=\sum_{v\in\mathcal{N}(u)}\bm{W_{R}}~{}\sigma\left(\bm{W_{Q}}\bm {h_{u}}+\bm{W_{K}}\bm{h_{v}}\right),$ (10) $$

where $\sigma$ is a non-linear activation function, $\bm{W_{Q}},\bm{W_{K}}\in\mathbb{R}^{d_{\text{hidden}}\times d_{\text{in}}}$, and $\bm{W_{R}}\in\mathbb{R}^{d_{\text{out}}\times d_{\text{hidden}}}$. Leveraging linearity, the model has a computational complexity of

$$ $\mathcal{O}\left(\left|\mathcal{V}\right|\times d_{\text{hidden}}\times d_{ \text{in}}+\left|\mathcal{E}\right|\times d_{\text{hidden}}+\left|\mathcal{V} \right|\times d_{\text{out}}\times d_{\text{hidden}}\right)$ (11) $$

with computational efficiency achieved by the application of only an activation function along edges, making it comparable to GAT. Nevertheless, $\sigma$ may also be replaced with a deep MLP in practice if modeling $g$ as a shallow two-layer MLP becomes infeasible.

In essence, the proposed SIR-GCN is a simple, interpretable, and computationally efficient instance of the MPNN framework. Moreover, in contrast to other MPNN instances in literature, the proposed model emphasizes the anisotropic and dynamic transformation of neighborhood features to obtain contextualized messages.

### 3.2 Soft-isomorphic graph readout function

Corollary 1 also shows that, for each graph $\mathcal{G}$, given a pseudometric distance $d_{\mathcal{G}}$ on $\mathcal{H}$ with a corresponding pseudometric distance $D_{\mathcal{G}}$ on multisets of $\mathcal{H}$ defined in Eqn. 5, there exists a corresponding feature map $r_{\mathcal{G}}$ and soft-injective graph readout function $R_{\mathcal{G}}$ defined in Eqn. 7. While this result holds for each graph $\mathcal{G}$ independently, one may simply consider a single $D$, $d$, $r$, and $R$ for every graph $\left\{\mathcal{G}_{d}\right\}_{d\in\mathcal{D}}$ under task $\mathcal{D}$. Nevertheless, the graph context and structure may also be integrated into $D$, $d$, $r$, and $R$, through a virtual super node (Gilmer et al., ) for instance, to imitate having distinct $D_{\mathcal{G}}$, $d_{\mathcal{G}}$, $r_{\mathcal{G}}$, and $R_{\mathcal{G}}$ for each graph $\mathcal{G}$ and to further enhance its representational capability.

Similarly, for a graph representation learning problem, $r$ may also be directly modeled as an MLP, with implicitly learned pseudometrics, to obtain the soft-isomorphic graph readout function

$$ $\bm{h_{\mathcal{G}}}=\sum_{v\in\mathcal{V}_{\mathcal{G}}}\textsc{MLP}_{R}\left (\bm{h_{v}}\right),$ (12) $$

where $\textsc{MLP}_{R}$ corresponds to $r$ and $\bm{h_{\mathcal{G}}}$ is the graph-level feature of graph $\mathcal{G}$.

## 4 Mathematical discussion

The mathematical relationship of SIR-GCN with GCN, GraphSAGE, GAT, GIN, and PNA are presented in this section to highlight the novelty and contribution. While activation functions and MLPs applied after each GNN layer play a significant role in the overall performance, the discussions only focus on the message-passing operation that defines GNNs. The relationship between SIR-GCN and the 1-WL test is also presented to contextualize the representational capability of the former.

### 4.1 GCN and GraphSAGE

It may be shown that Corollary 1 holds up to a constant scale. Hence, the mean aggregation and symmetric mean aggregation, by extension, may be used in place of the sum aggregation. If one sets $\sigma$ as identity or $\textsc{PReLU}(\alpha=1)$, $\bm{W_{Q}}=\bm{0}$, $\bm{W_{R}}\bm{W_{K}}=\bm{W}$, and $\tilde{\mathcal{N}}(u)=\mathcal{N}(u)\cup\{u\}$, one obtains

$$ $\bm{h^{*}_{u}}=\sum_{v\in\mathcal{N}(u)}\dfrac{1}{\sqrt{\left|\mathcal{N}(u) \right|}\sqrt{\left|\mathcal{N}(v)\right|}}\bm{W}\bm{h_{v}}$ (13) $$

and

$$ $\bm{h^{*}_{u}}=\dfrac{1}{\left|\tilde{\mathcal{N}}(u)\right|}\sum_{v\in\tilde{ \mathcal{N}}(u)}\bm{W}\bm{h_{v}}$ (14) $$

which recovers GCN and GraphSAGE with mean aggregation, respectively. Moreover, the sum aggregation may also be replaced with the max aggregation, albeit without theoretical justification, to recover GraphSAGE with max pooling. Thus, GCN and GraphSAGE may be viewed as instances of SIR-GCN.(^2^22GraphSAGE with LSTM aggregation is not included in this discussion.) The difference lies in the isotropic (Dwivedi et al., ) nature (i.e., a function of only the features of the key nodes) of GCN and GraphSAGE and the use of non-linearities only in the combination strategy.

### 4.2 GAT

Moreover, in Brody et al. (), the attention mechanism of GATv2 is modeled as an MLP given by

$$ $e_{u,v}=\bm{a}^{\top}~{}\textsc{LeakyReLU}\left(\bm{W_{Q}}\bm{h_{u}}+\bm{W_{K} }\bm{h_{v}}\right),$ (15) $$

with the message from node $v$ to node $u$ proportional to $\exp\left(e_{u,v}\right)\cdot\bm{W}\bm{h_{v}}$. While the model is anisotropic in nature, messages are nevertheless only linearly transformed with node $u$ only determining the degree of contribution through the scalar $e_{u,v}$. Meanwhile, SIR-GCN directly works with the unnormalized attention mechanism in Eqn. 15 and allows the features of the query node to dynamically transform messages. Specifically, if $\sigma=\textsc{LeakyReLU}$ and $\bm{W_{R}}=\bm{A}$, one obtains

$$ $\bm{h_{u}^{*}}=\sum_{v\in\mathcal{N}(u)}\bm{A}~{}\textsc{LeakyReLU}\left(\bm{W _{Q}}\bm{h_{u}}+\bm{W_{K}}\bm{h_{v}}\right)$ (16) $$

which shows Eqn. 15 becoming a contextualized message in the SIR-GCN model. Nevertheless, GAT and GATv2 may be recovered, up to a normalizing constant, with an appropriate choice of $\sigma$.

### 4.3 GIN

Likewise, within the proposed SIR-GCN model, one may explicitly add a residual connection in the combination strategy to obtain

$$ $\bm{h_{u}^{*}}=\textsc{MLP}_{\text{Res}}(\bm{h_{u}})+\sum_{v\in\mathcal{N}(u)} \bm{W_{R}}~{}\sigma\left(\bm{W_{Q}}\bm{h_{u}}+\bm{W_{K}}\bm{h_{v}}\right),$ (17) $$

where $\textsc{MLP}_{\text{Res}}$ is a learnable residual network. If $\textsc{MLP}_{\text{Res}}(\bm{h})=(1+\epsilon)\cdot\bm{h}$, $\sigma=\textsc{PReLU}(\alpha=1)$, $\bm{W_{Q}}=\bm{0}$, and $\bm{W_{R}W_{K}}=\bm{I}$, then

$$ $\bm{h^{*}_{u}}=\left(1+\epsilon\right)\cdot\bm{h_{u}}+\sum_{v\in\mathcal{N}(u) }\bm{h_{v}}$ (18) $$

is equivalent to GIN. Hence, SIR-GCN with residual connection encompasses GIN.

### 4.4 PNA

Furthermore, while SIR-GCN and PNA approach the problem of uncountable node features differently, both models highlight the significance of anisotropic message functions considering both the features of the query and key nodes. The key difference lies with PNA using a static (Brody et al., ) or linear message function $m$ which translates to

$$ $m\left(\bm{h_{v}},\bm{h_{u}}\right)=\bm{W_{K}}\bm{h_{v}}+\bm{W_{Q}}\bm{h_{u}}= \bm{W_{K}}\bm{h_{v}}+\bm{b_{u}}.$ (19) $$

As a result, the influence of the query node on the aggregated neighborhood features is limited. For instance, when using mean, max, or min aggregators, the influence of the query node $u$ is restricted to the bias term $\bm{b_{u}}$. Moreover, with normalized moment aggregators, the bias term is effectively canceled out during the normalization process, further reducing the influence of the query node. Hence, PNA does not fully leverage its anisotropic nature, limiting its expressivity. In contrast, the dynamic nature of SIR-GCN allows for the non-linear embedding of the features of the query node $\bm{h_{u}}$ within the aggregated neighborhood features, thereby fully leveraging its anisotropic nature.

### 4.5 1-WL test

Additionally, in terms of graph isomorphism representational capability, SIR-GCN is comparable to a modified 1-WL test. Suppose $w^{(l)}_{u}$ is the WL node label of node $u$ at the $l$th WL-test iteration. The modified update equation is given by

$$ $w^{(l)}_{u}\leftarrow\text{hash}\left(\left\{\!\!\!\left\{\left[w^{(l-1)}_{v}, w^{(l-1)}_{u}\right]:v\in\mathcal{N}(u)\right\}\!\!\!\right\}\right),$ (20) $$

where the modification lies in concatenating the label of the center node with every element of the multiset before hashing. This modification, while negligible when $\mathcal{H}$ is countable, becomes significant when $\mathcal{H}$ is uncountable as noted in the previous section. Thus, SIR-GCN inherits the theoretical capabilities (and limitations) of the 1-WL test.

### 4.6 SIR-GCN

Overall, SIR-GCN offers flexibility in two key dimensions of GNNs: aggregation strategy and message transformation. Consequently, it generalizes four prominent GNNs in literature—GCN, GraphSAGE, GAT, and GIN—ensuring that it is at least as expressive as these models. Notably, SIR-GCN sets itself apart from other GNNs as the first MPNN instance to incorporate both anisotropic and dynamic (i.e., contextualized) messages within the MPNN framework, making it well-suited for heterophilous tasks (Bronstein et al., ) while remaining adaptable to homophilous tasks.

Figure: Figure 3: SIR-GCN encompasses GCN, GraphSAGE, GAT, and GIN.

In addition, SIR-GCN distinguishes itself from PNA by employing only a single aggregator that theoretically holds for graphs of arbitrary sizes, thus reducing computational complexity. Nevertheless, its expressivity is maintained through contextualized messages, allowing it to inherit the representational capability of the 1-WL test.

## 5 Experiments

Experiments on synthetic and benchmark datasets in node and graph property prediction tasks are conducted to highlight the expressivity of SIR-GCN. To ensure fair evaluation, models not employing complex architectural design or manually crafted features using domain knowledge are used as primary comparisons.

### 5.1 Synthetic datasets

##### DictionaryLookup

DictionaryLookup (Brody et al., ) consists of bipartite graphs with $2n$ nodes—$n$ key nodes each with an attribute and value and $n$ query nodes each with an attribute. The task is to predict the value of query nodes by matching their attribute with the key nodes.

Figure: Figure 4: DictionaryLookup.

Figure: Figure 5: GraphHeterophily.

**Table 1: Test accuracy on DictionaryLookup.**
| Model | $n=10$ | $n=20$ | $n=30$ | $n=40$ | $n=50$ |
| --- | --- | --- | --- | --- | --- |
| GCN | 0.10 $\pm$ 0.00 | 0.05 $\pm$ 0.00 | 0.03 $\pm$ 0.00 | 0.03 $\pm$ 0.00 | 0.02 $\pm$ 0.00 |
| GraphSAGE | 0.10 $\pm$ 0.00 | 0.05 $\pm$ 0.00 | 0.03 $\pm$ 0.00 | 0.02 $\pm$ 0.00 | 0.02 $\pm$ 0.00 |
| GATv2 | 0.99 $\pm$ 0.03 | 0.88 $\pm$ 0.18 | 0.74 $\pm$ 0.28 | 0.56 $\pm$ 0.37 | 0.60 $\pm$ 0.40 |
| GIN | 0.78 $\pm$ 0.07 | 0.29 $\pm$ 0.03 | 0.12 $\pm$ 0.03 | 0.03 $\pm$ 0.00 | 0.02 $\pm$ 0.01 |
| PNA | 1.00 $\pm$ 0.00 | 0.97 $\pm$ 0.02 | 0.86 $\pm$ 0.09 | 0.66 $\pm$ 0.09 | 0.50 $\pm$ 0.05 |
| SIR-GCN | 1.00 $\pm$ 0.00 | 1.00 $\pm$ 0.00 | 1.00 $\pm$ 0.00 | 1.00 $\pm$ 0.00 | 1.00 $\pm$ 0.00 |

Table 1 presents the mean and standard deviation of the test accuracy for SIR-GCN, GCN, GraphSAGE, GATv2, GIN, and PNA across different values of $n$. SIR-GCN and GATv2 achieve perfect accuracy attributed to their anisotropic and dynamic nature. However, it is observed that GATv2 suffers from performance degradation in some trials. Meanwhile, the other models fail to predict the value of query nodes even for the training graphs due to their isotropic and/or static nature. The results underscore the utility of a dynamic attentional or relational mechanism in capturing the relationship between the query and key nodes.

##### GraphHeterophily

GraphHeterophily is an original synthetic dataset. It consists of random directed graphs with each node assigned one of $c$ classes. The task is to count the number of directed edges connecting two nodes with distinct class labels within each graph.

**Table 2: Test mean squared error on GraphHeterophily.**
| Model | $c=2$ | $c=4$ | $c=6$ | $c=8$ | $c=10$ |
| --- | --- | --- | --- | --- | --- |
| GCN | 22749 $\pm$ 1242 | 50807 $\pm$ 2828 | 62633 $\pm$ 3491 | 68965 $\pm$ 3784 | 72986 $\pm$ 4025 |
| GraphSAGE | 22962 $\pm$ 1215 | 36854 $\pm$ 2330 | 30552 $\pm$ 1574 | 21886 $\pm$ 1896 | 16529 $\pm$ 1589 |
| GATv2 | 22329 $\pm$ 1307 | 44972 $\pm$ 2834 | 49940 $\pm$ 2942 | 50063 $\pm$ 3407 | 49661 $\pm$ 3488 |
| GIN | 39.620 $\pm$ 2.060 | 37.193 $\pm$ 1.382 | 34.649 $\pm$ 1.502 | 32.424 $\pm$ 1.841 | 30.091 $\pm$ 1.429 |
| PNA | 172.15 $\pm$ 97.82 | 224.83 $\pm$ 85.80 | 249.99 $\pm$ 108.56 | 251.49 $\pm$ 98.84 | 195.72 $\pm$ 36.65 |
| SIR-GCN | 0.001 $\pm$ 0.000 | 0.004 $\pm$ 0.005 | 1.495 $\pm$ 4.428 | 0.038 $\pm$ 0.068 | 0.089 $\pm$ 0.134 |

Table 2 presents the mean and standard deviation of the test mean squared error (MSE) for SIR-GCN, GCN, GraphSAGE, GATv2, GIN, and PNA across different values of $c$. SIR-GCN achieves an MSE loss of nearly zero attributed to its anisotropic and dynamic nature and sum aggregation. In contrast, GCN, GraphSAGE, and GATv2 obtained large MSE losses due to their mean or max aggregation which fails to preserve the graph structure as noted by Xu et al. (). Meanwhile, GIN and PNA successfully retain the graph structure but fail to learn the relationship between the labels of the query node and key nodes due to their static nature. The results illustrate the utility of anisotropic and dynamic models using sum aggregation even with countable node features.

### 5.2 Benchmark datasets

##### Benchmarking GNNs

Benchmarking GNNs (Dwivedi et al., ) is a collection of benchmark datasets consisting of diverse mathematical and real-world graphs across various GNN tasks. In particular, the WikiCS, PATTERN, and CLUSTER datasets fall under node property prediction tasks while the MNIST, CIFAR10, and ZINC datasets fall under graph property prediction tasks. Furthermore, the WikiCS, MNIST, and CIFAR10 datasets have uncountable node features while the remaining datasets have countable node features. The performance metric for ZINC is the mean absolute error (MAE) while the performance metric of the remaining datasets is accuracy. Dwivedi et al. () provides more information regarding the individual datasets.

**Table 3: Test performance on Benchmarking GNNs.**
| Model | WikiCS ($\uparrow$) | PATTERN ($\uparrow$) | CLUSTER ($\uparrow$) | MNIST ($\uparrow$) | CIFAR10 ($\uparrow$) | ZINC ($\downarrow$) |
| --- | --- | --- | --- | --- | --- | --- |
| MLP | 59.45 $\pm$ 2.33 | 50.52 $\pm$ 0.00 | 20.97 $\pm$ 0.00 | 95.34 $\pm$ 0.14 | 56.34 $\pm$ 0.18 | 0.706 $\pm$ 0.006 |
| GCN | 77.47 $\pm$ 0.85 | 85.50 $\pm$ 0.05 | 47.83 $\pm$ 1.51 | 90.12 $\pm$ 0.15 | 54.14 $\pm$ 0.39 | 0.416 $\pm$ 0.006 |
| GraphSAGE | 74.77 $\pm$ 0.95 | 50.52 $\pm$ 0.00 | 50.45 $\pm$ 0.15 | 97.31 $\pm$ 0.10 | 65.77 $\pm$ 0.31 | 0.468 $\pm$ 0.003 |
| GAT | 76.91 $\pm$ 0.82 | 75.82 $\pm$ 1.82 | 57.73 $\pm$ 0.32 | 95.54 $\pm$ 0.21 | 64.22 $\pm$ 0.46 | 0.475 $\pm$ 0.007 |
| GIN | 75.86 $\pm$ 0.58 | 85.59 $\pm$ 0.01 | 58.38 $\pm$ 0.24 | 96.49 $\pm$ 0.25 | 55.26 $\pm$ 1.53 | 0.387 $\pm$ 0.015 |
| GatedGCN | - | 84.48 $\pm$ 0.12 | 60.40 $\pm$ 0.42 | 97.34 $\pm$ 0.14 | 67.31 $\pm$ 0.31 | 0.435 $\pm$ 0.011 |
| PNA | - | - | - | 97.19 $\pm$ 0.08 | 70.21 $\pm$ 0.15 | 0.320 $\pm$ 0.032 |
| EGC-M | - | - | - | - | 71.03 $\pm$ 0.42 | 0.281 $\pm$ 0.007 |
| SIR-GCN | 78.06 $\pm$ 0.66 | 85.75 $\pm$ 0.03 | 63.35 $\pm$ 0.19 | 97.90 $\pm$ 0.08 | 71.98 $\pm$ 0.40 | 0.278 $\pm$ 0.024 |

Table 3 presents the mean and standard deviation of the test performance for SIR-GCN and comparable GNN models across the six benchmarks where the experimental set-up follows that of Dwivedi et al. () to ensure fair evaluation. The results show that SIR-GCN consistently outperforms popular GNNs in literature. Notably, SIR-GCN also outperforms both PNA (Corso et al., ) and efficient graph convolution (EGC-M) (Tailor et al., ) which use multiple aggregators. This highlights the significance of contextualized messages in enhancing the expressivity of GNNs, complementing the discussion in the previous section.

##### ogbn-arxiv

ogbn-arxiv (Hu et al., ) is a benchmark dataset representing the citation network between all Computer Science (CS) arXiv papers indexed by Microsoft academic graph (Wang et al., ). Each node represents an arXiv paper and a directed edge represents a citation. The task is to classify each paper, based on its title and abstract, into the 40 subject areas of arXiv CS papers.

**Table 4: Test accuracy on ogbn-arxiv.**
| Model | GIANT-XRT<br>(Chien et al., ) | BoT<br>(Wang et al., ) | C&S<br>(Huang et al., ) | Others | Accuracy | Parameters |
| --- | --- | --- | --- | --- | --- | --- |
| GATv2 | ✓ |  |  |  | 0.7415 $\pm$ 0.0005 | 207,520 |
| GraphSAGE | ✓ |  |  |  | 0.7435 $\pm$ 0.0014 | 546,344 |
| SIR-GCN | ✓ |  |  |  | 0.7525 $\pm$ 0.0009 | 667,176 |
| ✓ | ✓ | ✓ |  | 0.7574 $\pm$ 0.0020 | 697,896 |  |
| LGGNN | ✓ | ✓ | ✓ |  | 0.7570 $\pm$ 0.0018 | 1,161,640 |
| RevGAT | ✓ |  |  | KD, DCN | 0.7636 $\pm$ 0.0013 | 1,304,912 |
| AGDN | ✓ | ✓ |  | self-KD | 0.7637 $\pm$ 0.0011 | 1,309,760 |

Table 4 presents the mean and standard deviation of the test accuracy for SIR-GCN and other models in literature. The tricks used and the number of parameters are also presented for completeness. The results show that SIR-GCN, utilizing only a single GNN layer, outperforms comparable models in predicting the subject area of the papers. As expected, however, SIR-GCN fails to compete with complex frameworks utilizing more tricks such as the reversible GAT (RevGAT) (Li et al., ) and the adaptive graph diffusion network (AGDN) (Sun et al., ), both of which build upon GAT by employing grouped reversible residual connections and adaptive graph diffusion, respectively. Nevertheless, SIR-GCN achieves performance close to that of the complex GNN frameworks mentioned, showcasing an effective balance between complexity and expressivity.

##### ogbg-molhiv

ogbg-molhiv (Hu et al., ) is another benchmark dataset where each graph represents a molecule with nodes representing atoms and edges representing chemical bonds. Node features contain information regarding the atom while edge features contain information regarding the chemical bond. The task is to predict whether or not the molecules inhibit HIV replication.

**Table 5: Test ROC-AUC on ogbg-molhiv.**
| Model | GraphNorm<br>(Cai et al., ) | VirtualNode<br>(Gilmer et al., ) | Others | ROC-AUC | Parameters |
| --- | --- | --- | --- | --- | --- |
| GIN |  | ✓ | FLAG | 0.7748 $\pm$ 0.0096 | 3,336,306 |
| GIN | ✓ |  |  | 0.7773 $\pm$ 0.0129 | 1,518,901 |
| EGC-M |  |  |  | 0.7818 $\pm$ 0.0153 | 317,265 |
| GCN | ✓ |  |  | 0.7883 $\pm$ 0.0100 | 526,201 |
| PNA |  |  |  | 0.7905 $\pm$ 0.0132 | 326,081 |
| SIR-GCN |  |  |  | 0.7721 $\pm$ 0.0110 | 327,901 |
| ✓ |  |  | 0.7981 $\pm$ 0.0062 | 328,201 |  |
| GSN |  |  |  | 0.7799 $\pm$ 0.0100 | 3,338,701 |
| GSAT |  |  |  | 0.8067 $\pm$ 0.0950 | 249,602 |
| CIN |  |  |  | 0.8094 $\pm$ 0.0057 | 239,745 |

Table 5 presents the mean and standard deviation of the test area under the receiver operating characteristic curve (ROC-AUC) for SIR-GCN and other models in literature. The tricks used and the number of parameters are also presented for completeness. The results show that with only a single GNN layer, SIR-GCN outperforms comparable models in predicting molecules inhibiting HIV replication, highlighting its expressivity. Given the simplicity of SIR-GCN, it is expected to exhibit lower performance compared to complex models such as the graph stochastic attention (GSAT) (Miao et al., ), which builds upon PNA by leveraging the information bottleneck principle, and the cell isomorphism network (CIN) (Bodnar et al., ), which is a hierarchical message-passing framework utilizing the topological features of graphs. Despite its simple design, the expressivity of SIR-GCN is evident in its close performance to that of complex GNN frameworks.

## 6 Conclusion

In summary, the paper provides a novel perspective for creating a powerful GNN across all levels when the space of node features is uncountable. The central idea is to use pseudometric distances to create soft-injective functions such that distinct inputs may produce similar outputs if and only if the distance between inputs is sufficiently small on some representation. From the results, the SIR-GCN is proposed as the first MPNN instance to emphasize contextualized message transformation, setting it apart from other GNNs. Furthermore, the model is shown to generalize classical GNN methodologies. Despite its simple design, empirical results underscore SIR-GCN as the best-performing MPNN instance that effectively balances model complexity and expressivity. The paper thus contributes to GNN literature by theoretically and empirically demonstrating the necessity of both anisotropic and dynamic messages to enhance GNN expressivity. Future works may consider incorporating SIR-GCN into complex frameworks, such as grouped reversible residual connections (Li et al., ), adaptive graph diffusion (Sun et al., ), graph stochastic attention (Miao et al., ), and hierarchical message-passing (Bodnar et al., ), to address the limitations inherent in the MPNN framework and to develop more expressive GNN architectures.

#### Acknowledgments

The work is supported by the Japan Society for the Promotion of Science through the Grants-in-Aid for Scientific Research Program (KAKENHI 18K19821 and 22K19833) and by Kyoto University and Toyota Motor Corporation through the joint project Advanced Mathematical Science for Mobility Society.

## Appendix A Proofs

###### Definition 2 (Conditionally positive definite kernel (Schölkopf, 2000 ) ) .

Let $\mathcal{H}$ be a non-empty set. A symmetric function $\tilde{k}:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}$ is a conditionally positive definite kernel on $\mathcal{H}$ if for all $N\in\mathbb{N}$ and $\bm{h}^{(1)},\bm{h}^{(2)},\ldots,\bm{h}^{(N)}\in\mathcal{H}$,

$$ $\sum_{i=1}^{N}\sum_{j=1}^{N}c_{i}c_{j}~{}\tilde{k}\left(\bm{h}^{(i)},\bm{h}^{( j)}\right)\geq 0,$ (21) $$

with $c_{1},c_{2},\ldots,c_{N}\in\mathbb{R}$ and $\sum_{i=1}^{N}c_{i}=0$.

###### Theorem 2 (Hilbert space representation of conditionally positive definite kernels (Berg et al., 1984 ; Schoenberg, 1938 ; Schölkopf, 2000 ) ) .

Let $\mathcal{H}$ be a non-empty set and $\tilde{k}:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}$ a conditionally positive definite kernel on $\mathcal{H}$ satisfying $\tilde{k}\left(\bm{h},\bm{h}\right)=0$ for all $\bm{h}\in\mathcal{H}$. There exists a Hilbert space $\mathcal{S}$ of real-valued functions on $\mathcal{H}$ and a feature map $g:\mathcal{H}\rightarrow\mathcal{S}$ such that for every $\bm{h}^{(1)},\bm{h}^{(1)}\in\mathcal{H}$,

$$ $\left\lVert g\left(\bm{h}^{(1)}\right)-g\left(\bm{h}^{(2)}\right)\right\rVert^ {2}=-\tilde{k}\left(\bm{h}^{(1)},\bm{h}^{(2)}\right).$ (22) $$

###### Proof.

See Schölkopf ().
∎

See 1

###### Proof.

Let $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ be a pseudometric. From Assumption 1 and Theorem 2, there exists a feature map $g:\mathcal{H}\rightarrow\mathcal{S}$ such that for every $\bm{h}^{(1)},\bm{h}^{(2)}\in\mathcal{H}$,

$$ $\left\lVert g\left(\bm{h}^{(1)}\right)-g\left(\bm{h}^{(2)}\right)\right\rVert= d\left(\bm{h}^{(1)},\bm{h}^{(2)}\right).$ (23) $$

Hence, for every $\varepsilon_{1}>\varepsilon_{2}>0$,

$$ $\varepsilon_{2}<\left\lVert g\left(\bm{h}^{(1)}\right)-g\left(\bm{h}^{(2)} \right)\right\rVert<\varepsilon_{1}\iff\varepsilon_{2}<d\left(\bm{h}^{(1)},\bm {h}^{(2)}\right)<\varepsilon_{1}.$ (24) $$

∎

###### Theorem 3 .

Suppose $\bm{h}^{(0)},\bm{h}^{(1)},\bm{h}^{(2)}\in\mathcal{H}$ and $\tilde{k}:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}$ is a symmetric function. Then

$$ $k\left(\bm{h}^{(1)},\bm{h}^{(2)}\right)=\dfrac{1}{2}\left[\tilde{k}\left(\bm{h }^{(1)},\bm{h}^{(2)}\right)-\tilde{k}\left(\bm{h}^{(1)},\bm{h}^{(0)}\right)- \tilde{k}\left(\bm{h}^{(0)},\bm{h}^{(2)}\right)+\tilde{k}\left(\bm{h}^{(0)}, \bm{h}^{(0)}\right)\right]$ (25) $$

is positive definite if and only if $\tilde{k}$ is conditionally positive definite.

###### Proof.

See Schölkopf ().
∎

See 1

###### Proof.

Let $D$ be a pseudometric on bounded, equinumerous multisets of $\mathcal{H}$ defined as

$$ $D^{2}\left(\bm{H}^{(1)},\bm{H}^{(2)}\right)=\sum_{\begin{subarray}{c}\bm{h}\in \bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})- \dfrac{1}{2}\sum_{\begin{subarray}{c}\bm{h}\in\bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(1)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})- \dfrac{1}{2}\sum_{\begin{subarray}{c}\bm{h}\in\bm{H}^{(2)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}d^{2}(\bm{h},\bm{h^{\prime}})$ (26) $$

for some pseudometric $d:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}_{\geq 0}$ and bounded, equinumerous multisets $\bm{H}^{(1)},\bm{H}^{(2)}$. From Assumption 1 and Theorem 3, the pseudometric $d$ has a corresponding positive definite kernel $k:\mathcal{H}\times\mathcal{H}\rightarrow\mathbb{R}$. A simple algebraic manipulation and using the fact that $\bm{H}^{(1)},\bm{H}^{(2)}$ are equinumerous results in

$$ $D^{2}\left(\bm{H}^{(1)},\bm{H}^{(2)}\right)=\sum_{\begin{subarray}{c}\bm{h}\in \bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(1)}\end{subarray}}k(\bm{h},\bm{h^{\prime}})+\sum_{ \begin{subarray}{c}\bm{h}\in\bm{H}^{(2)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}k(\bm{h},\bm{h^{\prime}})-2\sum_{ \begin{subarray}{c}\bm{h}\in\bm{H}^{(1)}\\ \bm{h^{\prime}}\in\bm{H}^{(2)}\end{subarray}}k(\bm{h},\bm{h^{\prime}}).$ (27) $$

Note that $D$ is indeed a pseudometric since $k$ is positive definite as noted by Joshi et al. ().(^3^33If $k$ is also integrally strictly positive definite (Sriperumbudur et al., ), then the hash function $G$ becomes injective and $D$ becomes a metric.) By the reproducing property of $k$ and the linearity of the inner product, it may be shown that

$$ $\left\lVert G\left(\bm{H}^{(1)}\right)-G\left(\bm{H}^{(2)}\right)\right\rVert= D\left(\bm{H}^{(1)},\bm{H}^{(2)}\right),$ (28) $$

where

$$ $G(\bm{H})=\sum_{\bm{h}\in\bm{H}}g(\bm{h})$ (29) $$

and $g$ is the corresponding feature map of the kernel $k$. Hence, for every $\varepsilon_{1}>\varepsilon_{2}>0$,

$$ $\varepsilon_{2}<\left\lVert G\left(\bm{H}^{(1)}\right)-G\left(\bm{H}^{(2)} \right)\right\rVert<\varepsilon_{1}\iff\varepsilon_{2}<D\left(\bm{H}^{(1)},\bm {H}^{(2)}\right)<\varepsilon_{1}.$ (30) $$

∎

###### Definition 2 (Conditionally positive definite kernel (Schölkopf, 2000 ) ) .

###### Theorem 2 (Hilbert space representation of conditionally positive definite kernels (Berg et al., 1984 ; Schoenberg, 1938 ; Schölkopf, 2000 ) ) .

###### Proof.

###### Proof.

###### Theorem 3 .

###### Proof.

###### Proof.

## Appendix B Experimental set-up

All experiments are conducted on a single NVIDIA^® Quadro RTX 6000 (24GB) card using the Deep Graph Library (Wang et al., ) with PyTorch (Paszke et al., ) backend. For synthetic datasets, the reported results are obtained from the models at the final epoch across 10 trials with varying seed values. For benchmark datasets, the reported results are obtained from the models with the best validation loss across the 10 trials. The hyperparameters are chosen based on previous results and heuristics without extensive tuning. The codes to reproduce the results may be found at [https://github.com/briangodwinlim/SIR-GCN](https://github.com/briangodwinlim/SIR-GCN).

### B.1 Synthetic datasets

##### DictionaryLookup

Adopting Brody et al. (), the training dataset consists of 4,000 bipartite graphs, each containing $2n$ nodes with randomly assigned attributes and values, while the test dataset comprises 1,000 bipartite graphs with the same configuration. All models utilize a single GNN layer with $4n$ hidden units. A two-layer MLP is also used for GIN and $\sigma$ of SIR-GCN while PNA uses the sum, max, and std aggregators. Model training is performed with the AdamW (Loshchilov & Hutter, ) optimizer for over 500 epochs with a batch size of 256 and a learning rate of 0.001 that decays by a factor of 0.5 with patience of 10 epochs based on the training loss.

##### GraphHeterophily

The training dataset consists of 4,000 directed graphs, each containing a maximum of 50 nodes with randomly assigned labels from one of $c$ classes, while the test dataset comprises 1,000 directed graphs with the same configuration. All models utilize a single GNN layer with $10c$ hidden units and sum pooling as the graph readout function. A feed-forward neural network is also used for GIN while PNA uses the sum, max, and std aggregators. Model training is performed with the AdamW (Loshchilov & Hutter, ) optimizer for over 500 epochs with a batch size of 256 and a learning rate of 0.001 that decays by a factor of 0.5 with patience of 10 epochs based on the training loss.

### B.2 Benchmark datasets

##### Benchmarking GNNs

The datasets are obtained from dgl with data splits (training, validation, test) following Dwivedi et al. (). In line with Dwivedi et al. (), all models utilize 4 GNN layers with batch normalization and residual connections while constrained with a parameter budget of 100,000. Regularization with weights in $\left\{1\times 10^{-7},1\times 10^{-6},1\times 10^{-5}\right\}$ and dropouts with rates in $\left\{0.1,0.2,0.3\right\}$ are also used to prevent overfitting. The mean, symmetric mean, and max aggregators are used since the sum aggregator is observed to not generalize well to unseen graphs as noted by Veličković et al. (). Additionally, sum pooling is used as the graph readout function for ZINC while mean pooling is used for MNIST and CIFAR10. Model training is performed with the AdamW (Loshchilov & Hutter, ) optimizer for over a maximum of 500 epochs with a batch size of 128, whenever applicable, and a learning rate of 0.001 that decays by a factor of 0.5 with patience of 10 epochs based on the training loss. The reported results for other models in Table 3 are obtained from Dwivedi et al. (), Corso et al. (), and Tailor et al. ().

##### ogbn-arxiv

The dataset is obtained from ogb with data splits (training, validation, test) following Hu et al. (). The models utilize a single GNN layer with 256 hidden units, batch normalization, and residual connections. Regularization with weight $1\times 10^{-6}$ and dropouts with rates in increments of 0.1 are also used to prevent overfitting. The symmetric mean aggregator is used along with existing tricks in literature. Model training is performed with the AdamW (Loshchilov & Hutter, ) optimizer for over 500 epochs and a learning rate of 0.01 that decays by a factor of 0.5 with patience of 50 epochs based on the training loss. The reported results for other models in Table 4 are obtained from the OGB leaderboard accessible at [https://ogb.stanford.edu](https://ogb.stanford.edu).

##### ogbg-molhiv

The dataset is obtained from ogb with data splits (training, validation, test) following Hu et al. (). The models utilize a single GNN layer, modified to leverage edge features as described in Appendix D, with 300 hidden units, batch/graph normalization, and residual connections. Regularization with weight $1\times 10^{-7}$ and dropouts with rates in $\left\{0.1,0.4\right\}$ are also used to prevent overfitting. The sum aggregator is used for SIR-GCN aggregation while mean pooling is used as the graph readout function. Model training is performed with the AdamW (Loshchilov & Hutter, ) optimizer for over 200 epochs with a batch size of 128 and a learning rate of 0.001 that decays by a factor of 0.5 with patience of 20 epochs based on the training loss. The reported results for other models in Table 5 are obtained from the OGB leaderboard accessible at [https://ogb.stanford.edu](https://ogb.stanford.edu).

## Appendix C Model run time

As an additional evaluation, the run time per epoch for each model in the synthetic datasets is presented in Tables 6 and 7. The results, when considered alongside Tables 1 and 2, illustrate that SIR-GCN achieves a balance between computational complexity and model expressivity. Notably, SIR-GCN is computationally less expensive than PNA while delivering superior performance. These results further underscore the practicality of the proposed model.

**Table 6: Run time per epoch on DictionaryLookup.**
| Model | $n=10$ | $n=20$ | $n=30$ | $n=40$ | $n=50$ |
| --- | --- | --- | --- | --- | --- |
| GCN | 0.3526s $\pm$ 0.0778s | 0.4734s $\pm$ 0.0468s | 0.4777s $\pm$ 0.0854s | 0.5619s $\pm$ 0.0518s | 0.5520s $\pm$ 0.0679s |
| GraphSAGE | 0.4565s $\pm$ 0.0873s | 0.5264s $\pm$ 0.0317s | 0.5716s $\pm$ 0.1132s | 0.7742s $\pm$ 0.0597s | 0.9193s $\pm$ 0.0473s |
| GATv2 | 0.3950s $\pm$ 0.1017s | 0.5276s $\pm$ 0.0556s | 0.6191s $\pm$ 0.0879s | 0.7472s $\pm$ 0.0346s | 1.0065s $\pm$ 0.0280s |
| GIN | 0.3696s $\pm$ 0.0899s | 0.4610s $\pm$ 0.0459s | 0.4670s $\pm$ 0.0781s | 0.5947s $\pm$ 0.0548s | 0.5194s $\pm$ 0.0993s |
| PNA | 0.8854s $\pm$ 0.0412s | 1.1913s $\pm$ 0.1024s | 1.4526s $\pm$ 0.0684s | 1.8793s $\pm$ 0.0528s | 2.8387s $\pm$ 0.0603s |
| SIR-GCN | 0.4687s $\pm$ 0.0777s | 0.6066s $\pm$ 0.0398s | 0.8053s $\pm$ 0.0485s | 1.1496s $\pm$ 0.0427s | 1.7031s $\pm$ 0.0458s |

**Table 7: Run time per epoch on GraphHeterophily.**
| Model | $c=2$ | $c=4$ | $c=6$ | $c=8$ | $c=10$ |
| --- | --- | --- | --- | --- | --- |
| GCN | 0.4243s $\pm$ 0.0520s | 0.3852s $\pm$ 0.0517s | 0.3868s $\pm$ 0.0743s | 0.4166s $\pm$ 0.0551s | 0.4177s $\pm$ 0.0494s |
| GraphSAGE | 0.4691s $\pm$ 0.0400s | 0.4790s $\pm$ 0.0440s | 0.4399s $\pm$ 0.0629s | 0.4501s $\pm$ 0.0603s | 0.4964s $\pm$ 0.0601s |
| GATv2 | 0.4710s $\pm$ 0.0978s | 0.4941s $\pm$ 0.0567s | 0.4718s $\pm$ 0.0361s | 0.5514s $\pm$ 0.0608s | 0.5437s $\pm$ 0.0724s |
| GIN | 0.4085s $\pm$ 0.0741s | 0.3875s $\pm$ 0.0627s | 0.3855s $\pm$ 0.0645s | 0.4298s $\pm$ 0.0566s | 0.4329s $\pm$ 0.0534s |
| PNA | 2.2963s $\pm$ 0.0413s | 2.4238s $\pm$ 0.0611s | 2.4577s $\pm$ 0.0533s | 2.4741s $\pm$ 0.0665s | 2.5623s $\pm$ 0.0425s |
| SIR-GCN | 0.5338s $\pm$ 0.0353s | 0.5264s $\pm$ 0.0737s | 0.5635s $\pm$ 0.0695s | 0.5764s $\pm$ 0.0401s | 0.6230s $\pm$ 0.0388s |

## Appendix D SIR-GCN extensions

Denote $\bm{h_{u,v}}$ as the feature of the edge connecting node $v$ to node $u$. Following the intuition presented in Eqns. 8 and 9, SIR-GCN with residual connection may be modified to leverage edge features to obtain

$$ $\bm{h_{u}^{*}}=\textsc{MLP}_{\text{Res}}(\bm{h_{u}})+\sum_{v\in\mathcal{N}(u)} \bm{W_{R}}~{}\sigma\left(\bm{W_{Q}}\bm{h_{u}}+\bm{W_{E}}\bm{h_{u,v}}+\bm{W_{K} }\bm{h_{v}}\right),$ (31) $$

where $\bm{W_{E}}\in\mathbb{R}^{d_{\text{hidden}}\times d_{\text{in}}}$. Consequently, this also increases the computational complexity of the model to

$$ $\mathcal{O}\left(\left|\mathcal{E}\right|\times d_{\text{hidden}}\times d_{ \text{in}}+\left|\mathcal{V}\right|\times d_{\text{out}}\times d_{\text{hidden }}+\left|\mathcal{V}\right|\times\texttt{MLP}_{\text{Res}}\right),$ (32) $$

with $\texttt{MLP}_{\text{Res}}$ denoting the computational complexity of $\textsc{MLP}_{\text{Res}}$, which is comparable to PNA. Similarly, this extension may be viewed as a generalization of GIN with edge features (Hu et al., ).

Furthermore, one may inject inductive bias into the pseudometrics which may correspond to specifying the architecture type for the corresponding message function $g$. For instance, if node features are known to have a sequential relationship (e.g., stock (Hsu et al., ) and fMRI (Kim & Ye, ) data), $g$ may then be aptly modeled using recurrent or convolutional networks.

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: See weakness.
soundness: 2
strengths: - The uncountable feature is an important topic in GNN. 
- The writing and organization are good to follow. 
- The insight of existing methods under the framework of SIR-GCN is interesting.
summary: This paper extends PNA, which considers uncountable node features, by incorporating anisotropic and dynamic. The difference between PNA and the proposed SIR-GCN is the nonlinear mapping outside the message creation. To motivate this method, the authors introduce the concept of soft-injective function. This paper shows some existing methods are variants of the proposed SIR-GCN. Evaluations on synthetic and real datasets demonstrate its effectiveness.
weaknesses: - The novelty seems weak. Both the anisotropic and dynamic are not novel.  This paper can be seen as a combination of PNA and GATv2. 
- The motivation and the proposed SIR-GCN are not closely connected. It is not clear the connection between the soft-injective function, dynamic transformation, and anisotropic message. 
- The description of the GraphHeterophily is not clear. Thus,  it is not obvious why the proposed SIR-GCN significantly outperforms existing ones. 
- The derivation from Eq. 15 to Eq. 16 seems incorrect. First, the definition of $A$ is not given. Secondly, the anisotropic of GAT is on the edge weight, while that of Eq. 16 is on the message. It is not obvious.
- Figure 2 is not described clearly. What is the meaning of the horizontal and vertical coordinates? Why the contour of MLP is as in Figure 2(c) and 2(d).
- The evaluations are not convincing. Firstly, the ablation study and illustrative examples are not given. So, the effect of the proposed SIR-GCN is not justified. Secondly, it is not knowns whether the proposed SIR-GCN can be applied to complex models, whose performance is higher.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1.	According to the description of GAT, does GAT also preserve both anisotropic and isotropic? 
2.	For Table 4, Can GAT or GraphSAGE achieve similar performance with more parameters?
soundness: 3
strengths: 1.	It is interesting to see how the author tackles the problem of uncountable node features using pseudo metric and soft-injective functions.
2.	The designed model has certain flexibility in terms of anisotropic and isotropic properties. The model architecture also generalizes easily to some popular GNNs.
3.	The experiment shows the SIR-GCN performance well on the Dictionary Lookup task and against other baseline models during the benchmarking test.
summary: This paper investigates the representational capacity of Graph Neural Networks (GNNs) with uncountable node features and introduces an MLP-based MPNN named SIR-GCN, which generalizes to several popular GNN architectures. The authors demonstrate that for uncountable node features, it is possible to identify a soft-injective function corresponding to a specific pseudometric that quantifies dissimilarity in the node feature space. They then model this soft injective function using an MLP and design an architecture that maintains both anisotropic and isotropic properties. Experimental results highlight the model’s superiority across various scenarios, including cases with countable and uncountable node features, as well as graphs exhibiting heterophily.
weaknesses: 1.	Since the SIR-GCN can generalize to other GNNs, it would be better if the author can explain why it is hard for other GNNs to handle the problem of uncountable node features.
2.	It would be nice if the author can explain why there are some missing values in Table.
3.	For the graph heterophily experiment, it would be better if the author can use some real world datasets with different degrees of heterophily[1].

[1] Mao H, Chen Z, Jin W, Han H, Ma Y, Zhao T, Shah N, Tang J. Demystifying structural disparity in graph neural networks: Can one size fit all?. Advances in neural information processing systems, 2024.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weaknesses
soundness: 3
strengths: 1. The paper presents an interesting approach, offering clear insights into relaxing the injective constraint in message-passing processes by defining a pseudometric distance, which captures differences within data effectively.

2. The theoretical basis is solid, providing a coherent and accessible framework that helps explain the introduced ideas.

3. Although the proposed method is limited by the 1-WL test, it shows strong representational capabilities. Its effectiveness is supported by experiments conducted on both synthetic and real-world datasets, confirming its practical usefulness.
summary: The paper introduces a new perspective on the representational capability of GNNs by presenting a soft-injective function using a pseudometric distance. It then proposes a new message-passing scheme that performs competitively across various datasets.
weaknesses: 1. The experimental section is somewhat unclear, especially regarding the number of parameters in Table 4 compared to Table 3. It is confusing why the same model appears to have twice the number of parameters. The authors emphasize "a single layer" in line 507 but do not mention this detail in Table 4, which could lead to potential inconsistencies. To improve clarity and fairness, the authors should add explanations of any differences in the model architecture between datasets. This would help readers better understand the experimental setup and assess the fairness of the comparisons.


2. Although the authors claim to achieve "a balance between computational complexity and model expressivity" (line 820), the experiments related to computational efficiency (Tables 6,7) are not convincing enough. Adding runtime analysis on larger-scale datasets, such as ogbg-molhiv/ogbn-arxiv, would support these claims and better demonstrate the method's scalability.