Mixture of Weak and Strong Experts on Graphs
Authors: Hanqing Zeng
Hanjia Lyu
Diyi Hu
Yinglong Xia
Jiebo Luo
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Mixture of experts
Node classification
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: We propose a system to combine a weak MLP expert and a strong GNN expert, so that the powerful GNN model can be better optimized by decoupling the feature and structure modalities of the graph.

Abstract: Realistic graphs contain both (1) rich self-features of nodes and  (2) informative structures of neighborhoods, jointly handled by a Graph Neural Network (GNN) in the typical setup. We propose to decouple the two modalities by **M**ixture **o**f **w**eak and **st**rong experts (**Mowst**), where the weak expert is a light-weight Multi-layer Perceptron (MLP), and the strong expert is an off-the-shelf GNN. To adapt the experts' collaboration to different target nodes, we propose a "confidence" mechanism based on the dispersion of the weak expert's prediction logits. The strong expert is conditionally activated in the low-confidence region when either the node's classification relies on neighborhood information, or the weak expert has low model quality. We reveal interesting training dynamics by analyzing the influence of the confidence function on loss: our training algorithm encourages the specialization of each expert by effectively generating soft splitting of the graph. In addition, our "confidence" design imposes a desirable bias toward the strong expert to benefit from GNN's better generalization capability. Mowst is easy to optimize and achieves strong expressive power, with a computation cost comparable to a single GNN. Empirically, Mowst on 4 backbone GNN architectures show significant accuracy improvement on 6 standard node classification benchmarks, including both homophilous and heterophilous graphs (https://github.com/facebookresearch/mowst-gnn).

MIXTURE OF WEAK & STRONG EXPERTS ON GRAPHS
Hanqing Zeng
Hanjia Lyu"
Diyi Hu
Meta Al zengh@meta.com com
University of Rochester h1 yu5eur. rochester.edi
University of Southern California di diyihuluss huhhuuusc....... edu
Yinglong Xia
Jiebo Luo
Meta AI
University of Rochester
yxia@meta.com com
jlucêcs, rochester.edu
ABSTRACT
Realistic graphs contain both (1) rich self-features of nodes and (2) informative structures of neighborhoods, jointly handled by Graph Neural Network (GNN) in the typical setup. We propose decouple the two modalities by Mixture of weak and strong experts (Mowst), where the weak expert is light-weight Multi- layer Perceptron (MLP), and the strong expert is off-the-shelf GNN. To adapt the experts' collaboration to different target nodes, we propose "confidence" mechanism based on the dispersion the weak expert's prediction logits. The strong expert is conditionally activated in the low-confidence region when ei- ther the node's classification relies on neighborhood information, or the weak expert has low model quality. We reveal interesting training dynamics by ana- lyzing the influence of the confidence function on loss: our training algorithm encourages the specialization of each expert by effectively generating soft split- ting the graph. In addition, our "confidence" design imposes a desirable bias toward the strong expert benefit from GNN's better generalization capability. Mowst is easy to optimize and achieves strong expressive power, with a com- putation comparable
single GNN. Empirically, Mowst on 4 backbone GNN architectures show significant accuracy improvement on standard node classification benchmarks, including both homophilous and heterophilous graphs (https: ////////// com/ htt.://ccooooeeeerccccccccccccca wwwprr/wweerrrcc.otwtee.o.. http://wwtttttoo qnn).
Node Features
Node Features Neighbor Info
_
High Dispersion
Dispersion
noa TO
LogeVVaue Value
Confidence
Class
Class
Weak Expert (MLP)
Strong Expert (GNN)
Figure 1: Design overview of Mowst. The full system is composed of weak expert, a strong expert, and gating module. Diverse collaboration behaviors between the weak & strong experts emerge as result the gating module's coordination. The gating function, which can be either manually defined automatically learned (via additional compact MLP), calculates confidence score based the dispersion of only the weak expert's prediction logits. The confidence score varies across different target nodes depending the experts' relative strength on the local graph region. The score also directly controls how each expert's own logits are combined into the system's 's final prediction.
"Equal contribution

---

INTRODUCTION
A main challenge in graph learning lies in the data complexity. Realistic graphs contain non- homogeneous patterns such that different parts of the graph may exhibit different characteristics. For instance, locally homophilous and locally heterophilous regions may co-exist in one graph (Zhu et al. 2021): depending on local connectivity, graph signals may be mixed in diverse ways quantified by node-level assortativity (Suresh al. 202T): the number of graph convolution iterations should be
adjusted based on the topology of the neighborhood surrounding each target node (Zhang et al. (002))
However, many widely-used GNNs have fundamental limitation since they are designed based on
global properties of the graph. For instance, GCN (Kipf & Welling (016) and SGC (Wu et al. 2019)
perform signal smoothing using the full-graph Laplacian; GIN (Xu et al., 2019) simulates k- k-hop subgraph isomorphism test with the same l on all target nodes; GraphSAGE (Hamilton et al. 2017 and GAT (Veličković et al. 2018) aggregates features from k-hop neighbors, again with a global k. There is large potential to improve GNN's s capacity by diversified treatments on per-node basis.
Model capacity can be enhanced in several ways. One solution is to develop more advanced layer architectures for single GNN (Brody al. 2022 Zheng et al.) 2023 Joshi et al.. 2023), with the aim of enabling the model to automatically adapt to the unique characteristics of different target nodes. The other way is incorporate existing GNN models into a Mfxture-of-Fxpert (MoE) system
(Jacobs et al. 1991 Hu et al.) 2022). considering that MoE has effectively improved model capacity in many domains (Masoudnia
Ebrahimpour 2014 Du al. 2022: Lepikhin et al. 202T). In this study, we follow the MoE design philosophy, but take a step back to mix simple Multi-Layer Perceptron (MLP) with an off-the-shelf GNN an intentionally imbalanced combination unseen in traditional MoE. The main motivation is that MLP and GNN models can specialize to address the two most fundamental modalities in graphs: the feature of node itself, and the structure of its neighborhood. The MLP, though much weaker than the GNN, can play an important role in various cases. For instance, in homophilous regions where nodes features are similar, leveraging an MLP to focus on the rich features of individual nodes may be more effective than aggregating neighborhood features through a GNN layer. Conversely, in highly heterophilous regions, message passing could introduce noise, potentially causing more harm than good (Zhu et al., 2020a). The MLP expert can help "clean up" the dataset ($2.4) for the GNN, enabling the strong expert to focus on the more complicated nodes whose neighborhood structure provides useful information for the learning task.
An additional advantage of our "weak-strong" duo is that incorporating lightweight and easily optimized MLP helps mitigate the issues of computation costs and optimization difficulties commonly associated with traditional GNN or MoE systems. The lack of recursive neighborhood aggregation in an MLP not only makes its computation orders of magnitude cheaper than a GNN (Wu et al.
2019 Zhang et al.] (022) (even when optimized by sampling techniques (Zeng et al.) [221]] Shi et al. 2023 ). but it also completely avoids issues such as oversmoothing (Chen et al., 2020a Li et al.
2018) and oversquashing (Topping et al.] 2022 Alon & Yahav (021). While the traditional Moï
approaches can partially address the computation challenges by activating a subset of expert through various gating modules (Shazeer et al. 2017 Nie et al. (022). , sparse gating may further complicate optimization due to the introduction of discontinuities and intentional noise (Fedus et al., 2022).
Contributions. We propose Mixture of weak and strong experts (Mowst) graphs, where the MLP and GNN experts specialize in the feature and structure modalities. To encourage collaboration without complicated gating, we propose "confidence" mechanism control the contribution of each expert on a per-node basis (Figure T]. Unlike recent MoE designs where experts are fused in each layer (Du al. 2022 Lepikhin al. 2021). our experts execute independently through their last layer and are then mixed based on a confidence score calculated by the dispersion of the MLP's prediction logits. Our mixing mechanism has the following properties. First, since the confidence score solely depends on the MLP's output, the system is inherently biased. This means that under the same training loss, the predictions of the GNN are more likely to be accepted than those of the MLP (2.3). Such bias is desirable due to GNN's ' better generalization capability (Yang et al.) (202).. and the extent of bias can be learned via the confidence function. Second, our model-level (rather than layer-level) mixture simplifies the optimization and enhances explainability. Through theoretical analysis of the optimization behavior (2.3) we uncover various interesting collaboration modes between the two experts ($2.3). In the specialization mode, the system dynamically creates soft splitting of the graph nodes based on not only the nodes' characteristics but also the two experts' relative model quality. After splitting, the experts each specialize on the nodes they own. In the
2

---

denoising mode, the GNN expert dominates almost all nodes after convergence. The MLP overfits a small set of noisy nodes, effectively removing them from the GNN's training set and thus enabling the GNN to further fine-tune. The above advantages of Mowst, together with the theoretically high expressive power, come at the cost of minor computation overhead. In experiments, we extensively evaluate Mowst 4 types of GNN experts and 6 standard benchmarks covering both homophilous and heterophilous graphs. We show consistent accuracy improvements over state-of-the-ar baselines.
2
MOWST
Our discussion mainly focuses on the 2-expert Mowst while $2.7 shows the many-cxpert generaliza- tion. The key challenge is to design the mixture module considering the subtleties in the interactions between the imbalanced experts. On the one hand, the weak expert should be cautiously activated to avoid accuracy degradation. On the other hand, for nodes that can be truly mastered by the MLP, the weak expert should meaningfully contribute rather than being overshadowed by its stronger coun- terpart. $2. and $2.2 present the overall model. $2.3 and $2.4 analyze the collaboration behaviors. $2.5 discusses a variant of Mowst. analyzes the expressive power and computation cost.
Notations. Let G (V,8, X) ) be graph with node set and edge set 6. Each node e has a length- raw feature vector V.. The node features can be stacked X E BRII Denote v's ground truth label as yv E IR", where n is the number of classes. Denote the model prediction as Po E R".
2.1 MOWST
Algorithm 1 Mowst inference
Algorithm 2 Mowst training
Input: G (V, S, X): larget made 1:
Input: G (V. 8, X): training labels [v+ Tnitialize MLP GNN weights
Output: prediction of
6
Run the trained MLP oxpert prediction Pa. conlidence (p.) [0,
for round = uotil convergence do
GNN weights 0'
if random number (0, 1] has g C (p.) then
Update MLP weights to O,, by gradient descent on Lyuust
Predict e by MI.8 prediction P.
until convergence
else
Fix MLP weights 0,
Run the trained GNN expert om
Update GNN weights to O, by gradient descent on Tyguest until convergence
Predict by GNN's prodiction P-
end
end for
Inference. Algorithm is executed on an already-trained Mowst: on target u, the two experts each execute independently until they generate their own predictions Pe and p The mixture module either accepts Pe with probability C' (p.) (in which case we do not need execute the GNN at all), or discards Pa and uses P', as the final prediction. We use random number to simulate the MIP's activation probability C (p.), where C (p.) reflects how confident the MI.P is in its prediction. For instance, in binary classification, p. [0, 1]T and [0.5, 0.5] correspond to cases where the MLP is certain and uncertain about its prediction, with (px) being close to and O, respectively.
Training. The training should minimize the expected loss incurred in inference. In Algorithm the MLP incurs loss L (Pu, yv) with probability C (p.). Therefore, the overall loss on expectation is:
1
Luoett
E(C(p)) L (Pv, + (1 (p.)) |0]
(p',,
(1)
where Pe MLP (z=;; 0) and p'. GNN (x.; are the experts' predictions; 0 and 0' are the experts' model parameters. Tmouss is fully differentiable. While we could simultaneously optimize both experts via standard gradient descent, Algorithm[ [] "training turn" strategy: we fix one expert's parameters while optimizing the other. Training each expert in turn enables the experts to fully optimize themselves despite having different convergence behaviors due to the distinct model architectures. If C is learnable (.2). we update its parameters together with MLP's O.
We demonstrate via a simple case study how C moderates the two experts. Suppose at some point of training, the two experts have the same loss some In case 1, v's self features are sufficient for a good prediction. Then MLP can make p, more certain to lower its L (p.: yo) and increase C. The improved ML.P's loss then contributes more to Tozat than GNN's loss, thus
Intuition.
3

---

improving the overall LNowet. In case 2, v's self-features insufficient for further reducing MLP's loss. If the MLP makes Pe more certain, LNowet will deteriorate since an increased C will up-weight the contribution of worse L (Pu. yv). Otherwise, if the MLP acts in the reverse way to even degrade P. to random guess, I. (po yv) will be worse but C reduces to O, leaving TNoest unaffected even MLP is completely ignored. Case shows the bias of Mowst towards the GNN. However, as shown in case 1, the weak MLP can still play a significant role in nodes where it specializes effectively.
2.2 CONFIDENCE FUNCTION
In this subsection, we omit the subscript c. We formally categorize the class of the confidence function C. Consider the dingle-task, multi-class node classification problem, where n is the total number of classes. The input to C, p. belongs to the standard (n 1) )-simplex, Sn-1- i.e., Eisisn = 1 and p: 2 0, for i = I, ..... n. The output of falls between 0 and 1. Since reflects the certainty of the MLP's prediction,
decompose it C = G D, where denotes function composition. Here, D takes p as input and computes its dispersion, and G is a real-valued scalar function that maps the dispersion to confidence score. We define G and D as follows:
Definition 2.1. D S + R continuous and quasiconvex where D (1 0 and D (p) > O # A G: R + R is monotonically non-decreasing where G (0) = 0 and 0 < G (x) I. Va > O.
Proposition 2.2. C = G is quasiconvex.
D's definition states that only a prediction as bad as random guess receives 0 dispersion. Typical dispersion functions such as variance and negative entropy (see $D.1.I for definitions) belong to our class of D. Definition of G states that C' does not decrease with higher dispersion, which is reasonable as dispersion reflects the certainty of the prediction. In training, we can fix C by manually specifying both D and G. Alternatively, we can use a lightweight neural network (e.g., MLPP to learn G, where the input to G's MLP is the variance and negative entropy computed by 5
2.3 INTERACTION BETWEEN EXPERTS
When optimizing the training loss in Equation D. confidence C' will accumulate on some nodes while diminish on the others. Different distributions of C' correspond to different ways that the two experts can specialize and collaborate. In the following, we theoretically reveal three factors that control the value of C: the richness of self-feature information, the relative strength between the two experts, and the shape of the confidence function. The analysis on the experts' relative strength also reveals why the confidence-basee gate is biased. Since both C and the MLP loss are functions of the MLP prediction P.. we analyze the optimal p. that minimizes Liouet given a fixed GNN expert.
We set up the following optimization problem. We first divide the graph into disjoint node partitions, where nodes are in the same partition, M2, if and only they have identical self-features. For all nodes in M,, an MLP generates the same prediction denoted p., On the other hand, predictions for different partitionn, p, and pj (i j). can be arbitrarily different since an MLP is universal approximator (Hornik et al. 1989). The above properties convert Equation T from an optimization problem on (MIP's weights) ) to the one on {p:} (MLP's predictions). Consider nodes and in the same partition 1/1, If they have different labels yı * ye. no MLP can distinguish from v because the model lacks necessary neighborhood information. Let OG be the label distribution for M. i.e., Oiy E (0. 1) portion of nodes in M, have label j. and Σisien ass = We are now ready to derive the optimization problem as follows (see ŞE. for detailed steps):
Σ C(p)) (Io: (P:) m1:) (p:), 1sism
(tt} arg min Luovst = arg min (P.)
where La, (p:) [. Evem, L (p:. Yo) = Eisisn asj pig is the average MLP cross- entropy loss on nodes in Mi 14 M. Evem, L (p',, yy) is constant representing the average loss of the fixed GNN on the M2, nodes. We first summarize the properties of the loss as follows:
Proposition 2.3. Given as La. (p:) is convex function of P. with unique minimizer P a4. Let A (a) l.a (ax) be a function of az, A is concave function with unique maximizer a" 1.
4

---

(ax)) reflects the best possible performance of any MLP group M.1 For optimization problem
Theorem 2.4 quantifies the positions of the minimizer p; and the corresponding values of C. In case 3 (A (a)) (4). it is impossible to derive the exact Př without knowing the specific C. Therefore, we bound P. via "sub-level sets", which characterize the shapes of the loss and confidence functions. The last sentence of Theorem 2.4 the "tightness" of the bound.
Theorem 2.4. Suppose C = G D follows Defimition 2.1 Denote L': = =tp La. (p:) μú}
and L' = {p: La. (p:) ps} as the level set and strict sublevel set of La.. Denote @-K {p: C (p:) < ps) as the strict sublevel set of C. For a given a; # n 1,,, the minimizer pe satisfies:
If (axi) > pr, then p = 1 In and C (pt) = =0.
(a.)) pr. then pi = a; or p 11.
If (a.) pr then P3 -C where p' = C (a,) S CC() s G (maxp, p.eat: D P(Pi)) Further, there exists C such that p = 0z or P is sufficiently close to the level set Lo:
Proposition and Theorem jointly reveal factors affecting the MLP's contribution:
(1) Node feature information, ax; a₁ being closer to 111 implies that node features are less in- formative. Thus, confidence C will be lower since is harder reduce the MLP loss (Proposition
2.3; (2) Relative strength of experts, A (as) - p4: when the best possible MLP loss A (a:) cannot beat the GNN loss Jı, the MLP simply learns to give up the node group M; by generating random guess D = 1. Otherwise, the MLP will beat the GNN by learning P in some neighborhood of a; and obtaining positive C. The worse the GNN (i.e., larger (.),, the easier to obtain more dispersed D (i.e., enlarged ) ), and so the easier to achieve a larger C (i.e., increased max p, E er;; (p:)): maxp,
(3) Shape of the confidence function C: the sub-level set, e<v', constrains the range of p Addi- tionally, changing G's shape can push C (1)) towards the lower bound C (ox) or the upper bound
G mmx,, E. D (p.)). See DD1 for specific constructions and all proofs.
Point (1) is a data property. Point (2) leads diverse training dynamics ($2... Additionally, it reflects Mowst's 's inherent bias: a better GNN completely dominates the by 1
C ( 1, while better MLP only softly deprecates the GNN with C. (ft) S 1. Such bias is by design since only cautiously activate the weak expert: (a) A GNN is harder to optimize, so even if it temporarily performs badly during training, we still preserve certain weight 1 C hoping that later catches up with the MLP; (b) Since a GNN generalizes better on the test set (Yang et al. (023), we prefer it when the two experts have similar training performance. Point (3) justifies our learnable G in 2.2
2.4 TRAINING DYNAMICS
Specialization via data splitting. At the beginning of training (r 1, Algorithm 2 randomly initialized GNN approximately produces random guesses. Therefore, the MLP generates a distribution of C' over all training nodes purely based on the importance of self-features. Denote the subset of nodes with large 1 C as SANN- When it is the GNN's turn to update its model parameters, the GNN optimizes SaNN better due the larger loss weight. In the subsequent round (r 2), the MLP will struggle to outperform the GNN on many nodes, especially on SGNN. According to Theorem 2.4 the MLP will completely ignore such challenging nodes by setting C on SONN, thus simplitying the learning task for the weak expert. When MLP converges again, it specializes better on smaller subset of the training set, and the updated C distribution leads to a clearer data partition between the two experts. This iterative process continues, with each additional round of "in-turn training" reinforeing better specialization between the experts.
Denoised fine-tuning. This is a special case of "specialization" where nodes are dominantly assigned to the GNN expert. This case can happen for two reasons: (1) GNN is intrinsically stronger; (2) Our confidence-based gate favors the GNN ($2.3). Let SMLP and SaNN represent the sets of nodes assigned to the two experts when the training of Mowst has almost converged. According to the "relative strength" analysis in $2.3 SMLP may only constitute small set of outlier nodes with high level of structural noises. Such SMLP does not capture a meaningful distribution of the training data, and thus the MLP overfits when it optimizes on SMIP and ignores SENN- What's interesting that
5

---

now MLP's role switches from true specialization to noise filtering: Without the MLP, SMLP and SONN are both in the GNN's training set. While the size of SMLP is small, it may generate harmful gradients significant enough to make the GNN stuck in sub-optimum. With the MLP, SMLP is eliminated from the GNN's training set, enabling the GNN to further fine-tune on SaNN without the negative impact from SMIP- The improvement is not attributable to the MLP's performance SMLP, but rather the enhancement of the GNN's model quality after training on a cleaner dataset.
2.5 MowST"
We propose model variant, Mowst", by modifying the training loss of Mowst. In Equation I we compute the losses of the two experts separately, and then combine them via C to obtain the overall loss Lxowst- In Equation 3 we first use C' to combine the predictions of the two experts, Pe and p'. and then calculate single loss for I Note that the cross entropy loss, (:, y-) is convex, and the weighted sum based on C' also corresponds to a convex combination. We thus derive Proposition 2.5 which states that Mowst* is theoretically better than Mowst due to a lower loss.
I Houst
[(C((P)) Pe + (1 - C (p.)) P', yo)
[V/|
WEV
Proposition 2.5. For any function C with range in [0, 1]. Lyoust upper-bounde R
Since Mowst* only has a single loss term, we no longer employ the "in-turn training" of Algorithm Instead, we directly differentiate Moust and update the MLP, GNN, and the learnable C' altogether. During inference, Mowst* computes both experts and predicts via C (pt) Pv + (1 Cp.)) P'.
Mowst vs. Mowst". Both variants have similar collaboration behaviors (e.g., $2.4). primarily driven by the "weak-strong" design choice and the confidence mechanism. Regarding trade-offs, Mowst may be easier to optimize as its "in-turn training" fully decouples the experts' different model architectures, while Mowst* has a theoretically lower loss. Both variants can be practically useful.
2.6 EXPRESSIVE POWER AND COMPUTATION COMPLEXITY
We jointly analyze Mowst and Mowst* due to their commonalities. Since the MLP and GNN experts execute independently before being combined, it is intuitive that our system can express each expert alone by simply disabling the other expert. In the following theoretical results, the term "exxressive power" is used in accordance with its standard definition (Lu et al. [201]). which characterizes the neural network's 's ability approximate functions. The formal definition and proof are in $D.2 In Proposition 2.6 we construct specific G so that the confidence function acts as a binary gate between experts. Theorem (2. provides a stronger result on the GCN architecture (Kipf & Welling 2016): when neighbors are noisy (or even adversarial), their aggregation brings more harm than benefit. An MI.P is simple yet effective way to eliminate such neighbor noises. The proof share inherent connections with the empirically observed "denoising" behavior in $2.4
Proposition 2.6. Mowst t and Mowst" are at least as expressive as the MIP or GNN expert alone.
Theorem 2.7. Mowst GGN and Mowst" -GCN are more expressive than the GCN expert alone.
For computation complexity, we consider the average cost of predicting one node in inference. For sake of discussion, we consider the GCN architecture and assume that both experts have the same number of layers E and feature dimension f. In the worst case, both experts in Algorithm we can skip the strong expert with probability C). The cost of the GCN is lower bounded by 52 ff2 (f + be-1)), where by-1 is the average number of (E - (f-1)-hop neighbors. The cost of the MLP is (f2 f). On large graphs, the neighborhood size b can grow exponentially with f, so realistically, be- > l. This means the worst-case cost of Mowst or Mowst" is similar to that of a vanilla GCN. The conclusion still holds if we use an additional, lightweight MI.P to compute the confidence C' (since such an MLP only approximates a scalar function G, it is not expensive).
activated (as noted
2.7 MIXTURE OF PROGRESSIVELY STRONGER EXPERTS
Suppose we have a series of ls progressively stronger experts where expert i is stronger than ; if i (e.g., 3 experts consisting of MI.P, SGC (Wu et al. 2019) and GCN (Kipf & Welling 2016))

---

Mowst and Mowst" can be generalized following recursive formulation. Let L be the loss of expert on node v, L be the loss of a Mowst sub-system consisting of experts to k, and C₁: be the confidence of expert i computed by i's prediction
node v. Equation [ then generalizes to TMooust [o| Eeey 1 and 1 = C I. + (1 - C.) 12241-- During inference, similar to Algorithm 1 the strong expert will be activated only when all previous weaker experts are bypassed due to their low confidence. The case for Mowst* can be derived similarly. See $E.2 for the final form of Lmoztt Due to the recursive nature of adding new experts, all our analyses and observations in previous sections still hold. For instance, the expressive power is ensured as follows: Proposition 2.8. Mowst and Mows t" are at least as expressive as any expert alone.
3 EXPERIMENTS
Table I: Mowst outperforms baselines under the same number of layers and hidden dimension. Values with 't', 't' and 'tt' are from Hu et al. (2020), Lim et al. (022)) and Wang et al. (2023). For each graph, show the best and second best results, and absolute gains against the GNN counterparts (e.g., Mowst (*) (*) -GCN vs. GCN and SraphMoE-GCNT All results are averaged over 10 runs.
Flickr
ogba- produprodccts
ogbn aibiv
Penn94
pokec
twitch- ggamer
MLPP
46.93 +0.00
61.06* +0.08
55.507 4-0.33
73.61
40.40
62.37
400.02
60.92 4-0.07
GAT
52.47 20.14
OOM
71.58 10.17
81.531
10.55
71.771
16.18
59,891
1:4.22
GPR-GNN
53.23 #0.14
72,41
+0.04
71.10 +0.22
81,38
+0.16
78.83
+0.05
61.89
+0:29
AdaGCN
48.96 +0.08
69.06
+-0.04
58.45
+00.0
74.42
+-0.58
55.92
+-0.55
+:0.14 61.02
GCN
53,86 10.37
75.64t
10021
71.74" 1.0.29
82.17
10.04
76.01
1.0.49
62.42 1..53
GCN-skip
52.98 10.00
69.56 1.0.00
76.58
1.0.53
73.46
1.0.04
61.05 1:0.23
GruphMoE-GCN
53.03 #0.14
73,90
10.00
71.88
20.32
81.61
20.27
76.99
1:010
62.76 +0.22
54.62 +0.23
76.49 +0022
72.52 +0.07
83.19
+0.43
77.28 +:0.08
63.74 +:0.23
Mowst("))ao
(+0.76)
(+0.85)
(+0.64)
(+1.02)
(+0.29)
(+0.83)
GIN
53.71 #0.35
69.39 +0056
82.68 +00332
$3.37
4:2.15
61.76 #:0.00
55.48 1.0.32
71.43 1.0.2
84.56 1.0.31
76.11 1.0.39
64.32 1:0.34
(+1.77)
(42.04)
(+1.88)
(+22.74)
(+2.56)
GIN-skip
52.70 .10000
71.28 10.00
80.32 10.43
76.29 1.0.51
64,27 1.0.25
53.19 #0.31
71.79 4.0.23
81.20 4.0.5
79.70 4-0.33
64,91 4:0.22
Moust (*) -GiTN-sski
(+0.49)
(+0.51)
(+0.88)
(+3.41)
(+0.644)
GraphSAGE
53,51 =0.05
78.50t #0.14
71.49 +:0.77
76.75 #0.52
75.76
#:000
61.99 #:0330
GruphMoE-SAGE
52.16 20.13
77.79
10.00
71.19 20.15
77.04 20.35
76.67 10008
63.42 ::0
53:90 10.18
79,38
+0044
72.04 +0.24
79.07 +0.43
77.84 +0.04
64.38 +0.14
Moust (*) SSAGE
(+0.39)
(+0.88)
(+0.55)
(+2.03)
(+1.33)
(+1.05)
Setup. We evaluate Mowst (*) on a diverse set of benchmarks, including 3 homophilous graphs (Flickr (Zeng et al. 2020), ogbn-arxiv and produccso (Hu et al.] 20200) and 3 heterophilous graphs (Penn94, pokec and povitch-games (Lim et al. (02Tt). Following the literature, we perform node classification using the "accuracy" metric, with standard training/ / validation / test splits. The graph sizes range from 89K (Flickr) to 2.4M (ogbn-products) nodes. See also |
BASELINES. GCN (Kipf & Welling 2016), GraphSAGE (Hamilton al. 2017), GAT (Veličković ett al., 2018), and GIN (Xu et al.) 2019) are the most widely used GNN architectures achieving state-of of-the-rr accuracy on both homophilous (Hu al. 20200: Shi et al. 2023) and heterophilous
(Lim et al. 2021 Zhu et al. | Platonov et al. [023) graphs. In addition, GPR-GNN (Chien et al. 2021)) decouples the aggregation of neighbors within different hops, which effectively addresses the challenges on heterophilous graphs (Lim et al., 202T Platonov et al. 2023). We also compare with H,GCN (Zhu et al. (020b), the state-of the heterophilous GNN. Additionall,, we construct variants of the baselines by adding skip connections. Since GraphS AGE and H,GCN have already implemented skip connections in their original design, we thus only integrate skip connection into exclude these variants in our experiments on the
GCN and GIN. Due to resource constraints, largest ggbn-products graph. AdaGCN (Sun et al., (222I) and GraphMoE (Wang et al. 2023) are the state-of-the-ane ensemble and MoE models, both combining multiple GNNs.
HYPERPARAMETER literature (Hu et al., 2020 Zeng al.) (222) to set the number of layers as 3 and hidden dimension as 256, for all the baselines as well as for both the MLP and GNN experts of Mowst (ooss("). Regarding
For Flickr, ogbn-products and ogbn ogbn-arxiv, we follow the original
Penn94, pokec and twitch gaame,,,,,,r the authors of the original paper (Lim al. 2021) searched
7

---

for the best network architecture for each baseline independently. We follow the same protocol and hyperparameter space for our baselines and Mowst (*). We set an additional constraint on Mowst (*) to ensure fair comparison under similar computation costs: we first follow Lim et al. (202I) to determine the number of layers é and hidden dimension d of the vanilla GNN baselines, and then set the same l and d for the corresponding Mowst models. We use another MIP implement the learnable G' function ($..)) To reduce the size of the hyperparameter space, we set the number of layers and hidden dimension of G's MLP the same as those of the experts. See $A..2 for the hyperaarameter space (e.g., learning rate, dropout) and the grid-search methodology.
As shown in Table I Mowst consistently achieves significant accuracy improvement on all datasets. It also performs the best compared to all the other baselines. Moreover, we perform a comparison within two sub-groups, one with GCN as the backbone architecture including GCN, GraphMoF-GGN and Mowst with GraphSAGE, including GraphSAGE, GraphMoEESSGE and Mowst (onsst()=Sa -SA-E In both sub- groups, Mowst(*) achieves significant accuracy improvement over the second best. The accuracy improvement is consistently observed across both homophilous and heterophilous graphs, showing that the decoupling of the eef-features and neighbor structures, along with the denoising effect of the weak expert are generally beneficial.
Comparison with state-of-the-art.
and the other
Table 2 presents the experimental results for H₂GCN and Mowst on three heterophilous graphs. H₂GCN consistently outperforms the GCN baseline, demonstrating its ability to ef- fectively handle heterophilous neighborhoods. More importantly, when compared to H,GCN, Mowst -H2GCN achieves a significant and consistent improvement in accuracy across all three graphs. This shows that Mowst can sub- stantially enhance the performance of state-of-the-are heterophilous GNN like H₂GCN, with the help of a relatively simple expert such as a standard MLP.
Table 2: Comparison with HGGCN on heterophilous graphs.
Penn94
pokec
tuitch- ggnner
GCN
82.17 =0.01
76.01 20.09 19
62.42 2:053
Mowst (C)-ON
83.19 =0.43
77.28
10:08
63.74 10023
(+1.02)
(+0.29)
(+0.83)
H1,GCN
82.71 =0.67
80.89
#0.16
65.70 #:0.0
(ouat(")-HHpae (*)_HOO
83.39
=0.43
83.02
+0030
66.03 +0.16
(+4.68)
(+2.13)
(+0.33)
MLP expert skip connections. We compare with the "skip connection" variants of the GNN baselines. Since the accuracy of GIN-skip is close to that of Mowst -*I- on ogbn-arxiv, pokec and twwtch-gaaaeee we additionally run Mowst -GNN--kkii We observe that Mowst (t) consistently improves the accuracy of the GIN baseline by a large margin. Effects of skip connections on GCN, GraphSAGE, GIN and H,GCN clearly indicate that the MLP expert integrated by Mowst enhances model capacity in a unique and valuable way. The MI.P expert is not simply providing a shorteut to bypass certain neighborhood aggregation operations. Rather, it meaningfully interact with the GNN expert to let the full system personalize on each target node. Note that there is no need to run Mowst GGNN-skip since Mowst (*) (GN already outperforms GCN-skip significantly w.r.t. both accuracy and computation cost. The analysis on computation cost can be found in E.3.4
Mowst vs. Mowst". Using the GCN ar- chitecture as an example, we compare three model variants: (1) Mowst, (2) Mowst* and (3) Mowst (joint), a vanilla version of Mowst that performs training by simultaneously up- dating the two experts from the gradients of the whole LNoget (Equation D. Mowst (joint) does not follow the "in-turn training" strategy discussed in Algorithm? 2 From Table 3. we observe that Mowst (joint) achieves lower test accuracy all three graphs. Intuitively, since the two experts may have difference convergence rates, updating one expert with the other one fixed may help stabilize training and improve the overall convergence quality. Moreover, Mowst or Moust* may outperform the other variant depending on the property of the graph, which consistent with our trade-off analysis in $2.5 Mowst* can theoretically achieve a lower loss, while Mowst may be casier to optimize. In practice, both variants can be useful.
Table 3: Comparison of test set accuracy.
Flickr
pokec
twitcb-ganer
Mowat-GON (joint)
$3.47=00.6
76.62:0011
63.44:0.22
Maxst-GCI
54.62:00.3
77.1 77.12:0009
63.7440.23
Mowat'
53.94+00.77
77.28
63.59+0.11
Training dynamics. The two behaviors described in $2.4 may be observed on both Mowat and Moust". For demonstration, we visualize each behavior using one model variant. The empirical findings on "denoised tnnettnning" are provided in SC.2
8

---

Poodi
SPECIALIZATION VIA DATA SPLITTING. We track the evolution of the confidence score C during Mowst*-GCH training. In Figure for each bench- mark, we plot C's distribution corresponding to dif- ferent model snapshots. The distribution the upper side corresponds to the earlier stage of training, while the distribution on the lower side reflects the weighting between the two experts after convergence. In each distribution, the height shows the percentage of nodes assigned with such C. On Penn94, the GNN dominates initially. The MLP gradually learns to specialize on a significant portion of the data. Eventually, the whole graph is clearly split between the two experts, indicated by the two large peaks around 0 and 0.8 (corresponding to nodes assigned to GNN and MLP, respectively). For pokec, the specialization is not so strong. When training progresses, the MLP becomes less confident when the GNN is optimized better- nodes initially having larger C' gradually reduce C' to form a peak at around 0.2. For different graphs, the two experts will adapt their extent of collaboration by minimizing the Sefiidenne-wiighte loss.
Figure 2: Evolution of the C distribution.
4 RELATED WORK
Our work is closely related to Mixture-of- Experts, model ensemble methods on graphs, as well as the decoupling models for feature and structure information. Please refer to $B for further discussion.
Mixture-of-Expert.. MoE can effectively increase model capacity (Masoudnia & Ebrahimpour 2014; Yuksel et al. 2012). The key idea is to localize specialize different expert models to different partitions of the data. Typically, experts have comparable strengths. Thus, the numerous gating functions in the literature have a symmetric form w.r.t. all experts without biasing towards a specific one (e.g., variants of softmax (Jordan & Jacobs 1994 Shazeer al. 2017 Puigcerver et al. (023) In comparison, Mowst deliberately breaks the balance among experts via a biased gating. Another concern in MoE is the increased computation cost. Even though efficient dense gating designs exist (Nie et al. 2022). sparse gating is still the most common technique to save computation by conditionally deactivating some experts. However, it is widely observed that such sparsity causes training instability (Fedus et al.] 2022; Shazeer et al. 2017
Puigcerver et al. [2023). Under our confidence-based gating, Mowst is both easy to train 2.4 and computationally efficient ($2.6). Finally, many recent designs incorporate MoË in each layer of a large model (Riquelme et al. 2021
Du al. 2022 Lepikhin et al. 202T), whereas Mowst mixes only the output layers. We fully decouple the experts with imbalanced strengths in consideration of their different training dynamics.
MoE model ensemble on graphs. GraphDIVE (Hu al. 2022) proposes mixture of multi- view experts to address the class-imbalance issue in graph classification. GraphMoE (Wang et al.) 2023) introduces mixing multiple GNN experts via the top-K sparse gating (Shazeer al. 2017). Zhou & Luo| (2019) explore a similar idea of mixing multiple GNNs with existing gating functions.
AdaGCN (Sun et al. (02I] proposes a model ensemble technique for GNNs, based on the classic AdaBoost algorithm (Freund et al. 1999). In addition, AM-GCN (Wang et al.) 2020b) performs graph convolution on the decoupled topological and feature graphs to learn multi-channel information.
CONCLUSION
In this study, we introduce a novel mixture-of-experts design to combine a weak MLP expert with a strong GNN expert to effectively decouple the self-feature and neighbor structure modalities on graphs. The "weak-strong" collaboration emerges under a gating mechanism based on the weak expert's prediction confidence. We theoretically and empirically demonstrate intriguing training dynamics that evolve based on the properties the graph and the relative strengths of the experts. We show significant accuracy improvement over state-of-the-arr methods across both homophilous and heterophilous graphs. Future work will focus on a comprehensive evaluation of the generalized Mowst framework, which progressively mixes stronger experts, outlined in $2.7 Additionally, exploring whether the wreak-strong" combination can serve as a general MoE design paradigm with benefits extending beyond graph learning is an interesting direction for further research.

---

ACKNOWLEDGMENTS
We are grateful to Jingyang Lin, Dr. Wei Zhu, and Dr. Wei Xiong for their constructive suggestions. Luo was supported in part by NSF Award #2238208.
REFERENCES
Sami Abu-El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard. Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg. and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning. pp. 21-29. PMLR, 2019.
Akshay Agrawal and Stephen Boyd. Disciplined quasiconvex programming. Optimization Letters, 14(7):1643-1657, Oct 2020. ISSN 1862-4480. doi: 10. 10.1007/s1 15000/0111190000-555556 URLhttpss
//doi.oog/10.10000
020 01561-8
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL htttaaa:/oppeeriiiie.e
net / Eorum? id=1 80CPhoCVH2
Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Convex analysis and optimization, volume 1. Athena Scientific, 2003.
S. Boyd and L. Vandenherghe. Convex Optimization. Cambridge University Press, 2004. ISBN 177340079 URL http::t//tooosssssttt /ttp/o/ks..oooleeeccoooooo////o/
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- tional Conference on Learning Representations, 2022. URL
net/
Forum??_==P2xiimsxXCC
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Arlificial Intelligence, 34(04):3438-344, Apr. 2020a. doi:
5747. UtLhttpss: //ojss aaai http:///a..aa.aa.aaaaaaaaaaaaat/
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018. 2018 URL
.nt forum https: wtt.:n/ooooolllleettttttttttt.e.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference machine learning, pp. 1725-1735. PMLR, 2020b.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL
https://oppereviae
net wwwp:/eeeeffotioooeeeeoo Eorum?2d-n6117fLxx2
Nan Du, Yanping Huang, Andrew M Dai, Simon Tong, Dmitry Lepikhin, Yuanzhong Xu, Maxim Krikun, Yanqi Zhou, Adams Wei Yu, Orhan Firat, Barret Zoph. Liam Fedus, Maarten P Bosma, Zongwei Zhou, Tao Wang, Emma Wang. Kellie Webster, Marie Pellat, Kevin Robinson, Kathleen Meier-Hellstern, Toju Duke, Lucas Dixon, Kun Zhang, Quoc Le, Yonghui Wu, Zhifeng Chen, and Claire Cui. GLaM: Efficient scaling of language models with mixture-of-experts. In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning. volume 162 of Proceedings of Machine Learning Research, pp. 5547-5569. PMLR, 17-23 Jul 2022. URL htttss://proee
mlr .press /aiess/viii du22c.duu2c... html
William Fedus, Jeff Dean, and Barret Zoph. A review of sparse expert models deep learning. arXiv preprint arXiv:2209.00 0/667, 2022.
10

---

Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 3294 ht.ml
3304. PMLR, 2021. URL httpthttp:::/ceeeeee
www.mng........o..m...........mm mlr wtt.lleeeeeee///e/eeeeeeeeee
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11198, 2020.
Yoav Freund, Robert Schapire, and Naoki Abe. A short introduction to boosting. Journal-Ja Journal-Japansse Society For Artificial Intelligence, 14(771-780)1611, 1999.
Johannes Gasteiger, Chendi Qian, and Stephan Günnemann. Influence-based mini-batching for graph neural networks. In Bastian Rieck and Razvan Pascanu (eds.), Proceedings of the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp. 9:1-9:119..... PMLR, 09-12 Dec 2022. URL htt.ps:/pproceedings www.innnsmm..rrm..mmmm gasteiger222.neet
http:p/eeeddnggg..r...rreee//// press/v198/
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In Proceedings of the AAAI conference on artificial intelligence, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, volume 30, 2017. URL
files/ pppper///1r File/ File://sawebsss3aacoooooaaaaaaae PappeeeaapPppp.ppopoo
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
Fenyu Hu, Liping Wang, Qiang Liu, Shu Wu, Liang Wang, and Tieniu Tan. Graphdive: Graph classification by mixture of diverse experts. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2080-2086. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10. (0.244633jjcai.22222 2022//28.. URL https::/doi.....o org 10. 24963/ /099/////ca...... 2022/ 288 Main Track.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 10-188-22 11-22133, 2020.
Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton. Adaptive mixtures of local experts. Neural computation, 3(1):79-87, 1991.
JoramSoch. Proof: Concavity of the Shannon entropy. httpss://stapprofboookkk tithh io/P/ent conc 2020. Accessed: 2023-05-15.
Michael I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm. Neural computation, 6(2):181-211) 1994.
Chaitanya K Joshi, Cristian Bodnar, Simon V Mathis, Taco Cohen, and Pietro Lio. On the expressive power of geometric graph neural networks. arXiv preprint arXiv:2301.09.0 2023.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint OrXiv:1412.6998 2014.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1ee.::1000000 0090000290,...... 2016.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang. Maxim Krikun, Noam Shazeer, and Zhifeng Chen. (GS haadd: Scaling giant models with condi- tional computation and automatic sharding. In International Conference on Learning Representa- tions, 2021. URL https: /ttp::/://eeeeeeeeeeeeee /tt/ http///rrmmm.ddpeeeeeettxtt
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.

---

Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- superviiee learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on homooooppisous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Zhou Lu, Hongming Pu, Feicheng Wang. Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17. pp. 6232-6240, Red Hook, NY, USA, 2017.
Curran Associates Inc. ISBN 9781510860964.
Hanjia Lyu and Jiebo Luo. Understanding political polarization via jointly modeling users, con- nections and multimodal contents on heterogeneous graphs. In MM '22: The 30th ACM In- ternational Conference on Multimedia, Lisboa, Portugal, October 10 14, 2022, 2022. URL
3547899
Saeed Masoudnia and Reza Ebrahimpour. Mixture of experts: a literature survey. Artificial Intelli- gence Review, 42:275-290 293, 2014.
James Murphy. Topological proofs of the extreme and intermediate value theorems. Chicago: University of Chicago, 2008.
Xiaonan Nie, Shijie Cao, Xupeng Miao, Lingxiao Ma, Jilong Xue, Youshan Miao, Zichao Yang. Zhi Yang, and Bin CUI. Dense-to-sparse gate for mixture-of-experts, 2022. URL |
//openreview iew. nwt. net/forum?ide 4D8 stt
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023. URL https
//openreview.o net.iiewwwweeeeeeeeeee.ee..eeeee (rpperreveeeennetfffooomooddd..d ott.:/oormm.......oooo
Joan Puigcerver, Carlos Riquelme, Basil Mustafa, and Neil Houlsby. From sparse to soft mixtures of experts. arXiv preprint ar..v:2308..009 2023.
Carlos Riquelme, Joan Puigcerver, Basil Mustafa, Maxim Neumann, Rodolphe Jenatton, André Susano Pinto, Daniel Keysers, and Neil Houlsby. Scaling vision with sparse mixture of experts. 2021.
Advances in Neural Information Processing Systems,
Rik Sarkar and Benedek Rózemberezki. Twitch gamers: dataset for evaluating proximity preserving and structural role-based node embeddings. In Workshop on Graph Learning Benchmarks@ @ The TheWebConf 2021, 2021.
Noam Shazeer, Azalia Mirhoseini Krzysztof Maziarz*, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gatee mixture-of-experts layer. In International Conference on Learning Representations, 2017. |RI http:ttts///peereeeee
net/ peet/fosee /tt/://ormmmudeieeee Bdddddd
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference on Learning Representations, 2023.
Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Adange Adaboosting graph convolutional networks into deep models. In International Conference on Learning Representations, 2021. URL https?
net
1M
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp- 1541-1551, 2021.
12

---

Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference Learning Representations, 2022. BtRL:htt:://pppto httpp:///pperrroo....tteeeeeeeee
700m7mRj A
Amanda L Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks. Physica A: Statistical Mechanics and its Applications, 391(16):4165-11 4180, 2012.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
net/ wwt.//oormmmiieooemm fo iCC
Haotao Wang, Ziyu Jiang, Yan Han, and Zhangyang Wang. Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling, 2023.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chich-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1): 396-413, 2020a.
Xiao Wang, Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. Am-gen: Adaptive multi- channel graph convolutional networks. In Proceedings of the 26th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining, KDD '20. pp. 1243-1253, New York, NY. USA. 2020b. Association for Computing Machinery. ISBN 978 1450379979
doi: 10.1145/
3394486.3403177. URL https: http:/ooo.ooo.ooo 10. 1145 5 34448444466664 3403177
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https //openreview. net feret/forump ffo.omrrdmddrraaaiiir A5Km
Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging GNNs and MLPs. In The Eleventh International Confer- ence on Learning Representations, 2023. URL Ttetps::/openreeiiss net htt//formm?? ?id=
dgnnWWomZZ16
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 974-983, New York, NY, USA, 2018. Association for Computing Machinery. doi: 10.1145/3211881992119999 3219 98198815 .. 3219890
ISBN 9781450355520.
URLlttts:://aoi org/20.1145/
Seniha Esen Yuksel, Joseph N Wilson, and Paul Gader. Twenty years of mixture of experts. IEEE transactions on neural networks and learning systems, 2377:1177- 2012.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. htt.:htttt///ppeeeeeeeeee
wtt.ieew.eeeeeeeeeeeeeeeeeeeeeee wwt. wttp:/ooourmmmmmeeeppee
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL id= IY3 4psXuf
ew. net./ forum??
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old MLPs new tricks via distillation. In International Conference on Learning Representations, 2022. C5H_WPPp_SHWWWWWW
URL htI.httss: http::::////peeeevviiie www.::..eeeefotrtreeee (aaprrummid=4pp__500
13

---

Wentao Zhang, Mingyu Yang, Zeang Sheng, Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang. and Bin CUL Node dependent local smoothing for scalable graph learning. In A. Beygelzimer, Y. Dauphin, P. Liang. and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
ew. met/foourm daekka
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. CoRR, abs/2110.03753, 2021. URL https://arxiv.ozg/
abs Noo/2210.0377.
Yizhen Zheng, He Zhang, Vincent Lee, Yu Zheng. Xiao Wang, and Shirui Pan. Finding the missing- half: Graph complementary learning for homophily-prone and heterophily-pronn graphs. arXiv preprint (txXfi:230600660000 2023.
Xuanyu Zhou and Yuanhang Luo. Explore mixture of experts in graph neural networks, 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020a.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 7793-7804. Curran Associates, Inc., 2020b. URL https:: httppp://prroeeeiinggg.nnn neurips orpp http://epppp.c/pppeeeaeeae/////a fit.ffs/sppppae/220011
Jiong Zhu, Ryan Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 11168 11176, 2021.
14

---

Table of Contents (Appendix)
More Details on Experiments
16
Dataset description statistics
16
A.2
Hyperparameters
17
A.3
Implementation details
17
A.4
Pretraining
17
A.5
Criteria for lair comparison
17
A.6
Further discussion on the comparison with the late-of-theearr on heterophilous graphs
18
A.7 7
Further discussion the comparisons with GIN & skip connection saaseettooo-bbedd GNNs
19
Extended Related Work
20
Additional Experiments
20
C.1
Alternative choice for weak strong experts
20
C.I.I ML.P as shallow GNN
20
Results on mixture of shallow-deep GCNs
Denoised fine-tuning
22
Proof and Derivation
23
D.I Proofs related to model optimization
23
D.I.1 Proof of Proposition 2.2
23
D.1.2 Proof of Proposition 2.3
23
D.I 1.3
Proofs related to Theorem
24
D.1.4
Proof of Proposition 2.5
30
D.2
Proofs related to expressive power
31
D.2.1
Proof of Proposition 2.6
31
D.2.2
Proof of Theorem
32
D.2.3
Proof of Proposition 2.8
33
Additional Algorithmic Details
34
Derivation of optimization problem
34
Extending to more than two experts
................................
34
Calculation of computation
................................
35
E.3.1
Setup
35
E33.2
Computation cost of MLP
36
E.3.3
Computation cost of GNN
36
E.3.4
Computation cost of GNN with skip connection vs. GNN with MLP expert
37
E.3.5
Scalable GNN techniques
38
15

---

A Study on "Failure Cases"
38
What are the two typical "failure cases"
38
22 How does Mowst address the "failure cases")
39
Design Considerations
40
G.1
Order of experts: GNP-GNN GNN-MLP
40
G.2
Non-confidence- gating
40
H
Limitations & Broader Impact
40
Limitations
40
H.2
Broader impact
41
A MORE DETAILS ON EXPERIMENTS
A.1 DATASET DESCRIPTION & STATISTICS
Table provides summary of the basic statistics for the six benchmark graphs. The Flickr dataset is originally introduced in Zeng et al. (2020), while ogbn-products and ogbn-arxiv are first proposed Hu al. (2020). The Penn94, pokec, and twitch gamer datasets are originally proposed in Lim et al. (2021). A brief overview of the dataset construction is as follows:
Table 4: Statisties of the datasets.
# nodes
# edges # classes
node features
Flickr
89,250
899,756
7
500
ogbn-produee
2,449,029
61,859,140
47
100
ogbn-arxiv
169,343
2,332,486
40
128
Penn94 1,632,803
41,554
1,362,229
2
5
pokec
30,622,564
2
65
twitch-gamer
164,114
6,797,557
2
Flickr, proposed by Zeng et al. 2020), is graph where each node represents image uploaded to Flickr. An undirected edge is drawn between two nodes if the corresponding images share common properties, such as the same geographic location, same gallery, or were commented on by the same user. The node features are si0-eiimail bag-of- -oodd representations of the images.
ogbn-arxiv, paper citation network curated by Hu al. (2020), consists nodes representing arXiv papers and directed edges indicating citation relationships. The 128-dimensional node features embeddings of words in the paper's title and abstract, with embeddings
are derived by averaging generated by word2vec model trained on the MAG corpus (Wang et al. (020a)).
ogbn-products, also curated by Hu al. (2020), represents an Amazon product co-purchasing network. Each node corresponds to Amazon product, and edges between nodes indicate that the two products are frequently purchased together. The node features are 100-dimensional bag-of-words vectors of the product descriptions.
Penn94 (Lim et al. 2021 Traud et al., 2012) is a Facebook 100 network from 2005 representing friendship network of university students. Each node represents student, with node features including major, second major/minor, dorm/house, year, and high school.
pokec (Lim et al. 2021 Leskovec & Krev] 2014) is the friendship graph of Slovak online social network. Nodes represent users, and edges represent directed friendship relations. Node features include profile information such as geographical region, registration time, and age.
twitch-gaate gamer (Lim et al. 2021 Sarkar & Rózemberezki 2021) is a connected undirected graph representing relationships between accounts the streaming platform Twitch. Each node represents
16

---

Twitch user, and edge indicates mutual followers. Node features include the number of views, creation and update dates, language, lifetime, and whether the account is dead.
A.2 HYPERPARAMETERS
We perform grid search within the entire hyperparameter space defined as follows. Note that for GPR-GNN (Chien et al. 2021) and AdaGCN (Sun et al. 2021). we use the same grid search as reported in their original papers.
MLP. GCN, GCN-skip, GraphSAGE, GAT, GIN, GIN-skip: learning rate Ir E (.1,.01. .001)
for all graphs. For all the homophilous graphs, the dropout ratio searched {.1, 22 3, .4. .5.
hidden dimension is set 256 and the number of layers is according to Hu et al. (2020). For
the heterophilous graphs, we follow the same hyperparameter space as Lim et al. (2021).
GPR-GNN:
05, .002), a E (-1,22,5,..9)
hidden dimension
(16,32, 64, 128, 256).
AdaGCN: |r E {.01, )0.1) number of layers E {5, 10). dropout ratio E {.0,.5).
GraphMoE: Ir E {.1, .01, .001), dropout ratio E {.1, .3, .4, .5. number of experts E {2,8).
H₂GCN: Ir {.01, .001}. dropout ratio (.1,.3..5)
Mowst and Mowst*: The learning rate and dropout ratio of the MLP expert and the GNN expert
are kept the same. The girds for them are Ir {-1, .01)). dropout ratio E (.1, 2, 3, .,, .5.. As for the gating module, we also conduct grid search to find the optimal combination of the learning rate and dropout ratio. The grid for them are Ir E {.1, 000, dropout ratio E {.1, 2, 3, .3..
A.3 IMPLEMENTATION DETAILS
The implementations for Mowst and the GNN baselines are built using PyTorch and the PyTorch Geometric library. The code for T AdaGCN and H₂GCN are sourced from the official repositories associated with their respective original papers. The GPR-GNN implementation is adapted from the repository provided by Lim et al. (202I). ). All models, including our models and the baselines, are trained NVIDIA A100 GPUs with 80GB of memory. Training is conducted using full-batch gradient descent with the Adam optimizer (Kingma & Ba 2014), without resorting neighborhood subgraph sampling techniques.
A.4 PRETRAINING
In our experiments, we find that pretraining the individual experts before the training process of Mowst (as described in Algorithm(2) ( can also improve the optimization. There are four pretraining scenarios for Mowst: pretraining only the weak expert, pretraining only the strong expert, pretraining both experts, and not pretraining either expert.
A.5 CRITERIA FOR FAIR COMPARISON
For fair experimental comparison between Mowst and its corresponding vanilla GNN baseline (e.g.. Mowst-GCN and GCN), two potential criteria can be considered:
Model size: Mowst and its corresponding vanilla GNN baseline should have the same number of parameters.
Computation cost: Mowst and its corresponding vanilla GNN baseline should have similar computation cost.
The above two criteria may not be simultaneously satisfied. Consider a scenario where both the ML.P and GNN experts in Mowst have the same number of layers and hidden dimensions f. If the
http:://giithbb.com/m/mmmm
17

---

ON vanilla GNN baseline is configured to have architecture identical to Mowst's GNN expert, then Mowst will have more model parameters due to the additional MLP expert. However, Mowst will have computation cost comparable to that of the vanilla GNN baseline (detailed derivation provided in F.3.4. In this case, the "computation cost" criterion is met, but the "model size" criterion is not.
Alternatively, we can enhance the vanilla GNN baseline by adding skip connection to each layer, where the skip connection performs a linear transformation with an f x f weight matrix. In essence, this approach constructs the baseline by integrating each layer of the MLP expert with each layer of the GNN. As a result, the modified GNN and Mowst have the same number of parameters. However, this configuration violates the "computation cost" criterion. As detailed in $E.3.4, the computation cost of GNN with a skip connection is significantly higher than that of the original GNN without a skip connection, and therefore also higher than that of Mowst. Thus, the "model size" criterion is met, but the "computation cost" criterion is not.
Given that no setting can be perfectly fair, we need to prioritize one criterion over the other. In our experiments, we choose to emphasize the "computation cost" criterion, considering the significant challenges GNNs face in terms of high computation costs, rather than large model sizes. As highlighted in $E.3 the computation cost of GNNs can be particularly high due to the well-known
"neighborhood explosion" phenomenon (Chen et al. 2018 Hamilton et al., 2017 Ying et al. 2018 Zeng et al. 2020). This leads to GNN models typically being shallow (with 2 to layers). resulting in a small model size. For instance, the notable work PinSAGE (Ying et al. 2018) employs a 2-layer GraphSAGE. model with 2,048 hidden dimension for Pinterest recommendations, resulting in total model size of only 84MB under 32-bit floating point representation. Despite its compact size, the computational cost of running such a GNN is substantial due to neighborhood explosion, requiring days on 16 GPUs to train PinSAGE. This unique challenge in graph learning highlights that GNN can incur a high computation cost even with small model size.
Therefore, when comparing Mowst with its corresponding vanilla GNN baseline. we ensure a similar computation cost by setting the architecture of Mowst's 's GNN expert be identical to the vanilla GNN baseline. It is important to note that we still conduct experiments on the GNN baselines augmented with skip connections ($A.7). but these experiments are primarily for architectural exploration.
A.6 FURTHER DISCUSSION ON THE COMPARISON WITH THE HETEROPHILOOUS GRAPHS
Heterophilous graphs are among the types of graphs that can benefit from our techniques, since is commonly believed that heterophilous neighborhoods are noisy for GNN's aggregation In this section, we present additional experimental results showing that even on top of a state-of-the-are heterophilous GNN, Mowst weak expert which is just a standard MLP.
still significantly improve its accuracy with the help from
We compare with the state-of the heterophilous GNN baseline, H₂GCN Zhu al. 2020b).
HGGCN integrates model components that are specifically optimized for aggregating heterophilous neighbors. It separates ego and neighbor embeddings, recognizing that a node's self-features may differ significantly from its neighbors' aggregated embeddings in heterophilous settings. Additionally, it leverages higher-order neighborhood aggregation to glean information from wider, potentially comophily-dominat contexts, providing more relevant signals. Finally, H₂GCN merges intermediate representations to capture both local and global graph information.
the experimental results for H₂GCN and Mowst on three heterophilous graphs. The experimental setup and hyperparameter search methodology are consistent with those described in $3 and {A.2] respectively. Specifically. for both H,GCN and Mowst (*)-H,GCM) we follow the hyperparameter space defined Lim et al. (202T). Similar to T we add an additional constraint on the model architecture of Mowst: after identifying the optimal H2 HCG,, we replicate its architecture to construct the GNN expert of Mowst. The MLP expert of Mowst is then configured with the same number of layers and hidden dimensions the H,GCN expert. Table clearyy shows the following:
Effectiveness of the H₂GCN baseline: H₂GCN achieves significantly higher accuracy than the GCN, GraphS AGE and GIN baselines. This shows that H,GCN's architecture can handle heterophilous neighborhoods very well.
However, note that heterophilous graphs are not the only type of graphs we target.
18

---

Performance boost by Mowst -H2GON: Compared with H₂GCN, Mowst (*) -07HHHyCO GCN further improves the accuracy significantly and consistently on the three graphs. The average accuracy improvement is 1.05.
A.7 FURTHER DISCUSSION ON THE COMPARISONS WITH GIN SKIP CONNECTION-BANE GNNs
In addition to the three Mowst variants in Table I and Table 2 we further construct Mowst on GIN and its variants, and show that Mowst significantly boosts the baseline accuracy across all five datasets (due to resource constraints, we exclude the largest ogbn prnn-ccouussss graph when running experiments this section). We further add skip connection the GIN and GCN baselines, and show that
Skip connection can help boost the baseline performance in some cases, but also result in accuracy degradation.
When skip connection improves the baseline, building Mowst with the "skip-connection GNN" expert can further boost the accuracy significantly.
Among the four GNN backbone architectures on which we have built Mowst, GraphSAGE and H₂GCN already incorporate skip connections in their native architectural definitions. Therefore, we only need to implement the skip-connection variants for GCN and GIN. The implementation details are folllows:
Consider a node v. Let its output embedding layer af. Let the set neighbors of v be 71" (excluding itself).
Without the skip connection, a GCN layer performs the following:
x =
W
aupet
(4)
"E"""(u)
where W, is the weight matrix, Que is scalar weight determined by the graph structure and the non-linear activation (e.g., ReLU).
With the skip connection, GCN-skip layer performs the following:
x = W -W;+
any 20 i-1
(5)
Without the skip connection, GIN layer performs the following:
x he (1+c) 2/
Σ x
(6)
where is learnable scalar, and he (+) is 2-layer MLP with ReLU activation in the hidden layer (but not in the last layer). with e denoting the learnable parameters of such an MLP.
With the skip connection, GIN-skip layer performs the following:
W/ x. the (1 (1+6).
Σ a
xy
uEn"
19

---

In Table compare GCN with GCN-skip, and GIN with GIN-skip. We observe that GCN-skip consistently degrades the performance GCN, while GlN-skip improves the accu- racy of GIN ogbn-arxiv, pokec and twitch- gamerr significantly. There is need to run Mowst (*) -GCN-skip since Mowst -GCN already outperforms GCN-skip by a large margin with respect to both accuracy and computation cost (see analysis of computation cost in $E.3.4p. On the other hand, since the accuracy of GIN-skip is close to that of Mowst (*) -GIN on agbn-arxixg pokec and twi testtch--eee teichhammer, we run Mowst (*) -FI--INNkii for additional comparisons. We summarize our findings as follows:
Adding the skip connection to a GNN layer can either enhance or degrade accuracy.
Mowst (*) -GIN consistently achieves substantial improvement in accuracy over the GIN baseline. Notably, on pokec, the GIN baseline exhibits poor convergence. Adding an MLP expert of Mowst dramatically improves the convergence quality.
Mowst (*) -INN- further boosts the accuracy of GIN-skip significantly.
The results of skip connections GCN (Table I GraphSAGE (Table GIN (Table and HyGCW (Table 2 demonstrate that: (1) Mowst is a general framework that is applicable to various GNN architecture variants, and (2) the contributions of the MLP expert and skip connection are different, with the weak MLP expert providing unique value in enhancing the quality of the GNN model.
Remark. Based on the reasoning in A..5 the following pairs in Table [ satisfy the fair comparison criteria: "GCN vs. Mowst GCCC "GIN vs. Mowst (*)=at") and "GIN-skip vs. Mowst -ae -GIN-skip".
B EXTENDED RELATED WORK
In addition to the related work ($4) in Mixture-of-Expertt and ensemble methods on graphs, our work also closely related to the decoupling feature and structure information and heterophilous GNNs. GraphSAGE (Hamilton et al. 2017). GCNII (Chnn et al. 2020b) and H₂GCN (Zhu et al.) 2020bb use various forms of residual connections to facilitate feature propagation, with H,GCN especially excelling heterophilous graphs. GPR-GNN (Chien al. 2021). MixHop (Abu-El-Haija et al. 2019) and SIGN (Frasca et al. (020) blend information from various hops away via different weighting strategies. NDLS (Zhang
2021 performs adaptive sampling to customize per-node receptive fields. GLNN (Zhang et al. 2022) distills structural information into an MLP. These models
decouple the feature and structure information within one model, while Mowst does explicitly separate experts.
C ADDITIONAL EXPERIMENTS
C.1 ALTERNATIVE CHOICE FOR WEAK & STRONG EXPERTS
In 22.3 $2.4 and 2.6 we have discussed the advantages of designing Mowst with an MLP as the weak expert and a GNN as the strong expert. Here, we explore an alternative approach and its tradc-offs. A question the same, and construct the weak strong variants only by varying the architectural parameters. For instance, the two experts could be shallow and deep GNN, respectively.
would naturally ask is: Should we keep the architecture of the two experts
We first affirm that the current setting of Mowst already following the above proposal, and then conduct additional experiments by replacing an MLP with shallow GCN.
C. MLP AS A SHALLOW GNN
We first show that MLP and GNN are not fundamentally two different architectures. In fact, an MLP is exactly a O-hop GNN when the GNN's layer architecture follows popular designs such as GraphSAGE (Hamilton al. 2017), GCN (Kipf & Welling 2016) GIN (Xu et al. 2019).
20

---

Let xy denote the embedding vector of node output by layer W, the weight parameter matrix of layer i, and 72" the set of neighbor nodes of v. Let o (+) represent the non-linear activation function.
Notations.
GraphSAGE. Each layer performs x. ( x._1 W? Emen- w In 0-hop version, where the neighbor 11" 0. the operation simplifies to z. = a (W) xx-1)) which is identical to the operation of an MI. layer.
GCN. Each layer performs xx = (W (Qvoz2 + Eugn- (uv where Cuu and Oue
are constants pre-defined by the graph structure. we perform O-hop aggregation and ignore the graph structure, then Quu and become and 11" = 0. The O-hop GCN performs x = a (W; x²-1). which is again identical to the operation of MLP layer.
A similar process can be applied to other architectures such as GIN (Xu et al. 2019). H2GCN ZZuu al. 2020b), and GAT (Veličković al. 2018) reduce them standard MLP.
Therefore, following our design in $3 our weak MLP expert is already consistent with our strong GNN expert from the perspective layer architecture.
C.1.2 RESULTS ON MIXTURE OF SHALLOW-DEER GCNS
We further construct variant of Mowst (*) -GCN by replacing the weak MLP expert with shallow GCN. In Table 5 we refer to this variant as Weak-SSroog GCN". The hidden dimension of the Iwo experts in Weak-Strong GCN the same that of Mowst (*) The "weak" expert of the "Weak-Strong GCN" is 2-layer GCN while the "strong" expert is a 3-layer GCN for Flickr, ogbn-arxiv, and I-layer GCN, and the "strong" expert is a 2-layer GCN. The detailed experimental settings and hyperparameter search methodology are the same as Table
For Penn94, pokec, and twitch- gamee,, the "weak" expert is
We observe the following from Table
Adding a weak, shallow GCN the strong GCN is overall still beneficial.
The accuracy gains fluctuate across datasets. For example, "Weak-Strong GCN" achieves significant accuracy improvement on twitch- but has accuracy degradation on Flickr.
The overall accuracy gain from "Weak-Stronp GCN" is lower than that from the original Mowst (*) -GCN.
Table Test set accuracy comparison among the baseline GCN and two variants of Mowst. "Weak- Strong GCN" consists of a 2-layer GCN the weak expert and a 3-layer GCN the strong expert. For each graph, we highlight the best accuracy. The experimental setting and hyperparameter search methodology are the same as Table
Flickr
ogbn-produse products
ogbn-arxiv
Penn94
pokec
twitch-gamer
MI.P
46.93
+0000
61.06*
+-0.8
55.501
-0.23
73.61
-0.40
62.374
4-0.02
60.92
+-007
Weak-Strong MLP
46.87
+0.16
61.24
+0.10
55.98
+0.10
73.78
=0.32
62,44
#0.05
60.68
+0.12
GCN
53.86
+0.37
75.64
=0.21
71.74
=0.29
82.17
=0.04
76.01
#0.19
62.42
+0.53
Weak-Strong GCN
54.19
+0.27
74.47
+0.21
71.92
10.19
82.38
20.32
76.51
20.08
63.36
10.25
Mowat -GN
54.62
10.23
76.49
10:22
72.52
10.07
83.19
20.43
77.28
20.08
63.74
10.23
We perform the following trade-off analysis on the "Weak-Strong GCN" variant. First of all, according
to 2 our Mowst design is not restricted specific expert architecture. Therefore, theoretically "Weak-Strong GCN" still improves the model capacity of the baseline GCN. While upgrading the weak expert from an MLP to a shallow GCN has the potential to further increase the model capacity (e.g.. "Weak-Strons GCN" twitch twitch-gamer), Mowst (*) -CCN may still be more favorable than "Weak-Strong GCN". We reveal the reasons by analyzing the specialization challenge in "Weak-Snn Strak-Strong GCN" (see 2.4)
Recall that in the original Mowst design, when the two experts specialize, the MLP expert would specialize to nodes with rich self-features but high level of structural noises. The GNN expert would
21

---

specialize to nodes with large amount of useful structure information. Following the above design consideration, in "Weak-Strong GCN", the 2-layer GCN expert will specialize to nodes with rich information in the 2-hop neighborhood. but noisy connections in the 3-hop neighborhood. However, in realistic graphs, a shallow neighborhood (e.g., 2-hop) already contains most of the useful structural information (Zeng al. (021) (consequently, the accuracy boost by upgrading 2-layer GNN to 3-layer one is much smaller than the boost by upgrading an MLP to GNN). As a result, the 3-hop noises in a 3-layer GNN can be much less harmful than the I-hop or 2-hop noises. Thus, it would be challenging for the 2-layer GCN to find nodes that it can specialize on. The intuitive explanation is that, the functionality of the 2-layer GCN expert overlaps significantly with the 3-layer GCN expert, and thus the benefits reduces when mixing two experts that are similar.
We im- plement "strong-strong"" variant of Mowst" consist- ing of two GNN experts with identical network ar- chitecture. Figure 3 shows the convergence curves of the test set accuracy during training, with GCN as the strong experts' architecture. On both Penn94 and ogbn-arxinn we observe that the convergence quality of the "strong-strong" variant is much worse. Specif- ically, on Penn94, the "strong-strong"" model does not identify a suitable collaboration mode between the two GNNs, causing the collapse of the accuracy curve. On ogbn-arxiv, the collapse of the "strong-strong" model does not happen. Yet it is still clear that (1) training "weak strong" model is more stable, indicated by the much smaller variance, and (2) the accuracy of the "strong-strong" variant is significantly lower. Lastly, note that the z-axis denotes number of epochs. The per-epoch execution time for "strong-strong" is also significantly longer, indicating an even longer overall convergence time than the "weak-strong model.
WEAK-STRONG vs. STRONG-STRONG,
Weak-Strong
Stron Sarong-Strong
Penn94
ogbn-arxiv
0.8
0.7
Test Accuracy
Text Accuracy
0.7
0.6
0.5
0.5
25
50
250
500
Epoch
Epoch
Figure 3: Test accuracy comparison be- tween "weak-strong" and "strong-strong".
C.2 DENOISED FINE-TUNING
we examine two distinct node groups and visualize their positions in a shared latent space using t-SNE (Van der Maaten & Hinton| 2008) applied to the second-to-lass layer of the GNN expert. The first node group comprises nodes that clicit high confidence from the MIP expert (nodes with top-25% C). The second group includes the remaining nodes. Green and blue dots represent the initial positions of the group and 2 nodes at the end of training round r. Red and orange dots represent the final positions of the group and nodes at the end of training round r + 10 (e.g.. a node starting from a green dot will end red dot). Notably, we observe that significant portion of nodes remains relatively stable throughout the training process, and thus their start and end positions almost completely overlap. We refrain from visualizing them, as their GNN's predictions remain unaltered. Instead, we only visualize nodes whose movement (Euclidean distance) exceeds the thth percentile. In Figure 4 the blue and green nodes are clustered together, indicating that the GNN cannot differentiate them. After the MLP filters out the green nodes of high C, the GNN is then able to better optimize the blue nodes even if doing so will increase the GNN loss on the green ones (since the loss on green nodes down-we weightedd. Eventually, the GNN pushes the blue nodes to better position belonging to their true class (the shift of the green nodes is side effect, as the GNN cannot differentiate the green from the blue ones).
In Figure 4
Figure 4: t-SNE visualization on GNN embeddings for Flickr.
22

---

D PROOF AND DERIVATION
D.1 PROOFS RELATED TO MODEL OPTIMIZATION
Definition D.I. (Convex function (Bertsekas et al. 2003) Let D be convex subset of R". A function f I is convex if (x- X) S VA E [0, 1).
(x) + (1 A) (t), Vz, E and
Definition D.2. (Quasiconvex function (Boyd & Vandenberghee 2004g) Consider real-valued function f whose domain D is convex. Function I quasiconvex if for any Y E IR, its 7-suleevel set {xr E 1 [(x) S < is convex. Equivalently, f is quasiconvex if. for all x. y E H and X E [0, 1}, we have fA x + (1- x) y) S max {f (z), f (y))-
Definition D.3. (Strictly quasiconvex sincctoon) A real-valued function f defined on a convex domain 5D is strictly quasiconver if. for all x, D. x + y and X E (0, 1), we have f (A x X) .).2)
y) <
max {f (x) f (v)).
D.1.1 PROOF OF PROPOSITION 2.2
Proposition D.4. (Originally Proposition 2.2 C G D is quasiconvex.
Proof. The proof directly follows Agrawal & Boyd (020), which states that if g : D R is quasiconvex function and / a non-decreasing real-valued function on the real line, then f = h h quasiconvex. By Definition 2.1 we have C = G D quasiconvex.
The only thing remains to be shown is the quasiconvexity of typical dispersion functions. We show the convexity of the variance and negative entropy functions by following Definition D.I Next, we complete the proof since any convex function is also quasiconvex (based on Definitions D. is convex, then (Ax (1 A) S Af(x) (1 A) f(y) S fax)
and D.2 D.2 if
(1 mfx(()))) f()) = (x),
To show the convexity of the dispersion function D (p), we first note that its domain a (n 1)- simplex (i.e,, Eigign = and p: 2 0 for i = 1,2,... n), which is a convex set. Next, for specific D:
Variance function is defined as D (p) = Eisisa (n. - -2²² For two points and p' and E [0, 1], it is easy to show that D (Ap (1-A)pp) I AD (D)
(1 (1-A) A) D (p') (we can follow similar treatment as Equation 16 by noting that scalar function d(x)) (x 1)²² is convex).
Negative entropy function is defined as D (p) = c+ E+EIsssn log where e is just constant satisfy Definition 2.1 that (+1) 0. well-known result that the negative entropy is convex. See the prool in JoramSoch 2020).
D.1.2 PROOF OF PROPOSITION 2.3
Proposition D.5. (Originally
PraullllPoPrrprr Proposition 2.3) Given an L.; (p:) is convex functio of ps with unique minimizer P Qt (a) La (a) be a function of a, A is a concave function with unique maximizer ax _1.
Proof. We can formulate the problem of finding the minimizer D of Lo. (p:)
min
Σ aij log Pij
(8)
p.
15J5R
s.t.
Pij 2 0, for j = 1, 2, 2..n
(9)
Σ P.j
(10)
1875
23

---

The Larangian is
L (Pa: Ai
A2, A2, An)
Σ
Osj
log Pij +2
Σ
Pig
1
Σ
AsPes
(11)
1
1sisn
1sisn
Applying the KKT condition (Bertsekas
2009), we have
04j x0 + 23 0,
for 1, ....
(Stationarity)
P1
Nj Pij 0,
for 1, ....
(Complementary slackness)
Pij 2 0,
for 1, 2, .....
(Primal feasibility)
(12)
Σ Pij
(Primal feasibility)
13J5n
X3 20 0
for j 2,,,....?
(Dual feasibility)
2" 20
(Dual feasibility)
Solving the system of equations in 12 we have Pij = au/ (Eisisnay) aw) Since ar forms
distribution, we further have Pig = Oijs Lee,
p ai
(13)
Since Lo, is also strictly convex (Proposition D.7 its minimizer is unique.
In particular, A (a;) L.. (a,) = - -Esijsn ay log azy H (ax). It is easy to show that the entropy function H is strictly concave w.r.t. the probability mass function and attains its maximum when a = 111 JJramSoch 2020).
D.1.3 PROOFS RELATED TO THEOREM 2.4
We first observe that the optimization problem defined in Equation Cean be fully decomposed:
min (P.)
Σ (p:) (La. (p.) - 11)=
Σ
min P:
(c:). (La. (0.) -p:))
(14)
15i5m
It is evident that the original optimization problem (Equation 2 dent sub-problems:
can be decomposed into indepen-
D = arg min (C.)). (Loc (p.) (oi)-1i) mi))
isis m
(15)
Therefore, in the following, we omit the subscript i.
Definition D.6. (Extreme points Bertsekas al. 2003)) Given nonempty convex set a point E C is extreme point there do not exist y E ID and D with y + I and + and a scalar (0, 1), such that Ay (1 X) z.
Proposition D.7. The loss function i.n (p) is strictly convex. For all μ, the sub-level set LSS is convex and compact.
Proof. For strict convexity, first of all, the domain of La. the (n 1i-simp is convex. Then consider points p and şi in F.g 's domain and some X E (0, 1):
24

---

(1
Σ
aj aa--loog (A 0: + (1 A) f2()
Igign
Σ 0i
- (1 - -) -log
1
Σ ai log +(1- (-Σ as log
=1.
Isisn
Isisn
=x La (p) + (1- L (p')
(16)
where " (.)), "²" is due to the strict convexity of the log function. This proves that La is strictly convex. Then it directly follows that all its sub-level sets are convex.
Note that La is continuous (and lower semicontinuous well). By Proposition 1.2.2 of Bertsekas al. 2003). all sublevel sets of La are elosed. Further, since La is defined on the (n J)simpleex L I8 also bounded. Therefore, - is compact (compact means closed and bounded).
Proposition D.8. The set of extreme points of L equals L.
Proof. Denote P as the of extreme points of LS" We first show that L S P. Consider point Po E Lt. Suppose there exist some other points Pl, P2 E LS" (with p1 & and P2 * Po). such that Ap1 + (1 A) P22 = Po for some X E (0, 1). By strict convexity shown Proposition D.7 we have = La (Po) = La (Ap1 + (1 - P2) < ALa (pi) + (1 - X) La (f2). This implies that La (f1) > or La (P2) > 1s, which contradicts with the condition that p1 P1. E L Thus, any point Po Lh an extreme point of L'."..
Now we show s0 LLC Consider point po E LCH. For any μ E R, we always have Po: > 0, for all i = 1,2,..., It (otherwise, La (po) oo). This means that we can find vector such that (1) E1) G (2) |al < Pos. for all 1 S i S n, and (3) La (po c) S μ and La (po c) S μ.. Point (1) and (2) ensure that Po + e and Po E are both with the domain of L.. For Point (3), we can always find small enough due to the continuity of the loss function L.. We thus find two points, p1= = Pu CE E L and p22 Po E LS",, where Po 2 + 12. Thus, Pu L an extreme point of LSS..
In summary, S =0=1! d'U..
Proposition D.9. (Krein-Milman Theorem (Bertsekas et al. 2003 Let 5D be a nonempty convex
subset of R", If is compact, then SD is equal to the convex hull of its extreme points.
Proposition D.10. (Caratheodory's 's Theorem (Bertsekas) 2009g) Ler D be a nonempty subset of TR... Every point from the convex hull of can be represented as convex combination of Z1.... Zm from D. where m S n + 1 and I2- I1...., Im
are linearly independent.
Proposition D.11. f f is cnnasiconvexfuncttiio defined on D. thenfor all "1,...,,.. E and A 2
O,..., Am 2 such that Eisism X; 1, we have f (Eigism >ix:)) S maxxssssm {1 (z:)).
Proposition D.12. If is strictly quasiconvex function defined on D. then for (1) Z1...., ......... I'm D such that 21 *
# Fm and 42 II...., Jm are linearly independent, and
(2) A1 > 0 O...., Am > such that Eisism A = 1, we have f (Eisism ArTTs) maxigism (x:)).
Proof. For brevity, we only show the proof for Proposition D.12 as the proof for Proposition D.I1 is similar (and easier). We prove by induction. The base case of m = automatically holds by Definition D.2
For 2, note that
25

---

Σ Aaa 1 + Isism
Σ d 25ism
Σ 25ism
Exsism A D/y
(17)
Let X2 Lagigm A Apparently, Eessem X2 and X3 0 for all 2 S S In ad- dition, 22, 4m I2 are linearly independent (To show this: Ezsism (z) - xi) xi)
A
Easism 3j (r, x2) + (Essism B) (02 - 11). If I3 22. . Im 222 are linearly de- pendent, then there exists $3,..., 3m such that Ezsism Bj (zj x2)
Then by letting B2 Ezgism 33. we have E2sigm 83 (x, - x1 = contradiction with the hypothesis that x2 2m 21 are linearly independent). Therefore, by induction hypothesis, have
Σ 25ism
Xaos
max (S (x²))
(18)
25/5m
Let Exsism Xazz. Since x2 21...., 2 I1 are linearly independent, we must have Egsism X, (zg 21) * Equivalently, Egsism Njz = x' + 01. Thus,
Σ Aati Isism
(A101 + (1- max {5 (x1) f (z'))
(19)
max
fx1)),
max {f (a:))
(20)
2515m
max {f (z;)} isism
(21)
This completes the induction process and thus concludes the proof.
Theorem D.13. (Originally Theorem 2.4 Suppose C G D follows Definition 2.1 Denote
La 1 La (f) p1} and Lz" {p La (p) {}} as the level and strict sublevel set of
L.a- Denote @ = {p C (p) < 1} as the strict sublevel set of C. For given * 1 1 the minimizer p satisfies:
n
(f) > μ. then p = n 1, and C (p*)= 0.
(a) μ4, then p = fr 1 n
(a) < p. then 8³ E LLE Car' where μ¹ ((a) S C S G (max D (p)).
Further, there exists C such that p = a, or pD is sufficienlly close to the level set L
Proof. We separately consider the three cases listed by Theorem 2.4
Case 1. By Proposition 2.3. we have f.x (p) r 2 ming (ia (p) -1) L. -
A (a: > 0 for all p. By Definition 2.1 we have C (p) 2 0 for all p. We can thus derive the following bound: C (p*). (La (p*) p) = ming
( (La (p) -1)) 2 Further, since
La (p) > 0 for all p. the lower bound C (f*).
i. (p*) - 11 = 0 is achieved if and only
C' (p*) 0. By Definition 2.1 the minimizer p 1
The reasoning is similar to Case 1. We can derive C (p²) (I.a (D*) -1) 2 0. Now to achieve the lower bound C (f*). [L (p*) - 1) 0, we either need C (p*) = Oor La (p') 4 0. which means either p 1 1, or fr
Case 2.
26

---

Case 3. First, observe that C (p*). [La -5"))+() minp (c (La (p) (()-)+)) n) p=o
v C(a).
(Tra (a) p) = C (a) (A (a) - 14) < 0 (note that we assume a o 11). Since C (f) 2 0 for
all p. this implies that
C(f*)
(22)
La (p') - - <<00 <0
(23)
By Inequality 23 we have pr Las
We can further constrain p such that (p¹) 2 C (a):: Suppose otherwise that 2 C (f()) (a)). By Proposition 2.3 we have La (f*) p 2 A (a) μ
La (f") -0 S
(a) - p.). Combining the two inequalities together, we have -C (f¹) (Iia (f") - 1) 1)
C(p¹) (La (p') -)) > ((a) (A (a) u)) This means that 1" is not a minimizer - contradiction. In other words, we must have f & e<H' where μ' = C (o))
(a) (a) u))
So far, we have proven p" E LS" - e<u' where μ' C (a) I (p*). Next, we further upper- bound the range of the confidence corresponding p". Note that
C (p²) S
sup BELS -Cew
(a) S (p)
sup BELL
C (b) G
max (()) pels
@ _
max D(O) (24)
ped=
For above, the reason is that Laz Geu' C L For 1. (b),,
(a)
let's first consider sup S D (p).
By Proposition D.7 LzSN is compact. By Definition 2.1, is continuous. So by the extreme value theorem Murphy 2008), D attains its maximum value, i.e. there exists p' E L such (P) max max_ss Ls- D (p). In other words, D (ø')= 2 D (ÿ) for all p LE"
that D (p')= = sup_55 5
Now since G is monotonically non-decreasing (Definition) 2.1 we have G (D ) 2 GD) for all p L... This means C G o attains its maximum p' and sup pels C(p)
max pEsa Sn C (p) G (maxpessi D (p) Finally, for (. we need to show max, max, pels D (p))
maxpe.s (g). By Propositions D.7 D.8 and D.9 L is the convex hull of Lz. So So Proposition D.10 for any point po E L'Sa, we can find
Pm E L' (with m I n + 1), such that Po = Eisism X (with Eisism X = and X; 2 0 for 1,...,m), m). By Proposition D.11 we have D (po)= S maxigism (D (p:)} S max D (p). Thus, max re D (p) max D (p). This completes the proof for Equation 24 Thus, we have proven the bound on both the minimizer p and its corresponding C' (f*).
Case 3: Tightness of the bound. From the above proof. we know that when A (a) < μ. the possible positions that the minimizer p" can take are determined by the two level sets CSa (p' C (ax) and L We now show that the bound on p* is tight since p* can be close to the two level sets under appropriate C = G o D function. Note that our proof is based on C' defined by 2.1 meaning that C does not need to be continuous.
First, we construct a C such that p a. Such a C' can be defined by a simple G for any D:
0, when æ S 0
G(x) 1, when x >
(25)
Since a # 11, we have D (a) > 0 and thus C' (a) =
= 1. By conditions 22
23 we
have C (p*). (ina (Ø*) 11) 2 max C (δ) min (ia (p) -1) = =1-(A (a) 14) = (a)
27

---

In addition, since the problem min (La (p) -
(b)- has a unique minimizer at a (Proposition 2.3
and (x) max C (p) 1, we know that under C defined by Equation 25 we have a unique minimizer p = for the overall optimization problem 15
Next, we construct C' such that p is close to Lg We first define the distance between point p and the level set d as:
dist (p.
= min
Ip 1'll
(26)
Thus, we want to show that there exists C, such that dist (()) for any 0.
Consider another sub-level set L'S-" for some 17 > 0 (we also let to be small enough so that Lzu-" is non-empty). We have shown before (by combining Propositions D.7 D D.9 and D.10 that any point p' E EL--0 can be expressed as a convex combination of p Pm. where m S. n + 1, p; E Lx and p2 - PI...., Pm - PI are linearly independent. Since i' in the strict sub-level set and p: are in the sub-level set, we have ç'' + pi, and thus we can write p' -iiiism App where A > and Eisism A =.
Suppose is strictly quasiconvex. We can now apply Proposition D.12 such that
D D
Σ Isism
Xpp
max (D.).) 1si5m
(27)
The strict "<" means that L<サ-" cannot contain any maximizer of the optimization problem "max pers" D (p)" (note that previously, we have only shown L contains the maximizer, but it is also possible for L-N-" to contain the maximizer if D is not strictly quasiconvex). Now, define Dmax = max PEL D (p) > and the corresponding maximizer (or one the maximizers) as p7 E LL"" For all P L<"=" we have D (p) D D Consider a function defined as follows:
0, when S
B, when < x < Dmuxx
(28)
1, when 2 Dmnx
By definition, La (p;) = p 17 0. Also, C ( = G(D(#:)) = 1. As a result, C (p;) (Ia (f7) 11) -17 For any point P E LLn-7, we have ( G (D) = 3. Consequently, min 15 ( (La (p) -1 1)) = 3 min pe (ia (p) - (A 1a). Therefore, as long as 1 < < a-A the minimizer 5³ of the original optimization problem 15 must satisfy P E L-H --#=" (or more precisely, 8 L'= -ー:ー" - -(w)),
Now the last issue is to determine the relationship between and e. We know that μ S La (p*) < μ. We utilize the idea of path integral. We first note that the domain of La (ø) is the (n 1) 1)-sipllex, which lies within a hyperplane of RT. It is easy to show that the normal vector of such hyperplane parallel to 1. For a point p, denote л (p) as the vector by projecting the gradient V VL,, (p) onto the hyperplane. With some basic calculation, we derive that
28

---

21
+ 1
Lisisn
P1
(p)
(29)
Σ Lisjsn Pj
Pu
1) al
a2
P1
Q1
(1
02
i'2
(30)
a1
a2
1 1) an
Pin_
The linear system of equations (p) 0 has unique solution of p since the coefficient matrix in Equation 30 has full rank. In other words, || (p)
for all p } a.
Imagine we start from p* and traverse path P' in the hyperplane. Suppose that the path always follows the direction of π (p) for all p on the P. the total length of P is less than - al|. then regardless of what path P looks like, it always holds that | (p) || > 0 for all P. Define dmin = min on path
(p) > 0.
Now consider the path integral along P. The start point of P is p.. Denote P's end point p
J, TD) (1)) dp (m) / via (0) dp ( La (8¹) Loa (f¹)
(31)
where ,!a). is due to that Vi.a (D) (p) is vector perpendicular to the hyperplane (and thus to dp). ..(b)., is due that V 1.a (f) defines gradient field, and the path integral be computed by the end points and is path independent (gradient theorem).
In addition, note that
/ (p) dp (o) S || (Ø)
f dmin
dmin / |dppl dnin len (P) (32)
|dpll >
||dpl
where _.0 is due that we always traverse the path along the direction of π (ø); len (P) denotes the total length of the path P.
Combining 31 and 32 we have La (p') 2 dmin len (P) + La (p*). This means, we start from a point 5 at level set -n and traverse path with length at most a.m. will arrive at point ý' the level set Li We can further derive the following bound:
dist (L) D" -pll len (P) <
(33)
dmin
In summary, for any budget > 0, we can construct C according to Equation 28 by choosing parameters such that < S dmin c and
< (a))
We follow the notations from 22. and apply Theorem 2.4 to the binary classification task, resulting in the following corollary:
Corollary D.13.1. For hinary classification (n = 2), w.L.ogg, assume on E [0.5, 1). Define i. (p) La ([p, - p)T) for p E [01, 1). For strictly quasiconvex D and monotonically increasing G,
oi E a1, f. (n)) and (a)) & ( < ([+x7" (n), i (m))) when (ax) < μ.
=zz((n))
29

---

Proof. For binary classification, we have P [21, [p1. 1 .11". Therefore,
La (p) = tr (fi1, 1 -11l") = -01 log - -(1 01) - log (1 - 51)
(34)
Let L (p) = -a logg- - (1 - a). log (1 - p). Define f, (p) f (p) where p E (a1, 1) and I_ (D) = L+ (p) where P E (0, a1). It is easy to verify that L+ monotonically increases and L_ monotonically decreases. In addition, L4 (a1) L- (a1) A (la1, 1 - anl²) A (a).
When A (a) na then L (0) μ if and only if P E [an Euj (w)) and L_ (Ø) μ (w), if and only if D E (i= (i)) an)
Thus, let p_ [ ( 1- (m) and p+
[ (x), (w) Then LJ = {p-. P+} and LI" consists of the open line segment connecting p_ and p+ (not including the two end points p- and p+).
[a1, a1] and a' = a1 a1 T have ( a + (1-X) A) aa) < max [D (a) (a') = D (a) = D (a') for X E (0, (see Definition D.3 also note that [p, p] and [1 p.p] should always have the same dispersion).
For C. since D is strictly quasiconvex, then let
Therefore, for all E (1 a1, 01), we have D ((p. (-p,1-p1 () < DD()). We can similarly show that for all ý (0, a1) U (an, 1), we have D ( )) > D (a).. Now since G is monotonically increasing, then for E (1 011 01), we have C (a1, 1), we have C' (lé, 1 - ) < p'. Therefore, @ consists of the open line segment connecting a and a' (not including the two end points of a and a').
T]T) < <C = μ². For á (0, 01) U
If -1 S --=11p < an, then the line segment connecting p_ and a overlap with e<r', Therefore, LL - - equals the line segment between a and p.. Le., L - -e*H = {1t, 1 - =p]
on, 1 (m))
0.5 > 1 a1 İ- (p), then the line segment between and a' fully overlap with the line segment between p- and p.. Therefore, L C. consisting of (1) a segment between p- and a', defined by S {[p. 1 T l [- (p) ai) }. and (2) segment between and p+, de- fined by 83 = {p 1- àE (a1. LI (w)).. We can further rule out segment (1) by the following
analysis. For all E (0, 0.5). we have L1 (f) - -L (1 P) (1 20x1) (log (1 - () log p) > 0. This implies that 1.=1 (n) 1 î- (1)) > 0.5. As result, for any ń [p,
p) E 81, T S2. Since and ø' have the same dispersion,
can find a corresponding p' = p,
then (p) = Cf") However, i.a (p) i. (p) i. (1 p) = f.a (f¹). Consequently, C' ('))) (La (1a(p)) (p) > C (p'). (Lo (p') m)) This implies that p cannot be minimizer. In summary, the minimizer can only fall in S2.
Considering the two cases, we have pi E a1, i (w) for the minimizer p'
Finally, let consider the range of C (p*). According to Theorem 2.4 we only need con- sider the upper bound G (maxpers D (p)). We have shown that L { p ), well as if (n) > 1- (p) > 0.5. Thus, the dispersion of p.+ is no less than that of p_.. meaning that
G (maxpe D = G Cp++) ([ (1), 1- iI [w)]
D.1.4 PROOF OF PROPOSITION 2.5
Proposition D.14. (Originally Proposition 2.5 For any function C with range in [0, 1), L
upper-bounds L Towee:
30

---

Proof. We compare Equations 1 and
Note that the loss L is convex function. In addition,
C' (pc) E [0, 1]. Thus, C (p.) P. + (p.)) P, is a convex combination of pa and pa in L's
domain.
Thus, by Definition D.I
(p.) - (p.) + (1- - (p,))
P. (1-C P.))
(35)
Summing the left-hand side and right-hand side of the above inequality over all nodes V, derive the conclusion that Lnowet 2 Liosst
D.2 PROOFS RELATED TO EXPRESSIVE POWER
When considering graph the model input, we define the following:
Model A is expressive model B if, for any application of model B any graph, there exists a corresponding model that produces identical predictions.
(2) Model A is more expressive than model B if (a) model A is at least expressive as model B, and (b) there exists a graph for which a model can be found that yields different predictions from any model B.
In the following proof, to demonstrate that one model is "as expressive as" another, we construct confidence functions such that Mowst generates exactly the same outputs as any of its experts. To show that one model is "more expressive than" another, construct specific graph and corresponding Mowst-GCN for which the Mowst-GCN can correctly classify more nodes than any standalone GCN,
D.2.1 PROOF OF PROPOSITION 2.6
Proposition D.15. (Originally Proposition 2.6 Mowst and Mows to least expressive the MLP or GNN expert alone.
Proof. We complete the proof by showing particular confidence function C' G D and expert configuration, that reduce Mowst to single expert.
Define g- C (p.) + (1 C (po)) P'.
Further, define the following G:
0,
when x < 0
G(x) 1 1, when >>
(36)
Mowst* + MLP expert. Let the GNN expert in our Mowst system always generate random prediction of pl, 1 regardless of If the MIP expert does not generate a purely random guess (i.e., Pe n 11), then D (p.) > 0 according Definition 2.1 Therefore, C' (p.) G GD (p.)) and thus q. P.- the extreme case, where P. I we have qu = P Yet, note that we configure our GNN expert to always output 1. As a result, we still have q. = P. 1. This shows that Mowst* can always produce an identical output to that of MLP expert alone.
Mowat* + GNN expert. We configure the MLP expert such that it always generates trivial prediction of p. 1. Consequently, D (p.) = for all e, and C (p.) G (D (Px)) 0 for all according to Equation 36 Thus, qu p',, implying that Mowst" always produces an identical output to that of GNN expert alone.
Cases for Mowst. Similar reasoning be applied the Mowst design, where G function defined in Equation to let the Mowst system always predict based solely on the MLP expert the GNN expert (see Algorithm for the inference operation).
the
31

---

D.2.2 PROOF OF THEOREM 2.7
Theorem D.16. (Originally Theorem 2.7 Mowst and Mows t -GCN are more expressive than the GCN expert alone.
Proof. We consider unweighted and undirected graphs for this theorem. According to Proposition least expressive standalone GCN. To show that Howst-GOl and Mowst" -GCN are more expressive than GCN, we compare the function class consisting of all possible K K-layer GCN models and the function class consisting of all possible K llyer Mowst*-GOW models. Then we will construct an example graph G with a pair of nodes u and On this G. for any GCN model M11 we can find a corresponding Mowst* -GCN model 771', such that
2.6 we know that Mowst-GCN and Mowst' -CNN
(1) Ill cannot distinguish from
(2) 777' can distinguish from v and,
(3) if m can distinguish some nodes, then 771' can also distinguish them.
Denote n as the set of neighbor nodes that are hops away from v (specifically, ni = {u})) We further enforee the following constraints the structure of G:
(I) The K-hop neighborhoods of u and v do not overlap, iee. (Uoseek n
(UUSESK m 6:
(2) For any node w E 7 (where 0 S & K 1), there exists an edge (w, w²) E where w" n and w" does not connect any node in n other than w; Similar constraint applies to node u's neighborhood n7
(3) The structures (i.e., not considering node features) of the K K-hop neighborhood of and are isomorphic. i.e., For the two subgraphs induced by Uogegk n and UoSkeK 71 can find an isomorphic node mapping F' where F(u) = and a node v' E 7 is mapped by node u' n
Next, we discuss how to set the node features for G. First, we let and have different node features, and thus and should distinguished if the model is powerful enough. Then, we consider the features of the neighbors of u and v. Recall the operation of a GCN layer. For node in layer k the GCN performs weighted sum of the embedding vectors w's direct neighbors in GCN's layer (k - 1). Denote h (k)
as the output embedding vector of w in layer k. Then,
(k) =o ((Wi)))
Σ
(k
(a))
(37)
V(deg (w) 1) (deg (wr² +
w'
w' o'En Uww
where a is the activation function, W (A) and (k)) are the learnable weight matrix and bias vector of layer h. and deg (-) denotes the degree the node.
Denote x. = h as the raw node feature. We can construct the graph features such that for all w Uo n5. This can always be achieved due to the constraints (1) and (2) above: for each E n., can find w" (as described in constraint (2)) and set ( s.t. "counter-acts" the aggregated features all w's other neighbors.
Ewtrngu(w +
(b) for all UbSksk-1 N2.. Thus, the layer output features are identical for all (K hop neighbors of both and i.e., after GCN's layer aggregation, we lose all information of the node features the neighborhoods of and For layer 2 and onwards, the GCN
In this case, by Equation h (WW())) 0 ((0)
completely isomorphic (including both structure
32

---

and feature) neighborhood subgraphs of u and u (due to constraint (3) above). And thus, regardless of the GCN's model parameters, the GCN will always output identical embedding vectors for u and And no GCN can distinguish u from
Now consider Mowst-GCN and Mowst" Recall that u and e have different self-features, 2n o Z.. In addition, for all other nodes in V {u} {v) that want predict, they have self-features different from both Ey and Eg. Consider the following confidence function:
when x A 0 0, G(æ) = {1, when >> 0
(38)
Due to universal approximation theory (Hornik et al. 1989), we can have an MLP expert that differentiates nodes u and e based on their input features V. and By (and produces meaningful predictions not equal to 1,1,, while always producing A1 prediction for all other nodes. In this scenario, for u and u, the MLP's prediction exhibits positive dispersion, leading to G = 1. Consequently, the confidence function acts binary gate, completely disabling the GCN expert on and u. Otherwise, the MI.'ss prediction has zero dispersion, resulting in G 0. In this case, the confidence function entirely disables the MI. expert and relies solely the GCN expert. With this confi figuutttio,, both Mowst-GCN and Moust' -CNN can differentiate all nodes that a standalone GCN model can, and they can also distinguish nodes that any GCN model cannot vs. v). This demonstrates that Mowst-GON and Mowst*-GOK are strictly more expressive than a GCN alone. C
D.2.3 PROOF OF PROPOSITION 2.8
Proposition D.17. (Originally Proposition 2.8 Mowst and Mowst" are at least as expressive any expert alone.
Proof. The proof follows the idea of proving Proposition 2.6
The logic to prove the case of Mowst is identical to that of Mowst", and thus we only discuss the Mowst case in detail. Consider confidence function C' = o D defined as follows:
S0, when $ 0 G(w) - 1, when x: >
-{1,
(39)
Equation 44 defines the general form for Mowst consisting of M experts. The coefficient " :=
II (1- C. in front of the loss I represents the probability of activating expert m 15tcm
during inference. This setup allows us to easily generalize Algorithm | based on Equation To ensure that the entire Mowst system produces identical results as the m-th expert, we need to approximately show that TM = 1 for all e, and Th = 0 for m' # m (with some exceptions to be discussed separately).
For m' * m, we always let the expert m' to generate random guess of 11 for all v. Note that a _1 prediction corresponds to 0 dispersion, and thus the corresponding G and C' are also 0. A prediction not equal to 1 1 leads to positive dispersion, and thus a confidence of 1. Given the binary nature of our confidence values, achieve T 0 for some preceding expert to have C = 1 for some mn" < m'. To obtain T all preceding experts must have C for all m" < m', and Co
m' < M, we need C or at least one
for some 1 < m < M,
1.
According to the above categorization, for expert m' where m' < <,, we always have their Th 0 since C = 0. If expert m generates non- 11 prediction, then - = 1 and thus the whole Mowst system reduces to single expert m. If expert predicts 11, then The
(since by definition, C% 1 for all v). Since the expert M also predicts 1 11, the system's 's output is also equivalent to expert mns output.
Therefore, both Mowst and Mowst* can produce identical results any individual expert.
33

---

E ADDITIONAL ALGORITHMIC DETAILS
E.1 DERIVATION OF OPTIMIZATION PROBLEM
We re-write Toovet (Fquation] 1 follows:
LNowet
1
Σ
(1- L (p',, vo))
NEV
1
Σ (p:) (T. Uo) - T. (p',, yo)) + T. (p's yo))
|0
PED
Σ
(p.)) (L (pv. yo) - L (p',, yo)) + |
Σ WEF
L (p'. ye)
(40)
V
DEV
Since we optimize the MLP parameters by fixing the GNN, (p', yo) remains constant throughout the process. Therefore,
arg min LNovet arg min {
(p.) (L (p.. L (p'.. yo))
(41)
{p=} NEV
Now we simplify it follows:
Σ Cp.) (L... yo) (p'. yo))
NEV
E Σ (p.) (L (Pv. yo) L (p', yo))
ISism vEM;;
Σ ISiSm DEMM;
Σ
C(.) L (Pv. yo)
Σ
E
(po) L (p'.. ye)
IsiSm vem;
Σ ISism
(p.)
Σ mum
L (p:, vo)
Σ 1sism
c(i)
Σ Aum
L (p', Mo)
Σ
(
Σ
L (p:.
Σ (p': Bo)
Isism
WEm
VEM
Σ
((.)
(m.-) Prax, (p:)
-m7al 14
151sm
-m,l
Σ
(Φ.)
(has (D:) 11,)
(42)
15:5m
where Equation 42 (almost) exactly our objective in optimization problem with the only difference being the scaling factor [/],]. We can use the "decomposible" argument in D.1.3 to easily derive that this scaling factor does affect the optimizer p
E.2 EXTENDING TO MORE THAN TWO EXPERTS
Following the notations in
2.7 we first have the case of 3 agents:
Lygust
Σ
L - (1 (1 (3- -1)))
+1
V
BEV
(CT - -0000-1---0--00---00------------
(43)
M
DEU
34

---

In general, for M experts, have the following loss:
L LMosat
1
E Σ
II
C1-
(1
c?)
C. by
(44)
|
NEV I5m5M
M
[Isi<m
where we define Nagis (1 -)+) = We further define the following term:
for any integer x.
L
Σ 9SMSM
II (1 C?)
C Lm
(45)
gsism
Therefore, TMosst recursive formulation.
1 [
EvED 1 and 12 = C% L + (1 - C%) I 2g21 defines the basic
E.3
CALCULATION COMPUTATION COMPLEXITY
We provide more details to support the analysis on computation cost in 2.6 We derive the specific equations for computation complexity for various model architectures, including
Vanilla MIP
Vanilla GNN (with GCN and GraphSAGE examples)
GNN with skip connections
Mowst consisting of MLP expert, GNN expert, and an optional MLP for confidence computation
We further discuss how state-of- state-of-the-art the-art techniques for scalable and efficient GNNs improve the computation complexity of a vanilla GNN, but still fall short in making GNN as lightweight as an MI.. In summary, our analysis reveals the following:
A GNN, even when scaled up, is significantly more computationally expensive than an MLP.
A Mowst has a similar computational complexity to that of its corresponding GNN expert alone.
A GNN with skip connections remains substantially more expensive than a Mowst with an equivalent number of model parameters.
Our analysis justifies the claim that Mowst efficient, and our baseline comparison criteria fair
A.5
E.3.1
SETUP
follow the same setup for computation complexity analysis as Zeng et al. (202T), where we analyze the total number of arithmetic operations needed to generate prediction for one target node during inference. Note that:
We focus on inference since the exact equations for training are hard to derive without strong assumptions about the specific training algorithm and convergence behavior. The conclusions from our following analysis apply to the training costs as well.
Batch processing group of target nodes may help reduce the computation complexity but its benefits tend to diminish on large, realistic graphs (Zeng et al. 2021). In addition, the benefits of batch processing strongly depend on both the graph connectivity pattern, and the neighborhood similarity among the same-bate batch target nodes (Fey et al.) 202I). Thus, similar to Zeng et al. (021), only consider the case for each individual target node.
35

---

Notations. Denote l as the total number of layers, and f as the hidden dimension (for simplicity, we assume that all layers have the same hidden dimension, and the raw node features are also of dimension f).
Denote ft" as the set of direct neighbors node e, excluding v itself (i.e., a node in 77" is connected to via an edge). Denote ??,' the set of v's neighbors within i hops, Le., n. consists of all nodes that can reach v in no more than hops. For instance, 7? = 77" U {u). Denote by = [ as the number of v's neighbors within i hops (e.g., bj = and by equals v's degree plus 1). Denote x; E R as v's embedding vector input to layer i. Denote W; E / as the weight parameter matrix of layer Denote 7 the computation cost measured by total number of mulippiicatoonaaccumllaaiio operations.
Simplifications. In the following calculation, we omit the non-linear activation and normalization layers, as their computation cost is negligible compared with the GNN and MLP layers.
E.3.2 COMPUTATION COST OF MLP
Each layer performs the following computation:
W x
(46)
As result, the number of cuttippicaatio-accumllala operations (corresponding matrix multipli- cation) equals f². For all layers, the total computation cost equals
MMP = f
(47)
E.3.3 COMPUTATION COST OF GNN
The GNN performs recursive neighborhood aggregation generate the embedding for the target node v. Specifically,
The é-th (i.e., last) layer aggregates information from v's I-hop neighbors 111 and outputs single embedding x for itself.
The (L - 1)-th layer aggregates information from v's 2-hop neighbors n2, and outputs b embeddings for each of u's 1-hop neighbors 77.
The first layer aggregates information from v's E-hop neighbors ny. and outputs by_1 embed- dings for each of v's (E hh-h neighbors 17
Mathematically, we formulate the layer operation follows:
UPDATE (x) AGGREGATE ((zi-1lu 12"1))
(48)
where the function AGGREGATE (-) aggregates the llyvious-layer embedding vectors of e's neighbors, and the function UPDATE (-) performs transformation on v's own embedding vector from the last layer, well as the aggregated neighbor embedding. Different GNNs have difference choices of the UPDATE (.) and AGGREGATE (.) functions. addition, to implement skip connection, we can let UPDATE function specifically operate x;-
Note that for layer i, each of its output nodes in ny- will exccute Equation Therefore, we describe the general layer operation follows: the i-th GNN layer
aggregates information from nodes in 77 into bY_, intermediate embeddings,
updates the intermediate embeddings and self-embeddinng of ny and
outputs embeddings for nodes in n
36

---

We ready to study the computation cost for two specific GNN architectures, GCN (Kipf & Welling 2016 and GraphSAGE (Hamilton et al. 2017
Both GCN and GraphSAGE implement AGGREGATE (-) weighted sum of the neighbor embed- dings. Thus, layer gathers the previous-layee embeddings of 11 and reduces them into by-; aggregated embeddings, via vector summation. Since AGGREGATE (-) only involves addition but no compu- tation cost definition (recall that for computation cost, we only count one multiplication-accmmilll
multiplication, its cost is much lower than UPDATE (.), and should be ignored according
unit cost, which is consistent with Zeng al. (02I)).
After AGGREGATE/ (-), both GCN and GraphSAGE implements UPDATE (.) as linear transformation via the layer's weight matrix. The difference is that for GCN, each layer only has single weight matrix operating on the aggregated embedding (i.e., output of AGGREGATE (-)). For GraphSAGE, each layer i has weight matrices, operating on the aggregated embedding vector and æ; respectively, The two embedding vectors after GraphSAGE's linear transformation are added to generate the final x; The computation cost for layer of GCN's UPDATE (+) function is thus f by- The computation cost for GraphSAGE, is doubled matrices. For all l layer, we omit the cost of AGGREGATE (-) as discussed before. Therefore, the total computation cost equals
f2 be=; due the operation from two weight
GGN f. Σ beii
(49)
1sisE
GGBpSAGG 2f2.
Σ
beー
(50)
Isist
where b denotes the average number of (E i)-hoop neighbors among all target nodes.
In 2.6 we perform further simplification of Equations 49 and 50: note that Eisis be-i
b 25ise b 2 bi-1+ E2sise b1-1+e-1. Thus, the computation cost is asymptotically
2 (f (E bc
(51)
which is the same as the results in $2.6
In large, realistic graphs, the number of (-hop neighbors target node can grow exponentially with f. For instance, in a social network, if one person has 10 friends, then he/she will have 10" friends of friends, and 10 friends of friends of friends. Such an exponential growth is commonly referred to as "neighborhood explosion" (Chen et al., 2018: Hamilton et al. 2017 Zeng et al.) 2020 |eyy et al. (02T) in the GNN literature. Consequently, a realistic GNN has much higher computation cost than an MIP: JGNN > TMLP since by_1 > f even for & as small as 2 or 3.
E.3.4 COMPUTATION COST GNN WITH SKIP CONNECTION vs. GNN WITH MLP EXPERT
First, let us derive the computation cost of Mowst with an MLP expert and GNN expert. For target node, the MLP expert only operate on the node itself, resulting in cost of f² as per Equation 46. If there is learnable confidence function implemented by another MLP, its cost is also f² assuming this MLP has the same architecture as the MI.P expert (as set up in (3) The cost of the
GNN expert is given by Equations 49 50 and 51 Therefore, the computation cost of Mowst can be estimated as:
Complexity of other architectures be derived similarly. We omit the details avoid redundancy. 'The original GraphSAGE (Hamilton et al. 2017) paper has proposed variants of AGGREGATE (-) and UPDATE (-). The version described here is the most common one (see for instance, the default implemen- tation from PyTorch Geometric https::/pttorchh.otttt www.eetrrreeeereoroooooo. cafic.rees readthedosss i oo/e//11 /ltetttt/ generatee//orrchgeoome
www.CONV. htm and also used in our experiments.
37

---

Moxst-GCu 2 f
Σ
b YGON
(52)
isise
Mowst-SABE R 2f
Σ
be- GGrppSSGG
(53)
1sise
(54)
where the second ">" is again due to b > L.
Now let us consider single GNN model with skip connection in each layer. As shown by the description regarding Equation 48 a skip connection can be implemented via specific UPDATE (-) function. If the skip connection implements linear transform on the self-features generated by the previous layer (i.e., x of Equation 48), then GraphS AGE discussed in F.3.3 already implements the skip connection.
Note that adding skip connection will increase the cost of UPDATE (-) due to additional linear transformation. The more expensive UPDATE (-) will applied on all the (e 1)-hop neighbors of the target node Thus, adding skip connection significantly increases the computation cost of a GNN. Specifically, note from Equations 49 and that GraphSAGE twice as expensive as GCN. The "2" factor is exactly due to the skip connection. Similarly, if we modify the GCN architecture by adding a skip connection each GCN layer, we will have "GCN skip
2GGCN-
Remark. From the architecture perspective, adding skip connection in each GNN layer can be seen as breaking down the MLP expert of Mowst and fusing each MLP layer with each GNN layer. However, from the computation lower cost than GNN + skip connection. The fundamental reason behind the gap in computation cost that the skip connection increases the cost on all neighbors, while the MLP expert only introduces overhead on the target node itself.
perspective, Mowst model with MLP GNN has much
E.3.5 SCALABLE GNN TECHNIQUES
Note that many techniques have been proposed to improve the scalability of GNN, including neighbor
sampling (Hamilton et al.) 2017 Ying et al. 2018), subgraph sampling (Zeng al. 2020 Gasteiger jet al., (022) and historical embedding reuse (Fey et al.) 2021 Shi et al.] 2023). Scalable GNN techniques may reduce the GNN computation cost derived in |E.3.3] but a scalable GNN will still be much more expensive than an MLP. We give a brief summary of the reasons:
Even with aggressive sampling, the neighborhood size will still much larger than 1.
Many sampling techniques (Hamilton al. 2017 (Shi al. 2023 Ying al. 2018 Fey et al., 2021 Zeng et al. 2020) aim to approximate the aggregation on the full neighborhood. Thus, sampling trade offs accuracy for efficiency. In addition, many sampling algorithms impose strong assumptions on the neighbor aggregation function.
Many scalable GNN techniques apply only to the training phase (Zeng et al., 2020 Shi et al.. 2023
2 and, such, do not address the computation challenges during inference. Fey al.
GPUs are inefficient in processing graph data due to the sparsity and irregularity of edge connections. As result, GPU utilization is significantly lower when running GNN (whether scalable or not) compared to running an MLP.
F A STUDY ON "FAILURE CASES"
We present an analysis on how Mowst can handle two typical "failure cases" by adjusting the predictions of the MLP expert and the shape of the confidence function during training.
F.1 WHAT ARE THE TWO TYPICAL "FAILURE CASES"?
Our goal here is not to exhaustively address all possible corner cases. Instead, we focus on typical failure cases that may controversial to aid understanding the interactions between experts.
38

---

Considering the overall training objective in Equation I the intuitive "success cases" should be:
Low MLP loss with high confidence: confident & correct MLP predictions
High MLP loss with low confidence: unconfident & incorrect MLP predictions
Therefore, the typical failure cases are essentially the opposites of these success cases: (I) Confident & incorrect MLP predictions, and (2) Unconfident & correct MLP predictions.
Given that we are considering two experts, we can refine the failure cases by taking into account the relative strengths of the experts:
Case Confident incorrect MLP predictions correct GNN predictions;
Case 2: Unconfident & correct MLP predictions + incorrect GNN predictions.
Side note: Nodes associated with Case I should have different self-features compared to those associated with Case 2, otherwise their confidence levels would be identical.
Since the balance between the experts is ultimately determined by the loss, we quantify each term in Equation I
Case 1: High C; high LMPP; low (1- C); low LGNN-
Case Low C: low LMLP; high (1 - C';; high LGNN.
where LMLP and LGNN denote the MLP loss and GNN loss terms in Equation respectively.
F.2 HOw DOES MOwST ADDRESS THE "FAILURE CASES"?
Observation:
The commonality between the two failure cases is that for one expert, both its loss and the weight coefficient in front of the loss are high. To address the failure case, the Mowst training should be able to either reduce the loss, OR reduce the weight coefficient.
In summary, Mowst will take the following steps:
(1) Update the MLP model to make the predictions for the case nodes closer to random guess.
(2) Update the confidence function to give it "over-confident" shape, increasing the C value for the case nodes.
independent. Step 1 is straightforward for MLP, will not significantly affect predictions for case 2 nodes. In Step 2, an "over-confident" C' means it is easier for the MLP to achieve high confidence. For discussion, consider simple function where C(p) 0 if the dispersion of is less than r, and C(p) = 1 if the dispersion is greater than J. We can make C more "over-confident" with smaller т. This update affects for both case and case 2 nodes.
These steps
After executing both steps, we analyze the joint effect on case and case 2 nodes:
In step can reduce until the dispersion of the MLP's case 2 predictions higher than 7 (we can always do so since MLP's case predictions are correct by definition). Simultaneously, in step 1, we need to push the MLP's case predictions towards a random guess until their dispersion lower than (we can always do so since random guess has dispersion).
Net effect of reduced Mowst loss. Each term the loss changes after executing steps and 2. For case 1, C' will reduce (to 0 under example confidence function). LMLP will increase. The net effect is that the overall loss is reduced: we now have L'
LALP + (1 (1-O) 0) LGNN = LGNN (by definition of case 1, LGNN is low). For case 2, C' will increase (to I under example confidence function). LMLP will remain the same. The net effect is that the overall loss also reduced: L'Mowet LMLP + (1-1) LONN LMLp where LMLP is low by definition of case 2.
Net effect of improved prediction behaviors. After jointly executing steps 1 & 2:
For case 1, the MLP has unconfident, incorrect predictions.
39

---

For case 2, the MLP has confident, correct predictions.
Thus, through Mowst training, we have successfully converted the two typical failure cases into two success cases.
G DESIGN CONSIDERATIONS
G.1 ORDER OF EXPERTS: MLP-GNN VS. GNN-MLP
With weak expert and strong expert, ordering possibilities for the mixture exist: ML.P GNN (our design) and GNN-MLP (alternative design).
In general, let consider experts A B. According to the analysis in 2.. (especially the last paragraph), when we compute confidence based on expert A, Mowst will be biased towards the other expert In other words, on some training nodes, if expert achieves lower loss, then Mowst will likely accept predictions from B and ignore those from A. Conversely, when expert A achieves lower loss, Mowst may still have some non-zero prohability (controlled by the learnable C)) to accept B's prediction. When B is the stronger expert with better generalization capability, the above bias is desirable when applying Mowst to the test set. Since GNN generalizes better (Yang et al. (023), we prefer the MLP-GNN order (current design) over GNN-MLP (alternative design).
G.2 NON-CONFIDENCE- BASED GATING
Consider a learnable confidence function C' implemented by an MLP. To create a non-confidence- based learnable gating module, we can modify the MLP for by replacing its dispersion-bais based input with the raw input features of the target node. This modified gating module would then output weights for each expert instead the confidence C.
The gating modules in existing Mixture-of-Exxe Expett systems (e.g., Shazeer et al. (017);; Wang et al. (2023)) resemble the above proposed gating module. Theoretically, such a gate can also simulate our confidence function the initial layers of this alternative gating neural network can learn to precisely generate the prediction logits of the MLP expert, while the remaining layers can learn to calculate dispersion and the G function. In this sense, confidence module can be gate, which is significantly simplified based on the inductive bias of the weak-strong combination. Our confidence-based gating makes the model explainable ($2.3 224). expressive and efficient ($2.6). More importantly, it enables Mowst to achieve significantly higher accuracy than GNNs based on traditional gating (e.g., GraphMoE (Wang al. 2023). Table Th due to our simplified design.
specific type of
H LIMITATIONS & BROADER IMPACT
H.1 LIMITATIONS
Our design is fundamentally driven by the goal of improving model capacity without compromising computation efficiency and optimization quality. Therefore, there are no apparent limitations to applying our model. Due the low computation complexity the weak MLP expert, the overall complexity of Moust is comparable to that of a single GNN model, ensuring that the increased model capability does come at the cost of more computation. Furthermore, the GNN expert can also be optimized individually following Algorithm 2 allowing the convergence of Moust to be as good as the baseline GNN. Additionally, since our conhdence mechanism is applied after executing the entire expert models, there are minimal restrictions on the experts' model architecture. For instance, on very large graphs, we can easily apply existing techniques to scale up the Mowst computation, such neighborhood (Hamilton et al.) 2017 Ying et al.) 2018) subgraph sampling (Zeng al. 2021 Gasteiger et al. 2022) commonly seen in scalable GNN designs.
An interesting question explore is under what types of graph structures Mowst would be most effective. For instance, understanding the properties of the graph that determine the experts' special- ization and measuring the relative importance of features and structures would be valuable. Moreover, identifying suitable choices for weak and strong experts in non non-graph domains (e.g., time-series analysis, computer vision, etc.) is an intriguing direction for future research.
40

---

H.2 BROADER IMPACT
In 22.7 we have discussed interesting extension of Mowst into multiple (more than 2) experts. Here, explore the potential of broader impact of this direction:
Graph learning task. Within the graph learning domain, there are two approaches to selecting "progressively stronger" experts for multi-expert version of Mowst:
(1) One simple way is progressively make the GNN deeper. For instance, MLP can be considered as a O-hop GNN, so we can implement expert as a GNN that aggregates i-hop neighbor information.
(2) Another approach is from the architectural perspective. Some GNN architectures theoretically more expressive than others. For instance, simplified GNN models like SGC intermediate expert between weak MLP and strong
(Wu al. 2019) could serve GCN. Alternatively, following general theoretical frameworks (e.g., (Zhao et al. (021)) to construct GNNs with progressively stronger expressive power is possible. In this case, stronger expert does not necessarily have more layers.
The choice of progressively stronger GNN experts should depend on the graph's properties. For example, if information from distant neighbors is still useful (Alon & Yahav 202I), it makes sense to follow direction and create deeper experts. Otherwise, if most useful information is concentrated within shallow neighborhood (Zeng al. 2021), following direction 2 to define stronger experts with more expressive layer architectures may be more appropriate.
Other domains. The concept of weak and strong experts perfectly holds in other domains. such as natural language processing and computer vision, e.g., experts may take various forms of Transformers when considering NLP tasks. From our theoretical understanding in we know that the design of the many-expert Mowstis not tied any specific model architecture, suggesting significant potential for generalizing Mowst beyond graph learning. Moreover, the benefits of multi-expert Mowst could be more pronounced when dealing with complex data containing multiple modalities (e.g., graphs with multimedia features (Lyu Luo 2022). opatio-temporal graphs (Guo et al. 2019). etc.).
Hierarchical mixture. Besides the model extension proposed in 2.7 another straightforward way integrate multiple experts to construct hierarchical mixture using the 2-expert Mowst. The strong expert in the 2-expert Moust can be any existing MoE model, containing several "sub-experts" controlled by traditional gating modules (e.g,, symmetric softmax gating). The interaction between the weak expert and the strong expert remains governed by the cecdddene-bbseee gating.
41


Reviews:
[{"review_id": "MCksgXeUb0", "reviewer": "Reviewer_BGLX", "summary": "The heterogeneity of node classes raise unique challenges to message passing graph neural networks. Iterative aggregating neighbors can magnify the negative impact of dissimilar nodes on the representation quality. This work tries to deal with this problem by decoupling node presentation into MLP and GNN. MLP mainly captures node-self property and receives much more less impact from neighbor than GNNs. With the help of confidence value calculated based on the output logits of MLP, the proposed approach tends to obtain a better balance on the predictions between homophilous and heterophilous nodes.", "questions": "please refer to question above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Strengths:\n1. This work proposes to combine MLP and GNN for balancing the predictions for homophilous and heterophilous nodes.\n2. Authors add theoretical analysis that are trying to fold out more insight to show the superiority of the proposed loss.\n3. Experiments are conducted on various scale of datasets to demonstrate the performance of the proposed method.", "weaknesses": "Weaknesses:\n1. The presentation quality still has lots of space to improve. That's also the main drawback of this work. The motivation is not clear enough. I guess that the main motivation of this work is about how to overcome the challenges raised by heterophily since most of GNNs work well on homophily network. But there is no literature overview on overcoming heterohpily in the related work section. Moreover, no baselines for dealing with heterophily are included in the experimental section. It's better to illustrate the diagram of learning objective to show how the MLP and GNN collaborate to each other, since they are not applied to mode layers.\n\nApart from the missing literature, many claims in this work are not clear. Here a incomplete list. \n  - \"GNNs are both expensive to compute and hard to optimize\". By far, many efficient way to run GNNs are already proposed and applied to solve industrial problems. It should not be the main drawback of advanced GNN layer or model. Comparing with MLP, GNN indeed requires more computation cost, but we still have solutions to make it applicable to deal with large scale data. With the claim, what is it relation to the proposed method? It's difficult see that the proposed method has dominated advantage in terms of time complexity since it still relies on the GNN. \n   - \"a cluster of high homophily, the neighbors are similar, and thus aggregating their features via a GNN layer may not be more advantageous\". The \"similar neighbors\" should be more clear. Assume that this work mainly focuses on node classification according to the experimental tasks, similar neighbors tend to have the same class, but not mean that they should have close similar feature distributions. In this case, aggregating neighbors could bring missing information to the target node for better classification performance.\n  - \"The MLP can help “clean up” the dataset for the GNN, enabling the strong expert to focus on the more complicated nodes whose neighborhood structure provides useful information for the learning task. \" Could you please explain why a weak classifier can provide high-quality dataset for GNNs? From the information presented in this work, I guess it's just use the classification confidence distribution. Suppose that the cleaned nodes by MLP are those the low-quality nodes that have heterophilous neighbors, can the GNNs still distinguish them?\n  -  \"since the confidence score solely depends on MLP’s output, the system is biased and inherently favors the GNN’s prediction. However, such bias is desirable since under the same training loss\". It's difficult to follow the statement. Could you please explain the system is biased by what? why it favors the GNN prediction and the bias is desirable?\n  -  \"Second, our model-level (rather than layer-level) mixture makes the optimization easier and more explainable.\" What is the difference between model- and layer-level mixture, and why the optimization is more easier and explainable?\n  - \"During training, the system dynamically creates a soft splitting of the graph based on not only the nodes’ characteristics but also the two experts’ relative model quality.\" The splitting of graph is difficult to follow, is the graph divided by nodes or edges?\n\n2. The theoretical analysis can be further improved. For me, it's difficult to follow the conclusion from the series of theorems. It comes with weak connections to the proposed learning objective. It's better to make the point stand out with a clear statement, such as the convergence, stability of confidence value, insight about how to select probable confidence value function. By the way, the exact definition of the confidence value function seems to be missed.\n\n3. The experimental results are incrementally improved comparing to previous methods. Typical baselines for overcoming heterophilous issue are ignored, such as but limited to $H_2$$GCN [1].\n\nReferences:\n1. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs, NeurIPS 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "112G7B66Pp", "reviewer": "Reviewer_3gAn", "summary": "The Mowst approach is a novel way of handling self-features and neighborhood structures in GNNs, using a mixture of weak and strong experts with a confidence mechanism to activate the strong expert in low-confidence regions. The authors demonstrate Mowst's effectiveness on multiple benchmark datasets and provide an analysis of its expressive power and computational efficiency. The contributions of the paper encompass an innovative mechanism for expert collaboration, a variant of Mowst designed for directed graphs, and insights into the training dynamics that foster expert specialization and the gradual partitioning of the graph.", "questions": "- How does mowest solve the scenarios where MLPs can exhibit both incorrect predictions and high confidence levels?\n- How do the alternative design choices  (in Weakness 2) compare to mowest?\n- What are the performances of Mowst*-GIN and GNN+MLP sc on Table 2?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-written and organized, with clear explanations of the Mowst approach and its variants.\n- The experiments are comprehensive, with ablation studies on several design choices", "weaknesses": "**Failure cases**: MLPs can exhibit both incorrect predictions and high confidence levels. This is particularly common when dealing with graph datasets featuring imbalanced classes or containing a small number of outlier nodes that may not be sufficiently representative. The authors didn't discuss the limitations of such cases and how mowest may or may not solve them.\n\n**Clarity:** There are several different design choices other than the proposed version. For instance, the authors do not provide a justification for positioning the weak expert at a lower order while placing the strong expert at a higher order. An alternative approach could involve computing confidence using the GNN and then determining the weight for further combining the MLP results. Another version might not involve confidence computation but instead rely on a learnable module to decide which expert is more suitable. Supervision can be obtained through self-supervision, i.e., comparing with a previously trained MLP and a GNN in terms of predictive accuracy on each instance.\n\n**Experimental justification:** The paper lacks results for Mowst*-GIN in Table 1. Including these results would be valuable for assessing whether Mowst can further enhance performance, especially since GIN is the top-performing model on Penn94. Moreover, demonstrating how Mowst can complement different GNN architectures would strengthen the assessment of its utility.\n\n**Experimental comparison:** It may not be fair to compare Mowst with either MLP or GNN in isolation. A more informative comparison could be made between Mowst and a GNN with an MLP skip connection since both have similar expressiveness (theoretically, when the strong expert is activated) and the same number of model parameters.\n\n**Minor:**\n\nIn the abstract, the authors mentioned \"GNN\" before \"... the strong expert is an off-the-shelf Graph Neural Network (GNN).\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ePywt11mB", "reviewer": "Reviewer_DN88", "summary": "This paper introduces a new method named Mowst for processing graphs, which decouples node features and neighborhood structures by employing a mixture of MLP and GNN. These two models are coordinated through a \"confidence\" mechanism that activates the GNN when MLP is uncertain, indicated by the spread of prediction logits.  Empirically, Mowst has proven to enhance accuracy on various node classification benchmarks and operates with a computational cost on par with a single GNN model.", "questions": "1. Are there experimental results show that the superior performance was due to the integration of weak and strong experts?\n\n2. How is the network in each dataset constructed? What are the features attributed to the nodes within these datasets.?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This authors introduced a new method named Mowst that structures by employing a mixture of MLP and GNN. \n\nThe proposed method outperform existing methods in the experiments.", "weaknesses": "The manuscript would be improved if the authors could more clearly explain the reasons behind the superior performance of their proposed method compared to existing ones. They attribute their success to the integration of weak and strong experts; yet, it appears that the true advantage may lie in the combination of Multilayer Perceptrons (MLPs) and Graph Neural Networks (GNNs). The distinction is that while MLPs leverage features of individual nodes, GNNs also capitalize on information transmitted across edges. This, I believe, might be the actual contributing factor to their method's effectiveness. To substantiate their claims, the authors should consider conducting additional experiments. Specifically, they could compare the performance of a combination of shallow and deep MLPs, as well as  a combination of shallow and deep GNNs. Such experiments would provide a more convincing validation of their results.\n\nAdditionally, the introduction to the datasets used in the study requires enhancement. The authors should provide a detailed description of how each network dataset is constructed and clarify the specific features attributed to the nodes within these datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x6XPiJl2dp", "reviewer": "Reviewer_MV5e", "summary": "The paper introduced a mixture-of-experts design to combine a weak MLP expert with a strong GNN. The proposed method relies on a confidence mechanism for controlling the contribution of each expert. The idea is to leverage the MLP for learning from nodes with self-expressive features that do not gain much from its connections and largely resort to the GNN for other cases. Their experiments show the superior performance of their method which is also well supported by several theoretical proofs.", "questions": "1. Is there any correlation/relationships between the edge density of the graph dataset and performance of the MLP part of the method? Intuitively, if the graph is sparsely connected, one may assume that the MLP contributes more in that case compared to when the graph is densely connected. \n2. What is the $\\circ$ symbol in Proposition 2.2? It has not been defined. \n3. The task for the experiments mentions \"node prediction\". Do the authors mean it's a node classification task?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles an interesting problem and proposes a relatively simple solution of mixing a weak model like MLP with a strong expert like GNN. \n2. The method is fairly intuitive and the paper is easy to follow. \n3. The proposed method is very effective as shown by the experiments. The experimental setup is extensive and shows the effectiveness of the method in several aspects including ablation study, visualization of learned embeddings and training dynamics.\n4. The paper is theoretically well-supported through theorems and propositions.", "weaknesses": "1. Although it has been briefly mentioned in supplementary section C2, it would be interesting to study the effect of the number of experts on the performance. This leads to further questions regarding the choice of multiple weak experts vs multiple strong experts. Is this even helpful in the given task? I think these are interesting follow up questions one could ask.\n2. The github page with code base is private and not accessible via the provided link. \n3. Minor grammatical and spelling errors which need to be improved. \n4. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wxve1lfL1i", "reviewer": "Reviewer_SJRD", "summary": "This paper introduces a novel prediction strategy designed for scenarios where the model inputs are graphs.  The authors try to improve the model's capacity in graph neural networks (GNN) without raising the computational costs. For making predictions, they introduce two experts: a basic Multi-Layer Perceptron (MLP) and an off-the-shelf GNN. The collaboration between these experts follows a system known as the mixture of experts (MoE), which is referred to as the confidence mechanism.  This gating scheme determines which expert's prediction should be chosen. The proposed solution employs two algorithms for both inference and training. During inference, a prediction is generated for each node, while during training, the MLP and GNN models are updated. The authors demonstrate the superiority of their proposed solution on node classification benchmarks for both homophilous and heterophilous graphs.", "questions": "See discussions in the weakness section.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper addresses a significant and challenging problem in graph neural networks: model capacity. It demonstrates good quality, offering clear explanations for mathematical aspects, and the appendix provides helpful content. The technical details of the proposed solution are well-explained. The idea of converting the prediction task into an ensemble technique (here mixture of experts, MoE) is impressive. Although the conventional MoE is not a novel method, model ensemble on graphs has received much attention in recent years.", "weaknesses": "The paper, in its current state, exhibits several deficiencies that require attention from the authors. The most significant issue with the paper is the absence of a clear presentation of the details of the proposed solution.\n\n- A Minor Issue: A minor issue I've observed in the paper is that on two pages, a significant portion of the content is dedicated to citations and references rather than the core content. On page 1, approximately 40 percent of the introduction is occupied by references, and a similar issue is present on page 6, where content presentation heavily relies on citations. While I understand that this issue may be related to the template used, it can inconvenience readers who may not wish to review all the references. It would greatly benefit the paper if the authors could pay attention to this issue to enhance the reader's understanding.\n\n- An important source of ambiguity arises in Algorithms 1 and 2. Algorithm 1 is responsible for generating predictions using the MLP or GNN, whereas Algorithm 2 focuses on estimating the parameters of the networks. The paper lacks clarity regarding the process when the MLP and GNN have not been trained, and Algorithm 1 does not contain an initialization step for their parameters or hyperparameters. It is imperative that the paper defines the interaction and collaboration between these two algorithms to address this issue. In particular, it is crucial to explain how Algorithm 1 can produce predictions when the experts have not yet been trained.\n\n- The loss functions in (Eq.1) and (Eq.3) play a crucial role in the training process, as they are meant to be minimized. However, an issue arises in these loss functions because all elements within them are known. Specifically, the confidence, and predictions of both experts and the true labels are all given. Algorithm 1 is responsible for generating confidence and predictions, while the true labels are known. This results in the loss function having a fixed value, and it remains unclear with respect to which parameters the minimization task is intended. As a result, the loss function appears to be independent of the experts' parameters. The paper should address and clarify this issue to ensure a proper understanding of the optimization process.\n\n- Confidence mechanism C: The paper introduces a novel gating variable, referred to as confidence, which holds promise for providing appropriate weightings in the Mixture of Experts (MoE) framework. However, a significant concern arises with the use of the random value q. The strategy resembles sampling techniques such as Metropolis-Hastings, where an acceptance ratio is compared with a generated uniform random number. Nevertheless, the fundamental problem here differs as the model's goal is to choose between experts. While the paper presents an innovative confidence mechanism, it ultimately compares it with a completely random value. This approach may not be a precise method for selecting one of the experts, as the confidence mechanism is inherently tied to the experts' predictions, while the ratio q is an independent value. The paper should address this issue to ensure a more reliable method for expert selection.\n\n- Limitations of the proposed solution based on MLP and GNN: It's important to note that available baselines often face challenges when dealing with graph inputs and have their own limitations. The paper introduces two experts, MLP and GNN. However, the use of MLP as an expert should be explored more thoroughly in the paper, particularly due to its potentially weak prediction quality. For example, if Algorithm 1 consistently generates small values for q, resulting in MLP being selected in most cases, questions arise about the guarantee for the prediction quality of the $M_{owst}$ method. Additionally, the paper should delve into the main advantages of using MLP compared to other potential candidates. The current discussion in the paper does not adequately address this scenario. On the other hand, the limitations of using an off-the-shelf GNN have not been sufficiently discussed. The paper should elaborate on how employing GNN as an expert can effectively address its known limitations. A more comprehensive discussion in these areas is necessary to provide a well-rounded understanding of the model's capabilities and potential challenges. \n\n- Computational complexity: While the paper briefly touches upon the complexity of the proposed model, it is imperative to provide a more comprehensive analysis of its computational efficiency, especially within the experimental context. The Abstract highlights the efficiency of the $M_{owst}$ method, making it essential for the authors to include sensitivity analyses related to the model's complexity in the experiments. This would help in quantifying the trade-offs between model performance and computational resources. Furthermore, the cost associated with the confidence mechanism, even if estimated using a simple MLP, should be clearly explained in the paper. Precise details on the computational cost will aid readers in understanding the practical implications of implementing this mechanism. Providing a more in-depth discussion and analysis of these aspects will enhance the paper's completeness and help readers assess the practical feasibility of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6DS4dfHwNt", "reviewer": "Reviewer_jetB", "summary": "In this paper, the authors leverage the idea of using mixture-of-experts models to improve the model capacity for graph neural networks (GNNs). Since the GNNs are both expensive and hard to optimize, the authors propose mixing a light-weight multi-layer perceptron (MLP), with an off-the-shelf GNN rather than modeling each expert as a GNN. Here, the MLP specializes in extracting the rich self-features of nodes and it is referred to a weak expert, while the GNN exploits the structure of neighborhood and is called a strong expert. To aggregate these two models, the authors introduce a biased gating function towards the GNN predictions based on a novel \"confidence\" mechanism, and name this model \"Mowst\"\n\nFor inference, the authors run the weak expert first and obtain a prediction. If the confidence score of that prediction exceeds some random threshold, then it is selected as the final prediction. Otherwise, they continue to run the strong expert, and use the prediction of that expert.\n\nFor training, they propose the loss function $L_{Mowst}$ by firstly computing the losses of two experts separately, and then combining them via the confidence function $C$.\n\nIn addition, the authors also introduce a variant of the Mowst model in which they use the confidence function $C$ to combine the predictions of the two experts, and then calculate a single loss.\n\nThe authors demonstrate that both models are at least as expressive as the MLP or GNN alone but with a comparable computional cost. Finally, they empirically show that these models have significant accuracy improvement on 6 standard node classification benchmarks.", "questions": "1. Below Proposition 2.2, the authors should either present formal formutions of variance and negative entropy functions or give references for these functions.\n\n2. In Section 2.3, are indistinguishable self-features are necessarily the same? The authors should explain more about the term 'indistinguishable'.\n\n3. In Proposition 2.5, does the loss function $L_{Mowst}$ upper bound its counterpart $L^*_{Mowst}$ for any choice of confidence function $C$?\n\n4. In Proposition 2.6 and Theoremm 2.7, the authors should illustrate the concept of expressiveness mathematically. \n\n5. At the end of page 1, the authors claim that the sparse gating function may make the optimization harder due to its discontinuity. I would like to emphasize that not all sparse gating functions are discontinuous. For instance, a temperature softmax gating function in [1] is a sparse yet continuous gating function.\n\n6. Could the authors please explain more clearly why the MLP denoises for the GNN during training?\n\n7. In Algorithm 2, what methods do the authors use to learn the MLP weights and the GNN weights? And what are the convergence rates of those parameters?\n\n8. Why do the authors need the confidence $C$ to be quasiconvex? What happens if $C$ is not quasiconvex?\n\n9. What are the main challenges of using the Mowst model?\n\n10. In Section 3, the authors should cite more relevant papers regarding symmetric gating functions in mixture-of-experts models, namely [1], [2], [3], [4]. \n\n**Minor issues**:\n\n1. The abbreviation 'GCN' in page 6 has not been introduced.\n2. Grammatical errors: 'the number graph convolution' (Section 1).\n3. After the statement of each result, the authors should give references to location (within the paper) of the corresponding proofs.\n\n**References**\n\n[1] X. Nie. Dense-to-Sparse Gate for Mixture-of-Experts.\n[2] H. Nguyen. A General Theory for Softmax Gating Multinomial Logistic Mixture of Experts.\n[3] H. Nguyen. Statistical Perspective of Top-K Sparse Softmax Gating Mixture of Experts.\n[4] H. Nguyen. Demystifying Softmax Gating Function in Gaussian Mixture of Experts.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. Originality: the idea of using mixture of weak and strong experts with the confidence mechanism is novel.\n2. Quality: the authors provide both theoretical and empirical results to demonstrate the effectiveness of the proposed model \"Mowst\".", "weaknesses": "1. Clarity: the paper is not well-written. \n- The authors should emphasize the problem they would like to solve more clearly in the introduction section. \n- The presentation of all propositions and theorems is informal. Additionally, the statements of Propositions 2.5, 2.6, 2.7 are so confusing (see Question section).\n- The notations used in this paper are difficult to digest (see Theorem 2.4 and Corollary 2.4.1).\n\n2. As far as I understand, with the confidence gating function, we can only leverage two experts in the Mowst without being able to use multiple experts as in previous work. Therefore, the ability to scale up the model capacity is quite limited.\n\n3. The experiments in Section 4 do not show the ability to scale up the model capacity of the Mowst model and its variant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)