Hacker News new | past | comments | ask | show | jobs | submit login
Algebraic graph calculus (2021) (gabarro.org)
120 points by 082349872349872 on April 15, 2023 | hide | past | favorite | 21 comments



We have also covered two other forms of calculus over the the last week:

Alien calculus [0][1] Matrix Calculus [2][3]

Might as well throw in some other generalizations of the derivative [4] , it is amazing how these concepts apply to all sorts of mathematical structures once you generalize them, whlie you are probably fairly interested in math if you are reading the comments here, but on the offi chance you have not done so, look up measure theory, it is a fun concept that allows you to generalize the integral in neat ways that you'll notice has a lot of application to computer science especially vision related applications.

[0] https://news.ycombinator.com/item?id=35476236 [1] https://www.quantamagazine.org/alien-calculus-could-save-par... [2] https://news.ycombinator.com/item?id=35568311 [3] https://www.matrixcalculus.org/ [4] https://math.stackexchange.com/a/1209684


Is there a calculus for sets or multi sets?


There is the theory of containers (unrelated to the docker kind). They represent functors on sets and the differential operator on them satisfies the usual laws.

In short a container is a set of shapes and a set of positions for data in each shape. The derivative of a container is the container you get by removing one position in each shape.

An example of a container is the list container, which maps any set to the sets of lists of elements from the set. The derivative of the list is the pair of lists.

As for multisets, the bag functor is better defined on groupoids than sets. But there is a generalised notion of container for groupoids, with a similar calculus. The bag functor is special because it is its own derivative, just like the exponential function.


What do I look up to learn more? Are there online lectures or papers to get an intro on the topic?


Of course LLMs probably have sparked an interest in calculus. I have dusted of decades old knowledge, relearning the difference between a d and a δ, or what is df/dx ln(x).


> what is df/dx ln(x).

Since this may be a misunderstanding, and it's very common among my students, let me suggest that you almost certainly mean df/dx, where f(x) = ln(x); or d(ln(x))/dx; or (d/dx)(ln(x)). All of these indicate taking the derivative of ln(x) with respect to x (which is 1/x). df/dx ln(x) would be the product of the derivative of some unspecified function f with ln(x).


Yes sorry I was being a bit lazy there


One cool application of the discrete laplace operator is that we can use it to calculate the number of spanning trees of the graph by considering the determinants of the submatrices we get my removing 1 row and 1 column from the matrix!

https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem


Why author did not used geometric algebra?

The curl(u) operator, which confines vectors and vector fields to R^3, is an outer product of nabla with u [1, page 9] in geometric algebra. And as such it is defined for arbitrary number of dimensions, not just 2, 3 and 7.

[1] https://hal.sorbonne-universite.fr/hal-00920544v2/document

Matrices (and more) can also be described in GA, because they are linear operators.


Neat. I wish someone wrote this down in the language of differential forms.


This is called "discrete exterior calculus" and you can find it easily.

The idea is that k-forms are functions defined on the k-cliques of the graph. TFA is just the 1-dimensional case of this.

The 2-dimensional case would be:

0-forms: functions defined on vertices

1-forms: functions defined on edges

2-forms: functions defined on triangles

The exterior derivative is defined in a natural way, by taking differences along signed boundaries.

In the case of a triangulated surface, the Hodge dual has a nice interpretation via the dual triangulation.


Does anyone has a similar reference for directed graphs? Very little of this generalizes out of the box for directed graphs as far as I know.


It generalizes easily. The main difference is the construction of the Laplacian matrix, which won't be symmetric in a directed graph, but you can still do spectral analysis and standard matrix derivatives, diagonalization, factorizations, etc.


This exposition probably could benefit from using differential forms.


It's just funny to me how people are stumbling on things I found pieces of to solve problems years ago. Keep on keeping on thinkers



What kind of problems did you solve with it?


love getting down voted for sharing joy in mutual overlapping discovery. This happens all the time in science and in math... I was using these sort of constructs for information theoretic explorations that attempted to extend physical laws to new domains. To put it loosely I was attempting to find a simpler explanation for some of our understanding of fundamental physics. Some of it stuck, some of it sucked. It was a lot of fun though


Except your comment doesn't come across like that - it comes across as very condescending thus the downvotes...


I'm sorry it's possible to read it that way. Wasn't my intention... Not the best with words.


Try using more words: one or two concrete examples would have gone a long way.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: