LSGNN: Towards General Graph Neural Network
in Node Classification by Local Similarity

We denote an undirected graph without self-loops as $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\{v_{i}\}_{i=1}^{n}$ is the node set and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the edge set. Let $\mathcal{N}_{i}$ denotes the neighbours of node $v_{i}$. Denote by $\mathbf{A}\in\mathbb{R}^{n\times n}$ the adjacency matrix, and by $\mathbf{D}$ the diagonal matrix standing for the degree matrix such that $\mathbf{D}_{ii}=\sum_{j=1}^{n}\mathbf{A}_{ij}$. Let $\tilde{\mathbf{A}}$ and $\tilde{\mathbf{D}}$ be the corresponding matrices with self-loops, i.e., $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$ and $\tilde{\mathbf{D}}=\mathbf{D}+\mathbf{I}$, where $\mathbf{I}$ is the identity matrix. Denote by $\mathbf{X}=\{\bm{x}_{i}\}_{i=1}^{n}\in\mathbb{R}^{n\times d}$ the initial node feature matrix, where $d$ is the number of dimensions, and by $\mathbf{H}^{(k)}=\{\bm{h}_{i}^{(k)}\}_{i=1}^{n}$ the representation matrix in the $k$-th layer. We use $\mathbf{Y}=\{\bm{y}_{i}\}_{i=1}^{n}\in\mathbb{R}^{n\times C}$ to denote the ground-truth node label matrix, where $C$ is the number of classes and $\bm{y}_{i}$ is the one-hot encoding of node $v_{i}$’s label.

SGC Wu et al. (2019) claims that the nonlinearity between propagation in GCN (i.e., the ReLU activation function) is not critical, whereas the majority of benefit arises from the propagation itself. Therefore, SGC removes the nonlinear transformation between propagation so that the class prediction $\hat{\mathbf{Y}}$ of a $K$-layer SGC becomes

where $\mathbf{S}$ is a GNN filter, e.g., $\mathbf{S}=\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}$ is used in the vanilla SGC, and $\mathbf{W}$ is the learned weight matrix. Removing the nonlinearities, such a simplified linear model yields orders of magnitude speedup over GCN while achieving comparable empirical performance.

Existing GNN models are usually based on the homophily assumption that connected nodes are more likely to belong to the same class. However, many real-world graphs are heterophilic. For example, the matching couples in dating networks are usually heterosexual. Empirical evidence shows that when the homophily assumption is broken, GCN may be even worse than simple Multi-Layer Perceptrons (MLPs) that use merely node features as input Chien et al. (2021). Therefore, it is essential to develop a general GNN model for both homophilic and heterophilic graphs.

Pei et al. Pei et al. (2020) introduce a simple index to measure node homophily/heterophily. That is, the homophily $\mathcal{H}(v_{i})$ of node $v_{i}$ is the ratio of the number of $v_{i}$’s neighbours who have the same labels as $v_{i}$ to the number of $v_{i}$’s neighbours, i.e.,

and the homophily in a graph is the average of all nodes, i.e.,

Similarly, the heterophily of node $v_{i}$ is measured by $1-\mathcal{H}(v_{i})$, and the heterophily in a graph is $1-\mathcal{H}(\mathcal{G})$.

In this section, we present the Local Similarity Graph Neural Network (LSGNN), consisting of a novel propagation method named Initial Residual Difference Connection (IRDC) for better fusion (Section 3.2), and a LocalSim-aware multi-hop fusion (Section 3.4) and thus cope with both homophilic and heterophilic graphs. We also demonstrate the motivation of using LocalSim as an effective indicator of homophily (Section 3.3). Figure 1 shows the framework of LSGNN.

Simply aggregating representation from the previous layer (as applied by most GNNs) might lose important information and consequently incur over-smoothing issues. To obtain more informative intermediate representations, i.e., outputs of different layers, we propose a novel propagation method, namely Initial Residual Difference Connection (IRDC).

Based on the hypothesis that nodes with similar features are likely to belong to the same class, we start out by defining a simple version of Local Similarity (LocalSim) $\phi_{i}$ of node $v_{i}$ to indicate its homophily, i.e.,

where $\operatorname{sim}(\cdot,\cdot):(\mathbb{R}^{d},\mathbb{R}^{d})\mapsto\mathbb{R}$ is a similarity measure, e.g.,

Figure 2 shows the relation between node homophily and LocalSim (using Cosine similarity) on Cornell (left column) and Citeseer (right column) datasets. From the upper figures, we observe that the homophily/heterophily among nodes are different. In particular, Cornell is a heterophilic graph, while Citeseer is a homophilic graph. Moreover, the lower figures show a clear positive correlation between node homophily and LocalSim, which indicates that LocalSim can be used to represent node homophily appropriately.

In Section 3.3, we show that LocalSim, leveraging the local topology information, can identify the homophily of nodes. We apply LocalSim to learn the adaptive fusion of intermediate representations for each node.

The naive LocalSim in Equation (6) simply averages the similarity between the ego-node and its neighbors. In what follows, we refine the definition of LocalSim by incorporating nonlinearity, i.e., $d^{2}_{ij}$. Specifically, the refined LocalSim $\varphi_{i}$ of node $i$ is given by

where $\operatorname{MLP_{ls}}:\mathbb{R}^{2}\mapsto\mathbb{R}$ is a 2-layer perceptron. It is trivial to see that incorporating $d^{2}_{ij}$ via $\operatorname{MLP_{ls}}$ can encode the variance of series $\{d_{ij}\}_{v_{j}\in\mathcal{N}_{i}}$, since $\operatorname{Var}[d_{ij}]=\mathbb{E}[d_{ij}^{2}]-\mathbb{E}^{2}[d_{ij}]$ with respect to $v_{j}\in\mathcal{N}_{i}$. As a consequence, $\varphi_{i}$ can better characterize the real “local similarity” than $\phi_{i}$. To illustrate, we compare $\varphi_{i}$ and $\phi_{i}$ through a simple example. Suppose that node $v_{1}$ has two neighbours $v_{2}$ and $v_{3}$ such that $d_{12}=0$ and $d_{13}=1$, while node $v_{4}$ has two neighbours $v_{5}$ and $v_{6}$ such that $d_{45}=d_{46}=0.5$. Then, $\phi_{1}=\phi_{4}=0.5$, which cannot characterize the distinct neighbour distributions. On the other hand, by introducing nonlinearity, we can easily distinguish $\varphi_{1}$ and $\varphi_{4}$. Finally, we have the LocalSim vector for all nodes $\bm{\varphi}=[\varphi_{1},\varphi_{2},\dotsc,\varphi_{n}]\in\mathbb{R}^{n}$.

LocalSim can guide the intermediate representations fusion, i.e., using $\bm{\varphi}$ as local topology information when learning weights for fusion. In addition, we also introduce nonlinearity by using $\bm{\varphi}$ and $\bm{\varphi}^{2}$ together to generate weights, i.e.,

where $\bm{\alpha}_{I},\bm{\alpha}_{L},\bm{\alpha}_{H}\in\mathbb{R}^{n\times K}$ are the weights for node representation from each channel and $\operatorname{MLP}_{\alpha}\colon\mathbb{R}^{2}\mapsto\mathbb{R}^{3K}$ is a 2-layer perceptron. Then, the node representations for the $k$-th layer is computed as follows:

where $\mathbf{Z}^{(k)}\in\mathbb{R}^{n\times z}$ and $\bm{\alpha}_{I}^{(k)},\bm{\alpha}_{L}^{(k)},\bm{\alpha}_{H}^{(k)}\in\mathbb{R}^{n}$ for $k=1,2,\dotsc,K$, and $\bm{\alpha}_{I}^{(k)}\odot\tilde{\mathbf{H}}_{I}$ is the $i$-th entry of $\bm{\alpha}_{I}^{(k)}$ times the $i$-th row of $\tilde{\mathbf{H}}_{I}$ for $i=1,2,\dotsc,n$ (so do $\bm{\alpha}_{L}^{(k)}\odot\tilde{\mathbf{H}}_{L}^{(k)}$ and $\bm{\alpha}_{H}^{(k)}\odot\tilde{\mathbf{H}}_{H}^{(k)}$). Then, we obtain the final representation as $\tilde{\mathbf{H}}_{I}\|\mathbf{Z}^{(1)}\|\mathbf{Z}^{(2)}\|\dotsb\|\mathbf{Z}^{(K)}$, where $\|$ is the concatenation function. Finally, the class probability prediction matrix $\mathbf{\hat{Y}}\in\mathbb{R}^{n\times C}$ is computed by

where $\mathbf{W}_{\text{out}}\in\mathbb{R}^{(K+1)z\times C}$ is a learned matrix.

Inspired by the Featured Stochastic Block Model (FSBM) Chanpuriya and Musco (2022), in the following, we introduce FSBM with mixture of heterophily that can generate a simple synthetic graph with different node heterophily.

According to Definition 1 and Equation (2), nodes in the same subgraph have identical homophily in expectation, while nodes from different subgraphs have distinct homophily. We consider FSBMs with $n=1000$, 2 equally-sized communities $C_{1}$ and $C_{2}$, 2 equally-sized subgraphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, feature means $\mu_{1}=1$, $\mu_{2}=-1$, and noise variance $\sigma=1$. We generate different graphs by varying $\lambda_{1}=\frac{p_{1}}{p_{1}+q_{1}}$ and $\lambda_{2}=\frac{p_{2}}{p_{2}+q_{2}}$, where $\lambda_{1},\lambda_{2}\in[0,1]$ and high $\lambda_{\tau}$ means high homophily, with the expected degree of all nodes to 10 (which means $\frac{1}{4}(p_{\tau}+q_{\tau})n=10$ for $\tau=1,2$).

We employ graph-level weight and LocalSim-based node-level weight to classify the nodes. For LocalSim-based node-level weight, we use the proposed method in Section 3. For graph-level weight, we replace $\alpha$ in Equation (8) with learnable graph-level value. For the similarity measure, we use $\operatorname{sim}(x,y)=-(x-y)^{2}$, where $x$ and $y$ are scalar values. Finally, considering the simplicity of the synthetic networks, we use the simple LocalSim in Equation (6), and only use adjacency matrix with self-loop $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$ and set the layers of IRDC to one.

As shown in Figure 3, our LocalSim-based node-level weight consistently outperforms graph-level weight. In particular, when node homophily is significantly different among subgraphs, the graph-level weight performs poorly, while our approach still performs very well which can recognize the node homophily well and adaptively provide suitable filters.

In addition to the empirical investigation, we theoretically confirm the capabilities of LocalSim node-level weight. For simplicity, we assume the number of inter-community and intra-community edges for all the nodes is the same as their expectation and without self-loop. Suppose that the optimal graph-level weight can provide a global filter that achieves the best average accuracy among all subgraphs (not the best in every subgraph), while the optimal node-level weight can provide the optimal filter for each subgraph which can achieve the best accuracy in every subgraph. However, to achieve the optimal node-level weight, we need to estimate the node homophily $\lambda$, and LocalSim is used for the aim. Next, we investigate the effectiveness of using LocalSim to indicate $\lambda$.

We defer the proof to Appendix A. Theorem 1 states that $\mathbb{E}[\phi(v_{i})]$ linearly correlates to $\lambda_{\tau}$ when $v_{i}\in\mathcal{G}_{\tau}$, which suggests that LocalSim can represent the homophily $\lambda_{\tau}$ of node $v_{i}$ unbiasedly. We can also get that the expectation of L1-norm distance positively correlates to $|\lambda_{1}-\lambda_{2}|$. This indicates that our estimation is likely to perform better when $|\lambda_{1}-\lambda_{2}|$ goes up. When the gap between $\lambda_{1}$ and $\lambda_{2}$ shrinks, the two subgraphs become similar to each other, so does the optimal filter for each community. These results confirm the effectiveness of LocalSim indicating node homophily, which yields high performance in our empirical investigation.

We evaluate LSGNN on nine small real-world benchmark datasets including both homophilic and heterophilic graphs. For homophilic graphs, we adopt three widely used citation networks, Cora, Citeseer, and Pubmed Sen et al. (2008); Getoor (2012). For heterophilic graphs, Chameleon and Squirrel are page-page Wikipedia networks Rozemberczki et al. (2021), Actor is a actor network Pei et al. (2020), and Cornell, Texas and Wisconsin are web pages networks Pei et al. (2020). Statistics of these datasets can be seen in Appendix D.

For all datasets, we use the feature matrix, class labels, and 10 random splits (48%/32%/20%) provided by Pei et al. Pei et al. (2020). Meanwhile, we use Optuna to tune the hyperparameter 200 times in experiments. For LSGNN, we set the number of layer $K=5$.

There are three types of baseline methods, including non-graph models (MLP), traditional GNNs (GCN, GAT Velickovic et al. (2017), etc.), and GNNs tolerating heterophily (Geom-GCN, GPRGNN, etc.).

As shown in Table 1, LSGNN outperforms most of the baseline methods. On homophilic graphs, LSGNN achieves the SOTA performance on the Cora and Pubmed datasets and is lower than the best result by only 1.28% on the Citeseer dataset. On heterophilic graphs except Actor, LSGNN significantly outperforms all the other baseline models by 1.77%–11.00%. Specifically, the accuracy of LSGNN is 7.83% and 2.97% higher than GloGNN, the existing SOTA method on heterophilic graphs, on Chameleon and Cornell, is 11.00% higher than LINKX Lim et al. (2021) on Squirrel, and is 2.43% and 1.77% higher than ACM-GCN on Texas and Wisconsin. In particular, LSGNN achieves the best average accuracy, higher than the second-best by 3.60%. This demonstrates that LSGNN can achieve comparable or superior SOTA performance on both homophilic and heterophilic graphs.

We also conduct experiments on two large datasets: ogbn-arXiv (homophilic) and arXiv-year (heterophilic), both with 170k nodes and 1M edges but different labels, following settings in Hu et al. (2020) and Lim et al. (2021), see Appendix D for setting details. Table 2 shows that our method has competitive performance on both homophilic and heterophilic larger graphs.

LSGNN only needs to propagate once during training, and the networks for node-level weight are small. Thus the efficiency of LSGNN can be close to SGC’s. As shown in Figure 4(a), on the average training time over nine datasets, our proposed method is only slower than SGC, a simple and effective model, and is nearly 2$\times$ faster than GCN and GAT. This confirms the high training efficiency of LSGNN. See Appendix C for more setting details and detailed comparisons of training costs on each dataset.

To validate whether LSGNN  can alleviate the over-smoothing issue, we compare the performance between vanilla GCN and LSGNN under different layers of propagation (Figure 4(b)), see Appendix E for full results. It can be seen that GCN achieves the best performance at 2 layers, and its performance decreases rapidly as layers increase. In contrast, the results of LSGNN keep stable and high. The reasons are two-fold: (i) our IRDC can extract better informative representations, and (ii) our LocalSim-based fusion can adaptively remain and drop distinguishable and indistinguishable representations, respectively. Through these two designs, LSGNN can perform well as layers increase, which indicates the capability of LSGNN to prevent the over-smoothing issue.

LocalSim-based node-level weight (Section 3.4) can be regarded as a plug-and-play module, which can be added to existing GNNs that also fuse intermediate representations without involving extra hyperparameters, such as H₂GCN, GPRGNN, and DAGNN.

H₂GCN and GPRGNN use learned graph-level weight to fuse the intermediate representations, which is only replaced by LocalSim-based node-level weight here. Note that we only add LocalSim-based node-level weight into H₂GCN and GPRGNN, but not the enhanced filters or the high-pass filters. As shown in Table 3, the performance of both H₂GCN and GPRGNN increases significantly, indicating that taking each node’s local topology into consideration when fusing intermediate representations is more reasonable and effective than merely considering graph-level structure.

DAGNN also fuse intermediate representations by node-level weight, which however is simply mapped from each node’s representation and is learned without involving any local topology information, leading to a suboptimal result. We use LocalSim-based node-level weight in DAGNN similarly. The drmatic improving in Table 3 suggests that using LocalSim as local topology information can ensure the weight being learned more effectively. Although DAGNN is not designed for heterophilic graphs, it can also perform well on heterophilic graphs after using LocalSim-based node-level weight, and is even superior to H₂GCN on Squirrel.

In what follows, we investigate the effectiveness of LocalSim-based node-level weight, weighted self-loops, and IRDC. Specifically, in the baseline model, we use graph-level weight learned without any local topology information to fuse the intermediate representations, add self-loops when conducting graph filtering, and apply the propagation method used in GCNs. Then, the above components are added one by one to the baseline model for performance comparison. As shown in Table 4, all the components are effective and can bring great benefits to the model in terms of performance improvement.

Note that learning node-level weight without any local topology information (‘Rand’) might even bring negative effect on the model (lower than baseline by 0.39% on average). Once LocalSim is used as local topology information, the model can easily learn an optimal node-level weight (75.16% on average, higher than the baseline by 1.32%), which indicates the superiority of LocalSim-Aware Multi-Hop Fusion.

When replacing the fixed self-loops with weighted self-loops, the performance increases significantly (by 2.34% to 77.50% on average), especially on heterophilic graphs, such as Chameleon and Squirrel. This is because self-loops might not always be helpful on heterophilic graphs.

IRDC also brings a significant improvement (by an increase of 1.71% to 79.21% on average). This suggests that such a propagation method can extract more informative representation for better performance.