Affinity-Aware Graph Networks

Summary

This work proposes to incorporate affinity measures as features into message-passing networks (MPNNs) in order to enhance the expressivity without enlarging the computational cost notably. The authors introduce three examples of random-walk-based affinity measures, e.g., effective resistance, hitting, and commute times, and provide efficient computation and low-rank approximation for them. On multiple graph benchmarks, ranging from graph-level tasks to transductive node-classification on large-scale graphs, the proposed affinity measures can remarkably improve the performance of MPNNs and reach state-of-the-art performance among models without privileged information.

Strengths

1. According to my best knowledge, this work is the first to propose that incorporating affinity-based measures into MPNNs can improve the expressive power of MPNNs, going beyond the 1-WL algorithm. 2. This work also provides several techniques to improve the efficiency of the introduced affinity-based measures. 3. The authors show that MPNNs+affinity measures are strictly more powerful than the 1-WL algorithm via the example of regular graphs. 4. The empirical experiments demonstrate the effectiveness of the proposed methods on graph-level tasks and transductive node-level tasks. The experiment on large-scale graphs also shows the efficiency of the proposed technique.

Weaknesses

1. The paper does not have more throughout comparisons with other positional encoding enhanced graph neural networks, theoretically and empirically. For details, please see the question section. 2. The baselines in empirical comparisons seem to have different numbers of parameters compared to the proposed method. It will be better to have a more detailed explanation on the choices of hyperparameters.

Questions

(Loukas, 2020; Dwivedi et al., 2021) mention that encoding can enhance the ability of MPNNs to uniquely distinguish nodes and hence improve the expressive power of MPNNs. I am curious whether the affinity measures enhance MPNNs in a similar way. Or they can provide extra valuable information that non-affinity-based encoding can not provide. In other words, if there exists a non-affinity-based encoding able to distinguish isomorphic graphs as well as the proposed affinity measures, such as subgraph counting (Bouritsas et al., 2022), will incorporating the proposed affinity measures into MPNNs enjoy extra advantages over such an encoding? Whether graph-level tasks and node-level tasks have different conclusions regarding this? If possible, it would be perfect if you could provide more comparisons theoretically/empirically against several PE-enhanced MPNNs (Dwivedi et al., 2021; Zhang et al., 2021; Wang et al., 2022; Lim et al., 2022; Li et al., 2020; Bouritsas et al., 2022) and potentially the PE for Graph Transformers (Zhang et al., 2023; Ma et al., 2023). - Loukas, A. (2020). How hard is to distinguish graphs with graph neural networks? Adv. Neural Inf. Process. Syst. - Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. (2021). Graph Neural Networks with Learnable Structural and Positional Representations. Proc. Int. Conf. Learn. Representations. - Bouritsas, G., Frasca, F., Zafeiriou, S. P., & Bronstein, M. (2022). Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1–1. - Zhang, Z., Cui, P., Pei, J., Wang, X., & Zhu, W. (2021). Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs. IEEE Transactions on Knowledge and Data Engineering. - Wang, H., Yin, H., Zhang, M., & Li, P. (2022). Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. Proc. Int. Conf. Learn. Representations. - Lim, D., Robinson, J. D., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. (2022). Sign and Basis Invariant Networks for Spectral Graph Representation Learning. ICLR 2022 Workshop on Geometrical and Topological Representation Learning. - Li, P., Wang, Y., Wang, H., & Leskovec, J. (2020). Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. Adv. Neural Inf. Process. Syst. - Zhang, B., Luo, S., Wang, L., & He, D. (2023). Rethinking the Expressive Power of GNNs via Graph Biconnectivity. Proc. Int. Conf. Learn. Representations. - Ma, L., Lin, C., Lim, D., Romero-Soriano, A., K. Dokania, Coates, M., H.S. Torr, P., & Lim, S.-N. (2023). Graph Inductive Biases in Transformers without Message Passing. Proc. Int. Conf. Mach. Learn.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No limitations are provided.

Summary

The paper proposes a strategy to strengthen the node and edge features in order to enhance the expressiveness of a message passing neural network. In particular, the paper introduces a set of effective resistance (ER) features, including node-level resistive embedding, which further derives two edge-level affinity measures: hitting time and commuting time/effective resistance. Additionally, the paper employs Constructive Johnson-Lindenstrauss to randomly project resistive embeddings to a lower-dimensional space, which is utilized to expedite the computation of hitting time and commuting time. Finally, the paper present the empirical evaluations on the proposed ER features.

Strengths

1. The paper is well-written: the motivation is clearly presented, and most sections are straightforward to follow. 2. The fast approximation of computing hitting time and commuting time is novel. The dimensionality of resistive embedding is reduced without the requirement of specifying a set of anchor nodes. 3. The experiment on large graphs demonstrates that the computation cost of adding these features to MPNN is manageable.

Weaknesses

1. The paper would benefit from providing stronger evidence to support certain claims made throughout the text. Please refer to the "Questions" section for details.

Questions

1. I would like to seek clarification from the authors regarding the connection between "1-WL" and "standard GNN" in the context of node classification, as demonstrated in the paper to support the claim made by Theorem 3.6. The provided example gives me the impression that a "standard GNN" represents each node using a spanning tree rooted at the node of interest (referred to as a computation tree) and distinguishes nodes based on the isomorphism of these spanning trees. To facilitate readers' understanding of this concept, I kindly request the authors to provide a specific example of the computation tree that a standard GNN employs to represent a node. It would also be helpful if the authors could provide some justification or reference regarding the connection between the node representation learned by standard GNNs and the utilization of spanning trees. 2. By utilizing the initial node feature as the one-hot encoding of the node's index, denoted as $\textbf{h}_v^{(0)} = \textbf{e}_v$, and employing the forward function $\mathbf{H}^{(t+1)} = \mathbf{A}\mathbf{H}^{(t)}$, we can observe that after 4 layers, the node embeddings generated by the standard GNN successfully differentiate the 3 color categories. Specifically, if we define a score $s_v = <\textbf{h}_v^{(4)}, \textbf{e}_v>$, the value for nodes {1,2} is 15, for nodes {3,4,7,8} it is 17, and for nodes {5,6} it is 19. This observation contradicts the claim that "a standard GNN that is limited by the 1-WL test cannot distinguish any pair of nodes in a regular graph." Consequently, I have some follow-up questions based on this discrepancy. (1) What is the specific constraint on the input features to a standard GNN? (2) Will the benefit from resistive embedding become less evident as we increase the depth of an MPNN? 3. In Appendix D.2, a comparison is conducted between resistive embedding and shortest-path-distance embedding in terms of their ability to differentiate nodes within a cycle and the corresponding nodes in the path obtained by removing one edge from the cycle. The example effectively illustrates that node embeddings based on shortest-path-distance are insufficient in capturing the divergence that can be successfully captured by resistive embeddings. However, this raises a valid concern regarding real-life networks where edges may be lost due to noise. In such cases, will the strong ability of resistive embeddings to distinguish between graphs that are close in terms of edit distance potentially make them susceptible to overfitting the noise?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

This paper proposes to use affinity measures as additional features that can incorporate in common standard MPNNs and theoretically and empirically shows the improvement in expressiveness and performance in some datasets without loss of much scalability. The main contributions are listed below. 1. Generality. The proposed approach can be adopted in standard MPNNs. 2. Expressiveness. Incorporating the proposed features can make standard MPNNs more powerful than the 1-WL test. 3. Scalability. The affinity measures used in this paper are based on the random walk. By approximation, the features derived from the proposed measures can be incorporated with high scalability. 4. Performance. MPNNs equipped with the proposed additional features can make progress or even rank 1 in some datasets.

Strengths

1. This paper was inspired by effective resistances and proposed HT, ER and resistive embeddings all help common MPNNs in both performance and expressiveness. As a feature-based approach, it can adapt to many standard MPNNs and does not need to specify any anchor or target nodes to capture both distance and connectivity information using general-purpose node and edge features. 2. By Approximation and fast computation of Resistive Embeddings and HT, the proposed features can scale up to large graphs in time and space complexity. 3. The experimental results are impressive. With relatively low computation cost, the proposed method can have a competitive performance on small datasets and higher performance on homogeneous/heterogeneous citation networks. Further, the best performance achieved on PCQM4M-v1 is impressive. 4. Both theoretical proof and empirical evaluations are provided.

Weaknesses

1. The motivation needs to be clarified more clearly. What the main drawbacks of the existing approaches are and which the proposed one surmounts? It’s said that the proposed approach “without the need for specifying any anchor or target nodes” and the scalability problem is mentioned in the experiments section. However, the advantages should be clarified further and organized better since there are other feature-based works and other categories of works aiming at a similar goal. Some practical evaluation or comparison may help if possible. 2. To demonstrate the superiority and necessity of the proposed affinity feature-based approach, other similar approaches need to be compared. Similar to the proposed affinity-based features, approaches incorporating other additional features (e.g. Random features or other dedicated designed features), and other methods that can improve GNNs’ expressiveness (e.g. other 2 directions mentioned in Expressivity para in Sec. 2) should also be compared in scalability and performance. 3. Although by approximation, the computation of random embeddings can be done in near-linear time and can be scaled to a large dataset, it’s better to provide the actual runtime of the proposed and baseline methods. 4. Theorem 3.6 claims that MPNNs that make use of any one of the proposed features are strictly more powerful than the WL-1 test. However, the experiments for it are not enough. Experiments on ogbg-molhiv show that it outperforms substructure counts, but the reasons are not clear. Experiments on some (artificial) datasets (e.g. [1][2]) which are designed for testing expressiveness would be better. 5. More well-organized writing should be considered. The notations scattering in Sec. 3.1-3.3 bring some difficulty in reading. The different baselines, settings, and experimental results in each subsection in Sec. 5 are scattered, either in the tables or in the text, which may weaken the empirical demonstration effects of experiments and cause some confusion. Some nouns or notations are introduced but not explained clearly, such as ER scalar features, node or edge features used in experiments, e_v in Eq. (1), and random rotations. Introducing them in a centralized and unified manner may help.

Questions

1. It’s said in Sec. 5.4 that ER embedding dimension become impractically high and authors alter to use ER scalar features. What are the theoretical and empirical (experimental) differences between the two kinds of features? If ER scalar features in small graphs can make the same progress with ER embedding? If not, why? 2. Incorporating hitting time features, resistive embeddings, and effective resistance are all proven to be more powerful than 1-WL in Sec. 3.4. Why does using ER/HT in experiments have different results? Is there any suggestion about selecting which feature? 3. The performance of the proposed method does not surpass the DGN in Table 2 and does not show advantages when more layers are in Table 3. More explanations are expected although the proposed method shows advantages in other aspects. 4. How the proposed features help in heterogeneous networks may be interesting. Possible explanations are expected.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

1. As said in W3, the actual runtime in large graphs may be much higher than (scalable) baseline methods. 2. As said in Q2, experiments use different features (ER embedding/HT …), thus suggestion about selecting feature is needed. 3. When demonstrating the expressiveness of the proposed approach, experiments on some datasets tailored for evaluating expressive power are expected. For instance, one can synthesize a dataset containing instances indistinguishable by 1-WL(e.g. [1][2]) to see if the proposed approach can distinguish. [1] Sato R, Yamada M, Kashima H. Random features strengthen graph neural networks[C]//Proceedings of the 2021 SIAM international conference on data mining (SDM). Society for Industrial and Applied Mathematics, 2021: 333-341. [2] Abboud R, Ceylan I I, Grohe M, et al. The surprising power of graph neural networks with random node initialization[J]. arXiv preprint arXiv:2010.01179, 2020.

Summary

In this paper, the authors present MPNN using affinity measures as node and edge features. As the affinity measures, the authors propose effective resistance, hitting times, and resistive embeddings. The authors demonstrate the effectiveness of using the affinity measures through experiments on various datasets. Experimental results on large graph datasets prove the good scalability of the scheme.

Strengths

1. I considered the need for a comparison with shortest path distances (SPDs), however, the related description in Section D (in the supplementary material) is convincing. 2. The proposed scheme has low computational complexity and good scalability. 3. The paper is well-written and easy to understand.

Weaknesses

It appears that the setting for MPNN models used in the experiments is not fair. According to Table 6 in the supplementary material, the number of layers is set to 3 for all models. Do the authors consider this setting to be fair? Furthermore, the hidden size of each layer is set differently for each method. What is the basis for setting the hidden size for each method? For example, the hidden size for GAT is set to 64 while that for HT + ER (rand rot) is set to 512. minor comment - fom -> from (Line 112)

Questions

Q1. Do the authors think that the experiments with the current hyper-parameter setting are fair? Q2. Could the authors explain on what basis they set the hyper-parameters for each method? Q3. Is it possible to improve performance by adding the proposed features to DGN?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors do not describe the potential negative social impact of their work while present future work to develop the work.

Thank you!

Thank you! We appreciate your taking the time to read through our rebuttal and adjust your score upwards.

Rebuttal Acknowledgement

Thank you for the response. These comments substantially address my concerns.

Thank you for rebuttal

hank you for your feedback. I appreciate your consideration in including the discussions we've had in the final revisions of the paper. The paper presents an intriguing and engaging topic, and based on its quality, I highly recommend its acceptance. I also want to acknowledge that I have upgraded my score to 7. Best of luck!