summaries: The paper studies a new variant of fair clustering for different fairness (group utilitarian, group egalitarian, group leximen) and clustering objectives(k-center, k-median, k-means). The main approach is to optimize the fairness objective under the constraint that the clustering cost are bounded by some value U. The main result can be thought of as a bi-criteria approximation: If we allow that U is violated by a factor of (2+alpha) (where alpha is the approximation ratio of some clustering algorithm for the given objective) then we can get an additive approximation on the fairness objective.   In addition to this algorithmic upper bound, the authors also give a number of complexity theory lower bounds for different variants of the problem.   The authors also provide a proof-of-concept study of their algorithm.

summaries: EDIT: I increased my score following the discussions and rebuttal. The main question in the paper is how can we cluster data so that we optimize for some fairness desiderata. In other words, if we have a target for the amount of clustering cost we are aiming for, how can we find the most fair solution, subject to that cost constraints? Put differently, the authors address the problem of minimizing the amount of "unfairness" subject to the clustering cost being below a certain threshold. The two desiderata put forth by the authors in terms of fairness have to do with "group utilitarian" objective and with "group egalitarian" (they also further study a generalization called "group leximin" objective. The authors give both positive results and some impossibility results. Finally, they run some experiments to validate their findings.  These three objectives are desiderata that have been studied in the past. Briefly, the group utilitarian objective minimizes the sum of all fairness violations, whereas the group egalitarian objective minimizes the maximum fairness violation. Going a step further, the leximin (LM) objective minimizes the maximum fairness violation first, then minimizes the second worst etc.   One of the hardness results they prove is that for all three objectives, both fairly clustering and fairly assigning points to fixed centers is NP-hard.  On the positive side, they give an approximation algorithm that yields a (2+a)U-approximation where U is an exogenous parameter that is the upper bound on the clustering cost and a is the approximation ratio of a color-blind clustering algorithm. The algorithms presented for the different objectives depend on some assumptions about the sizes of the clusters. The idea behind the algorithms is to first run a color blind clustering algorithm to select centers, followed by an LP to get a fair assignment and a flow computation.  The authors perform some computational experiments on the adult and the census data sets to evaluate how their fairness guarantees look like.

summaries: The paper studies the fair clustering (with balanced clusters requirement) and the goal of authors is to achieve the “fairest” possible clustering achievable with cost at most U. The idea here is that we know that PoF can be unbounded, and it is unrealistic to assume that in practical applications we cannot sacrifice the clustering quality for fairness with no limit. An important component is how to measure the amount of unfairness and then the goal is to minimize it while not violating the upper bound on affordable clustering cost. They have defined three notions called GROUP-UTILITARIAN, GROUP-EGALITARIAN and GROUP-LEXIMIN. Basically, in fair clustering, for each color h, we are given lower and upper bounds $\alpha_h, \beta_h$ and the goal is to guarantee that in each cluster the number of point from color h is at least $\alpha_h \cdot  |C_i|$ and is at most $\beta_h \cdot |C_i|$. Now, the amount of unfairness is defined by a new set of parameters $\Delta_h$ such that instead of satisfying the fair clustering requirements exactly, we have that the number of points from color h is at least $(\alpha_h - \Delta_h) \cdot  |C_i|$ and is at most $(\beta_h + \Delta_h) \cdot |C_i|$. The authors consider $\min \max_h \Delta_h$ and $\min sum_h \Delta_h$ objectives (GROUP-LEXIMIN is a lexicographical minimizing of \Delta_h: the top priority is to minimize the min value, then among those with the same min value, minimize the second min value and so on).

summaries: This paper derives the theoretical bound of fair clustering based on porotype based algorithms. Generally speaking, the authors expect to minimize the unfairness under the given upper bound. In this paper, the authors consider two types of fairness and two fairness clustering setting. Based on this, the authors derive the upper bound of the unfairness and design the corresponding algorithm. The major contributions of this paper lie in theoretical analysis.

abstractText: Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the “price of fairness,” can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.

authors:
S. Ahmadian
A. Epasto
M. Knittel
R. Kumar
M. Mahdian
B. Moseley
P. Pham
S. Vassilvtiskii
Y. Wang

title: Fair hierarchical clustering

venue: arXiv preprint arXiv:2006.10221,

authors:
S. Ahmadian
A. Epasto
R. Kumar
M. Mahdian

title: Clustering without over-representation

venue: In International Conference on Knowledge Discovery & Data Mining (KDD),

title: Fair correlation clustering

venue: In International Conference on Artificial Intelligence and Statistics,

authors:
S. Ahmadian
A. Norouzi-Fard
O. Svensson
J. Ward

title: Better guarantees for k-means and euclidean k-median by primal-dual algorithms

venue: SIAM Journal on Computing,

authors:
D. Arthur
S. Vassilvitskii

title: k-means++: The advantages of careful seeding

venue: In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),

authors:
V. Arya
N. Garg
R. Khandekar
A. Meyerson
K. Munagala
V. Pandit

title: Local search heuristics for k-median and facility location problems

venue: SIAM Journal on computing,

authors:
A. Backurs
P. Indyk
K. Onak
B. Schieber
A. Vakilian
T. Wagner

title: Scalable fair clustering

venue: In International Conference on Machine Learning (ICML),

authors:
S. Bandyapadhyay
F.V. Fomin
K. Simonov

title: On coresets for fair clustering in metric and euclidean spaces and their applications

venue: arXiv preprint arXiv:2007.10137,

authors:
S. Barocas
M. Hardt
A. Narayanan

title: Fairness and Machine Learning

authors:
S.K. Bera
D. Chakrabarty

title: Negahbani. Fair algorithms for clustering

authors:
I.O. Bercea
M. Groß
S. Khuller
A. Kumar
C. Rösner
D.R. Schmidt
M. Schmidt

title: On the cost of essentially fair clusterings

venue: In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX-RANDOM),

authors:
D. Bertsimas
V.F. Farias
N. Trichakis

title: The price of fairness

venue: Operations Research,

authors:
M. Böhm
A. Fazzone
S. Leonardi
C. Schwiegelshohn

title: Fair clustering with multiple colors

venue: arXiv preprint arXiv:2002.07892,

authors:
F. Brandt
V. Conitzer
U. Endriss
J. Lang
A.D. Procaccia

title: Handbook of computational social choice

authors:
B. Brubach
D. Chakrabarti
J.P. Dickerson
S. Khuller
A. Srinivasan
L. Tsepenekas

title: A pairwise fair and community preserving approach to k-center clustering

authors:
B. Brubach
D. Chakrabarti
J.P. Dickerson
A. Srinivasan
L. Tsepenekas

title: Fairness, semisupervised learning, and more: A general framework for clustering with stochastic pairwise constraints

venue: In AAAI Conference on Artificial Intelligence (AAAI),

authors:
J. Buolamwini
T. Gebru

title: Gender shades: Intersectional accuracy disparities in commercial gender classification

venue: In ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT),

authors:
J. Byrka
T. Pensyl
B. Rybicki
A. Srinivasan
K. Trinh

title: An improved approximation for k-median, and positive correlation in budgeted optimization

authors:
I. Caragiannis
C. Kaklamanis
P. Kanellopoulos
M. Kyropoulou

title: The efficiency of fair division

venue: International Workshop on Internet and Network Economics (WINE),

authors:
F. Chierichetti
R. Kumar
S. Lattanzi
S. Vassilvitskii

title: Fair clustering through fairlets

authors:
J.P. Dickerson
A.D. Procaccia
T. Sandholm

title: Price of fairness in kidney exchange

venue: In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS),

authors:
S.A. Esmaeili
B. Brubach
L. Tsepenekas
J.P. Dickerson

title: Probabilistic fair clustering

title: Clustering to minimize the maximum intercluster distance

venue: Theoretical Computer Science,

authors:
G. Gunduz
E. Fokoue

title: Uci machine learning repository

venue: University of California, School of Information and Computer Science,

authors:
A. Hagberg
D. Schult
P. Swart
D. Conway
L. Séguin-Charbonneau
C. Ellison
B. Edwards
J. Torrents

title: Networkx. high productivity software for complex networks

authors:
D.S. Hochbaum
D.B. Shmoys

title: A best possible heuristic for the k-center problem

venue: Math. Oper. Res.,

title: A unified approach to approximation algorithms for bottleneck problems

venue: J. ACM,

authors:
K. Holstein
J. Wortman Vaughan
H. Daumé III
M. Dudik
H. Wallach

title: Improving fairness in machine learning systems: What do industry practitioners need

venue: In ACM Conference on Human Factors in Computing Systems (CHI),

authors:
J.N. Hooker
H.P. Williams

title: Combining equity and utilitarianism in a mathematical programming model

venue: Management Science,

authors:
K. Huang
Y. Jiang
Y. Yuan
L. Zhao

title: Modeling multiple humanitarian objectives in emergency response to large-scale disasters

venue: Transportation Research Part E: Logistics and Transportation Review,

authors:
L. Huang
S. Jiang
N. Vishnoi

title: Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems (NeurIPS), pages 7587–7598

authors:
M. Kleindessner
S. Samadi
P. Awasthi
J. Morgenstern

title: Guarantees for spectral clustering with fairness constraints

venue: In International Conference on Machine Learning,

title: Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid

venue: In Kdd,

authors:
V.S.A. Kumar
M.V. Marathe
S. Parthasarathy
A. Srinivasan

title: A unified approach to scheduling on unrelated parallel machines

authors:
N.S. Lesmana
X. Zhang
X. Bei

title: Balancing efficiency and fairness in on-demand ridesourcing

authors:
S. Liu
L.N. Vicente

title: A stochastic alternating balance k-means algorithm for fair clustering

venue: arXiv preprint arXiv:2105.14172,

authors:
S. Mahabadi
A. Vakilian

title: individual) fairness for k-clustering

authors:
N. Mattei
A. Saffidine
T. Walsh

title: Fairness in deceased organ matching

venue: In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (AIES),

authors:
D. McElfresh
J.P. Dickerson

title: Balancing lexicographic fairness and a utilitarian objective with application to kidney exchange

authors:
C. Meek
B. Thiesson
D. Heckerman

title: The learning-curve sampling method applied to model-based clustering

venue: Journal of Machine Learning Research,

authors:
V. Nanda
P. Xu
K.A. Sankararaman
J.P. Dickerson
A. Srinivasan

title: Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours

authors:
D. Saha
C. Schumann
D.C. McElfresh
J.P. Dickerson
M.L. Mazurek
M.C. Tschantz

title: Measuring non-expert comprehension of machine learning fairness metrics

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
G. Varoquaux
A. Gramfort
V. Michel
B. Thirion
O. Grisel
M. Blondel
P. Prettenhofer
R. Weiss
V. Dubourg
J. Vanderplas

title: Scikit-learn: Machine learning in python

venue: J Mach Learn Res,

authors:
I.-C. Yeh
C.-h. Lien

title: The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients

venue: Expert Systems with Applications,

authors:
I.M. Ziko
E. Granger
J. Yuan
I.B. Ayed

title: Variational fair clustering

heading: 1 Introduction

text:
Machine learning algorithms are increasingly being applied to settings that directly influence human lives. This has spurred a growing fair machine learning community [9], which develops machine learning algorithms that are made to satisfy certain fairness criteria. Choosing an appropriate definition of fairness—and even deciding if explicitly defining fairness is appropriate to begin with— is a morally-laden and application-specific decision [28, 43]. We make no normative statements here; rather, we focus on a commonly-used and often legally-backed family of fairness definitions—group fairness—in the context of clustering, arguably the most fundamental unsupervised learning problem.
A recent group-membership fairness definition, called fair clustering in the literature, has received significant interest [20, 10, 11, 2, 7, 31, 22, 8, 3, 33, 1]. In fair clustering, each point has a color that designates its group membership, and a clustering objective such as k-median or k-means is given. The goal is to find a clustering that minimizes the objective subject to the constraint that each cluster has each color represented within some pre-specified proportions. For example, there may be two colors, red and blue, and the constraint could require per-color representation between 40% and 60%.
An acknowledged fact in fair clustering—and, indeed, in many allocation and matching settings—is that the fairness (e.g., proportion) constraint could cause degradation in the clustering objective [12, 19]. A point may be assigned to a further away center (cluster) to satisfy the proportion constraint [20].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The degradation in the objective due to the imposed fairness constraint is called the price of fairness (PoF), mathematically defined as PoF = (cost of fair solution) / (cost of agnostic solution).
Unlike some examples in the literature [12, 21], the price of fairness in the case of fair clustering is unbounded, as seen in Figure 1. By enforcing a form of group fairness requiring an even split across colors in each cluster, a fair clustering algorithm would perform arbitrarily poorly as the two groups of points separate in space, while a “colorblind” algorithm would remain unchanged (bottom-left and bottom-right of Figure 1, respectively). The possibly unbounded increase in the clustering cost (unbounded price of fairness) indicates that fair clustering can yield clusters consisting of points that are far apart in the metric space instead of combining nearby points—often the main motivation behind clustering in machine learning and data
analysis. Furthermore, the legal notion of disparate impact does not force an organization to output a fair clustering if it can justify an unfair one due to “business necessity,” i.e., potential loss in quality [45, 44]. This possible conflict between the clustering objective and the fairness constraint indicates the need for fair clustering algorithms that operate in a setting where the clustering cost cannot exceed a pre-set upper bound.
Our Contributions. In this paper, we address fair clustering under an exogenous threshold on the clustering objective. We formulate the problem mathematically in a general setting that captures all of the traditional k-clustering objectives, i.e. k-center, k-median, and k-means. Throughout, we focus on two general formulations of group fairness: GROUP-UTILITARIAN and GROUP-EGALITARIAN, along with the GROUP-LEXIMIN objective which generalizes the traditional GROUP-EGALITARIAN definition. We show that these objectives lead to problems that are NP-hard in general. Further, assuming P 6= NP we derive lower bounds on the additive approximation of any polynomial time algorithm for the GROUP-UTILITARIAN and GROUP-EGALITARIAN objectives. We provide bi-criteria approximation algorithms for the GROUP-UTILITARIAN and GROUP-EGALITARIAN objectives in which the constraint has a bounded violation and the objective is bounded from the optimal value by an additive error. For the GROUP-LEXIMIN objective we provide an effective heuristic. Further, we consider other possibly more “flexible” fairness objectives, but demonstrate inapproximability results for them. Finally, we test the performance of our algorithms on a collection of datasets and see that we obtain good solutions with low “fairness violations.” We note that due to the page limit, all proofs are placed in Appendix A.

heading: 2 Related Work

text:
The metric clustering problems k-center, k-median, and k-means are fundamental in unsupervised learning and operations research. All are NP-hard with a long line of research on approximation algorithms. For k-center, two distinct algorithms achieve a 2-approximation which is tight assuming P 6= NP [26, 23, 27]. The current best approximation for k-median is a (2.675 + )-approximation in nO((1/ ) log(1/ )) time [18], and for k-means, there is a 6.357-approximation [4].
The fair clustering problem with group fairness constraints was proposed by [20]. They studied k-center and k-median in a setting with only two colors. Followup work by [11, 10, 7, 31] gave extensions to the k-means objective, more than two colors, multi-color points (i.e., intersecting demographic groups), and scalability. Other works by [38, 15, 16] look at non-group-fairness definitions; the former investigates individual fairness, while the latter two address probabilistic fairness guarantees for pairs or communities of points. The aforementioned works optimize the clustering objective subject to fairness constraints; however, satisfying the fairness constraints may come at the expense of a significant increase in the clustering objective. Accordingly [48] and very recently [37] explored the cost/fairness tradeoff, but using a multi-objective approach. Unlike our work they do not establish approximation guarantees. Further, the fairness objectives used are different from ours, i.e. in [48] the fairness objective is penalized for proportions that are not precisely equal to the population level while in [37] it is penalized for color ratios that are not equal to 1. Moreover, in [48] the cost/fairness tradeoff is a non-monotone function of a parameter which the user must adjust, while [37] only focuses on the k-means objective and provides convergence guarantees only for a smoothed version of the original problem.
We focus on the formal tradeoff between fairness and the clustering objective. We note that the clustering objective can be replaced by the price of fairness (PoF). However, in our setting, the results are clearer if we refer to the clustering objective instead of the PoF. Ultimately a higher PoF corresponds to a weakly higher fair clustering objective and vice versa. In fact, they are multiples of one another: PoF = (cost of fair solution) / (cost of agnostic solution). This tradeoff between fairness and efficiency manifested the PoF concept, in operations research by [12] and simultaneously in computer science by [19], showing general approaches to defining and measuring it. Similar to our work, others have adapted PoF as a hard constraint in emergency response [30], organ allocation [39], and rideshare [36, 42], and a partial constraint in scarce resource allocation for kidney dialysis [29] and organ exchange [40]. We propose a framework for balancing PoF for a traditional “efficient” objective in clustering, which finds application in areas such as advertising, network analysis, and data summarization.

heading: 3 Preliminaries

text:
In a clustering problem, we are given a set of points C in a metric space. A distance function d(i, j) specifies the distance between each pair of points i, j ∈ C. Furthermore, d is symmetric, non-negative, and satisfies the triangle inequality. Common clustering cost (loss) functions (e.g., k-means or
k-median) can be written as min S:|S|≤k,φ Lkp(C) = min S:|S|≤k,φ
(∑ j∈C d p(j, φ(j)) )1/p where k is the
number of clusters, S is the set of cluster centers chosen from a candidate set of centers S, and φ : C → S is an assignment function that assigns points to cluster centers. The value p determines the type of clustering, i.e., p =∞, 1, and 2 for k-center, k-median, and k-means, respectively. In fair clustering, each point has a color associated with it to indicate its group membership. Specifically, we have a function χ : C → H whereH is the set of possible colors. We denote the set of all points of color h by Ch. The fair clustering problem (FC) [20, 10, 11, 2, 7, 31, 8] is to minimize the clustering objective while satisfying additional fairness constraints:
min S:|S|≤k,φ (∑ j∈C dp(j, φ(j)) )1/p
(1a)
s.t. ∀i ∈ S,∀h ∈ H : βh| Ci | ≤ | Chi | ≤ αh| Ci | (1b)
where Ci is the set of points in cluster i and Chi ⊆ Ci is the subset of points in cluster i with color h. βh and αh are pre-specified lower and upper proportion bounds for color h, respectively. Clearly, 0 < βh ≤ αh < 1. In “unfair” clustering problems, the assignment function φ maps points to the nearest center in S, i.e., φ(j) = argmini∈S d(i, j) since this minimizes the objective. However, satisfying the added constraints in fair clustering may cause points to be assigned to clusters that are farther away. This motivates the fair assignment problem (FA), in which the set of centers S is given and the objective is to minimize the clustering cost subject to fairness constraints:
min φ (∑ j∈C dp(j, φ(j)) )1/p
(2a)
s.t. ∀i ∈ S,∀h ∈ H : βh| Ci | ≤ | Chi | ≤ αh| Ci | (2b) The only difference between the fair assignment (2) and fair clustering (1) problems is that S is not an optimization variable in the fair assignment problem.
4 Fair Clustering Under a Bounded Cost (FCBC) The fundamental idea of fair clustering under a bounded cost (FCBC) is to minimize a measure of unfairness subject to an upper bound on the clustering cost:
min Unfairness (3a) s.t. Clustering Cost ≤ Given upper bound (3b)
Next, we transform (3a) and (3b) above into a clear mathematical optimization problem. The Constraint (3b): The clustering cost is (∑ j∈C d p(j, φ(j)) )1/p . Let U denote the exogeneous
upper bound on clustering cost. Then, (3b) becomes (∑
j∈C d p(j, φ(j)) )1/p ≤ U . Note that for the case of the k-center where p = ∞, the constraint reduces to a simpler form, specifically ∀j ∈ C, d(j, φ(j)) ≤ U .
The Objective (3a): In prior work, a given clustering is considered fair if for each cluster, the proportions of each color lie within pre-specified lower and upper bounds, i.e.: ∀i ∈ S, ∀h ∈ H : βh| Ci | ≤ | Chi | ≤ αh| Ci |. However, bounding the clustering cost may make it impossible to have a fair feasible solution. Therefore, we instead set a measure of unfairness for each color and try to minimize this measure. Let ∆h denote the worst proportional violation across the clusters for a color h. Specifically, for a given clustering, ∆h ∈ [0, 1] is the minimum non-negative value such that:
∀i ∈ S : (βh −∆h)| Ci | ≤ | Chi | ≤ (αh + ∆h)| Ci |. (4)
Clearly, if ∆h = 0, then color h is within the desired proportion in every cluster. Having set ∆h to be a measure of the unfair treatment that group h receives, we are faced with the question of setting the fairness objective, for which there are many reasonable options. We consider two prominent and intuitive fairness objectives [14]:
GROUP-UTILITARIAN = min ∑ h∈H ∆h , GROUP-EGALITARIAN = min max h∈H ∆h
The GROUP-UTILITARIAN objective minimizes the sum of proportional violations for all of the colors, treating all points of a specific color as a single player in a game. The GROUP-EGALITARIAN objective minimizes the maximum proportional violation across the colors. We also consider a more generalized version of the GROUP-EGALITARIAN objective, the GROUP-LEXIMIN objective. Like GROUP-EGALITARIAN, the GROUP-LEXIMIN objective minimizes the maximum (worst) violation, but it goes further to minimizes the second-worst violation, then the third-worst violation, and so on until no further improvement can be made. We now state the fair clustering under a bounded cost problem (FCBC):
min S:|S|≤k,φ UNFAIRNESS-OBJECTIVE (5a) s.t. (∑ j∈C dp(j, φ(j)) )1/p ≤ U (5b)
where the UNFAIRNESS-OBJECTIVE could equal GROUP-UTILITARIAN, GROUP-EGALITARIAN, or GROUP-LEXIMIN. Similar to the fair assignment FA problem (2), we may define the fair assignment under a bounded cost (FABC) problem as:
min φ UNFAIRNESS-OBJECTIVE (6a) s.t. (∑ j∈C dp(j, φ(j)) )1/p ≤ U (6b)
where similarly the optimization is over the assignment function φ while the set of centers S is fixed.
5 Hardness of FCBC & FABC First, we formally state the hardness of the fair clustering FC and the fair assignment FA problems. Theorem 5.1. The fair clustering FC (1) and fair assignment FA (2) problems are NP-hard.
We now establish the hardness of fair clustering under a bounded cost FCBC and fair assignment under a bounded cost FABC. We note that these hardness results follow for all objectives (GROUPUTILITARIAN, GROUP-EGALITARIAN, and GROUP-LEXIMIN). Theorem 5.2. Fair clustering under a bounded cost FCBC and fair assignment under a bounded cost FABC are NP-hard.
Although we have shown that both the fair clustering and fair assignment problems under a bounded cost are NP-hard, the reductions rely on setting the upper bound U to a small enough value, precisely that of the optimal fair clustering cost. It seems reasonable to expect both problems to transition into being polynomial time solvable if the upper bound becomes sufficiently large. We show in Section 8 that such a result is not easy to establish and would lead to a true approximation for fair clustering which is yet to be produced in the fair clustering literature for arbitrary metric spaces and arbitrary lower and upper color proportion bounds.
For a given clustering cost U , there are many clusterings (solutions) of cost not exceeding U . Let SU be the set of those solutions, i.e. if (St, φt) ∈ SU , then (St, φt) is a clustering with a cost that does not exceed U . Further, let Lt be the size of the smallest non-empty cluster1 in the clustering (St, φt),
1An empty cluster is a cluster with no points assigned to it. This could happen if for example the assignment function φ does not map any point to a a given center including the center itself.
then we define L(U) to be the size of the smallest cluster across all clusterings of cost not exceeding U , i.e. L(U) = min(St,φt)∈SU Lt. Clearly, for U1 and U2 such that U2 ≥ U1, then L(U2) ≤ L(U1) since SU1 ⊆ SU2 . We can conclude the following fact from the definition of L(U): Fact 5.1. For a given upper bound U , no clustering with cost less than or equal to U can have less than L(U) many points in a non-empty cluster.
We show that the quantity L(U) plays a fundamental role. In fact, lower bounds on the additive approximation2 for the proportional violations and fairness objectives are related to L(U) as shown in the following theorem:
Theorem 5.3. For a given instance of the FCBC or FABC problem with an arbitrary upper bound U , unless P = NP no polynomial time algorithm can produce a solution with a cost not exceeding U that satisfies any of the following conditions: (a) The proportional violation of any color h ∈ H is ∆h < 1 8L(U) . (b) The additive approximation for the GROUP-UTILITARIAN objective is less than
|H | 8L(U) . (c) The additive approximation for the GROUP-EGALITARIAN objective is less than 1 8L(U) .
6 Algorithms for FCBC
Our main result for the FCBC problem is the following theorem which follows as a direct consequence of the guarantees of Theorems 6.2, 6.4, 6.5, 6.6, and 6.7:
Theorem 6.1. For any clustering objective, given a boundU on the clustering cost, Algorithm 1 solves the fair clustering under a bounded cost FCBC problem at a cost of at most U ′ = (2 + α)U where α is the approximation ratio of the color-blind clustering algorithm. The additive approximation is |H |( + 2L(U ′) ) for the GROUP-UTILITARIAN objective and + 2 L(U ′) for the GROUP-EGALITARIAN objective.
From the theorem above, it is clear that the additive approximation guarantees we have improve when the cost does not permit small clusters. Indeed, in the absence of outlier points and for reasonable values of k, small clusters are unlikely to exist. Further, empirically we verify the smallest cluster size and find that the smallest cluster size is 159 points (see Section 9.3). See Appendix C for more discussion.
We now provide our general algorithm for fair clustering under a bounded cost FCBC which we denote by ALG-FCBC(U,UNFAIRNESS-OBJECTIVE) where we have made explicit reference to the dependence of ALG-FCBC on the given cost upper bound U and the desired UNFAIRNESSOBJECTIVE which could either be the GROUP-UTILITARIAN,GROUP-EGALITARIAN, or GROUPLEXIMIN objective.
ALG-FCBC(U,UNFAIRNESS-OBJECTIVE) (see Algorithm 1) involves two steps, in step (1): we use a color-blind approximation algorithm to find the cluster centers S, in step (2): we call the algorithm ALG-FABC(S,U ′,UNFAIRNESS-OBJECTIVE) for the FABC problem. It should be noted that we have fed ALG-FABC the set of centers S from step (1), further the cost upper bound for ALG-FABC is set to U ′ = (2 + α)U while the UNFAIRNESS-OBJECTIVE remains unchanged. We further note that ALG-FABC will have the same clustering objective as ALG-FCBC, e.g. if ALG-FCBC is given the k-median objective so well ALG-FABC.
Clearly, from algorithm ALG-FCBC the FCBC problem is closely related to the FABC problem. In fact, we establish the following general theorem for all clustering objectives: k-center, k-median, and k-means that shows that an algorithm which solves the FABC problem with provable guarantees can be used to solve the FCBC problem with provable guarantees:
Theorem 6.2. For any clustering objective and both the GROUP-UTILITARIAN and GROUPEGALITARIAN objectives, given an algorithm that solves fair assignment under a bounded cost FABC with additive approximation µ, the fair clustering under a bounded cost FCBC problem can be solved with an additive approximation of µ and at a cost of at most (2 + α)U , where α is the approximation ratio of the color-blind clustering algorithm.
2An algorithm for a minimization problem with additive approximation µ > 0, returns a value for the objective that is at most OPT +µ where OPT is the optimal value.
Algorithm 1 :ALG-FCBC(U,UNFAIRNESS-OBJECTIVE) 1: Choose a set of centers S by running a color-blind clustering algorithm of approximation ratio α. 2: Set U ′ = (2 + α)U and call ALG-FABC(S,U ′,UNFAIRNESS-OBJECTIVE)

heading: 6.1 Fair Assignment Under a Bounded Cost

text:
Algorithm block 2 shows the steps of our algorithm ALG-FABC for the FABC objective. In step (1): we search for the optimal proportional violations given the bound on the clustering cost U using LPs. Having found the near-optimal solution, in step (2): we round the possibly fractional solution to a feasible integer solution using a netowk flow algorithm. We note that the details of the search done in step (1) depend on the objective, i.e., GROUP-UTILITARIAN or GROUP-EGALITARIAN.
Algorithm 2 :ALG-FABC(S,U,UNFAIRNESS-OBJECTIVE) 1: Given the UNFAIRNESS-OBJECTIVE, search for the optimal proportion violation values ∆h at a
cost upper bound of U using the feasibility LPs of (7). 2: Apply network flow rounding to the LP solution with the optimal value. 3: return the set of centers S and the assignment function φ (resulting from the rounded LP
solution).
We note that in fair assignment under a bounded cost FABC the set of centers S has already been chosen and the optimization is done only over the assignment φ of points to centers. We let xij be a decision variable that equals 1 if point j is assigned to center i ∈ S and 0 otherwise. Note that the values of xij are a way to represent the assignment function φ. Regardless of the objective that is being minimized, the following set of constraints must hold:∑
i,j
dp(i, j)xij ≤ Up (7a)
∀j ∈ C : ∑ i∈S xij = 1, xij ∈ [0, 1] (7b)
∀h ∈ H : ∆h ∈ [0, 1] (7c)
∀h ∈ H, ∀i ∈ S : (βh −∆h) (∑ j∈C xij ) ≤ ∑ j∈Ch xij ≤ (αh + ∆h) (∑ j∈C xij )
(7d)
For the k-center problem, the first constraint (7a) is replaced by ∀j ∈ C : xij = 0 if d(i, j) > U . Note that in the above we have xij ∈ [0, 1] which is a relaxation of xij ∈ {0, 1}, as the latter would result in an intractable mixed-integer program. With our variables being xij and ∆h it is reasonable to consider a convex optimization approach. That is, we could choose to minimize the objective GROUP-UTILITARIAN or the objective GROUP-EGALITARIAN with our set of constraints being (7). Looking at the form of the GROUP-UTILITARIAN and the GROUP-EGALITARIAN objectives, it is not difficult to see that they are linear (and therefore convex) in the parameters xij and ∆h, however as the following theorem shows, the constraint set (7) is not convex. In fact, either of the proportion bounds alone in constraint (7d) would lead to a non-convex set. The non-convexity of the constraint set implies that the resulting optimization problem would also be non-convex: Theorem 6.3. The constraint set (7) is not convex. Although the constraint set (7) is not convex, if we fix the values of ∆h then we clearly have a simple feasibility LP with variables xij . We therefore take an approach where for a given objective (GROUP-UTILITARIAN or GROUP-EGALITARIAN), we search for the corresponding optimal values of ∆h by running the feasibility LP of (7). Note that with a given set of values for ∆h, we can obtain the corresponding value for the GROUP-UTILITARIAN or GROUP-EGALITARIAN objectives and therefore the LP does not need an objective: a feasibility check suffices. Further, since we only use non-trivial values for ∆h ∈ [0, 1], constraint (7c) can be omitted. Sections 6.1.1 and 6.1.2 detail how we use the feasibility LPs of (7) to obtain LP solutions that are approximately optimal (having bounded additive approximation from the optimal) for the GROUP-UTILITARIAN and GROUPEGALITARIAN objectives, respectively. Since these resulting LP solutions could contain fractional values, i.e., it is possible to have a value xij /∈ {0, 1}, the approximately optimal LP solution would have to be rounded to an integral solution. This rounding further degrades the approximation, but we show that this degradation is not large and can be bounded. The details of the rounding are shown
in Section 6.1.3. The search algorithms of Sections 6.1.1 and 6.1.2, followed by the rounding of Section 6.1.3, lead to an algorithm for FABC.

heading: 6.1.1 Search Algorithm for the GROUP-UTILITARIAN Objective

text:
We are searching for the optimal proportional violations ∆∗h ∈ [0, 1] for the GROUP-UTILITARIAN objective. The first step we take is to discretize the space by a parameter ∈ (0, 1). For convenience, we set = 1r where r ∈ Z
+, i.e., r is a positive integer. Accordingly, instead of interacting with the continuous interval [0, 1] for the proportional violations, we instead interact with E = { , 2 , . . . , . . . , ( 1 − 1) , 1}, with |E | = 1 . Therefore, we have a set of ( 1 ) |H | many possibilities for the proportional violations and we can obtain the optimal solution for the GROUP-UTILITARIAN objective through exhaustive search by checking the feasibility of LP (7) and picking the feasible combination of proportional violations which leads to the smallest value for the GROUP-UTILITARIAN objective, i.e., GROUP-UTILITARIAN = ∑ h∈H∆h.
The above approach would take O(( 1 ) |H |) many LP runs. Therefore, we show a faster search that tries instead O(( 1 ) |H |−1). The key to this speed up comes from the fact that for the two-color case,
we only need to evaluate O( 1 ) many possibilities. Theorem 6.4. For FABC with GROUP-UTILITARIAN objective, we can use O (( 1 )|H |−1) –many
LP runs to obtain an LP solution with additive approximation |H | . Furthermore, for the important two-color case with symmetric upper and lower bounds we show a search algorithm that requires only O ( log 1 ) LP runs. The two color case with symmetric upper
and lower bounds is that where the two colors h1 and h2 are present with proportions r1 and r2 in the dataset, and the proportion bounds are set to αi = ri + λi, βi = ri − λi for i ∈ {1, 2} and some valid λ1, λ2 ∈ [0, 1]. The key observation for the two-color symmetric case is that the proportion of one color implies the proportion of the other; hence, we can run binary search over the set E . Theorem 6.5. For FABC with two colors, symmetric lower & upper bounds, and the GROUPUTILITARIAN objective, we can use O ( log( 1 ) ) –many LP runs to get a solution with an additive
approximation of |H | = 2 .

heading: 6.1.2 Search Algorithm for GROUP-EGALITARIAN and GROUP-LEXIMIN Objectives

text:
For the GROUP-EGALITARIAN objective we follow the same discretization step as for the GROUPUTILITARIAN objective. For all colors, their violation ∆h is set to the same value and the optimal solution is found simply by doing binary search over the set E by running the feasibility LP (7). Theorem 6.6. For FABC with the GROUP-EGALITARIAN objective, we can use O ( log ( 1 )) –
many LP runs to get a solution with an additive approximation of .
We provide a heuristic algorithm for the GROUP-LEXIMIN objective; a rough sketch follows. In the first step, it obtains the GROUP-EGALITARIAN solution. Then, it proceeds by finding a color that cannot improve beyond the current optimal violation; if more than one color is found, then one of these colors is randomly picked. The algorithm then looks for the optimal violation for the remaining colors, having the violations of the previous colors fixed. These steps are followed until no color can have its proportional violation improved. See Appendix B for the full details.
6.1.3 The Rounding Scheme and ALG-FABC Guarantees
Having obtained the optimal LP solutions for either the GROUP-UTILITARIAN or GROUPEGALITARIAN objectives, we now round the solutions to integral values at a bounded increase to the additive approximation. To do the rounding, we apply the network flow method of [11] (see Appendix E for details), although other rounding methods are applicable. Given the LP solution xij and its associated proportional violations ∆h, if we denote the rounded integral solution by x̄ij and ∆̄h, then network-flow rounding guarantees the following: (i) ∑ i,j d p(i, j)x̄ij ≤ ∑ i,j d p(i, j)xij .
(ii) ∀i ∈ [k] : ⌊∑
j∈C xij ⌋ ≤ ∑ j∈C x̄ij ≤ ⌈∑ j∈C xij ⌉ . (iii) ∀h ∈ H,∀i ∈ [k] : ⌊∑ j∈Ch xij ⌋ ≤∑
j∈Ch x̄ij ≤ ⌈∑ j∈Ch xij ⌉ .
Property (i) ensures that the clustering objective will not increase beyond the LP value, and thus, provided the LP cost does not exceed the upper bound on the cost U , the cost of the rounded assignment will not exceed U as well. Property (ii) guarantees that the total number of points assigned to a cluster will not vary by more than 1 point. Property (iii) guarantees that the total number of points of a given color assigned to a cluster will not vary by more than 1 point. We can use the above properties along with with the lower bound on the size of any cluster L(U) to establish the following theorem: Theorem 6.7. For the FABC problem, the rounded solution has cost of at most U and an additive approximation of: (1) |H |( + 2L(U) ) for the GROUP-UTILITARIAN objective and (2) + 2 L(U) for the GROUP-EGALITARIAN objective.
Recalling the additive approximation lower bounds of Theorem 5.3 for the FABC problem, we see that we obtain a solution for FABC of cost at most U with near-optimal additive approximation. Specifically, our additive approximations for the GROUP-UTILITARIAN and GROUP-EGALITARIAN are 2|H |L(U) and 2 L(U) compared to their lower bounds of |H | 8L(U) and 1 8L(U) , respectively.
A randomized extension. We also briefly mention a randomized rounding algorithm’s guarantees; the description of this algorithm (which is motivated by an approach of [35]) is detailed in Appendix G. This algorithm efficiently constructs a random vector X̄ with entries X̄i,j in {0, 1} such that: (a) Properties (ii) and (iii) hold with probability 1, and (b) the expected value E[X̄i,j ] equals xi,j for all (i, j). This has three consequences: (b1) the fairness guarantee for each cluster and color become better in expectation: for all h ∈ H and for all i ∈ S: E[ ∑ j∈Ch X̄ij ] indeed lies between
(βh − ∆h) (∑ j∈C xij ) and (αh + ∆h) (∑ j∈C xij ) . (b2) The expected value of the objective function (the left-hand side in (i)) is at most the right-hand side of (i). (b3) Even if we had multiple linear objective functions, they will all be preserved in expectation.

heading: 7 Fairness Across the Clusters is not Possible

text:
It is tempting to modify both the GROUP-UTILITARIAN and GROUP-EGALITARIAN (or GROUPLEXIMIN) objectives to sum across the clusters instead of taking the maximum violation across the clusters. More specifically, we can replace the objectives by the following: GROUP-UTILITARIAN-SUM, which equals
∑ h∈H,i∈[k] ∆ih, and GROUP-EGALITARIAN-SUM, which
equals min max h∈H ∑ i∈[k] ∆ih, where ∆ i h is the violation of color h in cluster i; clearly the previously-
considered violation ∆h is max i∈[k] ∆ih. It can be seen that such an objective is more flexible. For example, the maximum violations might occur in a cluster that cannot be improved within the given bound on the clustering cost, while it may be possible to improve it for other clusters. The original GROUP-UTILITARIAN and GROUP-EGALITARIAN objectives may bring no improvement in such a situation but their above modifications could. We prove a negative result. Specifically, while we were able to approximate FABC by small additive values for the original objectives (Theorem 6.7), for the new objectives we cannot efficiently approximate the FABC problems within even relatively-large additive approximations: Theorem 7.1. For FABC, the objectives GROUP-UTILITARIAN-SUM and GROUP-EGALITARIANSUM that sum across the clusters cannot be approximated in polynomial time to within an additive approximation of O(nδ) where δ is a constant in [0, 1), unless P = NP .

heading: 8 Solving the Problem Optimally for a Large-Enough Cost

text:
It seems reasonable to assume that when the upper bound on the cost U is large enough, the problem becomes solvable in polynomial time. It is not difficult to devise such guarantees for some special cases. However, in the theorem below we show that an algorithm with such a guarantee would imply a true approximation3 for fair clustering. Since fair clustering has remained resistant to a true polynomial-time approximation for general metric spaces and arbitrary lower- and upper- proportion bounds [13, 8], this suggests that the problem is indeed nontrivial. Furthermore, we also show the converse, i.e., a true approximation algorithm for fair clustering would imply an exact algorithm for fair clustering under a bounded cost FCBC.
3A true approximation algorithm yields a solution that approximates the optimal objective value with no constraint violation, in contrast to bi-criteria algorithms which have a bounded violation in the constraints.
Theorem 8.1. Suppose that there is a polynomial time algorithm which can obtain the optimal solution for FCBC for the upper bound of U if U ≥ α(I) OPTcb(I) where I is a specific instance of FCBC and OPTcb(I) is the optimal cost of its color-blind clustering. Then we have a true polynomial time approximation algorithm for fair clustering. Further, a true polynomial time α′(I)-approximation algorithm for fair clustering implies that FCBC can be solved optimally in polynomial time for U ≥ α′(I) OPTFC(I). 9 Experiments We validate our algorithms on datasets from the UCI repository [24]. The results here are for k-means clustering; additional experiments are in Appendix F.
Hardware, Software, and Algorithms: We only use commodity hardware for all experiments with our programs running on Python 3.6. For the color-blind k-means clustering, we use the k-means++ algorithm [5] which has an approximation ratio of O(log k). Our LPs are solved using CPLEX [32]. Scikit-learn [46] is called for subroutines such as k-means++. The network-flow rounding is handled using NetworkX [25].
Datasets: We use all 32,561 entries of the Adult dataset [34]. For the Census1990 dataset [41], because of its large size (over 2 million points) we sub-sample the dataset to a range similar to that considered in the fair clustering literature [20, 10]; specifically we use 20,000 data points. We also use the CreditCard dataset [47] which has 30,000 points (results are in Appendix F). For all datasets we use the numeric attributes to assign the coordinates in the space and the distance between any two points is set to the Euclidean distance. Setting and Measurements: Each color h ∈ H has proportion rh, i.e., rh = | C h | | C | . We set the upper and lower bounds for each color to αh = (1 + δ)rh and βh = (1− δ)rh. This means that each cluster should have each color with the same proportion as in the population with a possible deviation of δ.
We first do color-blind clustering using the k-means++ algorithm. The clustering cost we obtain from the k-means++ is a proxy of the lowest possible value of the clustering cost (since the hardness of clustering forbids the calculation of the true optimal value). We gradually increase the upper bound cost from the color-blind cost to higher values and for each choice of the upper bound, we minimize either the GROUP-UTILITARIAN or GROUP-LEXIMIN objectives using our algorithms and record the objective value. For better interpretation, instead of showing the value of the upper bound, we show its ratio to the color-blind clustering, which is the PoF. Further, for all experiments we discretize the space by = 127 < 0.008.

heading: 9.1 GROUP-UTILITARIAN Experiments

text:
We use the Adult and Census1990 datasets with self-reported gender (male or female) as the attribute. We note that both datasets explicitly use categorical labels for this socially-complex concept, and acknowledge that this is reductive [17]. Figure 2 shows the PoF versus the achieved GROUPUTILITARIAN objective, with δ = 0.1. As expected, as the price of fairness increases (higher bound on the cost), we can further minimize the proportional violations. Eventually the GROUPUTILITARIAN objective becomes less than 0.1 and even very close to zero. We also observe that at a given cost upper bound, we can achieve lower values for the GROUP-UTILITARIAN objective when the number of clusters (k) is lower.
9.2 GROUP-EGALITARIAN and GROUP-LEXIMIN Experiments
We again use the Adult and Census1990 datasets. However, for Adult, we set the fairness attribute to race which—in this dataset, and with the same inherent social caveats as the categorization of gender—has 5 groups (colors). For Census1990, we set the fairness attribute to age where we have three age groups.4 We set δ = 0.05 and k = 10 for Adult and δ = 0.1 and k = 5 for Census1990. Figure 3 shows the results of our algorithm. We notice that for some colors smaller violations are harder to achieve and we need to set the maximum allowable clustering cost to larger values to reduce their violations.

heading: 9.3 Checking the Size of the Smallest Cluster

text:
As mentioned in Section 5 and Theorem 6.1 our approximations are dependent on the size of the smallest cluster in the solution. While it is not tractable to obtain the value of L(U) for a given U , we can still empirically check the size of the smallest cluster in the cost bounded clusterings we obtain. We note that, throughout, we do not impose any lower bound on the cluster size in our algorithm. For the above experiments we considered, we find that the minimum cluster size (across all choices of k) are as follows: Adult (159 points), Census1990 (171 points). The fact that the size of the smallest cluster is large means that we are achieving small (accurate) additive approximations with near-optimal objective values and when we obtain a large objective value it is because of how stringent the cost upper bound is.
Acknowledgments. Seyed Esmaeili and John Dickerson were supported in part by NSF CAREER Award IIS-1846237, NSF D-ISN Award #2039862, NSF Award CCF-1852352, NIH R01 Award NLM-013039-01, NIST MSE Award #20126334, DARPA GARD #HR00112020007, DoD WHS Award #HQ003420F0035, and a Google Faculty Research award. Aravind Srinivasan was supported in part by NSF awards CCF-1749864 and CCF-1918749, as well as research awards from Adobe, Amazon, and Google. We thank the anonymous reviewers for helpful feedback.

title: Fair Clustering Under a Bounded Cost


summaries: The authors in this work study the limitations of edge independent models which are an important class of graph generative models. Specifically the authors demonstrate that such models are inherently limited in their ability to generate graphs with high triangle and other subgraph properties which are typical in real-world graphs. The authors demonstrate the main results of their work via empirical experiments.

summaries: The main result is that certain structural properties of an edge-independent graph model, e.g. the expected number of triangles, are upper bounded by how strongly the graphs sampled from the model are expected to be overlapping.   Experiments on two datasets empirically confirm that several edge-independent baseline models require a high amount of overlap in their sampled graphs in order to match the number of triangles in the original graph dataset.

summaries: In this paper, the authors analyze some properties of edge-independent generative graph models: given a fixed matrix of connection probabilities in [0,1], the edges are drawn independently. This is the basis for several methods to generate graphs that match certain statistics of a given input graph (*over the same set of nodes*). It has been observed that such models tend to produce less triangles (or generally k-cycles) than real graphs. In light of this, the authors show that the expected density of k-cycles can be bounded by the model *overlap*, which measures how much the model tends to memorize only one graph, as opposed to generating a large variety of graphs. The proofs are simple and are mostly given in the main paper. They also show that their bounds are tight, up to multiplicative constants, for Erdös-Rényi graphs, which are models with minimal overlap. Numerical experiments are performed to compare several edge-independent models, including a novel one introduced in the paper, and illustrate the (negative) theoretical findings.

summaries: This paper studies edge independent graph models that covers a large family of graph models. The main result is that it shows under certain conditions, the edge independent models are limited to generate graphs with high triangle and other subgraph densities, which are commonly observed in real world networks. Based on this finding, this paper propose a way to generate graph which balances matching the original graph and memorizing the graph statistics.

abstractText: Why do many modern neural-network-based graph generative models fail to reproduce typical real-world network characteristics, such as high triangle density? In this work we study the limitations of edge independent random graph models, in which each edge is added to the graph independently with some probability. Such models include both the classic Erdös-Rényi and stochastic block models, as well as modern generative models such as NetGAN, variational graph autoencoders, and CELL. We prove that subject to a bounded overlap condition, which ensures that the model does not simply memorize a single graph, edge independent models are inherently limited in their ability to generate graphs with high triangle and other subgraph densities. Notably, such high densities are known to appear in real-world social networks and other graphs. We complement our negative results with a simple generative model that balances overlap and accuracy, performing comparably to more complex models in reconstructing many graph statistics.

authors:
Lada A Adamic
Natalie Glance

title: The political blogosphere and the 2004 us election: divided they blog

venue: In Proceedings of the 3rd International Workshop on Link Discovery,

authors:
Albert-László Barabási
Réka Albert

title: Emergence of scaling in random networks

authors:
Aleksandar Bojchevski
Oleksandr Shchur
Daniel Zügner
Stephan Günnemann

title: NetGAN: Generating graphs via random walks

authors:
Sudhanshu Chanpuriya
Cameron Musco
Konstantinos Sotiropoulos
Charalampos E Tsourakakis

title: Node embeddings and exact low-rank representations of complex networks

venue: Advances in Neural Information Processing Systems

authors:
Fan Chung
Linyuan Lu

title: The average distances in random graphs with given expected degrees

venue: Proceedings of the National Academy of Sciences,

authors:
Jesper Dall
Michael Christensen

title: Random geometric graphs

venue: Physical Review E,

title: Maximum entropy models and subjective interestingness: an application to tiles in binary databases

venue: Data Mining and Knowledge Discovery,

authors:
Nicola De Cao
Thomas Kipf

title: MolGAN: An implicit generative model for small molecular graphs

venue: ICML Deep Generative Models Workshop,

authors:
Nurcan Durak
Ali Pinar
Tamara G Kolda
C Seshadhri

title: Degree relations of triangles in real-world networks and graph models

venue: In Proceedings of the 21st ACM International Conference on Information and Knowledge Management,

authors:
Paul Erdös
Alfréd Rényi

title: On the evolution of random graphs

venue: Publications of the Mathematical Institute of the Hungarian Academy of Sciences,

authors:
David Gleich
Leonid Zhukov
Pavel Berkhin

title: Fast parallel pagerank: A linear system approach

venue: Yahoo! Research Technical Report,

authors:
Anna Goldenberg
Alice X Zheng
Stephen E Fienberg
Edoardo M Airoldi

title: A survey of statistical network models

authors:
Aditya Grover
Aaron Zweig
Stefano Ermon

title: Graphite: Iterative generative modeling of graphs

venue: In Proceedings of the 36th International Conference on Machine Learning (ICML),

title: Random effects models for network data

venue: In Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers. Citeseer,

title: Bilinear mixed-effects models for dyadic data

venue: Journal of the American Statistical Association,

authors:
Thomas N Kipf
Max Welling

title: Variational graph auto-encoders

venue: NeurIPS Bayesian Deep Learning Workshop,

authors:
Jure Leskovec
Deepayan Chakrabarti
Jon Kleinberg
Christos Faloutsos
Zoubin Ghahramani

title: Kronecker graphs: an approach to modeling networks

authors:
Yujia Li
Oriol Vinyals
Chris Dyer
Razvan Pascanu
Peter Battaglia

title: Learning deep generative models of graphs

authors:
Renjie Liao
Yujia Li
Yang Song
Shenlong Wang
Charlie Nash
William L Hamilton
David Duvenaud
Raquel Urtasun
Richard S Zemel

title: Efficient graph generation with graph recurrent attention

authors:
Zhuang Ma
Zongming Ma
Hongsong Yuan

title: Universal latent space model fitting for large networks with edge covariates

venue: J. Mach. Learn. Res.,

authors:
Ali Pinar
Comandur Seshadhri
Tamara G Kolda

title: The similarity between stochastic Kronecker and Chung-Lu graph models

venue: In Proceedings of the 2012 SIAM International Conference on Data Mining,

authors:
Luca Rendsburg
Holger Heidrich
Ulrike von Luxburg

title: NetGAN without GAN: From random walks to low-rank approximations

venue: In Proceedings of the 37th International Conference on Machine Learning (ICML),

authors:
Ryan A. Rossi
Nesreen K. Ahmed

title: The network data repository with interactive graph analytics and visualization

venue: In AAAI,

authors:
Alessandra Sala
Lili Cao
Christo Wilson
Robert Zablit
Haitao Zheng
Ben Y Zhao

title: Measurement-calibrated graph models for social network experiments

venue: In Proceedings of the 19th International World Wide Web Conference (WWW),

authors:
Prithviraj Sen
Galileo Namata
Mustafa Bilgic
Lise Getoor
Brian Galligher
Tina Eliassi- Rad

title: Collective classification in network data

venue: AI Magazine,

authors:
C Seshadhri
Aneesh Sharma
Andrew Stolman
Ashish Goel

title: The impossibility of low-rank representations for triangle-rich complex networks

authors:
Martin Simonovsky
Nikos Komodakis

title: GraphVAE: Towards generation of small graphs using variational autoencoders

venue: In International Conference on Artificial Neural Networks,

authors:
Tom AB Snijders
Krzysztof Nowicki

title: Estimation and prediction for stochastic blockmodels for graphs with latent block structure

venue: Journal of Classification,

authors:
Chris Stark
Bobby-Joe Breitkreutz
Andrew Chatr-Aryamontri
Lorrie Boucher
Rose Oughtred
Michael S Livstone
Julie Nixon
Kimberly Van Auken
Xiaodong Wang
Xiaoqi Shi

title: The BioGRID interaction database: 2011 update

venue: Nucleic Acids Research,

authors:
Duncan J Watts
Steven H Strogatz

title: Collective dynamics of ‘small-world’networks

authors:
Jiaxuan You
Rex Ying
Xiang Ren
William Hamilton
Jure Leskovec

title: GraphRNN: Generating realistic graphs with deep auto-regressive models

venue: In Proceedings of the 35th International Conference on Machine Learning (ICML),

heading: 1 Introduction

text:
Our work centers on edge independent graph models, in which each edge (i, j) is added to the graph independently with some probability Pij ∈ [0, 1]. Formally, Definition 1 (Edge Independent Graph Model). For any symmetric matrix P ∈ [0, 1]n×n let G(P ) be the distribution over undirected unweighted graphs where G ∼ G(P ) contains edge (i, j) independently, with probability Pij . I.e., p(G) = ∏ (i,j)∈E(G) Pij · ∏ (i,j)/∈E(G)(1− Pij).
Edge independent models encompass many classic random graph models. This includes the ErdösRényi model, where for all i ̸= j, Pij = p for some fixed p ∈ [0, 1] [10]. It also includes the stochastic block model where Pij = p if two nodes are in the same community and Pij = q if two nodes are in different communities for some fixed p, q ∈ [0, 1] with q < p [29]. Other examples include e.g., the Chung-Lu configuration model [5], stochastic Kronecker graphs [17].
Recently, significant attention has focused on graph generative models, which seek to learn a distribution over graphs that share similar properties to a given training graph, or set of graphs. Many algorithms parameterize this distribution as an edge independent model or closely related distribution. E.g., NetGAN and the closely related CELL model both produce P ∈ [0, 1]n×n and then sample edges independently without replacement with probabilities proportional to its entries, ensuring that at least one edge is sampled adjacent to each node [3, 23]. Variational Graph Autoencoders (VGAE), GraphVAE, Graphite, and MolGAN are also all based on edge independent models [16, 28, 8, 13].
Given their popularity in both classical and modern graph generative models, it is natural to ask:
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
How suited are edge independent models to modeling real-world networks. Are they able to capture features such as power-law degree distributions, small-world properties, and high clustering coefficients (triangle densities)?

heading: 1.1 Impossibility Results for Edge Independent Models

text:
In this work we focus on the ability of edge independent models to generate graphs with high triangle, or other small subgraph densities. High triangle density (equivalently, a high clustering coefficient) is a well-known hallmark of real-work networks [31, 25, 9] and has been the focus of recent work exploring the power and limitations of edge-independent graph models [27, 4].
It is clear that edge independent models can generate triangle dense graphs. In particular, P ∈ [0, 1]n×n in Def. 1 can be set to the binary adjacency matrix of any undirected graph, and G(P ) will generate that graph with probability 1, no matter how triangle dense it is. However, this would not be a particularly interesting generative model – ideally G(P ) should generate a wide range of graphs. To capture this intuitive notion, we define the overlap of an edge-independent model, which is closely related to the overlap stopping criterion for training used in training graph generative models [3, 23].
Definition 2 (Expected Overlap). For symmetric P ∈ [0, 1]n×n let V (P ) def= EG∼G(P )|E(G)| and
Ov(P ) def = EG1,G2∼G(P )|E(G1) ∩ E(G2)| V (P ) .
That is, for any P ∈ [0, 1]n×n, Ov(P ) ∈ [0, 1] is the ratio of the expected number of edges shared by two graphs drawn independently from G(P ) to the expected number of edges in a graph drawn from G(P ). In one extreme, when P is a binary adjacency matrix, Ov(P ) = 1, and our generative model has simply memorized a single graph. In the other, if Pij = p for all i ̸= j (i.e., G(P ) is Erdös-Rényi), Ov(P ) = p. This is the minimum possible overlap when V (P ) = p · ( n 2 ) .
Our main result is that for any edge independent model with bounded overlap, G ∼ G(P ) cannot have too many triangles in expectation. In particular: Theorem 1 (Main Result – Expected Triangles). For a graph G, let ∆(G) denote the number of triangles in G. Consider symmetric P ∈ [0, 1]n×n.
EG∼G(P ) [∆(G)] ≤ √ 2
3 ·Ov(P )3/2 · V (P )3/2.
As an example, consider the setting where the distribution generates sparse graphs, with V (P ) = Θ(n). Theorem 1 shows that whenever Ov(P ) = o(1/n1/3), EG∼G(P )∆(G) = o(n) – i.e. the graph is very triangle sparse with the number of triangles sublinear in the number of nodes. This verifies that an Erdös-Rényi graph cannot achieve simultaneously linear number of edges (i.e., Ov(P ) = O(1/n) ) and super-linear number of triangles (i.e., Ov(P ) = Ω(1/n1/3)) under our proposed lens of viewing generative models.
We extend Theorem 1 to give similar bounds for the density of squares and other k-cycles (Thm. 4), as well as for the global clustering coefficient (Thm. 6). In all cases we show that our bounds are tight – e.g., in the triangle case, there is indeed an edge independent model with EG∼G(P ) [∆(G)] = Θ ( Ov(P )3/2 · V (P )3/2 ) , matching the lower bound in Theorem 1.

heading: 1.2 Empirical Findings

text:
Our theoretical results help explain why, despite performing well in a variety of other metrics, edge independent graph generative models have been reported to generate graphs with many fewer triangles and squares on average than the real-world graphs that they are trained on. Rendsburg et al. [23] test a suite of these models, including their own CELL model and the related NetGAN model [3]. Of all these models, when trained on the CORA-ML graph with 2,802 triangles and 14,268 squares, none is able to generate graphs with more than 1,461 triangles and 6,880 squares on average. Similar gaps are observed for a number of other graphs. Rendsburg et al. also report that the triangle count increases as their notion of overlap (closely related to Def. 2) increases. Theorem 1 demonstrates that this underestimation of triangle count, and its connection to overlap is inherent to all edge independent models, no matter how refined a method used to learn the underlying probability matrix P .
While our theoretical results bound the performance of any edge independent model, there may still be variation in how specific models trade-off overlap and realistic graph generation. To better understand this trade-off, we introduce two simple models with easily tunable overlap as baselines. One is based on reproducing the degree sequence of the original graph; the other, which is even simpler, is based on reproducing the volume. In both models, P is a weighted average of the input graph adjacency matrix and a probability matrix of minimal complexity which matches either the input degrees or the volume. In the latter case, to match just the volume, we simply use an Erdös-Rényi graph. In the former case, to match the degree sequence, we introduce our own model, the odds product model; this model is similar to the Chung-Lu configuration model [5], but, unlike Chung-Lu, is able to match degree sequences of real-world graphs with high maximum degree. We find that these simple baselines are often competitive with more complex models like CELL in terms of matching key graph statistics, like triangle count and clustering coefficient, at similar levels of overlap.

heading: 1.3 Related Work

text:
Existing impossibility results. Our work is inspired by that of Seshadhri et al. [27], which also proves limitations on the ability of edge independent models to represent triangle dense graphs. They show that if P = max(0,min(1, XXT )) where X ∈ Rn×k for k ≪ n and the max and min are applied entrywise, then G ∼ G(P ) cannot have many triangles adjacent to low-degree nodes in expectation. This setting arises commonly when P is generated using low-dimensional node embeddings – represented by the rows of X . Chanpuriya et al. [4], show that in a slightly more general model, where P = max(0,min(1, XY T )), this lower bound no longer holds – X,Y ∈ Rn×k can be chosen so that P is the binary adjacency matrix of any graph with maximum degree upper bounded by O(k) – no matter how triangle dense that graph is. Thus, even such low-rank edge independent models can represent triangle dense graphs – by memorizing a single one. In the appendix, we prove a similar result when P is generated from the CELL model of [23], which simplifies NetGAN [3].
Our results show that this trade-off between the ability to capture triangle density and memorization is inherent – even without any low-rank constraint, edge independent models with low overlap simply cannot represent graphs with high triangle or other small subgraph density.
It is well understood that specific edge independent models, e.g., Erdös-Rényi graphs, the Chung-Lu model, and stochastic Kronecker graphs, do not capture many properties of real-world networks, including high triangle density [31, 22]. Our results can be viewed as a generalization of these observations, to all edge independent models with low overlap. Despite the limitations of classic models, edge independent models are still very prevalent in today’s literature on graph generative models. Our more general results make clear the limitations of this approach.
Non-independent models. While edge independent models are very prevalent in the literature, many important models do not fit into this framework. Classic models include the Barabási–Albert and other preferential attachment models [2], Watts–Strogatz small-world graphs [31], and random geometric graphs [6]. Many of these models were introduced directly in response to shortcomings of classic edge independent models, including their inability to produce high triangle densities
More recent graph generative models include GraphRNN [32] and a number of other works [19, 20]. Our impossibility results do not apply to such models, and in fact suggest that perhaps they may be preferable to edge independent models, if a distribution over graphs with high triangle density is desired. A very interesting direction for future work would be to prove limitations on broad classes of non-independent models, and perhaps to understand exactly what type of correlation amongst edges is needed to generate graphs with both low overlap 1and hallmark features of real-world networks.

heading: 2 Impossibility Results for Edge Independent Models

text:
We now prove our main results on the limitations of edge independent models with bounded overlap. We start with a simple lemma that will be central in all our proofs.
Lemma 2. For any symmetric P ∈ [0, 1]n×n, ∥P∥ 2 F
2 ≤ Ov(P ) · V (P ) ≤ ∥P∥ 2 F .
1We note that for non-edge independent models, the measure of overlap as defined earlier should be adapted to take into account the order (permutation) of the vertices in the final graph. In particular, the overlap in this case should be the maximum value of it over any permutation of the vertex set.
Proof. Let I[(i, j) ∈ G] be the 0, 1 indicator random variable that an edge (i, j) appears in the graph G. Ov(P ) · V (P ) = EG1,G2∼G(P )|E(G1) ∩ E(G2)|. By linearity of expectation and the independence of G1 and G2 we have,
Ov(P ) · V (P ) = EG1,G2∼G(P ) ∑ i≤j I[(i, j) ∈ G1] · I[(i, j) ∈ G2] = ∑ i≤j P 2ij .
The bound follows since P is symmetric. Note that the lower bound ∥P∥ 2 F
2 ≤ Ov(P ) · V (P ) is an equality if P is 0 on the diagonal – i.e., there is no probability of self loops.

heading: 2.1 Triangles

text:
Lemma 2 connects Ov(P ) · V (P ) to ∥P∥2F and in turn the eigenvalue spectrum of P since ∥P∥2F =∑n i=1 λi(P )
2, where λ1(P ), . . . , λn(P ) ∈ R are the eigenvalues of P . The expected number of triangles in G ∼ G(P ) can be written in terms of this spectrum as well, allowing us to relate overlap to this expected triangle count, and prove our main theorem (Theorem 1), restated below.
Theorem 1. For a graph G, let ∆(G) denote the number of triangles in G. Consider symmetric P ∈ [0, 1]n×n.
EG∼G(P ) [∆(G)] ≤ √ 2
3 ·Ov(P )3/2 · V (P )3/2.
Proof. By linearity of expectation,
EG∼G(P ) [∆(G)] = 1
6 n∑ i=1 n∑ j=1 n∑ k=1 Pr [(i, j) ∈ E(G) ∩ (j, k) ∈ E(G) ∩ (k, i) ∈ E(G)]
= 1
6 n∑ i=1 n∑ j=1 n∑ k=1 PijPjkPki = 1 6 tr(P 3) = 1 6 n∑ i=1 λi(P ) 3. (1)
Letting λ1(P ) denote the largest magnitude eigenvalue of P , we can in turn bound
tr(P 3) ≤ |λ1(P )| · n∑
i=1
λi(P ) 2 = |λ1(P )| · ∥P∥2F .
Since |λ1(P )| ≤ ∥P∥F , this gives via Lemma 2
tr(P 3) ≤ ∥P∥3F ≤ 2 √ 2 ·Ov(P )3/2 · V (P )3/2.
Combining this bound with (1) completes the theorem.
The bound of Theorem 1 is tight up to constants, for any possible value of Ov(P ). The tight example is when P is simply an Erdös-Rényi graph.
Theorem 3 (Tightness of Expected Triangle Bound). For any γ ∈ (0, 1], there exists a symmetric P ∈ [0, 1]n×n with Ov(P ) = γ and EG∼G(P )[∆(G)] = Θ(γ3/2 · V (P )3/2). Proof. Let Pij = γ for all i ̸= j. We have V (P ) = γ · ( n 2 ) and Ov(P ) · V (P ) = γ2 · ( n 2 ) Thus, Ov(P ) = γ. Further, by linearity of expectation,
EG∼G(P )[∆(G)] = γ3 · ( n
3
) = Θ(γ3 · n3) = Θ(γ3/2 · V (P )3/2).
We note that another example when Theorem 1 is tight is when P is a union of a fixed clique on Θ(γ · n) nodes and an Erdös-Rényi graph with connection probability 1/n on the rest of the nodes.
2.2 Squares and Other k-cycles
We can extend Thm. 1 to bound the expected number of k-cycles in G ∼ G(P ) in terms of Ov(P ). Theorem 4 (Bound on Expected k-cycles). For a graph G, let Ck(G) denote the number of k-cycles in G. Consider symmetric P ∈ [0, 1]n×n.
EG∼G(P ) [Ck(G)] ≤ 2k/2
2k ·Ov(P )k/2 · V (P )k/2.
Proof. For notational simplicity, we focus on k = 4. The proof directly extends to general k. C4(G) is the number of non-backtracking 4-cycles in G (i.e. squares), which can be written as
EG∼G(P ) [C4(G)] = 1
8 · n∑ i=1 ∑ j∈[n]\i ∑ k∈[n]\{i,j} ∑ ℓ∈[n]\{i,j,k} PijPjkPkℓPℓi.
The 1/8 factor accounts for the fact that in the sum, each square is counted 8 times – once for each potential starting vector i and once of each direction it may be traversed. For general k-cycles this factor would be 12k . We then can bound
EG∼G(P ) [C4(G)] ≤ 1 8 · ∑ i∈[n] ∑ j∈[n] ∑ k∈[n] ∑ ℓ∈[n] PijPjkPkℓPℓi = 1 8 · tr(P 4).
For general k-cycles this bound would be EG∼G(P ) [Ck(G)] ≤ 12k tr(P k). This in turn gives
EG∼G(P ) [Ck(G)] ≤ 1
2k · |λ1(P )|k−2 · ∥P∥2F ≤
1
2k ∥P∥kF ≤
2k/2
2k Ov(P )k/2 · V (P )k/2,
where the last bound follows from Lemma 2. This completes the theorem..
It is not hard to see that Theorem 4 is also tight up to a constant depending on k for any overlap γ ∈ (0, 1], also for an Erdös-Rényi graph with connection probability γ. Theorem 5 (Tightness of Expected k-cycle Bound). For any γ ∈ (0, 1], there exists P ∈ [0, 1]n×n
with Ov(P ) = γ and EG∼G(P )[Ck(G)] = Θ ( γk/2·V (P )k/2 k! ) .

heading: 2.3 Clustering Coefficient

text:
Theorem 1 shows that the expected number of triangles generated by an edge independent model is bounded in terms of the model’s overlap. Intuitively, we thus expect that graphs generated by the edge independent model will have low global clustering coefficient, which is the fraction of wedges in the graph that are closed into triangles [31]. Definition 3 (Global Clustering Coefficient). For a graph G with ∆(G) triangles, no self-loops, and node degrees d1, d2, . . . , dn, the global clustering coefficient is given by
C(G) = 3∆(G)∑n
i=1 di(di − 1) .
We extend Theorem 1 to give a bound on EG∼G(P ) [C(G)] in terms of Ov(P ). The proof, given in Appendix A, is related, but more complex due to the ∑n i=1 di(di − 1) in the denominator of C(G). Theorem 6 (Bound on Expected Clustering Coefficient). Consider symmetric P ∈ [0, 1]n×n with zeros on the diagonal and with V (P ) ≥ 2n.
EG∼G(P ) [C(G)] = O ( Ov(P )3/2 · n V (P )1/2 ) .
Thus, to have a constant clustering coefficient for a graph with O(n) edges in expectation, we need Ov(P ) = Ω(1/n1/3). Note that the requirement of V (P ) ≥ 2n is very mild – it means that the expected average degree is at least 1.
As with our triangle bound, Theorem 6 is tight when G(P ) is just an Erdös-Rényi distribution.
Theorem 7 (Tightness of Expected Clustering Coefficient Bound). For any γ ∈ (0, 1], there exists P ∈ [0, 1]n×n with zeros on the diagonal, Ov(P ) ≤ γ and EG∼G(P )[C(G)] = Θ ( γ3/2·n V (P )1/2 ) . Proof. Let Pij = γ for all i ̸= j. We have V (P ) = γ · ( n 2 ) = Θ(γn2) and Ov(P ) = γ. Additionally,
E[∆(G)] = Θ(γ3 · n3), and, if n is large enough with respect to γ, with very high probability,∑n i=1 di(di − 1) ≤ ∑n i=1 d 2 i = O(γ 2n3). This gives:
EG∼G(P )[C(G)] = Θ(γ) = Θ ( γ3/2 · n γ1/2 · n ) = Θ ( γ3/2 · n V (P )1/2 ) .

heading: 3 Baseline Edge Independent Models

text:
We now shift from proving theoretical limitations of edge independent models to empirically evaluating the tradeoff between overlap and performance for a number of particular models. Given an input adjacency matrix A ∈ {0, 1}n×n, these generative models produce a P ∈ [0, 1]n×n, samples from which should match various graph statistics of A, such as the triangle count, clustering coefficient, and assortativity. At the same time, P should ideally have lower overlap so that the model does not just memorize the original graph. We propose two simple generative models as baselines to more complicated existing models – in both the level of overlap is easily tuned. Our first baseline, the odds product model, is based on just matching the degree sequence of A; more simple still, the second baseline computes P as a linear function of A, just matching its volume.
Odds product model. In this model, each node is assigned a logit ℓ ∈ R, and the probability of adding an edge between nodes i and j is Pij = σ(ℓi + ℓj), where σ is the logistic function. We fit the model by finding a vector ℓ ∈ Rn of logits, with one logit for each node, such that the reconstructed network has the same expected degrees (i.e. row and column sums) as the original graph. We note that this model can be seen as a special case of the MaxEnt [7] and random-effects [21, 14, 15] models. In the context of directed graphs, ℓi has been called the expansiveness or popularity of node i [12].
For adjacency matrix A ∈ {0, 1}n×n, we denote its degree sequence by d = A1 ∈ Rn, where 1 is the all-ones vector of length n. Similarly, the degree sequence of the model is d̂ = P1. We pose fitting the model as a root-finding problem: we seek ℓ ∈ Rn such that the degree errors are zero, that is, d̂− d = 0. We use the multivariate Newton-Raphson method to solve this root-finding problem. To apply Newton-Raphson, we need the Jacobian matrix J of derivatives of the degree errors with respect to the entries of ℓ. Since d does not vary with ℓ, these derivatives are exactly ∂d̂i∂ℓj . Letting δij be 1 if i = j and 0 otherwise (i.e. the Kronecker delta), we compute in Appendix A,
∂d̂i ∂ℓj
= Pij (1− Pij) + δij ∑
k∈[n] Pik (1− Pik) .
In Algorithm 1, we provide pseudocode for the fully Jacobian matrix J and for implementing NewtonRaphson method to compute P . We do not have a proof that Algorithm 1 always converges and produces ℓ which exactly reproduces in the inut degree sequence. However, the algorithm converged on all test cases, and proving that it always converges would be an interesting future direction.
Our odds product model can be viewed as a variant of the Chung-Lu configuration model [5], which is also based on degree sequence matching. However, but our model comes without a certain restriction on the maximum degree: in Chung-Lu, it is assumed that the degrees of all nodes are bounded above by the square root of the volume of the graph, that is, di ≤ √ V (A) for all nodes i. Given this
restriction, each node is assigned a weight wi = di/ √ V (A), and the probability of adding edge (i, j) is Pij = wiwj . Since the weights are all in [0, 1], they can be interpreted as probabilities, and the probability of adding an edge between two nodes is the product of the two nodes’ probabilities.
Our odds product model works similarly, but instead of a probability, for each node, there is an associated odds, that is, a value in (0,∞), and the odds of adding an edge between two nodes is the product of the two nodes’ odds. There is a one-to-one-to-one relationship between probability p ∈ [0, 1], odds o = p1−p ∈ [0,∞), and logit ℓ = ln(o) ∈ (−∞,+∞). We outlined above how our
Algorithm 1 Fitting the odds product model input graphical degree sequence d ∈ Rn, error threshold ϵ output symmetric matrix P ∈ (0, 1)n×n with row/column sums approximately d
1: ℓ← 0 ▷ ℓ ∈ Rn is the vector of logits, initialized to all zeros 2: P ← σ ( ℓ1⊤ + 1ℓ⊤ ) ▷ σ is the logistic function applied entrywise, and 1 is the all-ones column vector of length n 3: d̃← P1 ▷ degree sequence of P 4: while ∥d̃− d∥2 > ϵ do 5: B ← P ◦ ( 11⊤ − P ) ▷ ◦ is an entrywise product 6: J ← B + diag (B1) ▷ diag is the diagonal matrix with the input vector along its diagonal 7: ℓ← ℓ− J−1 ( d̃− d ) ▷ rather than inverting J , we solve this linear system
8: P ← σ ( ℓ1⊤ + 1ℓ⊤ ) 9: d̃← P1
10: end while 11: return P
model is based on adding logits associated with each node; since the odds is the exponentiation of the logit, the model can equally be viewed as multiplying odds associated with nodes.
Varying overlap in the odds product model. We propose a simple method to control the trade-off between overlap and accuracy in matching the input graph statistics in the odds product model. Given the original adjacency matrix A and the P generated by the odds product model to match the degree sequence of A, we use a convex combination of P and A. That is, we use P̃ = (1 − ω)P + ωA, where 0 ≤ ω ≤ 1. As ω increases to 1, P̃ approaches a model which returns the original graph with high certainty; hence high ω produce P̃ with high overlap which closely match graph statistics, while low ω produce P̃ with lower overlap which may diverge from A in some statistics. Note that since P̃ is a convex combination of adjacency matrices with the expected degree sequence of A, P̃ also has the same expected degree sequence regardless of the value of ω.
Linear model. As an even simpler baseline, we also propose and evaluate the following model: we produce an Erdös-Rényi model P with the same expected volume as the original graph A, then return a convex combination P̃ of P and A. In particular, each entry of P is V (A)/n2, and, as with the odds product model, P̃ = (1− ω)P + ωA, where 0 ≤ ω ≤ 1. This model can alternatively be seen as producing a P̃ by lowering each entry of A which is 1 to some probability α, and raising each entry of A which is 0 to a probability β, with α ≥ β, such that the volume is conserved.

heading: 4 Experimental Results

text: We now present our evaluations of different edge independent graph generative models in terms of the tradeoff achieved between overlap and performance in generating graphs with similar key statistics to an input network. These experiments highlight the strengths and limitations of each model, as well as the overall limitations of this class, as established by our theoretical bounds.

heading: 4.1 Methods

text:
We compare our proposed models from Section 3 with a number of existing models described below
1. CELL [23] (Cross-Entropy Low-rank Logits) An alternative to the popular NetGAN method [3] which strips the proposed architecture of deep leaning components and achieves comparable performance in significantly less time, via a low-rank approximation approach. To control overlap, we follow the approach of the original paper, halting training once the generated graph exceeds a specified overlap threshold with the input graph. We set the rank parameter to a value that allows us to get up to 75% overlap (typical values are 16 and 32).
2. TSVD (Truncated Singular Value Decomposition) A classic spectral method which computes a rank-k approximation of the adjacency matrix using truncated SVD. As in [27], the resulting matrix is clipped to [0,1] to yield P . Overlap is controlled by varying k.
CCOP, HDOP, and Linear all produce edge probability matrices P with the same volume, V (G), in expectation as the original adjacency matrix. For TSVD, letting L be the low-rank approximation of the adjacency matrix, we learn a scalar shift parameter σ using Newton’s method such that P = max(0,min(1, L + σ)) has volume V (G). We then generate new networks from the edge independent distribution G(P ) (Def. 1). For CELL, we follow the authors’ approach of generating V (G) edges without replacement - an edge (i, j) is added with probability proportional to Pij).
We sample 5 networks from each distribution and report the average for every statistic. For implementation details and code, see the supplemental material.

heading: 4.2 Datasets and network statistics

text:
For evaluation we use seven popular datasets with varied structure, from triangle-rich social networks to planar road networks – see Table 1. We treat each network as undirected and keep its largest connected component. In the main text we present results on three of the networks, POLBLOGS, CITESEER, and WEB-EDU. POLBLOGS is a collection of political blogs and the links between them. CITESEER is a graph of papers from six scientific categories and the citations among them. Finally, WEB-EDU is a web-graph from educational institutions. Descriptions of other networks and results on them are deferred to the appendix.
We evaluate performance in matching the following key network statistics:
1. Pearson correlation of the degree sequences of the input and the generated network.
2. Maximum degree over all nodes.
3. Exponent of a power-law distribution fit to the degree sequence.
4. Assortativity, a measure that captures the preference of nodes to attach to others with similar degree (ranging from -1 to 1).
5. Pearson correlation of the triangle sequence (number of triangles a node participates in).
6. Total triangle count (analyzed theoretically in Thm. 1).
7. Global clustering coefficient (defined in Def. 3 and analyzed theoretically in Thm. 6).
8. Characteristic path length (average path length between any two nodes).

heading: 4.3 Results

text:
The theoretical results from Section 2 highlight a key weakness of edge independent generative models: they cannot generate many triangles (or other higher-order locally dense areas), without
having high overlap and thus not generating a diversity of graphs. We observe that these theoretical findings hold in practice – generally speaking, all models tested tend to significantly underestimate triangle count and global clustering coefficient, as well as inaccurately match the triangle degree sequence, when overlap is low. See Figures 1, 2, and 3 for results on the POLBLOGS, CITESEER, and WEB-EDU networks. As overlap increases, performance in reconstructing these metrics does as well, as expected.
All methods are able to capture certain network characteristics accurately, even at low overlap. Even for a relatively small overlap (less than 0.2), the CCOP and HDOP methods accurately capture the degree sequences of the true networks (as they are designed to do). These methods, especially HDOP which fixes edges from high degree nodes, often outperform more sophisticated methods like CELL in terms of triangle density and triangle degree sequence correlation. On the other hand, CELL seems to do a somewhat better job capturing global features, like the characteristic path length. TSVD provides a fair compromise – it performs better than CELL in terms of degree sequence and triangle counts, but worse in terms of characteristic path length. In general, it is the method that gives the best results when the overlap is extremely small, appearing to be less sensitive to the variation in overlap.
Broadly speaking, all methods do reasonably well in matching the power-law degree distribution of the networks, even when they do not match the actual degree sequence closely. With the exception of WEB-EDU, they tend to underestimate the characteristic path length (see additional plots in the supplemental). This is perhaps not surprising due to the independent random edge connections, however it would be interesting to understand more theoretically.

heading: 5 Conclusion

text:
Our theoretical results prove limitations on the ability of any edge independent graph generative model to produce networks that match the high triangle densities of real-world graphs, while still generating a diverse set of networks, with low model overlap. These results match empirical findings that popular edge independent models indeed systematically underestimate triangle density, clustering coefficient, and related measures. Despite the popularity of edge independent models, many nonindependent models, such as graph RNNs [32] have been proposed. An interesting future direction would be to study the representative power and limitations of such models, giving general theoretical results that provide a foundation for the study of graph generative models.
Acknowledgments and Disclosure of Funding
CT acknowledges support from Intesa Sanpaolo Innovation Center. CM was partially supported by NSF grants no. 1763618 and 2046235 and an Adobe Research Grant. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

title: On the Power of Edge Independent Graph Models