* [95] J. Wang, S. Hao, R. Wen, B. Zhang, L. Zhang, H. Hu, and R. Lu, “IoT-Praetor: Undesired behaviors detection for IoT devices,” _IEEE Internet of Things Journal_ , vol. 8, no. 2, pp. 927–940, 2021.
  * [96] T. F. J.-M. Pasquier, J. Singh, D. Eyers, and J. Bacon, “Camflow: Managed data-sharing for Cloud services,” _IEEE Transactions on Cloud Computing_ , vol. 5, no. 3, pp. 472–484, 2017.
  * [97] J. Singh, C. Millard, C. Reed, J. Cobbe, and J. Crowcroft, “Accountability in the IoT: Systems, law, and ways forward,” _Computer_ , vol. 51, no. 7, pp. 54–65, 2018.
  * [98] P. Emami-Naeini, Y. Agarwal, L. Faith Cranor, and H. Hibshi, “Ask the experts: What should be on an IoT privacy and security label?” in _2020 IEEE Symposium on Security and Privacy (SP)_ , May 2020, pp. 447–464, iSSN: 2375-1207.
  * [99] Pew Research Center, “Research in the crowdsourcing age, a case study,” https://www.pewresearch.org/internet/2016/07/11/research-in-the-crowdsourcing-age-a-case-study/, July 2016, accessed: 2022-11-14.
  * [100] F. M. Shipman and C. C. Marshall, “Ownership, privacy, and control in the wake of cambridge analytica: The relationship between attitudes and awareness,” in _CHI ’20_ , 2020, pp. 1––12.
  * [101] J. Jager, D. L. Putnick, and M. H. Bornstein, “More than just convenient: The scientific merits of homogeneous convenience samples,” _Monographs of the Society for Research in Child Development_ , vol. 82, no. 2, pp. 13–30, 2017.
  * [102] G. Chalhoub and I. Flechais, “Alexa, are you spying on me?: Exploring the effect of user experience on the security and privacy of smart speaker users,” in _HCI for Cybersecurity, Privacy and Trust_ , A. Moallem, Ed. Cham: Springer International Publishing, 2020, pp. 305–325.
  * [103] D. Winder, “How to stop your smart home spying on you,” https://www.theguardian.com/technology/2020/mar/08/how-to-stop-your-smart-home-spying-on-you-lightbulbs-doorbell-ring-google-assistant-alexa-privacy, March 2020, accessed: 2022-08-14.
  * [104] R. Yus and P. Pappachan, “Smart devices spy on you – 2 computer scientists explain how the Internet of Things can violate your privacy,” https://theconversation.com/smart-devices-spy-on-you-2-computer-scientists-explain-how-the-internet-of-things-can-violate-your-privacy-174579, March 2022, accessed: 2022-08-14.
  * [105] C. Norval and J. Singh, “Supplementary data — A room with an overview: Towards meaningful transparency for the consumer internet of things,” https://github.com/cnorval/meaningful_IoT, 2023, accessed: 2023-09-18.
  * [106] H. S. Alavi, E. F. Churchill, M. Wiberg, D. Lalanne, P. Dalsgaard, A. Fatah gen Schieck, and Y. Rogers, “Introduction to Human-Building Interaction (HBI): Interfacing HCI with architecture and urban design,” _ACM Trans. Comput.-Hum. Interact._ , vol. 26, no. 2, mar 2019.
  * [107] D. Bastos, F. Giubilo, M. Shackleton, and F. El-Moussa, “GDPR privacy implications for the Internet of Things,” in _4th Annual IoT Security Foundation Conference_ , vol. 4, 2018, pp. 1–8.
  * [108] V. Braun and V. Clarke, “Using thematic analysis in psychology,” _QRP_ , vol. 3, no. 2, pp. 77–101, 2006.
  * [109] M. H. Bornstein, J. Jager, and D. L. Putnick, “Sampling in developmental science: Situations, shortcomings, solutions, and standards,” _Developmental Review_ , vol. 33, no. 4, pp. 357–370, 2013.
  * [110] P. Sedgwick, “Convenience sampling,” _BMJ_ , vol. 347, 2013.
  * [111] S. J. Stratton, “Population research: Convenience sampling strategies,” _Prehospital and Disaster Medicine_ , vol. 36, no. 4, pp. 373––374, 2021\.
  * [112] MURAL, “MURAL,” https://www.mural.co/, January 2022, accessed: 2022-01-21.
  * [113] J. Smith and H. Noble, “Bias in research,” _Evidence-Based Nursing_ , vol. 17, no. 4, pp. 100–101, 2014.
  * [114] M. A. A. Elsood, H. A. Hefny, and E. S. Nasr, “A goal-based technique for requirements prioritization,” in _2014 9th International Conference on Informatics and Systems_ , 2014, pp. SW–18–SW–24.
  * [115] A. Cuthbertson, “Hackers can hijack your house through your light bulb, researchers discover,” https://www.independent.co.uk/tech/philips-hue-smart-light-bulb-hack-cyber-security-a9317456.html, February 2020, accessed: 2022-08-13.
  * [116] E. Ronen and A. Shamir, “Extended functionality attacks on IoT devices: The case of smart lights,” in _2016 IEEE European Symposium on Security and Privacy (EuroS &P)_, 2016, pp. 3–12.
  * [117] E. Ronen, A. Shamir, A.-O. Weingarten, and C. O’Flynn, “IoT goes nuclear: Creating a ZigBee chain reaction,” in _2017 IEEE Symposium on Security and Privacy (SP)_ , 2017, pp. 195–212.
  * [118] E. McGowan, “Here’s what your Ring doorbell knows about you,” https://blog.avast.com/what-amazon-ring-knows-about-you-avast, May 2021, accessed: 2022-08-14.
  * [119] K. N. Truong, G. R. Hayes, and G. D. Abowd, “Storyboarding: An empirical determination of best practices and effective guidelines,” in _Proceedings of the 6th Conference on Designing Interactive Systems_ , ser. DIS ’06. New York, NY, USA: Association for Computing Machinery, 2006, pp. 12––21.
  * [120] W. D. Perreault, “Controlling order-effect bias,” _The Public Opinion Quarterly_ , vol. 39, no. 4, pp. 544–551, 1975.
  * [121] J. Brooke, “SUS: A quick and dirty usability scale,” in _Usability evaluation in industry_. Taylor and Francis, 1996.
  * [122] A. Bangor, P. Kortum, and J. Miller, “Determining what individual SUS scores mean: Adding an adjective rating scale,” _JUS_ , vol. 4, no. 3, pp. 114–123, 2009.
  * [123] F. Loukil, C. Ghedira-Guegan, A. N. Benharkat, K. Boukadi, and Z. Maamar, “Privacy-aware in the IoT applications: A systematic literature review,” in _On the Move to Meaningful Internet Systems. OTM 2017 Conferences_ , H. Panetto, C. Debruyne, W. Gaaloul, M. Papazoglou, A. Paschke, C. A. Ardagna, and R. Meersman, Eds. Cham: Springer International Publishing, 2017, pp. 552–569.
  * [124] C. M. Gray, Y. Kou, B. Battles, J. Hoggatt, and A. L. Toombs, “The dark (patterns) side of UX design,” in _CHI ’18_ , 2018.
  * [125] M. Kowalczyk, J. T. Gunawan, D. Choffnes, D. J. Dubois, W. Hartzog, and C. Wilson, “Understanding dark patterns in home IoT devices,” in _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , ser. CHI ’23. New York, NY, USA: Association for Computing Machinery, 2023.
  * [126] R. Cloete, C. Norval, and J. Singh, “A call for auditable virtual, augmented and mixed reality,” in _Proceedings of the 26th ACM Symposium on Virtual Reality Software and Technology_ , ser. VRST ’20. New York, NY, USA: Association for Computing Machinery, 2020\.
  * [127] R. Cloete, C. Norval, and J. Singh, “Auditable augmented/mixed/virtual reality: The practicalities of mobile system transparency,” _Proc. ACM Interact. Mob. Wearable Ubiquitous Technol._ , vol. 5, no. 4, dec 2022.
  * [128] C. Norval, R. Cloete, and J. Singh, “Navigating the audit landscape: A framework for developing transparent and auditable XR,” in _Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency_ , ser. FAccT ’23. New York, NY, USA: Association for Computing Machinery, 2023, pp. 1418––1431.
  * [129] S. A. Javadi, C. Norval, R. Cloete, and J. Singh, “Monitoring AI services for misuse,” in _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , ser. AIES ’21. New York, NY, USA: Association for Computing Machinery, 2021, pp. 597––607.
  * [130] C. J. Millard, _Cloud computing law_ , 2nd ed. Oxford University Press Oxford, 2021.
  * [131] C. Norval, H. Janssen, J. Cobbe, and J. Singh, “Data protection and tech startups: The need for attention, support, and scrutiny,” _Policy & Internet_, vol. 13, no. 2, pp. 278–299, 2021.
  * [132] European Union, “Regulation (EU) 2016/679 of the European Parliament and of the Council of 27 April 2016 on the Protection of Natural Persons with Regard to the Processing of Personal Data and on the Free Movement of Such Data, and Repealing Directive 95/46/EC (General Data Protection Regulation),” _Official Journal of the European Union_ , vol. L119, pp. 1–88, May 2016\.
  * [133] A. F. T. Winfield, S. Booth, L. A. Dennis, T. Egawa, H. Hastie, N. Jacobs, R. I. Muttram, J. I. Olszewska, F. Rajabiyazdi, A. Theodorou, M. A. Underwood, R. H. Wortham, and E. Watson, “IEEE P7001: A proposed standard on transparency,” _Frontiers in Robotics and AI_ , vol. 8, 2021\.
  * [134] Electronic Frontier Foundation, “Electronic Frontier Foundation,” https://www.eff.org/, January 2022, accessed: 2022-01-20.
  * [135] Open Rights Group, “Open Rights Group,” https://www.openrightsgroup.org/, January 2022, accessed: 2022-01-20.
  * [136] J. Chen and L. Urquhart, “They’re all about pushing the products and shiny things rather than fundamental security: Mapping socio-technical challenges in securing the smart home,” _arXiv preprint arXiv:2105.11751_ , 2021.
  * [137] European Commission, “Europe’s Internet of Things Policy,” https://digital-strategy.ec.europa.eu/en/policies/internet-things-policy, October 2022, accessed: 2022-12-19.
  * [138] European Commission, “Cyber Resilience Act,” https://digital-strategy.ec.europa.eu/en/library/cyber-resilience-act, September 2022, accessed: 2022-12-19.
  * [139] GOV.UK, “New cyber security laws to protect smart devices amid pandemic sales surge,” https://www.gov.uk/government/news/new-cyber-security-laws-to-protect-smart-devices-amid-pandemic-sales-surge, April 2021, accessed: 2021-11-15.
  * [140] GOV.UK, “Code of practice for consumer IoT security,” https://www.gov.uk/government/publications/code-of-practice-for-consumer-iot-security, October 2018, accessed: 2022-12-19.
  * [141] Article 29 Working Party, “Guidelines on transparency under Regulation 2016/679,” no. WP260, April 2018.


We propose and study a novel graph clustering method for data with an intrinsic network structure.
Similar to spectral clustering, we exploit an intrinsic network structure of data to
construct Euclidean feature vectors. These feature vectors can then be fed into basic
clustering methods such as k-means or Gaussian mixture model (GMM) based soft clustering.
What sets our approach apart from spectral clustering is that we do not use the eigenvectors
of a graph Laplacian to construct the feature vectors. Instead, we use the solutions of total
variation minimization problems to construct feature vectors that reflect connectivity between
data points. Our motivation is that the solutions of total variation minimization are
piece-wise constant around a given set of seed nodes. These seed nodes can be obtained
from domain knowledge or by simple heuristics that are based on the network structure of data.
Our results indicate that our clustering methods can cope with certain graph structures
that are challenging for spectral clustering methods.

machine learning; clustering; non-smooth optimization; community detection; complex networks

§ INTRODUCTION

The analysis of networked data is often facilitated by grouping or clustering the data points
into coherent subsets of data points. Clustering methods aim at finding subsets (clusters) of
data points that are more similar to each other than to the remaining data points [29].
Many basic clustering algorithms aim at clusters that are enclosed by a hypersphere or hyperellipsoid
in a Euclidean feature space. These methods are most successful if data points are characterized by
Euclidean feature vectors whose distance is small (large) for data points in the same (different) cluster(s).

Graph clustering methods can be applied to data with an intrinsic network structure that reflects
a notion of similarity between different data points. Many important application domains, ranging
from the Internet of Things to the management of pandemics, generate distributed collections of
local datasets (“big data over network”) [22, 23]. The
network structure of these local datasets might be  induced by spatio-temporal proximity (“contact networks”),
statistical dependencies,  or functional relations [1, 2].

§ PROBLEM FORMULATION

We represent networked data using an undirected “empirical” graph $\graph=(\nodes, \edges, \edgeweights)$ [24, 9].
Every node $\nodeidx \in \nodes = \{1,\ldots,\nrnodes\}$ of the empirical graph represents a datapoint. The dataset
consists of $\nrnodes$ different datapoints. A datapoint might be a single sensor measurement, an entire time
series,  or even a whole collection of videos.

Our approach does not take the individual nature of datapoints into account. Rather, we only
use their similarities as encoded in the weighted edges of $\graph$. In particular, two nodes $\nodeidx, \nodeidx'$
are connected by an edge $\edge{\nodeidx}{\nodeidx'}$ if the corresponding datapoints are similar.
The amount of similarity is quantified by a positive edge weight $\edgeweight_{\nodeidx,\nodeidx'}$.

We find it convenient to use an oriented (or directed) version of the empirical graph $\graph$ by
declaring, for each undirected edge $\edge{\nodeidx}{\nodeidx'}$, the node $\min\{\nodeidx,\nodeidx'\}$
as tail and the other node $\max\{\nodeidx,\nodeidx'\}$ as head in the corresponding directed edge. The resulting
oriented empirical graph $\overrightarrow{\graph} \defeq \big( \nodes, \overrightarrow{\edges}, \edgeweights \big)$
has the same nodes as $\graph$ and contains the directed edge $\directededge{\nodeidx}{\nodeidx'}$ from node $\nodeidx$ to node $\nodeidx'$
if and only if $\nodeidx < \nodeidx'$ and $\edge{\nodeidx}{\nodeidx'} \in \edges$. This directed edge $\directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges}$ has the same
weight $\edgeweight_{\nodeidx,\nodeidx'}$ as the corresponding undirected edge $\edge{\nodeidx}{\nodeidx'} \in \edges$.

We will use several matrices that are naturally associated with an empirical graph $\graph$.
The weight matrix $\edgeweights$ contains the edge weight $\edgeweight_{\nodeidx,\nodeidx'}$
in its $\nodeidx$th row and $\nodeidx'$th column. The diagonal degree matrix $\degreemtx \defeq {\rm diag}\{\nodedegree{1},\ldots,\nodedegree{\nrnodes}\}$ collects the (weighted) node degrees
$\nodedegree{\nodeidx}=\sum_{\nodeidx'} \edgeweight_{\nodeidx,\nodeidx'}$ for each node $\nodeidx$.
The graph Laplacian matrix $\mathbf{L} \defeq \degreemtx - \edgeweights$ is instrumental
for spectral clustering methods (see Section <ref>).

There are also vector spaces naturally associated with an empirical graph. The vector space consisting of
maps $\vu$ from nodes to real numbers is denoted $\mathbb{R}^{\nrnodes}$. A vector $\vu \in \mathbb{R}^{\nrnodes}$
is a function or map that assigns each node $\nodeidx \in \nodes$ a real-number $u_{\nodeidx}$.
Similarly, we define the vector space $\mathbb{R}^{\overrightarrow{\edges}}$ that consists of vectors
$\edgesigvec$ that assign each edge $\directededge{\nodeidx}{\nodeidx'} \in \edges$ a real-number $\edgesig_{\directededge{\nodeidx}{\nodeidx'}}$.

Many graph clustering methods, such as spectral clustering, rely on a clustering assumption.
This clustering assumption applies to a dataset for which we know a useful empirical graph

[6, 7, 9]. A cluster is then
constituted by data points whose nodes in $\graph$ are more densely connected with each other
than with nodes representing data points outside the cluster [15, 18].
This informal clustering assumption can be made precise by constraining the cut-size of cluster [9].
By the maxflow/mincut duality, requiring a small cut is equivalent to requiring a minimum amount of network
flow that can be routed from the nodes inside a cluster through its boundary [25].

Using the above clustering assumption, we construct feature vectors $\featurevec^{(\nodeidx)}$ for
each node (or datapoint) $\nodeidx \in \nodes$. The feature vectors will be constructed such that
two nodes $\nodeidx, \nodeidx'$ that belong to a well-connected subset of nodes (a cluster) have more
feature vectors $\featurevec^{(\nodeidx)}, \featurevec^{(\nodeidx')}$ with a small Euclidean distance
$\big\| \featurevec^{(\nodeidx)}- \featurevec^{(\nodeidx')} \big\|$. Loosely speaking, the feature construction
maps similarity between datapoints in the empirical graph $\graph$ into proximity
of their Euclidean feature vectors. This allows us then to apply standard clustering methods, such as k-means
of soft clustering [29], to the network structured data.

§ SPECTRAL CLUSTERING

Before we detail our construction of the feature vectors $\featurevec^{(\nodeidx)}$ let us
briefly review the construction used by spectral graph clustering methods [9] .
The most basic variant of spectral clustering constructs the node feature vectors $\featurevec^{(\nodeidx)}$ using
the eigenvectors of the graph Laplacian matrix $\mathbf{L} = \degreemtx - \edgeweights$ [9].
The matrix $\mathbf{L}$ is positive semi-definite (psd) and therefore we can find an orthonormal set of
eigenvectors [11]

\begin{equation}
\label{equ_def_eigvals}
\vu^{(1)},\ldots,\vu^{(\nrnodes)} \mbox{ with eigenvalues } 0 \leq \eigval{1} \leq \ldots \leq \eigval{\nrnodes}.
\end{equation}

For a given a number $\nrcluster$ of clusters, spectral clustering methods use the feature vectors

\begin{equation}
\label{equ_def_feat_vec_spec_cluster}
\featurevec^{(\nodeidx)} = \big( u^{(1)}_{\nodeidx}, \ldots,u^{(\nrcluster)}_{\nodeidx} \big)^{T} \mbox{ for every node } \nodeidx \in \nodes.
\end{equation}

The Ideal Case. To develop some intuition for the usefulness of the construction (<ref>),
consider an empirical graph that contains $\nrcluster$ components $\datacluster{1},\ldots,\datacluster{\nrcluster} \subseteq \nodes$
that are not connected by any edge. In this case, the first $\nrcluster$ (possibly repeated) eigenvalues in (<ref>)
are equal to $0$. The correspond eigenvectors $\vu^{(1)},\ldots,\vu^{(\nrcluster)}$ constitute an orthonormal basis
for the subspace of $\mathbb{R}^{\nrnodes}$ that is spanned by the indicator vectors $\mathbf{e}^{(\clusteridx)}$
of the components $\datacluster{\clusteridx}$, $e_{\nodeidx}^{(\clusteridx)} = 1$ for nodes $\nodeidx \in \datacluster{\clusteridx}$ and $e_{\nodeidx}^{(\datacluster{\clusteridx})} = 0$ for nodes $\nodeidx \notin \datacluster{\clusteridx}$. Thus, the feature vectors of nodes in the
same cluster $\datacluster{\clusteridx}$ are identical and orthogonal to the feature vectors of nodes in different
clusters $\datacluster{\clusteridx'}$ with $\clusteridx' \neq \clusteridx$.

General Case. In general, the empirical graph will contain edges between different clusters.
A widely used approach to analyzing spectral clustering methods is to consider the effect of these
inter-cluster edges as perturbations of the Laplacian matrix $\mL$. For sufficiently small perturbations,
the subspace spanned by the first $\nrcluster$ eigenvectors of $\mL$ will be close to the subspace spanned
by the indicator vectors $\mathbf{e}^{(\clusteridx)}$. This deviation can be made precise using tools
from linear algebra and results in conditions on the empirical graph for the success of k-means
when applied to the feature vectors (<ref>) [9, 6].

There are certain types of empirical graphs that are challenging for spectral clustering methods that use
the features (<ref>) [9, 28, 27].
For example, spectral methods tend to fail for datasets that consist of clusters with significantly
varying sizes (see Section <ref>). Another example of a challenging network structure for spectral
clustering is a chain graph [26].

Consider a chain graph that consists of two clusters connected via a single edge. The
weights of all intra-cluster edges are equal to $1$ while the weight $\edgeweight_{o}$ of the single boundary
edge is slightly smaller. As the chain graph is connected,  $\eigval{1}=0$ with corresponding eigenvector $\vu^{(1)}$ having identical entries. The smallest non-zero eigenvalue is $\eigval{2}$ has a corresponding
eigenvector $\vu^{(2)}$ whose entries are depicted in Figure <ref>.
The resulting feature vectors (see (<ref>) with $k=2$) do not reflect well the cluster structure of the chain graph.

x=0.35cm,y=2.5cm,every path/.style=>=latex,node style/.style=circle,draw
[ head to column names,
late after head=ı,,
after line=ı]

[line width=0.0mm] (, ) (ı,) node $\circ$;

[ head to column names,
late after head=ı,,
after line=ı]

[line width=0.0mm] (, ) (ı,) node $\star$;

[->] (0.4,0) – (22,0);

[right] at (19.5,0.1) node $i$;
[->] (0.5,0) – (0.5,1.1);
[-,dashed] (0,0.5) – (22,0.5);

in 0/$0$,0.5/$0.5$,1/$1$

(0.4, – (0.6, node[left=2mm] ;

in 1/$1$,5/$5$,10/$10$,15/$15$,20/$20$

(1pt) – (-2pt) node[below] ;

Solution of TV minimization (“$\circ$”) for the chain graph
obtained from Algorithm <ref> using $\nriter=1000$ iterations.  Entries (“$\star$”)
of the eigenvector $\vu^{(2)}$ corresponding to the smallest non-zero eigenvalue $\eigval{2}$ (see (<ref>)).

x=4cm,y=2.5cm,every path/.style=>=latex,node style/.style=circle,draw
[ head to column names,
late after head=ı,,
after line=ı]

[line width=0.0mm] (,0) (,0) node $\circ$;

[ head to column names,
late after head=ı,,
after line=ı]

[line width=0.0mm] (,1 ) (,1) node $\star$;

[->] (-0.1,0) – (1.1,0);

[->] (-0.1,1) – (1.1,1);

[right] at (1.1,0.0) $\feature_{\nodeidx} \defeq \hat{u}_{\nodeidx}^{(\seednodes)}$ (<ref>);
[right] at (1.1,1.0) $\feature_{\nodeidx} \defeq u_{\nodeidx}^{(2)}$ (<ref>);

in 0/$0$,0.5/$0.5$,1/$1$

(1.02) – (0.98) node[below] ;

in 0/$0$,0.5/$0.5$,1/$1$

(0.02) – (-0.02) node[below] ;

Scatterplot of (scalar) node features $\feature_{\nodeidx}$ constructed by spectral and flow-based clustering
for the chain graph in Figure <ref>. Spectral clustering uses the entries (“$\star$”)
of the eigenvector $\vu^{(2)}$ (see (<ref>)). Flow-based clustering uses the solution of TV
minimization (“$\circ$”) (see (<ref>)).

We next describe our novel construction of feature vectors. The idea is to replace the eigenvectors
of the Laplacian in (<ref>) with solutions of total variation (TV) minimization problems.
It turns out that these feature vectors better reflect the cluster geometry of $\graph$ in terms of
bottlenecks for network flows between different clusters. These flow bottlenecks are the boundaries
between the clusters that are obtained by applying clustering methods to these feature vectors.

[1]
D. Koller and N. Friedman.
“Probabilistic Graphical Models: Principles and Techniques. Adaptive computation and machine learning,“
in MIT Press, 2009.

[2]
S. Banerjee, B.P. Carlin, and A.E. Gelfand.
“Hierarchical Modeling and Analysis for Spatial Data,“
in Chapman and Hall/CRC, 2015.

[3]
H.-J. Li and J.J. Daniels.
“Social significance of community structure: Statistical view,“
in IEEE Phys. Rev, 91(1):012801, Jan. 2015.

[4]
T. Pock and A. Chambolle.
“Diagonal preconditioning for first order primal-dual algorithms in convex optimization,“
in IEEE ICCV, 21, Nov. 2011.

[5]
A. Jung.
“On the duality between network flows and network lasso,“
IEEE Sig. Proc. Lett., 27:940 – 944, 2020.

[6]
A. Y. Ng, M. I. Jordan, and Y. Weiss,
“On spectral clustering: Analysis and an algorithm,“
in Adv. Neur. Inf. Proc. Syst, 2001.

[7]
D. Spielman,
“Spectral graph theory,“
in U. Naumann and O. Schenk,
editors, Combinatorial Scientific Computing. Chapman and Hall/CRC, 2012.

[8]
R. T. Rockafellar,
“Convex Analysis,“
in Princeton Univ. Press, 1970.

[9]
U. von Luxburg,
“A tutorial on spectral clustering,“
Statistics and Computing, vol. 17, no. 4, pp. 395–416, Dec.

[10]
A. Jung and Y. SarcheshmehPour,
“Local Graph Clustering With Network Lasso,“
IEEE Signal Processing Letters ( Volume: 28), 2020, pp. 106–110.

[11]
G. H. Golub and C. F. Van Loan,
“Matrix Computations, 3rd.“
Johns Hopkins University Press, 1996.

[12]
D. Hallac, J. Leskovec, and S. Boyd,
“Network lasso: Clustering and optimization in large graphs,“
in Proc. SIGKDD, 2015, pp. 387–396.

[13]
S. Boyd and L. Vandenberghe,
“Convex Optimization,“
Cambridge Univ. Press, Cambridge, UK, 2004.

[14]
A. Jung, A O. Hero, A. Mara, S. Jahromi, A. Heimowitz, and Y.C. Eldar.
“Semi-supervised learning in network-structured data via total
variation minimization,“
IEEE Trans. Signal Processing, 67(24), Dec. 2019.

[15]
A. BertrandMarc and M. Moonen.
“Seeing the bigger picture: How nodes can learn their place within a complex ad hoc network topology,“
IEEE Signal Processing Magazine, 30(3):71-82, May 2013.

[16]
M.C.V. Nascimento and A.C. De Carvalho.
“Spectral methods for graph clustering–a survey,“
European Journal of Operational Research, 211(2):221–231, 2011.

[17]
A. Jung and N. Tran.
“Localized linear regression in networked data,“
IEEE Signal Processing Letters, vol.26, no. 7, pp. 1090–1094, 2019.

[18]
B. Saha, A. Mandal, S.B. Tripathy , D. Mukherjee1
“Complex Networks, Communities and Clustering: A survey,“
CoRR, vol. abs/1503.06277, 2015.

[19]
B. He, Y. You, and X. Yuan.
“On the convergence of primal-dual hybrid gradient algorithm,“
SIAM J. Imaging Sci., 7(4):2526–2537, 2014.

[20]
C. Lee and D.J. Wilkinson .
“A review of stochastic block models and extensions for graph clustering,“
Applied Network Science., volume 4, Article number: 122, 2019

[21]
A. Jung.
“Clustering  in  partially  labeled  stochasticblock models via total variation minimization,“
inProc.54th Asilomar Conf.,  Signals, Systems, Computers, Pa-cific Grove, CA, Nov. 2020.

[22]
S. Cui and A. Hero and Z.-Q. Luo and J.M.F. Moura.
“Big Data over Networks,“
cup.,  Cambridge, UK. 2016.

[23]
A. Jung.
“Federated Learning over Networks for Pandemics,“
Manning.,  2021.

[24]
A . Chapelle and B. Schölkopf and A. Zien.
“Semi-Supervised Learning,“
The MIT Press., Cambridge, Massachusetts. 2006.

[25]
Y. Boykov and V. Kolmogorov.
“An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,“
IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 9, 2004.

[26]
A. Jung and M. Hulsebos.
“The Network Nullspace Property for Compressed Sensing of Big Data over Networks,“
Front. Appl. Math. Stat., 2018.

[27]
B. Nadler and N. Srebro and X. Zhou.
“Statistical Analysis of Semi-Supervised Learning: The Limit of Infinite Unlabelled Data,“
Advances in Neural Information Processing Systems 22., pages. 1330–1338, 2009.

[28]
Nadler, Boaz and Galun, Meirav.
“Fundamental Limitations of Spectral Clustering,“
Advances in Neural Information Processing Systems., B. Schölkopf and J. Platt and T. Hoffman, 2007, vol. 19, MIT Press.

[29]
A. Jung.
“Machine Learning: The Basics,“
ArXiv e-prints https://arxiv.org/abs/1805.05052., 2020.

§ TOTAL VARIATION MINIMIZATION

The construction of feature vectors (<ref>) in spectral clustering
methods is global. Indeed, the eigenvectors (<ref>) of the graph Laplacian will
typically depend on every edge in the empirical graph. Instead, we construct features in a more
local fashion by considering local clusters around seed nodes. These seed nodes might be obtained
by domain knowledge (telling us which nodes must belong to the same cluster), based on basic connectivity
properties (nodes with high degree),  or chosen randomly.

Given a set of seed nodes $\seednodes$ we solve the TV minimization problem

\begin{equation}
\label{equ_def_nLasso}
\hat{\vu}^{(\seednodes)} = \argmin_{\vu \in \mathbb{R}^{\nodes}}  \sum_{\nodeidx \in \seednodes} (1\!-\!u_{\nodeidx})^2/2\!+\! \sum_{\nodeidx \notin \seednodes} (\alpha/2) u_{\nodeidx} ^2\!+\!\regparam \| \vu \|_{\rm TV}.
\end{equation}

Here, we used the TV of a vector $\vu \in \mathbb{R}^{\nrnodes}$,

\begin{equation}
\label{eq_def_TV}
\| \vu \|_{\rm TV} = \sum_{\edge{\nodeidx}{\nodeidx'} \in \edges} \edgeweight_{\nodeidx,\nodeidx'} |u_{\nodeidx} - u_{\nodeidx'}|.
\end{equation}

Note that the TV minimization (<ref>) is parametrized by the set $\seednodes \subseteq \nodes$ of
seed nodes. Our clustering methods solve multiple instances of (<ref>), each time using another choice for the seed nodes $\seednodes$.
Section <ref> discusses approaches for choosing a useful set of seed nodes.

We have recently explored the duality between TV minimization (<ref>) and network flow optimization [10].
This duality allows to characterize the solution $\hat{\vu}$ of (<ref>) in terms of network flows.
A network flow is a vector $\edgesigvec \in \mathbb{R}^{\overrightarrow{\edges}}$ whose entries $\edgesig_{\directededge{\nodeidx}{\nodeidx'}}$
represent a flow from node $\nodeidx$ to $\nodeidx'$.

A vector $\widehat{\vu}$ solves TV minimization (<ref>) if and only if
there is a flow vector $\edgesigvec \in \mathbb{R}^{\overrightarrow{\edges}}$ such that

\begin{align}
-\sum_{\directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges}} \edgesig_{\directededge{\nodeidx}{\nodeidx'}} + \sum_{\directededge{\nodeidx'}{\nodeidx} \in \overrightarrow{\edges}}\edgesig_{\directededge{\nodeidx'}{\nodeidx}} & =  \hat{u}_{\nodeidx}\!-\!1 \mbox{ for } \nodeidx  \in \seednodes, \nonumber \\[2mm]
-\sum_{\directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges}} \edgesig_{\directededge{\nodeidx}{\nodeidx'}}
+\sum_{\directededge{\nodeidx'}{\nodeidx} \in \overrightarrow{\edges}}\edgesig_{\directededge{\nodeidx'}{\nodeidx}}& =  \alpha \hat{u}_{\nodeidx}  \mbox{ for } \nodeidx  \notin \seednodes,  \nonumber \\[2mm]
|\edgesig_{\directededge{\nodeidx}{\nodeidx'}}|  \leq \lambda \edgeweight_{\nodeidx,\nodeidx'}  \mbox{ for all } &\directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges}, \nonumber \\[2mm]
\hat{u}_{\nodeidx}\!-\!\hat{u}_{\nodeidx'}\!=\!0 \mbox{ for all } \directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges} \mbox{ with } & |\edgesig_{\directededge{\nodeidx}{\nodeidx'}}|\!<\!\lambda\edgeweight_{\nodeidx,\nodeidx'} . \label{equ_pd_optimal_non_staturated}
\end{align}

The result can be obtained by applying Fenchel duality <cit.> to TV minimization (<ref>)
and a dual minimum cost flow problem (see <cit.>).

Let us illustrate Theorem <ref> for the empirical graph in Figure <ref>.
This empirical graph is a chain graph and partitioned into two clusters $\datacluster{1}$ and $\datacluster{2}$ which
are connected by a boundary edge $b$ with weight $\edgeweight_{o}$.

Ideal Case. Assume we solve TV minimization (<ref>) for the chain graph in Figure <ref>
with a single seed node $\seednodes = \{ \nodeidx^{(1)} \}$ with $\nodeidx^{(1)} \in \datacluster{1}$. Moreover, we choose
$\regparam$ and $\alpha$ in (<ref>) such that

\begin{equation}
\label{equ_cond_alpha_lambda}
\regparam \edgeweight_{o} < 1\mbox{, and } | \datacluster{1}| (\alpha/\regparam)+ \edgeweight_{o}<1, | \datacluster{2}| \alpha \geq \regparam \edgeweight_{o}.
\end{equation}

A direct inspection of the optimality condition (<ref>) then yields the TV minimization solution

\begin{equation}
\label{equ_def_TV_min_chain}
\hat{u}_{\nodeidx} = \begin{cases} (1- \regparam\edgeweight_{o} )/ \big(1+ \alpha (|\datacluster{1}|-1) \big) & \mbox{ for } \nodeidx \in \datacluster{1} \\
\regparam\edgeweight_{o} /  \big( \alpha |\datacluster{2}| \big) & \mbox{ for } \nodeidx \in \datacluster{2} \end{cases}.
\end{equation}

Note that the vector (<ref>) is piece-wise constant over the clusters $\datacluster{1}$ and $\datacluster{2}$.
Thus, if we would use (<ref>) as (single) feature $\feature_{\nodeidx} = \hat{u}_{\nodeidx}$, basic clustering
methods would successfully recover the clusters $\datacluster{1}$ and $\datacluster{2}$.

General Case. Note that (<ref>) characterizes the solution of TV minimization (<ref>)
only when $\regparam$ and $\alpha$ are chosen such that (<ref>) is valid. However,  condition (<ref>)
is not useful in practice as it involves the size of the clusters which we would like to determine. A practical approach to choosing $\alpha$ and $\lambda$
can be based on probabilistic models for the empirical graph such as stochastic block models [21]. Alternatively, the
choice for $\alpha$ and $\lambda$ can be guided by the size of the piece $\{ \nodeidx \in \nodes: \hat{u}_{\nodeidx} = \hat{u}_{\nodeidx^{(1)}}\}$
around the seed node $\nodeidx^{(1)}$. This piece grows for increasing $\regparam$ and becomes the entire node set $\nodes$ whenever
$\regparam \edgeweight_{\nodeidx,\nodeidx'} > 1 \mbox{ for all edges } \edge{\nodeidx}{\nodeidx'} \in \edges.$

The duality between TV minimization (<ref>) and network flow optimization
is also instrumental for developing iterative methods to solve (<ref>).
Algorithm <ref> summarizes the application of a generic primal-dual method to solve (<ref>) [10].

Primal-Dual Method For TV Minimization (<ref>)

Input: $\graph=\big(\nodes,\edges,\edgeweights\big), \seednodes, \lambda, \alpha,  \nriter$

Initialize: $\hat{\vu}^{(0)}\!\defeq\!{\bf 0}$; $\hat{\vu}^{(-1)}\!\defeq\!{\bf 0}$;$\hat{\edgesigvec}^{(0)} \!\defeq\! {\bf 0}$;

Output: approximation $\widehat{\vu}$ of solution $\widehat{\vu}^{(\seednodes)}$ to (<ref>)

[1]
$\pditer = 0, \ldots,\nriter-1$

$\mbox{ {\bf for} } i\!\in\!\nodes \mbox{ {\bf do} } : \tilde{u}_{\nodeidx}  \!\defeq\! 2 \hat{u}^{(\pditer)}_{\nodeidx} - \hat{u}^{(\pditer\!-\!1)}_{\nodeidx} $

$ e = \directededge{\nodeidx}{\nodeidx'} \in \overrightarrow{\edges} $
$	\hat{\edgesig}^{(\pditer\!+\!1)}_{e} \!\defeq\!\hat{\edgesig}^{(\pditer)}_{e}\!+\! (1/2)  (\tilde{u}_{\nodeidx}\!-\!\tilde{u}_{\nodeidx'})$
$\hat{\edgesig}^{(\pditer\!+\!1)}_{e} \!\defeq\! \hat{\edgesig}_{e}^{(\pditer\!+\!1)}\!/\!\max\{1, |\hat{\edgesig}_{e}^{(\pditer\!+\!1)}|/(\regparam \edgeweight_{e}) \} $
$ \nodeidx \in \nodes $
$\hat{u}^{(\pditer\!+\!1)}_{\nodeidx}  \!\defeq\! \hat{u}^{(\pditer)}_{\nodeidx}\!-\!\gamma_{\nodeidx} \bigg[\hspace*{-1mm}\sum_{\directededge{\nodeidx}{\nodeidx'}} \hat{\edgesig}^{(\pditer\!+\!1)}_{\directededge{\nodeidx}{\nodeidx'}}  \!-\!\hspace*{-1mm}\sum_{\directededge{\nodeidx'}{\nodeidx}} \hat{\edgesig}^{(\pditer\!+\!1)}_{\directededge{\nodeidx'}{\nodeidx}} \bigg]$

$\nodeidx \in \seednodes$
$\hat{u}_{\nodeidx}^{(\pditer\!+\!1)} \!\defeq\!  \big(\gamma_{\nodeidx}\!+\!\hat{u}^{(\pditer\!+\!1)}_{\nodeidx}\big)/(\gamma_{\nodeidx}\!+\!1)$
$\hat{u}_{\nodeidx}^{(\pditer\!+\!1)} \!\defeq\! \hat{u}^{(\pditer\!+\!1)}_{\nodeidx}/(\alpha\gamma_{\nodeidx}\!+\!1)$
$\widehat{\vu} \defeq \hat{\vu}^{(\nriter)}$

The output $\widehat{\vu} \in \mathbb{R}^{\nrnodes}$ of Algorithm <ref> is an approximation to
the solution of (<ref>). We assume that the number of iterations $\nriter$ used for
Algorithm <ref> is sufficiently large such that the output of Algorithm <ref> can be considered
a (numeric) solution to (<ref>). The number $\nriter$ of iterations can be guided by
probabilistic models for the underlying empirical graph combined with the convergence rates guaranteed
by primal-dual methods [4]. Alternatively, we can tune the number of
iterations based on the final clustering result obtained by using Algorithm <ref> as a sub-routine
within our clustering method (see Algorithm <ref>).

It is instructive to interpret Algorithm <ref> as a message passing method for iteratively optimizing the network flow
$\hat{\edgesig}^{(\pditer)}_{\directededge{\nodeidx}{\nodeidx'}}$. Step <ref> enforces
the capacity constraint $| \hat{\edgesig}^{(\pditer)}_{\directededge{\nodeidx}{\nodeidx'}} | \leq \regparam \edgeweight_{\nodeidx,\nodeidx'}$.
Step <ref> adjusts the value $\hat{u}^{(\pditer)}_{\nodeidx}$ based on the
net flow into the node $\nodeidx$. In step <ref>, flow is injected into
seed nodes $\nodeidx \in \seednodes$ while in step (<ref>) flow is leaked out of remaining nodes $\nodeidx \notin \seednodes$.

§ FLOW-BASED GRAPH CLUSTERING

We are now in the position to formulate our flow-based graph clustering method as Algorithm <ref>.
This method constructs feature vectors $\featurevec$ using the solutions of TV minimization (<ref>)
for different choices of seed nodes $\seednodes$. Instead of using the values of eigenvectors
for the graph Laplacian (as used by spectral clustering), we use entries of the vector solving TV minimization (<ref>)
to construct feature vectors for each node $\nodeidx \in \nodes$.

Flow-Based Graph Clustering

Input: empirical graph $\graph$, TV min. parameters $\regparam$, $\alpha$,
number $\nrcluster$ of cluster; number $\nrseeds$ of seeds.

Output: cluster assignments $\hat{c}_{1},  \ldots , \hat{c}_{\nrnodes} \in \{1,\ldots,\nrcluster\}$

[1]
$\pditer = 1, \ldots,\nrseeds$
select new seed nodes $\seednodes$   with Algorithm <ref>
run Algorithm <ref> with $\graph,\seednodes,\regparam,\alpha$
store resulting vector in $\widehat{\vu}^{(\pditer)}$
construct node features

\begin{equation}
\label{equ_def_flow_vec_features}
\featurevec^{(\nodeidx)} = \big( \hat{u}^{(1)}_{\nodeidx}, \ldots,\hat{u}^{(\nrseeds)}_{\nodeidx} \big)^{T} \mbox{ for every node } \nodeidx \in \nodes.
\end{equation}

compute cluster assignments $\hat{c}_{\nodeidx}$ by applying k-means
to feature vectors (<ref>)

A key challenge for the successful application of Algorithm <ref> is a suitable
section of seed nodes in step <ref>. One simple
approach is to choose the set $\seednodes$ by randomly selecting a single
node $\nodeidx \in \nodes$. In general it is preferable to use more than one seed node.
However,  we must ensure that a particular selection of seed nodes $\seednodes$
contains only nodes from the same cluster.

Our numerical experiments (see Section <ref>) use a simple
heuristic method for selecting seed nodes $\seednodes$ in step (<ref>) of Algorithm <ref>.
This heuristic method is summarized in Algorithm <ref>. Algorithm <ref> constructs
a new set of seed nodes by first randomly choosing a node $\nodeidx'$ with large degree $\nodedegree{\nodeidx}$ and
then adding all neighbours of $\nodeidx'$ that have a sufficiently large number of common neighbours with $\nodeidx'$.

Select Seed Nodes $\seednodes$

Input: empirical graph $\graph$, minimum number of common neighbours $\eta$, minimum degree $d$

Output: seed nodes $\seednodes \subseteq \nodes$

[1]

initialize $\seednodes \defeq \emptyset$
determine  $\nodeidx' \defeq randomly\ select\ from\ \{\nodeidx : \nodedegree{\nodeidx} \geq d\}$
add node, $\seednodes \defeq \{ \nodeidx' \}$
each $\nodeidx''$ with $\edge{\nodeidx'}{\nodeidx''} \in \edges$
$\mathcal{D} = \{ \nodeidx''': \edge{\nodeidx'''}{\nodeidx'}, \edge{\nodeidx''}{\nodeidx'''} \in \edges \}$
$| \mathcal{D} | \geq \eta$
$\seednodes \defeq \seednodes \bigcup \{ \nodeidx'' \}$

§ NUMERICAL EXPERIMENTS

For datasets without intrinsic graphs, we construct the empirical graph by using an Euclidean distance based equation to define the similarity between data points:  $A_{i, j}:=\exp \left(-\left\|\mathbf{x}^{(i)}-\mathbf{x}^{(j)}\right\|_{2}^{2} /\left(2 \sigma^{2}\right)\right)$.

Here, $\sigma$ is a tuning parameter that chosen via cross-validation or using a probabilistic model for the data points to keep numerical stability.

§.§ Experiments with Synthetic data

A dataset [28] with two clusters, as depicted in Figure <ref>, the first cluster is a set of 2D data points drawn from Gaussian density centered at $(2,0.2)$ with diagonal covariance matrix $ 0.01*I $, the second cluster is a set of 2D data points denoting uniform density in a rectangular region: $\left\{ ( x_{1}, x_{2})  \mid 0 < x_{1}< 8, {-0.05} < x_{2} < 0 \right\}$. As shown in Figure <ref>, our method significantly outperforms spectral clustering. Parameters used for Algorithm <ref>  are $\alpha = 0.005$, $\lambda=0.01$,  $\eta=50$,  and $d=12$.

[ head to column names,
late after head=,
after line=]
=̧ 1[color=red] (, ) node $\cdot$;
=̧ 0[color=green] (, ) node $\cdot$;

(0,-1.5) – (8,-1.5) – (8,1.5) –(0,1.5) – (0,-1.5);

in -1/$-1$,0/$0$,1/$1$
(0, – (0.1, node[left=2mm] ;

in 2/$2$,4/$4$,6/$6$
(-1.5) – (-1.4) node[below=2mm] ;

[ head to column names,
late after head=,
after line=]
=̧ 1[color=red] (, ) node $\cdot$;
=̧ 0[color=green] (, ) node $\cdot$;

(0,-1.5) – (8,-1.5) – (8,1.5) –(0,1.5) – (0,-1.5);

in -1/$-1$,0/$0$,1/$1$
(0, – (0.1, node[left=2mm] ;

in 2/$2$,4/$4$,6/$6$
(-1.5) – (-1.4) node[below=2mm] ;

The left plot is the clustering result of Algorithm <ref>, the right one is the clustering result of spectral clustering [6].

§.§ Image Segmentation / Pixel Clustering

The performance of Algorithm <ref> for image segmentation/pixel clustering is tested on
some RGB images. We construct an empirical graph as mentioned in <ref> based on pixel values.  Each pixel is connected to other pixels within up to three hops.
empirical graph is forced to be sparse by removing some edges associated with small weights.
Pixels in a rectangular are set to be seed nodes. After 1000 iterations, a local cluster which
segment out the object of interest from the background is determined. As depicted in fig <ref>,
the algorithm can accurately detect which pixels belong to the object. To compare and contrast,
we also use spectral clustering to execute this task, the result in fig <ref> shows that
our algorithm out-performs spectral clustering.

The source code for the above experiments can be found at <https://github.com/YuTian8328/>.

Image Segmentation: The left plot is the original image, the middle one is the segmentation
result from Algorithm <ref>, the right one is the result from spectral clustering.