Graph that models interacting entities is ubiquitous in real-world applications, e.g., social networks (Perozzi et al., 2014), citation networks (Hamilton et al., 2017), and molecular modeling (Gilmer et al., 2017). The predominant message-passing graph neural networks (MP-GNNs) -based on local message-passing mechanisms -are effective in leveraging inductive bias of graph structures, excelling in graph deep learning (Duvenaud et al., 2015;Kipf and Welling, 2017;Gilmer et al., 2017;Corso et al., 2020;Satorras et al., 2021;Thorpe et al., 2022). MP-GNNs, e.g., graph convolutional network (GCN) (Kipf and Welling, 2017), usually update the features of each node by aggregating the features of its immediate (1-hop) neighbors. MP-GNNs encode the graph structure into their message-passing mechanism. Nevertheless, the locality of the message-passing in MP-GNNs can overlook the long-range interactions (LRI between distant nodes (Ying et al., 2021). The failure in learning LRI is problematic for many graph learning tasks. Taking the molecular property prediction as an example, while the molecular graph is typically represented as a covalent bond network with atoms directly linked through these bonds, the 3D folding of the molecule is also governed by long-range non-covalent interactions between distant atoms (Gilmer et al., 2017). This underlying principle of LRI's importance extends beyond molecules, finding relevance in areas like semantic segmentation label prediction in computer vision (Dwivedi et al., 2020) or robotics (Kurin et al., 2020).
Increasing the depth of MP-GNNs appears to be an obvious and plausible solution for learning LRI, as it allows the message to iteratively propagate to distant nodes. However, various studies have shown that deep MP-GNNs perform much worse than shallow models (Li et al., 2018;Oono and Suzuki, 2020). Furthermore, deep MP-GNNs are expensive in computational and memory costs, especially in the backward pass, which linearly scales with the number of layers. In the context of LRI learning, MP-GNNs are shown to have unsatisfactory performance (Ying et al., 2021). Therefore, improving message-passing mechanisms for MP-GNNs that can learn LRI effectively is desirable.
We present DRGNN -a new MP-GNN model for learning LRI effectively using a full (node) similarity matrix as the aggregation matrix for message passing rather than sparse adjacency matrices used in existing MP-GNNs. The full similarity matrix emerges from the Personalized PageRank matrix (Page et al., 1998) augmented by a rank-one matrix; see Equation 2in Section 3. However, directly using the full similarity matrix for message passing requires the prohibitive matrix inversion.
We address the computational challenges in matrix inversion by recognizing the monotonicity of the full similarity matrix from a monotone operator viewpoint; see Proposition 1 in Section 4. In particular, we reformulate the node representation -obtained from repeated message passing with the full similarity matrix -as the fixed point of an iterative equation. This idea aligns with deep equilibrium models (DEQs) (Bai et al., 2019(Bai et al., , 2022;;Pokle et al., 2022;Winston and Kolter, 2020;Gu et al., 2020;Baker et al., 2023), where the model's depth is task dependent. We notice that with a tailored design of the equilibrium equation (Equation 3in Section 4) and leveraging the Douglas-Rachford (DR) splitting (Douglas and Rachford, 1956), we can guarantee the fixed point exists and is unique and the computation of the fixed point can be computed efficiently without matrix inversion (See Subection 4.2.1). As a result, our model's computational complexity aligns with that of GCN. Moreover, DRGNN enjoys a constant memory footprint for backpropagation using implicit differentiation (Robinson, 1991).
We adopt the following notations throughout this paper: We represent vectors, matrices, and operators by lowercase boldface, uppercase boldface, and calligraphic letters, respectively. We use I n and 1 n to denote the identity matrix and all-one vectors of size n, respectively. We denote the adjacency matrix of graph G as A, and we use D to denote the diagonal matrix whose i-th diagonal element is the sum of the i-th column of A. For the augmented adjacency matrix, we introduce à = A + I n . For the normalized adjacency matrix, we use Ā = à D-1 to denote the random walk matrix and  = D-1/2 à D-1/2 to denote the symmetrically normalized adjacency matrix. We use the notation diag(B) to represent the vector of diagonal elements of B.
We organize this paper as follows: In Section 2, we discuss the related work. In Sections 3 and 4, we present the two key components of the proposed model. In Section 5, we present the experimental results on various benchmark graph learning tasks. Missing details and technical proofs are deferred to the appendix.
In this section, we review some related work. We first review some GNN models that expand the receptive field of message-passing beyond the immediate neighbors. We then discuss the fixed-point neural networks.
Multi-hop message passing: A particular idea to increase the receptive field of each node in MP-GNN is to employ higher orders of the adjacency matrices as the aggregation matrix (Wu et al., 2019;Gasteiger et al., 2019a,b;Zhu and Koniusz, 2021;Chien et al., 2021). A remarkable model is PPNP (Gasteiger et al., 2019a), which uses the personalized PageRank matrix (1 -α)(I n -α Â) -1 with α ∈ (0, 1) as its aggregation matrix. Using the Neumann expansion of the matrix inverse, represented as (1
we can deduce that PPNP's aggregation matrix attends to every node in the graph based on graph informed node similarities. However, the PPNP model is computationally expensive due to using the dense Personalized PageRank matrix. This challenge is further intensified when one seeks to stack multiple such layers to boost the expressivity of GNNs. To improve the efficiency of PPNP, Gasteiger et al. (2019a) further propose APPNP using a truncated Neumann approximation of the Personalized PageRank matrix. However, the truncated Neumann approximation inherently limits the receptive field of each node. This becomes particularly problematic when the depth required by the task is unknown. APPNP has been generalized in (Gasteiger et al., 2019b;Zhu and Koniusz, 2021;Chien et al., 2021) to incorporate generalized PageRank filters.
Graph Transformer: Transformer-based GNNs, e.g., (Dwivedi and Bresson, 2020;Ying et al., 2021;Kreuzer et al., 2021), leverage the self-attention mechanism between nodes and graph-related positional embeddings to learn node representations. Transformerbased GNNs enable full node connectivity and show remarkable performance in learning LRI (Ying et al., 2021). However, Transformer-based GNNs possess a weak inductive bias (Dosovitskiy et al., 2020); the positional embeddings may not reflect the graph structure, resulting in less meaningful attention weights. Moreover, the quadratic complexity of the self-attention mechanism makes Transformer-based GNNs computationally expensive even for moderately sized graphs.
There has been a line of works that learn representations as the fixed point of some equilibrium equation; see, e.g., (Bai et al., 2019;Gu et al., 2020;Bai et al., 2022). This approach results in expressive models with adaptive depth while maintaining a constant memory footprint using implicit differentiation (Robinson, 1991;Bolte et al., 2021). For the correct implementation and training stability of the fixed-point neural networks, one needs to ensure the well-posedness of the fixedpoint iteration -the existence and uniqueness of the fixed point. A general well-posedness result is established by Winston and Kolter (2020) that utilizes the monotone operator theory and allows us to use operator splitting schemes to find the fixed point. The fixed-point neural networks are versatile and competitive across various tasks including language modeling (Bai et al., 2019), semantic segmentation (Bai et al., 2020), optical flow (Bai et al., 2022), and diffusion models (Pokle et al., 2022).
In the context of graph learning, IGNN (Gu et al., 2020) is a fixed-point GNN where each iteration in the fixed-point solving process is modeled as a messagepassing step using the normalized adjacency matrix.
Given the fact that the memory cost in backward propagation in each message-passing layer directly scales with the number of edges and is linearly proportional to the number of layers, IGNN's constant memory cost is favorable for graph learning tasks. This is particularly true for graph learning tasks that require LRI as the necessarily increased depth of a typical MP-GNN model will incur a significant memory However, it is pointed out that IGNN's well-posedness constrains the choices of weight matrix and poses instability in learning LRI (Baker et al., 2023).
Spectral GNNs: Spectral GNNs have also been designed to learn LRI; remarkable examples include BernNet He et al. (2021) and ChebyNet Defferrard et al. (2016).
In this section, we discuss the motivation of the new aggregation matrix for message passing in our model. Consider a connected graph G = (V, E) with n nodesfoot_1 , one way to establish full node connectivity with the minimal extra computational cost is to utilize rank one matrices, e.g. 1 n 1 n 1 ⊤ n , which aggregates the averaged features of all nodes. However, the averaged feature is graph agnostic. Instead, one can turn to use the matrix J = 1 tr( D) diag( D1/2 )diag( D1/2 ) ⊤ to establish full node connectivity. Notice that matrix J accounts for node degrees; see the middle panel in Figure 1(b) for a visualization of using matrix J for a toy graph. We notice that rank-one modeling of the pairwise similarity has been used in efficient Transformers (Katharopoulos et al., 2020;Catania et al., 2023).
To further refine the above approach, we take inspiration from the Personalized PageRank matrix. Instead of directly relying on J for message passing, we integrate it into the Personalized PageRank matrix. This integration results in graph structure-aware full node similarities that are suitable for message passing between arbitrary nodes, as we will see later.
Modified Personalized PageRank matrix: Let Ā := Ã D-1 be the random walk matrix of the augmented graph G. The Personalized PageRank matrix Π ppr is characterized by the following equation:
where i x is the indicator vector of node x and α ∈ (0, 1) balances the random walk and restart probabilities. The Personalized PageRank matrix can be solved as Π ppr = (1 -α) I n -α Ā -1 . The entries of Π ppr represent nodes similarity characterized by the probability of reaching one node from another in a random walk with restart probability 1 -α (Fouss et al., 2016).
The Personalized PageRank matrix has been used in MP-GNN models, such as PPNP and APPNP (Gasteiger et al., 2019a). In these models, the random walk matrix Ā is replaced by its symmetrically normalized variant  = D-1/2 à D-1/2 . In our proposed DRGNN, we modify the Personalized PageRank matrix by additionally incorporating the rank one matrix J to enhance direct communication between distant nodes and to benefit the computational efficiency; see Section 4 for details. The modified Personalized PageRank matrix Π ppr satisfies
which resolves to:
(2)
The entities of Π ppr characterize node similarities that are influenced by the graph structure with coefficients that balance the random walk, restart, and (degree weighted) global average. The matrix Π ppr enables multi-hop message-passing using a single MP-GNN layer, which follows from Neumann series expansion:
We illustrate matrix Π ppr in a simple graph in the right panel of Figure 1(b). However, as encountered in PPNP (Gasteiger et al., 2019a), computing the inverse of (I n -αJ -β Â) is prohibitive for large graphs. We address this computational bottleneck using monotone operator theory in the next section.
DRGNN learns node features by finding the fixed point H * that satisfies the following equilibrium equation:
where |β| < 1, α + β + 1 > 0, and γ > 1 + |α| + |β| are learnable. Here, σ(•) is the activation function (e.g., ReLU), and f Θ (X) is a transformation of the input node features X parameterized by Θ. The rationale of the design in Equation 3 will be discussed in the rest of this section.
Starting from H (0) , one approach to find the fixed point of Equation 3 is through the (damped) iteration using the Forward-Backward (FB) splitting (Passty, 1979), with a certain damping value t > 0, one iterates:
for i = 0, 1, . . . , K. This iteration terminates when the difference between two consecutive iterations is smaller than some threshold ϵ and then H (K+1) is taken as the numerical fixed point H * . Each iteration can be viewed as one message-passing layer, then fixed point H * is a result of multi-step message passing involving full node similarity matrix (I n + αJ + β Â) -1 with its number of steps (depth) adaptive to the learning task. Therefore, H * captures LRI between distant nodes based on node similarities and also incorporates the nonlinearities between message-passing steps. We verify the improved LRI learning ability of DRGNN over APPNP in Section 5; see also Figure 2 for a visual comparison of the learned features in APPNP and DRGNN.
However, it remains unclear whether the dampened Picard iteration converges to the fixed point H * and the computation of the matrix inverse (I n +αJ +β Â) -1 in each iteration is computationally expensive. We will address these two challenges in the next two subsections.
We discuss the existence and uniqueness of the fixed point of Equation 3, i.e., the well-posedness of DRGNN. Our solution comes from a monotone operator theory viewpoint; see (Bauschke et al., 2011) or Appendix B for background on monotone operator theory. We will show that the fixed point H * of Equation 3 exists and is unique, even when directly interpreting Equation 3 as an iterative scheme results in a non-contractive operator.
According to the monotone operator theory, finding the fixed point H * for Equation 3 is equivalent to solving the following monotone inclusion problem (See Appendix B for details): find 0 ∈ (F + G)(H) with F and G being two set-valued functions, given as follows
where ∂g denotes the subgradient of a convex closed proper function g that satisfies σ = prox t g for some t > 0. Here, the proximal operator is defined as prox t g (x) := arg min z 1 2 ∥x -z∥ 2 + t g(z) for any t > 0. Most commonly used activation functions, such as ReLU, satisfy this condition. Specifically, ReLU = prox t g for ∀t > 0 with g being the indicator of the positive octant, i.e. g(x) = I{x ≥ 0}.
It's worth noting that the inclusion of 2H in equation 3 results in -I n in F and it marks a significant difference from what is used in the previous work that connects monotone inclusion problem with fixed-point neural networks (Winston and Kolter, 2020;Baker et al., 2023). This specific design will be a key factor in achieving computational efficiency; see Equation 8in the subsequent section.
According to the monotone operator theory, the monotone inclusion problem Equation 5 admits a unique solution if the linear operator F is strongly monotone.
In particular, we have the following result whose proof can be found in Appendix A.
Proposition 1. The operator F is strongly monotone if |β| < 1, α+β+1 > 0, and γ > 1+|α|+|β|. Moreover, the monotone inclusion problem find 0 ∈ (F + G)(H) with F and G defined in Equation 5 admits a unique solution, and Equation 3 admits a unique fixed point.
In this subsection, we present an efficient implementation of DRGNN. Specifically, in the forward pass, the fixed-point nature of the hidden encoding allows us to use any root finding solver for H * not necessarily the Picard iteration (Equation 4) derived from FB splitting. Peaceman-Rachford (PR) splitting (Peaceman and Rachford, 1955) has also been studied in the context of fixed-point neural networks (Winston and Kolter, 2020;Baker et al., 2023). PR splitting in general converges faster than FB splitting, but it requires the computation of the matrix inverse that originates from finding the resolvent for the operator F . As we will see in this subsection, our tailored design of F allows us to compute the resolvent efficiently by circumventing the computation of the matrix inverse, which is a sharp contrast to the previous work (Winston and Kolter, 2020;Baker et al., 2023). We additionally opt for DR splitting (Douglas and Rachford, 1956), which is an averaged version of PR splitting that has a better convergence guarantee in general (Ryu and Boyd, 2016), and we observed more robust performance in comparison to PR splitting for our setting. For the backward pass, the implicit differentiation method from (Geng et al., 2021) is employed.
We now elaborate on DR splitting for solving the monotone inclusion problem Equation 5 and hence to obtain the fixed point H * of Equation 3. DR splitting is a powerful tool for solving monotone inclusion problems (Ryu and Boyd, 2016). With operators F and G defined in Equation 5, DR splitting solves the monotone inclusion problem "find 0 ∈ (F + G)(H)" by starting with an initializationfoot_2 of the intermediate state U (0) , and then updates as follows:
where I denotes the identity operator, and the operators R G and C G denote the resolvent and Cayley operators of G, respectively. They are defined as
Similarly, C F is the Cayley operator of the operator F .
Then the fixed point H * of Equation 3 is determined by H * = σ(U * ). It is worth noting that both resolvent and Cayley operators are non-expansive for any strongly monotone operator. DR splitting converges linearly to H * for any choice of t > 0 when F is strongly monotone and Lipschitz; see (Ryu and Boyd, 2016, Section 6) or Appendix B for details.
Plugging the detailed form of F and G in Equation 5into Equation 6, we obtain the following iterative schemes for the intermediate state U (i) : 7) where
As discussed above, DR splitting converges to H * linearly for any t > 0, and when t = 1, we have
Therefore, when using DR splitting in Equation 7to compute the fixed point of Equation 3, the needs of computing I n + αJ + β Â -1 and in the linear part V of the resolvent operator R F cancel out. This is a particular advantage of having -I n in the operator F which comes from our tailored design of Equation 3.
Initializing with the fixed point of the previous forward pass: In training, the learned function f Θ (X) tends to stabilize as the model converges. Consequently, the difference between fixed points in consecutive forward passes become negligible. Therefore, it is natural to leverage the numerical fixed point from the previous forward pass to initialize the iteration of the new forward pass. This strategy has been adopted to accelerate training fixed-point networks (Bai et al., 2022;Pokle et al., 2022).
By utilizing fixed-point encoding for learning node features, the memory consumption for backpropagation becomes independent of the number of iterations (layers) by using implicit differentiation. For simplicity, we denote the DR splitting iteration in Equation 7as
). Let θ represent a parameter in Θ. For any loss function ℓ, by using the implicit differentiation, we have
where J F DR (U * ) is the Jacobian matrix of F DR evaluated at the fixed-point U * . Note that the matrix I n -J F DR (U * ) is invertible because the iteration of DR splitting is contractive. According to Equation 9, backpropagation only requires the gradient at the final fixed point. We can disable automatic differentiation during the fixed-point finding process and only run one more iteration with automatic differentiation to use the stored gradients for computing the true gradients through Equation 9. However, the inverse Jacobian term (I n -J F DR (U * )) -1 can be computationally expensive (Bai et al., 2019;Winston and Kolter, 2020).
In our implementation, we employ the inexact gradient method (Geng et al., 2021), which can maintain the descent direction. This method, also adopted in (Pokle et al., 2022;Anil et al., 2022), significantly accelerates backpropagation. This process involves locating the fixed-point H * with automatic differentiation off, enabling it for a few more iterations, and using the stored gradient to update DRGNN directly.
In this section, we analyze the time and memory complexities of DRGNN. Let n and |E| denote the number of nodes and edges in the graph, respectively. We use d to denote the feature dimension. We assume the graph is sparse, which is common in graph learning. During the forward pass, DRGNN has a time complexity of O(|E|M d), where M represents the maximum number of iterations. Correspondingly, its space complexity is O(|E| + nd). DRGNN leverages the inexact gradients to accelerate the backpropagation. Consequently, the time complexity is O(|E|P d), where P indicates the number of inexact gradient computations. The space complexity during the backward pass is O(P |E| + nd).
Our experiments align with findings in (Pokle et al., 2022;Anil et al., 2022) that small values of P (less than five) maintain high performance.
In this section, we validate the performance of DRGNN on various graph learning tasks, including both synthetic datasets and real-world peptide molecular modeling datasets for LRI learning, as well as graph transductive node classifications. We implement DRGNN using PyG (Fey and Lenssen, 2019) and GraphGym (You et al., 2020) frameworks and conduct all experiments on a single NVIDIA RTX 3090 GPU.
In this subsection, we consider two synthetic datasets that are designed to test the model's ability to learn LRI; the corresponding tasks provide controlled environments where LRI is crucial for the model to achieve high performance. We further provide a visual understanding of the learning process to demonstrate the effectiveness of DRGNN in learning LRI.
The Synthetic Chains node classification dataset (Gu et al., 2020) consists of a collection of chains where nodes within the same chain share identical labels. However, only the starting node on each chain has a meaningful feature as the one-hot indicator of the class, while all other nodes carry zero-valued features.
To accurately classify all nodes on the chains, a model must be able to propagate the class indicator feature from the initial node to the distant nodes in the forward pass without information loss. Consequently, the Synthetic Chains task poses a significant challenge for numerous GNN models, particularly when the depth of GNN is not sufficient or the model is unstable in learning LRI. We consider both a binary Synthetic Chain task consisting of 2 classes of 10 chains with 80 nodes each and a multi-class Synthetic Chain task consisting of 10 classes of 10 chains each. In both tasks, we follow the training procedure in (Gu et al., 2020).
A visualization of the learning process in binary classification: In Figure 2 We first train each model for 100 epochs and then use the learned parameters to predict the node labels from the learned features on the test graph at each iteration step. Each model is provided with a total of 80 iteration steps to propagate the node features. We observe that IGNN fails to correctly classify all nodes and the predicted probabilities of the two classes are not wellseparated. In contrast, both APPNP and DRGNN are able to correctly classify all nodes, which shows the effectiveness of using the personalized PageRank-style matrix for message passing in learning LRI. Additionally, DRGNN quickly obtains the correct prediction for all nodes while APPNP requires more iterations to achieve the same result. This demonstrates the effectiveness of the learned fixed point in DRGNN.
The multi-class classification task poses a more challenging problem for the models to learn LRI. Figure 3 illustrates the mean test accuracy, calculated over 10 random initializations, for baseline models trained on multi-class Synthetic Chains with chain lengths varying from 10 to 100. In this experiment, each architecture is tuned at chain length 100 with 200 iterations. Although each model is capable of fully propagating the node information, only DRGNN consistently classifies chains accurately across all investigated lengths. Additional results for various models can be found in Appendix C.
The Color-counting dataset (Liu et al., 2022) introduces a node classification task that is more challenging than the Synthetic Chains. This dataset uses the same chain-like structure but rather than determining node labels based on the starting node's color, node labels within each chain are assigned according to the majority node color, encoded as one-hot feature vectors. This setup emphasizes the need for GNNs to acquire multiscale information in LRI learning for optimal performance. In light of this, Liu et al. ( 2022) presented MGNNI, which surpasses other baseline models on this dataset.
We compare DRGNN with MGNNI as well as APPNP and GCN on this task. Therefore, the necessity of identifying the majority color during message passing raises additional challenges to learn LRI. We report the mean test accuracy over 10 random initializations for Color-counting chains of length 10 to 200 in Figure 4. We observe that DRGNN obtains close to full accuracy across all chain lengths, while all other models fail to learn LRI or identify the majority color. This validates the effectiveness of the DRGNN message-passing scheme in complicated LRI learning tasks.
We explore the effectiveness of DRGNN in realworld scenarios by evaluating its performance on the Peptides-Func and Peptides-Struct molecular modeling datasets (Dwivedi et al., 2022) Table 2: Performance comparison of different models on transductive node classification of Citation Networks.
Results marked with * are reported in (Chen et al., 2023). Models that run out of memory are reported with OOM and models without existing results with NA. GCN and APPNP are MP-GNN baselines, Graphormer, SAN, and GraphGPS are Transformer-based models, and NAGphormer is a mixture of MP-GNN and Transformer-style models. DRGNN achieves state-of-the-art results on Amazon-Computers and outperforms the baseline MP-GNN models on each task.
is shown that Transformer-based models are more effective than MP-GNNs. Both datasets contain 15,535 graphs with a total of 2.3 million nodes, each representing a peptide with atoms as nodes and covalent bonds as edges; see Figure 5 for an illustration. On average, peptide graphs from these datasets consist of about 150 nodes with a typical node degree nearing 2, making them chain-like structures. Peptide-func is a multi-label graph classification task and the goal is to predict the functional properties of peptides. Peptidestruct is a graph regression task and the goal is to predict the 3D structure of peptides. In both cases, capturing non-covalent LRI becomes vital for a GNN model to excel in this setting.
We compare DRGNN against several strong baseline models, including GCN (Kipf and Welling, 2017), GINE (Xu et al., 2019), GatedGCN (Bresson and Laurent, 2017) and its variant with random walk structural encoding (RWSE) GatedGCN+RWSE, Transformer (Vaswani et al., 2017) with Laplacian position encoding (LapPE), SAN variants (Kreuzer et al., 2021) (SAN+LapPE and SAN+RWSE), and GraphGPS (Rampášek et al., 2022). We summarize the mean training and test performance over 10 random initializations in Table 1, showing that DRGNN outperforms all baseline models on both datasets in terms of both training and test performance.
We further demonstrate the effectiveness of DRGNN in learning LRI across five transductive node classification tasks, including the citation networks Coauthor- CS/Physics (Shchur et al., 2018), ogbn-arxiv (Hu et al., 2020), and the co-purchasing networks Amazon-Computers/Photo (Shchur et al., 2018). These tasks consist of single large graphs with up to 170K nodes, 1.2M edges, and 23 length diameters, and contrasting the prior mini-batch training on multiple molecular graphs. Comprehensive dataset details can be found in Appendix D.1. Consequently, the transductive tasks bring to light memory challenges for several mainstream Transformer-based architectures and illustrate the memory efficiency of DRGNN. We compare against existing results from (Chen et al., 2023) which serves to illustrate the difference between MP-GNN and Transformer-based models. In particular, the MP-GNN baselines are GCN and APPNP, the Transformer-based architectures include Graphormer, SAN, and GraphGPS, and the NAGphormer (Chen et al., 2023) is a mixture of MP-GNN and Transformerstyle models.
Table 2 verifies the memory issues for prominent Transformer-based models and illustrates the strength of DRGNN. In particular, DRGNN achieves the best performance on ogbn-arxiv and Amazon-Computers/Photo and outperforms the baseline MP-GNNs on all five tasks. DRGNN also outperforms many Transformer-based models (only slightly inferior to NAGphormer on Coauthor-CS/Physics), highlighting its superior memory efficiency and effectiveness in learning LRI for inductive tasks.
The 1-hop message-passing nature of many MP-GNNs limits their ability to learn LRI, which is crucial for many graph learning tasks. To effectively learn LRI, We propose DRGNN leveraging a modified Personalized PageRank matrix -a full node similarity matrix. DRGNN is designed and efficiently implemented through the lens of monotone operator theory, which allows us to circumvent the matrix inversion that comes from the use of a full node similarity matrix. We demonstrate the effectiveness of DRGNN over existing strong baseline models on various graph learning tasks, including synthetic datasets and benchmark real-world datasets.
1. For all models and algorithms presented, check if you include:
(a) A clear description of the mathematical setting, assumptions, algorithm, and/or model.
[Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm.
[Yes] (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries.
[Yes]
2. For any theoretical claim, check if you include:
(a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results.
[Yes] (c) Clear explanations of any assumptions. [Yes] 3. For all figures and tables that present empirical results, check if you include:
(a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL).
[Yes] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen).
[Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times).
[Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider).
[Yes] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include: (a) Citations of the creator If your work uses existing assets. [Yes] (b) The license information of the assets, if applicable. [Yes] (c) New assets either in the supplemental material or as a URL, if applicable. [Yes] (d) Information about consent from data providers/curators. [Yes] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable] • Meanwhile, a subdifferential operator ∂f is maximal monotone if and only if f is a convex closed proper function.
Recall the resolvent and Cayley operator of an operator G are defined by
for any t, where I is the identity operator. The following results for the resolvent of linear and subdifferential operators are used in Section 4:
• when F (x) = Gx + h is a linear operator, then
• when F = ∂f for some CCP function f , then the resolvent is given by the following proximal operator
If an operator F is strongly monotone, its resolvent R F is contractive, and its Cayley operator is non-expansive (for any t > 0). If F is strongly monotone and Lipschitz, then its Cayley operator is also contractive, see (Ryu and Boyd, 2016, Section 6).
This section provides additional details for Section 4 about the monotone inclusion problem and the Forward-Backward splitting method. We will first introduce the Forward-Backward splitting method and then show that the monotone inclusion problem is equivalent to the fixed-point problem of the layer update Equation 3. Then we derive the damped Picard iteration used in Equation 4.
Forward-backward (FB) splitting is a technique used to find a zero in the sum of operators, i.e., locate x such that 0 ∈ (F + G)(x),
where F and G are maximal monotone, and F is single-valued. Then for any t > 0, we have
Where the last step uses the definition of the resolvent operator R G := (I + tG) -1 . Thus, x is a solution if and only if it is a fixed point of R G (I -tF ) for any t.
Equivalence between the fixed-point problem (Equation 3) and the monotone inclusion problem (Equation 5). Recall that the monotone inclusion problem used in Equation 5reads
where G is such that R G is the activation function σ. Then for any t > 0, the FB splitting updates as the following damped variant of Picard iteration
Therefore, the FB splitting iteration recovers exactly the fixed-point formulation in Equation 3 when t = 1 and the fixed-point in Equation 3 can be computed via a suitable damping factor t.
The Douglas-Rachford splitting method is derived by averaging the composition of two Cayley operators. For any t > 0, the following equivalence relation holds:
This can be further expanded as:
Then the fixed point iteration for this setup is:
C Additional Experimental Results on Multi-class Chain Classification
100 ( 芩 ) > U 巴 n u u v 75 50 25 。 ------丁--------____！一一一一一一一一一一一r__________ ! !
nodes per chain, the total number of nodes in the chain dataset is c × n c × l. In this task, we use the 5/15/80% train/valid/test splits.
Color-counting. The Color-counting dataset (Liu et al., 2022) is introduced to further test the model's ability to learn LRI while processing multiscale information. The dataset contains a collection of chains, with each chain containing 10 randomly selected nodes that are colored into one of two colors. Each node's label is determined by the majority color of the chain containing it. The dataset is balanced with 50% of the nodes in each class. In this task, we use the 5/15/80% train/valid/test splits.
Peptides-func. The peptides-func is a multi-label graph classification task introduced in Dwivedi et al. (2022).
The dataset consists of 15,535 graphs with a total of 2.3 million nodes. Each graph is constructed from a peptide sequence, where each node represents the heavy atom while the edges represent the chemical bonds between them. The OGB library (Hu et al., 2020) molecular features are used in this dataset. There is a total of 10 classes that represent peptide functions, e.g., anti-bacterial, anti-viral, cell-cell communication, etc. on average to 1.65 of the 10 classes. The labels are imbalanced, only 16.5% of the data is in the positive class, with the richest class having 62.7% positives and the poorest 1.9%. The license of this dataset is CC BY-NC 4.0.
Peptide-struct. The peptide-struct is also introduced in Dwivedi et al. ( 2022) and contains the same graphs as in the peptides-func dataset. This graph regression task aims to predict the peptide's graph level 3D structure, including inertia mass, inertia valence, length, sphericity, etc. The license of this dataset is CC BY-NC 4.0.
Transductive Datasets. The ogbn-arxiv is a large citation network with 169343 nodes and 1,166,243 edges introduced in (Hu et al., 2020). Each node is an arXiv computer science paper, and each directed edge indicates the source node cites the target node. The node feature is a 128-dimensional vector obtained from the word embedding of the title and abstract of its corresponding paper. The Coauthor CS and Physics datasets are introduced in (Shchur et al., 2018) represent co-authorship graphs from Microsoft Academic Graph. Each node represents an author, and each edge indicates two authors have co-authored a paper. The node feature represents the keywords of the corresponding authors' papers, and the label of the node is the author's most active field of study. The Amazon Computers and Amazon Photo datasets are introduced in (Shchur et al., 2018) and represent products bought together on Amazon. Each node represents a product, and each edge indicates two products are frequently bought together. The node feature is constructed from the bag-of-words of the product's reviews, and the label of the node is the product's category.
This section details the encoder, DRGNN, and decoder architectures used in Section 5. Additional hyperparameter details are provided in Appendix D.4.
The general architecture for DRGNN includes three auxiliary learnable parameters α, β, γ as in Equation 3and a bias term f Θ (•). The forward method is then performed via Equation 7. Fixed point iteration is first calculated without gradients until convergence or the maximum number of iterations is reached. The iteration is called again with gradients until the number of phantom gradients is reached. The maximum number of forward iterations and the number of phantom gradient steps may be adjusted. The forward method also allows for an optional initial guess to the iterative solver, which can significantly improve the computational efficiency of DRGNN (see Section 5). DRGNN automatically stores an initial guess for static graphs. For dynamic graphs, it is recommended that this value is augmented to the data and passed to the model with the batched data. We provide a data augmentation transform using the PyG library (Fey and Lenssen, 2019) in the publically available code.
Synthetic Chains. In the Synthetic Chains dataset, we use a single linear layer without bias followed by a dropout layer for encoding. We then use the DRGNN layer with ReLU activation and a bias term of two sequential linear layers without bias separated by a ReLU activation function. The DRGNN layer is followed by a decoding process of a ReLU activation function followed by a linear layer without bias. Finally, model predictions are generated using a logarithmic softmax activation.
Color-counting. The color-counting dataset uses the same encoder and decoder architecture as the Synthetic Chains dataset. The DRGNN layer uses a ReLU activation function and a bias term of two sequential linear layers without bias separated by a ReLU activation function.
Peptides-func. The atomic information provided by the peptides-func dataset is first encoded using the Atom encoder as in (Dwivedi et al., 2022). Then the feature is passed through four layers of DRGNN with LeakyReLU activation and a GCN-style bias term. The decoder architecture is a two sequential linear layer. The hidden dimension is chosen to be 300 for all layers to fit within the 500k parameter limit. The key hyperparameters are provided in Table 3.
Peptides-struct. Similar to the peptides-func dataset, the atomic information provided by the peptides-struct dataset is first encoded using the Atom encoder as in (Dwivedi et al., 2022). Then the feature is passed through three layers of DRGNN with LeakyReLU activation and a GCN-style bias term. The decoder architecture is a three-sequential linear layer. The hidden dimension is chosen to be 300 for all layers to fit within the 500k parameter limit. The key hyperparameters are provided in Table 3.
Transductive Datasets. The transductive datasets use the same encoder and decoder architecture as the Synthetic Chains dataset. The DRGNN layer uses a LeakyReLU activation function.
In this section, we provide the training details for the experiments in Section 5. All experiments are run using 8 NVIDIA RTX3090 GPUs and timing and memory experiments run on single A100 GPUs provided by Google Colab.
Synthetic Chains. The dataset is pre-processed by taking the symmetric normalized adjacency matrix. In these tasks, we utilize the Adam optimizer (Kingma and Ba, 2014), cross entropy loss, and early stopping based on the validation accuracy. Specifically, we train with a maximum of 2000 forward epochs with early stopping if the validation accuracy does not improve after 100 epochs. We save the model at the epoch with the best validation accuracy and use the saved model for testing.
Color-counting. The training procedure for the color-counting dataset is identical to the synthetic chains dataset.
Peptides-func and Peptides-struct. We follow the same training procedure as in (Dwivedi et al., 2022). The optimizer is AdamW (Loshchilov and Hutter, 2017) with a total of 250 epochs. The learning rate is halved when the validation loss does not improve after 20 epochs. The fixed 75/15/15% train/valid/test splits are used. The batch size is 128 for Peptides-func and Peptides-struct.
Transductive Datasets. The optimizer is AdamW (Loshchilov and Hutter, 2017) with a total of 100 epochs.
The learning rate follows a cosine scheduler with 5 warmup epochs. The random 60/20/20% train/valid/test splits are used.
To find the optimal hyperparameters of each model we use the hyperparameter searching range reported in Table 3. In the interest of space, when the spacing between values is linear, we use the notation {min:max:step}.
For instance dropout may be abbreviated {0.0:0.8:0.1}. We use lr to denote the initial learning rate and wd to denote the weight decay. For DRGNN, we use α init to denote the initialization of α, β init to denote the initialization of β, γ init to denote the initialization of γ. max iter to denote the maximum number of forward iterations, phantom grad to denote the number of steps used at the Phantom gradient stage, tol to denote the tolerance used for fixed-point iteration.
Synthetic Chains. For all models we use 16 hidden features. Each model is tuned using Bayesian metalearning to maximize the test accuracy for 50 iterations. For binary classification, the models are tuned with a
Proceedings of the 27 th International Conference on Artificial Intelligence and Statistics (AISTATS) 2024, Valencia, Spain. PMLR: Volume 238. Copyright 2024 by the author(s). Correspond to: wangbaonj@gmail.com.
The results in this section apply to graphs with multiple connected components by considering the relevant matrix as a block diagonal for each component.
In practice, we initialize the solver with the fixed point found in the previous forward pass.