Contextualized Messages Boost Graph Representations

Authors: Brian Godwin Lim, Galvin Brice Sy Lim, Renzo Roel Tan, Kazushi Ikeda
Primary area: learning on graphs and other geometries & topologies
Keywords: deep learning, graph neural network, representational capability, soft-isomorphic relational graph convolution network

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.

Decision: reject
Reviewer scores: 3, 6, 6

Reviews and discussion:
<thread>
creation date:
1730544128438

thread_type:
official_review

<thread_object>
creator: reviewer_yvug

<content>
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.

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.

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.

questions:
See Weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730684506374

thread_type:
official_review

<thread_object>
creator: reviewer_rjgm

<content>
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.

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731202111473

thread_type:
official_review

<thread_object>
creator: reviewer_nmsr

<content>
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.

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.

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.

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731863657628

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Clarifications on Novelty and Significance

comment:
We would like to further clarify the novelty and significance of our work, especially in relation to Velickovic et al. (2017), Brody et al. (2021), and Corso et al. (2020).

First, while Velickovic et al. (2017) introduced the original GAT by integrating attention mechanisms into GNNs, their work primarily focused on heuristic and empirical validation. It lacked a rigorous theoretical analysis of how attention mechanisms impact the representational capability of GNNs. Brody et al. (2021) later extended GAT by specifically analyzing the role of *dynamic* attention mechanisms, providing theoretical insights into their utility. However, their contributions were still limited to refining the intuition behind GAT and did not explore its implications for handling uncountable node features or the broader representational capability of GNNs. Moreover, given the focus on attention mechanisms, both studies simply employ linear transformations to the actual messages. 

Meanwhile, Corso et al. (2020) specifically tackled the problem of uncountable node features by providing theoretical justifications for using multiple aggregators and scalers in GNNs to enforce injectivity for graph isomorphism tasks, resulting in the PNA. Nonetheless, the *anisotropic* nature of PNA emerges as a consequence of applying the theoretical result heuristically within a linear/*static* MPNN framework as we noted in Line 343, rather than through theoretical insight. In fact, our analysis in Line 332 reveals a critical limitation in the *anisotropic* nature of PNA, specifically in the limited influence of center node features on the aggregated neighborhood features.

In contrast, our work fundamentally diverges from these prior studies by introducing a **novel and comprehensive perspective** on the representational capability of GNNs with uncountable node features. Specifically, we are the first to introduce **new theoretical results**, based on *pseudometrics* and *soft-injective* functions, demonstrating how GNNs can preserve their representational capability even by relaxing the strict injective and metric constraints in previous works, such as Corso et al. (2020). Our main theoretical result in Corollary 1 directly leads to the emergence of the *anisotropic* and *dynamic* properties of *soft-injective* message functions, as outlined in Lines 192 and 216. While these properties have been studied independently by Brody et al. (2021), their presence here only serves to underscore how existing works complement and validate our theoretical findings. Crucially, our work is the first to theoretically justify how these properties, when applied to message functions (in contrast to attention mechanisms), enable GNNs, specifically SIR-GCN, to effectively handle uncountable node features, as highlighted in Line 531. To support our theoretical findings, we also provide **intuitive illustrations** through two synthetic datasets, demonstrating the limitations of existing GNNs in simple node and graph property prediction tasks and how SIR-GCN, with its novel design, specifically addresses these weaknesses, offering an intuitive understanding of the practical utility of our theoretical results. Additionally, our framework is validated by **extensive experimental results** on benchmark datasets, where the theoretical concepts and intuition presented concretely translate to SIR-GCN consistently outperforming conventional GNNs across diverse tasks and domains, highlighting the significance of our theoretical results. Overall, our work introduces a novel theoretical foundation for a key problem in GNNs that is supported by both intuition and experimental results, thereby advancing our understanding of the representational capabilities of GNNs.

References:

Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105.14491, 2021.

Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260–13271, 2020.

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733149145760

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Rebuttal Discussions

comment:
We sincerely thank the reviewers for their time and valuable feedback!

In summary, our paper introduces a novel theoretical framework based on *pseudometrics* and *soft-injective* functions for understanding the representational capabilities of GNNs, with a specific focus on uncountable node features. Through rigorous theoretical analysis, we highlight that message functions in the MPNN framework must be *anisotropic* and *dynamic*. We then translate this theoretical insight into our proposed SIR-GCN, which is the first MPNN instance to satisfy these properties. Empirically, we also demonstrate how this key feature allows SIR-GCN to generalize and consistently outperform existing foundational GNNs, including GCN, GraphSAGE, GAT, GIN, and PNA, across various synthetic and benchmark datasets spanning diverse domains. Our work thus provides new, relevant, and impactful theoretical and empirical advancements toward understanding GNN representational capabilities.

Notably, our work fundamentally differs from Brody et al. (2021) by offering a comprehensive theoretical analysis of the broader representational capabilities of GNNs, extending beyond the GAT attention mechanism investigated by Brody et al. (2021). While GATv2 applies *anisotropic* and *dynamic* functions on its attention mechanism, its messages nevertheless remain linear, potentially limiting its expressivity. In contrast, motivated by our novel theoretical results, the *anisotropic* and *dynamic* messages of SIR-GCN are explicitly designed to boost GNN representational capability. Similarly, while Corso et al. (2020) also examined the representational capabilities of GNNs with uncountable node features, our theoretical framework is fundamentally distinct in being the first to *softly* relax the injective and metric requirements of prior works. This approach allows SIR-GCN to achieve computational efficiency with a single aggregator while still outperforming PNA and GATv2 despite its simple design. These key differences in scope and approach underscore the novelty and significance of our work.

In response to Reviewer NmsR, we would also like to clarify that, consistent with prominent foundational works in GNN such as Xu et al. (2018), Corso et al. (2020), and Brody et al. (2021), our foundational paper also focuses on introducing novel theoretical insights and developing a foundational GNN model within the MPNN framework. Extending these theoretical results to more complex frameworks, while important, involves significant additional theoretical analysis and experimentation that warrants a comprehensive discussion in a separate and dedicated study, similar to how separate and subsequent papers extended the results of Xu et al. (2018) to higher-order WL tests. Furthermore, these foundational GNN works also primarily compared their proposed models (*e.g.*, GIN, GATv2, PNA) to other foundational GNNs (*e.g.*, GCN, GraphSAGE, GAT) to isolate and highlight performance improvements solely attributed to the key features of their model. Following these works, we only directly compare SIR-GCN to existing foundational GNNs but do not extend the comparison to state-of-the-art models, as these incorporate additional techniques that significantly enhance their performance, making such a comparison neither fair nor meaningful. This experimental analysis would also require substantial model tuning and experimentation that also deserves a separate study to ensure rigor. Nonetheless, we emphasize that our work, in its current form, already makes a significant contribution to the GNN literature by addressing the important problem of uncountable node features and providing novel theoretical and empirical insights. Furthermore, as a foundational work, it already includes the key discussions and comparisons standard in prominent foundational GNN works.

References:

Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105.14491, 2021.

Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-13271, 2020.

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
</content>
</thread_object>

</thread>


Metareview: