Towards Global Interaction Efficiency of Graph Networks

We sincerely thank you for your time and valuable comments.

(W1) The key concepts of the paper (such as global/universal interaction, interaction sensitivity, and interaction expressiveness) are not well-defined.

• The definition of global interaction is defined in terms of the channels of inputs and outputs. How does this relate to interaction patterns, e.g., the five synthetic interaction patterns in Section 5.1? Also, how does this relate to node/pair symmetry?

  Global interaction as in Eq. 2 defines a $n\times n$ matrix, where each entry corresponds to a node pair. An interaction pattern refers to one such matrix with specific entry values. However, we do not need to deal with all $n\times n$ entries as the symmetric pairs always have the same entry values, which we call symmetry bias of GNNs (Please refer to the modification Section 3.2 in the updated PDF). So, let $\eta$ denote the number of symmetric partitions, an interaction pattern is an assignment of $\eta$ partitions. The 5 synthetic interaction patterns in Section 5.1 are 5 different assignments on the $\eta$ partitions.

• For "how a model can universally express any desired interaction within a given graph", what does "universally" mean? The paper also mentions universal interaction but no formal definition is provided.

  We refine the statement to "how a model can universally approximate any interaction", as universal approximation is a more well-adopted concept [1]. Then "universal interaction" means a model's capability to approximate any interaction with proper neural parameter assignments. This concept aligns with the idea of universal filters, as explored in various graph signal filtering studies [2, 3, 4, 5]. Please refer to the middle part of Page 2 in the updated PDF for further details.

• Interaction sensitivity is defined to measure the sensitivity of model outputs to perturbations in input node features. However, perturbations in input node features are not the same as interactions between node pairs - so how are they related? Also, why is interaction expressiveness considered as one aspect of interaction efficiency?

  As in Eq. 2, the global interaction $\mathrm J_{\theta,W}\in\mathbb R^{n\times n}$ includes interactions among all node pairs ($\mathrm J_{i,j}\in\mathbb R$ indicates the interaction between nodes $i$ and $j$), and it can be formalized as the Jacobian of all node features before and after GNN operations. That is why "perturbations in input node features" and "interactions between node pairs" are related. The determinant of the Jacoabian is commonly used in sensitivity measurement, so we use it to study interaction sensitivity, i.e. the rate of change of outputs with respect to the perturbation of inputs. Briefly, GNNs can learn different interactions $\mathrm J_{\theta,W}$ for the underlying graph, some interactions with small $|\mathrm J_{\theta,W}|$ refer to the change of model output less sensitive to the perturbations of model input. We employ the term 'interaction efficiency' to convey the ability to effectively model diverse and complex interactions. Analogous to filter expressiveness [2, 3, 4, 5], interaction expressiveness gauges the extent to which a model can express/approximate interactions. It serves as the fundamental criterion for interaction efficiency.

We sincerely thank you for your time and valuable comments.

Q1: Clarifications on Proposition 5

Proposition 5 serves as a general and self-consistent conclusion, with no need to specify symmetric or non-symmetric cases. Specifically, for the symmetric case, although injective $\varphi$ will generate different outputs for symmetric pairs, the MLP $f_{\Theta}$ which takes the outputs of $\varphi$ as inputs can learn the same interaction for them. So Proposition 5 always holds, whether considering the symmetry or not. Then, to ensure symmetric pairs always learn the same interactions, we relax the injectivity of $\varphi$ by ensuring that symmetric pairs always share the same output as in Equation 6.

We note that the related statement may result in such confusion, and we update the related statements in the updated PDF to make it clearer.

Q2: What is the specific $\varphi^{\textrm{LE}}$ is used in this paper?

Apart from existing design of $\varphi^{\textrm{LE}}$, we propose the new one $[(\tilde D^{\epsilon}\tilde A\tilde D^{-1-\epsilon})^k]\_{k\in[K],\epsilon\in[-1,0]}$. It preserves the benefits of two popular designs while avoiding their respective drawbacks: Compared with $[(\tilde D^{-1}\tilde A)^k]\_{k\in[K]}$ in [1], it provides more diverse pair encodings, and compared with $[(\tilde D^{\epsilon}\tilde A\tilde D^{\epsilon})^k]\_{k\in[K],\epsilon\in[-1,0]}$ in [2], it has the bounded spectrum thus can be easier to handle numerical instability when applying a larger $K$.

Given the flexible nature of the $\varphi^{\textrm{LE}}$ design, our primary focus lies in understanding its general properties, such as the partial order among implementations and the presence of symmetry bias. As a result, we include our implementation of $\varphi^{\textrm{LE}}$ in the appendix rather than the main body of the updated PDF.

Q3: Comparisons with “total resistance” [3] & Possible misunderstandings on global interactions

Our interaction efficiency analysis involves interaction sensitivity and interaction expressiveness respectively. The former one may be comparable to "total resistance" $R_{tot}$ [3] as they all measure the property of the entire graph with a scalar. But the considered metrics are different. We use the determinant of the Jacobian of all nodes. It is a commonly used metric in stability and sensitivity analysis, and in our settings, it captures the rate of change of all output nodes to changes in all input nodes. The total resistance study extends local pairwise effective resistance to the global scenario by summing of the effective resistance between all pairs of nodes.

"Furthermore, it does not seem necessary to distinguish 'global' and 'local' interaction efficiency because ..." seems to be a misunderstanding. Here is the clarification:

Our work aims to extend existing individual pair interaction studies, e.g. long-range interaction, to the global scenario. To this end, we use $\mathrm J_{\theta,W}\in\mathbb R^{n\times n}$ in Eq. 2 to model global interactions. Based on $\mathrm J_{\theta,W}$, we analyze

• interaction sensitivity, measured by its determinant $|\mathrm J_{\theta,W}|$ in Section 3.1, and
• interaction expressiveness, measured by the space $\{\mathrm J_{\theta,W}\big|\theta\in\mathbb R^k,W\in\mathbb R^{\star}\}$ in Section 3.2.

We added discussions on the difference with [3] in Section 1 in the updated PDF.

Q4: The scalability of UIGC

Our UIGC does not require the computation of graph automorphisms. Notably, learning the same interactions for symmetric pairs (where symmetry is induced by graph automorphisms) is inherently satisfied by all GNNs, including ours. This is facilitated by the symmetry bias inherent in $\varphi^{\textrm{LE}}$, as discussed in Section 4. The mention of graph automorphisms in our submission is solely for the purpose of interaction expressiveness analysis and does not introduce any additional computations.

We sincerely thank you for your time and valuable comments.

W1, Q1, Q2: Why do we specifically care about pairs of nodes and their interactions? & Why do we study global interactions?

• Why do we specifically care about pairs of nodes and their interactions?

  In a graph, one node can influence another node through direct or indirect connections. Pair interactions serve as a fundamental component to model this mutual influence. For instance, existing studies on long-range interactions concentrate on scenarios where a pair of nodes is distant from each other, demonstrating that their pair interaction decays exponentially with respect to the distance [1, 2].

• Why we should study global interactions which consider all pair interactions simultaneously?

  The influence among distinct pairs of nodes is not independent. Certain information can only be effectively captured when examined in a 'simultaneous' rather than an 'individual' manner. To explain this, we replace the "benzene rings" example with a more intuitive one: considering the scenario where A, B, and C co-author a paper together, where the relationship cannot be accurately represented by breaking it down into three separate relations like 'A and B co-author a paper together,' 'B and C co-author a paper together,' and 'A and C co-author a paper together.' The reason is that these individual relations also encompass cases where A&B, B&C, and A&C co-author in three distinct papers, respectively. To address this, we adopt a global interactions perspective, where we consider all node pairs and their interactions simultaneously, as illustrated in Figure 1.

Interaction expressiveness shares a similar concern with graph filter expressiveness [3]. For a graph with $n$ nodes, The corresponding Laplacian involves $n$ graph Fourier bases, each associated with a filtering coefficient. The concurrent consideration of filtering across different bases results in a filter space denoted as $\mathbb R^n$ [4, 5, 6, 7]. Recent studies emphasize the necessity to enhance filter expressiveness to effectively span and cover this space. In a parallel analogy, within the framework of global interactions, each node pair is assigned an interaction coefficient. To view all pair interactions simultaneously, the dimensions of the interaction space is related to the number of pairs.

We have refined the description of our motivations in Section 1 in the updated PDF.

W2: Experiments: The results in Table 2 and Table 3 show that the proposed method achieves strong performance on some of the datasets while falling short on some others.

In UIGC, we utilize the MLP $f_{\Theta}$ to model interactions. The classification improvement on small-scale datasets shows the alleviation of the overfitting issue. However, datasets like IMDB-B have no classification gains, indicating that label-related interaction patterns on these graphs may be inherently simple and can be easily captured by basic models.

Q3: The setup for Section 5.1

We refined the description of the setup in Section 5.1 in the updated PDF. In Section 5.1, we test five interaction patterns with different approximation difficulties, including $h(k)=\alpha$, $h(k)=\alpha k$, $h(k)=k^{\alpha}$, $h(k)=\sin(\alpha k)$ and $h(k)=\alpha\lceil k/40\rceil$, where $k$ is the pair partition index, $h(k)$ is the synthetic interaction, $\alpha$ is a scalar used to control the output. In Figure 3, x-axis is the partition index $k$ and y-axis is the interaction $h(k)$.

[1] Topping, Jake, et al. "Understanding over-squashing and bottlenecks on graphs via curvature." International Conference on Learning Representations. 2021.

[2] Liu, Juncheng, et al. "Mgnni: Multiscale graph neural networks with implicit layers." Advances in Neural Information Processing Systems 35 (2022): 21358-21370.

[3] Balcilar, Muhammet, et al. "Analyzing the expressive power of graph neural networks in a spectral perspective." Proceedings of the International Conference on Learning Representations (ICLR). 2021.

[4] He, M., Wei, Z., & Xu, H. (2021). Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 34, 14239-14251.

[5] Yang, Mingqi, et al. "A new perspective on the effects of spectrum in graph neural networks." International Conference on Machine Learning. PMLR, 2022.

[6] Wang, Xiyuan, and Muhan Zhang. "How powerful are spectral graph neural networks." International Conference on Machine Learning. PMLR, 2022.

[7] Bo, Deyu, et al. "Specformer: Spectral Graph Neural Networks Meet Transformers." The Eleventh International Conference on Learning Representations. 2022.