Extending Graph Condensation to Multi-Label Datasets: A Benchmark Study
Authors: Liangliang Zhang
Haoran Bao
Yao Ma
Venue: Accepted by TMLR ()

Abstract: As graph data grows increasingly complicated, training graph neural networks (GNNs) on large-scale datasets presents significant challenges, including computational resource constraints, data redundancy, and transmission inefficiencies. 
While existing graph condensation techniques have shown promise in addressing these issues, they are predominantly designed for single-label datasets, where each node is associated with a single class label. However, many real-world applications, such as social network analysis and bioinformatics, involve multi-label graph datasets, where one node can have various related labels. To deal with this problem, we extend traditional graph condensation approaches to accommodate multi-label datasets by introducing  modifications to synthetic dataset initialization and condensing optimization. Through experiments on eight real-world multi-label graph datasets, we prove the effectiveness of our method. In the experiment, the GCond framework, combined with K-Center initialization and binary cross-entropy loss (BCELoss), generally achieves the best performance. This benchmark for multi-label graph condensation not only enhances the scalability and efficiency of GNNs for multi-label graph data but also offers substantial benefits for diverse real-world applications.

Published in Transactions on Machine Learning Research (/)
Extending Graph Condensation to Multi-Label Datasets: A Benchmark Study
Liangliang Zhang Rensselaer Polytechnic Institute
shangl4 @rppi edu
Haoran Bao
baoh2@rpi.com edu
Rensselacr Polytechmic Institute
Yao Ma
may13arpp edu
Rensselaer Polytechnic Institute
Reviewed on OpenReview:
Abstract
As graph data grows increasingly complicated, training graph neural networks (GNNs) on large-scale datasets presents significant challenges, including computational resource con- straints, data redundancy, and transmission inefficiencies. While cxisting graph condensation techniques have shown promise in addressing these issues, they are predominantly designed for single-label datasets, where each node is associated with single class label. However, many real-world applications, such as social network analysis and bioinformatics, involve multi-label graph datasets, where one node can have various related labels. To deal with this problem, we extend traditional graph condensation approaches to accommodate multi-label datasets by introducing modifications synthetic dataset initialization and condensing optimization. Through experiments on eight real-world multi-label graph datasets, prove the effectiveness of our method. In the experiment, the GCond framework, combined with K- K-Center initial- ization and binary cross-entropy loss (BCELoss), generally achieves the best performance. This benchmark for multi-label graph condensation not only enhances the scalability and efficiency GNNs for multi-label graph data but also offers substantial benefits for diverse real-world applications. Code is available at lhtps:/ https://githuue //ggtggttbb.o.oo comm /oanm//iiaaiaan66 Saliiiannnvvoi/uiiiia /Muli-GG GC
1 Introduction
Graph-structured data fundamental to many real-world applications, including social networks, academic citation networks, chemical molecules, protein-protein interaction networks, mapping services, and product
vecommendation systems (Battaglia et al. 2018 Wu et al. 2020 Zhou et al. 2020 Wu et al. 2022 Tn these
graph structures, nodes represent entities (e.g., users in social networks), while edges represent relationships
between these entities (c.g., social connections between users) [Zhang et al. 2023
Graph Neural Networks (GNNs) are class of deep learning models specifically designed process and learn from graph-structured data. It utilizes the topology of the graph capture dependencies and learn meaningful nodes, edges, and graph-level representations. By extending deep learning to Euclidean domains, GNNs have achieved Seaate-ffttheartee performance in many graph machine learning applications
[hang et al. 2023 Hamilton et al.] 2018). ) For example, in the recommendation system [Li et al.] 2019 Mao
et al. 2021 Wu et al. 2022 Zhang et al.) 2019a), drug discoveries (Jiang el al. 2021 Zhang el al. 2021 D,
fraud account detection (Dou et al.) 2020 Wang et al. 2021) and traffic forecasting [Jiang & Luo 2022
GNNs combine the node features and structure of graph as the input and output the representations of
graph information (Hamilton al. 2018 Velickovic al. (2077). Among all the GNNs techniques, the most
broadly followed methods is recursive neighborhood aggregation scheme, which aims to get the represent ation

---

Published in Transactions on Machine Learning Research (/)
of each node, respectively (Xu et al. pooling methods, GNNs are capable of handling various of tasks like node classification (Xiao et al. 2022), 20110, and graph classification (Zhang et al. 2018
2018 By applying different neighborhood aggregation and graph-level
link prediction (Hasan & Zaki
Even though GNNs Zhang et al. 2023 2019b) are widely used for analyzing graphs, training these models on
large-scale graphs still computationalyy expensive (Gao et al. 2018 Bojchevski et al., 2020). Furthermore, nowadays, graph data is becoming gigantic with numerous nodes and edges in a single graph (Zhang et al, 2023). For example, the Twitter user graph has 288M monthly active users as of 3/2015 and estimated average of 208 followers per user for an estimated total of 60B followers (edges) (Ching et al. 2015 Such industry graphs can be two orders of magnitude larger, like hundreds of billions or up to one trillion edgos. In other words, the complexity and large scale of graph data pose significant challenges for training GNin let al. 2022b). Despite the scalability challenges, for some specific applications that need re-training multiple times models would encounter more hardships rather than computation cost.
To address these large-scale datasets challenges, graph condensation methods recently (Xu et al. 2024: Gao
et al. 2024) have gained lots of attention. Graph condensation is motivated by condensing large graph dataset into smaller informative synthetic graph, thereby enhancing the scalability and efficiency of GNNs
[Xu et al. 2024 Gao et al. 2024; Hashemi et al.) 2024). The goal is to achieve comparable performance in GNNs using this synthetic small graph, instead of relying on the original large-scale graph (Loukas] 2018 Jin et al. 2022a).. By doing so, condensed synthetic graph enables GNNs to maintain strong predictive performance while significantly reducing the computational resources required for tasks such as training and inference. By eliminating redundant information in original dataset, it makes the synthetic graph more manageable within the constraints of limited computation resources, thereby providing better support for graph data mining tasks and applications such as Continual learning (Liu et al. 2023), Network Architecture Search (NAS) (Gao et al., 2021 etc. Moreover, take node classification task as an example, the node can be well classified is because GNNs have learned to capture the unique pattern of nodes to distinguish them from other nodes in diffcrent classes.
Gao et al. 2024 explore diverse strategies such as gradient distance matching (Jin et al., 2022b Yang et al. 2023). trajectory matching (Zheng et al.) 2024 Zhang et al. 2024 kernel ridge regression (Xu et al. 2023 Wang et al. 2024). and distribution matching
Existing graph condensation methods (Xu et al. 2024
Liu el al. 2022 2023) However, in many real-world applications, nodes are often associated with multiple labels (Huang & Zhou 2012 Read et al. 2011]. For example, users in social networks may belong to multiple groups reflecting diverse interests, articles in citation networks can span multiple research topics, and proteins in biological networks may participate in various processes, such as molecular activities or cellular functions
(Shi et al.] 2019 Akujuobi et al., 2019 Zeng et al. 2019). Nodes in multi-label graphs not only possess features, but are also associated with multiple overlapping class labels (Shi et al., 2019 2020 Akujuobi et al. 2019 Zhao et al., 2023 ). Existing graph condensation methods are designed for single-label settings.
Directly applying labele-label methods to multi-labe datasets leads to the loss of critical label interaction
and distribution information, as the underlying wlass-wise for single label assumption does not hold.
To bridge this gap from single-label to multi-label setting, in this work, we adapt available graph condensation techniques to the mainstream multi-label datasets. Our approach includes modifications to the synthetic datasct initialization and original datasets condensation matching stages. By evaluating various adaptation settings, we identify three key insights into the optimal combination of initialization and optimization methods. Using these best settings, we further analyze graph condensation models and present three additional observations, highlighting the unique challenges of condensing multi-label graph datasets. Our contributions are as follows:
1.
We extend classic SOTA graph condensation methods, including GCond, GCDM, and SGDD, to the multi-label graph dataset scenario by introducing multi-label synthetic dataset initialization and condensing optimization mothods.
To find the best adaption strategics, we compare different initialization techniques such as Random sampling, Herding, K-Center and probability synthetic multi-label combine with two different multi-label loss functions- Soft.argin and BCELoss.
2

---

Published in Transactions on Machine Learning Research (/)
3. With the best adaption settings, we evaluate the condensation methods with F1-micro and F1-macro scores on eight real-world multi-label datasets: PPI, PPI-large, Yelp, DBLP, PCG, HumanGo, EukaryoteGo, and OGBN-Proteins. Finally, we find the GCond method generally works best with K-Center initialization and BCELoss.
2 Related Work
2.1
Graph Neural Networks
Graph Neural Networks (GNNs) are class of deep learning models specifically designed to process and learn graph-structured data. GNNs have achieved outstanding performance in many applications Zhang For instance, in the recommendation system on social network Li et al,
from
et al.
2023
Hamilton et al. 2018
2019
Mao ct al. 2021 Wu al.
2022 Zhang et al. 2019a). drug discoverics from molecule graphs (Jiang
et al.
2021
Duvenaud al.,
2015
Zhang al.) 2021). fraud account detection on financial graphs (Dou
et al.
2020
Wang et al. 2021 and traffic forecasting in transportation graph (Jiang & Luo 2022
GNNs combine the node features and structure of graph as the input and output the representations of graph Hamilton et al. 2018 Velickovic et al. 2017 Kipf & Welling 2016). Among all the GNNs techniques, they
broadly follow a recursive neighborhood aggregation scheme to get the representation of each node (Xu et al.
2018 Some of the typical GNNs models like the Graph Convolutional Network (GCN) (Kipf & Welling
2016) operate by aggregating and transforming information from neighboring nodes layer by layer. Variants like Graph Attenstion Nesworks (GAT)) (Velickovic et al. 2017) use attention mechanisms to prioritize certain neighbors, while GraphSAGE (Hamilton et al.) 2017 samples neighborhoods to scale to large graphs. By applying different neighborhood aggregation and graph-level pooling methods, GNNs are capable of handling various of tasks (Xiao et al.) 2022 Hasan & Zaki 2011 Zhang et al. 2018) like node classification, link prodiction, and graph classification.
2.2 Multi-Label Classification on Graphs
Multi-label classification on graphs (Zhao al. 2023 is fundamental task in graph machine learning, where nodes in graph are associated with multiple labels simultancously. This task is critical in numerous real-world applications, including social networks, bioinformatics, and recommendation systems. For instance, in social networks, users may belong to multiple interest groups, while in bioinformatics, proteins may participate in multiple biological processes such as molecular functions and cellular activitics (Huang & Zhou, 2012 Read et al. 2011 Shi et al. 2019 Akujuobi et al. 2019). In multi-label classification, the goal is to predict a set of labels for each data point in the dataset. The labels can be thought, of as binary variables, where label is either present (1) or absent (0). Recently, there have been several approaches that use neural networks for multi-label classification.
Traditional multi-label classification methods relied on adapting single-label classification techniques to multi-label scenarios. Popular strategies include problem transformation methods (e.g,, binary relevance and classifier chains) and algorithm adaptation approaches, which extend existing classifiers to handle multiple labels directly (Read et al. 2011 Tsoumakas Katakis 2008). These approaches use architectures such as recurrent neural networks (RNNs) and convolutional neural networks (CNNs) learn representations of the input data and make predictions for the labels. However, these approaches were not designed to exploit the graph structure and are therefore suboptimal for graph data.
With the advent of GNNs, rescarchers began exploring multi-label classification directly on graph-structured data. GNNs excel in capturing the relational and lopological information of graphs, making them well-suited for multi-label classification tasks. For example, GraphSAGE (Hamilton et al., 2017) and GAT (Velickovic ct al. (017)) utilize noighborhood aggregation to generate node embeddings, which can be fod into multi-label classifiers. Specialized models like ML-GCN (Chen et al.) 2019) integrate graph convolutional layers with multi-label prediction heads to improve performance multi-label datasets.
3

---

Published in Transactions on Machine Learning Research (/)
2.3 Graph Condensation
Despite the impressive performance of GNN models, training them large-scale datasets is often challenging due to high computational costs, especially when retraining or dealing with redundant information. To address these issues, graph condensation techniques have been developed. These methods distill large-scale graph into a smaller yet informative synthetic graph, improving the scalability and efficiency of GNNs (Xu et al., 2024 Gao et al. 2024 Hashemi et al. 2024). The condensation process generates compact representation that preserves essential topological and feature-basod properties from the original graph (Loukas) 2018 Jin al. 2022a). This allows GNNs to achieve comparable performance using the condensed graph while significantly reducing the computational resources needed for training and inference.
Existing graph condensation works (Xu et al. 2024 Gao et al. including gradient distance malching(Ji Jin et al. 2022b Yang et al. 2023 Irajectory matching matching(Zheng et. al.
2024 investigate different condensing strategics
2024 Zhang et al.) 2024], kernel ridge regression Xu et al. 2023
Wang et al. 2024). and distribution matching(Liu ct al. 2022 2023). Condensed graphs facilitate more efficient model exccution without sacrificing the quality of learning, making this technique promising method for real-world GNN deployments. By eliminating redundant information in original dataset, graph condensation makes the synthetic graph more manageable within the constraints of limited computation resources, thereby providing better support for graph data mining tasks and applications such as Continual learning (Liu et al., 2023) and Network Architecture Search (NAS) et al.) 2021). etc. Moreover, take node classification as an example, the reason a node can be well classified is that GNNs have learned to capture the unique pattern nodes to distinguish them from other nodes in different classes.
3 Problem Formulation
Original Graph (4,
Synthetic Graph (A', XX
X
X'
AA
Train
GNNo;
A,1
Update
M MGNNNo GNNes)
A'
Train
GNNa;
Y'
lodelaael
Figure 1: Workflow for multi-label graph condensation. shows the process condensing a large multi-label graph G {A, Y into a smaller synthetic graph S {A',, X', Y'), where Y and represent the multi- label matrix. Various matching strategies, denoted by .M((), are employed in the original graph is captured. Our goal is to use the synthetic graph S to train GNN that achieves comparable performance to the one trained the original graph G, thus reducing graph size while retaining performance.
ensure that key information
Consider graph G= (A, where N is the number of nodes, A E NNN is the corresponding adjacency matrix, X = {21, AN } E Nxx is the d-dimensional node fcature matrix. In multi-label scenario, each node is associated with multiple labels revealing characteristics or semantics of the node. In this case, the label matrix can be represented as Y e {v1, v2.-.. .NN } e {0, 1 where K the number of classes. Following the definition graph condensation, our goal is to learn a smaller synthetic graph denoted S, which can contain the ability to train downstream tasks' GNNs and achieve competitive performance compared with the original large-scale complex graph G. Similarly, the synthetic graph be denoted
4

---

Published in Transactions on Machine Learning Research (/)
S = (A',X', along with A' R'''', and X' E R Y' {0,1) During this stage, expectation is that the scale of the synthetic graph can be much smaller compared with the original graph, denotes as N' N.
In this work, we adapt the graph condensation techniques to a multi-label setting, trying to get the synthetic multi-label graph. First, we introduce the general framework graph condensation Figure | Generally, graph condensation methods are using different matching strategies optimize the synthetic graph similar to the original graph G. Despite these various strategies, the key point is to keep the comparable performance of GNNs while training small graph. Therefore, our objective can be formulated as follows 2022bb:
(Jin et al.
S = arg min M(O's 0g) s.t. 0 = arg min L(GNNN),
S
where GNN, denotes GNN paramcterized with 0. Specifically, 0s and 0g are the parameters trained graph S and G, respectively. M(.) is the matching strategy used to match the model 0'g trained synthetic graph S to the one 0g trained on the original graph g. L(-) is the loss function used to measure the difference between model predictions and ground truth. For most graph condensation methods, the loss function is cross-entropy loss.
As the specific initialization of model parameters 0 can lead the overfitting problem (Jin al. 2022b one common solution [Wang et al.) 2018) is to generate the synthetic data following distribution of random initializations of Po.. Furthermore, the reformulated optimization problem follows:
S arg min Ee,-ro, [M((') 02)
(2)
s.t. 0" = arg min L(GNV 8(0a)
where (0)) indicates is a function acting on Og-
4 Graph Condensation Methods
Building on the global understanding of existing single-label graph condensation methods, we observe that while different graph condensation methods differ primarily their matching strategies, the overall workflow remains largely consistent. Therefore, before adapting these methods the multi-label scenario, we will illustrate the different matching strategies of condensation methods first.
4.1 GCond: Gradient Matching
By computing the gradient of L w.r.t. S and optimize S via gradient descent. For each training step, the opta is the update rule, consider the onc-step gradient descent for model paramcters:
05 + 0.5 - VVLLGGN 05 (A', X'),)))
(3)
- - g5 VVVLLGNN Y)
where of and o denote the model parameters trained on S and g at step t. is the learning rate for the gradient descent.
By matching the training gradient trajectory, define distance function D(,:), define the gradient matching strategy MGCond as:
MaCond D(VoLGGNN of (A',X),, X'),Y) VoL(GNN (A, X),))
(4)
Assume T is the number of steps of the whole training, the final optimized objective is:
S = arg min Eg P
D(VoLIGNN (A', (A',
(5)
t=0
og (A, V))]
5

---

Published in Transactions on Machine Learning Research (/)
Direct joint learning can be highly challenging because the three variables A', X' and Y' in synthetic graph are interdependent. One straightforward way is to treat A' and X' as free parameters. By modeling the synthetic graph structure as a function of the condensed node features, synthetic graph structure A' can be learned by:
=' ==)o(X')
(6)
where ø is the parameter of multi-layer neural network. So the rewrite objective is:
T-1
S = arg min Ee X
oF X'), Y"),
Pog
(7)
(A.
4.2 SGDD: Structure- Brracture-rooadcasting
Instead of treating A' and X' in the synthetic graph S as free parameters, Yang et al. 2023 this way ignores the original structure A in g. To address this problem, they broadcast as supervision for the generation of A'. By introducing graph on (Gao & Caines 2019 Ruiz et al.] 2020 Xia et al. 2023 matching the different shapes between A and A', SGDD use random noise ((N) E RX'N" input coordinates. Through the generative model to synthesize adjacency matrix A' with N' nodes, the process can be formulated as:
points out that
A' = GEN()(N");
(8)
where GEN(-) the gencrative model with parameter Then the structure optimization is:
Mstructure = Dis(A, GEN(()))
where A is supervision and Dis(.) is a metric that measure the difference between A and A'. By adding the corresponding nodes information from X' and Y' to the inherent relation learning (Pfeiffer III et al.) 2014 Shalizi & Thomas 2017), the revised generation model GZN( @ X' ) Y @ denotes the concatenate operation. In general, SGDD concurrently optimizes the parameters X' and A'. While the refinement of X' is achieved through gradient matching stralegy, whereas the A' is enhanced using the Laplacian energy costribution(LED) matching technique (Tang et al. 2022 Das et al. 2016 Gutman & Zhou 2006). During cach step, the other component is frozen to ensure effective refinement, and the overall training loss function can be summarizzd as:
MsGDD = MaCond + aMstrnature + B||A|12
(10)
where ||A||/ is proposed as sparsity regularization term, and 3 are trade-off parameters.
4.3 GCDM: Distribution Matching
Inspired by the distribution matching strategy in image dataset condensation (Zhao & Bilen 2023). (Lu et al. 2022 adapt the receptive field distribution matching method in GNN, In the graph dataset, with the reproducinf kernal Hilbert space H defined by GNNs and with in each class k, GCDM optmize the maximum mean discrepancy (MMD). Let D be an L-layer GNN model parameterized by 8, the loss of GCDM is:
MGCDM min
max 0.
emb;
Σ
emb
(11)
0.X"
Vk veVi
VE
k=
JEV
2
where the node embeddings are:
{emb; N1 + Do. (A, 1==0
(12)
1 {emb]] |
N' + Db_
(X').
(13)
V& and V/ represent the node sets belong the class is of original graph & and synthetic graph S, respectively. K is the number of multi-label classes. denotes the condensed ratio of the synthetic graph.

---

Published in Transactions on Machine Learning Research (/)
5 Datasets and Experiment Settings
In this section, we first present the multi-label graph datasets used in our benchmark investigation, accompanied by the detailed introduction of label information in real-world application. Next, we detail the evaluation metrics used to assess the effectiveness of the adaptation methods, providing à robust framework for performance comparison.
Datasets. Specifically, we employ eight real-world datasets including PPT Zeng al. 2019:
PPr-large
ZZng al. 2019)
ZZng al. 2019), DBLP (Akujuobi al. 2019 OGIN--Proteins (Hu al. 2020
PCG Zhao et al. )023), HumanGo Chou & Shen 2007 Liberzon al. 2015 EukaryoteGo (Chou & Shen
2007
Liberzon et al. 2015). The details of those datasets are introduced in Appendix A
We follow the predefined data splits from (Zeng et al. 2019 Zhao & Bilen
2023
Hu ct al.
2020
Chou &
Shen
2007
presents an overview of the datasets' characleristics.
Table 1: Multi-Label Graph Dataset Statistics
Dataset
# NNodes
#Edges
# Avg. Edges
#Features
#Labels
Train Train/Val/Tin Val/Test Test
PPI
14,755
225,270
15.27
50
121
0.66/0.12/0.22
PPI-large
56,944
818,716
14.38
50
121
0.79/0.11/0.10
Yelp
716,847
6,977,410
9.73
300
100
0.75/0.10/0.11
DBLP
28,702
68,335
2.38
300
4
0.60/0.20 /0.20
OGBN-Proteins
132,000
39,000,000
295.45
8
112
0.66/0.16/0.18
PCG
3,233
37,351
11.55
32
0.60/0.20/0.20
HumanGo 3,106
18,496
5.96
32
14
0.60/0.00/0.40
EukaryoteGo 7,766
13,818
1.78
32
22
0.60/0.00/0.40
After introduce the single-label graph condensation methods, we will focus adjusting key components to fit the multi-label task while preserving the core matching mechanisms. This ensures that our framework can be extended to other existing graph condensation techniques, allowing for flexible and efficient adaptation across different methods.
This benchmark presents a thorough evaluation of the various set settings and methods used for graph condensa tion in the multi-label scenario. To evaluate the performance of adapted graph condensation methods, we utilize two widely recognized metrics in multi-label classification: F1-micro and F1-macro (Lipton et al.] 2014). The calculation details are listed in Appendix A We structure the benchnark results into three key parts: (1) identifying the best initialization and loss function settings, (2) comparing the full results of all graph condensation methods across multiple datasets, and (3) analyzing the results through multi-label class distribution and label correlation.
6 Adapt Existing Graph Condensation Methods for Multi-label Datasets
After the introduction of different graph condensation methods based on the matching strategies in Section including GCond, SGDD and GCDM, we apply the above methods in multi-label graph datasets in this section. However, these methods could not directly be applied to condense multi-label graphs majorly due to two reasons: (1) The synthetic graph initialization is designed for single-class augmentation with pre-defined condensed labels. (2) The condensation methods depend on GNNs to match the original graph G and synthetic graph S, the classification ion objectives are designed for single-label node classification. Therefore, in this section, we would like to adapt the existing graph condensation methods by investigating different adaptation strategics to address these two issues. In particular, we first describe the existing issues and the corresponding resolvents in Section 6.1 Then, we conduct experiments to investigate which strategies work best for the multi-label graph condensation tasks in Section 6.2

---

Published in Transactions on Machine Learning Research (/)
Random
Herding
K-Center
Datasets
C-rate
Probability
Whole Dataset
Subgraph
Nodes
Subgraph
Nodes
Subgraph
Nodes
PPI 1.00%
47.05
40.49
40.93
39.47
47.77
36.60
40.04
51.26
Yelp
0.02%
34.21
30.35
32.77
30.96
35.60
31.46
20.95
37.97
DBLP
0.80%
63.56
56.03
41.54
41.02
60.36
55.62
41.35
87.55
OGBN-Proteins
0.1%
14.12
15.41
11.62
15.36
29.95
24.81
15.53
18.86
PCG
4%
13.94
19.01
27.76
16.35
25.13
22.18
21.69
42.26
Table 2: F1-Micro Score (%) of Coreset Method with Different Initialization Strategies
Dutasets
C-rate
Without A'
Random
With A'
Without A'
Hording
With A'
Without A''
K-Center
With A''
Without A'
Probability
With A''
Whole Dataset
PPI
1.00%
35.39
48.315
51
Yelp
0.02%
30.16
29.53
-30.18
32.22
94.60
154.90
21.35
22.10
37.97
DELP
1%
52.10
87:48
45.95
47.12
02.56
00.77
48.24
48.50
87.55
OGBN-Proteins
0.30%
28.09
27.01
30.70
PCG
4%
20.50
23.70
22.14
25.38
19.88
22.36
22.07
27.21
42.26
Table 3: F1-Micro Score (%) of GCond Method with Random/ Handom/Herdiigg/ Ceerding/K-Centter//// LtKK///CContt/Pooaabiiilt Distribution Initialization with with/without without Learning from Structure for Soft MarginT.s..
6.1 Multi-label Adaptation
Most graph condensation methods, such as GCond, utilize batch sampling by class to optimize synthetic graphs. This involves initializing synthetic graph labels Y' based on predefined wlasswwise condensation rates r. To simplify computation and reduce memory usage, the loss of gradient matching typically calculated separately for nodes of different classes. Although this approach is effective for single-label graphs, where each node belongs to only one class, it encounters challenges in multi-label settings, where nodes are associated with multiple labels simultaneously.
One major challenge is in the classification of a single label graph, each node belongs to a specific class, which facilitates straightforward batch sampling in class. However, in multi-label graphs, nodes often have overlapping class memberships, complicating node partitioning for optimization while preserving the label's cooccurrence. Redundant node sampling worsens the problem by repeatedly including the same nodes in different subgraphs, which can bias certain label associations while ignoring others. It can undermine the integrity and representational accuracy of the synthelic graph. In multi-label graphs, the frequency of class in multi-label could be imbalance. Traditional sampling can worsen this, leading to poor representations for rare labels and distorting the original label distribution. Furthermore, single-label loss functions are not well-suited for multi-label scenarios. To ensure accurate gradient optimization and preserve the original multi-label structure, the loss function must effectively capture label dependencies.
To address these challenges, we explore various initialization and optimization methods to evaluate their impact preserving multi-label relationships and classification accuracy. Our focus is on two key areas: initialization and optimization of synthetic graphs, ensuring the essential multi-label features of the original graph are effectively captured.
Issue 1: Initialization of Synthetic Multi-Label Graph. In single-label settings, the condensed label yingle is predefined using ground- truth class distribution and retrieves X' randomly from each class.
As most of the graph condensation methods adapt Eq 5 to learn synthetic graph structure A' from node features X', one straightforward method for multi-label adaptation is sampling the nodes from original
Datasets
C-rate
Without
Random
With
Without
Herding
With
Without
K-Center
Without
Probability
With
Whole Dataset
PPI
1.00%
49.96
61.35
47.47
28.25
36.79
491.7
45.65
43.91
61.22 61::26
Yelp
0.02%
29.24
30.76
31.76
32.43
32.36
33.94
22.95
25.02
37.
DBLP
1%
46.87
48.50
64.21
70.74
87.35
OGBNeProteins
0.30%
26.65
28.88
21.45
26.21
21.78
27.11
PCG
4%
22.96
25.45
24.68
26.76
20.17
25.58
23.47
28.28
42.36
Table 4: F1-Micro Score (%) of GCond Method with
Tnitialization
with/without Learning from Structure for BCELoss.
8

---

Published in Transactions on Machine Learning Research (/)
datasets. Inspired by the heuristic sampling algorithms of baseline Coreset methods used in GCond, the sampled subgraph by different strategies can be used for the synthetic multi-label initialization to get a better performance.
As some of the coreset methods gain comparable performance as baseline [Weling 2009 Farahani & Hekmatfar 2009; Sener & Savarese 2017) we apply those heuristic algorithms to extract N' nodes from the full set of nodes obtain subgraphs 5' with corresponding condensation rates as the initialization methods.
Random selection is sampling the nodes randomly, probability of selecting node i is P()) N-
Herding (Welling) 2009 is more structured compared with random selection strategy. It is based on iterative minimization of the distance between the mean of the selected nodes' feature vectors and the mean of the entire graph feature vectors. Let [g present the mean feature vector of the original N'1 graph: Mg = * ΣN' 24 and Ps = N7 == z/j
K-Center Farahani & Hekmatfar 2009 Sener & Savarese, 2017) aims to maximize the coverage of the original graph feature space by minimizing the maximum distance between unselected nodes and their closest selected node. Let S = {51, $2,- , |NN' select nodes such that for every unsclected node i, the distance to the nearest selected node $j S is minimized: minl,,.-.,e ma, minjee(1..... |||, æegll2
be the selected node set. The goal is to
Probabilistic synthetic ensures the selected subgraph maintains the label distribution of the original graph. For each class k, we define the label distributtio as the fraction of nodes in the graph that belongs to class k: P& = - Em= Yi,k
Furthermore, the struct ure A' of hetthetii graph is optimized from nodes features X". Based on the researches (Ding et al.) 2022 Zhu et al., 2021 Jin et al. 2022b), this 'Graphless' learning process provides competitive results and facilitate various downstream tasks. To systematically evaluate the impact of this aspect, we clearly differentiate between 'node-only' initialization methods (which do not consider structural information) and 'subgraah--bsedd methods (which explicitly incorporate graph structure). By comparing these two categories throughout our experiments, identify the optimal settings for adapting graph condensation techniques to multi-label scenarios, thus enhancing coherence and readability in the subsequent discussion.
Issue 2: Optimization about Multi-Label Classification Loss.
In single-label settings, while the condensed graph is matched in various ways, the fixed label distribution can be used directly for synthetic graph initialization. With predefined synthetic label Y/ Yiinge E {0..... C 1 the synthetic node feature is randomly retrieved from the particular class. As calculate the matching loss for nodes from different classes separately,is casier than that from all classes. In other words, this single- label class-wise sample method will directly sample each class to optimize. Specifically, for given class c, it will sample batch of nodes of class e from original graph G with a portion of neighbors, denotes as (Ac: Xe, Y2) ~ G. For synthotic graph S, only sample the specific nodes of class c without the neighbors. By doing so, the synthetic graph will use all the other nodes for aggregation stages during condensation, similarly, this process can be wrote as (A', X Y2) ~ S. Further in terms of details, for each class c, there subset of nodes No that belong to this class. The loss computed class-wise, for example, the cross-entropy loss for single node j with ground truth label yj and predicted logit 2j,c for class is:
(CE(2).0)) log(
(14)
Σ Ec=0
C
The single-label final loss would be formulated as:
Esingle-label
Σ Σ (cE(2;,U)) == JeN.
(15)
However, in multi-label classification Y' E ....... ............ (yr E f0, 10.1) each node can associate with multiple classes simultaneously. Typically, the multi-label classification task is modeled as K independent binary

---

Published in Transactions on Machine Learning Research (/)
classification tasks, for each task k the model predicts logit 23 and ground-truth label Vy.k indicates whether node j belongs to class k. In multi-label classification, SoftMargin (Cao et al.) 2019 incorporates margin-based optimization, which is beneficial when dealing with imbalanced datasets and overlapping classes. In multi-label settings, cortain labels may frequently co-occur or exhibit correlations. SoftMarginL.os introduces a margin wetween positive and negalive label predictions, encouraging the model to differentiate between these labels more confidently.
Softmargin (2j,k, = log(1 + e e
(16)
This formulation is particularly useful in ensuring that the model not only predicts correct labels but does so with confidence, reducing the chances of ambignous prodictions near the decision boundary. On the other hand, Binary Cross-Entrop Loss (Durand et al. (019) is widely-used objective function for multi-label classification, it independently evaluates each label for each node in the graph. Then the task-wise loss for each binary classification task is computed using Binary Cross-Entre
(BCE) (Durand et al. 2019
loss:
(BCE(2 My,) = - (yy (z,(0(2))) + (1 Vj,k) log(1 - (z),,))),
(17)
where (22.k) 1/4 is the sigmoid function.
6.2 Experiments and Results Analysis
In this section, we investigate the effectiveness of various initialization and optimization strategies for multi- label graph condensation, aiming to determine the optimal settings. The results for characteristics of sampled subgraphs and additional metrics are provided in Appendix A We conduct experiments using GCond to assoss the impact of different initialization and optimization methods across representative datasets and their corresponding condensation rates. The condensation ratio (C-rate) is a critical measure in graph condensation, representing the fraction of the original graph retained in the condensed graph. For instance, with a C-rate of 1%, the synthetic graph S is only 1% of original graph G. We then perform statistical analysis the experimental results to compare the performance of different settings in multi-label graph condensation.
Settings. We select representative datasets for simplicity, using PPI as an example and testing its sottings (with PPI-large excluded). The C-rate determined based on the number of nodes in the synthetic graph. For instance, a 1.00% C-rate for PPI results in synthetic graph of 147 nodes compared the original 14,755 nodes. In general, synthetic graphs contain around 150 nodes. We evaluate different initialization strategies, including subgraph sampling methods (Random, Herding, K-Center), and probabilistic label sampling for syuthetic Y'. After initialization, the synthetic graph S is optimized using the gradienl matching stralegy in GCond.
Next, we compare optimization loss functions, including SoftMarginLoss (Cao et al. 2019 and BCELoss (Durand al. 2019), across various datasets with predefined condensation rales. These experiments aim to identify the optimal combination of initialization and loss function that balances graph size reduction and model performance in multi-label tasks.
Results and Analysis.
We evaluate the GCond framework under various multi-label settings, analyzing different initialization strategics and optimization methods with or without structure learning. Table 2 highlights F1-micro scores across subgraph and node-only settings, identifying strategies that best capture label distributions. Tables and compare optimization performance, while additional analysis examines the impact of structure information. Observing the experimental results, we draw three corresponding observation conclusions:
Observation 1: K-Center sampling achieves optimal initialization. K- K-Center sampling consistently delivers the highest F1-micro scores for dense, large-scale datascts (c.g., PPI, Yelp, OGBN-Protcins), as shown in Tables 2 g and 4 We believe K-Center sampling could cover the dataset's feature space more comprehensively by selecting a diverse set of nodes. This ensures better representation of all classes, including those that are underrepresented. In contrast, simpler strategics like Random and Herding, which focus less on diversity, perform better on sparser datasets (c.g., DBLP, PCG), where the feature space is less complex. Comparisons of Sort and BCELoss optimizations further reveal that K-Center initialization
10

---

Published in Transactions on Machine Learning Research (/)
achieves the best performance across loss functions, with or without graph structure learning. Notably, structure learning significantly enhances multi-label generalization in datasets like PPT and DBLP, showing its importance in improving performance.
Observation 2: Preserving graph structure could improves performance of condensed large datasets. Our analysis shows that incorporating graph structure information instead of relying solely on node attributes for label initialization leads significant performance improvements, especially in large- scale datasets. This is because preserving the structural information enables a more accurate modeling of relationships and dependencies among nodes, crucial for maintaining multi-label interactions. For example, as shown in Table 2 using K- K-Center sampling on PPI with condensation rate of 1.00%, preserving structure achieved an F1-mieeo score of 47.77% compared to 36.60% when using nodes alone. This trend persists during the condensation process, where incorporating structure learning (A') consistently enhances performance across various methods (sce Tables 3 and + These findings underscore the critical role of structural information in improving the effectiveness of condensed graphs.
Observation 3: BCELoss provides better overall results. BCELoss consistently outperforms Soft- MarginLoss in terms of Fl-micro scores, particularly when combined with structure learning. Theoretically, BCELoss could independently handle each label as a separate binary classification problem, thus better accommodating the non-mutually exclusive nature of labels in our case. For example, in the DBLP dataset, with K-Center sampling and structure learning, BCELoss achieves 70.74%, compared to 60.77% with Soft- MarginLoss (Table 4. K-Center sampling also proves effective across dense datasets like PPI, Yelp, and OGBN-Proteins while simpler methods such as Random and Herding perform relatively well on less dense datasets like DBLP and PCG but still fall short of K-Center. Preserving graph structure further enhances performance, seen in the PPI dataset, where K-Center sampling achieves 47.77% with structure learning compared to 36.60% without it (Table These patterns hold consistently across experiments, with BCELoss paired with K-Center initialization delivering the best results in most scenarios, regardless of structure learning. Notably, structure learning in advancing performance on datascts like PPI and DBLP, proves its effectiveness in condensation lasks. For additional comparisons and results, refer to Appendix A
Consistent with Observations and 2, initializing with K- K-Center sampling and incorporating structure learning A' could increase the performance of synthetic lulti-label graph. As shown in Observation 3, arcoss voriety of dalasels, BCELoss performs belter than SoftMuryinLoss. Parlicularly when paired with K-Center and structural learning, BCELoss improves the F1-micro score, suggesting it can offer greater label retention and general adaptability. Therefore, we adopt the K-Center and BCELoss as the initialization and optimization methods with structure information for multi-labed scenario.
7 Benchmarking
In this section, we adapt the discussed condensation methods the multi-label scenario using the optimal scttings outlined in Section 6. Table 5 compares corcset selection stratogics (Random, Herding, K-Center) and graph condensation methods (SGDD, GCDM, GCond) against the full dataset at different condensation rates. SGDD and GCond utilize gradient matching between GNNs trained on the original graph G and the synthetic graph S, while GCDM employs embedding matching based on nodes sharing the same class in the multi-label context. These results reveal key insights into the methods' effectiveness, dataset characteristics, and evaluation settings, with performance metries reported as F1-scores in decimal values.
GCond achieves the best results across datasets. GCond consistently outperforms other methods on most datasets, particularly excelling in large-scale datasets with substantial label complexity. On the PPI dataset, GCond achieves F1-micro and Fl-macro scores of 51.35% and 23.86%, respectively, at a 1.00% condensation rate. This robustness extends to PPI-large, where it achieves scores of 52.23% (F1-micro) and 28. 59% (F1-macro) at a 0.40% condensation rale. Similarly, on DBLP, GCond demonstrales its superiority with F1-micro and Fl-macro scores of 70.74% and 68 68,44, respectively, at 0.80% condensation, showcasing its ability to preserve label correlations and structural integrity during condensation. However, GCond's advantage diminishes in the Yelp dataset at high condensation levels, likely due to the datasct's unique label structure, which poses challenges for methods relying on label coherence preservation.
Observation 1:
11

---

Published in Transactions on Machine Learning Research (/)
Table 5: Graph Condensation Methods Performance Comparison. ' out-of-memory (OOM) errors.
Dutasei
Create
Flemiern
Usreact (Randon))
Fl-marmo
Fl-mdero
Lureass (Heeding)
Pl-maaro
Fl-mlem
Corcact (K-Conierr)
Fl-marro
Fl-mirro
SGDD
Flemarmo
Pl-miero
GCDM
Fl-mamm
Fl-mieeo
GCond
Flumbero
Whole Dutasee
Fl-marro
0.38%%
11:00
11:00
11:16
12:25
13:65
15:54
04.90
22.37
23.16
PPI
1.007%
30.07
47:43
47.02
47.07
23.76
30.00
PPL-lage
0.4075
61:01
13:71
01.0
13.05
59.00
11.06
16:15
52.23
28.59
0.01%
15.73
3.50
34.20
13.30
1.28
75.40
7.51
0.027
58.64
0.00
12.54
1.06
36.04
12.30
27.54
3.70
13.34
0.22
Yelp
0.00%
0.0-1%
36:00
58.74
3:41
0.80
32.57
33.50
0.17
8.67
36.62
36.51
12:51
11:30
24.10
26.12
2.42
2.87
32.77
34.
0.56
5.85
32
15.15
0.107
58.56
5.19
33.55
01.1
36.00 65
0.70
24.50
2.55
33,70
6.17
0.20%
T3
0.30
33.20
4.71
37.81
11.48
25.05 63
3.322
12.43
12.09
0.20%
00:25
34.51
01:02
13:41
02.09
23.75
$4.41
35.84
63.55
54.27
DBLP
0.80%
62.08
46.20
1.607%
08.30
25.47
70.49
5,20%
71.50
16.21
42:70
67.53
65.54
02.17
25.05
07.51
28.02
70.21
67.75
0.06%
16.00
1.70
11:20
0.25
28.74
F.50
21,52
755
15.35
9.36
Proeiir
0.107
10.63
2.1
15.38
5.91
31.04
10:13
20:18
3.07
28:40
7.47
10.14
9:36
0.20%
18.08
2000
8.50
1.86
23:25
6.52
23:36
6:78
29.26
7.73
3.00%
16.72
6.27
15.05
3.165
27:34
5.30
27.53
16.32
29.45
13:23
15.54
14.2.
PCG
4.007
16.83
0.20
25:08
13.34
25.13
6.75
29.40
9.00
$2.10
5.81
25.35
18.32
42.25
81.4
K.00%%
16.87
3.02
22.16
1.365
14:33
4.59
33.50
8.58
31.56
12:53
15:37
13.90
2.00%
28-18
137
19:22
23:35
6:35
30.54
101195
36.71
6.53
30.54
11:24
HonsuGo
4.007
37.00
31:01
7.34
7.31
34.93
25.07
31.45
17.29
KukaryotaGo
2.007%
10
5.03
76.71
5.16
00.99
3.00
4.00
35.35
7.00
45.85
19.97
3.00%
30.79
75.50
3.43
23.05
4.31
36.57
36.97
1.81
38.90
Observation 2: K-Center demonstrates stability in extreme condensation setting. The K-Center method shows consistent performance, particularly on large-scale and dense-label datasets, highlighting its strength in preserving diversity at low condensation rates. On the Yelp dataset, K-Center outperforms traditional Coreset methods, achieving the highest F1-micro score (37.61%) a 0.20% condensation rate. This suggests that its selection strategy effectively retains essential structural and label information, even under high condensation, making it advantageous for large-scale settings where extreme data reduction risks losing critical information.
Observation 3: SGDD's performance is constrained by scalability issues on larger datasets. SGDD faces OOM errors on large datasets like Yelp and OGBN-Proteins, revealing its scalability limitations. However, on smaller datasets, SGDD performs compelitively, benefiting from its strucdure-broddcasting graphon technique, which efficiently captures structural patterns. For example, on datasets such as PCG, HumanGo, and EukaryoteGo, SGDD achieves strong F1-micro and F1-macro scores, demonstrating its effectiveness smaller scales. Nevertheless, its applicability to larger datasets requires further optimization.
While the performance of condensation methods varies with dataset characteristics, GCond excels on complex, high-dimensions datasets like DBLP and PPI, where maintaining label consistency and intricate relationships is crucial. In contrast, simpler methods such as Random and Herding show stable performance but are outperformed by GCond and K-Center on datasets that demand preservation of structure and label diversily- These results highlight the importance of selecting condensation methods based on dataset scale, complexity, and label interaction patterns to achieve optimal performance.
8 Conclusion
In this benchmark, we introduce a comprehensive framework for multi-label graph condensation, extend- ing traditional single-label methods to address the complexities of multi-label classification. Our results demonstrate that GCond not only preserves the original graph's 's structural integrity but also enhances label correlations, leading to more accurate multi-label predictions.
While our study establishes baseline across standard benchmarks, the generalizability of these methods to other graph domains remains an open question. As a future direction, we aim to explore the applicability and robustness of our approach across diverse graph lypes, including dynamic graphs (Barros et al. 2021 (e.g., time-varying traffic flow graphs), heterogeneous graphs (Wang et al., 2022) (e.g., user-item graphs), and heterophilous graphs (Platonov et al. 2023) (c.g., graphs with dissimilar node labels). Such explorations will provide deeper insights into the fiexibility and practical utility of our proposed mothods across diverse real-world graph scenarios.
12

---

Published in Transactions on Machine Learning Research (/)
References
Uchenna Akujuobi, Han Yufei, Qiannan Zhang, and Xiangliang Zhang. Collaborative graph walk for semi- supervised multi-label node classification. In 2019 JEEE International Conference on Data Mining (ICDM), pp. 1-10. IEEE, 2019.
Claudio DT Barros, Matheus RF Mendonga, Alex B Vicira, and Artur Ziviani. A survey on embedding dynamic graphs. ACM Compuling Surveys (CSUR), 55(1):1 2021.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez- Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 1rXii:1806.011 2018.
Sanmitra Bhattacharya, Viet Ha-Thue, and Padmini Srinivasan. Mesh: a window into full text for document summarization. Bioinformatics, 27(13):1120 i128, 2011.
Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózem- berczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473, 2020.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with labelldlistibbution-awaee margin loss. Advances in nearal informalion processing systems, 32, 2019.
Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo. Multi-label image recognition with graph convolutional networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 5177-5186, 2019.
Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One trillion edges: Graph processing at facebook-scale. Proceedings of the VLDB Endowment, 8(12):1804 1815, 2015.
Kuo-Chen Chou and Hong- Bin Shen. Euk-mploc: a fusion classifier for large-scale eukaryotic protein subcellular location prodiction by incorporating multiple sites. Journal of Proteome Research, 6(5): 1728 1734, 2007.
Kenneth Ward Church. Word2vee. Natural Longuage Engineering, 23(1):155 162, 2017.
Kinkar Ch Das, Seyed Ahmad Mojallal, and Vilmar Trevisan. Distribution of laplacian eigenvalues of graphs. Linear Algebra and its Applications, 508:48-61, 2016.
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.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-based frand detoctors against camouflaged fraudsters. In Proceedings of the 29th ACM international conference on informalion & knowledge management, pp. 315 324, 2020.
Thibaut Durand, Nazanin Mchrasa, and Greg Mori. Learning a deep convnct for multi-label classification with partial labels. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 647-657, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Junfeng Fang, Xinglin Li, Yongduo Sui, Yuan Gao, Guibin Zhang, Kun Wang, Xiang Wang, and Xiangnan He. Exge: Bridging efficiency and explainability in graph condensation. In Proceedings of the ACM Web Conference 2024, pp. 721-732, 2024.
Reza Zanjirani Farahani and Masoud Hekmatfar. Facility location: concepts, models, algorithms and case studies. Springer Science & Business Media, 2009.
13

---

Published in Transactions on Machine Learning Research (/)
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 1416 1424, 2018.
Shuang Gao and Peter Caines. Graphon control of largo-scale networks of linear systems. JEEE Transactions on Aulomatic Control, 65(10)44090 4105, 2019.
Xinyi Gao, Junliang Yu, Wei Jiang, Tong Chen, Wentao Zhang, and Hongzhi Yin. Graph condensation: A survey. Xixiv preprint orXiv:2411.00 11720, 2024.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graph neural architecture search. In Interna- tional joint conference on artificial intelligence. International Joint Conference on Artificial Intelligence, 2021.
Ivan Gutman and Bo Zhou. Laplacian energy a graph. Linear Algebra and its applications, 414(1):29-35 -7, 2006.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs, 2018. URL
wwwp//g//////oooooo/..ooo..eeee/ .22216
Mohammad Al Hasan and Mohammed J Zaki. A survey of link prediction in social networks. Social network data analytics, pp. 243-275, 2011.
Mohammad Hashemi, Shengbo Gong, Juntong Ni, Wenqi Fan, B. Aditya Prakash, and Wei Jin. A compre- hensive survey on graph reduction: Sparsification, coarsening, and condensation. ArXiv, bbs/2202.03355 2024. URL. http:///app..eemaaiccccchccoooee htt.://a.....roooooa..00020331..
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00657 2020.
Sheng-Jun Huang and Zhi-Hua Zhou. Multi-label learning by exploiting label correlations locally. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 949 955, 2012.
Rachael P Huntley, Tony Sawford, Prudence Mutowo-Meullenet, Aleksandra Shypitsyna, Carlos Bonilla, Maria Martin, and Claire O' Donovan. The goa database: gene ontology annotation updates for 2015. Nucleic acids research, D3151) D1063, 2015.
Dejun Jiang, Zhenxing Wi, Chang-Yi Yu Hsich, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou. Could graph neural networks learn better molecular representation for drug discovery? a comparison study of descriptor-bant based and graph-based models. Journal of cheminformatics, 13:1-23, 2021.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: survey, Expert systems with applications, 207:117921, 2022.
Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bin Ying, Condensing graphs via one-step gradient matching. Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022a. URL stttp:://ap..smmaticccc
org/CorpusID 249712265
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks, 2022b. URL httpp://arxxi.. wwteexivv.orgeee abs///aa///// 221///110..00. 07580
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar Xie: 609. 02907, 2016.
14

---

Published in Transactions on Machine Learning Research (/)
G. Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go deep enns? 2019 /EFE/CVF International Conference Compuler Vision (TCCV), pp. 9266-92755 2019. URL
Arthur Liberzon, Chet Birger, Helga Thorvaldsdóttir, Mahmoud Ghandi, Jill P Mesirov, and Pablo Tamayo.
The molecular signatures database hallmark gene set collection. Cell systems, 1(6):417-425, 2015.
Zachary Lipton, Charles Elkan, and Balakrishnan Naryanaswany, Optimal thresholding of classifiers to maximize fl measure. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, Seplember 1 15-19, 2014. Proceedings, Port II 14, pp. 225 239.239. Springer, 2014.
Mengyang Liu, Shanchuan Li, Xinshi Chen, and Le Song. Graph condensation via receptive field distribution matching, 2022. URL
htt.aaawww......r.////////aaaaaa ab2/ 13697
Yilun Liu, Ruihong Qiu, and Zi Huang. Cat: Balanced continual graph learning with graph condensation. In 2023 IEEE International Conference on Data Mining (ICDM), pp. 1157 1162. IEEE, 2023.
Andreas Loukas. Graph reduction by local variation. ArXiv, abs/1808. 10650, 2018. URL https://apl
semanticscholar wwg.:/rrrrrooroooooooooooo hrw.riarrrrrr/ooosssDDi::... SOrpusID:522447333
Kelong Mao, Jieming Zhu, Xi Xiao, Biao Lu, Zhaowei Wang, and Xiuqiang He. Ultragen: ultra simplification of graph convolutional networks for recommendation. In Proceedings of the 30th ACM international conference on information. & knowledge management, pp. 1253- 2021.
Joseph J Pfeiffer III, Sebastian Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. At- tributed graph models: Modeling network structure with correlated attributes. In Proceedings of the 23rd international conference on World wide web, pp. 831-842, 2014.
Janet Piñero, Juan Manuel Ramírez-Anguita. Josep Saüch--Ptarch, Francesco Ronzano, Emilio Centeno, Ferran Sanz, and Laura Furlong. The disgenet knowledge platform for disease genomics: 2019 update. Nucleic acids research, 48(D1):D845 D855, 2020.
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characterizing graph datascts for node classification: Nomopphlyy-hctrrphhie dichotomy and beyond. Advances in Newral Information Processing Systems, 36:523 548, 2023.
Jesse Read, Bernhard Pfahringer, Gcoff Holmes, and Eibe Frank. Classifier chains for multi-label classification. Machine learning,
2011.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. Advonces in Neural Information Processing Systems, 33:1702-1712, 2020.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 708. 708.00489, 2017.
Cosma Rohilla Shalizi and Andrew C Thomas. Homophily and contagion are generically confounded in observational social network studies. Sociological methods & research, 40(2):211-25 233,29 2011.
Min Shi, Yufei Tang, and Xingquan Zhu. Mine: Multi-label network embedding. JEFE tronsactions on neural networks and learning systems, 31(9):3682 3695, 2019.
Min Shi, Yufei Tang, Xingquan Zhu, and Jianxun Liu. Multi-label graph convolutional network reprosentation learning. IEEE Transactions on Big Data, 8(5):1169-115 1181, 2020.
Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In International Conference on Machine Learning, pp. 21076-21088 PMLR, 2022.
Grigorios Tsounakas and Ioannis Katakis. Multi-label classification: An overview. Data Warehousing and Mining: Concepts, Methodologies, Tools, and Applications, pp. 64-74, 2008
15

---

Published in Transactions on Machine Learning Research (/)
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, Yoshua Bengio, et al.
Graph attention networks. stat, 1050(20):10-4886) 485500, 2017.
Jianian Wang, Sheng Zhang, Yanghua Xiao, and Rui Song. A review on graph neural network methods in financial applications. arXiv preprint arXio:2111.15367 2021.
Lin Wang, Wenqi Fan, Jiatong Li, Yao Ma, and Qing Li. Fast graph condensation with structure-based neural tangent kernel. In Proceedings of the ACM on Web Conference 2024, pp. 4439 4448, 2024.
Tongzhou Wang, Jun-Yar Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint
arX1u:1811. 10959, 2018.
Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, and S Yu Philip. A survey on heterogeneous graph embedding: methods, techniques, applications and sources. IEEE Transactions on Big Data, 9()) 415 436, 2022.
Max Welling, Herding dynamical weights to learn. In Proceedings of the 26th onnual international conference on machine learning, pp. 1121-1128, 2009.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: a survey. ACM Compuling Surveys, 55(5):1 37, 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprchensive survey graph neural networks. IEEE transactions neural nelworks and learning systems, 32(1):4 24, 2020.
Xinyue Xia, Gal Mishne, and Yusu Wang. Implicit graphon neural representation. In International Conference on Artificial Intelligence and Statishics, pp. 10619-10634. PMLR, 2023.
Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33(1):4, 2022.
Hongjia Xu, Liangliang Zhang, Yao Ma, Sheng Zhou, Zhuonan Zheng, and Bu Jiajun. A survey on graph condensation. arXiv preprint arXiv:2402. 02000, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
arviv preprint arXie:18100 00826, 2018
Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hanghang Tong. Kernel ridge regrossion-based graph dataset distillation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2850 2861, 2023.
Beining Yang, Kai Wang, Qingyun Sun, Cheng Ji, Xingcheng Fu, Hao Tang, Yang You, and Jianxin Li. Does graph distillation see like vision dataset counterpart?, 2023. URL httpt::// //atps wwtpxiiv.org/aae prg/abs/2310.00
Xiaodi Yang, Shiping Yang, Qinmengge Li, Stefan Wuchty, and Ziding Zhang. Prediction of human-virus protein-proted interactions through a sequence embedding based machine learning method. Computational and structural biotechnology journal, 161, 2020.
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04091, 2019.
Jiani Zhang, Xingjian Shi, Shenglin Zhao, and Irwin King. Star-gen: Stacked and reconstructed graph convolutional networks for recommender systems. Xix preprint arXie:1905.13129, 2019a.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Shichang Zhang, Atefch Sohrabizadch, Cheng Wan, Zijic Huang, Ziniu Hu, Yewen Wang, Jason Cong, Yizhou Sun, al. A survey on graph neural network acceleration: Algorithms, systems, and customized hardware. Xix preprint arx::2200.1 14052, 2023.
16

---

Published in Transactions on Machine Learning Research (/)
Si Zhang, Hanghang Tong, Jicjun Xu, and Ross Maciejewski. Graph convolutional networks: comprchensive review. Compulational Social Networks, 6(1):1 2019b.
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. Graph neural networks and their current. applications in bioinformatics. Prontiers in genetics, 12:690049, 2021.
Yuchen Zhang, Tianle Zhang, Kai Wang, Ziyao Guo, Yuxuan Liang, Xavier Bresson, Wei Jin, and Yang You. Navigating complexity: Toward lossless graph condensation via expanding window matching. arXiv preprint ar Kiv:24402 05011, 2024.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. In Proceedings of the IEEE/CVE Winter Conference on Applications of Computer Vision, pp. 1514-6520 2023.
Tianqi Zhao, Ngan Thi Dong, Alan Hanjalic, and Megha Khosla. Multi-label node classification on graph- structured data. arXvv preprint arXiv:2304.10300 2023.
Xin Zheng, Miao Zhang, Chunyang Chen, Quoe Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure- free graph condensation: From large-scale graphs to condensed graph-free data. Advances in Newral Information Processing Systems, 36, 2024.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph ncural networks: A review of methods and applications. AI open, 1:57-81, 2020.
Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Yuanqi Du, Jieyu Zhang, Qiang Liu, Carl Yang, and Shu Wu. A survey graph structure learning: Progress and opportunitics. ar preprint
2021.
A Appendix
A.1 Adapted GCond Algorithm
Algorithm 1: Multi-Label GCond Adaptation
Input: Training data = YY)
Initialize multi-label synthetic graph S with X', y for == 0 to K K-1 do
Initialize 0n ~ Pao
4 for t == 0 to T 1 do
D' 0
Compute A' go(X'), then S = (A', XY,Y
Compute L7 L(GNN (A, x),Y)
7
Compute L L(GNN A', X", Y')) D' D' + DDVo,, Vg
10
if t%(1 + T2) < Ti then
L Update X X m D
11
12 else
L Update @ VVD''
13
14
Update 0,+1 f- oplo(0,, S, T8)
15
Compute new adjacency matrix: A' = (x)) for each edge (i,j) in A' do
16
L Ah. Al.g if Ah,, > otherwise Aly
17
18
return (A',',Y')
17

---

Published in Transactions on Machine Learning Research (/)
Table 6: Graph Condensation Methods Performance Comparison on Multi-label Benchmarks. '-" Out-of- memory (OOM); r*1; Estimated via smaller batch training due to memory constraints.
Dutases
Camate
F1-3ikero
(aandm)) F1-Maaro
F1-Micco
(eeding)) F1-Macro
Conrect F1-Mico
(K-Center: F1-3tacro
FL-Micco
SGDD
F1-Macro
F1-32icro
GCDM
F1-Mlacto
F1-Micr
GCand
FI-Macro
F1-Mico
60-SNTK'
FL-Mucro
0.50%
41.00
14:00
41:10
12:36
05.65
15.54
61.09
22.38
48.
23.37
49.63
23:16
38.76
13:25
PPI
1.00%%
30.37
12.58
41.20
11.00
47:48
17.36
47.02
18:26
47,07
21.76
51.35
23.86
41.47
16.90
2,00%%
41.12
14.12
39.21
10.23
52.34
26.02
06.73
21.24
47.91
21.03
51.21
24.32
45.25
16.94
0.10%%
44.43
14.49
49.37
10.74
41.12
18.11
49.32
18.33
47.13
37.59
51.05
27,51
PPL
0.20%%
15.80
65:30
15.01
00.86
64.82
46,25
22.24
63.00
29,05
0.4095
15.43
18.74
69.89
44.06
62.23
28.00
A.2 Recent Condensation Methods Discussion
Recent condensation methods have investigated various stralegies to deal with the challenges in scalability, robustness, inductiveness, and explainability. While selecting methods for our benchmark, we mainly aimed for fair and systematic evaluation across consistent condensation sctting. Several recent methods fall outside this scope present practical issues that prevent their direct inclusion fair comparison. Here we will summarize and discuss these methods, categorizing them by the considerations leading to their exclusion or special treatment in our current benchmark.
Dynamic and Open-world Settings. The Open-world Graph Condensation (OpenGC) Gao et al. 2024
solves distribution shifts in dynamic graph settings through struclure-aware condensation of evolving graphs. It utilizes kernel ridge regression and -on-paraettric graph convolutions to update condensed graphs for life-long learning scenarios. While our benchmark focuses primarily on graph condensation scenarios under a static distribution setting common in multi-label graph classification. Meanwhile, at the time of our study, the implernentation code was not publicly available yet. Future extensions of our work could integrate dynamic and evolving datasets, providing an evaluation benchmark suited explicitly assess OpenGC and similar dynamic methods.
Interprctability Constraints. The EXGC (Efficient and eXplainable Graph Condensation) Fang et al. (2024) method proposes variational approximations coupled with Gradient Information Bottlenecks (GDIB) enhance the interpretability in large-scale graph condensation tasks. Due to the absence of publicly accessible implementations at the time of our benchmark, EXGC could not be integrated despite its potential practical and interpretability advantages. With code availability, future benchmarks may consider evaluating EXGC's effectiveness.
Inductive Learning Scenarios. The Mapping-awar Graph Condensation (MCond) Gao et al (2024) learns node mappings between the original large graph and the synthetic condensed graph from an inductive learning perspective. It allows integration of unseen (inductive) nodes without referring back to the original large graph at inference time. However, our study strictly evaluates methods under the transductive settings where nodes are fully observed during training. Since MCond targets inductive and unseen node inference specifically, its cennetive-oouuse design places beyond our present evaluation objectives. Expanding our benchmark to explicitly include inductive graph condensation paradigms remains prospective focus for future work.
Practical Implementation Limitations. The Graph Condensation via Structure-based Neural Tangent Kernel (GC-SNTK) [Wang et al. (2024) uses structure-informed neural tangent kernels complete the condensation stage without bi-level constraints. In our experimentation we encouter several challenges: (1) its kernel computation is limited to training set nodes, unlike methods utilizing entire graph structures; (2) it struggles with complex label dependencies, as it optimizes synthetic node features A' and labels Y' in a single-label selting; (3) memory limitations due to kernel scalability issues, which restrict batch sizes and may lead to unfair comparisons under standardized benchmarking conditions; (4) a sparse structure requirement for kernel optimization, which is problematic as multilabel graphs have denser edges and more complex structures. Despite these challenges, we implemented GC-SNTK a simplified form in our code https://github..om/
http://gttubbbcoooo/laangnggg/// /liang/iangvvv///1 M/it666MMul//CC/ Sampled results are illustrated by the PPI dataset in Table 6
18

---

Published in Transactions on Machine Learning Research (/)
Adjustments such as kernel generalization and more sophisticated label-aware formulations are necessary to effectively leverage GC-SNTK for multilabel tasks.
A.3 Datasets and Metrics
Datasets. We use eight real-world datasets from diverse domains, including bioinformatios and social networks, to assess the efficacy of graph condensation methods in multi-label scenarios. A detailed description of cach dataset is listed as follows:
PPI (Zeng et al. 2019 is the Protein-Protein Interaction network. It classifies protein functions based on the interactions of human tissue proteins. Positional gene sets are used, motif gene sets and immunological signatures as features and gene ontology sets as labels (121 in total), collected from the Molecular Signatures Database (Liberzon et al. 2015 And PPI-large is the larger version of PPI dataset.
Yelp (Zeng et al. 2019 is processed from a public open dataset from yelp..om The nodes represent active users and the edges are the relationship between the uscrs. The multi-label of cach node represents the types of business like Coffee & Tea, Flowers & Gifts, Tours, and so on. Node features contain the information of all the reviews and rates by users, generated by pre-trained Word2Vec model (Church 2017).
DBLP (Akujuobi et al. 2019 is the citation network extracted from DBLP. The nodes represent authors and edges are the co-authorship between the authors. Multi-label here indicates the four research areas like database, data mining, information and retricval and artificial intelligence.
OGBN-Proteins from Open Graph Benchmark (Hu et al. 2020) an undirected, weighted, and lyped (according to species) graph. Nodes represent proteins, and edges indicate different types of biologically meaningful associations between proteins, e.g., physical interactions, co-expression homology. The task is to predict the presence of protein functions in multi-label binary classification setup, where there are 112 kinds of protein functions denote as labels to predict in total. Here the protein functions refer to the specific biological activities or roles that a protein performs within a cell or organism. These functions are typically described using Gene Ontology (GO) database (Huntley et al. 2015) or other biological annotation systems and can fall into different categories.
PCG (Zhao et al. 2023 is Protein- Protein-Phenotppo graph dataset, which focused on predicting phenotypes associated with proteins. Phenotypes refer observable traits or charactcristies of discases, and identifying these associations can be valuable for clinical diagnostics or discovering potential drug targets. The dataset is constructed using protein-phenotee
associations from the DisGeNET database (Piñero et al. 2020), where each protein is linked to one or more phenotypes. The phenotypes are grouped into discase categories based on the MESH ontology (Bhattacharya et al. 2011), and labels with fewer than 100 associated proteins are removed. The PCG includes 3,233 proteins as nodes and 37,351 protein-protein interactions as edges. The task to predict multiple phenotype labels for cach protein based on its interactions and features.
HumanGo (Chou & Shen, 2007 Liberzon et al. 2015) contains 3,106 proteins, each potentially associated with one or more of 14 subcellular locations as multi-label. The proteins are represented as nodes in graph, with features generated from their sequences using pre-trained model (Yang) let al.) 2020). Protein-protein interactions form the edges of the graph, with each edge representing the confidence of different interaction types. Different location associations come from the GO database (Huntley et al. 2015), which assigns standardized terms to proteins based on their roles in biological processes (e.g., cell division, metabolism), molecular functions (e.g., enzyme activity, receptor binding), and cellular components (e.g., nucleus, membrane).
EukaryoteGo (Chou & Shen 2007 Liberzon et al. 2015) follows a similar structure but focuses on cukaryote proteins. includes 7,766 proteins and their interactions, with proteins being assigned to one or more of 22 subcellular locations. Like HumanGo, uses protein sequences for node features and protein-protein interactions for graph structure.
19

---

Published in Transactions on Machine Learning Research (/)
Metrics. To evaluate the performance of graph condensation methods in multi-label classification, two widely recognized metrics: F1-micro and F1-macro (Tipton et. al. 2014
F1-micro score aggregates the contributions of all classes to compute the average F1 score. It does this by first calculating the total true positives, false positives, and false negatives across all labels, and then using these aggregated values to compute a global precision and recall. The Fl-micro score particularly useful when dealing with imbalanced datasets, as it gives equal weight to each instance rather than each class. It. defined as:
2 2x Precision x Recall
F1-micro
(18)
Precision Recall
where:
TP
Precision
TP + FP TP
Recall
TP FN
F1-macro computes the F1 for each class independently and then averages these scores. This metric treats all classes equally, regardless of their frequency in the dataset. It is particularly useful for understanding the model's performance across all classes, especially in scenarios where some classes may be underrepresented. The F1-macro score is defined as:
Fl-macro
F1,
(19)
C
where C is the number of classes and F1; ; is the F1 score for the 8th class, calculated as:
F1; 2 x Precision, X Recall,
(20)
Precision; Recall;
A.4 Visualization of Multi-Label Datasets
In this section, we delve deeper into the charactoristics of the condensed graphs by analyzing class distribution and label correlation within the multi-label datasets. This detailed examination is crucial for understanding how effectively the condensation methods preserve the multi-label relationships present in the original datasets. After obtaining the full benchmark results, provide detailed analysis of the condensed graphs by examining the class distribution and label correlation within the synthetic graphs. These statistical properties are crucial for understanding how well the condensed graphs preserve the multi-label relationships present in the original datasets.
Label Correlation:
To analyze the relationships between labels the dataset, we define the correlation matrix: Let Glabels be the set of labels from the original dataset G, and Y the corresponding original label matrix. We denote (i.j) the occurrence times of labels L, and Lj. and N, as the total number of times label L3 appears.
The conditional probability P(i.j) is defined as:
P(i,)) M(i.j) N
(21)
This conditional probability matrix models the edges as co-occurrence matrix.
Next, we define the diagonal matrix as follows:
D Diag P)
(22)
20

---

Published in Transactions on Machine Learning Research (/)
Finally, the Laplacian matrix Lo is computed as:
D
(23)
By computing the label correlation matrix, we investigate whether the co-occurrence patterns between labels in the original graph are retained in the condensed graph.
Class Distribution: We analyze how evenly or unevenly the labels are distributed across the classes in different datasets by index, which helps assess the quality of the condensation process.
Following the above definition, report the visualizations of different datasets as follows. The label correlation and class distribution are shown in Figures 2 and [ respectively. We find that the more complex the labels, the more the condensation methods would rely on structure and become more random. For future work, more suitable methods need to be fit to multi-label scenarios.
(a) PP1
(b) PPI-Large
(c) Yelp
(d) OGNE- Proteins
(e) DBLP
(f) PCG
(g) HumanGO
(h) EukaryoteGo
Figure 2: Multi-label Correlation Visualization
A.5 Characteristics of Subgraph Initialization
Analyzing subgraph structures requires characterizing two essential aspects: structural connectivity and attribute-driven node similarity (homophily). Connectivity captures how tightly connected the subgraph is, quantified by the average connected component size:
TN Σ m
Ctl,
(24)
where C, represents each connected component and m the total number of components.
On the other hand, homophily measures how interconnected nodes share similar attributes, especially relevant in multi-label scenarios. Using binary attribute vectors Vu and the Jaccard similarity, subgraph homophily H is defined as the average pairwise similarity across edges:
18 0 yvl
=
J(Hu, with [Vu. vv)
(25)
E
1y,. U yol
21

---

Published in Transactions on Machine Learning Research (/)
100.0
100
100.0
10000
(a) PPI
(b) PPI-Large
(c) Yelp
(d) OGBN-Proteins
DBLP
(1) PCG
(g) HumanGO
(l) EukaryoteCo
Figure 3: Multi-label Class Distribution Visualization
we observe that methods preserving higher structural and attribute-based similarity consistently achieve better Fl performance (Table 2 For instance, in datasets like PPI and OGEN-Proteins the K-Center method maintains higher subgraph connectivity and homophily compared to Random and Herding, resulting in clearly superior predictive accuracy. Conversely, for datasets such as PCG, the Herding method's better homophily and connectivity align with its improved classification performance. These outcomes highlight that maintaining structural coherence and attribute similarity in subgraphs directly supports better multi-labed classification results.
Based on subgraph connectivity (Table 7 and homophily (Table S
Connectivity Herding
Datasets
C-rate
Whole Dataset
Random
K-Center
PPI 1.00%
24.5
17.8
32.6
216.98
Yelp
0.02%
9.7
12.2
18.3
114
DBLP 0.80%
5.6
3.8
6.9
7.93
OGBN-Proteins
0.10%
55.4
46.2
79.8
295.45
PCG
4.00%
24.3
42.2
36.7
129.32
Table 7: Subgraph Connectivity Charactoristics Across Different Methods with Condensation Rates
Homophily Herding
Datasets
C-rate
Whole Dataset
Random
K-Center
PPI 1.00%
0.24
0.22
0.30
0.36
Yelp
0.02%
0.15
0.21
0.19
0.26
DBLP
0.80%
0.60
0.55
0.69
0.76
OGBN-Proteine PCG
0.10%
0.33
0.29
0.45
0.53
4.00%
0.10
0.15
0.13
0.17
Table 8: Subgraph Homophily Characteristics Across Different Methods with Condensation Rates
A.6 F1-Macro Results of Adaptation
Figures and show the visualizations of different adapation strategics measured by F1-micro score. To
further investigate the effectiveness of the methods, also report the F1-macro score in Tables TO and 11
22

---

Published in Transactions on Machine Learning Research (/)
Sampled Subgraph Initialization
Sampled Node Set Initialization
100
100
140
140
PPI
80
Yelp
120
120
DBLP
60
60
OGBN-Protein
Ft-micro Score (%%
100
40
100
40
PCG
80
20
80
20
0
-20
-20
40
-40
20
-60
-60
0
Random
Herding
K-Center
Whole Dataset
Random
Herding
K-Center
Probability
Whole Dalasel
(a)
(b)
Figure 4: Different Initialization Methods Performance. Performance metrics of the model, with the Fi-score represented decimal value.
Condense without A'
Condense with A'
100
100
140
PPI
80
80
Yelp
120
120
DBLP
60
60
OGBN-Pratein
F1-micro Score (%)
100
40
100
40
PCG
80
20
80
20
0
0
-20
-20
-40
-40
20
20
-60
-60
0
Random
Harding
K-Centar
Probability
Whole Datasal
Random
Herding
K-Center
Probability
Whole Dalaset
(a)
(b)
Figure 5: Performance Optimized by SoftMargin Loss. Performance metrics the model, with the Fi-score
represented decimal value.
A.7 Class-Weighted Optimization
Let. Nmax ma...e.....C N₂ is the maximum number of samples across all classes. For each class the class-wise coefficient is defined
N
ac
(26)
N Waxx
23

---

Published in Transactions on Machine Learning Research (/)
Condense without A'
Condense with A'
100
100
140
140
PPI
80
Yelp
120
120
DBLP
60
60
OGBN-Protein
Ft-micro Score (%)
100
40
100
40
PCG
80
20
80
20
0
-20
-20
-40
-40
20
-60
-60
0
Random
Harding
K-Centar
Probability
Whole Datesel
Random
Herding
K-Center
Probability
Whole Dalasel
(a)
(b)
Figure Porformance Optimized by BCE Loss.
Performance metrics of the model, with the Fi-score
represented decimal value.
Random
Herding
K-Center
Dalasets
C-rate
Subgraph
Nodes
Subgraph
Nodes
Subgraph
Nodes
Probability
Whole Dataset
PPI 1.00%
12.58
10.67
11.66
17.98
17.36
18.37
12.55
30.06
Yelp 0.02%
3.76
15.18
DELP
0.80%
56.00
51.43
15.63
15.41
56.90
52.74
15.68
86.39
OGBN-Pro 0.1%
2.12
7.12
5.21
7.17
10.13
6.42
6.36
9.16
PCG 4%
5.20
9.69
13.84
6.45
5.73
7.10
11.35
31.49
Table F1 Macro Score(%) of Coreset Method with Different Initializetion Strategies
The total loss for all the nodes would be the sum over all the classes and their respective nodes No:
Lsingle-label label = Σ
Σ
(oE(Z,,U))
(27)
c=0
JEN.
Datasets
C-rate
Without
With A1
Without
With
W Without
With
Without 1'
Probability
With
Whole Dataset
1.00%
18.32
11.62
Yelp
0.02%
3.72
6.98
3.57
3.99
6.37
9.02
2.13
1.86
15.18
DBLP
1%
35.81
37.84
27.08
27.11
32.21
49.36
42.33
38.08
86.39
OGBN-Pro
0.10%
5:47
5.32
PCG
4%
12.42
13.86
10.00
15.50
7.34
9.47
13.29
6.50
31.49
Table 10: F1-Macro Score (%) of GCond Method with Random Heeenin///riiggn/. K- Cea--CenerrPeee Centei/Probbbiliit Distribution Initialization with with/without without Learning from Graph Structure for Morginags
Herding
K-Center
Probability
Datasets
C-rate
Without A'
With 4'
Without A'
With A'
Without A
With 2'
Without 2'
Wich X
Whole Dataset
1.00%
Yelp
0.02%
3.57
8.02
4.24
4.13
6.13
6.22
4.00
3.07
15.18
DALP 1%
34.80
51.44
26.04
28.28
34,87
68.44
39.36
33.87
86.30
OCEN-Pro
6.19
7.47
PCG
4%
7.83
7.29
16.17
14.27
8.02
13.32
13.13
11.30
31.49
Table 11: F1-Macro Score (%) of GCond Method with Random/Herding Herdingg/ Baannng/-Ceee Wer-Ceeeer/Proaaiiii Distribution Initialization with/without Learning from Adjacent Nodes for BCELoss
24

---

Published in Transactions on Machine Learning Research (/)
Random
Hording
K-Center
Probability
Datasets
C-rate
Whole Dataset.
Without
With
Without A'
With A''
Without
With A'
Without
With
PPI
1.00%
19.30
51.28
46.25
46.65
45.10
16.15
16.32
43.61
51.26
Yelp
0.02%
31.06
30.12
32.42
32.58
34.26
33.75
22.10
25.82
37.97
DBLP
0.80%
62.47
65.27
46.19
48.73
62.58
87.05
OGBN-Proleins
0.10%
26.51
23.25
22.25
26.36
21.81
25.25
26.47
90.13
30.99
PCG
4%
Table 12: FI-Micro Score (%) of GCond Method with Random/ HHerding///////ee / / KKCeeterr Center/Probabllee Probbabiitt Distribution Initialization with/without Learning from Adjacent Nodes for BCE Loss and Balanced Coefficient
This is the general equation for different methods, as the condensation part using the M(-) as the matching loss, for example, GCond would compute the gradient for each class with class-wise wise coefficient and sum them up to get the final loss.
Furthermore, for each task we are working on the binary classification problem. To better capture the contribution of each class in multi-label, we introduce class weights RR for each task k:
(BC Uj.k) -wk(yj, log(o + (1 U5.k log(or
(28)
where wi is the positive class weight, scaling the loss for each positive class Vi.k 1. Therefore, the final loss of multi-label classification is:
Lmultti-lbel
wk (Uj,A log(0
(29)
+(1 Vj log( (z),a))
This is helpful when there is an imbalance between the number of positive and negative samples. The
Fl-micro results are shown in Table 12 and Figure 7 Fl-macro results are shown in Table 13
Condense without A'
Condense with
100
100
140
140-
PPI
Yelp
120
120
DBLP
60
OGBN-Protein
Ft-nicro Score (%)
100
40
100
PCG
80
20
80
60
60
-20
-20
40
400
-40
-60
-60
0
Random
Herding
K-Center
Probability
Whole Datasel
Random
Herding
K-Center
Probabilty
Whole Dalaset
(a)
(b)
Figure 7: Performance Optimized by BCE Loss with Class Weight
25

---

Published in Transactions on Machine Learning Research (/)
Random
Herding
K-Center
Probability
Datasets
C-rate
Whole Dataset
Without A'
With A'
Without
With
Without
With A
Without A'
With
PPT
1.00%
21.75
25.05
15.55
27.21
27.09
31.97
14.31
21.43
30.06
Yelp
0.02%
3.91
6.49
4.06
5.16
11.72
7.78
1.86
2.42
15.18
DBLP
0.80%
32.79
61.83
32.64
56.29
37.78
OGBN-Pro
0.10%
4.60
6,05
3.54
4.69
6.42
7,89
4.38
8.56
9.16
PCG
1%
13.26
11.83
12.21
15.75
5.70
9.88
11.60
8.36
31.19
Table 13: FI-Macro Score (%) of GCond Method with Random Baaoom//erreee Beaeeiiig/k--Ceeee/PPeooe Initialization with/withon Learning from Adjacent Nodes for BCE Loss and Balanced Coefficient
Distribution
26


Reviews:
[{"review_id": "fXc0nE8cFr", "reviewer": "Reviewer_veQG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n(1)The paper addresses an important problem in multi-label node classification. \n\n(2)The paper benchmarks existing methods as well as different initialization and optimization techniques, offering valuable insights for graph condensation on multi-label classification.\n\nWeakness:\n\n(1) In section 2.2 related work: The discussion on prior work primarily focuses on studies published before 2019. However, several recent works have explored multi-label graphs. Please include a discussion of these more recent contributions on multi-label node classification to provide a comprehensive and up-to-date perspective. \n\n(2) Notation definition: Ensure precise definitions of all notations used. For example, in Section 4.3, while explaining GCDM, the meaning of C is unclear. Please clarify. \n\n(3) challenges of applying existing methods on the multi-label setting are not clear: in section 6.1, explain more concretely what exactly is the problem of applying the approaches developed on the single-label graphs directly to multi-label graphs. Does same nodes get sampled multiple times in the subgraphs cause a problem? Do class imbalances in sampled subgraphs affect learning? What fundamental issues arise when applying methods from single-label to multi-label settings?  \n\n(4) Categorize the methods: in section 6.1, bold the names of methods/settings in the itemized list for clarity. Clearly distinguish between node-only and subgraph-based methods, aligning these categories with later discussions to improve readability and coherence.\n\n(5) In section 6.2, the performance differences across graph condensation methods could be influenced by the connectivity of sampled subgraphs and their homophily levels. Include characteristics of sampled subgraphs under node-only and subgraph-based settings to provide a clearer understanding of these differences. Structure observations by explicitly associating each method with the setting in which it is evaluated (e.g., Method A in Setting S).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides a benchmark study on the graph condensation methods on the multi-label graph datasets. Especially, it discusses and analyses the impact of different initializations and optimizations strategies as well as different graph condensation methods on the multi-label graph.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "seen above in the weakness.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BlUMWSO9Vt", "reviewer": "Reviewer_KUjt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n1.\tThe paper is well-structured, with a clear problem formulation, detailed methodology, and comprehensive experimental results. It introduces several adaptations to existing graph condensation methods to handle multi-label datasets. The modifications to synthetic dataset initialization and optimization strategies are well-motivated and clearly explained.\n\n2.\tThe authors conduct extensive experiments on eight real-world multi-label datasets, providing a thorough evaluation of their proposed methods. The use of multiple datasets from diverse domains (e.g., PPI, Yelp, DBLP) enhances the generalizability of the findings.\n\n3.\tThe paper provides three key observations based on the experimental results:\n- K-Center sampling is optimal for initialization.\n- Preserving graph structure improves performance, especially for large datasets.\n- Binary Cross-Entropy Loss (BCELoss) generally outperforms SoftMarginLoss.\n   These insights are valuable for researchers working on graph condensation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "As a benchmark-type study, this paper extends existing graph condensation techniques from single-label classification task on graphs to multi-label datasets, making a significant contribution to the field of graph condensation. The empirical results are extensive and compelling, and the insights provided are valuable for researchers. However, the paper lacks in-depth theoretical analysis and a more comprehensive baseline comparison. With these improvements, the paper would be even more complete.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Cons:\n\n1.\tWhile the paper provides extensive empirical results, it lacks a theoretical analysis of why certain methods (e.g., K-Center initialization, BCELoss) perform better in multi-label settings. A deeper theoretical justification could strengthen the paper's contributions.  \n \n2.\tThe paper compares the proposed methods against each other but does not include a comparison with state-of-the-art methods [1-4]. \n\n3.\tWhile the paper evaluates the methods on several datasets, it would be beneficial to discuss how well the proposed techniques generalize to other domains or types of graph data (e.g., dynamic graphs, heterogeneous graphs, heterophilous graphs). This could be a direction for future work.\n\n4.\tIncluding a link to the code or a more detailed appendix with implementation details would improve the reproducibility of the results.\n\n[1] Gao X, Chen T, Zang Y, et al. Graph condensation for inductive node representation learning[C]//2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024: 3056-3069.\n[2] Fang J, Li X, Sui Y, et al. Exgc: Bridging efficiency and explainability in graph condensation[C]//Proceedings of the ACM on Web Conference 2024. 2024: 721-732.\n[3] Wang L, Fan W, Li J, et al. Fast graph condensation with structure-based neural tangent kernel[C]//Proceedings of the ACM on Web Conference 2024. 2024: 4439-4448.\n[4] Gao X, Chen T, Zhang W, et al. Graph condensation for open-world graph learning[C]//Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024: 851-862.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XdyoV38oLA", "reviewer": "Reviewer_2yYV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n(+) The setting of multi-label graph condensation is new.\n\n(+) The experiment seems extensive.\n\n## Weaknesses\n\n(-) The current writing, especially about the motivation on why graph condensation is meaningful, relies on readers to agree with prior graph condensation works in advance.\n\n(-) The citation format is pretty off. It seems like the authors recycle the paper from other venue format but did not even bother to check and proofread. \n\n## Neutral\n\n(*)  I know the TMLR policy does not care about novelty, but I want to say the proposed multi-label extension is not as non-trivial as the authors’ claim in the introduction.\n\n## Detail comments\n\nFirst of all, I admit that I am not familiar with the line of works on graph condensation so I may misunderstand something here. Please correct me if I am wrong. According to the authors introduction and the section about graph condensation, the goal is to learn a synthetic graph so that the GNN trained on this graph will be similar as if it is trained on the original training graph. The motivation of graph condensation is that training on this small synthetic graph is much more efficient. However, what I do not understand is that the process of obtaining this synthetic graph is already more costly than training on the original graph directly. Thus, unless the condensed graph can be used for inference, it makes no sense to me. Unfortunately, according to Figure 1, we can see that even the number of nodes are different, which implies that it is hard (or even impossible) to do inference tasks using the condensed graph unless some mapping can be established. I feel the prior graph condensation works must have addressed this issue and I feel the authors should address (or at least mentioned and referred to prior works) it. The paper should by default be self-contained.\n\nAnother thing is that the citation format of the paper is quite off. One should use \\citet{} and \\citep{} properly. Right now, there is even no space between the name from the citations and the main text, which make the paper hard to read. I feel this issue is very obvious and can be avoided by a brief proof read. Finally, while TMLR does not care about novelty, but I want to say the proposed multi-label extension is not as non-trivial as the authors’ claim in the introduction. It is nothing wrong with this point, but I just want to state it as a fact to help the judgement of AC.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is a benchmarking study for off-the-shelf graph condensation methods to the multi-label setting. The main contribution is to show the behavior of each extended graph condensation methods under extensive experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "1. Please address the issue on the motivation of graph condensation that I mentioned above.\n2. Please correct the reference format.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a benchmark study on graph condensation methods for multi-label graph datasets. It specifically analyzes the impact of various initializations, optimization strategies, and graph condensation techniques on multi-label graphs. The proposed benchmark study is insightful and extensive experiments are conducted. The key observations provide valuable contributions to the field of graph condensation. The paper requires revisions and improvements before it can be accepted. The motivation behind the paper should be clarified further, and more related works and state-of-the-art methods should be discussed and incorporated into the benchmark. Additionally, the presentation needs improvement, particularly in reference formatting and clearer notation definitions. Overall, this is a useful contribution, but some revisions are necessary. Therefore, I recommend acceptance with minor revisions.
Decision: Accept (poster)