NetInfoF Framework: Measuring and Exploiting Network Usable Information
Authors: Meng-Chieh Lee
Haiyang Yu
Jian Zhang
Vassilis N. Ioannidis
Xiang song
Soji Adeshina
Da Zheng
Christos Faloutsos
Venue: ICLR 2024 spotlight (2024)
Keywords: Graph Neural Networks
Information Theory
Heterophily Graphs
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a framework that measures the usable information of graphs and exploits it to solve the graph tasks, namely link prediction and node classification.

Abstract: Given a node-attributed graph, and a graph task (link prediction or node classification), can we tell if a graph neural network (GNN) will perform well? More specifically, do the graph structure and the node features carry enough usable information for the task? Our goals are
(1) to develop a fast tool to measure how much information is in the graph structure and in the node features, and
(2) to exploit the information to solve the task, if there is enough.
We propose NetInfoF, a framework including NetInfoF_Probe and NetInfoF_Act, for the measurement and the exploitation of network usable information (NUI), respectively. Given a graph data, NetInfoF_Probe measures NUI without any model training, and NetInfoF_Act solves link prediction and node classification, while two modules share the same backbone.
In summary, NetInfoF has following notable advantages:
(a) General, handling both link prediction and node classification;
(b) Principled, with theoretical guarantee and closed-form solution;
(c) Effective, thanks to the proposed adjustment to node similarity;
(d) Scalable, scaling linearly with the input size.
In our carefully designed synthetic datasets, NetInfoF correctly identifies the ground truth of NUI and is the only method being robust to all graph scenarios. Applied on real-world datasets, NetInfoF wins in 11 out of 12 times on link prediction compared to general GNN baselines.

Published as a conference paper at ICLR 2024
NETINFOF FRAMEWORK: MEASURING AND EXPLOITING NETWORK USABLE INFORMATION
Meng-Chich Lee'., Haiyang Yu², Jian Zhang', Vassilis N. loannidis', Sainidis"XXinn Song', Soji Adeshina', Da Zheng*1, Christos Faloutsos 1..1 'Carnegie Mellon University, Teeas A&M University, 'Amazon (mengehil, christos @cs. cmu edu, (haiyangh @tt.g/ttammmu..mmmmmmm edu, jamezhan, ivasilei, xiangsx, adeso jia, dzzhen eamazonn@amano.....mmmm
amazon......... com
ABSTRACT
Given a node-attributed graph, and a graph task (link prediction or node classi- fication), can we tell if graph neural network (GNN) will perform well? More specifically, do the graph structure and the node features carry enough usable in- formation for the task? Our goals are (I) develop a fast tool to measure how much information is in the graph structure and in the node features, and (2) to exploit the information INFOF, framework including NETINFOF PROBE and NETINFOF ACT, for the measurement and the exploitation of network usable information (NUT), respec- tively. Given graph data, NETINFOF PRROBE measures NUI without any model training, and NETINFOF ACT solves link prediction and node classification, while modules share the same backbone. In summary, NETINFOF has following notable advantages: (a) General, handling both link prediction and node clas- sification; (b) Principled, with theoretical guarantee and closed-form solution; (c) Effective, thanks to the proposed adjustment to node similarity; (d) Scalable, scaling linearly with the input size. In our carefully designed synthetic datasets, NETINFOF correctly identifies the ground truth of NUI and is the only method being robust all graph scenarios. Applied on real-world datasets, NETINFOF wins in / out of 12 times on link prediction compared to general GNN baselines.
solve the task, if there is enough. We propose NET-
INTRODUCTION
Given a graph with node features, how tell if graph neural network (GNN) can perform well on graph tasks or not? How can we know what information (if any) is usable to the tasks, namely, link prediction and node classification? GNNs (Kipf & Welling, 2017: Hamilton et al., 2017; Veličković et al., 2018) are commonly adopted on graph data to generate low-dimensional representations that are versatile for performing different graph tasks. However, sometimes there are no network effects, and training a GNN will be waste of computation time. That is to say, we want measurement of how informative the graph structure and node features are for the task at hand, which we call network usable information (NUI).
We propose NETINFOF, framework to measure and exploit NUI given graph. First, NET- ANFOF_PRORE measures NUI of the given graph with NETINFOF (Eq. 2), which we proved is lower-bound the accuracy (Thm. 2). Next, our NETINFOF ACT solves both the link prediction and node classification by sharing the same backbone with NETINFOF_ fort, we propose to compute NETINFOF -SCORE by representing different components of the graph with carefully derived node embeddings. For link prediction, we propose the adjustment to node similarity with a closed- -frm formula to address the limitations when the embeddings are static. We demonstrate that our derived embeddings contain enough usable information, by showing the supe- rior performance on both tasks. In Fig. 1, NETINFOF ACT outperforms the GNN baselines most times on link prediction; in Fig. 2, NETINFOF SCoRE measured by NETINFOF PROBE highly cor- relates to the test performance in real-world datasets.
To save training ef-
"The work done while being an intern at Amazon.
1 "oorrsponniig authors.

---

Published as a conference paper at ICLR 2024
Competitor Hits@K
100
X-y
1.0
2=2x-1
1.0
GCN
Test Accuracy
Test Hits@k
0.8
GAT
0.6
H25CN
NETINFOF
Ideal
0.6
CPR-GNN
Wins!
Slmm
Ideal
0.4
0.2
20
0.7 0.8 NetInfoF Score
0.4
0.8
NetInfoF Seconn
Score
20
40
80 100
(b) Node Classification NETINFOF wins in real- Figure 2: NETINFOF SCORE highly correlates to test
NetInfoF Hits@K
(a) Link Prediction
Figure 1:
world datasets on link prediction (most performance in real-world datasets. Each point denotes points are below or line = y). the result of component from each dataset.
In summary, our proposed NETINFOF has following advantages:
1. General, handling both node classification and link prediction (I (Lemma 1-2); 2. Principled, with theoretical guarantee (Thm. 1-2) and closed-form solution (Lemma 1-2);
3. Effective, thanks the proposed adjustment of node similarity (Fig. 1);
4. Scalable, scaling linearly with the input size (Fig. 6).
In synthetic datasets, NETI correctly identifies the ground truth of NUI and is the only method being robust to all possible graph scenarios; in real-world datasets, NETINFOF wins in // out of 12 times on link prediction compared to general GNN baselines.
Reproducibility: Code is at https://github... http:://gihub..oo/mmaooooo wwwpaaaazooossinceeeetttteee Usable- Info- Framework.
2 RELATED WORKS
Table 1:
NETINFOF matches all properties.
We introduce the related work in two groups: information theory, and GNNs. In a nut- shell, NETINFOF the only one fulfills all the properties as shown in Table 1.
while baselines miss more than one property.
Subgraph GNNe
Genera GNN'
NETINOP
Information Theory. The typical measure of the dependence between the random vari- ables is the mutual information (Kraskov et al., 2004). is powerful and widely used in sequential feature selection (Li et al., 2017), but its exact computation is difficult (Panin- ski. 2003; Belghazi et al., 2018) especially on continuous random variables (Ross, 2014; Mesner & Shalizi, 2020) and high-dimensional data (François et al., 2006; Mielniczuk Teisseyre, 2019). Recently (Xu et al., 2020; Ethayarajh et al., 2022) proposed the concept of y-information. However, the definition needs trained model, which is expensive to obtain and is dependent on the quality of training.
Slmm
Property
1. General
I.I. Node Classiication
Graph Task
1.2. Link Prediction
2. Principted
Theoretical Guarantee
2.2. Closed-Form Solution
3. Scalable
Robust
4.1. Node Classilcation
w.E.L. Input Scenario
4.2. Link Prediction
Only few works study the usable information in the graphs, but not feasible in our problem settings because of three challenges, i.c., our desired method has to: (1) work without training any models, where Akhondzadch al. (2023) requires model training: (2) identify which components of the graph are usable, where Dong & Kluger (2023) ignores the individual components; and (3) generalize to different graph tasks, where Lee et al. (2022) focuses on node classification only.
Graph Neural Networks. Although most GNNs learn node embeddings assuming homophily, some GNNs (Abu-El El-ja et al., 2019; Zhu et al., 2020; Chien al., 2021; Liu et al., 2021) break this assumption by handling k-step-away neighbors differently for every k. and some systematically study the heterophily graphs on node classification (Platonov et al., 2022: Luan et al., 2022: 2023; Mao al., 2023; Chen al., 2023; Ma et al., 2021). Subgraph GNNs (Zhang & Chen, 2018; Yin et al., 2022) are designed only for link prediction and are expensive in inference. On the other hand, linear GNNs (Wu al., 2019; Wang et al., 2021; Zhu & Koniusz, 2021; Li et al., 2022; Yoo al., 2023) target interpretable models. Such approaches remove the non-linear functions and maintain good performance. As the only method being robust to all graph scenarios, SLIMG (Yoo et al., 2023) works well on node classification. However, it is unclear how well it works for link prediction. In conclusion, the proposed NETINFOF the only one that fulfills all the properties in Table 1.
2

---

Published as a conference paper at ICLR 2024
3 BETINFOF-SCORE WOULD A GNN WORK?
How to tell whether GNN will perform well on the given graph task? A graph data is composed of more than one component, such as graph structure and node features. In this section, we define our problem, and answer two important questions: (1) How measure the predictive information of each component in the graph? (2) How to connect the graph information with the performance metric on the task? We identify that a GNN is able to perform well on the task when its propagated representation is more informative than graph structure or node features.
3.1 PROBLEM DEFINITION
Given an undirected graph G = (V. E) with node features X vix where f is the number of fea- tures, the problem is defined as follows:
Measure the network usable information (NUT), and Exploit NUI, if there is enough, solve the graph task.
We consider two most common graph tasks, namely link prediction and node classification. In link prediction, & is split into &qain and Epss. The negative edge set Eneg is randomly sampled with the same size of Epss The goal is to predict the existence of the edges, for the edges in Epocs and 0 for
the ones in Ene- In node classification, |Vrainl node labels y {1,.... c) Maizl are given, where is the number of classes. The goal is to predict the rest [V] D unlabeled nodes' classes.
3.2 PROPOSED DERIVED NODE EMBEDDINGS
To tell whether a GNN will perform well, can analyze its node embeddings, but they are only available after training. For this reason, we propose to analyze the derived node embeddings in linear GNNs. More specifically, we derive 5 different components of node embeddings that can represent the information of graph structure, node features, and features propagated through structure.
Cl: Structure Embedding. The structure embedding U is the left singular vector of the adjacency matrix A, which is extracted by the singular value decomposition (SVD). This aims to capture the community information of the graph.
C2: Neighborhood Embedding. The neighborhood embedding R aims to capture the local higher- order neighborhood information of nodes. By mimicking Personalized PageRank (PPR), we con- struct random walk matrix AppR, where each element is the number of times that node visits another node in T trials of the kspR-step random walks. By doing random walks, the local higher- order structures will be highlighted among the entire graph. To make Appr sparser and to speed up the embedding extraction, we eliminate the noisy elements with only one visited time. We extract the left singular vectors of AppR by SVD the neighborhood embeddings R.
C3: Feature Embedding. Given the raw node features X, we represent the feature embedding with the preprocessed node features F (X), where g is the preprocessed function.
C4: Propagation Embedding without Self-loop. We row-normalize the adjacency matrix into ARow D A, where D is the diagonal degree matrix. The features are propagated without self- loop to capture the information of krow-Step neighbors, where knw is an even number. This is useful capture the information of similar neighbors when the structure exhibits heterophily (e.g., in bi- partite graph). Therefore, we have node embedding P = (I( X)), where I is the column- wise L2- 12-normalization ensuring every dimension has similar scale.
C5: Propagation Embedding with Self-loop. The adjacency matrix with self-loop has been found useful to propagate the features in graphs that exhibit homophily. Following the most common strategy, we symmetrically normalize the adjacency matrix into Asym = (D + - (A + I)(D + I where I is the identity matrix. Similar to C4, we have node embeddings S = ( from sym X)).
While C1-2 aim to capture the information with only the graph structure, C4-5 aim to capture the information of propagation, which is similar to the one that trained GNN can capture. To ensure that the embeddings have intuitive meanings, we set all the number of steps kppR, kno and ksym as 2, which works sufficiently well in most cases. As C1-2 adopted SVD their last step, the embedding
3

---

Published as a conference paper at ICLR 2024
Xmy
X-y
Valld Accuracy
0.5
Vallid Accuracy
Test HisS@ 100
Test Accuracy
0.75
0.75
0.6
97
0.4
0.8
(Thorem 2)
Our Bound
Our Bound (Theorem
0.2
05
0.25
0.
0..9 R²
0.25
69 NetinfoF_Scoom
08 NetinfoF_Score _ccore
0.50 NetinfoF _ccore _eeon
NetinfoF_Scom
(a) Link Prediction
(b) Node Classification
(a) Link Prediction
(b) Node Classification
Figure 3: Thm. 2 holds. NETINFOF_S SCCORE is Figure 4: SEPINFOF_SCORE predicts right. It is
always less than or equal to validation accuracy. correlated to test performance in synthetic datasets.
dimensions are orthogonalized. For C3-5, use principal component analysis (PCA) as g to reduce and orthogonalize the embedding dimensions, leading to faster convergence and better performance when training the model. Each component has the same number of dimensions d.
3.3 NETINFOF SCORE: DEFINITION AND THEOREMS
Next, want to find formula that connects the metrics of graph information and task performance. To begin, we derive the inequality between entropy and accuracy:
Theorem (Entropy and Accuracy). Given a discrete random variable Y, we have:
2 H(Y < accuracy(Y)) = max Py
(1)
yeY
where =-Y)=-Eyet Py log denotes the Shannon entropy.
Proof. See Appx. A.I.
Before extending Thm. I to the case with two random variables, we need a definition:
Definition 1 (NETINFOF of Y given X). Given two discrete random variables X and Y, NETINFOF SCORE of Y given is defined as:
NETINFOF SIIINFFFSSCOREEEE -
(2)
where H(-I-) denotes the conditional entropy.
We prove that NETINFOF SCORE low-bounds the accuracy:
Theorem 2 (NETINFOF SCORE). Given discrete random variables X and Y, NET- INFOF_SCORE of given low-hounds the accuracy:
NETINFOF SCORE 2-H(YIX) S aaccurac(Y|(x)
Σ
max Pr.y yEY
(3)
#EX
where Pa,y is the joint probability of x and y.
Proof. See Appx. A.2.
Thm. 2 provides an advantage to NETINFOF SCORE by giving it intuitive interpretation, which is the lower-bound of the accuracy. When there is little usable information to the task, the value of CEIINNOF_SCORRP is close to random guessing. To empirically verify it, we run the experiments on the synthetic datasets (Appx. D. with five splits, and report NETINFOF.SCOOM SCORE and accuracy for all components the derived embeddings. In Fig. 3, we find that even for the validation set, NETINFOF-SCORE is always less than equal to the accuracy, strictly following Thm. 2. In the next sections, we show how NETINFOF SCORE can be effectively and efficiently computed with proposed NETINFOF PROBE.
4

---

Published as a conference paper at ICLR 2024
4 NETINFOF FOR LINK PREDICTION
With the derived node embeddings, how can we measure NUI in link prediction as well as solve the task? Compared to general GNNs, the node embeddings of linear GNNs are given by closed- form formula. They are thus rarely applied on link prediction because of following two reasons: (I) Predicting links by GNNs relies on measuring node similarity, which is incorrect if the neighbors are expected to have dissimilar embeddings; for example, in a bipartite graph, while source node connected a target node, their structural embeddings are expected to be very different, resulting in low node similarity by linear GNNs; (2) In order to perform well on Hits @ K, it is crucial to suppress the similarity of the nodes of negative edges, i.c. the unexisting connections in the graph. Hits @ K is the ratio of positive edges that are ranked K-th place above among both the positive and negative edges, which is preferred in link prediction where most real-world applications are recommendations. Since the embeddings of linear GNNs static, they not learn separate the embeddings of nodes on each side of the negative edges. Therefore, how to generalize linear GNNs to solve link prediction remains challenge.
For these reasons, we propose an adjustment to the similarity of the nodes, which generalizes NET- INFOF link prediction, including NETINFOF_ to measure NUT and NETINFOF.ACT to solve the task.
4.1 PROPOSED ADJUSTMENT TO NODE SIMILARITY
To solve the limitations of linear GNNs on link prediction, it is crucial to properly measure the simi- larity between nodes. We consider cosine similarity as the measurement, whose value is normalized between 0 and 1. By 1.2-normalzzing each node embedding Zixd- the cosine similarity reduces to simple dot product z; z,. However, even if node i and node j connected by edge, it may result in low value if they are expected to have dissimilar embeddings (e.g. structure embeddings in bipartite graph). Therefore, before the dot product, we propose using the compatibility matrix Haxa to transform one of the embeddings, and rewrite the node similarity function into z, Hzzz..
The compatibility matrix H represents the characteristics of the graph: if the graph exhibits ho- mophily, H is nearly diagonal; if it exhibits heterophily, H is off-diagonal. It is commonly assumed, given in belief propagation (BP) to handle the interrelations between node classes. In our case, H represents the interrelations between the dimensions of the node embeddings. By maximizing the similarity of nodes connected by edges, H can be estimated by the following lemma:
Lemma 1 (Compatibility Matrix). The compatibility matrix H has the closed-form solution and can be solved by the following optimization problem:
min Σ 1 Zz 121
(4)
(LJ)EE
where & denotes the set of (positive) edges in the given graph.
Proof. See Appx. A.3.
This optimization problem can be efficiently solved by multi-target linear regression. Nevertheless, this estimation of H does not take into account negative edges, which may accidentally increase the similarity of negative edges in some complicated cases. This hurts the performance especially when evaluating with @its@ K. Therefore, based on Lemma 1, we propose an improved estimation H*, which further minimizes the similarity of nodes connected by the sampled negative edges:
Lemma 2 (Compatibility Matrix with Negative Edges). The compatibility matrix with negative edges H' has the closed-form solution and can be solved by the following optimization problem:
min (1-HH(2)) H
Σ
(2,HH²z)).
(5)
(GJ)EE
(i
where Eneg denotes the set of negative edges.
Proof. See Appx. A.4.
5

---

Published as a conference paper at ICLR 2024
With great power comes great responsibility, estimating H" has higher computational cost than estimating H. Thus, we provide three techniques to speed up the computation of H with the help of H, and the details are in Algo. 1.
TI: Warm Start. We approximate the solution by LSQR itcratively and warm up the approximation process with H. Since H is similar to H' and cheap compute, this step largely speeds up the approximation process and reduces the number of iterations needed for convergence.
T2: Coefficient Selection. We reduce the number of coefficients by only estimating the upper tri- angle of H", and keep the ones with 95% energy in H. This is because the similarity function is symmetric, and the unimportant coefficients with small absolute values in H remain unimportant in H The absolute sum of the kept coefficients divided by Σ Žj-it1 H
95% and the rest are zeroed out. This helps us reduce the number of coefficients from d² to be less than (d + 1)d/2.
T3: Edge Reduction. We sample S positive edges from the 2-core graph, and 28 negative edges, where the sample size S depends on d. Since in large graphs [&] is usually much larger than d², necessary to estimate fewer than (d + 1)d/2 coefficients with all |] edges. Moreover, the 2- core graph remains the edges with stronger connections, where each node in it has at least degree 2. Sampling from the 2-core graph avoids interference from noisy edges and leads to better estimation.
4.2 NETINFOF PROBEE FOR NUI MEASUREMENT
Based on Thm. 2, we propose NETINFOF_ PRRBBE that computes NETINFOF.SCORE without actly computing the conditional entropy of the high-dimensional variables. By sampling negative edges, the link prediction can be seen of embeddings, NETINFOF_ PROBBB esitmates its corresponding H' and discretizes the adjusted node similarity of positive and negative edges. To avoid overfitting, fit the k-bins discretizer with the similarity of training edges, and discretize the one of validation edges into A bins. NET- categorical variables. For instance, the node similarity between node i and with embedding U is ( U,, where denotes the em- bedding preprocessed by column-wise standardization and row-wise L2-normalization. The details are in Algo. 2.
binary classification problem. For each component
SFFOFSSCORE can then be easily computed between
4.3 NETINFOF FOR NUI EXPLOITATION
To solve link prediction, NETINFOF ACT shares the same derived node embeddings with NET- INFOF PROBE, and uses link predictor following by the Hadamard product of the embeddings. We transform the embeddings on one side of the edge with H', which handles the heterophily em- beddings and better separates the nodes in the negative edges. By concatenating all components, the input to the predictor is as follows:
U Ú R.H
O R
F
F. O I
P.H. P.H.POP
I S. S
(6)
Structure
PPR
Features
Features of 2-Stop Neighbors
Features of Grand Neighbors
where (i,j) E E Ensg- Among all the choices, we use LogitReg as the predictor for its scalability and interpretability. We suppress the weights of useless components, if there is any, by adopting sparse-group LASSO for the feature selection. The time complexity of NETINFOF ACT is:
Lemma 3. The time complexity of NETINFOF-ACTI for link prediction is linear on the input size |E|:
f"
where I and d are the number of features and embedding dimensions, respectively.
Proof. See Appx. A.5.
5 NETINFOF FOR NODE CLASSIFICATION
In this section, we show how we can generalize NETINFOF to node classification. In contrast to link prediction, node classification does not rely the node similarity, needing no compatibility matrix.

---

Published as a conference paper at ICLR 2024
5.1 NETINFOF_PRORE FOR NUI MEASUREMENT
To effectively and efficiently compute NETINFOF_SCORE propose to assign labels to the nodes by clustering. This idea based on the intuition that good embeddings for node classification can be easily split by clustering. Among clustering methods, we use k-means it is fast. We cluster each component of the embeddings and compute NETINFOF _SCORE, where 2 c. To ensure that the clustering is done stably, row-wise L2-normalization is done the embedding. The details are in Algo. 3.
5.2 NETINFOF-ACE FOR NUI EXPLOITATION
To solve node classification, we again concatenate the embeddings of different components, and the input of classifier as follows:
I(S)
(8)
Features 2-Step Neighbors
Features Grand Neighbors
where is the column- wise L2- 1.2-noralization. Similar to NETINFOF in link prediction, we use LogitReg the classifier and adopt sparse-group LASSO for the regularization.
SYNTHETIC DATASETS FOR SANITY CHECKS
To ensure that NETINFOF is robust to all graph scenarios, we carefully design the synthetic datasets for sanity checks. We include all possible graph scenarios, where the ground truth of NUI is avail- able. The details of implementation are in Appx. D.1.
6.1 LINK PREDICTION
Designs. We separate the nodes into e groups to simulate that there are usually multiple communities in graph. To cover all the possibilities in the real-world the scenarios the cross-product of different scenarios on the node features X and the graph structure A, as shown in Fig. 5. We ignore the scenario that X is useful but A is useless, since this is impractical in the real-world.
There are 3 scenarios of node features X:
1. Random: the node features random, with correlation with the existence of edges.
2. Global: all dimensions of the node features are correlated with the existence of edges.
3. Local: only subset of dimensions of the node features are correlated with the existence of edges, where there is no overlapping between the subsets of node groups.
There are scenarios of graph structure A:
1. Diagonal: the nodes and their neighbors are in the same group.
2. Oit-Diagonal: the nodes and their neighbors are two different groups.
Observations. In Table 2, NETINFOF receives the highest average rank among all GNN baselines. and is the only method that can handle all scenarios. While GNNs have worse performance when X is either random or local, SLIMG, linear GNN, cannot handle cases with off-diagonal A.
Would GNN work? Fig. 4a shows that NETINFOF.ScOme is highly correlated with test Hits @ 100, with high R² values, where each point denotes a component of embeddings from each split of synthetic datasets. In Appx. C. Table reports NETINFOF SCORE and test performance of each component. By measuring their NETINFOF SCORE, NETINFOF PRROBE tells when prop- agating features through structure contains less information than using features or structure itself. For example, in scenarios where node features are useless (the first two scenarios in Table 6). NET- INFOF PROBE spots that F (i.e., g(X)) provides little NUI to the task, and thus the propagated embeddings P and S have less NUI than the structural embeddings U and R. This indicates that training GNNs is less likely to have a better performance than only utilizing the information from
the graph structure, which correctly matches the test performance in Table 6.

---

Published as a conference paper at ICLR 2024
Global
Locel
Group
Diagonal
Oth
Table 2: NETINFOF wins on link prediction in the syn- thetic datasets. Hits @ 100 is reported.
Medel
Rond. X
Deg.
Off.lag
Rand. X
Global X
Dlgg
Giobal OH--1ing.
Diag. A
Loca X
Lucal Ott-Nong
Renk
800
1.000
14
4000
552222
110212
095219
5.111
GAT
86.1.00 0.
81.1:011
87:3:09
8523105
160120
16912
3.5
HFGCN GNN
2455=k.3
589933
753ee11
558=25
182215
50:2.1
Figure 5: Scenarios of node features X and graph structure A synthetic datasets.
75.1-08
45,7=08
52.32166
57.6610
83
70.5216
55.1-13
31.1111
171122
33.1.3)
6.11.
NerissoF
813:607
86.:88
803:93
$98:10
806202
905207
1..00.)
6.2 NODE CLASSIFICATION
Designs. We remain the same scenarios in SLIMG, while using our graph generator in Appx. D.1.
Observations. Fig. 4b shows that NETINFOF SCORe is highly correlated with test accuracy. In Appx. C.5, Table 10 shows that NETINFOF generalizes to all scenarios as SLIMG does; Table 11 shows that the component with the highest NETINFOF SCORe always has the highest test accuracy.
EXPERIMENTS
We conduct experiments by real-world graphs to answer the following research questions (RQ):
RQI. Effectiveness: How well does NETINFOF perform in real-world graphs?
RQ2. Scalability: Does NETINFOF scales linearly with the input size?
RQ3. Ablation Study: Are all the design choices in NETINFOF necessary?
The details of datasets and settings are Appx. D. Since we focus on improving linear GNNs in link prediction, the experiments for node classification are in Appx. C.6 because of space limit. The experiments are conducted on an AWS EC2 G4dn instance with 192GB RAM.
7.1 EFFECTIVENESS (RQ1)
Real-World Datasets. We evaluate NETINFOF on homophily and 5 heterophily real-world graphs. We randomly split the edges into training, validation, and testing sets by the ratio 2ff/10%%/2ff five times and report the average for fair comparison. Since our goal is pro- pose a general GNN method, we focus on comparing NETINFOF with 6 GNN baselines, which are general GNNs (GCN, SAGE, GAT), heterophily GNNs (H'GCN, GPR-GNN), and linear GNN (SLIMG). While Hits @ 100 is used for evaluating most graphs, Hits 1000 is used on the larger ones, namely, Products, Twitch, and Pokec, which have much more negative edges in the testing sets.
In Table 3, NETINFOF outperforms GNN baselines in 11 out of 12 datasets, and has the highest average rank, as our derived embeddings include comprehensive graph information, that is, struc- ture, features, and features propagated through structure. Compared to non-linear GNNs, SLIMG performs worse in most heterophily graphs, showing that it cannot properly measure the node sim- ilarity of heterophily embeddings in link prediction. By addressing the limitations of linear GNNs, NFTINFOF is able to consistently outperform both SLIMG and non-linear GNNs in both homophily and heterophily graphs. Note that the results in Pokec are similar to the ones in homophily graphs, since it can be labeled as either homophily (by locality) or heterophily (by gender).
Table 3: NETINFOF wins on link prediction in most real-world datasets. Hits @ 100 is reported for most datasets, and Hits @ 1000 for the large datasets (Products, Twitch, and Pokec).
Mudd
Cora
CluSsor
Publiel
Camp-
Photo
ArNiv
Products
Cham.
Squirrel
Actor
Twitch
Pokic
Rank
OCN
67.1+1.8
606 10
47.6113
20.5-3.1
19.1
148+06
022246.1
82.1+4.5
16.++10
31. 11.1-1.
163440
07.9-1.
(.1(1.5)
SAGR
68.4+3.8
55.9-255
57.+1.1
23.5-2.1
400+1.9
00.+0.
00346.3
84.7436
15.5+1.5
2-.6-14
083406
85Sen.5
4.
GAT
66.763.6
65.2=2.
55.142.4
28.3-16
46243.
05.808
D.O.M.
848:45
156608
32.3-2.4
0822603
00M.
4.00..)
IPOCN
64.413.4
35.725.4
50.520.9
179907
20.412
0.M.
O.O.M.
703845
16082.6
25.7-211
G.O.M
00M.
62.00.0
GPR-GNN
60.9199
33.528.1
66.313.3
2077-1
36181.1
1384088
O.O.M.
77.2556
14662.7
1-.1
126602
050002
4.60.88
SLIMG
77.94135
16.8110
559428
25,3.09
40.2225
20.2110
27.6:0.6
76922.5
1964115
187--1
120103
21.7502
3.5)
NETISTOF
$1.35066
87.3:13
39741.1
31.1:19
468:22
39.11:8
35.211.1
869:23
34:2:111
362:11
196807
31.3:05
(.(33))
8

---

Published as a conference paper at ICLR 2024
Table 4: NETINFOF wins on link prediction in OGB datasets. Hits @ Hits@ 50, and Hits @ 100 are reported for ddi, collab, and ppa, respectively.
Run Time (s)
Slope=1
Model
ogbl-ddi
ogbl-collab
oghl-ppa
37.145.1
4488+1.1
18.74+1.3
10? 10"
SAGE
53.914.7
48.120.8
16.6:2244
Number Edges
SLIMG
35.9
45.1:10.2
21.140..6
Figure 6: NETINFOF AACT is scalable on link
NETINFOF
56.81:34
53.7:10.2
24.2:00.1
prediction, being linear with number of edges.
OGB Link Prediction Datasets. We evaluate NETINFOF on OGB datasets. Table 4 shows that NETINFOF outperforms other general GNN baselines, while using a model with much fewer pa- rameters. NETINFOF has only 1280 learnable parameters for all datasets, while GCN and SAGE have at least 279K and 424K, respectively, which is 218x more than the ones that NETINFOF has.
7.2 SCALABILITY (RQ2)
We plot the number of edges versus the time of link prediction in seconds the real-world datasets. In Fig. 6, we find that NETINFOF scales linearly with the number of edges, thanks to our speed-up techniques in estimating compatibility matrix H" To give a concrete example, the numbers of coefficients of Hú are reduced from d(d + 1)/2 8256 to 3208, 5373, and 4293, for Products, Twitch, and Pokec, respectively. Moreover, those numbers are very reasonable: Products is a homophily graph, its Hú has the fewest coefficients, which are mostly on the diagonal; Twitch a heterophily graph, its Hú has the most coefficients, which are mostly on the off-diagonal; Pokec can be seen either homophily or heterophily, its Hü has the number of coefficients in between.
7.3 ABLATION STUDY (RQ3)
To demonstrate the necessity of addressing the limitations of linear GNNs in link prediction with our design choices, we study NETI (1) without compatibility matrix (w/o CM), and (2) with only compatibility matrix (w/ only H), which is not optimized with negative edges. Table shows that NETINFOF works best with both design choices. In heterophily graphs, merely using H leads to better performance because of properly handling heterophily embeddings; while in homophily graphs, it accidentally increases the similarity between nodes in negative edges and hurts the per- formance. Taking into account both heterophily embeddings and negative edges, using H as the compatibility matrix has the best performance in both heterophily and homophily graphs.
Table 5: Ablation Study All design choices in NETINFOF necessary link prediction. CM stands for compatibility matrix, and H is not optimized with negative edges.
Model
Cora
CiteSeer
PubMed
Comp.
Photo
ArXiv
Products
Cham.
Squirrel
Actor
Twitch
Pokec
CM
79.--99
865++.6
585+1.2
27.40.
447-12
350+18
346404
74.+1.5
14.3-06
295++8
08900.8
30.5+0.3
w/ only H
80.9.05
$7.0114
588114
265112
434_11
325115
30..104
74,1332
19311.
322111
10.313.1
29.8.004
NoTINooF
81.3-06
87,3+13
59.+11
311+19
468-21
39.2118
35.2+1.1
869-23
242-20
362+11
1966+0.7
31,3+0L
CONCLUSIONS
We propose the NETINFOF framework measure and exploit the network usable information (NUT). In summary, NETINFOF has the following advantages:
1. General, handling both link prediction and node classification (Lemma 1-2);
2. Principled, with theoretical guarantee (Thm. 1-2) and closed-form solution (Lemma 1-2);
3. Effective, thanks the proposed adjustment of node similarity;
4. Scalable, scaling linearly with the input size (Fig. 6).
Applied carefully designed synthetic datasets, NETINFOF correctly identifies the ground truth of NUI and is the only method that is robust to all graph scenarios. Applied on real-world graphs, NETINFOF wins in // out of 12 times on link prediction.

---

Published as a conference paper at ICLR 2024
REFERENCES
Sami Abu-El-Haija. Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, In international conference machine learn- ing, pp. 21-29. PMLR, 2019.
Mohammad Sadegh Akhondzadeh, Vijay Lingam, and Aleksandar Bojchevski. Probing graph repre- sentations. In International Conference on Artificial Intelligence and Statistics, pp. 16300-11649.
PMLR, 2023.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pp. 531-540. PMLR, 2018.
Jie Chen, Shouzhen Chen, Junbin Gao, Zengfeng Huang, Junping Zhang, and Jian Pu. Exploiting neighbor effect: Conv-agnostic gnn framework for graphs with heterophily. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2021.
Courtesy of the US National Library of Medicine. Pubmed, 1996.
Mingze Dong and Yuval Kluger. Towards understanding and reducing graph structural noise for GNNs. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pp. 8202-8226. PMLR, 2023.
Dhivya Eswaran, Srijan Kumar, and Christos Faloutsos. Higher-order label homogeneity and spread- ing in graphs. In Proceedings of The Web Conference 2020, pp. 2493-2499, 2020.
Kawin Ethayarajh, Yejin Choi, and Swabha Swayamdipta. Understanding dataset difficulty with mathcal V -sable information. In International Conference on Machine Learning, pp. 5988- 6008. PMLR, 2022.
Damien François, Vincent Wertz, and Michel Verleysen. The permutation test for feature selection by mutual information. In ESANN, pp. 239-244, 2006.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wwXiv:20055006633 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information. Phys- ical review E. 69(6):066138. 2004.
Meng- Keng-ChhehhB Lee, Shubhranshu Shekhar, Jaemin Yoo, and Christos Faloutsos. Ultraprop: Principled and explainable propagation on large graphs. arXiv preprint arXiv:2301.00270 2022.
Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
Jundong Li, Kewei Cheng, Suhang Wang, Fred Morstatter, Robert P Trevvino, Jiliang Tang, and Huan Liu. Feature selection: A data perspective. ACM computing surveys 506): 2017
2017.
10

---

Published as a conference paper at ICLR 2024
Mingjie Li, Xiaojun Guo, Yifei Wang, Yisen Wang, and Zhouchen Lin. Ge Graph gaussian convolution networks with concentrated graph filters. In Interattonaal Conference on Machine Learning. pp. 12782-12796. PMLR, 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser- Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, 2021.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE transactions on pattern analysis and machine intelligence, 44(12)10270-10276 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35: 15:1132-1375, 2022.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification: In- vestigating the homophily principle node distinguishability arXiv preprint 2rX1::230411227 2023.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? International Conference on Learning Representations, 2021.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? arXiv preprint arXiv:2306.01323, 2023.
Octavio César Mesner and Cosma Rohilla Shalizi. Conditional mutual information estimation for mixed, discrete and continuous data. IEEE Transactions on Information Theory, 67(1):464-484 2020.
Jan Mielniczuk and Pawel Teisseyre. Stopping rules for mutual information-based feature selection. Neurocomputing, 158:255-274 2019.
Jan Motl and Oliver Schulte. The etu prague relational learning repository, 2015.
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-labeled reviews and ine-grained aspects. In Proceedings of the 2019 conference empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-UCNLP)), pp. 188-197, 2019.
Liam Paninski. Estimation of entropy and mutual information. Neural computation, 15(6):1191- 1253, 2003.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 2.0Xiv:0002.05287, 2020.
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and I. Liudmila Prokhorenkova. Characterizing graph datasets for node classification: Beyond homophily--heterophily dichotomy. arXiv preprint vrXiv:2209.06177 2022.
Brian C Ross. Mutual information between discrete and continuous data sets. PloS one, 9(2): e87357, 2014.
Ryan Rossi and Nesreen Ahmed. The network data repository with interactive graph analyties and visualization. In AAAI Conference on Artificial Intelligence, volume 29, pp. 4293-4293, New York, NY, USA, 2015.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scien- fific conference and international workshop present day trends of innovations, volume 2012.
11

---

Published as a conference paper at ICLR 2024
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liô, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. Advances in Neural Information Processing Systems, 34: 5758-5761 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference machine learning, pp- 6861-6871. PMLR, 2019.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints, In International Conference Learning Represen- tations, 2020.
Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and system co-design for efficient subgraph-bass graph representation learning. Proceedings of the VLDB Endowment, 15(1
2022.
Jaemin Yoo, Meng-Chiee Chich Lee, Shubhranshu Shekhar, and Christos Faloutsos. Less is more: Slimg for accurate, robust, and interpretable graph mining. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2023.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. Advances in neural information processing systems, 31, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9073, 2021.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference Learning Representations, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX: PROOFS
A.1 PROOF OF THM.
Proof. Let Y be a discrete random variable with n outcomes (y1,..,,un) and with probabilities
(p1,.... Pa), where:
1= Pi +... + Pv.
Let Pmax be the highest probability (break ties arbitrarily), that is:
Pmaz max p;
(10)
For ease of presentation, and without loss of generality, assume that the most likely outcome the first one, 1/1 and thus Pmnar P1- Given no other information, the best classifier for Y is the one that always guesses outcome y1, and it has accuracy:
accuracy(Y)) p1 Pmaz
(11)
The entropy H(Y is:
H(Y) (pi log Pl +... + Pr log
(12)
Thus we have:
2- 110)
pr PL p2 P2 Pr Pn
(13)
< Pmaz
P1 Pmax" 12 * Pmaor 11 Pman Pi
(14)
S Pmaz +
(15)
S Pmaz
(16)
which completes the proof.
A.2 PROOF OF THM.
Proof. Let and X be two discrete random variables with outcomes (yn,..., yo) and m outcomes (C,,...,Tmll respectively, then their joint probabilities are ,.,,1...,,,p,,))) where:
= P1 + ..... + Pm
Σ 1=1
Pis +... +
Pm.
(17)
The accuracy is:
m
accuracy(Y[X) Σ max Pr.j
(18)
The conditional entropy H(Y[X) is:
H(YI)) p1
P1.j
log2 pl
P1.j + ... Pm
Pmo
logg
Pm..j
(19)
P1
Pm
Pm
Thus we have:
n
n
-((((X)= =
Pl.j
logz
P1.j ) + + Pm *
Pm..i
logg
Pmn.i pm
(20)
Pm
j=1
j=1
Pi.j )2) +
Pin. )2) 11 Jensen's Inequality
< Pi * log
Pm * loga
p1
Pm
/=1
==1
(21)
Spi * loga (p) 2
Σ
pi. 2) +... ...... + Pm * logg (pm²
Σ Pin.s)
(22)
1=1
3=1
S Pı log, (0i max p1.;) + ... + Pm log, (pml max Pmn.))
(23)
3
13

---

Published as a conference paper at ICLR 2024
This is because vi = 1,,.. ,
Pi.j Pt,1 * Pt.1 +... Pi,n Pi
(24)
/=1
S Pr, * max Pi,j +... + Pin max Pi.j
(25)
(pi. .... pi,n) max
(26)
Pi max
(27)
To continue, we have:
= 2- H(Ix)) s 201-1oR2 (PT) (pp''mmm emax; pi tm -lo (Pm. smax, pmns)
(28)
S (pi" max (1.)) *... * (Pml max pmm.) Pm
(29)
Mm. Pm. 11 Weighted AM-GM Inequality < max P1, + + max
(30)
= accuracy(Y|x))
(31)
which completes the proof.
A.3 PROOF OF LEMMA 1
Proof. The goal is to maximize the similarity of nodes connected by edges. If we start from cosine
similarity and L2- 12-nomaalize the node embeddings z, we have:
Hz.
1, (i,,)) E
kz ||,
(32)
2, Hzj = |
-2, H = 2j
Setting 2, the input data and 2j the target data, this equation be solved by d-target linear regression with d coefficients, which has the closed-form solution.
A.4 PROOF OF LEMMA 2
Proof. First, we rewrite the adjusted node similarity s from matrix form into simple computation:
s(2;, Zj, H) 2, Hz!
H1,1
Hi,d
[2,,1
Zi.al
Ha,1
Ha.d
3j,a]
(33)
24,14,,1
Zi,1
H1,1
H1.d
Zi,dZj,1
Ha
Ha.
2,, H1,1 + Z,, H1 +
H1,
+ 2;,1 Hi. + .....4 + Zi Had
Next, maximize the similarity of nodes connected by positive edges, and to minimize the similar- ity of nodes connected by negative edges, we have:
{
(1,j) E
s( Zj H
(34)
(i,j) E Ereg
Therefore, this equation can be solved by linear regression with dl coefficients, which has the closed- form solution.
14

---

Published as a conference paper at ICLR 2024
A.5 PROOF OF LEMMA 3
Proof. NETINFOF includes four parts: SVD, PCA, compatibility matrix estimation, and LogitReg. The time complexity of truncated SVD is VI), and the one of PCA f Compatibility matrix estimation optimized by Ridge regression with regularized least-squares routine, whose time complexity is d []. The time complexity of training LogitReg is dt|E), where is the number of epochs. In our experiments, t is no greater than 100, and V is much less than [|] in most datasets. By combining all the terms and keeping only the dominant ones, we have time complexity of NETINFOF for link prediction 0( + + + d El).
B APPENDIX: ALGORITTMM
Algorithm 1: Compatibility Matrix with Negative Edges
Input: Preprocessed node embedding 2, edge set E, and sample size S Extract 2-core edge set Epos from E;
2 Estimate H with Ž and Epos by Lemma 1;
if |Eposl > S then
L Sample S edges from Epos:
Initialize H" with H;
Keep top coefficients in upper triangle of H" with 95% energy;
7 Sample 2 Eypss negative edges as Enegi
Estimate H' with Z, Epos and Eneg by Lemma 2;
Return H*:
Algorithm 2: NETINFOF _PROBEEEBBBBBBB for Link Prediction
Input: Node embedding Z, train edge Etraéns valid edge Evalid, valid edge labels y yealids sample size S, and bin size k
Preprocess Z into Z by column- wwse standardization and row-wise L2- normalizaaiin;
H
Compatibility-Martee harpiii--MMariiiwit--eeeaaaaeee with-Negative- 2, Etrain,S)
if Eposl > S then
Sample S edges from Eposi
else
L Epos E;;
7 Sample 2 Epo negative edges as Enegi
8 Fit k-bins discretizer with é, H' 2J. V(i,)) E Epas UEngii
E Evalid into bins as Spatidi 10 Return NETINFOF SCORE, computed with Spalid and Yvalid by Eq. 2;
9 Discretize 2, H (ii.j)
Algorithm 3: NETINFOF_ for Node Classification
Input:
Train, valid, and test node embedding Zerain Zvolid. and Zeests train and valid node labels Ytrain and Yoolid, and cluster number k
Preprocess Z into Z row-wise L2- n--oommalization:
2 Fit clustering model with Ziesti
Assign cluster labels Strain and Swatid Zerain and Zratid, respectively;
Return NETINFOF SCCRRE, computed with Strain Spalid and Ytrain U Yvalid by Eq. 2;
15

---

Published as a conference paper at ICLR 2024
C APPENDIX: EXPERIMENTS
C.I LINK PREDICTION IN SYNTHETIC DATASETS
To study the information of the derived node embeddings, we conduct NETINFOF PRObe on cach component, and LogitReg have performance link prediction. In Table 6, the components with the top-2 NETINFOF_SCOOM SCORE as well have the top-2 test performance in every scenario.
Table 6: Results of each derived node embeddings. NETINFOF ScoRE and test Hits@ 100 on link prediction are reported. Red highlights the results close to random guessing.
Metric
Feature Component
Random Diagonal
Random
Global Diagonal
Global
Local X
Local X
75.21088
76.5-09
NETINFoF.
C3:
50:00:00
67.0:0.5
71.52006
75911:1
73.51:06
.P
75.1=007
73:2-0066
78:220.7
78.5205
78.51:.2
78.9103
CS :.5
74.3-1.1
72.0-0.5
78.7=1.1 1.01
79.2-11.5
790++0.9
$1.1+066
C1:
83.3-1.2
764-2.11
83.5+1.2
267-00.5
83.2+1.1
78.2+09
C2: f
83.0_115
74.71144
83.0.1.3
75.0.1.5
8322110
73.310.7
Test Hissor 100
CB: F
02 02.2=002
02.5=0022
52.3e1.9
63.0 63.0+22.2
80.7+111
77.1110
C4: P
82.3-12
73:4:044
8622:1111
7..3:0077
85.751.5
79.45:13
C5
80.7-0.9
68.121.8
86440.9
79.211.1
$6.11.0
85.2111
C.2 LINK PREDICTION IN WORLD DATASETS
To study the effectiveness of each derived node embedding, we conduct experiments on each in- dividual component for the real-world datasets. As shown Table different components have variable impact depending on the input graph.
Table 7: Ablation study NETINFOF each component of derived node embedding. Hits @ 100 reported for most datasets, and @its@ 1 1000 for the large datasets (Products, Twitch, and Pokec).
CiteSeer
PabMed
Comp.
Squirrel
Twitch
C1:C
G
48.310.8
369.25
43.741.8
24.0-13
38.512.6
18.1:0.6
13.210.3
75.015..2
1233118
23.24:2.2
158110.2
16.2::06
C2:R
61.51122
10.0199
47.910.88
194_08
36.813.3
12.3_10
09:110.7
61.613.2
08:1114
34.2.1.3
01.510.2
05.2100.2
C3:55
F
58.3+3.2
715=24
416600
07.1204
15.6112
049-002
00.400.1
10.7&1.0
006:40.1
02.620.5
013+00
00520.2
C1:P
67.31188
609-2.
48.1118
28.6-14
42.41144
342-1
27.610.5
84.3118
20.92.3
13.111.1
073110
12.420.8
82.4110
88.115
63.311.1
192.12
22.31099
02.118
16.210.6
C.3 SENSITIVITY ANALYSIS OF NETINFOF PROBE LINK PREDICTION
We conduct a sensitivity analysis on a medium size dataset "Computers", study the effect of the number of bins & in NETINFOF PROBE (Algo. 2). As shown in Table 8 and Fig. 7, NET- INFOF_SCORE is insensitive to exact value of k; forming a plateau when increases.
NetinfoF Score
Table 8: Sensitivity analysis of NETINFOF PROBE in link prediction. NETINFOF SCORE reported.
00.75
0.70
Number
U 74.240.3
79.71-0.2
80.420.3
8088:0.3
81.0+0..
0.6
C2 R
76.5+0.2
80.410.0
81.2.0.3
81.420.3
81.5410.
2
63.841..1
64.94022
65.0=0.1
65.0-0011
65.1460.1
Number Bins
04 P
77.340.2
82.110.11
83.020.3
83.3-2033
83.410.3
C5:
77.3400.1
82.5+0.1
83.340.1
83.6-0.2
83.7400.
Figure 7: Sensitivity analysis CECTINOFFPPROHS is insensitive to the number of bins k.
16

---

Published as a conference paper at ICLR 2024
C.4 COMPARISON WITH SUBGRAPH GNN IN REAL- HEAL-WORLD DATASETS
Although the comparison with subgraph GNN is beyond the scope of this paper, the experimental results of a subgraph GNN, SEAL (Zhang & Chen, 2018), are provided in Table 9 for the interested readers. The hidden size is set to 128 as the same as other baselines, and the hyperparameter search is done on the number of hops (11, 3)), learning rate (00.001, 0.01]). weight decay ((0, 5e="), and the number layers ([2, 3). Other hyperparameters are set as the default ones in Zhang et al. (2021).
To emphasize again, shown in Table 1, subgraph GNNs are beyond the scope of this paper, because: (1) they are not designed as general GNNs and can only solve link prediction; (2) they are only scalable small graphs. To give concrete example, using AWS EC2 G4dn instance with 384GB RAM and running on the largest dataset Photo without running out of memory (O.O.M.) in the preprocessing step, SEAL takes 17606 seconds (around 4.9 hours) to train single split of data, while NETINFOF takes only 52 seconds, which is x faster than SEAL.
Table 9: Comparison with SEAL. Hits 100 is reported for most datasets, and Hits @ 1000 for the large datasets (Products, Twitch, and Pokec).
Model
Cora
CiteSeer
PubMed
Comp.
Photo
ArXiv
Products
Cham.
Squirrel
Actor
Twitch
Pokec
SEAL
6.
61.11.
628117
O.O.M.
58.5 1.0
O.O.M.
O.O.M.
19.410
O.D.M.
43.6.0.7
O.O.M.
O.O.M.
NEtiNooF
81.3-06
87,3&13
397211
311#19
46.-11
39.2&18
35.2=111
86.923
24.2-20
36.2+112
19.6:0.7
31.3:005
C.5 NODE CLASSIFICATION IN SYNTHETIC DATASETS
We keep the same settings of sanity checks in SLIMG, but our graph generation process in Appx. D.I. To study the information of the derived node embeddings, we conduct NET- INFOF PROBE each component, and LogitReg to have test performance on node classification. In Table 11, the component with the highest NETINFOF SCORE as well has the highest test accuracy in every scenario. In Table 10, NETINFOF generalizes all scenarios SLIMG does.
Table 10: NETINFOF works well on node classification in synthetic datasets. Accuracy is reported.
Model
Useful X
Random X
Random X
Useful X
Useful X
Uniform A
Homophily
Heterophily
Homophily A
Heterophily A
SLIMG
85,4+2.3
88.9=2044
874=25
97.3+0022
97.0=0.1
NETINFOF
86.711.5
88.6.1..5
87
97.110.1
97.0.0.2
Table 11: Results of each derived node embeddings. NETINFOF and test accuracy on node classification are reported. Red highlights the results close random guessing.
Metric
Feature Component
Uniform
Useful X
Homophily
Random X
Random X Heterophily
Homophily
Useeful X
Heterophily
Useful X
74.4:399
73.62:26
C2 R
25.7.0.1
62.51.3.5
1..7
61.72377
56,3-333
NertrpoF_Score
C3: F
64.614.2
26.0.10.1
26.010..1
13.12:32
73.1-:32
C4: P
33.7::155
56.011-.22
5891339
87.2:33
87.2-32
C
33.9208
58.744488
55,5133.5
86.1224
88.3-34
80.3209
8133008
C2: R
25.3.104
60.7.0.88
58.411.1
61.5009
58.8.13
Test Accuracy
C3: F
74.7..08
25.4.00.6
25.4100.6
74.71.11
74.7-111
C4: P
47
75.2+-0.9
774208
97.1:-0.1
966-0.1
47.9-0.9
75.8+1.0
74,1+0.8
96-9-0.1
969-0.1
C.6 NODE CLASSIFICATION IN REAL-WORLD DATASETS
We follow the same experimental settings in SLIMG. The nodes randomly split by the ratio 2.5% 995% into the training, validation and testing sets. In Table 12, we find that NETINFOF always wins and ties with the top baselines.
17

---

Published as a conference paper at ICLR 2024
Table 12: NETINFOF works well on node classification in real-world datasets. ported.
Accuracy re-
Model
Cora
CiteSeer
PubMed
Comp.
Photo
ArXiv
Products
Cham.
Squirrel
Actor
Twitch
Pokec
OCN
760-1.2
65.0++2.9
84.3-0.
85.1+0.9
91.6-0.5
6288+0.6
O.M.M.
38.5+30
31.4-188
26.8+04
57.+0.11
63.9+04
SAGE
7.661.
63.71336
82.10.41
83.8.0.5
90.6.0.5
61.510.5
O.O.M.
39.814,3
27.011.3
27.8.009
56.6.0.4
68.910.1
TPGCN
776-09
64.713.8
K5440.44
49,5116.
758-11.
0.O.M.
O.O.M.
3199:26
25.0:0..
28.9:006
58.710.0
O.O.M.
GPR-GNN
64.244.0
85.1+07
850++1
026-0.3
58.5088
31.7+4.7
26221.
29.5+11
57.6+0.2
676++01
65.814.0
354114
58.11.0
264104
O.M.M
SLIMG
77.=1.1
67.142.3
84.6.00.
86.3+0.7
91.8=03
663340.3
84.=000
40.8432
31.1=0.7
30.9:0.6
59.7#0.1
73.9+0.1
NETINFOP
7.5_13
61.513.6
84.10033
86.6.0.66
91.6.003
66.8.0.77
85.3.0.0
41.6132
30.11.
30,71003
61.010.2
74.0.0.1
D APPENDIX: REPRODUCIBILITY
D.1 SYNTHETIC DATASETS
The synthetic datasets are composed of two parts, namely, graph structure and node features. Noting that link prediction and node classification share the same generator of graph structure, but differ in the one of node features. Noises are randomly injected into both graph structure and node features to ensure that they contain consistent usable information across different scenarios. The number of nodes is set to be 4000, and the number of features is set to be 800.
Graph Structure. There are three kinds of graph structures, namely, diagonal, off-diagonal, and uniform. For each graph, we equally assign labels with classes to all nodes. In the diagonal structure, the nodes are connected to the nodes with the same class label, which exhibits homophily. In the off-diagonal structure, the nodes are connected to the nodes with different class label, which exhibits heterophily. nodes. Other than randomly picking node pairs to make connections, that the nodes are connected by higher-order structure in the real-world (Eswaran et al., 2020). To achieve that, in the diagonal structure, random amount of nodes (between 4 and 8) with the same class are randomly picked and made into a clique; In the off-diagonal structure, a random amount of nodes (between 4 and 8) from each of the two classes randomly picked and made into a bipartite clique. This process continues until the graph reaches our desired density. In the link prediction, the assigned node labels are not used; in the node classification, they are used the target labels.
the uniform structure, the connections are randomly made between mimic the phenomenon
Node Features in Link Prediction. In the case that the node features are useful, they are generated by the left singular vectors of the 2-step random walk matrix. The (i, element of the matrix the counting of the node on row visited the node on column j. and each node walks for 1000 trials. The node features are directly used in the global scenarios, but split into different slices based on the labels in the local scenarios. The random node features are the rows in random binary matrix.
Node Features Node Classification. the case that the node features are useful, we randomly sample center for each class label. For nodes with the same class, we add Gaussian noises on top of their class center. The random node features are the rows in a random binary matrix.
D.2 REAL-WORLD DATASETS
In the experiments, we use 7 homophily and 5 heterophily real-world datasets that have been widely used before. All the graphs are made undirected and their statisties are reported Table 13. We also conduct experiments on 3 link prediction datasets from Open Graph Benchmark (OGB) (Hu et al., 2020), namely ogbl-ddi', ogbl-collab', and ogbl-ppa².
Homophily Graphs. Cora (Motl & Schulte, 2015)², CiteSeer (Rossi & Ahmed, 2015 and PubMed (Courtesy of the US National Library Medicine, 1996) are citation networks between
" "hutps//ogbb.tanfood..ee http:///www.oo/iiio///////ohooo.
hhtps://ogb.stanfor.. http:://wo...aaaooooo.d/d//llllp www.ddoes//iinknppo///ggggppppp
'ntts://relational ft..oaa..z/daaase///COOAA
/hups://wwww. www.miiiiiti...
www.:w/www....gg.oaaaooooooooooa html
18

---

Published as a conference paper at ICLR 2024
research articles. Computers and Photo (Ni et al., 2019)² are Amazon co- co-purchasing networks be- tween products. ogbn-arXiv and igbn-Products are large graphs from OGB (Hu et al., 2020). ogbn- arXiv is citation network of papers from arXiv; and ogbn- Products is also Amazon product co-purchasing network. In the node classification task, we omit the classes with instances fewer than 100 that each class has enough training data.
Heterophily Graphs. Chameleon and Squirrel (Rozemberczki et al., 2021) 10 are Wikipedia page- to-page networks between articles from Wikipedia. Actor (Pei et al., 2020 is co-occurrence network of actors on Wikipedia pages. Twitch (Rozemberczki et al., 2021) 2 and Pokec (Takac & Zabovsky, 2012; Leskovec & Krevi, 2014)| are online social networks, which are relabeled by Lim et al. (2021)* to present heterophily. Penn94 is not included in this paper because of legal issues.
Table 13: Network Statistics. The left and right parts are homophily and heterophily, respectively.
Cora
CituSeer
PubMed
Computers
Photo
eghn-arXiv
oghn-Proddccts
Chamcloon
Squirrel
Actor
Twitch
Pokre
of Nodes
2,508
3,327
19:717
13,75)
7,850
169,343
2,449,229 61,859, 140
2.277
5,20)
7,600
1,632,003
Edges
5.499
4.752
44.338
245.86 861
119.081
1,166,243
36.101
216.933
29.926
6,997.557
30,622.644
Frontrex
5703
745
128
100
2089
931
of Classes
3
10
40
39
5
2
D.3 EXPERIMENTAL SETTINGS
For fair comparison, each experiment run with different splits of both synthetic and real- world datasets. In link prediction, edges are split into training, validation and testing sets with the 70%/109 10% 0066//0% 20% ratio. In node classification, the nodes are split into training, validation and testing sets with the 2.5%/ 2.5%% 55/95% ratio. For small graphs, the linear models trained by L-BEGS for 100 epochs with the patience of 5, and the non-linear models are trained by ADAM for 1000 epochs with the patience of 200. For large graphs (Products, Twitch, and Pokec), most models are trained by ADAM for 100 epochs with the patience of 10, except GPR-GNN and GAT, they are trained by ADAM for 20 epochs with the patience of speedup. All the training are full-batch, and the same amount of negative edges are randomly sampled for each batch while training.
D.4 HYPERPARAMETERS
The search space the hyperparameters is pro- vided in Table 14. Each experiment is run with different splits of the dataset, and grid search of hyperparameters based on the validation per- formance is done on each of the splits. The hid- den size of all methods is set 128.
Table 14: Search space of hyperparameters.
Method
Hsperparamciers
GCN
0.001 0.01)
1e
Jayers -
SAGE
0.001 0.61.
0.
Japera -
HGOON
6r
0.001 0.00
0.5c
Japers [1:]]
GPR GNN
0.001 0.00
add 0.5e
deperss Japers 18. a 021.022,0500
OAT
(0.001 0.01
axt 0.5-
Jugera hende
Linear GNNs. For sparse-group LASSO, wd1 the coefficient of overall sparsity, and wdz is the one of group sparsity. The derived embed- ding R in NETINFOF uses T = 1000 for the synthetic and OGB datasets, and T = 200 for the real-world datasets. The sample size S is set to be 200, 000 in all experiments. Since the large graphs (Products, Twitch, and Pokec) have no more than 128 features, to ensure NETINFOF and SLIMG have enough parameters,
StEMG
Gr vod,
De
".1e"),nd, -(e Ie
Nerhsoo
ir - sod
"e."" (1em) 10 1o-1.10 J6
concatenate the one-hot node degree to the original features. The hidden size is set to 256 for NETINFOF and SLIMG in the OGB experiments. For ogbl-ddi, since there is node features, they use the one-hot node degree as the node features. For ogbl-ppa. we concatenate the embedding from node2vec (Grover & Leskovee, 2016) to the original features, as Hamilton et al. (2017) did for GCN and SAGE.
hhttss//nijiaamoo.iinn wo/amazoo//ndex....../// html
"bups://ogh.staafoodddeue http:///.....nooodddeddd///o/nno http////ss////ddpoo/////oaaaaaaa
10
data/film
12 http:////l...ooooooocccccceueeas hete netwoks
"https///snap.stafford
htt./ddttaassc-ooocccchlltll Pokec.html
14
thaps://gthuh..om///
Haapa//lacccc///AAo/oooooooohaaa Homophily-Large-See
19


Reviews:
[{"review_id": "GtLnkH1PYa", "reviewer": "Reviewer_96be", "summary": "The paper presents a novel framework, NETINFOF, designed to quantify and leverage Network Usable Information (NUI) for graph tasks like link prediction and node classification. The approach tackles the need for extensive model training by using NETINFOF_PROBE to measure NUI directly from graph data, which is a significant improvement  from traditional GNNs that rely on trained low-dimensional representations. The NETINFOF_ACT component then uses this measured information to enhance the performance of graph tasks. The framework's robustness is tested on synthetic datasets designed to include various graph scenarios and validated on real-world datasets, showing superior results in link prediction tasks over standard GNN models. This paper's primary contribution is a method that can quickly assess a graph's usefulness for a task, offering a theoretical lower bound for accuracy without the computational overhead of model training​. The empirical study of this paper is very strong, surpassing most GNN methods both in accuracy and scalability.", "questions": "1. Can the authors provide a more detailed justification for Theorem 2, particularly in light of the concerns highlighted in the first weakness?  I will raise my score if the authors can give a reasonable update. \n2. How are the \"Our bound\" lines in Figures 3 and 4 derived? Additional details on this calculation would aid in understanding these figures.\n3. How NetInfoF_Probe estimates and calculates the discretizer in section 4.2? Maybe some examples or explanations will help reader understand this.\n4. An ablation study detailing the individual contributions of the five different node embedding components mentioned in Section 3.2 would be beneficial. Are these components equally influential in terms of accuracy, or do some weigh more significantly than others?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- **Methodological Innovation**: NetInfoF introduces a novel approach to measure NUI directly from the graph structure and node features, which is a different from traditional methods that rely heavily on model training. This innovation could have a broad impact, particularly in scenarios where computational efficiency is paramount​. Also, the adjustments of node similarity using compatibility matrix w/ negative edges is very interesting.\n- **Teoretical Foundation and Empirical Validation**: The paper provides a theoretical analysis for the NetInfoF_Score, presenting it as a lower bound for the accuracy of a GNN on a given task. This theoretical contribution is well-supported by empirical evidence on both synthetic datasets and real-life datasets.\n- **Scalability**: The demonstrated scalability of NetInfoF, especially its linear scaling with input size (Fig. 6), and the use of significantly fewer parameters compared to GAE methods (1280 vs 279k) demonstrates its potential for application in large-scale graph tasks, presenting a substantial advancement in the practical deployment of GNNs​. Though NetInfoF is slower than SlimG [1], NetInfoF has better accuracy. \n\nCombining 2nd and 3rd points, NetInfoF is better than GAE methods both in accuracy and scalability empirically, which is a significant contribution in link prediction tasks.\n\n\n\n\n\n\n[1] Yoo, Jaemin, Meng-Chieh Lee, Shubhranshu Shekhar, and Christos Faloutsos. \"Slendergnn: Accurate, robust, and interpretable gnn, and the reasons for its success.\" arXiv preprint arXiv:2210.04081 (2022).", "weaknesses": "1. The proof of Theorem 2 is problematic due to the incorrect use of conditional entropy. The proof incorrectly states the conditional entropy in Appendix A.2 as:\n$$\nH(Y|X) = \\sum_{i=1}^{m} p_i \\left(-\\sum_{j=1}^{n} p_{ij} \\log_2 p_{ij}\\right),\n$$\nwhich is incorrect because it uses the joint probabilities $p_{ij}$ instead of the conditional probabilities. The correct expression for conditional entropy, which is based on the conditional probabilities, is:\n$$\nH(Y|X) = -\\sum_{i=1}^{m} \\sum_{j=1}^{n} p_{ij} \\log_2 P(Y=y_j|X=x_i),\n$$\nwhere $P(Y=y_j|X=x_i) = \\frac{p_{ij}}{p_i}$ is the conditional probability of $Y$ given $X=x_i$. And $p_i = \\sum_{j=1}^{n} p_{ij}$ represents the marginal probability of $X$ taking the value $x_i$. This definition adheres to the fundamental property that the conditional probabilities for a given $x_i$ should sum to 1, i.e., $\\sum_{j=1}^{n} P(Y=y_j|X=x_i) = 1$.\n\nThe misuse of conditional entropy in the proof leads to an erroneous application of Jensen's Inequality and subsequently invalidates the derived bound on the NetInfoF score.\n\n2. (Minor) Given the paper is mostly dealing with link prediction tasks. It will be beneficial to include some subgraph-based methods as baselines, such as SEAL [1]. I understand that NetInfoF is intended as an advancement beyond traditional GNN approaches, but including subgraph-based methods will give the community a more comprehensive evaluation of NetInfoF's capabilities. It's evident NetInfoF is way more scalable than subgraph-based methods, but subgraph-based methods are still SOTA on some datasets, e.g. Ogbl-collab.\n\n\n\n\n\n\n\n[1] Zhang, Muhan, and Yixin Chen. \"Link prediction based on graph neural networks.\" Advances in neural information processing systems 31 (2018).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0lNMc1z86T", "reviewer": "Reviewer_WXaL", "summary": "The paper proposes a framework called NETINFOF for measuring and exploiting network usable information (NUI) in node-attributed graphs. The authors aim to determine if a graph neural network (GNN) will perform well on a given task by assessing the information present in the graph structure and node features. NETINFOF consists of two components: NETINFOF PROBE, which measures NUI without model training, and NETINFOF ACT, which solves link prediction and node classification tasks. The framework offers several advantages, including generality, principled approach, effectiveness, and scalability. The authors demonstrate the superiority of NETINFOF in identifying NUI and its performance in real-world datasets compared to general GNN baselines.", "questions": "see weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces the novel NETINFOF framework, which addresses the problem of measuring and exploiting network usable information in graph for GNNs. \n2. The paper demonstrates sound technical claims, supported by theoretical guarantees and empirical evaluations on synthetic and real-world datasets.\n3. The writing style is clear, and the paper is well-organized, making it easy to understand the proposed framework and its contributions.\n4. The paper's contributions are promising as they provide a practical tool (NETINFOF) for assessing the usefulness of graph structure and node features in GNN tasks. The framework shows promising results and outperforms existing baselines in link prediction.", "weaknesses": "1. How does the NETINFOF framework handle noisy or incomplete graph data? Can it effectively measure and exploit network usable information in such scenarios?\n\n2. Are there specific types of graph structures or node features for which NETINFOF may not perform well? How robust is the framework in diverse graph settings?\n\n3. I have concerns regarding the sensitivity of NETINFOF to the estimated compatibility matrix (H) used in the framework. It would be beneficial if the authors could provide additional empirical results that examine the performance of NETINFOF under different label rates, as label rates can significantly impact the correctness of H.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YdYTw9FaqZ", "reviewer": "Reviewer_ANgE", "summary": "The paper discusses the NETINFOF framework, which focuses on measuring and utilizing the usable information in node-attributed graphs for graph tasks such as link prediction and node classification. The authors propose two components of the framework: NETINFOF PROBE, which measures the amount of information present in the graph structure and node features without any model training, and NETINFOF ACT, which uses the measured usable information to solve the graph tasks.", "questions": "1. \"How to connect the graph information with the performance metric on the task?\" Here are some missed related works [1,2,3,4,5].\n\n2. What is $f$ in C4? I suggest not using $f$, because you already use it as the number of features.\n\n3. In theorem 1, \"Given a discrete random variable Y , we have...\" What is \"accuracy(Y)\"? Accuracy of a a discrete random variable? This looks weird and I suggest giving a more strict and accurate statement. What is $p_y$?\n\n4. \"Predicting links by GNNs relies on measuring node similarity, which is incorrect if the neighbors have heterophily embeddings.\" The embedding will be similar even with heterophily connections if the nodes share similar neighborhood patterns [6].\n\n5. \"the node embeddings of linear GNNs require no model training“ I don't understand this. Why linear GNNs don't require training? Do you mean SGC [7] don't require training?\n\n6. \"It results in low value when node i and node j have heterophily embeddings, even if they are connected by an edge.\" This is not correct, see [2,3,6].\n\n\n\n[1] Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy. arXiv preprint arXiv:2209.06177.\n\n[2] Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35, 1362-1375.\n\n[3] When do graph neural networks help with node classification: Investigating the homophily principle on node distinguishability. arXiv preprint arXiv:2304.14274.\n\n[4] Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?. arXiv preprint arXiv:2306.01323.\n\n[5] Exploiting Neighbor Effect: Conv-Agnostic GNN Framework for Graphs With Heterophily. IEEE Transactions on Neural Networks and Learning Systems.\n\n[6] Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations 2022.\n\n[7] Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861–6871. PMLR, 2019.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Lots of experiments", "weaknesses": "See below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)