Towards characterizing the value of edge embeddings in graph neural networks

We thank the reviewer for their time and effort, and for appreciating our study of an “under-investigated” model and our “well-structured” writing. We address the reviewer’s comments below:

1. “I am not sure if I missed anything, but I feel the proof of the main theorem is somewhat inconsistent. First, the authors assume the graph has O(N) edges, implying a constant degree for the graph.”

Indeed, the graph has O(1) average degree, and it has O(n) maximum degree. These facts are consistent with each other, and not even unnatural in real-world settings where graph degrees often roughly follow e.g. Zipfian distributions.

2. “Following the above point, in Theorem 1, it seems that we assume constant memory for each embedding…If a real-world graph has an approximately constant average degree, I believe that by increasing the memory by a constant factor for node-based GNN models, they could achieve the same theoretical power as edge-based models”

If the graph has constant maximum degree, then this statement is true (Proposition 3). If the graph has constant average degree, then this statement is false (Theorem 1) unless one allows a different amount of memory per node (i.e. scaling with the node’s degree), in which case one essentially recovers the edge model. However, non-uniformity in the dimensions of different node embeddings adds engineering challenges and hence computational overheads—motivating our work, which studies when and whether this overhead is worthwhile.

Finally, we remark that in Theorem 1, the constructed edge protocol does not use extra total memory compared to the node protocols, since the graph has constant average degree.

3. “In the real-world experiments, although the absolute metrics of edge-based GNN models are better, the improvement is marginal. Considering the extra memory used by the edge-based GNN model to store embeddings, I question the practical value of this approach."

Indeed, the improvement is marginal. This means that the common benchmarks may be too easy to witness dramatic performance gains, but the theoretical results and synthetic tasks (e.g. Table 2) demonstrate that settings with dramatic gains do exist. As with any architectural design choice, there is always a trade-off: in this case, there is a trade-off between computational overhead and performance/representational advantage.

The practical value of edge GNNs has already been robustly demonstrated; see the references on lines 64–67. The purpose of this work was not to redo those experiments. As discussed in the paper (lines 67–70, lines 449–450), the purpose of this paper is to ablate the effect of maintaining edge embeddings via rigorous theory and controlled experiments. From this perspective, we would argue that our experiments are sufficient evidence for our main point: the edge-embedding architectural choice, when disentangled from the (many other) design choices made in prior works, does not hurt performance (across many common benchmarks) and can significantly help (in theoretically-grounded synthetic experiments).

4. “Regarding the synthetic task, I wonder if the authors constrained the total memory available to node-based and edge-based models.”

Yes. In the synthetic tasks, the graph is a tree, so E = N-1. We gave both models the same embedding dimension (d = 10). Thus, the comparison is fair: the only architectural change we made was placing embeddings on edges vs nodes (and giving the node GNN up to 2x the depth, which makes its high error an even stronger result).

We hope these clarifications are helpful. Please let us know if you have further questions!

I acknowledge the authors' response, which shows complete disinterest in taking my comments seriously, disregards my effort spent reviewing the paper and trying to give an objective but constructive perspective on the work. The authors do not seem to perceive the rebuttal as a place to discuss how to improve the paper and get it accepted but rather as a "battle arena".

I will nonetheless continue with my reviewer's duties and provide further comments below:

• The fact that the other reviewers found a high-level summary of the results readable does not necessarily mean (statistically speaking) that the paper is well structured or organized. The other reviewers, due to the same time constraints, might have decided to focus more on empirical aspects (indeed, see the general response of the authors) and decided not to focus too much on how the theoretical concept have been conveyed. I have read many theoretical papers whose presentation elegantly mixes theoretical results and high-level discussions without the redundancy of the manuscript under review, and for this reason I think that the manuscript could have much improved. So no, this is not "common practice" in theoretical papers.
• I think the authors are underestimating ICLR reviewers, who are well aware that rigor is necessary. Following previous papers does not guarantee that the authors' choice of notation is the best out there. More importantly, verbosity may imply rigor but the converse is not true. For instance, in most parts of the paper the subscript $G$ can be removed as clear from the context without extreme loss of rigor (the authors could just write a note in the paper); putting some effort in reducing the verbosity of terms like $I(\{u, v\}))$ would not hurt readability as well. These are just a few of many tricks that would not break rigor but reduce verbosity.
• I would not dare to underestimate the ICLR audience. I simply recognize good practice: a manuscript submitted to a general ML venue should be written accordingly for a general ML audience, and it is the reviewer's job to make sure this happens. Not all readers of ICLR proceedings know about graph machine learning, in fact I know quite a few myself. The authors' comment is presumptuous and unprofessional to say the least.
• I was referring to the assumption of O(1) bits per node processor. It is likely I did not understand something, but this is not something that happens in practice, where embeddings can have much higher dimensionality and does not require to go to O(n).

Questions:

• Lines 64-67: thank you for the clarification. What I can see is a list of application areas, not a specific set of use cases where the inductive bias of the edge-processor is helpful. As for previous answers, the "this is the list of previous works" is not a valid answer to my question. I was expecting a more fine-grained discussion on real-world problems, perhaps in the domain of "molecular property prediction" where predicting the edge information is necessary.
• I still believe that the "connection" might be the source of confusion, but I will not argue further about it.
• See comment above.

Overall, I do not think the authors gave me convincing reasons to believe that my arguments are incorrect. I will therefore keep my score.

We thank the reviewer for their time and effort. We are glad that the reviewer found our contributions “worthy” and “very welcome”, and for appreciating our attempt to “bridge the gap” with well-known frameworks that have received little attention in the graph machine learning community. We address the reviewer’s comments below:

1. “The organization of the paper seems to reflect more the thought process of the authors, instead of developing a narrative that helps the reader to follow.”

We regret that the reviewer found the exposition confusing. Since the other reviewers found that the paper is “well-structured”, “clear and accessible”, and that the writing “helps the readers quickly grasp the main ideas”, we are not sure how to respond.

(1a) “there seems to be an effort of the authors in presenting the same topics in an informal way before moving to the details”

This is common practice in theoretical papers, particularly in notationally heavy papers such as ours: Section 2 discusses our results in English, without the burden of formality, and subsequent sections make the results mathematically rigorous.

We are happy to add additional proof sketches in the appendix, but removing proof sketches from the main body seems counterproductive for non-theory readers. We are also happy to add details about e.g. hyperparameter sweeps to the appendices.

(1b) “Notation is also extremely verbose, and there would have been tons of ways to improve their readability.”

Notation is a necessary evil for theoretical rigor. We have tried to follow notation in prior works as closely as possible, see e.g.:

• (Xu et al., 2019) “How Powerful Are Graph Neural Networks?”
• (Huang and Villar, 2021) “A Short Tutorial On The Weisfeiler-Lehman Test And Its Variants”

As such, we believe our notation is as simple as possible, but if the reviewer has concrete suggestions we are happy to adjust.

(1c) “It is generally not a good idea to introduce message passing in an introduction for a general reader”

We believe that the reviewer is underestimating the ICLR audience.

2. “O(1) in lines 137-138 becomes O(log n) in lines 381-382”

Thanks for pointing out this typo. We will update lines 137-138 to say O(log n).

3. “One might argue that the memory assumptions of the Sections up to 6 are quite unrealistic”

What is the argument for this? We would argue that memory limitations are highly realistic. In large graphs it would be completely prohibitive to store O(n) memory per node. Space constraints have been a fundamental consideration in computer science and machine learning for decades.

Next, we address the reviewer’s questions.

1. “Are there more practical/real-world problems where you envision a particularly successful application of the edge framework compared to classical message passing?”

On lines 64–67, we discuss the extensive list of real-world applications where the edge GNN framework has already found success. Do these answer the reviewer’s question?

2. “Do you think it would be better to replace "symmetry" with "weight sharing"? Symmetry might refer to group theory concepts being applied to GNNs.”

“Symmetry” is the most common terminology in the theoretical GNN literature. The connection to group theory is not accidental, since symmetry constraints imply e.g. that the computation respects graph homomorphisms.

3. “Could the authors at least try to revise the notation during the rebuttal to make it less verbose and more readable?”

Again, we believe that the notation is already as minimal as possible without sacrificing rigor. However, if the reviewer has any concrete suggestion we would be happy to discuss.

We thank the reviewer for their time and effort. We are glad they find our results “noteworthy” and “contributing fresh theoretical insights”, and that our proof methodology is “a solid contribution to the literature”. Moreover, we are glad they found our paper to be “effectively communicating complex ideas”. See below for our responses to the reviewer’s comments:

1. “While the theoretical contributions are substantial, the empirical validation relies on a relatively small set of benchmarks and synthetic tasks. Expanding the experiments to include more diverse datasets and real-world applications would strengthen the claims made about the edge-based architecture's advantages.”

We would argue that our empirical validation—five common benchmarks, and two carefully-designed synthetic tasks, along with a fairly extensive sweep over hyperparameters for each considered architecture—is not “relatively small”. Please note that the purpose of this paper is not to propose a new architecture. Edge GNNs have already seen robust successes in many real-world settings (lines 64–67), well beyond common benchmarks.

As discussed in the paper (lines 67–70, lines 449–450), the purpose of this paper is to ablate the effect of maintaining edge embeddings via rigorous theory and controlled experiments. From this perspective, we would argue that our experiments are sufficient evidence for our main point: the edge-embedding architectural choice, when disentangled from the (many other) design choices made in prior works, does not hurt performance (across many common benchmarks) and can significantly help (in theoretically-grounded synthetic experiments).

2. “The paper primarily focuses on comparing two architectures (node-based and edge-based) without considering hybrid approaches or other recent advancements in GNN architectures that might offer competitive performance. A broader comparative analysis could provide a more comprehensive view of the landscape.”

To reiterate a previous point, the point of our paper is not to introduce a new architecture, but rather to isolate one important design choice (edge vs node embeddings) and understand its impact. To this end, simplicity is a virtue. A “broader comparative analysis” would be counterproductive, and even risks producing spurious scientific findings.

3. “While theoretical insights are valuable, the paper could benefit from a deeper discussion on the practical implications of adopting edge-based architectures. Addressing potential challenges in implementation, particularly regarding scalability and computational resources, would provide a more rounded perspective.”

We do point out in the conclusion that edge GNNs have computational overhead, and developing more efficient architectures that do not sacrifice the representational advantages is an interesting direction for future research. We are happy to expand this discussion if the reviewer wishes.

4. “The exploration of symmetry constraints in Theorem 5 is interesting, but the practical relevance of this focus could be questioned. Clarifying how these theoretical results translate into actionable insights for GNN design would enhance the paper's impact.”

Symmetry constraints are the standard theoretical lens for studying GNNs in prior literature; see e.g. the ICLR 2019 paper “How Powerful Are Graph Neural Networks” by Xu et al., which currently has over 9000 citations.

But the reviewer is not wrong: in fact, the purpose of Theorem 5 was precisely to show that the lens of symmetry constraints alone may not be the right theoretical tool for principled GNN design, since it fails to adjudicate the distinctions between edge and node embeddings (lines 152–153).

To address the reviewer’s questions:

1. “Could the authors elaborate on the intuition behind the theoretical separation results for edge and node message-passing protocols? Specifically, what practical implications arise from the hub node bottleneck, and how might this influence GNN architecture decisions?”

As the reviewer alludes to, the basic intuition is that hub nodes serve as bottlenecks to information flow for node-based protocols, but not for edge-based protocols which essentially have “more scratch space” near the hub node. This is made formal using techniques inspired by time-space tradeoffs and distributed computation lower bounds, as discussed in Remark 9. We hope that our results may inspire more efficient architectures that avoid the representational limitations of node GNNs, perhaps by adding more embeddings near bottlenecks, but we leave this interesting research question to future work.

2. “How generalizable are the findings in Theorems 1 and 4 to other types of graphs beyond the specific constructions discussed? Are there certain classes of graphs where edge-based protocols are expected to perform particularly poorly, or vice-versa?”

Intuitively, we expect that edge GNNs will be better in graphs with hub node bottlenecks. Lemma 2 is a quite general statement, and a separation arises whenever there is an edge-based protocol that “beats” the lower bound from Lemma 2.

From a representational perspective, it’s not hard to show that edge GNNs cannot be worse than node GNNs. We believe it unlikely that there is a clean, complete characterization of when edge GNNs are strictly better, due to the similarity between this question and deep questions in communication complexity and circuit complexity.

3. “Could you consider incorporating visual representations of key concepts to enhance reader understanding and engagement in the main content?”

If the reviewer has any concrete suggestions of useful visualizations, we are happy to discuss.

Dear Reviewer eeGn,

Thanks for your follow-up!

About link prediction tasks: for our benchmark evaluations, we wanted tasks that can be naturally implemented by both edge-based and node-based architectures, and where the only salient architectural difference is “edge-based vs node-based”. Implementing link prediction with a node-based architecture requires an extra step at the end where each edge collates its prediction from the embeddings of the incident nodes. The choice of collation function is an important design element for which there is no “canonical” choice (e.g. [1] uses a sigmoid function, [2] uses a Fermi-Dirac decoder, etc.). Since an edge-based architecture would not have this collation step, this introduces a confounder into any comparative experiment.

Additionally, in line with the message of the paper, we wanted to show that even in benchmarks in which the only benefit of the edge-based architecture is computational, rather than the task being a more “natural” fit for edge-based architectures—there’s still benefits from edge embeddings.

About diagrams: Thanks for the suggestions! In the revision we just uploaded, we have moved a figure illustrating the construction for Theorem 1 which was previously in the appendix to the main body. We have also added a new figure (to the appendix, due to space constraints) that visually illustrates the main intuition behind Theorems 1 and 4: namely, how hub nodes lead to an “information bottleneck”.

We hope that these address your remaining concerns – if so, we would greatly appreciate if you wish to increase your score!

[1] Kipf and Welling, “Variational Graph Auto-Encoders”. NeurIPS Bayesian DL Workshop, 2016.

[2] Chami et al., “Hyperbolic Graph Convolutional Neural Networks”. NeurIPS 2019.

We thank the reviewer for their time and effort, and we are glad they appreciate our exposition and “insights into the role of edge embeddings into graphs with hub nodes”. See below for responses to the reviewer’s comments:

1. “For dense graphs, maintaining edge embeddings requires substantial memory and can introduce considerable computational overhead, which may limit the scalability of edge-based architectures.”

Indeed, we are not suggesting that edge GNNs are a “one-size-fits-all” solution to graph machine learning. As we point out in the conclusion, we agree that on dense graphs, edge GNNs incur significant computational overhead over node GNNs. Despite this overhead, edge GNNs have found various applications in practice (see lines 64–67).

In any architectural design choice (even beyond just graph machine learning), there are inevitable trade-offs. Our theoretical results demonstrate potential representational advantages of edge GNNs—which, in any application, must be weighed against the potential computational drawbacks.

Finally, we remark that our separations hold on graphs with O(n) total degree, i.e. the representational advantages of edge GNNs can arise even in an “apples-to-apples” comparison where the total memory of the edge-based protocol (and the parallelized runtime) is comparable to that of the node-based protocol.

2. “Although the paper provides insights into the role of edge embeddings into graphs with hub nodes. The paper generally lacks practical guidance on which types of graphs would benefit most from edge embeddings. Providing examples or criteria for when edge embeddings are advantageous would enhance its applicability.”

“Providing examples or criteria for when edge embeddings are advantageous” is exactly what our paper does ! Theorem 1 provides an example where edge embeddings are provably advantageous from a representational perspective. As discussed after Theorem 1, the intuition is that in a graph with high-degree “hub” nodes, these nodes may be a bottleneck to the flow of information for any node-based protocol, whereas they do not bottleneck edge-based protocols.

We complement this result with the observation that in graphs with low maximum degree (i.e. no “hub” nodes), there is no representational advantage (Proposition 3).

If the reviewer is asking for a complete characterization of which graphs or tasks are easier for edge-based protocols — we believe it is unlikely for a clean characterization to exist, given the connections between this problem and theoretically deep areas of research such as communication complexity.

3. “With more depths, node embedding can simulate edge embeddings. Would be good to see such experiments and memory consumption comparison”

We prove that with more memory, node embeddings can simulate edge embeddings (Proposition 3). With the same memory but much more depth, it is an open theoretical question whether node embeddings can simulate edge embeddings.

Our first synthetic experiment does address this question empirically: Table 2 shows that even if the node GNN is given 2x the depth, it cannot simulate a planted edge-based protocol (whereas the edge GNN does learn this planted protocol).

If the reviewer has a concrete experimental setup in mind that differs from this one, we would be happy to discuss it.