Lovász Principle for Unsupervised Graph Representation Learning
Authors: Ziheng Sun
Chris Ding
Jicong Fan
Venue: NeurIPS 2023 poster (2023)
Keywords: Lovász Number
graph-level representation learning
unsupervised learning
semi-supervised learning

Abstract: This paper focuses on graph-level representation learning that aims to represent graphs as vectors that can be directly utilized in downstream tasks such as graph classification. 
We propose a novel graph-level representation learning principle called Lovász principle, which is motivated by the Lovász number in graph theory. The Lovász number of a graph is a real number that is an upper bound for graph Shannon capacity and is strongly connected with various global characteristics of the graph. Specifically, we show that the handle vector for computing the Lovász number is potentially a suitable choice for graph representation, as it captures a graph's global properties, though a direct application of the handle vector is difficult and problematic. We propose to use neural networks to address the problems and hence provide the Lovász principle. Moreover, we propose an enhanced Lovász principle that is able to exploit the subgraph Lovász numbers directly and efficiently. The experiments demonstrate that our Lovász principles achieve competitive performance compared to the baselines in unsupervised and semi-supervised graph-level representation learning tasks. The code of our Lovász principles is publicly available on GitHub.

Lovász Principle for Unsupervised Graph Representation Learning
Ziheng Sun 1.2
Chris Ding'
Jicong Fan 1,2+
School of Data Science, The Chinese University of Hong Kong, Shenzhen, China Shennhen Research Institute of Big Data, Shenzhen, China zihengsun@l ink. cuhk. edu. en
{chrisding, fan iong)/n//uu edu.
Abstract
This paper focuses graph-level representation learning that aims to represent graphs as vectors that can be directly utilized in downstream tasks such as graph classification. We propose novel graph-level representation learning principle called Lovász principle, which is motivated by the Lovász number in graph theory. The Lovász number of a graph is real number that is an upper bound for graph Shannon capacity and is strongly connected with various global characteristics of the graph. Specifically, we show that the handle vector for computing the Lovász number is potentially a suitable choice for graph representation, as it captures graph's global properties, though direct application of the handle vector is difficult and problematic. We propose to use neural networks to address the problems and hence provide the Lovász principle. Moreover, we propose an enhanced Lovász principle that is able to exploit the subgraph Lovász numbers directly and efficiently. The experiments demonstrate that our Lovász principles achieve competitive performance compared to the baselines in unsupervised and semi-supervised graph-level representation learning tasks. The code of our Lovász principles is publicly available on GitHul
Introduction
Graphs, such as chemical compounds, protein structures, and social networks, are non-Euclidean data that represent the relationships between entities. There have been a large number of previous works studying many aspects of graphs, including mutagenicity prediction of chemical compounds (Debnath et al. [991] Kriege and Mutze! 2012), protein structure prediction [Borgwardt er al. 22005).
and community analysis of social networks Yanardag and Vishwanathan 2015].
Graph-based learning problems can be organized into two categories: node-level learning and graph- level learning. this paper, we will only focus on graph-level learning. It known that in graph-level learning, one fundamental task or step is measure the distance similarity between graphs. An important class of methods comparing graphs is graph kernel and many graph kernels have been proposed in the past decades (Siglidis et al. 2020]. For instance, random walk kernels |aärtner et al.) 2003) are the most widely-used and well-studied graph kernel family, which measure the graph similarity by counting the common random walks between graphs. The Weisfeiler-Lehme Weisfeiler and Leman [1968] family kernels are based on node label reassignment. Most graph kernels extract the similarity information between graphs by sampling sub-structures of graphs such as walks or reassigning the attributes of nodes with their neighhorhoods. Note that graph kernels are implicit graph representation methods and hence their flexibilities not high. In addition, the time and space complexities are quadratic with the number of graphs.
Corresponning author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Graph representation learning aims to convert data with graph structure into vector representations that can be applied to various downstream tasks, such as graph clustering and classification. Many studies have been conducted on graph-level representation learning, and some of them use neural message- passing algorithms [Kipf ef 2018 Xie and Grossman, 2018: Gilmer el al. 2017]. For instance, the InfoGraph proposed by [Sun et al. 2019] achieves graph-level representations by maximizing the mutual information between the graph-level representation and the node-level representations. Graph contrastive learning (GraphCL) (You et al.) 2020] and adversarial graph contrastive learning (AD-GCL) (Suresh et at.) [02T] obtain graph-level representations by training graph neural networks (GNNs) to maximize the correspondence between the same graph 's representations in its various augmented forms. JOint Augmentation Optimization (JOAO) (You et al. [021] is a framework that automatically and adaptively selects data augmentations for GraphCL specific graph data, using unified bi-level min-max optimization approach. Automated Graph Contrastive Learning (AutoGCI)) Yin et al. 2022 uses learnable graph view generators and auto-augmentation strategy generate contrastive samples while preserving the most representative structures of the original graph. These graph-level representation learning methods are all based the InfoMax principle [Linsker] [988].
Note that there are many other graph representation learning methods such as VGAE Kipp and
Welling. 2016; Hamilton et al.) [017 Cui et al.) 2020], graph embedding [Wu et al. [2020] Yu et al.
2021 Bai et al. 2019; Verma and Zhang 2019). sell-supervised learning [Liu et al. [2022]Hoo Hou et al.
2022; Lee et al.
2022] Xie er al. 2022, Wu et al. 2021, Rong et al., [2220] Zhang et al.) [2021b a
Xiao ef al. [2022]
and contrastive learning Le-Khac et al. [2020] Qiu et al. 20200; Ding et al. 20022
Xia et al. 2022
Fang et al.) 2022
Trivedi et al. [2022] Han et |l.] 2022 Mo er al [222]] Yin et al.
2022, Xu et al. 2021: Zhha et al.
2021 Zeng and Xie [021 Li el al. 2022a by Wei et al. 2022]
which will not be detailed in this paper due to the page length limit.
The InfoMax principle (Linsker 1988). which is very popular in graph-level representation learning. advocates maximizing the mutual information between the representations of entire graphs and the representations of substructures of varying sizes [Peng et al.) 2020; Velickovic et al. 2019 Hassani
and Khasahmadi 2020; Xie et al. 2022] Qiu el al. 2020). J. These InfoMax-based methods usually
evaluate the mutual information (MI) between different representations using Jensen- Monsen-Shannon MI
estimator (Sun er al. 2019]. following the formulations of f-GAN (Nowozin et al.) 2016] and Mutual Information Neural Estimation (MINE) [Belghazi et al. 2018). However, the Jensen-Shannon MI estimator necessitates the training of a neural network parameterized discriminator, which is overly complex. In addition, the estimator is based on sampling, which may not be accurate enough in exploiting the mutual information. As opposed to InfoMax, researchers proposed the graph information bottleneck (GIB) [Wu et al.) (020) and the subgraph information bottleneck (SIB) Yuu et al. [222]] that aim to learn the minimal sufficient representation for downstream tasks. But GIB [Wu et al. 2020] and SIB (Yu et al. 2021 may fail if the downstream tasks are not available in the representation learning stage.
In this work, we introduce novel graph learning principle called Lovász principle, which is inspired by the Lovász number [Lovász] 1979] in graph theory. The Lovász number is an upper bound for a graph's 's Shannon capacity. It is closely associated with various global characteristics of a graph, such as the clique number and chromatic number of the complement graph. The handle vector for calculating the Lovász number is potentially suitable choice for the graph-level representation, as it captures graph's 's global features, though suffers from few difficulties. The contributions of this work are summarized as follows.
We propose the Lovász principle, a novel framework for unsupervised graph representation learning. We show how effectively and efficiently utilize the handle vectors represent graphs. The Lovász principle exploits the topological structures of graphs globally via neural networks.
We propose enhanced Lovász principle via effectively incorporating subgraph Lovász numbers, while direct computation of subgraph Lovász numbers is extremely costly. The enhanced Lovász principle ensures similar graphs have similar representations.
We extend the Lovász principles to semi-supervised representation learning. Note that it is possible to adapt the Lovász principles to more graph-based learning problems.
The experimental results of unsupervised learning, supi-supe learning, and transfer learning on many benchmark graph datasets show that the proposed I Lovász principles outperform graph kernels, classical graph embedding methods, and InfoMax principle based representation learning methods.
2

---

2 Notations and Preliminaries
In this work, we v., æ:, X, X' (or X) to denote scalar, vector, matrix, and set respectively. laxb is matrix of size a x b consisting only ones. I, denotes an identity matrix of size n X n. Let G = (V, F) be a graph with n nodes and a-dimensional node features {æe R l E V}. We denote
as the adjacency matrix and X [x1, _n] E R=*a as the node features matrix. Let R be the d-dimensional graph-level representation of G, h E IRd be the d-dimensional node-level representation of node v, and H = [.., h.,] E Raxd be the node-level representations matrix of G. We denote (p, q) as edge between nodes p, and (p,g) E' if they are connected.
Let G IG......G 3 be a dataset of N graphs with K classes, where G; E.). For G., we denote its number of nodes as ni, graph-level representation as Z;, the adjacency matrix as A, the node feature matrix as X;, and node-level representation matrix H,. The graph-level representation matrix of dataset G is denoted as Z = [zi..... ZN] IR Nxd representations is denoted as {H...... H
The set of all node-level
2.1 Lovász number
The definition of Lovász number [Lváász]
1979 is based on orthonormal representations a graph. Therefore we first introduce the definition of orthonormal representations.
Definition 2.1 (Orthonormal representations). Given a graph G = (V. with [ = n. Let
T Ut 0, v(p, & E). U := IU E RRdx ||tupl22 1, 1,2, up
(1)
where up the p-th column of U. Then every E 24 is an orthonormal representation of in Rd.
Clearly, every graph has at least one orthonormal representation. For example, a trivial representation is that each node p is represented by the standard basis vector en- Based Definition 2. introduce the Lovász number [ováász 1979| of a graph as follows.
Definition 2.2 (Lovász number). The Lovász number of graph G (V, E) is defined
((G) = min max c,UEu PEV (c up)
where c Rd ranges over all unit vectors. The vector e yielding the minimum for (2. denoted by c², is called the handle of the representation, where the corresponding U is denoted as U for convenience. U called the optimal representation of G in Rd
László Lovász provided a pentagon example, shown in Figure I to explain Lovász number defined by (2). The visualization of U* and c* of a pentagon is like umbrella whose handle is cº and the ribs are the five columns of U These five disjoint node pairs, i.e. (ui, uz), (ui, ux), (uz u (uī, uz),, (ug, ug), are orthogonal to each other in visualization.
The Lovász number O(G') is upper bound on the Shannon capacity of a graph G and is polynomial-time computable GGötschell et al. 198T, Galli and Letchford 2017] (e.g., using semidefinite programming (SDP). Let G be the complement of G with its clique number (G) and chromatic number XG). The Lovász "sand- wich theorem" shows that the Lovász number is bounded between the clique number and the chromatic number of G i.e., (G) S ((G)= < XG).. Although computing (G) and X() are
u1
L13
ugo
ug
ug
U3
U2
Figure 1: Pentagon example for Lovász number
both NP-hard, the "sandwich theorem" allows us to estimate the clique number and the chromatic number of G using only (G). More detailed discussion can be found in Knuth 1993..
2.2 Lovász theta kernel
Johansson et al. (2014) defined the Lovász theta kernel to evaluate the similarity between graphs. Suppose S C V is subset of the vertices of graph G, then the Lovász number of the subgraph
3

---

induced by S is defined as
1
(s(G)= == min max PES (c' up)
where U was pre-computed by Eq. 2 and ranges over all unit vectors.
Definition 2.3 (Lovász-O) kernel [Jhhansoon et al. 2014). ). Let be a base kernel. The Lovász theta kernel between graphs G (V, E) and G' (V. E') is defined as
((1) ((ss(G),ss((G))
G',
E Σ SCV s'gV
(4)
Cs.s
where Cs.s'
(15) 5y 8(S)) (()) if |S| = |S and 8([)). ( otherwise.
Lo is a positive semi-definite kernel [Johansson et al. 2014]. It is able to capture global properties of graphs and has been shown useful in SVM-based graph classification [Johansson et al. 2014
3 Lovász Principle for Graph Representation Learning
The Lovász number O(G) of a graph G' provides insight into the global property of the graph. It a unique and deterministic value associated with an orthonormal representation U and a unit handle vector c*. The umbrella example in Figure I exxlains how to compute the Lovász number: compacting the ribs (i.e. U*) as much as possible and using c* as the handle. This example provides intuition that the handle vector c² is natural and suitable representation of the graph G.
Given G 1G1, G2, ... Gx) drawn from an unknown distribution De, we want to represent each graph as a vector such that these vectors preserve some important information of Da. Suppose we have an algorithm A such that
i= 11 N,
(5)
where A is some solver for 2 is natural to use ci, ci....... cjy as representations of G1, G2,.... .,, GN respectively. However, this method has the following limitation
i. Non-uniqueness For any G,, both U and cx are not unique. For example, let Q E Rdxd be an orthonormal matrix, i.e., Q Q QQ = Id, and let cf Qct and U QU; We have ||''l22 1, (U") = (U;) U and (c') (c')Tus = ((G)). This means (c) U and (c', U') yield the same Lovász number for G,, though they could be very different. Thus. for two graphs G, and Gj in G. even when they are isomorphic, of and ej could be very different. However, for graph representation, we hope that similar graphs have similar representations. For two graphs G, and G,. one may align their orthonormal representations using Q = argmin Q=1a = U0. - QUí [ and compare them according to ||c/ - -c3 2122 This however only works when the n; ny and G; and G, are matched.
ii High computational cost For each G; in G, we need to solve the optimization problem ( for which the time complexity of SDP is at least O (2(255))) [Jiang el al. 2020 Thus the total time complexity for G is O 1=1 E (n?)).) Therefore, this representation method is not scalable to large datasets.
iii. Ignorance of node features The computation of (5) solely relies on the graph structure and does not take advantage of the node feature matrix X; that is often available and informative.
iv. Non-generalization Suppose we have some new graphs and want obtain their representa- tions. We cannot utilize the representations of G and we have to solve 2 again for each new graph.
Non-global sensing The computation of (5) treats each graph separately and cannot effec- tively take advantage of the global information or structure of G. Individual graphs may have noise or outliers, which cannot be handled by local method.
'In our experiments (Table 1 this naive method, termed LovászNum, is tested. In addition, the Lovász-1 kernel introduced in Section 2.2 is also tested.

---

To solve the aforementioned five issues, we present a machine learning method. We use neural network Fw (parameterized by W) to approximate A. Fw can be learned from G as well as some additional information such as the node feature matrices {X (X..... XN). Specifically, we hope that
(U c.) ~ Fw X:), = 1,2,....
(6)
Thus, Fw plays a role representing a graph (drawn from DG) to a matrix of nodes representation and vector of graph representation. For new graphs sampled from Dc. Fw should generalize well when the approximation errors in (6) are small enough and Fw is not too complex. For convenience, we split Fw into two parts, i.e., Fw(s))
(F(s 0), f(. =o)), though F and can share some parameters. We let U x F(A,, X;; 0) and c ~ (A,, X 0). F)) is the model of node-level representation learning while ((, +: Φ) is the model of graph-level representation learning. We let
H FAA, 0); and _ = f(A,, X; Ø),
Vi = 1,2.....
We denote the graph-level representations matrix as Z - | ... N and the node-level represen- tations set as Ho = [ H }- To achieve (6) we propose to solve
minimize 0,0
Σ
max PEV. ((2)) Th))
1
tp
M O H ( I.. I1 ((x)) 2, -1)
(8)
where M,- Xn, A, is mask matrix and y > 0 a regularization parameter. The roles of Li, lg, and lg in (8) are explained as follows.
& corresponds to the objective in the definition of Lovász number of G,,
&g is to approximate the orthonormal representation for G,, i..., (he) T hg =0 0 (p.4) & E, and |/pp|22 s 1 Vp E V4,
fa corresponds the unit-length requirement for the handle vector of Gj, i.e., ||
1l 1.
We call Lovász principle since it aims learn Fw solve the optimization of Lovász number for the graphs drawn from Da. It is known that the Lovász number ( is an upper bound on the Shannon capacity of G (V, E). The Shannon capacity [Shannon 1956) models the amount of information that can be transmitted across a noisy communication channel, where certain signal values can confused with each other. Here, one signal value corresponds to one node of G and (p. 9) E E means that the corresponding two signals can be confused with each other. Therefore, the graph-level and node-level representations given by our Lovász principle correspond to the upper bound of the amount of information transmitted over the graph that is distinguishable between nodes.
Note that instead of the regularized unconstrained optimization (8) we can also use constrained optimization (f2 = fa = 0), which we call strict Lovász principle. We may use the Lagrange multipliers method. projected gradient descent, or exact (or inexact) penalty method to solve the constrained optimization. Take the inexact penalty method as an example, we just need to increase the μ in (8) gradually in the optimization. The graph representation performance comparison between unconstrained and constrained optimizations will be shown in Section 6.5 and Appendix
For convenience, we let
I6l
Thgz2 + (I. O (H I,,))l + [o (9) PEV;
CLo = max
and call it Lovász loss. The Lovász loss is mainly designed for unsupervised grapheeeverpprreenntaare representation learning [Wu et al. 2022 Maron et al. [019 Oono and Suzuki 2019; Ståhlberg et al. 2022), which
can be used as an alternative to the popular InfoMax loss [Linsker 1988 (see 16)).
Lovász principle for semi-supervised learning Inspired by InfoGraph (Sun et al. 2019 (see 17
we propose a Lovász loss function for semi-supervised learning tasks. Suppose the dataset 9 has
We also provide an equivalent formulation based on the complement graph of G in Appendix A
5

---

two subsets: a labeled dataset G and an unlabeled dataset G". Then we deploy another supervised encoder with parameter d and generate the supervised node-level representations H graph-level representations x/" and then prediction y." The overall loss function
164
Lo-semi
supervised 0i yt) Lunsupervised (9)
(10)
where À is positive hyperparameter, the supervised loss supervised is the cross-entropy loss, and the unsupervised loss Consupervised is the Lovász loss Li (Eq. (9) or the enhanced Lovász loss CELO (Eq.
(4) The last term encourages the representations learned by the two encoders to be similar.
4 Enhancing Lovász Principle with Subgraph Lovász Number
Lovász principle does not explicitly utilize the Lovász number in graph embedding. though the Lovász numbers of subgraphs can be useful in comparing graphs (Johansson et al. a [2014). Therefore, we propose to use subgraph Lovász number enhance Lovász principle based graph representation learning. We may consider taking advantage of the Lovász-d kernel proposed by [Johansson et al. 2014). However, we encounter the following two difficulties.
Computing the Lovász numbers (3 of subgraphs time-consuming because we need to solve (2) for every graph and the number of subgraphs of each graph is often very large (up to 21Vl), y). Hence, for large graph dataset, we cannot use (4) directly.
ii The Lovász-1 kernel (4) a pair-wise method and cannot effectively exploit the global structure of G.
To solve the aforementioned problems, present iterative-refinemes strategy that computes the subgraph Lovász numbers using the embeddings given by the Lovász principle. Specifically, at
iteration 6, we have the graph-level representations (f-1)) and the node-level representations H (f-1) given by iteration l - 1. Inspired by the Lovász-0 kernel (4) we compute the similarity between graph G2 and Gy as
K K
Σ
((ISA)
k(0 (G.), (G.) (G,)),
Cs..s,
(11)
SICV SYCV
Vi (s) ( where Cs.ss, =
and S.. (t-1) 1) (G:) (similar for G₁) is obtained by
S. (G.)
max PES; (z) (t-1) hpp 1)22
(12)
The computation of 1/(21' (t-1) T)T hp 2) for every p E V; was already done when computing Li
via (9) at iteration and there no need to solve (3) For (IT). we do not need to consider all
possible subgraphs and we can just randomly sample subgraphs with some fixed sizes (numbers of
nodes), which similar to the truncated Lovász-0 kernel of [Johansson el al. [011]] Thus we can
obtain the similarity (t-1) efficiently. Adapting the idea of spectral embedding [Belkin and Niyogi 2001 propose the following subgraph Lovász number (SLN) loss (at iteration
99 |91
=11 + (12 2. Iall + +1 1xx1
CLL = Σ
(13)
1=1
(()) where > 0. The two regularization terms in SLN aim to make the graph-level representations orthonormal and centered, which is consistent with the constraints in spectral embedding. Minimizing SLL encourages that the graph-level representations of similar graphs (in the sense of subgraph Lovász numbers) are closer each other at iteration t. Integrating (13) with ()) we obtain the following enhanced Lovász loss at iteration /.
d == c( + +
(14)
where 7 > 0 is hyperparameter. It is worth noting that LMA as well as Lia can be implemented batch-wisely, via replacing G with its subsets. Similar to Liss LELD can also be applied semi- supervised graph classification, i... (IO..

---

Related Work
Besides the Lovász-0 introduced in Section 2.2. the closest work to our Lovász principle is the InfoMax principle. Following [Nwwzzi et al. 2016 Sun et al. 2019 Belghazi et al. 2018], suppose the node-level representation hp(x) and the graph-
representation 2(x) are depending on the
input T&p is discriminator parameterized by neural network with parameters the Jensen- Shannon mutual information (MI) estimator [Fuglede and Topsoe|
2004; Nowozin el al. 2016 Hjelm
el al. 2019 Sun el al. 2019) L between hy and is defined
4 (hp, 2) Epp-sp(--appp (o z (x)))) EE (h, =x))))
(15)
where x is the input sample from distribution IP. x' is the negative sample from distribution PP, and sp(a) = log(1 + e*) denotes the softplus function. Many recent graph-level representation learning methods [Sun er al. 2019: You er al., 2220;) Yin er al.) [202] are based on the InfoMax principle,
ie., maximizing (15). For instance, the InfoGraph proposed by (Sun er al., 2019] obtains graph-leve level
representations by maximizing the mutual information between the graph-level representation and the node-level representations as follows
G
0% arg MIX
- -unsspperviveee
(16)
6.0.0
PEV.
For semi-supervised learning, the dataset G is split into labeled dataset go and unlabeled dataset g", They deploy another supervised encoder with parameter yp and then generate the supervised node-level representations H, graph-level representations z and prediction g," The loss function of InfoGraph for semi-supervised learning is defined as follows
10
Linfo-semi
Esupervised (0)", y1) + L unsspeervised (9) A
(z))
(17)
The comparison between the InfoMax principle and our Lovász principle is as follows.
The InfoMax principle focuses on the mutual information between graph-level representation and node-level representation, while our Lovász principle is derived from the Lovász number, fundamental topological property of graph.
Our Lovász principle only needs to optimize é and e. Differently, besides ø and 6, the InfoMax principle has to optimize an additional discriminator parameter &p for the Jensen- Shannon MI estimator. Thus, Lovász principle is simpler than the InfoMax principle.
Approximating mutual information using neural network is challenging [Nowozin el al. 2016) and the lensen-Shannow MI estimator Io only provides an approximation by sampling rather than exact computation. In contrast, our Lovász principle does not rely on mutual information and sampling.
It is worth noting that the Lovász convolutional networks (LCN) proposed by Yadav et al. 2019 was motivated by the observation that removing certain vertices from a graph doesn't affect the graph's global properties such the Lovász number. LCN does not involve any optimization related to the Lovász number and was designed as an alternative to GCN. Our Lovász principle is an optimization principle that can be used in any graph neural network (e.g. LCN). It also useful
in many applications such as graph prompt learning [Liu el al. 2023 Sun et al. 2022 and graph
anomaly detection [a al. 2021
Zhang al. 2023
Cai el 2023
Experiments
In this section, we evaluate the effectiveness of the Lovász principle compared to the InfoMax principle in graph representation learning methods and a few other baselines such as graph kernels. The graph representation learning methods we considered in this paper include InfoGraph (Sun el
af. 2019]. GraphCI. (You el al.) 2020), AD-GCI. [Suresh el al. [202], JOAO Youu el al.) [021] and AutoGCL Yin et al. 2022 which are the most current and influential methods spanning from
7

---

2019 to 2022. Note that the graph-level representation learning principles (GIB) (Wu et al. 2020]
and (SIB) YYu et al.) 202T] are not suitable for unsupervised graph learning and hence will not be compared in this work. To ensure fair comparisons, we follow the neural network architectures of
those InfoMax based methods and replace the InfoMax loss (Eq. (T)) with the Lovász. loss LL (Hq.
( or enhanced Lovász loss LELO (Eq. (14) while keeping the network structures and parameter settings unchanged. We conduct the experiments on TUD benchmark datasets [Morris et al. 2020
and ChEMBL benchmark datasets [Mayr et al. 2018: Gaulton et al. 2012].
6.1 Unsupervised Learning
The first category of compare methods is graph kernel-based methods such as graphlet kernel (GL)
SShervashidze et al.) 2009). Weisfeiler-Lehman tubetree kernel (WL) [Shervashidze et al.) 2011]
deep graph kernel (DGK) Yanardag and Vishwanathan, 2015]. and Lovász-0 kemel [Johansson
er al. 2014). The second category is traditional unsupervised graph representation methods like
node2vec Grover and Leskovee, 2016). sub2vee AAdhikari
SubivecAddhika el al. 2018), and graph2vec [Narayanan]
el al. 2017|. The third category is the methods based on the InfoMax principle (Eq. (16)). including
InfoGraph Sun el al.) 2019], GraphCI. [You el al. [020], AD-GCI. [Suresh el al.) [221], (, JOAOv2
You er al. 2021], and AutoGCL (Yin et al. [202]]. We also include the Lovász number method
(LovászNum) [ováasz 1979] as a baseline, where we solve the Lovász number (Eq. (2) using
semidefinite programming (SDP) [Wolkowicz et al. 2012 and then use the handle vector c* as the
graph-level represetttinn...
Following [Sun et al. [2019] You er al. 2021 Yin et al. 2022], we train graph representation model on unlabeled data obtain graph representations and use these representations and graph labels to train a classifier. Our experimental setup is similar to that of AutoGCL. (Yin et al. 2022]. Specifically, we use 5-layer GIN [Xu et al.) 2018] with hidden size 128 as the representation model and an SVM as the classifier. The model is trained with a batch size of 128 and a learning rate of 0.001. For those contrastive learning methods JOJOv2 and AutoGGL), we use 30 epochs of contrastive pre-training under the naive strategy. We perform 10-fold cross- voss-vaai on each dataset and repeat 10 times with different random seeds and record the average accuracy (ACC) and standard deviation.
Table I: Performance (ACC) of unsupervised learning. The baseline results are from AutoGCL Yin et al.) [2222] and JOAO YYou et al. 2021]. The bold, blue and green numbers denote the best, second best and third best performances respectively, which also applies to Tables
2 and 3
methods
MUTAG
PROTEINS
DD
NCT
COLLAB
IMD8-B
REDDTI-B
REDDIFMM
GL
81.66=2.11
77,39=0188
41.0
kemels
DGK
WT.
87.4422.72
80.72++3.00
92.9240.56
73.302088
80.3120.46
80.01+0.550
66 66.9620.556
72.30-33.44
78.04=0.39
68.82-041
41.27:0.18
46.06+ 0.21
Lovász-0
82,57+1.68
16.411141
75.90=
67,26 1.85
76.03=1.87
43.57+11.9
vector
Bode2ves
sub2vee
61.05=15.80
53.0345.555
52.8421.47
55.26:11.5
71.4820.41
36.6810.42
embedding
graph2vve
13
30:-2.05
73.22+1188
71.10=0.554
75.78=1008 1.3
47, 86+00.26
InfoGraph
1.13
14.4450.31
7235 1.88
76:20: 106
1..5
75.05:287
8250=147
principle
InfoMax
Graphct.
AD-GCL
JOAOx2
87.15+1.56
86.80+1133
8..9111001
73 59:0.65
74 34.3--0
25.2510885
66.91
74.49=0.52
78.62-0.40
72.9910.75
77.87+0.4
09.67=0.51
03.32+0.61
70.4012.11
71.3++1.
71.57=1.01
71.14+0.44
71.6010.86
89.53-0.84
85.52=0.79
78.3511.38
53 0..02
55. 55.57
55. 99 99--0.28
AutoGCL
88.6411.08
80100.336
77.5710.60
82.0010.29
70.1240.68
75.30:0040
88.58=1.49
75
LovászNum
81,4411599
62.4611.11
67.65=2.31
74.735188
724771885
70.57:11.73
71,25=1.99
43.24
InloGraph
59.611
261145
74.131
7821511.35
71461121
15871131
84.76
Lovisz
GraphC1.
1.96
79.
72.444
89,87
principle
AD.
17.44.2.13
74.2912.00
76.25
1.48
22.12
73.85
73.02
17.11
$4.61 1.335
(use (ex)
10A0x2
87.19-1.99
73.
15+
73.15+2.17
15:16.
72.22+14
45
12.12=1.72
19-16
53.74+11.70
AutoGiC
89.02.1 1.47
76.25-1..25
78.95
39
82.63-22112
71.31:1.72
73.9521366
19.41=1811
$7.28 1 1.62
InfoGraph
90. 2.05
76.121 1.72
75.76
79,3611.37
72.67
95
74.96
1.49
84.53
55.1211147
Lovász
GraphC1.
87.9112.42
77.35
74.
73.87
90.23
principle
AD-GCI.
224
193
76.
1.21
154111881
7.
73.48+11
15.64+1.61
(use Casa)
JOA0x2
88.76.
1.43
75
74.62-2.55
76
1.75
72.8511.7
72.97
1.37
85.31
A8
64 1.48
AutoGCL
19.87
16
79.31
12995=1266
72.23+155
52
14,52+144
90.65=146
57.93+11.22
As shown in Table [ the enhanced Lovász loss LELO (Eq. (14) achieves the best performance on all datasets. By replacing the InfoMax loss with the Lovász loss LLo. the performances of the five graph representation learning methods are improved, which demonstrates the effectiveness of the Lovász principle. Furthermore, LF outperformed Lia in most cases, which verified the effectiveness of introducing subgraph Lovász numbers to the Lovász principle. It is worth noting that the LovászNum method performs worse than the Lovász principle based methods, which confirms the limitations we analyzed in Section 3 and verifies the necessity and significance of our proposed methods.
8

---

6.2 Semi-supervised Learning
2022]. we compare Lovász principle with InfoMax principle in semi- supervised learning tasks. The semi- sumi--upervieed losses of our Lovász principle based methods and InfoMax based methods Linfo-semi were shown in (TO) and (17) respec- tively. Following the settings of AutoGCI. (Yin el al.) [022]. we employ a 10-fold cross-validation on each dataset. For each fold, we use 80% the total data as the unlabeled data, 10% as labeled training data, and 10% as labeled testing data. The classifier for labeled data is ResGCN [Chen ei al. [019] with 5 layers and a hidden size of 128. We repeat each experiment 10 times and report the average accuracy in Table 2 We see that our Lovász loss Li and the enhanced Lovász loss CELO outperformed InfoMax loss in all cases, Furthermore, LELo outperformed LLo in most cases. These results are consistent with those in Secion
Following [Hu et al. 2019 You al. 2021 Yin et al.
Table 2: Performance (ACC) of semi-supervised learning.
methods
NC11
PROTEINS
DD
COLLAB
REDDIT-B REDDIT-M5K
GITHUB
Pretrain
73.72+40.24
70.40=1.54
73.5610044
73.71+0.27
86.63-0.27
51.33-1.44
60.8740.17
Pretrain-
Infomax
74.86:10.26
72:2710:40
75.7810.44
73.76:10.29
88.66.00.55
53.61:10.31
65.21
GNN
ContextPred
73.00++0.30
70.23+0.63
74.66+0.51
73.69+0..7
84.76+00.22
51.23-+0.44
62.35++0.3
GrapliCL.
74.63+:0.25
74.17=0.34
76.17=1.37
74.23+0.21
39.11
52.55+0.55
65.81=00779
InfoMax
AD-GCL
75.18:40.31
73.9620477
77.91+0.73
75.82+00.26
90.10:0.15
53.4940.288
64.17+1.38
principle
JOAOv2
74.86-10.39
73.3140.48
75.81-00.73
75.53+4.188
88.7940.65
52.71+0.28
66 66:66000660
AutoGCL
73.75:22.25
75.65-2.40
77.30:1..41
77.16=1.48
79.80:3.47
49.9142.70
12.46:21511
Lovász
GruphiLL
75.46:11.53
75.121187
11,46:11.52
76.12:11.15
89.87111.68
53.6911.68
66.72.11.3
principle
AD-GCL
76.62+1.83
74.21+1.71
78.27+1.39
76.27++1.74
11.36+1.56
65.32+1.00 1..0
JOAOv2
76.13-11.76
73.734188
76.2711148
77.35+1.27
89.31
13.1711..6
1.99
(use Lio)
AutoGCI.
75.77+1.48
16.36+1.57
1..16+1.61
77.63++1.78
4..54-
51.31+181
6.667+1662
Lavász
GraphiCL.
15.81+1.68
75.83
1.67
18.431145
148
71.37+1.58
9..67+1.27
1.75
17.04=1.455
principle
AD-GCL
17.2 15.43=1.58
18.67+1.64
1..98++1.77
91,54
1.546=1.59
1.25
J0A0v2
76.25+1..9
14.6741.37
1.696-18.6
78.8411.75
90.25-11.22
54.3241899
67.52-1173
(use CEL.)
A
76.53:41.92
76.89
1,55
78,82
78.46.
87,31
53.1741.50
66.477+1.26
6.3 Transfer Learning
Following (uu et al., 2019 You et al. 2021 Yin et al. 2022], we compare the performance of our Lovász principles with the InfoMax principle in the task of transfer learning. We use the Pretrain- GNN method [Hu et al.) [019]] as a baseline and employ the Infomax, EdgePred, AttrMasking, and ContextPred pre-training strategies. The experimental settings follow those of AutoGCL (Yin er aa., 2022). More details are in the appendix. As shown in Table the improved Lovász loss LEL performs the best transfer learning tasks. In addition, the Lovász principle based methods generally outperform those based on the InfoMax principle in most cases.
Table 3: Performance (ROC-AUC score) of transfer learning.
methods
BBBP
1ox21
TosCast
SIDER
Con 58.0=44
MUV
HIV
BACE
no Pretrain
63,8=4,3
74.0+0.8
634=0.0
37.3-16
71822.3
75.3=1.9
70.1
Pretrain-
Intomax
68.108
75.3103
38410.8
60.9
7..0-077
1.
GNN's
AttMaakiin
EdgePred
67.3+244
64.3+2.8
76.740.4
76.010.6
64.2-0.5
64.1=0.6
610010.
604400
7188-11
64.1-3.7
74.122.1
7..741.4
77.2=1.1
76.3=10
79.9=0.9
79.3-11.6
strategies
ContextPred
68.0+2.0
7
63.9-066
60.94-066
65.9-38
75.8+1177
77.3+100
79.6++1.2
UragECL
69.6800667
13.8720.56
62.000.S7
60.5310.88
60.80122666
78.88114
InfoMax
AD-GCL
70.01
76.54+0.82
82
03.07=0.72
63.28-10.79
79.78-3.52
12.30=+1.61
78.28=0.97
78.51=080
principle
10A0v2
01.39-0.92
74.2740.62
13.16-045
60.49-1074
80.97-1.64
73.67+1.000
77.51
1.249+1.27
AutoGCI
73.36-0.77
75.69+-0.29
63.47-0.38
0.38
62,51+0063
80.99-3.38
75.83++1.30
78.35-
0.64
83.26+ 1.13
Lovász
GraphCL
71.771.74
75.6611822
147
62.1111.35
7102 1.67
12.2511.42
19:25=145
783111158
principle
AD-GCL
J0A0v2
72.24=1.89
72.16=1.35
17.52+11.74
75.86+1121
63.92
1..36-1.36
12,56=11122
63.87-1553
80.35-2.36
81.26-2.37
74.42+1.57
75.94
79.01=2.68
78.95=2.21
80.17=1.04
79,82+1.3 1.39
(use (io)
AutoGCI.
73.79-1.4
13+1
64.1=1.58
1.58
63.24++1.11
81-32-2.12
76.0441..5
78.64=1.95
82,57 1.95
Lovász
GrapaCt
73.5-1121
26.45+1.33
D4
1.75
63.72F1.32
1.21-2.31
74.541995
N0.37 132
80185+ 1.65
principle
AD-GCL
10A0+2
12.8=1.59
74.13-1.26
17.96=1.71
76.21+11.35
64.27=100
64.1
68
63.91
63.38
74
8176--.01
82.75
2.69
76.51+1.53
1.48
81.08-2.35
11-13118
12,21=1.49
81.34+1.33
(use Law.)
AutoGCI.
74.67 1.81
76.974-1.76
1.45 64.13 1.88
2.41
7.6
79.56-1141
83.57 1.30
6.4 Overall Performance and Significance Analysis
For convenience, we show the average performance of all methods over all datasets in Figure We see our Lovász principles outperformed other methods in the three tasks.
To measure the significance of the improvement over the baselines, we implement paired t-tests on the mean scores obtained from the datasets. A p-value below 0.05 indicates a significant difference. The results presented in demonntttte the statistical significance of the improvements achieved by our methods across all the datasets.

---

Aecuuat Enterene Ohagon Je
Arouued conemoees aeseeoe Loaking
Arcucc Netken Lountes
(a) Unsupervised learning
(h) Semi-supervised learning
(c) Transfer learning
Figure 2: The average performance of different types of methods
Table 4: Significance analysis (p-values) of improvement via the paired t-test. A p-value less than 0.05 indicates a significant improvement.
tasks
principles comparison
InfoGraph
GraphCL
AD-GCL
JOAOv2
AutoGCL
InfoMax vs Lovász (Lto)
0.00067
0.00286
0.02238
0.07347
0.00059
unsupervised
InfoMax vs Lovász (LEL.)
0.00005
0.01626
0.01541
0.01319
0.00035
Lovász ()) vs Lovász (Le1
0.00429
0.10925
0.01522
0.00079
0.00466
InfoMax Lovász (LLo)
0.00028
0.01115
0.04290
0.02147
semi-supervised
InfoMax Lovász (CEL.)
0.00051
0.00051
0.00116
0.01129
Lovász (L) vs Lovász (CH)
0.00169
0.00076
0.00133
0.00545
6.5 Measuring the Quality of Solver Approximation
Given GNN model Fw trained via the Lovász principle, the predicted Lovász number of graph G is denoted (G). while the ground-truth Lovász number ((G) can be computed by SDP
Wolkowicz et al. 2012 Then we define the relative prediction error for the Lovász number as
c = - - (G))/()))))
(18)
Besides the regularized optimization the Lovász principle ( we also propose a constrained optimization method in Appendix [ We select 50 graphs from each of the four datasets and report ep given by both the regularized (μ 10) optimization and the constrained optimization for Lovász principle in Table We can that in almost all cases, the relative prediction errors are less than 10%. This indicates that the Fw trained by the Lovász principle is a good and reliable approximator for the solver A of the Lovász number. This is similar to the idea of learning to optimize.
Table 5: Relative prediction errors eo given by regularized optimization and constrained optimization
(%)
MUTAG
PROTEINS
DD
NCTT
regularized optimization
9.7
8.2+2.1
6.3E1.1
10.2 3,6
constrained optimization
6.5 2.4
7.311.6
6.1
8.5 2.3
6.6
More Numerical Results
The results of parameter sensitivity analysis, ablation study, and time cost comparison are in and Appendix Frrespectivvly.
Appendix C
Appendix
D
7
Conclusions
This paper proposed a novel method called Lovász principle for unsupervised graph-level representa- tion learning. An extension using the subgraph Lovász number was also presented. The numerical results of unsupervised learning, semi-supervised learning, and transfer learning showed that the proposed methods are more effective than graph kernels and InfoMax principle based representation learning methods. Besides unsupervised representation learning, it is possible to apply our methods to other tasks such as graph-level clustering and graph generation. For instance, we can add clustering module (e.g. [Xie el at.) 2016)) to LLD to construct combine LLo with variational autoencoder [Kingma and Welling 2013) train model generate new graphs. Nevertheless, the implementation of these methods out of the scope of this paper.
end-to-end clustering algorithm. We can
10

---

Acknowledgments
This work was partially supported by the Youth program 62106211 of the National Natural Science Foundation of China, the General Program JCY120210024 Research, the research funding T00120210002 of Shenzhen Research Institute of Big Data, the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, and the funding UDF01001770 of The Chinese University of Hong Kong, Shenzhen.
of Shenzhen Fundamental
The authors appreciate the reviewers' and AC's comments and time.
References
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and Aditya Prakash. Sub2vee: Feature learning for subgraphs. In Advances in Knowledge Discovery and Data Mining: 22nd Pacific-Asia Conference, PAKDD 2018, Melbourne, VIC, Australia, June 3-6, 2018, Proceedings, Part 11 22, pages 170-182. Springer, 2018.
Yunsheng Bai, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. Unsupervised inductive graph-level representation learning via graph-graph proximity. arXiv preprint 10:Xvv:904.00000 2019.
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 learming, pages 531-540. PMLR, 2018.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, 14, 2001.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21(uuppl 1):147 i56, 2005.
Jinyu Cai, Yunhe Zhang, and Jicong Fan. Self-discriminative modeling for anomalous graph detection. arXiv preprint urXiv:2310.0626. 2023.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on graph classification. arXiv preprint arXiv: 190500455999 2019.
Ganqu Cui, Jie Zhou, Cheng Yang. and Zhiyuan Liu. Adaptive graph encoder for attributed graph embedding. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 976-985, 176-985,770 2020.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-799 797, 1991.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
Yin Fang. Qiang Zhang, Haihong Yang. Xiang Zhuang, Shumin Deng, Wen Zhang, Ming Qin, Zhuo Chen, Xiaohui Fan, and Huajun Chen. Molecular contrastive learning with chemical element knowledge graph. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 19968-9776 2022.
Bent Fuglede and Flemming Topsoe. Jensen-shannon divergence and hilbert space embedding. In International symposium oninformation theory, 2004. ISIT 2004. Proceedings., page 31. IEEE, 2004.
Laura Galli and Adam N. Letchford. On the lovász theta function and some variants. Discrete Optimization, 25:159-1744 174, 2017.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pages 129-143. Springer, 2003.
11

---

Anna Gaulton, Louisa J Bellis, A Patricia Bento, Jon Chambers, Mark Davies, Anne Hersey, Yvonne Light, Shaun McGlinchey, David Michalovich, Bissan Al-Laziikai, al. Chembl: a large-scale bioactivity database for drug discovery. Nucleic acids research, 40(D1):D1 100-D1 107, 2012.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855 864, 2016.
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint (7X.vv:709.05:00 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. International Conference on Machine Learning, pages 8230-8248, PMLR, 2022.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. International conference on machine learning, pages 4116-4126. PMLR, 2020.
Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. I Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Karan Grewal, Phil Bachman, Adam
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjje Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 6044604, 2022.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 12265, 2019.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 6lst annual symposium on foundations of computer science (FOCS), pages 910-918. IEEE, 2020.
Fredrik Johansson, Vinay Jethava, Devdatt Dubhashi, and Chiranjib Bhattacharyya. Global graph kernels using geometric embeddings. In International Conference on Machine Learning, pages 694-702. PMLR, 2014.
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv: 1312.61312.6114 2013.
arXiv preprint
Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pages 2688-2697. PMLR, 2018.
Donald E Knuth. The sandwich theorem. arXiv preprint muth/9312214, 1993.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint DxXiv:/206.6440 6483, 2012.
Phuc H Lh-Khac, Graham Healy, and Alan Smeaton. Contrastive representation learning: A framework and review. Ieee Access, -:199907-193334, 2020.
Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation-fres self- supe-supe learning on graphs. In Proceedings of the AAAÍ Conference on Artificial Intelligence, volume 36, pages 7372-7380, 2022.
12

---

Shuangli Li, Jingbo Zhou, Tong Xu, Dejing Dou, and Hui Xiong. Geomgel: Geometric graph contrastive learning for molecular property prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 4541-4549, 2022.
Yinqi Li, Hong Chang, Bingpeng Ma, Shiguang Shan, and Xilin Chen. Optimal positive generation via latent transformation for contrastive learning. Advances in Neural Information Processing Systems, 35:18327-18342, 2022.
Ralph Linsker. Self-organization in a perceptual network. Computer, 21(3):105-117, 1988.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and S Yu Philip. Graph self-supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering. 35(6):5879-5900 2022.
Zemin Liu, Xingtong Yu, Yuan Fang, and Xinming Zhang. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. In Proceedings of the ACM Web Conference 2023, pages 417-428, 2023.
László Lovász. On the shannon capacity of graph. IEEE Transactions on Information theory, 25(1):1-7, 1979.
Xiaoxiao Ma. Jia Wu, Shan Xue, Jian Yang, Chuan Zhou, Quan Z Sheng, Hui Xiong, and Le- man Akoglu. A comprehensive survey on graph anomaly detection with deep learning. IEEE Transactions on Knowledge and Data Engineering, 2021.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Andreas Mayr, Günter Klambauer, Thomas Unterthiner, Marvin Steijaert, Jörg K Wegner, Hugo Ceulemans, Djork-Amé Clevert, and Sepp Hochreiter. Large-scale comparison of machine learning methods for drug target prediction on chembl. Chemical science, 9(24):5441-545 2018
Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph repre- sentation learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7797-7805, 2022.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663 2020.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv: 05000000.0000,.... 2017.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: using variational divergence minimization. Advances in neural information processing systems, 29, 2016.
Training generative neural samplers
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint
2019. 2019.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceed- ings of The Web Conference 2020, pages 259-270, 2020.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang, and Jie Tang. Gec: Graph contrastive coding for graph neural network pre- vve-training. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, pages 1160-1160, 2020.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances Neural Information Processing Systems, 33:12559-12571, 2020.
13

---

C. Shannon. The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3):8-19, 1956.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lhhman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. Grakel: graph kernel library in python. The Journal of Machine Learning 2020.
Research,
Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits. In Proceedings of the International Conference on Automated Planning and Scheduling. volume 32, pages 629-637, 2022.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. arXiv preprint arXiv:1908.010000 2019.
Mingchen Sun, Kaixiong Zhou, Xin He, Ying Wang, and Xin Wang. Gppt: Graph pre-training and prompt tuning to generalize graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1717-1727, 2022.
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 34:15920-15933, 2021.
Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan, Yaoqing Yang, and Danai Koutra. Augmentations in graph contrastive learning: Current methodological flaws & towards better practices. In Proceedings of the ACM Web Conference 2022, pages 1538-15499 2022.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Saurabh Verma and Zhi-Li Zhang. Learning universal graph neural network embeddings with aid of transfer learning. arXiv preprint arXiv: 10086, 2019.
Chunyu Wei, Jian Liang, Di Liu, and Fei Wang. Contrastive graph structure learning via information bottleneck for recommendation. Advances Neural Information Processing Systems, 35:20407- 20420, 2022.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9): 1968.
Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe. Handbook of semidefinite program- ming: theory, algorithms, and applications, volume 27. Springer Science & Business Media, 2012.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec, Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-20448, 2020.
Jiancan Wu, Xiang Wang, Fuli Feng. Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. Self- supervised graph learning for recommendation. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pages 726-735, 2021.
Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Le Song. Graph neural networks. Springer, 2022.
Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, pages 1070-1079, 2022.
14

---

Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self- supervised learning for graphs. Advances Neural Information Processing Systems, 35:620-634 2022.
Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Physical review letters, 120(14):145301 2018.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International conference on machine learning, pages 478 487. PMLR, 2016.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. IEEE transactions on pattern analysis and machine intelligence, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 181000060 2018.
Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information- aware graph contrastive learning. Advances in Neural Information Processing Systems, 34:30414- 30425, 2021.
Prateck Yadav, Madhav Nimishakavi, Naganand Yadati, Shikhar Vashishth, Arun Rajkumar, and Partha Talukdar. Lovasz convolutional networks. In The 22nd international conference on artificial intelligence and statistics, pages 1978-1987. PMLR, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1374-1374, 2015.
Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogel: Automated graph contrastive learning via learnable view generators. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8892-8900, 2022.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In International Conference on Machine Learning, pages 12121-12132. PMLR, 2021.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Recognizing predictive substructures with subgraph information bottleneck. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Jiaqi Zeng and Pengtao Xie. Contrastive self-supervised learning for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10824-10832. 2021.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis self-supervised graph neural networks. Advances in Neural Information Processing Systems, 34:76-89, 2021.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self- supervised learning for molecular property prediction. Advances in Neural Information Processing Systems, 34:15870-111 15882, 2021.
Yunhe Zhang, Yan Sun, Jinyu Cai, and Jicong Fan. Deep graph-level orthogonal hypersphere compression for anomaly detection. arXiv preprint arXiv:2302.064530 2023.
Han Zhao, Xu Yang. Zhenru Wang. Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In IJCAI, pages 3434 3440, 2021.
15

---

A Comaprision with the equivalent forms of the Lovász principles
In this section, we propose equivalent form of the Lovász principle based on the complement graph of G. We first introduce an equivalent definition of Lovász number as follows.
Definition A.1 (Lovász number Lovász (179)). Let G be the complement graph of G and U be the orthonormal representations of G. Lovász proposed an equivalent definition of Lovász number as
((G) =
max Σ (d') up) d.Veu PEV
(19)
where d E Rd ranges over all unit vectors.
The unit vector d in the Eq. (19) is also suitable representation vector for graph G. Thus we can obtain a Lovász loss LTo based on Definition A. as follows.
90
L = Σ
Σ PEV;
(2 (<)))T?)
[| (H,) - II + (xx))=2 (00))==--)) -1)
+
1=1
(20)
where M, = A; is a mask matrix for complement graph G. Similar to the main paper, an enhanced Lovász loss based on Definition At at iteration t. is defined as
((t) BLO == Z(t) + A
(21)
where Elt) is the subgraph Lovász number (SLN) loss of complement graph G based on Lovász number definition (19).
We compare the Lovász loss LLD and enhanced Lovász loss ((t) (based on d) with the LL. and L (based on handdle vector c). The results are shown in 6 and For convenience, we show the average performance of all methods over all datasets in Figure We see the two equivalent forms of Lovász principles have very similar performance in the three learning tasks and both of them outperform the InfoMax principle.
Table 6: Performance of unsupervised learning. The bold, blue and green numbers denote the best, second best, and third best performances respectively, which also applies to Tables 7 and
methods
MUTAG
PROTEINS
DD
NCTI
COLLAB
IMDB
REDDITB
REDDIT MSK
Lovász
InfoGraph
89.67+1.54
75.26=1143
74.13+1.49
78.21=1.35
71,46+1.2 1:21
73,87+132
84.76+1..80
54.57+1.38
(use Le.
principle
AC
Graph11.
87.2441..96
87.4412.33
742912880
75.8742.17
76.2511.48
79.14+1.67
79.13+1.27
75.12.1.13
72.52+1.37
1.88
72.4+1446
73.0211.35
87.1111955
89.8742.13
1..122+1.33
54.61
JOAO22
87.1911.92
73.1521.46
73.1542.17
74.1521.67
72.6211.43
72.1811.72
84.191167
53.7411.70
and c)
AutoGCL
89.02411.47
76.23=1.25
78.95:11.99
62.6322.12
71.31+1.72
73.9521.36
89441
57.2841.6
Lovász
IntoGraph
90.1312.05
76.1211.72
15.761164
19.361.37
12.671195
74.96
14.5
55,121
principle
GraphCt.
87.93-42.42
7.3
77.35+11.5
80.11+147
14.7
73.87+1552
00.23++1.87
56.83+1.3
(use Cun
AD-GCI
88.504-1.822
1.92
76.1441.21
78.15+1.1
7..57
73.48+144
1.41
88.16 1.37
55.64 1.63
JOAOz2 88.76.11.43
75.27
74.52
76.2311.75
72.8511.3
72.97.1377
85.31
54.68
and c)
AutoCCL
89.87:1:185
76.0321..37
79.3111.27
82.95=1.26
7..23:1152
74.524144
90.65
57,9311722
Lovász
InfoGraph
88,41+2.47
7433=2253
7.2261157
17.16=245
72.51=193
14.12=165
16
55, 15:18:2222
principle
GraphC1.
86.59411.82
76.2--197
78.35+1.42
78.24+1.68
68
71.46-22.2
73.81+192
16+
54.7542.41
(use Leo
AD.
87.36111.67
25.10
76.7742.10
76.67
1.51
74.2412.17
13.14+1551
88.21
55.42.1 1.31
JOAOz2
88.5812.30
7..2611.52
75.0111.65
71.28
73.21
73.21
85.47.1.02
$5.09.122 2.46
and d)
AutoGCL
88.2542.11
75.7812.31
77.1611.91
80.1611.07
73.11122.1
74.6412.07
87.5742.11
56.83412.5
Lovāsz
InfoGrapp
89.9211.26
1.78
16.121181
80.711199
75.1811.64
73.11
85.16.12.31
54.7 1
principle
GraphCL.
88.93112.51
7..1
77.5212.18
813351162
73.26.12.01
14.211145
89.47.12.33
55.211
(use Lmp
AD-GCL 89.3811.79
76.72-2.09
75.33411995
80.02=2.51
74.1811.44
74.0921550
87, 1.55
56.39-12.2
JOAOv2 87.30::1.25
1..62=1.30
76.12+1.112
79.1422.55
73.11+2.30
16:
37.69-22.20
55.67+1888
and d)
AutoCCL 89,31+2011
75.23+ 46
19.87+1.34 82.71=1334
74,20
73.90+1.67
9044742.5
18.17=1.68
B Experimental setting of transfer learning
Following (Hu et al. 2019: You et al. [022]] Yin et al. 2022]. we compare the performance of transfer learning of the Lovász principle with the InfoMax principle. We use the Pretrain-GNN method (Hu al. 2019] a baseline and employ the Infomax, EdgePred, AttrMasking, and ContextPred
pre-traiming strategies. The experimental settings followed those of AutoGCL (Yin et al. 2022) Specifically, we performed supervised pre-training for 100 epochs on the ChEMBL dataset MMar er al.) 20188] Gaulton et al.) 2012), and then fine-tuned the model for 30 epochs on 8 chemistry evaluation subsets, using a classifier with hidden size of 300. Our training employed a batch size of 256 and a learning rate of 0.001. We substitute the InfoMax loss in the four contrastive learning methods (GraphCL., AD-GCL, JOAO22, and AutoGCL) with the Lovász loss Lio or LE We repeat each experiment 10 times and report the average ROC-AUC scores in Table 3 of the main paper.
16

---

Table 7: Performance of semi-supervised learning.
methods
NCT
PROTEINS
COLLAB
REDDIT-B
REDDIT-M5K
C
Lovász
GraphCL
1..4
75.12+1877
77.4611.52 76.12-1.15
89.87
53.69=1.68
66. 76.12-31553
AD-GCL
76.62.1.88 74.2111.771
78.27 76.27-1.74
90.3611.56
14.06
65.3211.04
(use Lt.
10A0v2
76.13+1.76 73.73+1.86
76.27+1.48
77.35-1.27
89.31+1.85
53.17+1.76
66.36
and c)
AutoGCL
75.7711148
76.36.1.57
78.1611.11
77.63-1.78
84.6412.53
51,311181
64,87.1..22
Lovász
GraphCL
15.81=1.68
75.8811667
78.43+1.48
77.57=1.58
90.67=1.27
5481=1.73
67:44:145
(use CaLa
AD-GCL
77.28.11.04 75.43.11.58
78.67.1..4
76.98
91.54.1..39
55.46.1.59
66.87.1..25
10AOv2
76.25+1.59
74.67+1.37
77.96=1.86
78.84=1.75
90.25+1.22
54.32=1.899
6..52-21.73
and c)
AutoGCL
76.53.11.92
76.8911..55
78.82.11.90
78,46-
87.31
53.1711.50
66.47.1..26
Luváss
Graphi
7..21+1.80
76.67=22.1
78.20=1.64
78.26-2477
90.24+2.13
54.71=197
65.91+2.43
(use L.o
AD-GCL
15.71+1.46 75.39+1.57
77.86=1.77
77.53=1.89
91,1442.63
54.17=2.75
66. 16-11111771
10A0v2
76.40:12.32
74.6141.22
77.26412.01
76.45-1.34
88.2711.89
54.34-2.53
65.41112.76
and dt)
AutoGCL
76.8441.53
76.49+2.03
7..35=1.75
78.02-2.41
16.17=1.61
12.26=11776
64.26+2.41
Luváss
GraphCL
76.28+1.59
76.21+2.300
79.34+2.51
78.10-1.76
91.21+2204
55.62-2.68
6..59+1.62
(use CaLa
AD-GCL
77.65+22.17 15.52+1.97
1.97
77.29-2.33
90.76+2.18
55.14=1.73
67.31+2.41
IOAOv2
76.19++2.30
75.41+2.24
78.03+2.58
1..31-1.49
91.34+2.11
53.70-2441
66.35+2.228
and df)
AutoGCL
1.84
77.25+2.67
1..54
78.27=2.43 88.6942.63
54.28=1.64
66. 1671777667
Table 8: Performance of transfer learning.
НПИР
TaxCast
SIDER
Clin
Lovász Cio
GraphCL
11.37=1.74
75.66=1882
63.351147
62
770021167
72.25=142
0023=143
78.51=1..58
AD-GCL
72.24+1.89
77.52-1.74
63.56+
63.87+1533
80.35+2.36
74.42-1.57
78.95+2.21 2.21
80.17+ 1.7+ 0.4
JOADv2
72.16=1.35
75.86=1.21
63.92.1.52
02.5621.12
81.2642.37
75.94=1.88
79.01
1..
and c)
AutoGCL
13.79=1.41
76.13=1.48
64.21+1.58
63.24+1.51
81.3242.12
76.04=187
78.64
82.57-1100
Lovász
GraphC1.
73.05+ 1.21
76.45+1.35
64.58+1.73
63.72++152
80.2142.11
74.43-195
80.37+1.52
80.63+-1.63
(use Ce
AD-GCL
JOAOv2
72.48=1.59 77.96=1.71
74.13+1.26
76.21=1.35
64.81+192
64.27+1.66
63.38+1.89
13.91
81.7642.01
82.75-2.699
75.88=1.48
76.51=155
81.08+2.35
81.134
12.21+149
and
AutoGCL
74.67=1881
76.97=1.76
65.3611
64.132148
82, 13:2241
76.93-1.62
79.56:1.41
83.57
Lovász ELo
GraphCL.
72.53+42.16
75.27=1.35
64.20+1822
63.16:22.25
17:
74.53-2.28
78.61
1.77777777
AD-GCL
1..7 76.48=2.03
63.7842.21
62.85-22.31
29.33:22.9
73.19=1.22
79.42+1444
18.26714477
JOAOv2
71.78=2.27 75.19=1.8 1.87
64.26+1.65
63.27-11800
81,46
74.39-2.48
79.59-2..1
80. 14:22.51
and d)
AutoGCL
72.52=2.30
76.46=2.33
63.8122.53
62.84:1.334
80.9112.27
25.57=2.16
79.35
81
Lovász
GrapliCL.
22.54::2.23
76.32:
65.6211.74
64.441
817511661
75,20
816411..7
11.57
(use Ca
AD-GCL
10A0v2
71.744281
77.85 1.95
649242.17
64
63.56 1.67
24-25-2557
80
54.4
75.34-111
1.76
81.534
80.56+11
2.42
2..7642..1
and d)
AutoGCL
74.69-2.10
76,21
181
65.134183
63.7742.52
82.47-2.52
75.42=2.25
1.,74+1.56
82.89-2..68
07460
m940
(a) Unsupervised learning
(b) Semi-supervised learning
(c) Transfer learning
Figure 3: The average performance of different types of methods
C Parameter sensitivity analysis
There are five hyperparameters need tuned in Lovász principle method: the dimension of representations d, the hyperparameter of orthonormal representation regularization μr, the hyperpa- rameter of orthogonal regularization in subgraph Lovász number (SLN) loss 7, hyperparameter of subgraph Lovász number (SLN) loss in enhanced Lovász loss 17, the hyperparameter of graph-level representations f2-norm regularization semi-supervised Lovász loss À. In this section, we analyze the parameter sensitivity the InfoGraph Sun et al. [2019) with different hyperparameters. We repeat each experiment for ten times and plot the average accuracy on different datasets.
C.1 as the dimension of representations
In Lovász principle, d is the dimension of node-level representations H -hi,..,,,h, hn.]T E ga and graph-level representation of G, h, E Rd. In the definition of Lovász number, the node-level representations are orthonormal representations, i.e., E Let ax (G) the independent number of graph G, which is the size of the maximum independent set. If d < a(G), the node-level representations H are impossible to orthonormal representations such that the Lovász number cannot be obtained. In Figure we fix other hyperparameters and tune from {10, 20, .... 90, 100).
17

---

(a) MUTAG
(b) PROTEIN
(c) DD
(d) NCI1
(c) COLLAB
IMDB-B
REDDIT-B
(h) REDDIT-MS
Figure 4: The average ACC of different on different dataset
The results show that small adversely affects the performance because may less than (G)) on some graphs. When d is too large, the average accuracy decreases slightly because the representations with large d may capture some noisy information of graph.
C.2 ( for orthonormal representation regularization
(a) MUTAG
(b) PROTEIN
(c) DD
(d) NCII
COLLAB
IMDB-B
REDDIT-B
(h) REDDIT-M5
Figure 5: The average ACC of different on different data
In Lovász principle, μ the hyperparameter for orthonormal representation regularization in Lovász loss Li 9 as follows
[
+ (I (H - I.) + 2 (22)
L1o
max PEV. (.."Th@))
In Figure 5) we fix other hyperparameters and tune from {10 3,003.1--2 10 ..... 105. 10 The results
show that y not sensitive when 0.1 < μ S 1e3. If μ too small, the average accuracy decreases slightly because the node-level representations H may not be orthonormal representations. A very large μ adversely affects the performance because the orthonormal representation regularization dominates the representation learning such that the Lovász principle fails.
18

---

(a) MUTAG
(b) PROTEIN
(c) DD
(d) NCII
(c) COLLAB
IMDB-B
REDDIT-B
(h) REDDIT-MS
Figure 6: The average ACC of different different data
C.3
7 for orthogonal regularization in subgraph Lovász number (SLN) loss
In Lovász principle, y is the hyperparameter for orthogonal regularization in subgraph Lovász number (SLN) loss SIN as follows
Gl
|
SLN =
2 =5112 2 Z Ial + 12 INx 112),
(23)
In Figure 6 we fix other hyperparameters and tune 7 from {10 10 2..., 10S 10 The results
show that 7 not sensitive when 0.1 5 < le3. y is too small, the average accuracy decreases slightly because the orthogonal constraints of spectral embedding may not hold. A very large y adversely affects the performance because the orthogonal regularization of spectral embedding dominates the representation learning such that the Lovász principle fails.
C.4 7) for subgraph Lovász number (SLN) loss in enhanced Lovász loss
(a) MUTAG
(b) PROTEIN
(c) DD
(d) NCT1
COLLAB
IMDB-B
REDDIT-B
(h) REDDIT-MS
Figure 7: The average ACC of different different data
In Lovász principle, 7 is the hyperparameter for subgraph Lovász number (SLN) loss S in (t) enhanced Lovász loss ELo follows
(())
c(t) + T
19

---

In Figure 7 we fix other hyperparameters and tune from {10 2,1002 ..... 10", 10 The results show that 1j is not sensitive when 10 2 I 17 I 1e4. 1j very small number, the enhanced Lovász loss clt) degenerates into the Lovász loss Lto, which also performs well in representation learning. very large yi adversely affects the performance because the subgraph Lovász number (SLN) loss (lt) dominates the representation learning such that the Lovász principle may fail.
C.5 for the normm regularization semi-supervised Lovász loss
(a) MUTAG
(b) PROTEIN
(c) DD
(d) NCI1
COLLAB
IMDB-B
REDDIT-B
(h) REDDIT-MS
Figure 8: The average ACC of different À on different data
semi-supervised learning, the hyperparameter for the no-m regularization semi-supervised Lovász loss as follows
19 Los-sei Σ Sappervise (9) y1) Lunsapervisedd H 2, + x > ||
2, 112
(24)
In Figure 8 we fix other hyperparameters and tune À from {10- 10 ...., 10a 10 The results
show that 17 is not sensitive when 0.1 < S Te3. If X is a very small number, the supervised encoder and unsupervised encoder may learn different information of a graph such that the average accuracy slightly decreases. A very large y) will cause the training to be trapped in early iterations such that the representation learning fails.
D Ablation study
In this section, we analyze the importance the orthonormal representation regularization (Eq. p and the subgraph Lovász number (SLN) loss (Eq. 14) by ablation study on unsupervised learning.
D.1 Ablation study of orthonormal representation regularization
In the ablation study, we remove the orthonormal representation regularization in Eq. ( by setting f 0. The results Table | show that the orthonormal representation regularization can improve the performance of graph representation learning for two reasons:
The orthonormal representation constraint is part of the definition of I Lovász number such that the Lovász principle may fail without the orthonormal representation regularization.
The orthonormal representation regularization guides the method the learn the structure property of a graph.
20

---

Table 9: Performance (ACC) of unsupervised learning for Ablation study. The ablation indicates
in Eq.
The bold numbers denote the better performances of the same method.
methods
ablatin
MUTAG
PROTEINS
DD
NCT
COLLAB
IMDE-8
REDDIT-B
REDDIT-MKK
InfoCrrphh
88.2511.63
89.67-1.554
7..36+1.43
74.18.11.52
13.0511.77
74.13+1.49
76.89:11.22
78.21+1.355
71.46-1.21
1.35
7387-1.8
7200
1.32
1.41
84.76-11 1.86
1.22
51.2121150
54.57-1.88 1.38
Loväsz principle
GraphCL
87.24 1.96
96.1621.33
75.87-2.17
15.1521.50 15
18.211100
19.14:167
79.13
17.8121133
11:05=1.20
72.52-11
1.37
72.44
71322
1,46
57,792138
89.87-2.13
56.12-177 1.73
35.05=2.7
(usc Canl
AD-GCL
JOADv2
27.44
73:52411.8
72.397
76.2511448
12:534201
15
74.53:1
75.12:2.113
25.242252
73.85-100
12.41=1.58
71.1
87.1111.95
88.46:1.35
1.67
53.27=1511
AutoGCL
19.02-1147
88.76:22.15
76.23
75:59:2.03
18.95
78:12:1181
78.95
81:79:=1:05
82.63-12.12
71.31
10:42:1:00
73.95
73.64=1:5
1:52
1.36
33:31:1:22
53.
1.81
$7.28 1.62
56
53:
InfoCraphh
76.12.11.72
GraphCCL
1:57
76.71+1.60
73.57-1.22
89. 90.90-1:52
Lovisz principle
87.93=2244
76.82:11.34
17.35:1995
80.11::1447
74.16=1.37
73.87=1.52
90.23:1877
56.83-1.35
(use KEL.)
ADAGCL
JOADv2
18.36:11:51
88.50=1.82
18.27-11.39
143
75.22:+1.93
74.5241.00
75.27
74,651
14
74.62-1.58
16.14+11221
13
78.15=1881
15.78.11443
76.23:21.75
17.8811
74.57-1.96
72.85
72
74:15: 1.32 74-73 1:22
10:
3.73
1..97-1.37
72.39-2.15
73.48=1.41
18.16:1.37
85.31=1488
11.451136
S1.11
$1.68=1.48
$4.21=1.52
$5.87:
55.64=1.63
AmtOCCI
89: 89.24 2.41
89.87=1855
76.03+1137
75,191
75.
1.58
79.31+1.27
184ZE1A8
82.95=1.26
82.31:1 79
72.23
71
1.52
1.88
74.52=144
74,36
1.44
188
90.651146
90.10 1.73
57.93=1.72
$7.27
D.2 Ablation study of subgraph Lovász number (SLN) loss
If we remove the subgraph Lovász number (SLN) loss in Eq. (4) by setting 1 0, the enhanced Lovász loss (14) degenerates to simple Lovász loss 9 The results in Table show that the subgraph Lovász number (SLN) loss improve the performance of graph representation learning because similar graphs are guaranteed to be close to each other in the representation space.
D.3 Ablation study of orthonormal representation regularization
Table 10: Performance (ACC) of unsupervised learning for Ablation study. The ablation indicates 7 in Eq. (14).
The bold numbers denote the better performances of the same method.
methods
ablation
MUTAG
PROTEINS
COLLAB
IMDB-B
REDDIT-B
REDDIT-M5K
InfoGraph
8966111.54
75.26:1.43
7413:
78.2111.355
71.4611.21
73.871132
84.761 1.86
$4.57 1.38
90.13:12.05
76.12:11.2
75.76.1.64
79.36.1.57
72.67-1.95
74.99.1.49
84.5311.79
55,12:1.A4
GraphCL
87.24=1.96
75.87:22.17
7911=1167
79.13+1127
72.52+1.37
72.4411466
89.8742.13
56.12=11.73
X
87.93-2..2
76,82=1.34
77.35=1.55
80.11:1.47
74.16:+1.37
7388=11.2
90.23++..87
56.83=1.35
AD-GCL
87.4412.13
14.2911330
76.2511.88
75.12:2213
71.551105
13.0211.33
37.1111995
54.6122.35
1,93
76.14-1.21
74.57
73.48
8.31
JOA0v2
88.76++1.43
87:19:192
75.27+
73.13:21:6
73.1=2217
74.62-2.588
74154:167
76.23+1.75
72.62=143
72.85+1.72
72.97+1.77
12.122172
85.31+1448
141991667
54.68 1.48
$3.74=1.77
AutoGCL
89.8711.85
89.02
76.03.1177
78.95
79.31:1.27
82.95:1.266
72.23-1.22
71311172
74.52-1.44
73.95
90.65:11.46
1..93
E
Strict Lovász Principle
We use regularization in Lovász principle instead of constraint because its optimization is much casier and its performance is very close to the constrained optimization. In Algorithm we propose a constrained optimization for the "strict Lovász principle" via projection.
Algorithm 1: Constrained optimization for "strict Lovász principle"
1: Initialization:
2: repeat
3: f F(A, 0²) and #t [AA,
4: Ht = proje (1 and z² = TETT
5: obtain 0'+1, + by SGD updating
6: until Convergence
In Algorithm 1 the Proju project i to the orthonormal representation space, which is similar <h.w>
to the Schmidt process. We define proj (h) = Zw,w>> w. Let W; be the set that Wi- == {wi, W2, ... ). For each vertex i E V, we denote Q2 as the set of vector wys where j can be each vertex not adjacent to vertex Then the H' ) is defined in Algorithm
21

---

Algorithm 2: The definition of projection function Proje
1: w1 h1 E1
1
2: W2 h2g E
ZwEWs.Ing pr (ht), 62
u02 || wea
3:
4: = hi EweWs proj (ft)).
M2% 1
5:
6:
Wn hn Emew, 1 12, proj (hn) en
Win 1
7: Ouiput 11 |el, e2,,,,,..., En
The comparisons between the regularized (μ1 1) optimization and the constrained optimization for two methods on four datasets are as follows.
Table 11: Comparison between regularized optimization and constrained optimization
method
MUTAG
PROTEINS
DD
NCTI
regularized opt.
IntoGraph
89.67+ 1.54
75.26 + 1.43
14.13+
1.49
78.21
1.35
regularized opt.
GraphCL
87.24=1.96
75.87
2.17
79.14
1.67
79.134
1.27
constrained opt.
InfoGraph
86.12: 2.32
75.491
1.52
76.42
1.56
77,80
1.24
constrained opt.
GraphCL
87.52 2.75
76.11
1.36
78.54
#221
77.63
1.58
F
Time cost comparison
We compare the time cost between the InfoMax principle and Lovász principle using the InfoGraph Sun et al. [2019) model on different datasets. We run the programming on a machine with Intel 7 CPU and RTX 3090 GPU. We repeat the experiment five times and report the results in Table [2 The Lovász principle is the fastest method among the three. The Lovász principle is the fastest method
Table 12: Time cost of InfoGraph. h stands for hour and stands for minute. The brown value indicates the lowest time cost.
tasks
priccplle
MUTAG PROTEINS
DD
NCIT
COLLAB IMDE-B
REDDIT-B REDDIT-MSK
InloMax
2.3m
12.6
36.5 m
50
3.8
14
7h
unsupervised
Lovász
18
11.7
1h.25 m
33.2 m
16
5.1
3
76.26
leaming
Enhanced
1.8 m
12.2
1 1130
34.3 m
1
5.3
3 10
h
Lovász
semi-
InfoMax
2.3
13.1
Th47 m
46.3 m
2h m
9.6 m
3h m
8h m 8Th 16
supervised
Lovissz
2.
12.7
Th
43.1
2h
8.1
5
Enhanced
learning
2.0
12.8
h
42.6
2 17
8.3
3
Lovász
among the three, and the reasons are as follows:
The Lovász principle is faster than the InfoMax principle because the former does not the f-GAN [Nowozin er al. 2016) and the Jensen- Shasnon MI estimator Ip to evaluate the mutual information.
Enhanced Lovász principle is slightly lower than Lovász principle because the computation of 1/ 1)T (t- y2 for every p V, was already done when computing Lio. up
22


Reviews:
[{"review_id": "J2z1RvNm3g", "reviewer": "Reviewer_JpeL", "summary": "This submission presents a new approach to graph-level representation learning inspired by the Lovász number in graph theory. Specifically, the study proposes using the Lovász principle as a novel framework for unsupervised/semi-supervised graph representation learning. It offers a method to utilize handle vectors, which capture a graph's global features through neural networks. An enhanced Lovász principle is also proposed, which efficiently uses subgraph Lovász numbers, thereby ensuring similar graphs have similar representations. Experimental results show that the Lovász principles outperform other graph representation methods (such as InfoMax) in unsupervised learning, semi-supervised learning, and transfer learning. Therefore, the Lovász principles offer a promising new approach to graph-level representation learning.", "questions": "Overall, this paper has a good idea of using the Lovasz Principle (the handle vector) to present the graph and incorporate this idea to design GNN models. However, there is some related work, and the authors should have discussed it in the submission.\n\nQ1: How could you deal with large-size graphs? For example, the datasets RDT-B and RDT-M5K were used in [2]. My concern is that it is unclear how you can estimate C_{S_i,S_j} accurately when n, the number of nodes in the graph, is large. \n\nQ2. Compared with InfoMax, why the performance of InfoMax-based (in terms of best ones) are very close to the proposed? More discussions are needed.\n\n[2] Sun, Fan-Yun, Jordan Hoffmann, Vikas Verma, and Jian Tang. \"Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization.\" arXiv preprint arXiv:1908.01000 (2019).\n\nSome minors:\n\n1. It is helpful to list out all dataset statistics for people who are unfamiliar with this area.\n\n", "limitations": "None.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "There are three main strengths:\n\n1. A new approach based on the Lovász principle is proposed for graph-level representation learning. This principle, inspired by the Lovász number in graph theory, adds a new perspective and strategy to graph learning, shifting from traditional methods.\n\n2. Some subgraph tricks are used to enhance the performance of Loasz-based GNN models.\n\n3. The Lovász principles outperform other methods in experiments on unsupervised learning, semi-supervised learning, and transfer learning. \n", "weaknesses": "Weaknesses:\n\n1. Compared with current GNN models, such as Infomax-based and kernel-based methods, there are indeed some gains in terms of ACC on the task of graph classification. However, the overall gained performance in Table 1,2, and 3 is not very significant, especially when you consider the variances. This may question whether Lovász Principle can provide more useful global information than InfoMax. The other concern is that it is unclear how the approximation affects the whole performance since the final vectors used in the proposed models are approximated.\n\n2. In terms of the novelty of using the Lovász Principle for designing GNN models, one of my main concerns is that this idea is not very novel. There is a lack of discussion on the difference between current work and previous works. See related works in [1]. In terms of run-time comparison, there is no significant reduction compared with InfoMax based on the run-time table in the appendix.\n\n[1] Yadav, P., Nimishakavi, M., Yadati, N., Vashishth, S., Rajkumar, A. and Talukdar, P., 2019, April. Lovasz convolutional networks. In The 22nd international conference on artificial intelligence and statistics (pp. 1978-1987). PMLR.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Concern about the novelty**\n\n**Response:** We have to clarify that our method is **very different** from [1] (Lovasz Convolutional Networks (LCN)). LCN was motivated by the observation that removing certain vertices from a graph doesn't affect the graph's global properties such as the Lovasz number. LCN replaces the affinity matrix $\\hat{A}$ of classical GCN by a Lovasz kernel $K = \\frac{A}{-\\lambda_{\\text{min}}(A)} + I$ and hence yields the following model: $f({X}, {K}) = \\text{softmax}({K} \\text{ReLU}({K}{X}{W}^{(0)}){W}^{(1)})$. In contrast, our Lovasz principle is inspired by the umbrella analogy in Figure 1. We summarize the differences as follows:\n* The goal of LCN is node embedding and classification while the goal of our Lovasz principle is graph representation learning.\n* More importantly, according to $f({X}, {K})$, we see that LCN does not involve any optimization related to Lovasz number. It just replaced $\\hat{A}$ of classical GCN with a predefined $K$.  In contrast, our Lovasz principle transcends specific GNN designs and it solves the optimization of Lovasz number and orthogonal representation via deep neural networks:\n$\\mathcal{L}_ {\\mathrm{Lo}}=\\sum_{i=1}^{|\\mathcal{G}|} \\max _{p \\in V_i} \\frac{1}{\\left(\\left(\\boldsymbol{z}_i^\\phi\\right)^{\\top} \\boldsymbol{h}_p^\\theta\\right)^2}+\\mu\\left(\\left\\Vert\\boldsymbol{M}_i \\odot\\left(\\boldsymbol{H}_i^\\theta\\left(\\boldsymbol{H}_i^\\theta\\right)^{\\top}-\\boldsymbol{I}_n\\right)\\right\\Vert_F^2+\\left(\\left(\\boldsymbol{z}_i^\\phi\\right)^{\\top} \\boldsymbol{z}_i^\\phi-1\\right)^2\\right)$\n* Our Lovasz principle yields better graph representations than other methods such as the Infomax principle.\n\nWe sincerely thank the reviewer for pointing out the reference and we will include it in our revised paper and provide a discussion.\n\n\n\n**Concern about the regularization approximation instead of exact constraints**\n\n**Response:** We use regularization instead of constraint because its optimization is much easier and its performance is very close to that of the constrained optimization. For the constrained optimization (\"strict Lovász principle\"), we consider the following projection based methods:\n\nStep 1: $\\hat{H}^{t} = F({A}, {X}; \\theta^t)$ and ${\\hat{z}}^{t} = f({A}, {X}; \\phi^t)$\n\nStep 2: ${H}^{t} = \\text{Proj}_U ({\\hat{H}}^{t})$ and ${z}^{t} = \\frac{{\\hat{z}}^{t}}{\\|{\\hat{z}}^{t}\\|}$\n\nStep 3: obtain $\\theta^{t+1}, \\phi^{t+1}$ by SGD updating\n\nThe $\\text{Proj}_U$ project ${\\hat{H}}^{t}$ to the orthonormal representation space, which is similar to the Gram–Schmidt process. We define:\n$\\text{proj}_w (h) := \\frac{<h, w>}{<w, w>} w$.\nLet $W_k$ be the set that $W_k := \\{{w}_1, {w}_2, ..., {w}_k\\}.$ For each vertex $i \\in V$, we denote $\\Omega_i$ as the set of vector ${w}_j$s where $j$ can be each vertex not adjacent to vertex $i$. Then the ${H}^{t} = \\text{Proj}_U ({\\hat{H}}^{t})$ is as following:\n\n--------------------------------\n\n$ {w}_1 = \\hat{h_1^t},  {e}_1 = \\frac{{w}_1}{\\|{w}_1\\|}$ \n\n...\n\n\n$w_k = \\hat{h_k^t} - \\sum_{w \\in W_{k-1} \\cap \\Omega_k} \\text{proj}_w (\\hat{h}_k^t),  e_k = \\frac{w_k}{\\|w_k\\|},$\n\n...\n\nOutput ${H}^{t+1} = [{e}_1, {e}_2, ..., {e}_n]^\\top$\n\n--------------------------------\n\nThe comparisons between the regularized ($\\mu = 1$) optimization and the constrained optimization for two methods on four datasets are as follows.\n\\begin{matrix}\n\\hline\n&method & MUTAG &  PROTEINS &  DD & NCI1  \\\\\\\\     \\hline\n regularized\\ opt. & InfoGraph &  89.67\\pm 1.54   & 75.26 \\pm 1.43 &74.13\\pm 1.49 &78.21\\pm 1.35  \\\\\\\\\n regularized\\ opt. &GraphCL   &87.24\\pm1.96    & 75.87\\pm 2.17  & 79.14 \\pm 1.67 &79.13\\pm 1.27 \\\\\\\\\n constrained\\ opt. &InfoGraph  &86.12\\pm 2.32     &75.49\\pm 1.52  &76.42\\pm 1.56  & 77.80\\pm 1.24 \\\\\\\\\n constrained\\ opt. &GraphCL    &87.52 \\pm 2.75     & 76.11\\pm 1.36  & 78.54 \\pm 2.21  &77.63\\pm 1.58 \\\\\\\\ \\hline\n\\end{matrix}\nWe see that the approximation has less effect on performance. We also tested the **exact penalty** method, i.e. increasing $\\mu$ gradually and the performance is similar to those in the above table.\n\n**Question 1: Dealing with large-size graphs**\n\n**Response:** This is a good question. Our first formulation $\\mathcal{L}_ {Lo}$ is more efficient than the Infomax principle and can handle large graphs easily. In our second formulation $\\mathcal{L}_ {SLN}$, we use the truncated Lovasz kernel [8] for large-size graphs. Instead of calculating the Lovasz number for all $2^{|V|}$ vertex subsets $V$, we evaluate it on a more manageable set of subgraphs sampled from the $2^{|V|}$ possibilities. This sampling strategy significantly mitigates the computational complexity on large graphs and works very well in practice [8]. We will include the experiments on RDT-B and RDT-M5K [2] in the revised paper.\n\n[8] Johansson F et al. Global graph kernels using geometric embeddings[C] ICML 2014.\n\n\n**Question 2: Concerns about the significance of performance improvement over InfoMax principle**\n\n**Response:** Actually, the improvement especially our second method $\\mathcal{L}_{ELo}$ over InfoMax principle is large in most cases. For instance, in Table 1, in terms of InfoGraph on NCI1, the performance of InfoMax principle is 76.20±1.06 while the performances of our two methods are 78.21±1.35 and 79.36±1.57 respectively. Considering that we have eight datasets, we apply the paired t-test on the mean scores over the datasets to show the significance of our methods over each of the baselines. The p-values are as follows. A p-value less than 0.05 indicates a significant difference. We see that 9 out of 10 cases are significant. This demonstrated the significance of gains given by our methods.\n\\begin{matrix}\n\\hline\n& InfoGraph &GraphCL &AD-GCL &JOAOv2 &AutoGCL \\\\\\\\  \\hline                           \nInfoMax\\ vs\\ Lovasz& 0.00067 & 0.00286 & 0.02238 & 0.07346 & 0.00059 \\\\\\\\\nInfoMax\\ vs\\ Enhanced Lovasz.& 0.00005 & 0.01625 & 0.01540 & 0.01319 & 0.00035 \\\\\\\\ \\hline\n\\end{matrix}\n\n\n"}, {"review_id": "gSdpEGwGRs", "reviewer": "Reviewer_1BFQ", "summary": "The authors present a new method for graph representation in supervised, semi-supervised and transfer learning based on the Lovasz theta function [Lov79]. They also incorporate local information using Lovasz subgraph numbers inspired by the work on Lovasz theta kernal [Joh+14]. They also present empirical evaluation and show that their method is competitive with state-of-the-art. \n", "questions": "\n- It would be interesting to see in eqn (9) how the different loss terms during training corresponding to the theta-value ($l1$) and  orthonormal representations ($l2$ and $l3$) and similarly for SLN when thinking of the final READOUT as non-linear analogues of the Lovasz representation. \n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper is easy to follow for the most part.  \n- The empirical evaluation shows the method performs well compared to existing methods.\n", "weaknesses": "Some rewriting needed on Section 4 and minor typos. Also ablation studies and final parameter selection still a bit unclear. \n\n**SLN** \n\n- Lines 209-211. Please define \"subgraph Lovasz number\" explicitly. \n\n- Lines 214-218. The description of Lovasz $\\vartheta$ kernel [Joh+14] is misleading. \n    - Lines 214-216. Possibly I misunderstood this, but subgraph lovasz value as defined in [Joh+14, Definition 2] can be well-approximated using $O(n \\log n)$ samples [Joh+14, Thm. 1].\n\n    - Lines 217-218. In so far as the kernel being a pair-wise method and not capturing the \"global structure\" of $\\cal G$, here is the trivial equivalent using the kernel:  $ \\sum_{i=1}^{\\cal G} \\sum_{j=1}^{\\cal G} \\hat{k}_{\\tt Lo}(G_i, G_j) $.\n\n- Lines 226-229. How is $K^{(t)}_{ij}$ computed, more precisely the number of  sampled subgraphs and how those are selected? \n\n**Ablation and default parameters** \n\n- The ablation study has explored parameter choices for $\\mu$, $\\eta$, etc. over log-ranges for the different graph datasets. However, what is not so clear is the influence of graph dataset properties (e.g., size of the graphs, density, node properties, etc.) \n\n- It would be great if the authors could present preferably in the main text or the appendix, a set of sane starting points. Of course, for each use-case, HPO should be done but often, the practitioner take is to go with defaults initially. \n\n**Minor typos**\n\n- Appendix. Section 4. lines 80-91 \"orthnormal\" -> \"orthonormal\"\n- Appendix. Section 5. line 95. \"guarantee\" -> \"guaranteed\" \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely thank the reviewer for recognizing our contribution. Our responses are as follows.**\n\n**On SLN**\n\n* The definition of \"subgraph Lovasz number\" is in [Joh+14, Definition 2]. Given a graph $G = (V, E)$, let $G[S]$ be a subgraph of $G$ induced by a vertex subset $S \\in V$. The \"subgraph Lovász number\" is defined as \n$ \\vartheta_S (G) = \\min_c \\max_{u_i \\in U_{G|B}} \\frac{1}{(c^\\top u_i)^2}, $\nwhere $U_{G|S} := \\{u_i \\in U_G | i \\in S\\}$ and $U_G$ is the orthonormal representations associated with $\\vartheta(G)$. Note that in general $\\vartheta_S (G) \\neq \\vartheta(G[S])$. We added this definition to the revised paper. \n\n* You're right. In the case of larger graphs, [Joh+14] doesn't calculate the Lovasz kernel for all graphs; instead, they employ a sampling strategy to decrease the run-time. Similarly, in our experiments involving large graphs, we also utilize sampling techniques to enhance run-time efficiency. The equivalent totally sum-up kernel you mentioned is actually effective in capturing the graph information across the entire graph dataset $\\mathcal{G}$. We will modify the formulation accordingly.\n\n* We follow the implementation code of the Lovasz kernel [Joh+14] in the Grakel framework [1]. When dealing with large-size graphs, Grakel [1] selects subgraphs of sizes 3, 4, and 5, while excluding others. This is their code implementation for achieving a well-approximated Lovasz kernel using samples as in [Joh+14, Theorem 1].\n\n[1] Grakel \\url{https://ysig.github.io/GraKeL/0.1a8/kernels/lovasz_theta.html}\n\n**On ablation study and default parameters**\n\n* Thanks for pointing it out. We will add a comprehensive description of the data statistics, parameter settings, and starting points for each dataset in the supplementary material. We will also release our codes publicly.\n\n**Question: Analysis of Losses and the non-linear READOUT analogues**\n\n* The role of each loss has been analyzed in the supplementary material. In Appendix 3 (Parameter sensitivity analysis), we choose the weight of each loss from $10^{-3}$ to $10^6$. The performance of very small hyperparameters can be regarded as the ablation for each loss.  The Ablation study in Appendix 4  also indicates that orthonormal regularization is of great importance in our Lovasz principle.\nby the way, instead of using a fixed $\\mu$, we can increase the value of $\\mu$ gradually, which corresponds to the exact penalty method and is able to well approximate the constrained optimization. \n\n* The role of Lovasz principle is very similar to the READOUT function or pooling layers in graph-level representation learning. The typical READOUT [2] methods tend to be straightforward, like average pooling or max pooling. The Lovasz principle, on the other hand, is firmly rooted in graph theory, stemming from its connection to the Lovasz number.\n\n[2] William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning\n\n**We're grateful for your suggestion. We plan to enhance the clarity of the definition and presentation of SLN in the main text, and we'll also include additional experimental details about the data and default parameters in the supplementary materials.**\n\n\n"}, {"review_id": "4rstqCp9Ie", "reviewer": "Reviewer_4DKt", "summary": "This paper centers on graph-level representation learning, aimed at converting graphs into vectors useful for downstream tasks like graph classification. The authors propose a unique learning principle named the Lovász principle, inspired by the Lovász number in graph theory. The Lovász number, a real number serving as an upper bound for a graph's Shannon capacity, has strong ties to various global graph characteristics. The authors suggest that the handle vector, used for calculating the Lovász number, could be an effective choice for graph representation given its ability to capture global graph properties. However, its direct application poses challenges. To address these, the authors propose using neural networks to offer the Lovász principle. They also present an enhanced Lovász principle capable of directly and efficiently utilizing subgraph Lovász numbers. Experimental results demonstrate competitive performance of these Lovász principles in comparison to the baselines in both unsupervised and semi-supervised graph-level representation learning tasks.", "questions": "1. I strongly suggest that the author discuss the application of graph kernel in updated scenarios, such as graph prompt learning. It is highly recommended that the authors consider citing the prompt learning on graph[1,2] paper and explore its application in conjunction with the proposed method in this paper, especially for unsupervised settings. This would enhance the discussion and potential application of prompt-based models.\n\n [1] Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. Z Liu, X Yu, Y Fang, X Zhang - Proceedings of the ACM Web Conference 2023, 2023\n\n [2] Sun, M., Zhou, K., He, X., Wang, Y. and Wang, X., 2022, August. Gppt: Graph pre-training and prompt tuning to generalize graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining.\n\n2. Providing a framework of the proposed model can indeed enhance the clarity of its functionality.\n3. Why semi-supervised learning baseliens such as GCN, GAT, GIN are not compared in the paper?", "limitations": "See weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors' proposal of Lovász theta kernels for graph representation learning shows great promise, thanks to its theoretical foundation.\n2. The paper includes thorough experiments conducted in various settings, including unsupervised, semi-supervised, and transfer learning. These experiments provide strong evidence of the effectiveness of the proposed methods.", "weaknesses": "1. Although the author proposed a new graph kernel, the contribution seems slightly small to me.\n2. The author did not demonstrate the framework of the model.\n3. Some classic baselines were not compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Question 1: Applications for graph prompt learning**\n\n**Response:** We appreciate your suggestion and will cite papers [1,2] in the revised paper. Graph prompt learning involves transferring learning in graphs. Challenges arise when refining a pre-trained Graph Neural Network (GNN) for specific tasks using limited labeled data. Fortunately, when the GNN is initially pre-trained based on the Lovász principle, it acquires representations geared towards solving the Lovász number problem, rather than being tailored to a specific task. This pre-trained GNN, rooted in the Lovász principle, can seamlessly adapt to downstream tasks' unlabeled data to learn their orthogonal representations. Moreover, we can determine the true Lovász number of the downstream task's data and employ the pre-trained GNN to predict the Lovász number for the same data. The regression loss between the true Lovász number and the predicted Lovász number serves as a prompt to fine-tune the pre-trained GNN. The Lovász principle, being a graph-based learning principle, is exceptionally well-suited for graph prompt learning.\n\n**Question 2: Lack of model framework**\n\n**Response:** We in this rebuttal provide a model framework in the attached PDF file.\nLovasz principle Eqn. (8) is actually a loss function Eqn. (9). This loss function finds utility in all graph learning models satisfying Eqn. (7), including examples like InfoGraph [3] and GraphCL [4]. To illustrate, consider InfoGraph [3]: by substituting the original InfoMax loss with the loss function from Eqn. (9), we establish an InfoGraph framework guided by the Lovasz principle. Importantly, the Lovasz principle's applicability isn't confined to any specific GNN model or graph data; rather, it offers a versatile approach across various contexts. Its generality is parallel to that of the InfoMax principle. \n\n[3]Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-\n476 supervised graph-level representation learning via mutual information maximization. \n\n[4]Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph\n527 contrastive learning with augmentations.\n\n\n**Question 3: Comparison with  some basic GNN models**\n\n**Response:** When it comes to learning graph-level representations, our primary comparison baselines (InfoGraph[3], GraphCL[4], AD-GCL[5], JOAO[6], AutoGCL[7]) stand out as the most current and influential methods spanning from 2019 to 2022, each boasting high citations on Google Scholar. Notably, these approaches are considerably more sophisticated and effective compared to fundamental GNN models like GCN, GAT, and GIN. Furthermore, these updated methods incorporate basic GNNs as foundational elements, with GIN serving as a fundamental component in all five techniques. Particularly, InfoGraph employs five GINs to acquire $H$ and  $z$. It's worth mentioning that graph-level representation learning achieved by merely adding a READOUT function [8] to basic GNNs doesn't lend itself well to direct comparison.\n\n\n[5] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve\n graph contrastive learning. \n\n[6] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated.\n\n[7] Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogcl: Automated graph contrastive learning via learnable view generators.\n\n[8] Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and\ninterpretable prediction of material properties.\n\n**We sincerely thank the reviewer for recognizing the contribution of our work.**"}, {"review_id": "L70KqU2faP", "reviewer": "Reviewer_JWhm", "summary": "This paper presents a technique for unsupervised graph-level (and potentially node-level) representation learning on graphs. The main idea behind the proposed method is the concept of the *Lovász number*, a graph invariant that is related to several graph properties and is computed by solving a min-max optimisation problem on the graph. In particular, to compute this, one needs to optimise a graph-level representation (named the *handle vector*), as well as a set of node-level representations (named the *optimal graph representation*), under certain constraints.\n\nAlthough the optimisation problem can be solved in polynomial time, it has several disadvantages (it is computationally expensive, it does not have a unique solution, it cannot generalise to unseen graphs, etc.). The authors propose to overcome them by replacing the conventional optimiser with a neural network-based one, i.e. they train a neural network to map each graph to the aforementioned representations, by optimising the Lovasz number objective (regularised by the constraints) with gradient descent. This idea is extended to a more fine-grained setup in order to incorporate subgraph-level information via the so-called Lovasz kernel (a kernel that compares subgraph-level Lovasz numbers). The method is evaluated on several scenarios (unsupervised, semi-supervised and transfer learning), showing consistently competitive performance, and ablated with regards to some algorithmic choices and hyperparameters.\n", "questions": "**Experiments**.\n- Could the authors discuss how the loss terms behave in practice (for both Eq. (8) and Eq. (13))? Does one term dominate over the others, and how far are the constraints from being satisfied (this is also related to my first concern)?\n- More experimental/implementation details are needed regarding the transfer learning experiment. The authors mentioned that these can be found in the supplementary material, but I couldn't find enough details. For example, it was unclear how the pre-training is performed and where the Lovasz number loss is used.\n- Appendix Section 3.2.: I found it a bit puzzling that the performance does not deteriorate when $\\mu$ is too large (e.g. 1000). I would expect that these values would imply an unsuccessful optimisation of the first term of the objective. Have the authors tested this (e.g. by testing if the learned graph and node-based representations lead to a value close to the Lovasz number)?\n- Appendix section 4.1. is a bit confusing. It seems that in several cases, using the orthonormality constraint deteriorates performance. Could the authors comment on this?\n- Did the authors reimplement the baselines, in order to ensure fairness of comparison?\n\n\n**Minor**:\n- If I am not mistaken the Lovasz number is computed by also optimising over the dimension of the handle vector. Could the authors account for this as well? \n- Could the authors provide more details on the computational complexity of computing the Lovasz number (this is relevant to the question if a GNN can solve this problem to optimality)?\n- In the last two sections of Table 1, I assume that the authors simply used the neural network architectures of the mentioned papers, however the way the results are presented is a bit confusing. Maybe explicitly mentioning it in the caption would help. Moreover, the important element that should be highlighted in this table, is if the Lovasz optimisation objective improves against the baseline one, so maybe the authors would like to reorder the rows in the table to emphasise this comparison.\n- It might be also useful to add some results in Table 1 from end-to-end supervised learning methods, in order to obtain a more complete picture of the capabilities of the unsupervised methods.\n- Have the authors considered using the node-level representations for node-wise tasks?\n- L291: “For those contrastive…naïve strategy”. Do the authors refer to the baselines? This should be clarified to avoid confusion.\n- Typo: Section 4.3.\n\n\n\n", "limitations": "The authors make a short discussion on the limitations in the conclusion, but I think more should be mentioned (especially regarding the ambiguity regarding the learned representations - see the weaknesses section).  No foreseeable negative societal impact.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "**Presentation and motivation**: The paper is generally well-written (with the exception of some clarity issues – see weaknesses). The idea of the Lovasz number is well-explained and illustrated, as well as its role as a graph description is well-motivated. Moreover, the arguments in favour of devising a learning algorithm instead of a conventional optimiser are well-presented. \n\n**Originality and potential impact**. The concept of the Lovasz number is under-explored by the graph ML community (especially from the perspective of graph neural networks), therefore this paper brings a refreshing idea into the field, that might be useful in topics beyond unsupervised learning and pose some interesting new research questions (I mention some of them in the weaknesses section).  It may also incentivise more research exploring other graph properties and combinatorial optimisation problems for unsupervised learning.\n\n**Empirical results**. The method seems to provide consistent performance improvements over multiple unsupervised learning baselines, which indicates its practicality. Moreover, judging from the reported results in the appendix, it seems relatively robust to hyperparameter choices. \n", "weaknesses": "**Lack of theoretical justification & ambiguity regarding what the model is learning**. Given the empirical results, it seems that the method has some appealing property that makes it work well in practice. However, perhaps the biggest weakness of this paper is that it remains unclear what this property is and the authors have not discussed this adequately. In particular,\n- It is unclear if the GNN is actually learning the handle vector + optimal graph representations (when optimising Eq. (8)). To be more precise, it is unclear if a GNN *can* express this (mapping a graph to representations that optimise Eq. (2), using a GNN). Given the computational complexity of the problem, I suspect that a GNN (of linear complexity), probably will *not* be able to optimally succeed in this task, but perhaps maybe only approximate it? These are important theoretical questions that should be discussed by the authors.\n- Additionally, the constraints are not guaranteed to hold, which casts further doubt on the ability to converge to the desired representations. I think it would be useful to actually test (e.g. for the models whose performance is reported in the tables) how far are the resulting representations from satisfying the constraints, and how good are they in approximating the Lovasz number. Moreover, do the node features (that are taken into account by the GNN, but not in Eq. (2)) affect the resulting representations? Reporting these results will provide further insights into what these models are actually learning. \n- I am wondering if it is actually desired to learn to infer the handle vector since the results in Table 1 (reported as Lovasz number) are significantly worse than the proposed method (reported as Lovasz principle). Isn’t this contradictory to the initial motivation?\n- Eventually, I am wondering why is this method so good (and better than the Lovasz number) at solving the tested downstream tasks. What kind of information do the resulting representations contain? Maybe something related to substructures? Note that the arguments mentioned by the authors are attractive properties of the Lovasz number, but not the handle vector. \n\n\n**Clarity issues and inadequate justification of design choices**. Some of the choices made by the authors are not sufficiently justified and I’d like to encourage them to provide more details. In particular,\n- Section 3, Eq. (8):  Wouldn’t it be possible to guarantee the satisfaction of the 2nd constraint (unit-length constraint for the handle vector) by construction? For example, isn’t it possible to extract an unconstrained graph representation using a GNN and then divide it by its norm? It would be interesting to discuss if something similar could happen for the 1st constraint.\n- Section 3, Eq. (10): Similarly, here why does one need a second encoder (and therefore the third regularisation term)? Why not use the same encoder and compute both objectives with that?\n- Section 4. This section lacks the required level of detail and some parts are inadequately explained. \n  - I am a bit confused by the iterative nature of the algorithm here. Could the authors elaborate? Do the iterations refer to gradient iterations, i.e. is this akin to bi-level optimisation? If this is the case, why is the first term of Eq. (14) not indexed by $t$? \n  - How many subgraphs are needed to obtain a good estimate of the kernel?\n  - The role of the spectral embedding idea is unclear to me. Why are the handle vectors encouraged to be orthogonal in Eq. (13), and most importantly what is the role of the last term?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We highly appreciate your comprehensive review, insightful comments, and positive assessment.**\n\n\n**Weakness: Lack of theoretical justification & ambiguity regarding what the model is learning**\n\n* We assumed that the training data ($N$ graphs) are from the same distribution. Thus, the graphs should share some common structures or properties. For instance, when two graphs are in the same class, their orthonormal representations should be similar and the Lovasz numbers of them or their subgraphs are similar [Johansson et al., 2014].  Therefore, it is expected that a sufficiently large neural network is able to learn the intrinsic structure from the training graphs and then solve the optimization related to the orthonormal representation and handle vector in an end-to-end manner. The idea is similar to the general idea of learning to optimize [Li and Malik ICLR 2017; Chen et al. JMLR 2022]. Please also refer to our response to Q4 of Reviewer 2QoV.\n\n* Although in our paper we only reported the results given by the regularized optimization, we actually have found that the performances are similar to the constrained optimization (solved by projected update or exact penalty method). Moreover, in the ablation study of the supplementary material, we can see that the method is not very sensitive to the penalty parameter $\\mu$. This is due to the good quality of the handle vector, though not the exact solution. In addition, the node features are indeed useful though  Eq. (2) is not related to the node features.\n\nWe define the following metric:\n$r = \\frac{|\\hat{\\vartheta(G)} - \\vartheta(G)|}{\\vartheta(G)}$\n\nWe have the following results (see our response to Reviewer 2QoV). The estimation errors are less than 10% in almost all cases.\n\\begin{matrix}\n\\hline\n  r& \\text{MUTAG} &  \\text{PROTEINS} &  \\text{DD} & \\text{NCI1}  \\\\\\\\  \\hline\n regularized\\ opt.  &  0.097\\pm 0.034   & 0.082\\pm 0.021  &0.063\\pm 0.011 &0.102\\pm 0.036  \\\\\\\\\n constrained\\ opt.  &  0.065\\pm 0.024   &0.073\\pm 0.016   &0.061\\pm 0.012 & 0.085\\pm 0.023 \\\\\\\\\n \\hline\n\\end{matrix}\n\n* The bad performance of the Lovasz number in Table 1 stems from the fact that the orthonormal representation and handle vector for a graph is not unique, which was explained in lines 149-157 in the main paper. Thus, even if two graphs are exactly the same, the solver for (2) may provide two very different handle vectors, which leads to bad performance in downstream tasks.\n\n* In our Lovasz principle, because of using neural network and the end-to-end formulation, the orthogonal representation and handle vector  of each graph are unique and rotation-invariant. That's why it is much better than the Lovasz number in Table 1. By the way, in our Lovasz principle, the end-to-end formulation learned the distribution information of the $N$ graphs successfully, while solving the Lovasz number for each graph by a solver independently failed to learn the distribution information.\n\n\n**Clarity issues and inadequate justification...**\n\n* Yes. We have provided a solution in the response to Reviewer JpeL. Besides this projection-based strategy, we can use the exact penalty method, i.e., increasing $\\mu$ gradually, which is a common strategy for constrained optimization.\n\n* The InfoGraph method used two encoders (see Eq. (17)) for the semi-supervised learning and the works (GraphCL, AD-GCL, JOAO, AutoGCL, etc.) followed the convention.  To ensure a fair comparison, we considered two encoders in our work.  \n\n* -----\n   * The optimization related to (14) is not a bi-level optimization. In each iteration $t$, the objective function is (14) and the parameters are updated by a mini-batch optimization. We can just regard the $K_{ij}^{(t-1)}$ in (13) as a constant not related to the network parameters, so the optimization problem changes in every iteration. The idea is very similar to that of the iteratively reweighted least squares. We will provide more explanation in the revision.\n   * We follow the implementation code of the Lovasz kernel [Joh+14] in the Grakel framework [1]. When dealing with large-size graphs, Grakel [1] selects subgraphs of sizes 3, 4, and 5, while excluding others. This is their code implementation for achieving a well-approximated Lovasz kernel using samples as in [Joh+14, Theorem 1].--------[1] Grakel \\url{https://ysig.github.io/GraKeL/0.1a8/kernels/lovasz_theta.html}\n   * The orthogonality of the handle vectors and the last term (sum to 1) are constraints of spectral embedding [2,3].\n[2] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. \n[3] \\url{https://perso.telecom-paristech.fr/bonald/documents/spectral.pdf}\n\n\n**Experiments**\n\n* The loss behavior is reported in the attached PDF file.\n\n* We will provide more details about the experimental setting of transfer learning.\n\n* The performance is indeed not sensitive to $\\mu$ if it is in the range of $[0.1,1000]$. When $\\mu$ is too large, the learned Lovasz number is quite different from the one given by a solver. \n\n* Yes, in some cases, the orthonormality constrainn reduced the accuracy. One possible reason is that the baseline method on a specific dataset learned diverse features which lead to difficulties in making them orthonormal. \n\n* We reproduced the results of the baselines and found that they are very close to the results reported in the original paper. Therefore, we just report the original results of the authors in the tables. This convention has been followed by previous works such as  [Hu et al., 2019; You et al., 2021; Yin et al., 2022]. It should be pointed that for our methods, based on the codes released by [You et al., 2021; Yin et al., 2022], we just replaced the Infomax principle by our Lovasz principle, without changing any structure or optimization parameter in the original codes. Therefore, the comparison is fair.\n\n**Minor issues**\n\nWe thank the reviewer's detailed comments again and we will address these minor issues in the revised paper.\n\n\n"}, {"review_id": "KleA74cjIE", "reviewer": "Reviewer_2QoV", "summary": "The paper introduces the \"Lovasz Principle\", an unsupervised or semi-supervised graph representation learning approach inspired by the Lovasz number. The motivation for using the Lovasz Principle is well established, and the authors extensively discuss related work and similar approaches. The experimental setup is sound, and the Lovasz Principle is tested against many widely used graph representation learners, with better results in all experiments.\n", "questions": "- While Figure 1 and the description for the pentagon example are great, I was slightly confused when I initially read the part regarding the orthogonal vector pairs. This is because I've read $(u_i*, u_j*)$ as being a vector, not a pair. It would be great if the authors somehow clarified the intuition about the orthogonality.\n\n- I assume that $\\odot$ in Eq. 8 is the Hadamard product? It would be nice to state this somewhere explicitly.\n\n- The authors mention obtaining node-level representations via the $F(\\cdot, \\cdot, \\theta)$ function but are tackling only graph-level tasks. Have you tried node-level tasks? It would be interesting to see the approach tested on them.\n\n- Have you tried assessing if $\\mathcal{F}_W$ is a good approximator for $(U_i*, c_i*)$? Maybe the formulation helps only in a representation-learning sense and doesn't produce a good approximator.\n\n- Will the code be publicly available? I will update my score accordingly if this is the case.", "limitations": "- The Lovasz Principle adds some new hyperparameters that could affect the final performance if not correctly chosen. The authors have included an extensive discussion regarding this in the Supplementary to the paper, but I believe this should also be mentioned in the main paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and easy to follow, with compelling arguments and intuitive explanations.\n\n- The steps taken to derive the Lovasz Principle are well laid on. \n\n- The experimental setup is sound and contains many different approaches to graph representation learning. Variants of the Lovasz Principle consistently obtain the best scores on all datasets. I appreciate the inclusion of Figure 2 for a quick visual summary.\n\n- Compared to InfoMax, the Lovasz Principle is simpler because it does not require a discriminator for the Jensen-Shannon MI estimator. The Lovasz Principle also has a faster runtime.\n", "weaknesses": "- The authors discuss the non-uniqueness of $U_i*$ and $c_i*$ and give some intuition regarding why this is the case, but mention that they \"hope that similar graphs have similar representations\". It would be interesting and make the argument more compelling if the authors computed $c*$ for various \"similar\" and \"different\" graphs and showed empirically that they are indeed similar or different.\n\n- Similarly, it would be interesting if the authors empirically showed that $\\mathcal{F}_W$ is actually a good approximator for $(U_i*, c_i*)$ by comparing them with $\\mathcal{A}(G_i)$, where $\\mathcal{A}$ is some solver.\n\n\n- It would make the paper more readable if the authors moved the footnote from page 4 to the caption of Tab. 1.\n\n- I appreciate that the authors go into great detail regarding hyperparameter sensitivity in the Supplementary material, but they don't mention the effect of the hyperparameters in the main paper. The reader should be aware that hyperparameters can significantly affect the final performance, and one should consider this when using the Lovasz Principle.\n\n- I could not find any code provided by the authors for reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1: Handle vector comparison between \"similar\" and \"different\" graphs**\n\n**Response:** Given two graph sets $\\mathcal{S}_ 1$ and $\\mathcal{S}_ 2$, we denote $c_ i$ as the handle vector for $G_ i$, $i=1,2$. We define the following cross-set difference: \n\n$\\ell_ {c}(\\mathcal{S}_ 1, \\mathcal{S}_ 2) =  \\frac{1}{|\\mathcal{S}_ 1| \\times |\\mathcal{S}_ 2|} \\sum_{G_ i \\in \\mathcal{S}_ 1, G_ j \\in \\mathcal{S}_ 2} \\Vert z_ i - z_ j \\Vert_ 2^2.$\n\nGiven a graph dataset $\\mathcal{G}$, it is natural to assume that the graphs in the same class are \"similar\" and graphs in the different class are \"different\". Then we select $\\mathcal{S}_1$ and $\\mathcal{S}_2$ from the first class of $\\mathcal{G}$ where $\\mathcal{S}_1 \\cap \\mathcal{S}_2 = \\emptyset$. $\\mathcal{S}_3$ is selected from the second class of $\\mathcal{G}$. We use InfoGraph as our GNN framework by substituting its InfoMax loss with the Lovasz loss Eqn. (9). For each dataset, we select 30 graphs for each subset. We repeat the experiment10 times and report the results as follows:\n\n\\begin{matrix}\n\\hline\n Difference & MUTAG &  PROTEINS &  DD & NCI1  \\\\\\\\     \\hline\n \\ell_{c}(\\mathcal{S}_ 1, \\mathcal{S}_ 2) &  0.24\\pm 0.13   & 0.27 \\pm 0.08  &0.23 \\pm 0.10 &0.26 \\pm 0.12  \\\\\\\\\n\\ell_{c}(\\mathcal{S}_ 1, \\mathcal{S}_ 3) &  0.31\\pm 0.16   & 0.33 \\pm 0.11  &0.28 \\pm 0.15 &0.35 \\pm 0.17  \\\\\\\\ \\hline\n\\end{matrix}\n\nThe results show that the handle vector of \"similar\" graphs are close, while that of \"different\" graphs are different. \n\n**Weakness 2: $\\mathcal{F}_W$ vs $\\mathcal{A}(G)$**\n\n**Response: please refer to our response to your Question 4.**\n\n**Question 1: intuition about orthogonality**\n\n**Response:**  In [1], a coding source with symbols is represented as a graph $G = (V, E)$, where each vertex represents one symbol. If the symbols of vertex $i$ and vertex $j$ share some information in common, these two symbols are probably confused in coding a message. This confusable relationship is represented as an edge between vertex $i$ and vertex $j$. Laszlo Lovasz proposed to represent the information of a coding symbol as an orthonormal vector. If vertex $i$ and vertex $j$ are not adjacent, that means they share no information in common, and thus their vector representations $v_i$ and $v_j$ should be orthogonal to each other, thus $v_i^\\top v_j = 0$. That is the intuition about the orthogonality, which is derived from the information theory view.\n\n[1] László Lovász. On the Shannon capacity of a graph\n\n**Question 2:** $\\odot$ is a Hadamard product**. \n\n**Response:** Yes. Will state it explicitly. \n\n**Qeustion 3: Lovasz principle for Node-level tasks**\n\n**Response:** Yes. Our Lovasz principle can also be applied to node-level tasks but may not provide very good results. The reason is that Lovasz principle aims to learn the global representation of graphs and may not provide discriminative representations for individual nodes.  Here we apply Lovasz principle to GCN and then evaluate the node-level representations in the edge prediction task, comparing with VGAE[2]. We report the AUC scores as follows.\n\n\\begin{matrix}\n\\hline\n  Method & Cora &  Citeseer &  Pubme   \\\\\\\\     \\hline\n VGAE    &  91.4\\pm 0.01   & 90.8\\pm 0.02  &94.4\\pm0.02   \\\\\\\\\n Lovasz  &  84.3\\pm 0.24   & 83.1\\pm 0.96  &87.2\\pm0.37 \\\\\\\\\n \\hline\n\\end{matrix}\n\nVGAE outperformed the Lovasz principle. Nevertheless, if we convert the node-level tasks to subgraph tasks, i.e., representing each node by a small (local) subgraph containing the node, we may obtain better results for Lovasz principle. We will add more discussion about the application to node-level tasks in the supplementary material.\n\n[2] Kipf T N, Welling M. Variational graph auto-encoders[J]. \n   \n\n**Question 4: Quality of solver Approximation**\n\n**Response:** Solving for the Lovasz number is a problem with the computation complexity of $O(n^3)$, which can be learned by a GNN with sufficient capacity.\n\nGiven a GNN model $\\mathcal{F}_W$ trained via the Lovasz principle, the predicted Lovasz number is defined as \n\n$\\hat{\\vartheta}(G) = \\max_ {p \\in V} \\frac{1}{(\\hat{z}^\\top \\hat{h} _ p)^2}, ~~\\text{with} ~~(\\hat{z}, \\hat{H}) = \\mathcal{F} _ W(G)$.\n\nThe ground truth Lovasz number of $G$ is denoted as $\\vartheta(G)$, which can be computed by the optimization method in [3]. We define an evaluation metric as \n\n$r = \\frac{|\\hat{\\vartheta(G)} - \\vartheta(G)|}{\\vartheta(G)}$\n\n[3] Wen Z, Yin W. A feasible method for optimization with orthogonality constraints[J].\n\nWe use InfoGraph as our GNN $\\mathcal{F}_W$ by substituting its InfoMax loss with the Lovasz loss.\nWe also propose a constrained optimization method in the **Concern about the regularization approximation instead of exact constraints** part of the rebuttal for Reviewer JpeL [4].\n\n[4]Reviewer JpeL: \\url{https://openreview.net/forum?id=0vdEHDwamk&noteId=J2z1RvNm3g}\n\nWe select 50 graphs from four dataset and reported the Lovasz number regression rate $r$ for both the regularized ($\\mu = 10$) optimization and the constrained optimization for Lovasz principle as follows.\n\n\\begin{matrix}\n\\hline\n  r& \\text{MUTAG} &  \\text{PROTEINS} &  \\text{DD} & \\text{NCI1}  \\\\\\\\  \\hline\n regularized\\ opt.  &  0.097\\pm 0.034   & 0.082\\pm 0.021  &0.063\\pm 0.011 &0.102\\pm 0.036  \\\\\\\\\n constrained\\ opt.  &  0.065\\pm 0.024   &0.073\\pm 0.016   &0.061\\pm 0.012 & 0.085\\pm 0.023 \\\\\\\\\n \\hline\n\\end{matrix}\n\nWe see that the estimation errors given by $\\mathcal{F}_W$ $ are less than 10% in almost all cases. The constrained optimization method [3] performs better than the regularized optimization.\n\n**Question 5: Will the code be publicly available?** \n\n**Response:** Sure, we will make all of our codes publicly available. We will upload the codes to Github. Actually,  our Lovasz principle is a loss that can be used by almost all GNN methods. \n\n**Limitation**\n\n**Response:** We will move more results from the supplementary material to the main paper since NeurIPS allow adding an additional page in an accepted paper.\n\n"}]

Author rebuttal:
* We thank the area chair and all reviewers for processing our submission. We have provided detailed responses to every reviewer. In the revision, we will fix minor issues pointed out by the reviewers and improve the presentation of this work. We will also add a comprehensive description of the data statistics, parameter settings, and starting points for each dataset in the supplementary material. We will make all of our codes publicly available. 

* The attached PDF contains three figures: 
   1) the intuitive example of orthonormal representation and handle vector; 
   2) the flowchart (framework) of our method; 
   3) the iteration performance of the loss function and its terms.

* Here we briefly summarize a few key points of our rebuttal.
   1) For Reviewer JpeL as well as Reviewer JWhm and Reviewer 2QoV, we provide some experimental of comparison between regularized optimization and constrained optimization. The results showed that the solutions are close.
   2) For Reviewer JWhm and Reviewer 2QoV, we showed the learning ability of $\mathcal{F}_W$ for solving the Lovasz problem. We defined $r=\frac{|\vartheta(G)-\vartheta(G)|}{\vartheta(G)}$ to measure the quality of $\mathcal{F}_W$. The results showed the approximation error is less than 0.1 in almost all cases. This means $\mathcal{F}_W$ can indeed learn an end-to-end solver for the Lovasz problem.
   3) For Reviewer 2QoV, we defined a metric $\ell_c(\mathcal{S}_1,\mathcal{S}_2)$ to quantify the similar or dissimilarity between graphs in the same class or in different classes. The results showed that the handle vectors are effective in providing discriminative graph-level representations. 



Meta-review: The reviewers mostly liked the paper from the beginning. They mention that it adds a novel perspective, is theoretically founded, and demonstrates good empirical results. The rebuttal and discussion by and large resolved the remaining issues.
Decision: Accept (poster)