A Unified View on Neural Message Passing with Opinion Dynamics for Social Networks

Weaknesses-1. Structure of the Paper:

After introducing the intuition of social network and opinion dynamics and their connection to graphs and MPNNs in the Introduction, we introduced the key concepts in GNNs (Section 2) and two types of models in opinion dynamics, as well as the connection of their formulation with respect to MPNNs and their properties with respect to the oversmoothing issue (Section 3). Based on the two models’ inherent characteristics, we then proposed ODNet with its discrete and continuous update schemes and generalized it for updating hypergraphs (Section 4). In section 5, we designed extensive experiments to validate ODNet from various perspectives. Section 6 then demonstrates the ability of ODNet to simplify social networks with practical biological examples. Section 7 and 8 review related works and concludes the work.

Weaknesses-2. The Connection of the Network Simplification Task and Social Networks in General:

Co-occurrence networks of metabolic genes characterize the likelihood that different genes occur simultaneously within the same microbial species. The nature of this co-occurrence indicates that the genes have potential interconnections with each other, thus forming a complete set of metabolic pathways to maintain normal microbial activity. The co-occurrence networks of metabolic genes can be considered a general form of social networks due to their structural and functional similarities (Nature Reviews Microbiology 2012, 10, 538-550; BMC Genomics 2015, 16, S6; Microbiome 2020, 8, 82). Firstly, these networks reflect interactions and associations among genes, much like individuals forming relationships in a typical social network. In both cases, entities (genes or individuals) are connected and thus influence each other’s behavior or function. Secondly, typical social networks exhibit clusters of individuals with similar interests or affiliations, whereas metabolic gene networks showcase clusters of genes involved in specific metabolic pathways of functions. Lastly, both types of networks demonstrate resilience to perturbations, with redundancies in gene pathways ensuring functionality despite changes, akin to the way multiple connections in a social network can provide stability in the face of disruptions.

Due to the large number of genes and their connections, it becomes particularly difficult to find the key genes and their connections to functional genes. Therefore, we need to develop tools that assist in exploring the nature of social interactions of genes. The tool should demonstrate ways to efficiently gather extensive information about these networks and present them visually in an effective manner. As for our work, by comparing the network structures after simplification, we can clearly observe whether microorganisms that survive in two distinct environments (Mount Everest vs. Mariana Trench) have similar ways of organizing their metabolic pathways.

Weaknesses-3. MPNN combines Sociology:

We have conducted a thorough search and found the only similar previous work that also mentioned opinion dynamics and MPNN in their paper is SINN (Okawa et. al., 2022, KDD). While both papers proposed MPNN update schemes inspired by opinion dynamics, our work is largely different from theirs from multiple perspectives.

(1) We employed a potential term to avoid excessive attraction or repulsion from neighbors, so as to progressively update node representations. In this regard, our update rule prevents the energy from being continuously reduced, thus circumventing the oversmoothing issue.

(2) We established the bounded confidence with scaling factors. In particular, we leveraged different scaling factors when aggregating the neighborhood information that balances the attractive or repulsive forces.

(3) We further generalize our ODNet for hypergraph representation learning, which is a nontrivial extension from graph settings.

Questions-1. Comparison between MT&ME is an Architecture Simplification Task:

Due to the large number of genes and their complicated connections, analyzing metabolic gene networks is a difficult task. This difficulty makes it challenging to establish relationships between key genes and functional genes. Hence, there is a need to simplify the metabolic network.

In this study, through the simplification of the original gene networks of the Mariana Trench and Mount Everest from our previous work (Microbiome, 10(1): 215, 2022), we discovered that in the MT network, the key gene nitrous oxide reductase (nos) bridged the carbon (Alkane, Aromatic, Complex sugar, D-AA, and L-sugar) and nitrogen metabolism (N) (Fig. 4c). Conversely, in the ME network, the key genes involved in sulfate reduction (sat and aprA) connected the carbon and sulfur metabolism (S) (Fig. 4d). This indicates that in different environments, the same functional genes couple with different key genes.

It is notable that the analysis of genes and their connections in the metabolic network from different environments relies primarily on the simplified microbial social network architecture to facilitate meaningful comparison. While the genes are essentially the same in different networks, it requires the simplification algorithm to modify the network based solely on the initial connection of the graph.

Questions-2. Identification of Network Roles Through ODNet:

We drew Figure 4 with force-directed placement (Software - Practice and Experience, 21(11):1129-1164, 1991) based on the ODNet-learned edge weights. The algorithm allocates the nodes to concentrate nodes with connections while repulsing overly-closed nodes to avoid overlapping. Here, ODNet refines the edge weights of the network to influence the visualization from two perspectives. Firstly, it enhances connections among the genes in the same communities (i.e., genes exhibit similar functionality) and weakens or even cuts the connections between loosely connected genes. Consequently, genes within the same community will exhibit locally dense connections by ODNet and result in compact positioning in the visualization. Secondly, key genes that are connected to more genes with an above-average degree will be identified as the opinion leader or the bridge communicator and will be forced to be apart from other nodes in the visualization. Isolators, as implied by their names, are usually loosely connected to any other nodes with a small degree and small edge weights.

Weaknesses-1. Connection Between Opinion Dynamics and GNN:

Before further explaining our motivation for designing our message passing scheme with opinion dynamics, we would like to clarify some conceptual misunderstandings.

Firstly, GNNs are trained to update hidden representations for nodes, instead of making label predictions. GNN layers extract high-level hidden representations for nodes to better describe the local environment. The prediction is made by extra read-out layers, such as MLPs for static graphs and LSTMs for spatial-temporal graphs. Also, there are cases where the label prediction is not complimentary. For instance, GAE is a classic network that optimizes the hidden representation that reconstructs the graph and graph connections.

Also, we do not design ODNet based on the belief that GNNs have to do message passing following the way humans exchange opinions. Instead, we initially analyzed the similarity between opinion dynamics and existing MPNNs (e.g., GRAND) to demonstrate the inherent connections between these two different systems, i.e., the formulation of the two systems in describing the information exchange among agents (nodes). Based on this, we then leveraged the concept of bounded confidence and proposed a novel MPNN that (1) follows a simple yet effective construction, (2) is physically informed, and (3) alleviates the oversmoothing issue. We argued that a trivial combination of tools from different domains with fine-tuned ‘SOTA’ performance does not form an elegant research work. Instead, we aimed to propose a novel framework that is practically meaningful (e.g., can be applied for solving real-world scientific problems) with explainable (e.g., physically informed) constructions and certain theoretical guarantees (e.g., alleviating the oversmoothing issue).

Weaknesses-2. Additional Complexity in ODNet:

We recognize that leveraging graph sparsity is an important aspect of GNN. However, network expressivity is also important, and one should not sacrifice it only to pursue the sparse aggregation rule. In our case, we attached the potential term and the bounded confidence in eq. 6-7 to circumvent the oversmoothing issue. While it introduces extra complexity for the update rule in a single update step, it does not significantly increase the training time. For instance, on an A100 (single card), it costs ~50 seconds to complete the entire program for one iteration on Cora, whereas ~80 seconds is required for SINN (Okawa et. al., 2022, KDD).

Weaknesses-3. Baselines:

As the proposed ODNet follows a continuous update scheme, we selected representative discrete and continuous MPNN baseline methods for comparison, which were published between 2017-2022 with the majority released after 2020. As per the suggestion, we added two other baseline methods, SINN (2022, KDD) and ACMP (2023, ICLR). Both are continuous MPNN update schemes with neural ODE with public official PyTorch implementations. Due to the time limitation, we implemented the new baseline methods and reported their performance on the Citation networks. The reason is mainly that SINN requires additional time-consuming data processing for the DataLoader. We will update the rest results on node classification when they are available. Note that the existing methods do not apply to prediction tasks on hypergraphs as their pipeline requires additional non-trivial modifications.

W1:

We would like to clarify that this work is NOT ‘essentially just borrowing the idea of HK model to alleviate oversmoothing’, and we are not ambitiously aiming at bridging every single piece of MPNN and opinion dynamics (which is also impossible to be covered by a conference paper and there are not enough existing work to summarize at this stage). To this end, we will explain again the main workflow, in the hope of eliminating misunderstanding and confusion regarding the contribution and novelty of this research.

(1) We started from the FD model and GRAND, two representative models in opinion dynamics and continuous MPNN, to show their intrinsic connections. Based on this, we provided a new explanation from sociology on why FD-like models fail to address the oversmoothing problem.

(2) It naturally motivates us to refer to the ideas in sociology, e.g., bi-clustering, to design GNNs that alleviate the oversmoothing issue. In particular, we adopted the construction of bounded confidence and scaling factors from opinion dynamics to formulate our aggregation rule in its discrete and continuous form.

(3) We then generalized ODNet to analyze hypergraphs, a less-explored type of graphs with typical features exhibited in social networks (e.g., strong local connectivity). Note that such a generalization is non-trivial, and our method achieves superior performance over existing baselines.

(4) We made further theoretical analysis and discussions regarding the effectiveness of the collective behaviors in ODNet (Appendix A), which suggests potential future explorations in extending the idea in sociology and particle systems for designing and analyzing MPNNs.

W2:

We would like to clarify the two misunderstandings regarding the different understandings of a ‘practical meaningful’ method between us and the reviewer. Firstly, as we responded in the previous post, we believe our method is meaningful because it ‘can be applied for solving real-world scientific problems’. This statement has been validated in Section 6, where ODNet is able to simplify social networks. Secondly, we agree with the reviewer that scalability is one aspect that empowers certain types of GNNs in some applications and it is desired to have a computationally efficient tool to interpret large-volume data if the model performance does not hurt significantly and the scalability is the primary concern of the application. We argue that:

(1) expressivity is more important than graph sparsity especially when the trained graph is not crazily large, e.g., over billions of nodes.

(2) we do not completely sacrifice graph sparsity, as believed by the reviewer. As a matter of fact, ODNet simplifies the graph connection to delete unnecessary connections. For instance, in the gene co-occurrence network simplification task, the original ME network includes 2517 edges. After simplification, the remaining number of edges is 260 (with a cutoff of 0.05).

(3) In the context of node representation learning and social network simplification, large-volume graphs do not dominate real-world applications. The majority of the existing graph benchmark datasets contain fewer than a million nodes. For the simplification task, as it aims at understanding and explaining the relationship within the network, it is unrealistic to imagine the analysis being done on more than hundreds of thousands of nodes. Consequently, scalability is not the primary concern in our study.

Training times and depth:

As we did not use the term ‘training depth’ within the paper, we are uncertain if it refers to the number of network layers in the review. If this is the case: we do not fix the number of layers for any datasets. Instead, it adapts to the ODE solver. In terms of training time, for your reference, on Cora, the entire program takes ~50 seconds for ODNet for one repetition, whereas for SINN it takes ~80 seconds to complete one repetition (excluding the additional data processing time). For other baseline methods mentioned in Section 5.1-5.2 (and Appendix B), the benchmarks are directly loaded from PyG or follow pre-processing from previous work, and the results are sourced from previous studies.

Comparison with Okawa et al.’s work:

We have provided a detailed comparison with SINN (Okawa et. al., 2022) in the revised version. In summary, both papers proposed MPNN update schemes inspired by opinion dynamics. However, our work is different from theirs from three perspectives.

(1) We employed a potential term to avoid excessive attraction or repulsion from neighbors, so as to progressively update node representations. In this regard, our update rule prevents the energy from being continuously reduced, thus circumventing the oversmoothing issue.

(2) We established the bounded confidence with scaling factors. In particular, we leveraged different scaling factors when aggregating the neighborhood information that balances the attractive or repulsive forces.

(3) We further applied our ODNet for hypergraph representation learning, which is a nontrivial extension from graph settings. Empirically, we implemented SINN for node classification tasks based on its official implementation at (https://github.com/mayaokawa/opinion_dynamics). As it requires additional time-consuming data processing for the DataLoader, we were only able to perform the program on Citation networks within the limited time constraint. We will update the rest results on node classification when they are available. Also, it is notable that the current version of SINN does not apply to prediction tasks on hypergraphs, as its pipeline requires additional sophisticated modification.

Overall Contribution:

We hope the reviewer could agree with the overall contribution after our clarification. In summary:

(1) Although SINN (which is the only existing work that expands opinion dynamics to MPNNs to the best of our knowledge) designed MPNNs from the perspective of sociology, their method is significantly different from ours from methodology design, model functionality, and applications.

(2) We designed our experiments with extensive investigations to well-suited our main claims from different perspectives, which goes beyond simply node classification tasks on graph benchmark datasets.

(3) On top of baseline comparisons, we conducted further investigations to analyze why our model surpasses other baseline methods and how it achieves the target of network simplification with an empirical example in biology. We tried our best to comprehend theoretical and empirical analysis to support the novelty of the proposed method, demonstrating that it is practically meaningful with explainable constructions and certain theoretical guarantees.