Local Graph Clustering with Noisy Labels
Authors: Artur Back de Luca
Kimon Fountoulakis
Shenghao Yang
Venue: ICLR 2024 poster (2024)
Keywords: local graph clustering
graph diffusion
attributed graphs
noisy labels
Primary area: learning on graphs and other geometries & topologies
TL;DR: We provide a simple yet highly effective way to perform local clustering in attributed graphs while utilizing node labels, without the need to access the entire graph.

Abstract: The growing interest in machine learning problems over graphs with additional node information such as texts, images, or labels has popularized methods that require the costly operation of processing the entire graph. Yet, little effort has been made to the development of fast local methods (i.e. without accessing the entire graph) that extract useful information from such data. To that end, we propose a study of local graph clustering using noisy node labels as a proxy for additional node information. In this setting, nodes receive initial binary labels based on cluster affiliation: 1 if they belong to the target cluster and 0 otherwise. Subsequently, a fraction of these labels is flipped. We investigate the benefits of incorporating noisy labels for local graph clustering. By constructing a weighted graph with such labels, we study the performance of graph diffusion-based local clustering method on both the original and the weighted graphs. From a theoretical perspective, we consider recovering an unknown target cluster with a single seed node in a random graph with independent noisy node labels. We provide sufficient conditions on the label noise under which, with high probability, using diffusion in the weighted graph yields a more accurate recovery of the target cluster. This approach proves more effective than using the given labels alone or using diffusion in the label-free original graph. Empirically, we show that reliable node labels can be obtained with just a few samples from an attributed graph. Moreover, utilizing these labels via diffusion in the weighted graph leads to significantly better local clustering performance across several real-world datasets, improving F1 scores by up to 13\%.

Published as a conference paper at ICLR 2024
LOCAL GRAPH CLUSTERING WITH NOISY LABELS
Artur Back de Luca, Kimon Fountoulakis, Shenghao Yang
School of Computer Science, University of Waterloo, Canada
{abackdel, kimon. fountoulakis, shenghao . yaaggn/wwtttrrroo.
ABSTRACT
The growing interest in machine learning problems over graphs with additional node information such as texts, images, or labels has popularized methods that require the costly operation of processing the entire graph. Yet. little effort has been made to the development of fast local methods (i.e. without accessing the entire graph) that extract useful information from such data. To that end, propose study of local graph clustering using noisy node labels as a proxy for additional node information. In this setting, nodes receive initial binary labels based on cluster affiliation: 1 if they belong to the target cluster and O otherwise. Subsequently, a fraction of these labels is flipped. We investigate the benefits of incorporating noisy labels for local graph clustering. By constructing a weighted graph with such labels, we study the performance of graph diffusion- on both the original and the weighted graphs. From theoretical perspective, we consider recovering an unknown target cluster with single seed node in a random graph with independent noisy node labels. We provide sufficient conditions on the label noise under which, with high probability, using diffusion in the weighted graph yields more accurate recovery of the target cluster. This approach proves more effective than using the given labels alone or using diffusion in the label-free original graph. Empirically,
local clustering method
show that reliable node labels can be obtained with just few samples from an attributed graph. Moreover, utilizing these labels via diffusion in the weighted graph leads significantly better local clustering performance across several real-world datasets, improving Fl scores by up to 13%.
INTRODUCTION
Given a graph and a set of seed nodes from the graph, the task of local graph clustering aims to identify small cluster of nodes that contains all or most of the seed nodes, without exploring the entire graph (Spielman & Teng 2013, Orecchia & Zhul 2014). Because of their ability to extract local structural properties within graph and scalability to work with massive graphs, local graph clustering methods are frequently used in applications such as community detection, node ranking,
and node embedding (Weng al. 2010 Mahoney al. 2012 Kloumann & Kleinberg, 2014 Perozzi ct al. 2014 Gleich 20155 Macgregor & Sun 2021] Choromanski 2023 Fountoulakis et al. 2023).
Traditionally, the problem of local graph clustering is studied under simple, homogeneous context where the only available source of information is the connectivity of nodes, i.e. edges of the graph. There is often little hope accurately identify well-connected ground-truth target cluster which also has many external connections. Meanwhile, the emergence of heterogeneous data sources which consist of a graph and any additional node information like texts, images, or ground-truth labels offers new possibilities for improving existing clustering methods. This additional information can significantly benefit clustering, especially when the graph structure does not manifest tightly-kmit cluster of nodes. Yet, little effort has been made to formally investigate the benefits of combining multiple data sources for local graph clustering. Only recently, the work of Yang & Fountoulakis (2023) has studied the usage of node attributes under a strong homophily assumption. However, they require separable node attributes-ofic impractical for real-world data-and neglect other forms of node information that might be available. For example, in many cases, we also have access to the ground-truie labels of a small set of nodes which reveal their cluster affiliation, such as when is known that certain nodes do not belong to the target cluster. While ground- touth label information has been extensively used in (semi-)superree >supervised learning contexts and proved vital in numerous applications (Kipf & Welling 2017 Hamilton al. 2017) it is neither exploited by existing methods

---

Published as a conference paper at ICLR 2024
for local graph clustering nor analyzed in proper theoretical settings with regard to how and why they can become helpful.
A challenge in designing local graph clustering algorithms that exploit additional sources of infor- mation and analyze their performance lies in the fact that additional data sources come in different forms. These can take the form of node or edge attributes, and even additional ground-truth labels for some nodes. Alternatively, one may just have access to an oracle that outputs the likelihood of node belonging to the target cluster, based on all available information. Due the variability of attributed graph datasets in practice, a local graph clustering method and its analysis should ideally be agnostic to the specific source or form of additional information. To that end, in order investigate the potential benefits that various additional sources of information can potentially bring to local graph clustering task, we propose a study in the following setting.
Local Graph Clustering with Noisy Node Labels: Given a graph and a set of seed nodes, the goal to recover an unknown target cluster around the seed nodes. Suppose that we additionally have access to noisy node labels (not to be confused with ground-truth labels), which are initially set to I if a node belongs to the target cluster and otherwise, and then a fruction of them is flipped. How and when can these labels be used to improve clustering performance?
In this context, node labels may be viewed as an abstract aggregation of all additional sources of information. The level of label noise, i.c the fraction of flipped labels, controls the quality of the additional data sources we might have access to. From a practical point of view, noisy labels may be seen the result of applying imperfect classifier that predicts cluster affiliation of node based on its attributes More generally, one may think of the noisy labels as the outputs of an encoder function that generates binary label for a node based on all the additional sources of information we have for that node. The quality of both the encoder function and the data we have is thus represented by the label noise in the abstract setting that we consider.
Due to their wide range of and successful applications in practice (Mahoney et al. 2012 Kloumann
& Kleinberg| 2014 Gleich 2015 Eksombatchai et al. 2018 Fountoulakis et al. 2020). in this work, we focus on graph diffusion based methods for local clustering. Our contributions are:
1. Given a graph G and noisy node labels, we introduce a very simple yet surprisingly effective way to utilize the noisy labels for local graph clustering. We construct a weighted graph G based on the labels and employ local graph diffusion in the weighted graph.
2. From theoretical perspective, we analyze the performance of flow diffusion (Fountoulakis et al. 2020: Chen et al., 2022) over a random graph model, which is essentially local (and more general) version of the stochastic block model. We focus on flow diffusion in our analysis due to its simplicity and good empirical performance (Fountoulakis et al. 2020 2021). The diffusion dynamics of flow diffusion
similar to that of approximate personalized PageRank (Andersen let (006) and truncated random walks (Spielman & Teng 2013), and hence our results may be easily extended to other graph diffusions. We provide suffecintt conditions the label noise under which, with high probability, flow diffusion over the weighted graph G leads to a more accurate recovery of the target cluster than flow diffusion over the original graph G.
3. We provide an extensive set of empirical experiments over 6 attributed real-world graphs, and we show that our method, which combines multiple sources of additional information, consistently leads to significantly better local clustering results than existing local methods. More specifically, we demonstrate that: (1) reasonably good node labels can be obtained as outputs of classifier that takes as input the node attributes; (2) the classifier can be obtained with or without ground-truth label information, and it does not require access to the entire graph; (3) employing diffusion in the weighted graph G outperforms both the classifier and diffusion in the original graph G.
1.1 RELATED WORK
The local graph clustering problem is first studied by Spielman & Teng (013) using truncated random walks and by Andersen et al. (2006) using approximate personalized PageRank vectors. There is long line of work on local graph clustering where the only available source of information is the graph
'hhe classifier may be obtained in supervised manner in the presence of limited ground truth label information, or in an unsupervised way without access to any ground-trun labels. If obtaining and applying such a classifier is part of local clustering procedure, then neither its training nor inference should require full access the graph. Our empirical results show that simple linear models can work surprisingly well in this context.
2

---

Published as a conference paper at ICLR 2024
and seed node (Spielman & Teng 2013 Andersen et al.] 2006 Chung 2009: Reid & Yuval
2009
Allen-Zhu et al. 2013]] Andersen et al. 2016 Shi et al. 2017] Yin et al. 2017] Wang et al.
2017
Fountoulakis et al.) 2020; Liu & Gleich 2020). Most of existing local clustering methods are based
on the idea of diffusing mass locally in the graph, including random walks (Spielman & Teng 2013)
heat diffusion (Chung 2009), maximum flow (Wang al.) 2017) and network flow (Fountoulakis
ct al. 2020). We provide more details in Section 2 where we introduce the background in more depth.
Recently, Yang & Fountoulakis (002)) studies local graph clustering in the presence of node attributes. Under a strong assumption on the separability of node attributes, the authors provide upper bounds on the number of false positives when recovering a target cluster from a random graph model. The assumption requires that the Euclidean distance between every intra- intra-cluster pair of node attributes has to be much smaller than the Euclidean distance between every inter-cluster pair of node attributes. Such an assumption may not hold in practice, for example, when the distributions of node attributes do not perfectly align with cluster affiliation, or when the node attributes are noisy. This restricts the practical effectiveness of their method. Our work takes very different approach in that we do not restrict to a particular source of additional information or make any assumption on node attributes. Instead, we abstract all available sources of additional information as noisy node labels.
Leveraging multiple sources of information has been extensively explored in the context of graph clustering (Yang et al. 2013 Zhe et al., 2019; Sunn et al., 2020), where one has access to both the graph and node attributes, and in the context of semi-supervised learning on graphs (Zhou et al. 2003 Kipf & Welling 2017 Hamilton et al.] (217)), where one additionally has access to some ground-truth class labels. All of these methods require processing the entire graph and all data points, and hence they are not suitable in the context of local graph clustering.
2 NOTATIONS AND BACKGROUND
We consider a connected, undirected, and unweighted graph G (V, where V = ( is a set of nodes and E S V x V is a set of edges. We focus on undirected and unweighted graphs for simplicity in our discussion, but the idea and results extend to weighted and strongly connected directed graphs. We write i ~ j is (i.j) E E and denote A E (0, 1 1)axn the adjacency matrix of G, i.e. Au = is i j and A.j 0 otherwise. The degree of node E V is (i) == H E V :j i ~ ii), i.e. the number of nodes adjacent to it. The volume of subset U S V is volc(U) = Eiev diga(i). We use subscripts to indicate the graph we are working with, and we omit them when the graph clear from context. We write E(U, W) == ((,,j) E ; U.j E } as the set of edges connecting two subsets U, W C V. The support of a vector & E R" is supp(æ> = {i x; * 0}. Throughout our discussion, we will denote K as the target cluster we wish to recover, and write K := V.K. Each node i E V is given label iA E {0, 1}. For E 1) we write Y, = ii V: is = c). Throughout this work, labels that provide ground-truth information about cluster affiliation will be referred to as ground- -tuth labels. When the word labels is mentioned without the modifier ground-truth, one should interpret those as the noisy labels yi.
..... n)
In the traditional setting for local graph clustering, we are given a seed node a which belongs to an unknown target cluster K, or sometimes more generally, we are given a set of seed nodes 5 C V such that S n K * 0. is often assumed that the size of the target cluster K is much smaller than the size of the graph, and hence good local clustering method should ideally be able recover K without having to explore the entire graph. In fact, the running times of nearly all existing local clustering algorithms scale only with the size of K instead of the size of the graph (Spielman & Teng
2013 Andersen et al. 2006 2016 Wang et al.) 2017: Fountoulakis et al.) 2020; Martínez-Rubio al. 2023). This distinguishes the problem of local graph clustering from other problems which require processing the entire graph. In order to obtain a good cluster around the seed nodes, various computational routines have been tested to locally explore the graph structure. One of the most widely used ideas is local graph diffusion. Broadly speaking, local graph diffusion is a process of spreading certain mass from the seed nodes to nearby nodes along the edges of the graph. For example, approximate personalized PageRank iteratively spreads probability mass from node to its neighbors (Andersen et al., 2006), heat kernel PageRank diffuses heat from the seed nodes to the rest of the graph (Chung 2009), capacity releasing diffusion spreads source mass by following combinatorial push-relabel procedure (Wang et al. 2017). 7). and flow diffusion routes excess mass out of the seed nodes while minimizing network flow cost (Fountoulakis et al. 2020). In local graph diffusion process, mass tends to spread within well-connected clusters, and hence a careful look at where mass spreads to in the graph often yields good local clustering result.
3

---

Published as a conference paper at ICLR 2024
Our primary focus is the flow diffusion (Fountoulakis al., 2020) and in particular its 22-norm version (Chen et al. 2022). We choose flow diffusion due to its good empirical performance and its flexibility in initializing a diffusion process. The flexibility allows to derive results that are directly comparable with the accuracy of given noisy labels. In what follows, we provide a brief overview of the (2-norm flow diffusion. For a more in-depth introduction, itt al. (2020) and Chen et al. (2022). In a flow diffusion, we are given A, > 0 units of source mass for each seed node s. Every node i V has a capacity, T 2 which is the maximum amount of mass it can hold. If A; > T; at some node i, then we need to spread mass from i to its neighbors in order to satisfy the capacity constraint. Flow diffusion spreads mass along the edges in a way such that the f--norm of mass that is passed over the edges is minimized. In particular, given a weight
refer the readers to Fountoulakis
vector w E [2 (i.c., edge has resistance 1/we), the ty-norm flow diffusion and its dual can be
formulated as follows (Chen et al. 2022):
Se/ee s.t. B
min 2
BEE
min x² +z (T A) s. 0,
(2)
where B IR E x VI is the signed edge incidence matrix under an arbitrary orientation of the graph. and L B"W B is the (weighted) graph Laplacian matrix where W is the diagonal matrix of w. If the graph is unweighted, then we treat w as the all-ones vector. In the special case where we set A, = 1 for some node and 0 otherwise, T, 1 for some node t and 0 otherwise. the flow diffusion problem ( reduces to an instance of electrical flows (Christiano et al. 2011). Electrical flows are closely related to random walks and effective resistances, which are useful for finding good global cuts that partition the graph. In a flow diffusion process, one has the flexibility to choose source mass A and sink capacity T' so that the entire process only touches small subset of the graph. For example, T; = for all i, then one can show that the optimal solution x² for the dual problem 2 satisfies |supp(=") S Eiev A,, and moreover, the solution x² can be obtained in time O(supp(( xx I) which is independent of either [V] or E| (Fountoulakis et al. 2020). This makes flow diffusion useful in the local clustering context. The solution x² provides a scalar embedding for each node in the graph. With properly chosen A and T, Fountoulakii et al. (2020) showed that applying a sweep procedure on the entries of x* returns a low conductance cluster, and Yang & Fountoulakis (2023) showed that supp(x") overlaps well with an unknown target cluster in a contextual random graph model with very informative node attributes.
3 LABEL EDGE WEIGHTS IMPROVE CLUSTERING ACCURACY
In this section, we discuss the problem of local graph clustering with noisy node labels. Given a graph G= E) and noisy node labels St E {0. 1} for E V, the goal is to identify an unknown target cluster K around a set of seed nodes. We primarily focus on using the f2-norm flow diffusion (2) for local clustering, but our method and results should easily extend to other diffusion methods such as approximate personalized PageRank
adopt the same rounding strategy as Ha ct al. (202I) and Yang & Fountoulakis (2023), that is, we consider supp(x") (x*) as the output cluster and compare it against the target K. Specific diffusion setup with regard to the source mass A and sink capacity T is discussed in Section 3.1 Occasionally we write x (T, A) or the source mass and sink capacity, and omit them when they are clear from the context. Whenever deemed necessary for the sake of clarity, we use different superscripts x¹ and xf distinguish solutions of (2) obtained under different edge weights.
[ Let x denote the optimal solution of 2).
xr" (A) to emphasize its dependence
We will denote
:= = :>=KKn
KK n 8111K), do : n
which quantify the accuracy of labels within K and outside K, respectively. If ao a1 = 1, then the labels perfectly align with cluster affiliation. We say that the labels are noisy if at least one of ag and aj is strictly less than 1. In this case, we are interested in how and when the labels can help local graph diffusion obtain a more accurate recovery of the target cluster. In order for the labels to provide any useful information at all, will assume that the accuracy of these labels is at least 1/2.
Assumption 3.1. The label accuracy satisfies do 1/2 and a 2 1/2.
We demonstrate this through comprehensive empirical study in Appendix D.2
4

---

Published as a conference paper at ICLR 2024
To exploit the information provided by noisy node labels, consider straightforward way to weight the edges of the graph G = (V, E) based on the given labels. Denote G = (V, E, w) the weighted graph obtained by assigning edge weights according to - R. We set
w(i.j)
if ú: ūj. and w(i,)) if D: + ūj.
(4)
for some small [0, 1). This assigns a small weight over cross-label edges and maintains unit weight over same-label edges. The value of e interpolates between two special scenarios. If = 1 then G reduces to G, and if с = 0 then all edges between Y1 and Y, are removed in G In principle, the latter case can be very helpful if the labels are reasonably accurate or the target cluster well-connected. For example, in Section [3.1 we will show that solving the --ror flow diffusion problem (2) over the weighted graph G by setting the target cluster than solving it over the original graph G. In practice, one may also choose a small nonzero e improve robustness against very noisy labels. In our experiments, we find that the results are not sensitive to the choice of e, as we obtain similar clustering accuracy for e E [10-² 10 over different datasets with varying cluster sizes and label accuracy. We use the F1 score to measure the accuracy of cluster recovery. Suppose that a local clustering algorithm returns a cluster C C V, then
0 can lead
accurate recovery of
K K + CVK / CK/2
FI(C)-
Even though the edge weights (4) are fairly simple and straightforward, they lead to surprisingly good local clustering results over real-world data, as we will show in Section Before we formally analyze diffusion over G let us start with an informal and intuitive discussion on how such edge weights can be beneficial. Consider a step during a generic local diffusion process where mass spread from node within the target cluster to its neighbors. Suppose this node has similar number of neighbors within and outside target cluster. An illustrative example shown in Figure Ta In this case, since all edges treated equally. diffusion will spread lot of mass to the outside. This makes it very difficult to accurately identify the target cluster without suffering from excessive false positives and false negatives. On the other hand, if the labels have good initial accuracy, for example, if a1 > an, then weighting the edges according to (4) will generally make more boundary edges smaller while not affecting many internal edges. This is illustrated in Figure Tb) Since diffusion step spreads mass proportionally to the edge weights (Xing & Ghorbani] 2004 Xie et al.) 2015, Yang & Fountoulakis. 2025), neighbor that is connected via a lower edge weight will receive less mass than a neighbor that is connected via a higher edge weight. Consequently, diffusion in such a weighted setting forces more mass be spread within the target cluster, and hence less mass will leak out. This generally leads to more accurate recovery of the target cluster.
Target cluster
Target cluster
Diffusion leaks
Diffusion keeps
mass
mass
(a) Diffusion the original graph
(b) Diffusion the weighted graph
Figure 1: Label-based edge weights avoid mass leakage by attenuating more boundary edges than internal edges. This helps local diffusion more accurately recover the target cluster.
3.1 GUARANTEED IMPROVEMENT UNDER A RANDOM GRAPH MODEL
Following prior work on statistical analysis of local graph clustering algorithms (Ha et al. 202 Yang & Fountoulakis 2023), assume that the graph and the target cluster generated from the tollowing random model, which can seen as a localized stochastic block model.
Definition 3.2. [Local random model (Ha et al., 2022 Yang & Fountoulakis 2023)] Given a set of nodes V and target cluster K C V. For every pair of nodes i and j, if i. E K then we draw
edge (i. with probability pt if E K and j E K then we draw an edge (i,j) with probability q;
otherwise, if both i E K then we allow any (deterministic or random) model to draw edge.
5

---

Published as a conference paper at ICLR 2024
Let l |K] and [V]. For node E K, the expected number of internal connections is p( 1) and the expected number of external connections is q(n - k). We will denote their ratio by
p( 1)
7 q ic)
The value of y can be seen as measure of the structural signal of the target cluster K. When y is small, node within K is likely to have more external connections than internal connections; when is large, a node within K is likely to have more internal connections than external connections.
Recall our definition of the weighted graph G whose edge weights are given in 4 based on node labels. We will study the effect of incorporating noisy labels by comparing the clustering accuracy obtained by solving the flow diffusion problem ( over the original graph G' and the weighted graph G respectively. For the purpose of the analysis, we simply set c = 0 as this is enough to demonstrate the advantage of diffusion over G Determining an optimal and potentially nonzero e E [0. 1J that maximizes accuracy is an interesting question and we provide additional discussion in Appendix B For readers familiar with the literature local clustering by minimizing conductance, if and q are reasonably large, c.g., 2 4 loo k/k and 2 4log k/(n - k). then a simple computation invoking the Chernoff bound yields that
cutg (K) x (01 (1 ao) + ao - ai)) cut with high probability,
volg- volg=<x((K) x (aî + (1 (1- a1)²) voloxx((K); with high probability,
where G[C] denotes the subgraph induced on C V. so volg measures the overall internal connectivity of K. Since a 13l-a) a0) + an(1 - a1) a1) < aî + (1 a1)² as long as ao, 01 > 1/2, the target cluster K will have smaller conductance in G long as the label accuracy is larger than 1/2. As a result, this potentially improves the detectability of K in G Of course, a formal argument requires careful treatments of diffusion dynamics in G and G" respectively.
We consider local clustering with a single seed node using flow diffusion processes where the sink capacity is set to T; 1 for all i V. Although discussed earlier, we summarize below the key steps of local clustering with noisy labels using flow diffusion:
Input: Graph G (V, E), seed node E V, noisy labels for i V, source mass parameter 0.
1. Create weighted graph G based on (4). Set source mass A, = 0 if = s and 0 otherwise.
2. Solve the 82-norm flow diffusion problem (2) over G Obtain solution x (0).
3. Return a cluster C = supp(z (#)).
Remark 3.3 (Locality). In a practical implementation of the method, Step 1 and Step 2 can be carried out without accessing the full graph. This is because computing the solution æ1 only requires access to nodes (and their labels) that either belong to supp(x:) or neighbors of node in supp(æ:)). See, for example, Algorithm 1 from Yang & Fountoulakis (2023) which provides a local algorithm for solving the 2--ormm flow diffusion problem (2). Recall that the amount of source mass controls the size of supp(x!), ). In the above setup, 0 controls the amount of source mass, and since T for
all we have supp x S 6. Applying the complexity results in Fountoulakis et al. (2020): Yang Fountoulakis 2023). , we immediately get that the total running time of the above steps are O (d6) where d the maximum node degree in supp(x*).
). This makes the running time independent of [V]
Given source mass 0 2 the seed node, let (8) and xt (6) denote the solutions obtained from solving ( over G and G",, respectively. Theorem 3.4 provides a lower bound on the Fl score obtained by supp(x! (0t)) with appropriately chosen source mass 01, addition, gives a sufficient condition on the label accuracy ag and a₁ such that flow diffusion over G with source mass Ø at the seed node results in a more accurate recovery of K than flow diffusion over G with any possible choice of source mass. For the sake of simplicity in presentation, Theorem 3.4 has been simplified from the long and more formal version provided in Appendix A Theorem A. The long version requires weaker assumptions on p, and provides exact terms without involving asymptotics.
Theorem 3.4 (Simplified version). Suppose that p = w( Vo
and q= w( ((on With probability
vk
at least 1/k, there is set K' C K with cardinality least |K// and choice of source mass of, such that for every seed node s E K' we have
1 (1 (1-a1) 01) (1 (1-0a)
un)
(1- a0)
(1sspp((=*(0))
-Ix()
(5)
2
24
201

---

Published as a conference paper at ICLR 2024
Furthermore, the accuracy of noisy labels satisfies
Vpp/7 + 201 - 11) 11 a1) 7 + on (1),
0g 2 1
then we have (()supppx!(()))
maxa20 Fl (Isupp((" (0))).
Theorem 3.4 requires additional discussion. First, the lower bound in ( increases with dg, ai and y This naturally corresponds to the intuition that, as the label accuracy do and @1 become larger, we can expect a more accurate recovery of K; while on the other hand, as the local graph structure becomes noisy, i.e. as 7 becomes smaller, it generally becomes more difficult to accurately recover K. Note that when dg = a1 = 1, the labels perfectly align with cluster affiliation, and in this special case the lower bound on the F1 score naturally becomes 1 o% (1). This means that the solution xf over the weighted graph G fully leverages the perfect label information. Finally, notice from (5) that the F1 is lower bounded by constant long y Sr, (1), even if an is low 1/2. In comparison, under a typical local clustering context where k < n, the Fl score obtained from directly using the noisy labels can be arbitrarily close to 0, i.e. we have F1 (Y)) S o (1), as long as ao is bounded away from 1. This demonstrates the importance of employing local diffusion. Even when the initial labels are deemed fairly accurate based on dg and @j e.g. still be very low. In the next section, over both synthetic and real-world data, we show empirically that flow diffusion over the weighted graph G can result in surprisingly better Fl even when the Fl of labels very poor.
1, ag = 0.99, the Fl score of the labels can
Second, if a1 then becomes
@p 21 (V1- oz().
Observe that: (i) The function /22+ +p- -y is increasing with 7, therefore the left-hand side of 7 increases as 7 decreases. This corresponds to the intuition that, as the external connectivity of the target cluster becomes larger (i.e. as y decreases), we need more accurate labels to prevent a lot of mass from leaking out. (ii) When q 2 Q - we have p/y 2 S2(1), and (7) further simplifies to expect that flow diffusion over GO to give
ag 2 1 22 In this case, if y is also constant, better result even if a constant fraction of labels is incorrect. Here, the required conditions on and may look bit strong because we did not assume anything about the graph structure outside K. One may obtain much weaker conditions than 6 or (7 under additional assumptions on K
EXPERIMENTS
In this section, evaluate the effecttivnness of employing flow diffusion over the labgh-weighted graph G whose edge weights are given in (4) for local clustering. We will refer to it as Label- based Flow Diffusion (LFD). We compare the results with the standard fz-norm flow diffusion (FD) (Fountoulakis et al. 2020 Chen et al. (022). Whenever dataset includes node attributes, we also compare with the weighted flow diffusion (WFD) from Yang & Fountoulakis (2023). Due to space constraints, we only report experiments involving flow diffusion in the main paper. We carried out extensive experiments comparing Label-based PageRank (LPR) on the weighted graph G" with PageRank (PR) on the original graph G. The results are similar: LPR consistently outperforms PR. Experiments and results that involve PageRank can found Appendix [ addition, we show that our method is not very sensitive to hyperparameter choice (see Appendix (..)) and that our method maintains the fast running time of traditional local diffusion algorithms (see Appendix C.2).
We use both synthetic and real-world data to evaluate the methods. The synthetic data is used to demonstrate our theory and show how local clustering performance improves as label accuracy increases in controlled environment. For the real-world data, we consider both supervised (i.e. we have access to both node attributes and some ground-trume trrnt labels) and unsupervised (i.e. we have access to only node attributes) settings. We show that in both settings, one may easily obtain reasonably good node labels such that, leveraging these labels via diffusion over G leads to consistently better results across all 6 datasets, improving the F1 score by up to 13%.
4.1 EXPERIMENTS ON SYNTHETIC DATA
We generate a synthetic graph using the stochastic block model with cluster size l = 500 and number of clusters 20. The number of nodes in the graph equals kc 10, 000. Two nodes within
7

---

Published as a conference paper at ICLR 2024
the same cluster are connected with probability p 0.05, and two nodes from different clusters are connected with probability
0.025. For edge weights (4) in G we set = 0.05. We vary the label accuracy ag and d defined in (3) to demonstrate the effects of varying label noise. We consider 3 settings: (i) fix dg = 0.7 and vary E [1/2, 1); (ii) fix dj = 0.7 and vary Ag E [1 /2, 1 (iii) vary both ag; 01 [1/2, 1) the same time. For each pair of (4g, a1),
run 100 trials. For each trial, we randomly select one of the 20 clusters as the target cluster. Then we generate noisy labels according to dg and d₁. For each trial, we randomly select a node from the target cluster as the seed node. We set the sink capacity T; = for all nodes. For the source mass at the seed node, we set it to ak for a = 2, 2..5..... 4, out of which we select the one that results in the highest Fl score based on supp(x") ) where x² is the optimal solution of the flow diffusion problem (2)
We compare the F1 scores achieved by FD and LFD over varying levels of label accuracy. Recall that FD does not use and hence is not affected by the labels at all, whereas L.FD uses label-based edge weights from (4). The results of over 100 trials are shown in Figure In addition to the results obtained from flow diffusion, we also include the FI scores obtained from the labels alone (Labels), Le. we compare Y = {i E V D1 = }} against K. Not surprisingly. as predicted by (5). the Fl of LFD increases as least one of ao, d1 increases. Moreover, LFD already outperforms FD at reasonably low label accuracy, e.g. when ag. Q1 = 0.7 and the F1 of the labels alone is as low as 0.2. This shows the effectiveness of incorporating noisy labels and employing diffusion over the labgh-weighted graph G". Even fairly noisy node labels can boost local clustering performance.
0.9 -8
FD
0.9
FD
0.9
FD
++ LFD
LFD Label
UTD Labels
3.7 Labels
2.6
0.5
0.6
0.5
0.4
333
0.3
0.3
0.5
0.9 0.5 0.7 0.9
0.5 0.6
0.7
1.5
0b.
Figure 2: Fl scores obtained by employing flow diffusion over the original graph (FD) and the label- weighted graph (LFD). For comparison, we also plot the F1 obtained by the noisy labels (Labels). The solid line and error bar show mean and standard deviation over 100 trials, respectively. As discussed in Section 3.1 even fairly noisy labels can already help boost local clustering performance.
4.2 EXPERIMENTS ON REAL-WORLD DATA
We carry out experiments over the following 6 real-world attributed graph datasets. We include all datasets used in Yang & Fountoulakis (2023) -namely, Amazon Photo (McAuley et all 2015). Coau- thor CS, and Coauthor Physics (Shchur et al.) 20088 to ensure compatibility of results. Additionally, we use 3 well-established graph machine learning benchmarks: Amazon Computers (Shchur et al. 2018), Cora (McCallum et al. 2000) and Pubmed (Sen al., 2008). We provide the most informative results in this section. Detailed empirical setup and additional results are found in Appendix [
We divide the experiments into two settings. In the first, we assume access to a selected number of ground-truth labels, evenly sampled from both the target and non non-target classes. These nodes are utilized to train a classifier (without graph information). The predictions of the classifier are then used as noisy labels to construct the weighted graph G as defined in (4). and we set c = 0.05 as in the synthetic experiments. We use all the positive nodes, i.e. nodes that belong to the target cluster based on the given ground-truth labels, as seed nodes during the diffusion process. For each cluster in each dataset, we compare LFD against FD and WFD over 100 trials. For each trial, a classifier is trained using randomly sampled positive and negative nodes which we treat as ground- truth information. Figure 3 shows the average Fl obtained by each method versus the number of samples used for training the classifier. As illustrated in Figure 3 using the outputs from weak classifier (e.g. with an Fl score as low as 40%) as noisy labels already enhances the diffusion process, obtaining an improvement as high as 13% over other methods (see Coauthor Physics with 25 positive and negative
We do this for our synthetic experiments to illustrate how label accuracy affects local clustering performance. In practice, without the ground-truth information, one may fix reasonable o, e.g. 2, and then apply sweep-cut procedure x². We adopt the latter approach for experiments on real-world data.
8

---

Published as a conference paper at ICLR 2024
Conuthor
Coeuther Physics
Amazon Photo
Amazon Computers
0.8-
1.5
0.7-
1.10
00-
Ceaoeer
0.3
VID
041
Cora
P_bmed
0.7
0.70
0.0
0.35
25
57
150
25
30
100
Supersised points
Supervised
Figure 3: F1 scores for local clustering using Flow Diffusion (FD), Weighted Flow Diffusion (WFD), Label-based Flow Diffusion (LFD), and Logistic Regression (Classifier) with increasing number of positive and negative ground-truth samples.
nodes). The increasing availability of ground-trute positive nodes typically benefits all diffusion processes. However, outside the target class and hence result in lower accuracy. such cases, the learned classifier mitigates this problem by reducing inter-edge weights.
in Cora, additional seed nodes can also increase the risk of mass leakage
In the second set of experiments, we consider the setting where we are only given a single seed with access to ground-truth labels pre-trained elassifier. To demonstrate the effectiveness of our method, a heuristic approach is adopted. First, we solve the flow diffusion problem (2) over the original graph G and get solution x². Then, we select 100 nodes with the highest and lowest values in xx,, which are designated as positive and negative nodes, respectively. We use these nodes to train binary classifier. As demonstrated in prior work (Fountoulakis al. 2020; Yang & Fountoulakis 2023), nodes with the highest values in x typically belong to the target cluster, whereas nodes with the lowest values in x² - typically zero - are outside of the target cluster. We use the outputs the classifier as noisy node labels to construct the weighted graph G", We test this approach against the standard and weighted flow diffusion, both in the single and multi-seed settings. the multi-sced setting, the 100 (pseudo- poositvvv nodes are used seed nodes. Additionally, for each dataset, compare LFD with the best-performing baseline and report the improvement in Table T The results demonstrate consistent improvement of LFD over other methods across all datasets.
Table 1: Comparison of Fl scores across datasets for Flow Diffusion (FD), Weighted Flow Diffusion (WFD), and Label-based Flow Diffusion (LFD) in the absence of ground-truth information
Dataset
FD (single-seed) seed)
WFD (single seed)
FD (multi seed)
WFD (multi (malli-seed) seed)
LFD
Improv. (+)
Improv. (%)
Coauthor CS
43.8
39,9
47.1
63.1
+12.6
+24.9
Coauthor Physics
62.8
57.0
55.5
51.1
72.9
+10.1
+16.1
Amazon Photo
54.5
57.4
62.1
62.6
66.8
+4,2
+6.7
Amazon Computers
56.2
53.3
58.2
54.6
60.4
+2.2
+3.8
Cora
33.3
33.7
55.4
55.4
56.5
+1.1
+1.9
Pubmed
53.0
53.2
53.9
53,9
55,3
+1.4
+2.7
AVERAGE
50.6
49.1
55.9
54.1
62.5
+5.3
+9.3
CONCLUSION
introduce the problem of local graph clustering with access to noisy node labels. This new problem setting serves as proxy for working with real-world graph data with additional node information. Moreover, such setting allows for developing local methods that are agnostic to the actual sources and formats of additional information which can vary from case to case. We propose simple label-based based edge weight scheme to utilize the noisy labels, and we show that performing local clustering over the weighted graph is effective both in theory and in practice.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
K. Fountoulakis would like acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Cette recherche a été financée par le Conseil de recherches en sciences naturelles en génie du Canada (CRSNG), [RGPIN-2019 04067, DGECR-2011 NETER-2011-0011477
S. Yang would like to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
REFERENCES
Z. Allen-Zhu, Silvio, and S. M. Vahab. local algorithm for finding well-connected clusters. In International Conference on Machine Learning (ICML), 2013.
R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. IEEE Symposium on Foundations of Computer Science (FOCS), 2006.
R. Andersen, O. Gharan, Y. Peres, and L. Trevisan. Almost optimal local graph clustering using evolving sets. Journal of the ACM, 63(2), 2016.
L. Chen, R. Peng, and D. Wang. 2-norm flow diffusion in near-linear time. In IEEE Symposium on Foundations of Computer Science (FOCS), 2022.
K. Choromanski. Taming graph kernels with random features. In International Conference on Machine Learning (ICML). 2023.
P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S.-H. Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow undirected graphs. ACM Symposium on Theory of Computing (STOC), 2011.
F. Chung. A local graph partitioning algorithm using heat kernel pagerank. Internet Mathematics, 6 (3):315-330, 2009.
C. Eksombatchai, Jindal, Liu, Y. Liu, Sharma, C. Sugnet, Ulrich, and J. Leskovee. Pixie: A system for recommending 3+ billion items to 200+ million users in real-time. In Proceedings of the 2018 World Wide Web Conference (WWW), 2018.
K. Fountoulakis, F. Roosta-KKoortt Khorasann,,,,,i, J. Shun, X. Cheng, and M. W. Mahoney, Variational perspective on local graph clustering. Mathematical Programming, 174:553-573, 2017.
K. Fountoulakis, D. Wang, and S. Yang. p-norm flow diffusion for local graph clustering, International Conference on Machine Learning (ICML), 2020.
K. Fountoulakis, P. Li, and S. Yang. Local hyper-flow diffusion. In Advances Neural Information Processing Systems (NeurIPS), 2021.
K. Fountoulakis. M. Liu. D. Gleich, and M. W Mahoney. Flow-based algorithms for improving clusters: unifying framework, software, and performance. SIAM Review, 65(1):59-143, 2023.
D. Gleich. Pagerank beyond the web. SIAM Review, 57(3):321-363, 2015. 2015.
W. Ha, K. Fountoulakis, and M. W. Mahoney. Statistical guarantees for local graph clustering. The (005)6638865991 2021.
Journal of Machine Learning Research,
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations (ICLR), 2017.
I. M. Kloumann and J. M. Kleinberg. Community membership identification from small seed sets. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2014.
M. Liu and D. F. Gleich. Strongly local p-norm-cut algorithms for semi-supervised learning and local graph clustering. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
10

---

Published as a conference paper at ICLR 2024
P. Macgregor and H. Sun. Local algorithms for finding densely connected clusters. In International Conference on Machine Learning (ICML), 2021.
M. W. Mahoney, L. Orecchia, and N. K. Vishnoi. A local spectral method for graphs: With applications to improving graph partitions and exploring data graphs locally. The Journal of Machine Learning Research,
01:2339-23655 2012.
D. Martinez-Rubio.
Wirth, and S. Pokutta. Accelerated and sparse algorithms for approximate personalized pagerank and beyond. In Proceedings of Thirty Sixth Conference on Learning Theory (COLT), 2023.
J. McAuley, C. Targett, Q. Shi, and A. Van Den Hengel. Image-based recommendations on styles and substitutes. In ACM International Conference on Research and Development in Information Retrieval (SIGIR), 2015.
A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
L. Orecchia and Z. A. Zhu. Flow-based algorithms for local graph clustering. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
B. Perozzi, R. AI-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2014.
A. Reid and P. Yuval. Finding sparse cuts locally using evolving sets, ACM Symposium on Theory of Computing (STOC), 2009.
Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
Shi, He, D. Bindel, and J. Hopcroft. Local Lanezos spectral approximation for community detection. In European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2017.
D. A. Spielman and S.-H. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal on computing, 42(1):1-28 2013.
H. Sun, F. He, J. Huang, Y. Sun, Y. Li. C. Wang, Liang He, Z. Sun, and X. Jia. Network embedding for community detection in attributed networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(3):1-25, 2020.
D. Wang, K. Fountoulakis, M. Henzinger, M. W. Mahoney, and S. Rao. Capacity releasing diffusion for speed and locality. International Conference on Machine Learning (ICML), 2017.
J. Weng, E.PP. Lim, J. Jiang, and Q. He. Twitterrank: Finding topic-sensitive influential twitterers. In ACM International Conference on Web Search and Data Mining (WSDM), 2010.
W. Xie, D. Bindel, A. Demers, and J. Gehrke. Edge- weighte personalized pagerank: Breaking decade-old performance barrier. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2015.
W. Xing and A. Ghorbani. Weighted pagerank algorithm. In IEEE Annual Conference on Communi- cation Networks and Services Research (CNSR), 2004.
J. Yang, J. McAuley, and J. Leskovec. Community detection in networks with node attributes. In IEEE International Conference on Data Mining (ICDM), 2013.
S. Yang and K. Fountoulakis. Weighted flow diffusion for local graph clustering with node attributes: an algorithm and statistical guarantees. In International Conference on Machine Learning (ICML), 2023.
11

---

Published as a conference paper at ICLR 2024
H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich. Local higher-order graph clustering. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Association for Computing Machinery. 2017.
C. Zhe, A. Sun, and X. Xiao. Community detection on large complex attribute network. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In Advances neural information processing systems, 2003.
12

---

Published as a conference paper at ICLR 2024
A FORMAL STATEMENT OF THEOREM 3.4 AND PROOFS
For convenience let us remind the reader the notations that we use. We use K C V to denote the target cluster and we write K V.K. Each node i E V comes with noisy label 9s E {0, 1)- For c {0, } we write Y, {i V yi c). The label accuracy are characterized by ao = k Yo | and a1 KK K Given a graph G (V, and a target cluster K
generated by the random model in Definition 3.2 let v == [V], k: = |K], and == m(k=1) Given
q(n-
edge weight E R or equivalently vector w [F| let G denote the weighted graph obtained by assigning edge weights to G according to w. our analysis we consider edge weights given by (4) that is j(
if ÚJ Øj. and w(i,j)
if Y; Új. and set 0.
Recall that the l-- noro flow diffusion problem 2 is set up as follows. The sink capacity is set to T, for all i E V. We set T, instead of T, dega (i) used in Fountoulakis et al. (2020) because it allows us to derive bounds on the F1 score in a more direct way. In practice, both can be good choices. For given seed node K, we source mass A, = 0 node for some 0 >> and we set A = 0 for all other nodes * s. Given source mass 0 at the seed node, let x (0) and (0) denote the solutions of the fo-norm flow diffusion problem (2) over G and G respectively.
We write x" (0) and (f) to emphasize their dependence on A. When the choice of 0 is clear from the context, we simply write x" and xt.
We state the formal version of Theorem 3.4 below in Theorem A.1 First, let us define two numeric quantities. Given 0 < 81, 62 6g I 1, let
(1 + 81 (1) + 81 + 2 and r= r -1)))
p(K-TT) 51)(1 82))
Theorem A.1 (Formal version of Theorem 3.4
Suppose that p 2 max (6+e1) log (v8+ea) Mogg
8f
k-2
82V1-81 vk-
and q 2 (3-ea) log for some E1, E2, 63 > O and O < 81, d2, 83 S L. Then with probability at least
og
1 /// -k k-ea - k-/3/ there is set K' S K with cardinality least K1/2 2 and choice of source mass 8t, such thatfor every seed node s E K' with source mass H at the seed node, we get
((())))(=*(0)))) 2 1
d1 2
017
(k
2)
+ +1 0p)
r-1 1 +
al
(8)
(k-2)
2
a17
(K-1)
In this case, if the accuracy of noisy labels satisfies,
(/(r +
(k- - 2) (k - 1) rd
p/7
201 1) 01 a1 )
On 2
(9)
r
then we have
Fl (supp( (0l)) > max Fl (suppp<> (0))).
020
Outline: The proof is based on (1) lower bounding the number of false positives incurred by supp(>") (Proposition A.2). (2) upper bounding the number of false positives incurred by supp(=") (Proposition A.3), and (3) combine both lower and upper bounds.
We will use some concentration results concerning the connectivity of the random graphs G and results are mostly derived from straightforward applications of the Chernoff bound. For completeness we state these results and provide their proofs the end of this section.
Let å denote a generic optimal solution of the flow diffusion problem which is obtained over either G or G We will heavily use the following two important properties of & (along with its physical interpretation). We refer the reader to Fountoulakis et al. (2200) for details.
1. The solution R" defines a flow diffusion over the underlying graph such that, for all i, V. the amount of mass that node i sends to node along eege (i, is given by w(i,)) (i; 2z).
2. For all E V, 2; > only if the total amount of mass that node has equals T,, i.c. A, Ejer w) (#g (x)) Tí.
13

---

Published as a conference paper at ICLR 2024
3. For all i E V, Rt 0 if and only if the total amount of mass that node i receives exceeds T,, i...
Á + Enm,,, w(i,j) :) (2) - ..)) > Tç.
Using these properties we may easily obtain a lower bound on the number of false positives incurred by supp(x*). ). Recall that x² denotes the optimal solution of (2) over G, with sink capacity T, 1 for all i. We state the result in Proposition A.2
Proposition A.2. If 2
(3++) log for some e > O and 0 < ò S 1, then with probability at least
8² n-k
1 --/3 e/ee//for for every seed node s K, if (s/ssppp"")) 2 2 then we have that
|supp(x") n > (1 8) _
Proof. If |supp(>*)] 2 2 means that x² > 0 as otherwise we must have 0. Moreover, let i E V be such that # and x; 2 27 for all j * s. Then we must have that is a neighbor of s. Because A; = x > 0 and x; 2 2z for j o s, we know that the amount of mass that node sends to node i is strietly larger than 1, and hence x², > 27 + 1 >> 1. But then this means that we must have x > O for all ~ 8. By Lemma A.4 we know that with probability at least - k-</3, every node E K has more than (1 - 6) k) neighbors in KS, This applies to s which was chosen arbitrarily from K. Therefore we have that with probability at least - kee/s, for every seed node E K, if [supp(x*)] 2 2 then (supp(x*) n K > (1 8))(n k). The required result then follows from our definition that q(=-k]"
p(k-1)
On the other hand, Proposition A.3 provides an upper bound on the number of false positives incurred by supp(x!) under appropriately chosen source mass ot at the seed node. Its proof based on upper bounding the total amount of mass that leaks to the outside of the target cluster during a diffusion process, similar to the strategy used the proof of Theorem 3.5 in Yang & Fountoulakis (2023).
Proposition A.3. 1fp 2 max(
(6+r)) logk (VR+c2) Vlogky for some 0 < 88, 52 S and 61, 0,
of k-2 82v1-60 vk-2
then with probability at least /6/ - for every seed node K YY with source mass
(k-2) a17
[k-1] + (1 ao)
2
razk,
(k-2)
017 (k-1)
we have that K n Vi C supp(ot) and
a17 (17 (k-2)
(k-1) + (1 au)
supp(x*) (Kpp 5
r-1 axk.
(k-2)
a1 (k-1)
Proof. To see that yi S supp(x*)) let us assume for the sake of contradiction that a! = 0 for some E n n.. This means that node receives at most unit mass, because otherwise we would have x > 0. We also know that / 8 because A, > Denote == (j E K Kn : s). We will consider two cases depending on if e F or not.
Suppose that i F. Then have that x² x < 1 because node i receives at most 1 unit mass from node 8. This means that x S + x = 1. follows that the total amount of mass which flows out of node is
Σ (x) x1) < Σ 2 < dego (s) < (1 (plank 1) + (1 a0)g(n k)), Erus
8o08
14

---

Published as a conference paper at ICLR 2024
where the last inequality follows from Lemma A.5 Therefore, get that the total amount of source mass is at most
Øt $ (1+ - + (1 an)g(n - k))
= (1 + 6)p(a,k - a1p(k 1/a1) (1 a0 a0)g(n k)
aip(k - 1/a1)
(1 8)p(a)kpp1k)) a17 (1-1/a11 (1- a0)
(k-1)
+1
(k-1/as)
017 (k-1)
(2-2) + (1 ao)
a17 18-13
< (1 + 5)p(ark-
+1
(k-2)
017 (k-1)
017 (k-2) (1 ao)
$ (1+ 51 2//b)
(k-1)
ajk < 1
(k-2)
a1 (R-1)
where the second last inequality follows from a₁ 2 1/2. This is a contradiction, and hence we must have i & F.
Now, suppose that &f F. Then we know that the total amount of mass that node receives from its neighbors is at most 1. In particular, node i receives most I unit mass from nodes in F. This means that
Σ m
- - $1. S1.
j-i
jui
JEF
JEF
By Lemma A.6 we know that with probability at least 1 - 2k- k2 node i has at least (1 (1) 02 (a,k: h 1) neighbors F, and thus
Σ Eafs1=
min 2f JEF (1 11-1))11 -1-b)11163)pp(a 62)p
JEF j.si
Therefore, let j E F node such that æ/} S x for all E F, then with probability at least 1 -1 1 t2,
z) S (1- - (a
(10)
By Lemma A.6 with probability least 1 -1/ k² node j has least (1 81) (apk - 1) neighbors in F. Since z/ S x for all l F and x²} S æ!, we know that
He j and x 2 vr H 2 (1 - 8, (1 - 52)x² (a, - 1).
(11)
Therefore, with probability at least 34 1 /3 k 2 the total amount of mass that node sends its neighbors is at most
Ear (nj
x/) <
(1)
- xt)) <
Σ
Eng 2!52]
[-
x152]
@
(11+6)(6p(akk - 1) (1-an)q(n k:)) (1 61)(1111111 -2)pp 11) 11)
(1 (1+
11) (1 )n) - k)
-1.
(1 (1-61)(1- 82)
(aakk111))
where (i) follows from Lemma A.5 and (1 and (ii) follows from (1O). Since node settles unit
mass, the total amount of mass that node j. receives from its neighbors is therefore at most
(1 + 61)
p(aakk 1) + (1 an)g(n - k)
- 1-),111- -5,)
15

---

Published as a conference paper at ICLR 2024
Recall that the amount of mass that node receives from node is given by x 15- xz.. and hence
get
(1 (1+5)) m S (1 - 61)(1 - 52)
- (1 (1- k.) + aj..
(12)
pa
Apply the same reasoning as before, we get that with probability at least 1 1- -1/6/ k= the total amount of mass that is sent out from node s is
E(sl - x/)) < dego (8) 2a S (1 + 81)(((ak - 1) + ao)g(n -a)) x!!
Eru
(1 + 61)
(11+ (plark (1 1) + (1 - an)g(n 2
(1 61)(1 52]
p² 1)²
plank 1) + (1 10)g(n k)
(ark 1)
p2 (01 k - 1)2
(m))
(1+68)(11+ + +01 p(k
p(ajk - 1) (1 10)g - k))
?
(ark: 1)
(1-6))(1 - 82)
pla,k 1 - 1)
+ +5 + 2
a17 (k-1/a1)
(k-1) + (1 - an)
2
(
p(k-I)
(ath: 1)
(1 (1-81)(1 (8)
(k-1/a1)
017 (k-1)
a17 (k-2) (K-1) + (1 an)
2
+1 + p(k
(a.k: 1),
61 82)
(k-2)
a (x-1)
where (i) follows from Lemma
A.5
(ii) follows from 10) and 12 (iii) and (v) uses on 2 1/2, and p(k-1) This implies that the total amount of source mass is q(n-k)
(iv) follows from the definition
gt < (1 (1+ + +. + p(k-T) (1-8)((1- -52)
@1 #1
(k-2) + (1 on)
azk a=k=
(k-2) at (K-1)
which is contradiction. Therefore we must have i & Kny, but then this contradicts our assumption
that E K i Yi. Since our choice of i, K₁ were arbitrary, this means that x!! 0 for all i K₁ and for all s E K1.
Finally, the upper bound on |supp(=t) n nX follows directly from the fact that x! > only if node settles I unit mass.
By Proposition A.2 the F1 score for supp(>*) most
2k
Fi(supp(a)))
2k + (1 - 83) 1)/7
By Proposition A.3 the Fl score for supp(x!) is at least
2k:
(s(upp((*))) 2
(k-2) a17 (k-1) + (1 ao)
2k +
r r-1
0ik + (1 a1)h
(k-2)
a17 [K-1)
16

---

Published as a conference paper at ICLR 2024
Therefore, sufficient condition for FI(supp(=*)) Fl (((upp((z*) is
017 017 [R-1] + (1 an)
(k-2)
2
(k -1-1
r-1
a1 (1 (1-a)) s (1 63)
(K-2)
? k
a17 (k-1)
(k-2) 017 [k-1)
+ (1 - 00)
2
al
(1 (1- 03)
p (A: -6)
+ 201 -1)
- r
(k-2)
? h:
(k-1)
(k - 2)
(k: 2)
P
(k (k-1)
-6) + 2a1 -1)
017
(k
+ 1 ao S
7
(k 1) V r
(1 - 03)
7 k
(k 2)
(1/7
1//7
201 -
1) V = = (k
a1
ag 1 (k 2 2) kk -8-1) 1)
p/7 pd
+ 2a1 1
01
a1
7.
Finally, setting K' = K i Vi completes the proof of Theorem A.1
A.1 CONCENTRATION RESULTS
Lemma A.4 (External degree in G). If 2 (3+c) log
5 n-E for some 0 and 0 < 6 S 1, then with
probability at least -c/3 we have that for all i K,
(((i),K) 2 (1 - 85)((n (ap(n-Mp - k).
Proof. This follows directly by noting that, for each i E K, |E(fi), K9 is the sum of independent Bernoulli random variables with mean q(n - k). Applying a multiplicative Chernoff bound on [E((}, K9] and then union bound over i E K gives the result.
Lemma A.5 (Node degree in )D)). I 2
(6+c) log k-2 for some 0 and 8 S 1, then with
probubility at least 1 h--/6 we have that for all i E K KnB Vi,
dega (1) S (1 (p((azk 1) + - -00)aaagnnnn kk))
Proof. For each node i E K n Yr, since K n = aık and K K (1 (1- cn) - k). its degree in G that is dego- (i), is the sum of independent Bernoulli random variables with mean
E(dego" (i)) = pla,k- - 1) + (1 an)g(n k) 2 p(a,k - 1) 2
[3+r/2] log k. Apply the Chernoff
6"
bound get
IP (deg@ (i) 2 (1 + B(dego (i)) < exp(- E(deg (1))3) S exp(((1++ log
Taking a union bound over all E K n Ý1 gives the result.
Lemma A.6 (Internal connectivity in G If 2 max( (G+e1) log (VS+ea) ylog
of k-2 62v1-1 vk=2) then with
probability at least 1 - -// k k we have that for all i,j E K nY where i + j. there are at least (1 - 61)(1 62)p² (a1 - 1) distinct paths connecting node to node such that, each of these paths consists of at most edges, and each edge from G appears in at most one of these paths.
Proof. Let F; denote the set of neighbors of a node i in K Pg. By our assumption that p 2 (6+e1) logk of 2- we may take a Chernoff bound on the size of F; and a union bound over all i E Kn V
to get that, with probability at least 1 - 2k -
61 61)p(ark 11) < R S (1 + 51)p(ark 1), We Wek.
17

---

Published as a conference paper at ICLR 2024
If j & Fú. then since [E()), , Fi)) is sum of independent Bernoulli random variables with mean [Flpp, may apply the Chernoff bound and get that, with probability at least 1 2k -1/6 (under the event that (1 - 61)p(ark - 1) = [ - (1 51)p(ark - -)),
P(IE((), F.) S (1 62)1 Pi S exp( - Ftlp/2) - exp( 1 -52(1 (011-))p- b1)p((rkk - 1)/2))
S exp(-(22 c2) +2)
logh).
(13)
(vS+ea) ylog If F. The last inequality in the above follows from our assumption that p 2 8 vk-
then the edge (i,j) is path of length 1 connecting, j to i, and moreover, let l E K o Vi be such that l & F; and & o i, we have that
F2pp - F() S (1- (1-
S cxp((-2++c)
log k)),
where the last inequality follows from 13). Note that, for a node j in K n y2 such that j * i, each edge (i,)) E F(D)).MM)) identifies unique path (j. and none of these paths has overlapping edges. Therefore, denote j) the set of mutually non-overlapping paths of length at most 2 between i and j. and take union bound over all i,j E n Y1. we get that
P( E K KY, j,s. P(r, j) (1 12)p k
Finally, taking uninon bound over the above event and the event that there is i E K KnY such that [R] < (1)ak))pa 1) gives the required result.
B DISCUSSION: How TO SET EDGE WEIGHT E IN GD UNDER THE LOCAL RANDOM MODEL (DEFINITION 3.2)
Given graph G = (V, F)) generated from the local random model described in Definition 3.2 noisy labels ÿt for node i E V, recall from (4) that the edge weights in G are such that ((i = 1 YJ Vj and w({
otherwise. Our analysis in Section 3 takes = O. While understanding diffusion in G" with c = already provides us with some insights with regard to how noisy labels can be useful, natural extension of our analysis is to determine an "optimial" given model parameters n, k p. q and label accuracy ap, ai
To see why this is interesting problem, consider the case when d1 is low. In this case, if we set e = 0 and start diffusing mass from a seed node & E K with D. = 1, then diffusion in G" cannot because the graph G is disconnected with two components Yi = {i E V : 3 1} and Yo = {i E V : 9; = 0}. Consequently, the recall of the output cluster is at most d1. On the other hand, if we instead set > O, this allows diffusion in G to reach node i K whose label SA- = however, at the same time, diffusion in G incurs the risk of reaching node i & K whose label is h = 0. Therefore, setting e >> 0 allows for discovering more true positives at the expense of incurring more false positives. Whether one should set e = will depend on n. k P. q, 4n, 41 and the accuracy metric (e.g. precision, recall, or the F1) one aims to maximize. If maximize recall, then is easy to see that one should set > to allow recovering nodes in K that receive different noisy labels. In general, it turns out that rigorously characterizing an "optimal" e that maximizes other accuracy metrics such as the Fl nontrivial. what follows we discuss intuitively the potential conditions under which one should set 0 or 0 to obtain better clustering result which balances precision and recall, i... attains a higher F1. In addition, we empirically demonstrate these conditions over synthetic data.
reach a node E K such that Tt
the objective
Conjecture I: A sufficient condition to favor e > 0 is (1 - a1)pk > aog(n - k).
Conjecture 2: A sufficient condition to favor = 0 is a1-a1)p²t
aog²(1) (n- k).
We provide an informal explanation for these conditions. Note that if seed node s is drawn uniformly at random from K, then with probability 01 2 1/2 we get that s K n Y,. Therefore let us assume that a seed node is selected from K Y, In this case, since the diffusion of mass starts from within K n Yi, excess mass needs to get of K Y, along the cut edges of K n Yi. Let focus on the edges between K 0 Vi and Yo since these are the edges affected by The edges between
18

---

Published as a conference paper at ICLR 2024
KnY and K n Y1 are not affected by c. In expectation, every node in K n Yy has (1 a1 ppk number of neighbors in K Yg and ang(n k) number of neighbors in K n Vo. Therefore, in diffusion step when we push excess mass from node in K n Y its neighbors, for every (1 (1-a1 (-aa)p ay)pk unit mass that is pushed into K n Yo, on average agg(n - k) unit mass is pushed into K If (1 (1-00 ai )pk > ang(n - k). then this means that K Yo receives more mass than K r Yo. Consequently, as a result of K n Yo receiving more mass than R n Y, from diffusion step within K Y1, we can expect that by setting e > 0, we obtain more true positives as the diffusion process covers nodes in K n Yg at the expense of fewer false positives as the diffusion process covers less nodes in Kº n Yo. This leads to our first conjecture on the condition to favor > over e 0.
For the condition in our second conjecture, note that even when K n Yo receives less mass from K Y than the amount of mass that K Yo receives from K n Fi, it does not necessarily imply that we would get more number of false negatives from K n Yo and fewer number of true positives from K n %o- Recall that we use supp(#") ) as the output cluster where x² is the optimal solution of the diffusion problem (2). For a node E V. we know that oद >> 0 only if node i receives more than 1 unit mass. Consider the following two average diffusion dynamics. First, as discussed before, for every (1 (1- p1kpk unit mass that is pushed into K nY, from the jipk nodes in K YY, on average (i.e. averaged over multiple nodes) ang(n ke) unit mass is pushed into K Yg. Second, in expectation. every node in K O Yo has aipk neighbors in K Vi and every node in K n Y. has aigh neighbors For every unit mass that moves from K Yi to K KnY, node in K n Yo on average (i.e. averaged over multiple nodes and multiple diffusion steps) receives paik/aik p unit and node in K n Yo on average receives gazk/ kajk/a k/akk q unit. Combining the above two points, we get that on average, for every (1 - aj ) unit mass received by node in K n Yg, node in K n Y, receives ang"(n - k) unit mass. Therefore, if (1 ai )y²k < oog (n - k). then setting e > 0 would make a node i E KS n Yo generally receive less mass than a node in j E K n Yo. Consequently, node j E K Yo is more likely to receive more than I unit mass. This implies that, by setting >> 0 we would get fewer number of true positives from K E Vn at the expense of incurring more number of false positives from KC n y- This leads to our second conjecture.
in K Y
Of course, rigorous argument justify both conjectures will require much more careful analysis of the diffusion dynamics and additional assumptions on p, q so that the average behaviors described in the above hold with high probability. In addition, there is a gap of order p/g between the two conditions. It is also an interesting question to determine good strategy to set e in that "gap regime". Addressing these questions are nontrivial and we leave for future work.
B.1 EMPIRICAL DEMONSTRATION OF OUR CONJECTURES
We demonstrate our conjectures when to set 0 or >> O over synthetic data. As in Section 4.1 we generate synthetic graphs using the stochastic block model with cluster size k = 500 an number of clusters 20. The number of nodes in the graph equals n = kc 10, 000. Two nodes within the same cluster are connected with probability and two nodes from different clusters are connected with probability q. We consider different choices for q, ao al such that the condition either Conjecture I or Conjecture 2 is satisfied. Other empirical settings are the same as in Section 4.1
In Table 2 we report the Fl scores obtained by setting e and 0.2, respectively. We average over 100 trials for each setting. For comparison purposes we also include the results obtained by employing Flow Diffusion (FD) over the original graph. Note that FD is equivalent setting e 1. Observe that, when (1 - a1 )pk >> aog(n nn- k) as required by Conjecture I, setting = 0.2 leads to a higher F1, whereas when (1 - a1 ) < aon? (n - k) as required by Conjecture 2, setting e = leads to a higher F1. This demonstrates both conjectures.
From a practical point of view, we would like to remark that real networks often have much more complex structures than the synthetic graphs. Therefore the same conditions may not generalize to the real networks that one would work with in practice. To that end, in Section C.1 we provide an empirical study on the robustness of our method with respect to different values of Our empirical results in Section Cindicatte that, over real networks, the local clustering accuracy remains similar for different choices of e, ranging from 0.01 to 0.2.
19

---

Published as a conference paper at ICLR 2024
Table 2:
Empirical demonstration of our conjectures: Fl scores for local clustering in the local random graph model with different model parameters and label accuracy
Empirical Setting
FD
LFD (e=0)
LFD (e=0.2)
|=0.05, 0.000, 40 01=0.6
69.2
64.5
77.8
Conjecture
p=0.05, (005:50=00001,000 4g0.6 0,
69.2
64.2
74.6
p=0.05, q-..05,0-000055,aa--- an 01
9.7
48.8
37.3
Conjecture
p=0.05, (00.0,,,0000055, a0=099 a1 01
9.7
76.7
61.1
C FURTHER EVALUATIONS AND COMPARISONS
C.I HYPERPARAMETHR ANALYSIS
In this section, test the robustness of our method against various choices of hyperparameters. There are hyperparameters in our method. The first hyperparameter is the edge weight E [o, 1) from ) and the second hyperparameter is the total amount of source mass at the seed node(s) to initialize the flow diffusion process.
We conduct a detailed case study using the Coauthor CS dataset. Similar trends and results are in the experiments using other datasets. We focus on the one of the empirical settings considered in Section 4.2] where we are given 10 positive and 10 negative ground-trute node labels. Apart from the choices for and 0, we keep all other empirical settings the same as in Section 4.2 We report the average local clustering result over 100 trails.
We vary the total amount of source mass 0 as follows. Set 0 (volg(()) and we let a E (2, 4, 5). Recall that K denotes the target cluster. Therefore picking a in the range of [2, results very large variations in 0. The experiments in Section 4.2 use = 2 and 0.05. Here, we present results using different combinations values for a and e. Observe that for fixed a E 3, 4), the maximum change in the Fl score across [10-2 10-1 '] is 1.2. Moreover, for all combinations of and a, our method has a much higher F1, highlighting the effectivess and robustness to incorporate noisy labels for local clustering.
Table 3: F1 scores for different values of source mass and inter-edge weight
LFD
a
FD
WFD
0.01
0.025
0.05
= 0.075
= 0.1
0.2
62.8
56.4
73.0
73.1
72.6
72.4
72.2
70.8
67.5
58.3
74.8
74.1
74.1
74.0
74.0
73.0
68.1
57.6
73.4
72.7
72.1
72.3
72.2
72.0
66.1
55.4
71.8
70.8
70.0
69.5
69.3
68.7
C.2 RUNTIME ANALYSIS
We report the running time of our Label-based Flow Diffusion (LFD) along with other flow diffusion- based local methods. The experiments are run on an Intel 19- 13900K CPU with 36MB Cache and 48GB DDR5 RAM. We highlight the fast running time of LFD. Fast running times typically seen in local methods and are due to the fact that these methods do not require processing the entire graph. The runtimes reported in Table 4 are based the experiments using the Coauthor CS dataset, averaged over 10 trials across 15 clusters.
C.3 COMPARISON WITH GRAPH CONVOLUTIONAL NETWORKS (GCNs)
Within the task of clustering or node classification the presence of ground node labels, is natural to extend the comparison other types of methods which exploit both the graph structure and node information. To that end, we provide an empirical comparison with the performance of GCNs in problem setting. Note that both the training and the inference stages of GCNs require
20

---

Published as a conference paper at ICLR 2024
Table 4: Average runtimes for different local diffusion methods
FD Fountoullkis al.
2020
WFD YYang & Fountoulakis 2023
LFD (ours)
Train model
0.09 + 0.01
Calculate weights
1.11 0.77
0.03 1 0.02
Diffusion process
0.01 0.01
0.01 + 0.01
0.01 0.01
TOTAL
0.01 +: 0.01
1.12 + 0.78
0.13 +: 0.03
accessing every node in the graph, and this makes GCNs (and more generally other global methods that require full graph processing) unsuitable for local graph clustering. In contrast, local methods only explore a small portion of the graph around the seed node(s).
To highlight the strengths of our local method against global methods such GCNs, we carried out additional experiments to compare both runtime and accuracy. Again, we fix the same empirical setting before, that is, we the Coauthor CS dataset and select 10 nodes each from positive and negative ground-truth categories. Let us remind the reader that, here, a positive ground-truv label means that node selected from the target cluster K given a label 1. Similarly, a negative ground-truth label means that a node selected from the rest of the graph is given a label O.
Table 5: Comparison between Label-based Flow Diffusion (LFD) and Graph Convolutional Network (GCN)
LFD
GCN
F1-score
73.0
46.9
Runtime
0.13 0.03
3.68
0.31
We use a two-layer GCN architecture with a hidden layer size 16. When training the GCN model, terminate the training process after 100 epochs. In our approach, each class is treated separately in one-vs-all classification framework during training. We replicate this procedure for each class across 10 independent trials. The results are shown in Table Observe that our method not only runs substantially faster (i.e. 28 times faster) than GCN but also obtains a much higher F1. The poor performance of GCNs is due the scarcity of ground -oound-truth data in our setting, where we only have 20 samples. GCNs generally require much greater number of ground-truth labels to work well. In order to make GCN achieve a better accuracy than LFD, we had increase the number of ground-truth labels to 600 samples, which is not very realistic for local clustering contexts.
D EXPERIMENTS
D.1 REAL-WORLD DATASET DESCRIPTION
Coauthor CS is a co-authorship graph based on the Microsoft Academic Graph from the KDD Cup 2016 challenge (Shchur et al. (2018)). Each node in the graph represents an author, while an edge represents the co-authorship of a paper between two authors. The ground-truth node labels determined by the most active research field of each author. The Coauthor CS graph consists of 18,333 computer science authors with 81,894 connections and 15 ground-trute clusters.
Coauthor Physics is co-authorship graph also extracted from the Microsoft Academic Graph and used in the KDD Cup 2016 challenge (Shchur et al. (2018)). Its structure is similar to Coauthor CS with focus Physics research. The dataset has 34,493 physics researchers and 247,963 connections among them. Each physics researcher belongs to one of the 5 ground-truth clusters.
Amazon Photo is co-purchasing graph from Amazon (McAuley et al. (2015) ), where nodes represent products and an edge indicates whether two products are frequently bought together. Labels of the nodes are determined by the product's category, while node attributes are bag-of-wor encodings of product reviews. The dataset consists of 7,487 photographic equipment products, 119,043 co-purchasing connections, and 8 categories
21

---

Published as a conference paper at ICLR 2024
Amazon Computers is another co-purchasing graph extracted from Amazon (Shchur et al. (2018)) with the same structure as Amazon Photo. has 13,752 computer equipment products, 245,861 connections, and 10 categories.
Cora (McCallum et al. (2000) is a citation network where each node denotes a scientific publication in Computer Science. edge from node A indicates a citation from work A to work B. Despite their directed nature, we utilize an undirected version of these graphs for our analysis. The graph includes 2,708 publications, 5,429 edges, and 7 classes denoting the paper categories. The node features are bag-of-wortd encodings of the paper abstract.
Pubmed (Sen et al. (2008)) is a citation network with a similar structure as Cora. We also adopt undirected version of the graph. The dataset categorizes medical publications into one of 3 classes and comprises 19,717 nodes and 44,338 edges. Node features are TF/IDF encodings from selected dictionary.
D.2 BEYOND FLOW DIFFUSION: EMPIRICAL VALIDATIONS WITH PAGERANK
In this section, we extend the comparisons beyond just flow diffusion, considering another local graph clustering technique, namely PageRank. We employ the f-rreuularized PageRank (Fountoulakis et al. 2017), demonstrating that the outcomes align consistently with those of flow diffusion. In the next sections, findings are reported for both Flow Diffusion (FD) and PageRank (PR).
SYNTHETIC EXPERIMENTS
IR
P2
0.7
Lubds
5.7
J0553
0.7
Libda
9.5
0.4
Figure 4: scores obtained by employing ferregularized PageRank (Fountoulakis et al. 2017 ) over the original graph (PR) and the label-weing weighte graph (LPR). For comparison, also plot the F1 obtained by the noisy labels (Labels). The solid line and error bar show mean and standard deviation over 100 trials, respectively.
REAL-WORLD EXPERIMENTS: LABEL-BASEE PAGERANK WITH GROUND-TRUTH DATA
3.50
Coather Phylo
Causthrr
Amaon
Ar Compstes
3.00
6220-
03
8.0
25
Cera
Pobreed
Supere dato
Supertied peRns
Figure 5: Fl scores across datasets for fe-reullrizzed PageRank, Label-based PageRank (LPR), and Logistic Regression (Classifier) with an increasing number of positive and negative ground truth samples
WORLD EXPERIMENTS: SINGLE SEED LABEL-BASEE PAGERANK WITH NO GROUND-TRUTII LABELS
22

---

Published as a conference paper at ICLR 2024
Table 6: Comparison of Fl scores across datasets for PageRank (PR) and Label-based PageRank (LPR) in the absence of supervised data.
Dataset
PR (singlo-seed)
PR (mulii-seed)
LPR
Improv. (#)
Improv. (%)
Coauthor CS
52.8
56.4
66.2
+9.8
+17.3
Coauthor Physics
63.4
61.9
72.1
+8.7
+13,6
Amazon Photo
64.2
63.8
67.6
+3,4
+5.3
Amazon Computers
57.7
63.2
+2.8
+4.7
Cora
55.7
58,5
60.6
+2.1
+3.5
Pubmed
56.1
54.9
58,8
+2.7
+4.8
AVERAGE
58.3
59.3
64.7
+4.9
+8.2
D.3. DETAILED RESULTS EXPERIMENT WITH GROUND-TRUTH DATA
In this subsection, we present detailed results from the first experiment with real-world data. We report the performance of the setting with 25 positive and 25 negative nodes. We employ Logistic Regression model with & regularization for binary classification. During inference, labels form weighted graph as described in with c 0.05, applied only over existing edges. In flow diffusion, the source mass of each seed node is assigned to be twice the volume of the target cluster. For PageRank, the starting scores of the source nodes are proportional to their degrees. The & regularization parameter for PageRank is set to be the inverse of the total mass dispersed in flow diffusion. Additionally, we execute a line search process to determine the optimal teleportation parameter for PageRank. After finishing each diffusion process, sweep-cut procedure is conducted on the resulting embeddings using the unweighted graph.
Table Fl scores for the Coauthor CS dataset with 25 positive and 25 negative nodes.
Cluster
CLF
FD
WFD
L.FD
LPR
Bioinformatics
85.5
45.8
61.9
Machine Learning
26.8
50.2
49.6
63.9
54.1
61.3
Computer Vision
79.4
64.8
38.5
82.4
60.9
71.2
4
NI.P
16.7
58.2
73.5
73.0
68.6
76.6
5
Graphics
52.8
76.8
75.5
85.7
74.1
79.2
6
Networks
79.5
67.7
64.4
80.7
64.2
73.3
Security
38.3
49.4
58.5
62.5
57.3
62.7
Databases
39.6
73.0
72.0
81.0
75.2
75.1
mining
49.4
43.4
10
Game Theory
7.6
92.0
92.3
91.9
91.2
90.9
11
HCI
43.0
89.1
86.5
91.6
87.9
88.1
12
Information Theory
79.3
77.2
35.1
83.6
73.0
76.0
13
Medical Informatics
26.9
86.6
85.0
89.2
85.3
85.6
Robotics
91.4
86.7
55.8
93.4
79.2
87.5
Theoretical CS
57.0
84.2
75.5
89.6
84,3
84.1
AVERAGE
51.5
69.7
64.0
79.6
70.2
75.5
23

---

Published as a conference paper at ICLR 2024
Table 8: Fl scores for the Coauthor Physics dataset with 25 positive and 25 negative nodes.
Cluster
CL.F
FD
WFD
LFD
L.RR
Partices,, fields, gravitation, and
87.5
87.2
74.2
91.9
87.7
cosmology
Atomic, molecular, optical physics and quantom information Condensed matter materials
69.2
69.5
63.7
82.7
73.8
77.9
90.5
81.1
88.1
95.
89.9
93.3
physics
Nuclear physies
55.2
81.6
79.4
87.3
82.6
84.6
Statistical, nonlinear, biological,
60.4
46.9
48.3
74.
58,8
72.6
matter physics
AVERAGE
72.6
73.2
70.7
86.2
78.6
83.6
Table Fl scores for the Amazon Photo dataset with 25 positive and 25 negative nodes.
Cluster
CLF
FD
WFD
LFD
PR
LPR
1 Film Photography
37.2
89.9
82.6
90.0
87.8
89.1
2 Digital Cameras
69.5
81.6
76.9
82.0
79.5
79.8
3 Binoculars
59.2
97.4
96.7
96.9
96.6
4 Lenses
62.7
64.9
66.2
73.0
64.9
70.4
5 Tripods & Monopods
65.7
82.8
83.1
90.4
78.2
84.1
6 Video Surveillance
71.4
98.3
98.1
98.7
98.3
98.3
7 Lighting & Studio
66.4
47.3
62.6
46.6
80.4
82.9
8 Flashes
30.9
56.5
60.2
67.8
48.2
55.1
AVERAGE
57.9
77.3
78.3
80.7
79.2
82.1
Table 10: Fl scores for the Amazon Computers dataset with 25 positive and 25 negative nodes.
Cluster
CLF
FD
WFD
LFD
PR
LPR
Desktops
23.5
60.5
70.8
68.6
72.2
80.3
2
Data Storage
52.2
39.0
41.1
44.2
54.7
58.7
3
Laptops
62.3
93.1
87.6
91.9
89.1
88.6
Monitors
36.3
61.1
64.5
81.1
59.7
74.0
5
Computer Components
72.7
79.9
75.2
79.7
76.0
79.2
Video Projectors
45.3
95.2
95.2
95.0
94.5
94.3
Routers
27.9
59.3
53.4
60.9
58.0
59.4
Tablets
43.4
89.8
85.7
89.1
87.9
86.6
9
Networking Products
57.2
64.3
55.5
70.1
61.6
65.4
10
Webcams
25.8
89.6
83.4
89.7
86.7
86.8
AVERAGE
44.7
73.2
71.2
77.0
74.1
77.3
D.4 DETAILED RESULTS OF EXPERIMENT WITH SAMPLING HEURISTIC
This subsection outlines the second experiment conducted with real-world data. In this experiment, single seed node is provided without any access to ground-truth data or a pre-trained classifier. As outlined in section 4.2 adopted heuristic approach begins with executing initial flow diffusion process from the provided seed node. In all reported single-seed diffusion processes, we increase the amount of mass used from twice ten times the volume of the target cluster. The 100 nodes with the highest and lowest flow diffusion embeddings are designated as positive and negative nodes, respectively. This data is used to train classifier, as described in the previous experimental setting, and diffusion is then run from the positive nodes, followed by sweep-cut procedure. The following tables report the results for each dataset, broken-down by their clusters.
24

---

Published as a conference paper at ICLR 2024
Table 11: scores for the Cora dataset with 25 positive and 25 negative nodes.
Cluster
CLF
FD
WFD
LFD
PR
LPR
Case Based
44.1
70.3
70.7
70.4
71.0
69.2
2
Genetic Algorithms
60.0
91.8
91.8
92.6
90.5
90.5
Neural Networks
57.1
69.4
69.6
68.2
67.9
67.5
Probabilistic Methods
48.6
66.0
66.5
68.8
72.7
Reinforcement Learning
44.5
77.4
77.2
77.2
76.4
75.0
Rule Learning
32.4
71.5
71.5
71.1
69.8
69.4
Theory
41.5
60.8
60.5
60.0
60.3
60.4
AVERAGE
46.9
72.5
72.5
72.6
72.7
72.1
Table 12: Fl scores for the Pubmed dataset with 25 positive and 25 negative nodes.
Cluster
CLF
FD
WFD
LFD
PR
LPR
Diahetes Mellitus
75.9
49.3
49.4
61.7
53.2
58.9
(Experimental)
2
Diabetes Mellitus
70.1
77.8
77.9
77.2
74.5
75.5
Type 1
Diabetes Mellitus
65.2
66.1
66.1
66.8
64.1
65.7
Type 2
AVERAGE
70.4
64.4
64.5
68.6
63.9
66.7
Table 13: Fl scores for the Coauthor CS dataset in the absence of ground-truth data
Cluster
FD (sigge--sed
WFD (ingle-seed)
FD (mali-scod)
WFD (malii-sced)
PR (singleseedi
PR (mulii-see))
Bioinformatics
34.1
35.5
23.7
28.3
34.1
31.6
26.5
45.2
Machine Learning
29.0
22.5
21.5
26.9
25.6
30.8
28.9
44.3
3
Computer Vision
34.5
18.5
39.2
28.0
63.5
48.0
49.2
59.0
4
NLP
53.5
58.1
37.8
47.8
54.5
46.3
43.0
66.5
5
Graphics
28.6
43.2
60.5
61.5
72.0
58.2
63.1
69.8
6 Networks
42.1
32.5
46.3
48.2
71.6
50.7
54.5
62.3
7 Security
31.9
34.0
27.8
31.0
34.3
30.7
31.1
53.4
8 Databases
27.5
23.1
56.8
61.0
73.5
60.0
67.3
74.3
Data mining
26.6
12.9
19.5
21.4
30.0
28.1
40.7
Game Theory
82.0
81.0
83.0
58.8
84.4
85.6
11 HCI
68.7
83.6
79.9
81.0
87.6
75.6
82.0
86.4
12 Information Theory
36.3
12.3
56.2
26.0
78.0
61.5
65.9
70.3
13 Medical Informatics
80.9
76.4
73,9
72.2
83.4
75.3
78.1
83.6
14 Robotics
36.9
32.0
68.0
27.1
82.9
64.8
67.7
73.0
Theoretical CS
43.9
28.1
70.6
67.0
81.3
69.5
76.6
78.7
AVERAGE
43.8
39.9
50.5
47.1
63.1
52.8
56.4
66.2
25

---

Published as a conference paper at ICLR 2024
Table 14: Fl scores for the Coauthor Physics dataset in the absence ground truth data
Cluster
FD (single
WFD (single seed)
FD seed)
WFD (multi-sced)
LFD
PR (ingle seed)
PR
LPR
seed)
Particles, fiolds, gravitation, and cosmology
78.5
60.8
65.5
48.8
80.9
72.9
72.5
80.7
Atomic, molecular, and optical physics and quantum information Condensed mutter and materials physics
38.2
35.1
45.8
40.9
58.9
48.9
50.5
57.5
84.0
81.6
87.4
84.9
85.4
87.6
Nuclear physics
63.5
68.6
60.6
58.9
77.7
68.7
68.0
72.1
Statistical, nonlincar, biological, soft physics
52.3
36.4
23.5
25.6
59.4
41.8
33.2
62.5
AVERAGE
62.8
57.0
55.5
51.1
72.9
63.4
61.9
72.1
Table 15: Fl scores for the Amazon Photo dataset in the absence of ground-tret -tunh data
Cluster
FD (siagle-sedd)
WFD (singlo-sod))
FD (multi-szed)
WFD (uullt-seed)
LFD
PR
LPR
(singlo-seed)
1 Film Photography
69.4
69.3
80.5
67.1
82.3
77.1
78.5
82.6
2 Digital Cameras
43.8
61.4
64.1
59.7
67.2
69.3
69.2
69.8
3 Binoculars
97.2
94.6
87.0
81.7
80.4
86.8
83.0
86.2
4 Lenses
33.5
35.2
36.0
37.7
45.5
41.3
42.2
49.7
Tripods Monopods
34.3
36.6
53.6
69.8
71.9
54.0
6 Video Surveillance
98.3
98.1
98.3
97.9
98.8
98.1
98.2
97.0
7 Lighting & Studio
39.3
46.7
46.8
54.1
50.7
58.7
56.9
59.1
8 Flashes
19.8
17.2
30.3
33.1
38.1
32.1
28.8
34.4
AVERAGE
54.5
57.4
62.1
62.6
66.8
64.2
63.8
67.6
Table 16: scores for the Amazon Computers dataset in the absence of ground -ruth data
Cluster
FD (single-sed)
WFD Gingle-seed)
FD (multi-eed)
WFD (multi-sed))
LFD
PR (sigge-seed)
PR (multi-seed)
L.RR
1
Desktops
43.1
47.6
40.7
41.7
44.3
41.6
43.1
44.3
2 Data Storage
28.8
32.1
30.6
30.1
32.2
38.0
35.6
40.0
3
Laptops
77.6
69.6
73.5
69.8
80.3
71.1
74.8
78.7
4 Monitors
32.8
32.6
38.7
41.0
53.8
31.0
37.1
50.2
5
Computer Components
54.1
57.3
73.4
58.7
73.1
68.5
68.8
6
Video Projectors
95.1
94.2
95.1
94.9
94.9
92.6
94.3
94.4
7
Routers
40.5
33.1
36.9
33.4
34.4
42.4
46.6
47.6
8
Tablets
79.0
67.4
72.9
68.8
71.6
69.5
73.3
73.7
9
Networking Products
27.4
29.8
37.9
31.1
36.7
46.2
48.2
50.2
10 Webcams
83.4
69.1
82.0
76.0
82.6
76.7
82,2
84.0
AVERAGE
56.2
53.3
58.2
54.6
60.4
57.7
60.4
63.2
26

---

Published as a conference paper at ICLR 2024
Table 17: Fl scores for the Cora dataset in the absence of ground -hound-truth data
Cluster
FD (singlo-sedd)
WFD (single-sed))
FD (multi-sced)
WFD (mulli-szed)
LFD
PR (single-eco))
PR (malii-scod)
LPR
Case Based
36.0
36.4
55.1
55.4
58.4
49.0
53,4
60.9
Genetic Algorithms
30.8
31.6
88.7
88.9
90.5
82.8
88.1
89.5
Neural Networks
45.9
46.3
43.8
43.7
40.3
56.4
59.0
55.9
4 Probabilistic Methods
33.7
34.0
37.6
38.0
38.2
41.9
39.4
41.6
Reinforvement Learning
25.3
26.2
67.7
67.7
68.0
64.4
69.2
69.4
Rule Learning
34.4
33,9
52.4
52.3
57.3
48.5
55.0
59.6
Theory
27.2
27.2
42.3
42.2
42.8
46.7
45.7
47.4
AVERAGE
33.3
33.7
55.4
55.4
56.5
55.7
58.5
60.6
Table 18: Fl scores for the Pubmed dataset in the absence of ground-truth data
Cluster
FD (single seed)
WFD
FD
WFD
LFD
PR (single seed)
PR
LPR
(single seed)
Emaiti seed)
amalti-sced
(muiti scod)
Diabetes Mellitus
34.8
35.0
37.0
37.0
43.9
43.9
42.1
49.8
(Experimental)
Diabetes Mellitus
69.7
69.8
71.6
71.6
69.7
69.5
71.3
Type
3
Diabetes Mellitus
54.6
55.0
53.1
53.1
52.4
54.1
53.1
55.2
Type
AVERAGE
53.0
53.2
53.9
53.9
55.3
56.1
54,9
58.8
27


Reviews:
[{"review_id": "WQK8Oxb20q", "reviewer": "Reviewer_LuBd", "summary": "This paper studies the local graph clustering task using noisy node labels. The theoretical justification is provided to investigate the benefits of incorporating noisy labels for local graph clustering. Some empirical results are shown to illustrate the method.", "questions": "See above.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Graph clustering is a very fundamental problem for graph-related problems, and exploring noisy labels perspective is a very interesting topic.\n- The paper is well-organized and easy to be understood.", "weaknesses": "- About my confusion with the setting of the paper. The setting is local graph clustering or local graph clustering with noisy node labels? If it is local graph clustering, I think this paper tackles the local graph clustering problem with the help of noisy labels. The authors say that they abstract all available sources of additional information as noisy node labels. However, the setting of their experiments does not reflect this point, i.e., they only use the predicted labels as the noisy labels. I did not see any other available sources to transform into noisy labels. If the setting is local graph clustering with noisy node labels, the authors should compare the proposed method with other existing methods that focus on this setting, i.e., node labels should be contained in the compared methods. So the experiments have limitations. I hope the authors clarify the setting and make more comparisons with existing methods. Experiments should be enriched to verify the effectiveness of the method.\n- The paper lacks complexity analysis.\n- The comparison of the empirical running time of each method should be contained. Hyperparameter analysis is also missed. \n- The analysis and discussion of the empirical results are clearly inadequate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uunOOaxno8", "reviewer": "Reviewer_CYJN", "summary": "This paper studies local graph clustering (identifying a small cluster containing the seed nodes) with noisy node labels. The authors propose a localized algorithm based on flow diffusion on a weighted graph constructed from the noisy labels. For a particular local random model, it is shown that the proposed algorithm yields an accurate recovery of the target cluster with high probability measured by F1 score. The authors also demonstrate through synthetic data as well as several real-world datasets that the approach has better performance compared to using edges or labels alone.", "questions": "1.  As noted by the authors, $\\epsilon$ interpolates between two special scenarios that are suitable for different level of label noise. From a theoretical perspective, how should $\\epsilon$ be chosen if $a_0$ and $a_1$ are known? Also, is there possibly a way to estimate $\\epsilon$ and $\\theta^\\dagger$ from the graph?\n2. The main theorem requires $p = \\omega(\\frac{\\sqrt{\\log k}}{\\sqrt{k}})$ which produces a dense cluster. Can this condition be relaxed to include less dense clusters?\n3. Is there an information-theoretic limit on recovering local graph cluster with noisy labels such that the sharpness of the lower bound on F1 can be evaluated?\n4. It would be helpful to compare the current result with these on local graph clustering without labels. In particular, when the labels do not provided any information ($a_0 = a_1 = 1/2$), does the proposed algorithm have improvements over the previous ones?\n5. Weighted message passing is another localized algorithm applied to SBM with noisy label information (see [1] and references therein). How does the flow diffusion algorithm and theoretical result compare to it?\n\n[1] Cai, T. T., Liang, T., & Rakhlin, A. (2020). Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information. The Journal of Machine Learning Research, 21(1), 346-379.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem of recovering a small cluster with additional noisy labels is new and interesting.\n2. The proposed method, though based on a simple modification of flow diffusion, is localized and computationally efficient.\n3. The theoretical analysis is sound and convincing. Moreover, it addresses the situation when the F1 score of labels is very low.\n4. The experiments further justify the findings and show significant improvements over using only edges or labels.", "weaknesses": "1. Flow diffusion has been studied extensively under various settings in the literature. The current work is a direct application of it.\n2. The theoretical analysis is limited to a very simple random graph model in specific parameter regimes, and there is room for stronger arguments (see question 2-5).\n3. The choice of several parameters in the algorithm probably requires more investigation and discussion (see question 1).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8Q0Xnw9RnM", "reviewer": "Reviewer_oYEs", "summary": "In this paper, the authors study the local graph clustering problem. They investigate the benefits of incorporating noisy labels for local graph clustering. By constructing a weighted graph with such labels, they study the performance of graph diffusion-based local clustering method on both the original and the weighted graphs. The experimental results demonstrate the effectiveness of the proposed methods.", "questions": "Q1. In Section 1, the authors claim that the task of local graph clustering aims to\nidentify a small cluster of nodes that contains all or most of the seed nodes, without exploring the entire graph. However, it is unclear whether the proposed method needs to explore the entire graph.\n\nQ2. In Section 1, the authors claim that the additional information like texts, images can significantly benefit clustering, but the relation between the additional information and the proposed methods is unclear.\n\nQ3. Only flow diffusion and Label-based PageRank methods are compared in the experiments, it is unclear whether the compared methods in the experiment section are comprehensive or not.\n\nQ4. It is unclear whether the assumption on a_0 and a_1 is practical in real applications.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The problem studied in the paper is important.\nS2. The performance of flow diffusion over a random graph model is analyzed.\nS3. Empirical experiments are conducted to evaluate the proposed methods.", "weaknesses": "W1. It is unclear whether the proposed method needs to explore the entire graph.\nW2. The relation between the additional node information like texts, images and the proposed methods is unclear.\nW3. Whether the compared methods in the experiment section are comprehensive or not is unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nmgdOz6jHA", "reviewer": "Reviewer_PWgh", "summary": "The paper proposes a method that leverages noisy node labels for local graph clustering. In this approach, edge weights are defined based on the noisy labels in the graph, giving higher weight to nodes with the same noisy label and lower weight to nodes with different labels. Using this weighted graph, the authors apply a graph diffusion local clustering method called 'flow diffusion' to determine the clustering. The paper includes both theoretical proofs and empirical evidence, demonstrating why this approach improves clustering accuracy compared to applying the flow diffusion method directly to the original graph.", "questions": "- Regarding the discussions following Theorem 3.4:\n  \n  - The statement that \"as $\\gamma$ becomes lager, it generally becomes more\n    difficult to accurately recover K [the cluster]\" appears counterintuitive. Given that $\\gamma\\coloneqq \\frac{p(k-1)}{q(n-k)}$ signifies the ratio of internal to external connections within a cluster, an increase in $\\gamma$ implies more internal connections. This suggests a stronger, more cohesive cluster. Could you elaborate on why higher $\\gamma$ values lead to increased difficulty in cluster recovery?\n  \n  - The assertion that \"F1 is lower bounded by a constant as long as $\\gamma$ is a constant\" raises questions.  What does \"$\\gamma$ is constant\" mean in this context? As far as I understand, the value $\\gamma$ is defined for each node and implicitly depends exclusively on the cluster size, $k$, and the edge probabilities, $p$ and $q$. I suggest that this dependence is stress further, since as it is written now, $\\gamma$ is apparently a constant by itself. Consequently, I guess that \"$\\gamma$ constant\" means that it has the same value for all nodes (or for all clusters). Nonetheless, the lower bound of F1 would still depend on $a_0$ and $a_1$. Could you clarify why the lower bound of F1 is described as a constant despite potential dependencies on other parameters?\n  \n  - The statement, \"even when the initial labels are deemed fairly accurate based on $a_0$ and $a_1$, e.g. $a_1$ = 1, $a_0$ = 0.99, the F1 score of the labels can still be very low.\" Could you explain the factors contributing to the low F1 score in this scenario?\n\n- How robust is the proposed method concerning the source mass of the seed ($\\Delta_s$)?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The proposed method for local graph clustering is conceptually simple and easy to implement while apparently being effective. It is also flexible, as it can be combined with different diffusion-based local clustering algorithms. In addition, the authors provide theoretical guarantees for its success under mild conditions.", "weaknesses": "The experimental section lacks a comparison with alternative methods that are not flow-based.\n\nThe paper lacks a detailed exploration of the algorithm's sensitivity to hyperparameters. While the robustness to the choice of $\\epsilon\\in[0.01,0.1]$ is briefly mentioned, there is no reference to the robustness of the source mass of the seed ($\\Delta_s$). For the experiments with the synthetic datasets, different $\\Delta_s$ values are tested but only the best is provided. The paper would benefit if there was an study on the choice of the hyperparameters.\n\nThe discussion regarding Theorem 3.4 is not adequately understandable. See questions for more details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)