Open Your Eyes: Vision Enhances Message Passing Neural Networks in Link Prediction

Thanks for your insightful reviews. Please note that all the new tables and figures mentioned here are put in https://anonymous.4open.science/r/GVN-CLap/README.md.

compares assigning the visualized node positions as node features. compares more standard node positional encoding (PE) mechanisms like Laplacian-based and distance-based ones.

As you adviced, we compared VSFs for nodes with 4 representative encoding mechanisms: 1) 2-d axis position of nodes in subgraph image, 2) Laplacian PE, 3) Distances to other nodes, and 4) Node degree (centrality encoding). These PEs were used as node features and decoded by 2-layer GCN+2-lyaer MLP for link prediction. The results in Table A show that VSFs outperform those PEs across datasets. Notably, directly encoding the 2-d axis is not effective enough, underscoring the importance of using a vision encoder for comprehensive structural information.

Why does the paper only consider link prediction tasks?

As the title indicates, this work focuses on link prediction within the context of MPNN because:

1. Link prediction is one of the cornerstone tasks in graph learning, with 1) long history, 2) significant applications, and 3) well-established experimental settings, making it vital and representative.
2. As a first exploratory work for incorporating vision to MPNN, we faced many factors to explore. For example, we have revealed the effects on style consistency, node coloring, node labeling, image scopes, feature integration strategies, node shapes, visualizer, and encoder, etc. Efforts on those findings cost 8 months. Therefore, multiple efforts on other tasks are impractical for this starting work given limited resource.

Moreover, we provide results in Table B, which demonstrate that the benefits of VSF are promising for the node classification task. We will study such extensions in future works.

Is there any reason to believe that the methods do not scale linearly with increasing batch size?

While logarithmic axis labels are utilized in Fig. 5, the time actually scales linearly to the batch size. A version of Fig 5 with linear axis labels is provided in Fig. A.

O(VE) should be exemplified. Welcome to analyzing the scalability on larger graphs by increasing the graph but not the batch size.

As you advised, we here supplement another scalability analysis on randomly generated Erdos-Renyi graphs (edge possibility=0.2) with increasing numbers of nodes from 100 to 5000. The total training times for training 200 epochs of GCN/GVN/E-GVN/SEAL are provided in Table C, and the contributions of O(VE) are explicitly listed in parentheses. As shown, the O(VE) time of GVN scale quadratically w.r.t. the node size, making it unavailable for large graphs. Instead, E-GVN can handle large graphs in time comparable to GCN and its O(VE) time scales nearly linearly.

Remark 4.1 is not really surprising, as the method also completely breaks permutation equivariance. GVs don’t usually yield unique and permutation equivariant representations.

We acknowledge that VSFs are not permutation-equivariant. However, our performances have surpassed many permutation-equivariant SF-MPNNs, demonstrating it is not fatal. We think that there are two main reasons: 1) the learnable VSFs can provide some specific information, e.g., important structure patterns/motifs (Remark 4.2). 2) Visualization also imports meaningful data augmentations on permutation (e.g., varying layouts), which forces the decoder model to become less sensitive to node order, potentially alleviating the drawbacks. We will add these discussions with revisions.

Should mention representative works about 1) general positional encoder, 2）GNNs with language embeddings, 3) graph drawing techniques and their optimization targets

Incorporating these discussions would definitely provide a more comprehensive background. We will add the discussion with them in the revision.

Matplotlib and igraph are not graph drawing frameworks. which doesn’t sufficiently describe what method was used

Matplotlib is used to render images, while networkx handles the structures. For Igraph, it provides a built-in graph visualization function. We will add details about them in the revision.

Is there any reason for selecting fdp for graphviz?

We choose fdp since a preliminary experiment comparing E-GVN with different layout algorithms on Cora (Table D) shows dot and fdp are better. Then we select fdp but not dot with reasons:

1. The force-based layout algorithm in fdp highlights node clustering, which is important for link prediction.
2. The tree-based layout in dot often results in a flattened image where the length exceeds the width, leading to a waste of the canvas.

Thanks again for your kind reviews. We sincerely hope we have addressed your concerns. If you have any question, please feel free to discuss with us.

Thank you for your insightful feedback.

I believe the authors should concentrate on the efficient GVN within the paper's architecture, as it can achieve better performance with NCNC and is significantly more efficient.

We sincerely appreciate your suggestion. We will focus on highlighting the efficient GVN in the revision.

Thanks again for recognizing our work.

Thanks for your insightful reviews. We here address your concerns point by point by merging and re-arranging relevant comments together:

The justification for why VSFs work better remains unclear, particularly in relation to existing expressive power analysis on models with SFs. The expressive power of models incorporating VSFs remains unclear, raises concerns about whether VSFs fundamentally improve representation power or simply introduce additional complexity without well-characterized benefits. How well does VDecoder perform alone?

First, we want to clarify that we did not claim VSFs always have stronger expressive power than other SFs, instead, our main claims for VSFs include

1. When used alone, VSFs benefits MPNNs. (Qualitatively demonstrated in Sec. 4.2, remarks 4.1-4.4).
2. When used together with other SFs, VSFs still provide remarkable orthogonal improvements. (Empirically demonstrated in Sec. 5).

Second, the proposed VSFs show different characteristics from classic SFs: 1) Classic link prediction SFs are typically derived from a single type of heuristic (e.g., SFs in SEAL only encode path distance, and SFs in BUDDY only focus on high-order common neighbors). However, VSFs encode the whole subgraph from images, containing massive and hybrid types of structural biases (as demonstrated in Fig.4). 2) With training on specific data, VSFs can vary to align the data requirements (Remark 4.4). Due to such characteristics, it is not easy to theoretically analyze the properties of VSFs precisely, and instead we conducted empirical demonstrations (Sec. 4.2 and 5) to describe properties of VSFs.

Lastly, we provide the standalone performance of 2-hop VSFs from ResNet50 encoder in the following table, which is a direct comparison for the representation quality of different SFs on the link prediction task. As illustrated, both individual link-based and node-based VSFs proposed in this paper outperform common neighbor SFs (i.e., CN, RA, and AA) and distance-based SFs (i.e., SPD) across various datasets, showing their superior structural representations beyond classic link prediction SFs.

Implementation details and hyperparameter settings for Sec 5’s results are missing, which makes reproducing results difficult. What are the vision model configurations and hyperparameters used in Table 3, Fig. 5 and other results. Explicitly provide a direct runtime comparison of preprocessing VSFs vs. classical SFs.

Thanks for your suggestion.

1. For hyperparameter configurations, please note that we have included all the hyperparameters for the main results in ./scripts/ path of our submitted code repo. We also give the ranges and optimization approaches of the significant hyperparameters in Sec 5.1. Therefore, we think that it is easy to reproduce our results. For the scalability analysis in Fig.5 and other experiments, the encoder is ResNet50 by default as mentioned in Sec. 4.2, and the default hop is 2.
2. Pre-processing time compared with SFs: We provide the time comparison on pre-processing VSFs and classic SFs on cora and ogbl-ddi testing in the following table. As shown, E-GVN can process VSFs in comparable time (in seconds) as classic SFs. For the dense graph like ogbl-ddi, it is even more efficient because the number of nodes are much smaller than that of links.

How does VSF handle hub nodes?

As exemplified in Fig 2, hub nodes are faithfully reflected in the image, revealing important cluster information.

Could the limited scope of visual perception cause nodes with non-isomorphic subgraphs to be mapped to non-distinguishable VSF?

No. For any hop k, non-isomorphic subgraphs are visualized as different images, resulting in distinguishable VSFs.

Would node-centered visualization degenerate to standard MPNNs for nodes with isomorphic subgraphs?

No. Though we eliminated node labels for structural clarity in visualization, we constructed the adjacent matrix with ascending order of node labels. This makes the visualization for isomorphic subgraphs different in layout if their relative label orderings are not permutation-equivariant.

Several relevant works are missing from the discussion in Sec 4.3 and 4.4.

Thanks for your supplement. Incorporating these discussions can definitely make the discussion more comprehensive. We will add discussions with them in the revision.

Sincerely wish we could address your concerns. For any further clarification, please feel free to let us know.

Thanks for your insightful reviews.

1. The discussion for RQ1 could be more convincing if some empirical study or theoretical analysis could be provided, instead of just intuition analysis.

Thanks for your advice. For RQ1, you can find the following supports for our discussion.

1. For subgraph visualization, we have provided empirical ablation for keeping style consistency in Table 4 of Sec 5.3, where Appendix H provides more details. Appendices I.1 and I.2 provide the empirical study on color and shape influences on nodes, particularly demonstrating the significance of highlighting the center nodes. Appendix I.3 provides an ablation study on node labeling strategies, noting that eliminating node labels performs the best.
2. For decoupled vision scope, we exemplified the actual cases in Figure 2 to support our claim about the vision scope and provide a sensitivity study in Table 5 of Sec 5.3. The theoretical analysis of decoupling subgraph scope from MPNN has been proven by [r1], and we omitted the details due to the page limit. We will add them in the revision.

[r1] Decoupling the depth and scope of graph neural networks. NeurIPS 2021

2. More link prediction methods that consider the graph sub-structures could be included in the comparison, such as Link-MOE ("Mixture of Link Predictors on Graphs").

As suggested, we have included Link-MOE in the comparison. Please note that Link-MOE integrates many MPNNs as experts to achieve good performance. Differently, as a plugin method outside MPNN, our proposed framework can be a supplement for enhancing individual MPNN to provide additional enhancements. Some results (i.e., Hits@50 for ogbl-collab, Hits@100 for ogbl-ppa) are shown in the following table, where we substitute the GCN and NCNC experts in Link-MOE as E-GVN(GCN) and E-GVN(NCNC). According to the results, we can see that incorporating VSFs can further enhance the performance of Link-MOE.