Implicit Graph Neural Networks

Introduction

Graph neural networks (GNNs) (Zhou et al.,, 2018; Zhang et al.,, 2020) have been widely used on graph-structured data to obtain a meaningful representation of nodes in the graph. By iteratively aggregating information from neighboring nodes, GNN models encode graph-relational information into the representation, which then benefits a wide range of tasks, including biochemical structure discovery (Gilmer et al.,, 2017; Wan et al.,, 2019), computer vision (Kampffmeyer et al.,, 2018), and recommender systems (Ying et al.,, 2018). Recently, newer convolutional GNN structures (Wu et al., 2019b, ) have drastically improved the performance of GNNs by employing various techniques, including renormalization (Kipf and Welling,, 2016), attention (Veličković et al.,, 2017), and simpler activation (Wu et al., 2019a, ).

The aforemetioned modern convolutional GNN models capture relation information up to $T$-hops away by performing $T$ iterations of graph convolutional aggregation. Such information gathering procedure is similar to forward-feeding schemes in popular deep learning models, such as multi-layer perceptron and convolutional neural networks. However, despite their simplicity, these computation strategies cannot discover the dependency with a range longer than $T$-hops away from any given node.

One approach tackling this problem is to develop recurrent GNNs that iterate graph convolutional aggregation until convergence, without any a priori limitation on the number of hops. This idea arises in many traditional graph metrics, including eigenvector centrality (Newman,, 2018) and PageRank (Page et al.,, 1999), where the metrics are implicitly defined by some fixed-point equation. Intuitively, the long-range dependency can be better captured by iterating the information passing procedure for an infinite number of times until convergence. Pioneered by (Gori et al.,, 2005), new recurrent GNNs leverage partial training (Gallicchio and Micheli,, 2010, 2019) and approximation (Dai et al.,, 2018) to improve performance. With shared weights, these methods avoid exploding memory issues and achieve accuracies competitive with convolutional counterparts in certain cases.

While these methods offer an alternative to the popular convolutional GNN models with added benefits for certain problems, there are still significant limitations in evaluation and training for recurrent GNN models. Conservative convergence conditions and sophisticated training procedures have limited the use of these methods in practice, and outweighed the performance benefits of capturing the long-range dependency. In addition, most of these methods cannot leverage multi-graph information or adapt to heterogeneous network settings, as prevalent in social networks as well as bio-chemical graphs (Wan et al.,, 2019).

In this work, we present the Implicit Graph Neural Network (IGNN) framework to address the problem of evaluation and training for recurrent GNNs. We first analyze graph neural networks through a rigorous mathematical framework based on the Perron-Frobenius theory (Berman and Plemmons,, 1994), in order to establish general well-posedness conditions for convergence. We show that most existing analyses are special cases of our result. As for training, we propose a novel projected gradient method to efficiently train the IGNN, where we leverage implicit differentiation methods to obtain the exact gradient, and use projection on a tractable convex set to guarantee well-posedness. We show that previous gradient methods for recurrent graph neural networks can be interpreted as an approximation to IGNN. Further, we extend IGNN to heterogeneous network settings. Finally, we conduct comprehensive comparisons with existing methods, and demonstrate that our method effectively captures long-range dependencies and outperforms the state-of-the-art GNN models on a wide range of tasks.

Paper outline.

In Section 2, we give an overview of related work on GNN and implicit models. In Section 3, we introduce the background and notations for this paper. Section 4 discusses the IGNN framework together with its well-posedness and training under both ordinary and heterogeneous settings. Section 5 empirically compares IGNN with modern GNN methods.

Related Work

Pioneered by (Gori et al.,, 2005), GNN models have gained influence for graph-related tasks. Led by GCN (Kipf and Welling,, 2016), convolutional GNN models (Veličković et al.,, 2017; Hamilton et al.,, 2017; Wu et al., 2019a, ; Jin et al.,, 2019; Chang et al.,, 2020) involve a finite number of modified aggregation steps with different weight parameters. On the other hand, recurrent GNN models (Gori et al.,, 2005) use the same parameters for each aggregation step and potentially enable infinite steps. (Li et al.,, 2015) combines recurrent GNN with recurrent neural network structures. Methods such as Fast and Deep Graph Neural Network (FDGNN) (Gallicchio and Micheli,, 2010, 2019) use untrained recurrent GNN models with novel initialization to its aggregation step for graph classification. While the Stochastic Steady-State Embedding (SSE) method (Dai et al.,, 2018) uses an efficient approximated training and evaluation procedure for node classification. Recently, global method Geom-GCN (Pei et al.,, 2020) employs additional embedding approaches to capture global information. However, Geom-GCN (Pei et al.,, 2020) also belongs to convolutional-based GNNs, which struggle to capture very long range dependency due to the finite iterations they take.

Implicit Models.

Implicit models are emerging structures in deep learning where the outputs are determined implicitly by a solution of some underlying sub-problem. Recent works (Bai et al.,, 2019) demonstrate the potential of implicit models in sequence modeling, physical engine (de Avila Belbute-Peres et al.,, 2018) and many others (Chen et al.,, 2018; Amos et al.,, 2018).(El Ghaoui et al.,, 2020) proposes a general implicit framework with the prediction rule based on the solution of a fixed-point equilibrium equation and discusses the well-posedness of the implicit prediction rule.

Oversmoothing.

To catch the long-range dependency, another intuitive approach is to construct deeper convolutional GNNs by stacking more layers. However, (Li et al.,, 2018) found that the learned node embeddings become indistinguishable as the convolutional GNNs get deeper. This phenomenon is called over-smoothing. Since then, a line of empirical (Li et al.,, 2018; Chen et al.,, 2020; Rong et al.,, 2020) and theoretical (Oono and Suzuki,, 2020; Zhao and Akoglu,, 2020) works follows on the over-smoothing phenomenon. Unlike convolutional GNNs, IGNN adopts a different approach for long-range dependency based on recurrent GNNs and doesn’t seem to suffer performance degradation as much even though it could be viewed as an infinite-layer GNN. See appendix E.5 for details.

Preliminaries

Given graph data, graph models produce a prediction $\hat{Y}$ to match the true label $Y$ whose shape depends on the task. GNN models are effective in graph-structured data because they involve trainable aggregation steps that pass the information from each node to its neighboring nodes and then apply nonlinear activation. The aggregation step at iteration $t$ can be written as follows:

Modern GNN approaches adopt different forms of graph convolution aggregation (1). Convolutional GNNs (Wu et al., 2019b, ) iterate (1) with $\Omega=0$ and set $X^{(0)}=U$. Some works temper with the adjacency matrix using renormalization (Kipf and Welling,, 2016) or attention (Veličković et al.,, 2017)). While recurrent GNNs use explicit input from features at each step with tied weights $W$ and $\Omega$, some methods replace the term $\Omega U$ with $\Omega_{1}UA+\Omega_{2}U$, in order to account for feature information from neighboring nodes (Dai et al.,, 2018). Our framework adopts a similar recurrent graph convolutional aggregation idea.

A heterogeneous network is an extended type of graph that contains different types of relations between nodes instead of only one type of edge. We continue to use $G=(V,\mathcal{E})$ to represent a heterogeneous network with the node set $V$ and the edge set $\mathcal{E}\subseteq V\times V\times R$, where $R$ is a set of $N:=|R|$ relation types. Similarly, we define the adjacency matrices $A_{i}$, where $A_{i}$ is the adjacency matrix for relation type $i\in R$. Some heterogeneous networks also have relation-specific feature matrices $U_{i}$.

Implicit Graph Neural Networks

We now introduce a framework for graph neural networks called Implicit Graph Neural Networks (IGNN), which obtains a node representation through the fixed-point solution of a non-linear “equilibrium” equation. The IGNN model is formally described by

Unlike most existing methods that iterate (1) for a finite number of steps, an IGNN seeks the fixed point of equation (2b) that is trained to give the desired representation for the task. Evaluation of fixed point can be regarded as iterating (1) for an infinite number of times to achieve a steady state. Thus, the final representation potentially contains information from all neighbors in the graph. In practice, this gives a better performance over the finite iterating variants by capturing the long-range dependency in the graph. Another notable benefit of the framework is that it is memory-efficient in the sense that it only maintains one current state $X$ without other intermediate representations.

Despite its notational simplicity, the IGNN model covers a wide range of variants, including their multi-layer formulations by stacking multiple equilibrium equations similar to (2b). The SSE (Dai et al.,, 2018) and FDGNN (Gallicchio and Micheli,, 2019) models also fit within the IGNN formulation. We elaborate on this aspect in Appendix C.

IGNN models can generalize to heterogeneous networks with different adjacency matrices $A_{i}$ and input features $U_{i}$ for different relations. In that case, we have the parameters $W_{i}$ and $\Omega_{i}$ for each relation type $i\in R$ to capture the heterogenerity of the graph. A new equilibrium equation (3) is used:

In general, there may not exist a unique solution for the equilibrium equation (2b) and (3). Thus, the notion of well-posedness comes into play.

For the IGNN model to produce a valid representation, we need to obtain some unique internal state $X(U)$ given any input $U$ from equation (2b) for ordinary graph settings or equation (3) for heterogeneous network settings. However, the equilibrium equation (2b) and (3) can have no well-defined solution $X$ given some input $U$. We give a simple example in the scalar setting in Appendix B, where the solution to the equilibrium equation (2b) does not even exist.

In order to ensure the existence and uniqueness of the solution to equation (2b) and (3), we define the notion of well-posedness for equilibrium equations with activation $\phi$ for both ordinary graphs and hetergeneous networks. This notion has been introduced in (El Ghaoui et al.,, 2020) for ordinary implicit models.

We first develop sufficient conditions for the well-posedness property to hold on ordinary graph settings with a single edge type. The idea is to limit the structure of $W$ and $A$ together to ensure well-posedness for a set of activation $\phi$.

In the following analysis, we assume that $\phi$ is component-wise non-expansive, which we refer to as the component-wise non-expansive (CONE) property. Most activation functions in deep learning satisfy the CONE property (e.g. Sigmoid, tanh, ReLU, Leaky ReLU, etc.). For simplicity, we assume that $\phi$ is differentiable.

Assume that $\phi$ is a component-wise non-expansive (CONE) activation map. Then, $(W,A)$ is well-posed for any such $\phi$ if $\lambda_{\rm pf}(|A^{\top}\otimes W|)<1$. Moreover, the solution $X$ of equation (4) can be obtained by iterating equation (4).

Recall that for any three matrices $A,W,X$ of compatible sizes, we have $(A^{\top}\otimes W)\mathop{\bf vec}(X)=\mathop{\bf vec}(WXA)$ (Schacke,, 2018). Showing equation (4) has an unique solution is equivalent to showing that the following “vectorized” equation has a unique solution:

It follows directly from Lemma B.1 that if $\lambda_{\rm pf}(|A^{\top}\otimes W|)=\lambda_{\rm pf}(A)\lambda_{\rm pf}(|W|)<1$, then the above equation has unique solution that can be obtained by iterating the equation.

We find Theorem 4.1 so general that many familiar and interesting results will follow from it, as discussed in the following remarks. Detailed explanations can be found in Appendix B.

For any component-wise non-expansive (CONE) $\phi$, if $\mathcal{A}(X)=\phi(WXA+B)$ is a contraction of $X$ (w.r.t. vectorized norms), then $(W,A)$ is well-posed for $\phi$.

For a directed acyclic graph (DAG), let $A$ be its adjacency matrix. For any real squared $W$, it holds that $(W,A)$ is well-posed for every CONE activation map. Note that $\mathcal{A}(X)=\phi(WXA+B)$ need not be a contraction of $X$.

For a k-regular graph, let $A$ be its adjacency matrix. $(W,A)$ is well-posed for every CONE activation map if $k\|W\|_{2}<1$.

A similar sufficient condition for well-posedness holds for heterogeneous networks.

Assume that $\phi$ is some component-wise non-expansive (CONE) activation map. Then, $(W_{i},A_{i},\;i=1,\dots,N)$ is well-posed for any such $\phi$ if $\lambda_{\rm pf}\left(\sum_{i=1}^{N}|A_{i}^{\top}\otimes W_{i}|\right)<1$. Moreover, the solution $X$ of equation (5) can be obtained by iterating equation (5).

We give a complete proof in Appendix B. Sufficient conditions in Theorems 4.1 and 4.2 guarantee convergence when iterating aggregation step to evaluate state $X$. Furthermore, these procedures enjoy exponential convergence in practice.

2 Tractable Well-posedness Condition for Training

At training time, however, it is difficult in general to ensure satisfaction of the PF sufficient condition $\lambda_{\rm pf}(|W|)\lambda_{\rm pf}(A)<1$, because $\lambda_{\rm pf}(|W|)$ is non-convex in $W$. To alleviate the problem, we give a numerically tractable convex condition for well-posedness that can be enforced at training time efficiently through projection. Instead of using $\lambda_{\rm pf}(|W|)<\lambda_{\rm pf}(A)^{-1}$, we enforce the stricter condition $\|W\|_{\infty}<\lambda_{\rm pf}(A)^{-1}$, which guarantees the former inequality by $\lambda_{\rm pf}(|W|)\leq\|W\|_{\infty}$. Although $\|W\|_{\infty}<\lambda_{\rm pf}(A)^{-1}$ is a stricter condition, we show in the following theorem that it is equivalent to the PF condition for positively homogeneous activation functions, (i.e. $\phi(\alpha x)=\alpha\phi(x)$ for any $\alpha\geq 0$ and $x$), in the sense that one can use the former condition at training without loss of generality.

The proof is given in Appendix B. The above-mentioned condition can be enforced by selecting a $\kappa\in[0,1)$ and projecting the updated $W$ onto the convex constraint set $\mathcal{C}=\{W:\|W\|_{\infty}\leq\kappa/\lambda_{\rm pf}(A)\}$.

For heterogeneous network settings, we recall the following:

For any non-negative adjacency matrix $A$ and arbitrary real parameter matrix $W$, it holds that $\|A^{\top}\otimes W\|_{\infty}=\|A^{\top}\|_{\infty}\|W\|_{\infty}=\|A\|_{1}\|W\|_{\infty}$.

Similar to the difficulty faced in the ordinary graph settings, ensuring the PF sufficient condition on heterogeneous networks is hard in general. We propose to enforce the following tractable condition that is convex in $W_{i}$’s: $\sum_{i=1}^{N}\|A_{i}\|_{1}\|W_{i}\|_{\infty}\leq\kappa<1$, $\kappa\in[0,1)$. Note that this condition implies $\left\|\sum_{i=1}^{N}A_{i}^{\top}\otimes W_{i}\right\|_{\infty}\leq\kappa$, and thus $\lambda_{\rm pf}\left(\sum_{i=1}^{N}|A_{i}^{\top}\otimes W_{i}|\right)\leq\kappa<1$. The PF sufficient condition for well-posedness on heterogeneous networks is then guaranteed.

3 Training of IGNN

We start by giving the training problem (6), where a loss $\mathcal{L}(Y,\hat{Y})$ is minimized to match $\hat{Y}$ to $Y$ and yet the tractable condition $\|W\|_{\infty}\leq\kappa/\lambda_{\rm pf}(A)$ for well-posedness is enforced with $\kappa\in[0,1)$:

The problem can be solved by projected gradient descent (involving a projection to the well-posedness condition following a gradient step), where the gradient is obtained through an implicit differentiation scheme. From the chain rule, one can easily obtain $\nabla_{\Theta}\mathcal{L}$ for the parameter of $f_{\Theta}$ and $\nabla_{X}\mathcal{L}$ for the internal state $X$. In addition, we can write the gradient with respect to scalar $q\in W\cup\Omega$ as follows:

where $Z=WXA+b_{\Omega}(U)$ assuming fixed $X$ (see Appendix D). Here, $\nabla_{Z}\mathcal{L}$ is given as a solution to the equilibrium equation

where $D=\phi^{\prime}(WXA+b_{\Omega}(U))$ and $\phi^{\prime}(z)=d\phi(z)/dz$ refers to the element-wise derivative of the CONE map $\phi$. Since $\phi$ is non-expansive, it is 1-Lipschitz (i.e. the absolute value of $d\phi(z)/dz$ is not greater than 1), the equilibrium equation (8) for gradient $\nabla_{Z}\mathcal{L}$ admits a unique solution by iterating (8) to convergence, if $(W,A)$ is well-posed for any CONE activation $\phi$. (Note that $D\odot(\cdot)$ can be seen as a CONE map with each entry of $D$ having absolute value less than or equal to 1.) Again, $\nabla_{Z}\mathcal{L}$ can be efficiently obtained due to exponential convergence when iterating (8) in practice.

Once $\nabla_{Z}\mathcal{L}$ is obtained, we can use the chain rule (via autograd software) to easily compute $\nabla_{W}\mathcal{L}$, $\nabla_{\Omega}\mathcal{L}$, and possibly $\nabla_{U}\mathcal{L}$ when input $U$ requires gradients (e.g. in cases of features learning or multi-layer formulation). The deriviation has a deep connection to the Implicit Function Theorm. See Appendix D for details.

Due to the norm constraint introduced for well-posedness, each update to $W$ requires a projection step (See Section 4.1). The new $W$ is given by $W^{+}=\pi_{\mathcal{C}}(W):=\mathop{\rm argmin}_{\|M\|_{\infty}\leq\kappa/\lambda_{\rm pf}(A)}\|M-W\|_{F}^{2}$, where $\pi_{\mathcal{C}}$ is the projection back onto $\mathcal{C}=\{\|W\|_{\infty}\leq\kappa/\lambda_{\rm pf}(A)\}$. The projection is decomposible across the rows of $W$. Each sub-problem will be a projection onto an $\mathcal{L}_{1}$-ball for which efficient methods exist (Duchi et al.,, 2008). A similar projected gradient descent training scheme for heterogeneous network settings is detailed in Appendix D. Note that the gradient method in SSE (Dai et al.,, 2018) uses a first-order approximated solution to equation (8). FDGNN (Gallicchio and Micheli,, 2019) only updates $\Theta$ at training using gradient descent.

Numerical Experiment

In this section, we demonstrate the capability of IGNN on effectively learning a representation that captures the long-range dependency and therefore offers the state-of-the-art performance on both synthetic and real-world data sets. More specifically, we test IGNN against a selected set of baselines on 6 node classification data sets (Chains, PPI, AMAZON, ACM, IMDB, DBLP) and 5 graph classification data sets (MUTAG, PTC, COX2, PROTEINS, NC11), where Chains is a synthetic data set; PPI and AMAZON are multi-label classification data sets; ACM, IMDB and DBLP are based on heterogeneous networks. We inherit the same experimental settings and reuse the results of baselines from literatures in some of the data sets. The test set performance is reported. Detailed description of the data sets, our preprocessing procedure, hyper-parameters, and other information of experiments can be found in Appendix E.

To evaluate GNN’s capability for capturing the underlying long-range dependency in graphs, we create the Chains data set where the goal is to classify nodes in a chain of length $l$. The information of the class is only sparsely provided as the feature in an end node. We use a small training set, validation set, and test set with only 20, 100, and 200 nodes, respectively. For simplicity, we only consider the binary classification task. Four representative baselines are implemented and compared. We show in Figure 1 that IGNN and SSE (Dai et al.,, 2018) both capture the long-range dependency with IGNN offering a better performance for longer chains, while finite-iterating convolutional GNNs with $T=2$, including GCN (Kipf and Welling,, 2016), SGC (Wu et al., 2019a, ) and GAT (Veličković et al.,, 2017), fail to give meaningful predictions when the chains become longer. However, selecting a larger $T$ for convolutional GNNs does not seem to help in this case of limited training data. We further discuss this aspect in Appendix E.

Node Classification.

The popular benchmark data set Protein-Protein Interaction (PPI) models the interactions between proteins using a graph, with nodes being proteins and edges being interactions. Each protein can have at most 121 labels and be associated with additional 50-dimensional features. The train/valid/test split is consistent with GraphSage (Hamilton et al.,, 2017). We report the micro-averaged $F_{1}$ score of a multi-layer IGNN against other popular baseline models. The results can be found in Table 1. By capturing the underlying long-range dependency between proteins, the IGNN achieves the best performance compared to other baselines.

To further manifest the scalability of IGNN towards larger graphs, we conduct experiments on a large multi-label node classification data set, namely the Amazon product co-purchasing network data set (Yang and Leskovec,, 2015) http://snap.stanford.edu/data/#amazon. The data set renders products as nodes and co-purchases as edges but provides no input features. 58 product types with more than 5,000 products are selected from a total of 75,149 product types. While holding out 10% of the total nodes as test set, we vary the training set fraction from 5% to 9% to be consistent with (Dai et al.,, 2018). The data set come with no input feature vectors and thus require feature learning at training. Both Micro-$F_{1}$ and Macro-$F_{1}$ are reported on the held-out test set, where we compare IGNN with a set of baselines consistent with those in the synthetic data set. However, we use struct2vec (Dai et al.,, 2016) as an alternative to GAT since GAT faces a severe out-of-memory issue in this task.

As shown in Figure 2, IGNN again outperforms the baselines in most cases, especially when the amount of supervision grows. When more labels are available, more high-quality feature vectors of the nodes are learned and this enables the discovery of more long-range dependency. This phenomenon is aligned with our observation that IGNN achieves a better performance when there is more long-range dependency in the underlying graph.

Graph Classification.

Aside from node classification, we test IGNN on graph classification tasks. A total of 5 bioinformatics benchmarks are chosen: MUTAG, PTC, COX2, NCI1 and PROTEINS (Yanardag and Vishwanathan,, 2015). See details of data sets in Appendix E. Under the graph classification setting, we compare a multi-layer IGNN with a comprehensive set of baselines, including a variety of GNNs and a number of graph kernels. Following identical settings as (Yanardag and Vishwanathan,, 2015; Xu et al.,, 2018), 10-fold cross-validation with LIB-SVM (Chang and Lin,, 2011) is conducted. The average prediction accuracy and standard deviations are reported in Table 1. In this experiment, IGNN achieves the best performance in 4 out of 5 experiments given the competitive baselines. Such performance further validates IGNN’s success in learning converging aggregation steps that capture long-range dependencies when generalized to unseen testing graphs.

Heterogeneous Networks.

Following our theoretical analysis on heterogeneous networks, we investigate how IGNN takes advantage of heterogeneity on node classification tasks. Three benchmarks based on heterogeneous network are chosen, i.e., ACM, IMDB and DBLP (Wang et al.,, 2019; Park et al.,, 2019). More information regarding the heterogeneous network data sets can be found in Appendix E. Table 2 compares IGNN against a set of state-of-the-art GNN baselines for heterogeneous networks. The heterogeneous variant of IGNN continues to offer a competitive performance on all 3 data sets where IGNN gives the best performance in ACM and IMDB data sets. While on DBLP, IGNN underperforms DMGI but still outperforms other baselines by large margin. Good performance on heterogeneous networks demonstrates the flexibility of IGNN on handling heterogeneous relationships.

Conclusion

In this paper, we present the implicit graph neural network model, a framework of recurrent graph neural networks. We describe a sufficient condition for well-posedness based on the Perron-Frobenius theory and a projected gradient decent method for training. Similar to some other recurrent graph neural network models, implicit graph neural network captures the long-range dependency, but it carries the advantage further with a superior performance in a variety of tasks, through rigorous conditions for convergence and exact efficient gradient steps. More notably, the flexible framework extends to heterogeneous networks where it maintains its competitive performance.

Broader Impact

GNN models are widely used on applications involving graph-structured data, including computer vision, recommender systems, and biochemical strucature discovery. Backed by more rigorous mathematical arguments, our research improves the capability GNNs of capturing the long-range dependency and therefore boosts the performance on these applications.

The improvements of performance in the applications will give rise to a better user experience of products and new discoveries in other research fields. But like any other deep learning models, GNNs runs into the problem of interpretability. The trade-off between performance and interpretability has been a topic of discussion. On one hand, the performance from GNNs benefits the tasks. On the other hand, the lack of interpretability might make it hard to recognize underlying bias when applying such algorithm to a new data set. Recent works (Hardt et al.,, 2016) propose to address the fairness issue by enforcing the fairness constraints.

While our research focuses on performance by capturing the long-range dependency, like many other GNNs, it does not directly tackle the fairness and interpretability aspect. We would encourage further work on fairness and interpretability on GNNs. Another contribution of our research is on the analysis of heterogeneous networks, where the fairness on treatment of different relationships remains unexplored. The risk of discrimination in particular real-world context might require cautious handling when researchers develop models.

Acknowledgments and Disclosure of Funding

Funding in direct support of this work: National Key Research and Development Program of China (No. 2020AAA0107800, 2018AAA0102000), ONR Award N00014-18-1-2526, and other funding from Berkeley Artificial Intelligence Lab, Pacific Extreme Event Research Center, Genentech, Tsinghua-Berkeley Shenzhen Institute and National Natural Science Foundation of China Major Project (No. U1611461).

References

Appendix A Kronecker Product

Leveraging the definition of Kronecker product and vectorization, the following equality holds, $(A^{\top}\otimes W)\mathop{\bf vec}(X)=\mathop{\bf vec}(WXA)$ (Schacke,, 2018). Intuitively, this equality reshapes $WXA$ which is linear in $X$ into a more explicit form $(A^{\top}\otimes W)\mathop{\bf vec}(X)$ which is linear in $\mathop{\bf vec}(X)$, a flattened form of $X$. Through the transformation, we place $WXA$ into the form of $Mx$. Thus, we can employ Lemma B.1 to obtain the well-posedness conditions.

Appendix B Well-posedness of IGNN: Illustration, Remarks, and Proof

Consider the following scalar equilibrium equation (9),

B.2 Detailed Explanation for Remarks

For some non-negative adjacency matrix $A$, and arbitrary real parameter matrix $W$, $\lambda_{\rm pf}(|A^{\top}\otimes W|)=\lambda_{\rm pf}(A^{\top}\otimes|W|)=\lambda_{\rm pf}(A)\lambda_{\rm pf}(|W|)$.

The final equality of the above remark follows from the fact that, the spectrum of the Kronecker product of matrix $A$ and $B$ satisfies that $\Delta(A\otimes B)=\{\mu\lambda:\mu\in\Delta(A),\;\lambda\in\Delta(B)\}$, where $\Delta(A)$ represents the spectrum of matrix $A$. And that, the left and right eigenvalues of a matrix are the same.

We find Theorem 4.1 to be quite general. We show that many familiar and interesting results following from it.

For any component-wise non-expansive (CONE) $\phi$, if $\mathcal{A}(X)=\phi(WXA+B)$ is a contraction of $X$ (w.r.t. vectorized norms), then $(W,A)$ is well-posed for $\phi$.

The above remark follows from the fact that the contraction condition for any CONE activation map is equivalent to $\|A^{\top}\otimes W\|<1$, which implies $\lambda_{\rm pf}(|A^{\top}\otimes W|)<1$.

For a directed acyclic graph (DAG), let $A$ be its adjacency matrix. For any real squared $W$, we always have that $(W,A)$ is well-posed for any CONE activation map. Note that in this case $\mathcal{A}(X)=\phi(WXA+B)$ needs not be a contraction of $X$.

Note that for DAG, $A$ is nilpotent ($\lambda_{\rm pf}(A)=0$) and thus $\lambda_{\rm pf}(|A^{\top}\otimes W|)=\lambda_{\rm pf}(A)\lambda_{\rm pf}(|W|)=0$.

For a k-regular graph, let $A$ be its adjacency matrix. $(W,A)$ is well-posed for any CONE activation map if $k\|W\|_{2}<1$.

It follows from that for a k-regular graph, the PF eigenvalue of the adjacency matrix $\lambda_{\rm pf}(A)=k$. And $\lambda_{\rm pf}(A)\lambda_{\rm pf}(|W|)\leq k\|W\|_{2}<1$ guarantees well-posedness.

For some non-negative adjacency matrix $A$, and arbitrary real parameter matrix $W$, $\|A^{\top}\otimes W\|_{\infty}=\|A^{\top}\|_{\infty}\|W\|_{\infty}=\|A\|_{1}\|W\|_{\infty}$.

The above remark follows from the facts that, $\|\cdot\|_{\infty}$ (resp. $\|\cdot\|_{1}$) gives maximum row (resp. column) sum of the absolute values of a given matrix. And that, for some real matrices $A$ and $B$, $\|A\otimes B\|_{\infty}=\max_{i,j}\left(\sum_{k,l}|A_{ik}B_{jl}|\right)=\max_{i,j}\left(\sum_{k}|A_{ik}|\;\sum_{l}|B_{jl}|\right)=\max_{i}\left(\sum_{k}|A_{ik}|\right)\;\max_{j}\left(\sum_{l}|B_{jl}|\right)=\|A\|_{\infty}\|B\|_{\infty}$.

B.3 An Important Lemma for Well-posedness

If $\phi$ is component-wise non-negative (CONE), $M$ is some squared matrix and $v$ is any real vector of compatible shape, the equation $x=\phi(Mx+v)$ has a unique solution if $\lambda_{\rm pf}(|M|)<1$. And the solution can be obtained by iterating the equation. Hence, $x=\lim_{t\rightarrow\infty}x_{t}$.

For existence, since $\phi$ is component-wise and non-expansive, we have that for $t\geq 1$ and the sequence $x_{0},x_{1},x_{2},\dots$ generated from iteration (10),

For $n>m\geq 1$, the following inequality follows,

Because $\lambda_{\rm pf}(|M|)<1$, the inverse of $I-|M|$ exists. It also follows that $\lim_{t\rightarrow\infty}|M|^{t}=0$. From inequality (11), we show that the sequence $x_{0},x_{1},x_{2},\dots$ is a Cauchy sequence because $0\leq\lim_{m\rightarrow\infty}|x_{n}-x_{m}|\leq\lim_{m\rightarrow\infty}|M|^{m}w=0$. And thus the sequence converges to some solution of $x=\phi(Mx+v)$.

For uniqueness, suppose both $x_{a}$ and $x_{b}$ satisfy $x=\phi(Mx+v)$, then the following inequality holds,

It follows that $x_{a}=x_{b}$ and there exists unique solution to $x=\phi(Mx+v)$.

B.4 Proof of Theorem 4.2

Similarly, we can rewrite equation (5) into the following “vectorized” form.

It follows from a similar scheme as the proof of Lemma B.1 that if $\lambda_{\rm pf}\left(\sum_{i=1}^{N}|A_{i}^{\top}\otimes W_{i}|\right)<1$, the above equation has unique solution which can be obtained by iterating the equation.

B.5 Proof of Theorem 4.3

The proof is based on the following formula for PF eigenvalue (Berman and Plemmons,, 1994).

Appendix C Examples of IGNN

In this section we introduce some examples of the variation of IGNN.

It is straight forward to extend IGNN to a multi-layer setup with several sets of $W$ and $\Omega$ parameters for each layer. For conciseness, we use the ordinary graph setting. By treating the fixed-point solution $X_{l-1}$ of the $(l-1)$-th layer as the input $U_{l}$ to the $l$-th layer of equilibrium equation, a multi-layer formulation of IGNN with a total of $L$ layers is created.

where $\phi_{1},\dots,\phi_{L}$ are activation functions. We usually assume that CONE property holds on them. And $(W_{l},\Omega_{l})$ is the set of weights for the $l$-th layer. Thus the multi-layer formulation (13) with parameters $(W_{l},l=1,\dots,L,\;A)$ is well-posed (i.e. gives unique prediction $\hat{Y}$ for any input $U$) when $(W_{l},A)$ is well-posed for $\phi_{l}$ for any layer $l$. This is true since the well-posedness for a layer guarantees valid input for the next layer. Since all layers are well-posed, the formulation will give unique final output for any input of compatible shape. FDGNN (Gallicchio and Micheli,, 2019) uses a similar multi-layer formulation for graph classification but is only partially trained in practive.

Special Cases.

Many existing GNN formulations including convolutional and recurrent GNNs can be treated as special cases of IGNN. We start by showing that GCN (Kipf and Welling,, 2016), a typical example of convolutional GNNs, is indeed an IGNN. We give the matrix representation of a 2-layer GCN as follows,

where $A$ is the renormalized adjacency matrix; $W_{1}$ and $W_{2}$ are weight parameters; $\phi_{1}$ is a CONE activation map for the first layer; and $X_{1}$ is the hidden representation of first layer. We show that GCN (15) is in fact a special case of IGNN by constructing an equivalent single layer IGNN (2) with the same $A$ matrix.

Another interesting special case is SSE (Dai et al.,, 2018), an example of recurrent GNN, that is given by

Appendix D Implicit differentiation for IGNN

To compute gradient of $\mathcal{L}$ from the training problem (6) w.r.t. a scalar $q\in W\cup\Omega$, we can use chain rule. It follows that,

where $\nabla_{X}\mathcal{L}$ can be easily calculated through modern autograd frameworks. But $\frac{\partial X}{\partial q}$ is non-trivial to obtain because $X$ is only implicitly defined. Fortunately, we can still leverage chain rule in this case by carefully taking the “implicitness” into account.

where $Z=WXA+b_{\Omega}(U)$ ($\vec{Z}=(A^{\top}\otimes W)\vec{X}+\overrightarrow{b_{\Omega}(U)}$) assuming fixed $X$. Unlike $X$ in equation (2b), $Z$ is not implicitly defined and should only be considered as a closed evaluation of $Z=WXA+b_{\Omega}(U)$ assuming $X$ doesn’t change depending on $Z$. In some sense, the $Z$ in equation (21) doesn’t equal to $WXA+b_{\Omega}(U)$. However, the closeness property will greatly simplify the evaluation of $\frac{\partial\vec{Z}}{\partial q}$. It turns out that we can still employ chain rule in this case to calculate $\frac{\partial\vec{X}}{\partial\vec{Z}}$ for such $Z$ by taking the change of $X$ before hand into account as follows,

where the second term accounts for the change in $X$ that was ignored in $Z$. Another way to view this calculation is to right multiply $\frac{\partial\vec{Z}}{\partial q}$ on both sides of equation (22), which gives the chain rule evaluation of $\frac{\partial\vec{X}}{\partial q}$ that takes the gradient flowing back to $X$ into account:

The equation (22) can be simplified as follows,

which is equivalent to equation (7). $\nabla_{\vec{Z}}\mathcal{L}$ should be interpreted as the direction of steepest change of $\mathcal{L}$ for $Z=WXA+b_{\Omega}(U)$ assuming fixed $X$. Plugging equation (22) to (25), we arrive at the following equilibrium equation (equivalent to equation (8))

Finally, by plugging the evaluated $\nabla_{Z}\mathcal{L}$ into equation (24), we get the desired gradients. Note that it is also possible to obtain gradient $\nabla_{U}\mathcal{L}$ by setting the $q$ in the above calculation to be $q\in U$. This is valid because we have no restrictions on selection of $q$ other than that it is not $X$, which is assumed fixed. Following the chain rule, we can give the closed form formula for $\nabla_{W}\mathcal{L}$, $\nabla_{\omega}\mathcal{L},\omega\in\Omega$, and $\nabla_{u}\mathcal{L},u\in U$.

We start by giving the training problem for heterogeneous networks similar to training problem (6) for ordinary graphs,

The training problem can be solved again using projected gradient descent method where the gradient of $W_{i}$ and $\Omega_{i}$ for $i\in R$ can be obtained with implicit differentiation. Using chain rule, we write the gradient of a scalar $q\in\bigcup_{i}(W_{i}\cup\Omega_{i})$,

where $Z=\sum_{i=1}^{N}(W_{i}XA_{i}+b_{\Omega_{i}}(U_{i}))$ and $\nabla_{Z}\mathcal{L}$ in equation (28) should be interpreted as “direction of fastest change of $\mathcal{L}$ for $Z$ assuming fixed $X$”. Similar to the derivation in ordinary graphs setting, such notion of $\nabla_{Z}\mathcal{L}$ enables convenient calculation of $\nabla_{q}\mathcal{L}$. And the vectorized gradient w.r.t. $Z$ can be expressed as a function of the vectorized gradient w.r.t. $X$:

Finally, by plugging the evaluated $\nabla_{Z}\mathcal{L}$ into equation (28), we get the desired gradients. It is also possible to obtain gradient $\nabla_{U_{i}}\mathcal{L}$ by setting the $q$ in the above calculation to be $q\in\bigcup_{i}U_{i}$. This is valid because we have no restrictions on selection of $q$ other than that it is not $X$, which is assumed fixed.

After the gradient step, the projection to the tractable condition mentioned in Section 4.2 can be done approximately by assigning $\kappa_{i}$ for each relation $i\in R$ and projecting $W_{i}$ onto $\mathcal{C}_{i}=\{\|W_{i}\|_{\infty}\leq\kappa_{i}/\|A\|_{1}\}$. Ensuring $\sum_{i}\kappa_{i}=\kappa<1$ will guarantee that the PF condition for heterogeneous network is satisfied. However, empirically, setting $\kappa_{i}<1$ with $\sum_{i}\kappa_{i}>1$ in some cases is enough for the convergence property to hold for the equilibrium equations.

Appendix E More on Experiments

In this section, we give detailed information about the experiments we conduct.

For preprocessing, we apply the renormalization trick consistent with GCN (Kipf and Welling,, 2016) on the adjacent matrix of all data sets.

In terms of hyperparameters, unless otherwise specified, for IGNN, we use affine transformation $b_{\Omega}(U)=\Omega UA$; linear output function $f_{\Theta}(X)=\Theta X$; ReLU activation $\phi(\cdot)=\max(\cdot,0)$; learning rate 0.01; dropout with parameter $0.5$ before the output function; and $\kappa=0.95$. We tune layers, hidden nodes, and $\kappa$ through grid search. The hyperparameters for other baselines are consistent with that reported in their papers. Results with identical experimental settings are reused from previous works.

We construct a synthetic node classification task to test the capability of models of learning to gather information from distant nodes. We consider the chains directed from one end to the other end with length $l$ (i.e. $l+1$ nodes in the chain). For simplicity, we consider binary classification task with 2 types of chains. Information about the type is only encoded as 1/0 in first dimension of the feature (100d) on the starting end of the chain. The labels are provided as one-hot vectors (2d). In the data set we choose chain length $l=9$ and 20 chains for each class with a total of 400 nodes. The training set consists of 20 data points randomly picked from these nodes in the total 40 chains. Respectively, the validation set and test set have 100 and 200 nodes.

A single-layer IGNN is implemented with 16 hidden unites and weight decay of parameter $5\times 10^{-4}$ for all chains data sets with different $l$. Four representative baselines are chosen: Stochastic Steady-state Embedding (SSE) (Dai et al.,, 2018), Graph Convolutional Network (GCN) (Kipf and Welling,, 2016), Simple Graph Convolution (SGC) (Wu et al., 2019a, ) and Graph Attention Network (GAT) (Veličković et al.,, 2017). They all use the same hidden units and weight decay as IGNN. For (GAT), 8 head attention is used. For (SSE), we use the embedding directly as output and fix-point iteration $n_{h}=8$, as suggested (Dai et al.,, 2018).

As mentioned in Section 5, convolutional GNNs with $T=2$ cannot capture the dependency with a range larger than $2$-hops. To see how convolutional GNNs capture the long-range dependency as $T$ grows, we give an illustration of Micro-$F_{1}$ verses $T$ for the selected baselines in Figure 4. From the experiment, we find that convolutional GNNs cannot capture the long-range dependency given larger $T$. This might be a result of the limited number of training nodes in this chain task. As $T$ grows, convolutional GNNs experience an explosion of number of parameters to train. Thus the training data becomes insufficient for these models as the number of parameters increases.

E.2 Node Classification

For node classification task, we consider the applications under both transductive (Amazon) (Yang and Leskovec,, 2015) and inductive (PPI) (Hamilton et al.,, 2017) settings. Transducive setting is where the model has access to the feature vectors of all nodes during training, while inductive setting is where the graphs for testing remain completely unobserved during training. The statistics of the data sets can be found in Table 3.

For experiments on Amazon, we construct a one-layer IGNN with 128 hidden units. No weight decay is utilized. The hyper parameters of baselines are consistent with (Yang and Leskovec,, 2015; Dai et al.,, 2018).

For experiments on PPI, a five-layer IGNN model is applied for this multi-label classification tasks with hidden units as and $\kappa=0.98$ for each layer. In addition, four MLPs are applied between the first four consecutive IGNN layers. We use the identity output function. Neither weight decay nor dropout is employed. We keep the experimental settings of baselines consistent with (Veličković et al.,, 2017; Dai et al.,, 2018; Kipf and Welling,, 2016; Hamilton et al.,, 2017).

E.3 Graph Classification

For graph classification, 5 bioinformatics data sets are employed with information given in Table 1. We compare IGNN with a comprehensive set of baselines, including a variety of GNNs: Deep Graph Convolutional Neural Network (DGCNN) (Zhang et al.,, 2018), Diffusion-Convolutional Neural Networks (DCNN) (Atwood and Towsley,, 2016), Fast and Deep Graph Neural Network (FDGNN) (Gallicchio and Micheli,, 2019), GCN (Kipf and Welling,, 2016) and Graph Isomorphism Network (GIN) (Xu et al.,, 2018), and a number of state-of-the-art graph kernels: Graphlet Kernel (GK) (Shervashidze et al.,, 2009), Random-walk Kernel (RW) (Gärtner et al.,, 2003), Propagation Kernel (PK) (Neumann et al.,, 2016) and Weisfeiler-Lehman Kernel (WL) (Shervashidze et al.,, 2011). We reuse the results from literatures (Xu et al.,, 2018; Gallicchio and Micheli,, 2019) since the same experimental settings are maintained.

As of IGNN, a three-layer IGNN is constructed for comparison with the hidden units of each layer as 32 and $\kappa=0.98$ for all layers. We use an MLP as the output function. Besides, batch normalization is applied on each hidden layer. Neither weight decay nor dropout is utilized.

E.4 Heterogeneous Networks

For heterogeneous networks, three data sets are chosen (ACM, IMDB, and DBLP). Consistent with previous works (Park et al.,, 2019), we use the the publicly available ACM data set (Wang et al.,, 2019), preprocessed DBLP and IMDB data sets (Park et al.,, 2019). For ACM and DBLP data sets, the nodes are papers and the aim is to classify the papers into three classes (Database, Wireless Communication, Data Mining), and four classes (DM, AI, CV, NLP)DM: KDD,WSDM,ICDM, AI: ICML,AAAI,IJCAI, CV: CVPR, NLP: ACL,NAACL,EMNLP, respectively. For IMDB data set, the nodes are movies and we aim to classify these movies into three classes (Action, Comedy, Drama). The detailed information of data sets can be referred to Table 4. The preprocessing procedure and splitting method on three data sets keep consistent with (Park et al.,, 2019).

State-of-the-art baselines are selected for comparison with IGNN, including no-attribute network embedding: DeepWalk (Perozzi et al.,, 2014), attributed network embedding: GCN, GAT and DGI (Veličković et al.,, 2018), and attributed multiplex network embedding: mGCN (Ma et al.,, 2019), HAN (Wang et al.,, 2019) and DMGI (Park et al.,, 2019). Given the same experimental settings, we reuse the results of baselines from (Park et al.,, 2019).

A one-layer IGNN with hidden units as 64 is implemented on all data sets. Similar to DMGI, a weight decay of parameter $0.001$ is used. For ACM, $\kappa=(0.55,0.55)$ is used for Paper-Author and Paper-Subject relations. For IMDB, we select $\kappa=(0.5,0.5)$ for Movie-Actor and Movie-Director relations. For DBLP, $\kappa=(0.7,0.4)$ is employed for Paper-Author and Paper-Paper relations. As mentioned in Appendix D, in practice, the convergence property can still hold when $\sum_{i}\kappa_{i}>1$.

E.5 Over-smoothness

Convolutional GNNs has suffered from over-smoothness when the model gets deep. An interesting question to ask is whether IGNN suffers from the same issue and experience performance degradation in capturing long-range dependency with its "infinitively deep" GNN design.

In an effort to answer this question, we compared IGNN against two latest convolutional GNN models that solve the over-smoothness issue, GCNII Chen et al., (2020) and DropEdge Rong et al., (2020). We use the same experimental setting as the Chains experiment in section 5. Both GCNII and DropEdge are implemented with 10-layer and is compared with IGNN in capturing long-range dependency. The result is reported in Figure 5. We observe that IGNN consistently outperforms both GCNII and DropEdge as the chains gets longer. The empirical result suggest little suffering from over-smoothness for recurrent GNNs.